Institut de la Francophonie pour l’Informatique
MEMOIRE DE FIN D’ETUDES
MASTER D’INFORMATIQUE

Probl`
eme de tourn´
ees de
v´
ehicules avec livraisons divisibles
par
NGUYEN Thanh Tuan
Responsable de stage:
Sophie MICHEL-LOYAL
Ce stage a ´et´e r´ealis´e au sein de l’´equipe
REAOPT de l’INRIA
Hano¨ı, 2008


` ma famille
A


Remerciements
Tout d’abord, je tiens `a remercier ma famille qui m’a soutenu dans mes ´etudes et aussi dans mon stage.
Je tiens `a remercier l’Institut de la Francophonie pour l’Informatique qui me permet d’effectuer mon Master et de faire
ce stage en France.
Je tiens a` remercier Madame Sophie Michel-Loyal pour m’avoir
dirig´e dans mes travaux tout au long de mon stage. Je la remercie de ses conseils et encouragements.
Je remercie tous les professeurs, les doctorants du Laboratoire Math´ematique Appliqu´ees du Havre, Monsieur Fran¸cois
Vanderbeck, C´edric Joncour et les membres de l’´equipe REALOPT - INRIA qui m’ont donn´e les meilleurs supports toute
la dur´ee de mon stage.

Merci enfin `a mes camarades de promotion 12 IFI qui m’ont
donn´e les meilleurs sentiments dans mes ´etudes a` l’IFI.

i


R´
esum´
e
Dans le probl`eme de tourn´ees de v´ehicules (Vehicle Routing
Problem - VRP) une flotte de v´ehicules est disponible pour
servir un ensemble de clients avec la demande connue. Chaque
client est n´ecessaire pour ˆetre visit´e exactement par un v´ehicule et l’objectif est de r´eduire la distance totale voyag´ee. Dans
Le probl`eme de tourn´ees de v´ehicules avec livraisons divisibles
(Split Delivery Vehicle Routing Problem - SDVRP) la restriction que chaque client doit ˆetre visit´e exactement une fois est
supprim´ee, c’est-`a-dire, des livraisons divisibles sont autoris´ees,
plusieurs v´ehicules peuvent ˆetre utilis´es pour satisfaire la demande de chaque client. Dans cette m´emoire, nous pr´esentons
un ´etat de l’art de SDVRP et l’approche de la g´en´eration de
colonnes pour le SDVRP qui a ´et´e impl´ement´ee avec la plateˇ
forme BapCod. Des r´esultats num´eriques montrent lSefficacit´
e
de la m´ethode propos´ee.
Mots cl´
es : Le probl`eme de tourn´ees de v´ehicules, Le probl`eme de tourn´ees de v´ehicules avec livraisons divisibles, Recherche Op´erationnelle, G´en´eration de Colonnes.

ii


Abstract
In the classical Vehicle Routing Problem (VRP) a fleet of

capacitated vehicles is available to serve a set of customers with
known demand. Each customer is required to be visited by
exactly one vehicle and the objective is to minimize the total
distance traveled. In the Split Delivery Vehicle Routing Problem (SDVRP) the restriction that each customer has to be
visited exactly once is removed, i.e., split deliveries are allowed, the demand of each customer can be fulfilled by several
vehicles.. In this report we present a survey of the state-of-theart on the SDVRP and a column generation approach which
is implemented for the SDVRP with the place-form BapCod.
Computational results show the effectiveness of the proposed
method.
Keywords: Vehicle Routing Problem, Split Delivery Vehicle Routing Problem, Operations Research, Column Generation.

iii


Table des mati`
eres
Remerciements

i

R´
esum´
e

ii

Abstract

iii


Table des mati`
eres

iv

Table des figures

vi

Introduction
0.1 Equipe REALOPT - Reformulations et algorithmes
pour l’Optimisation combinatoire . . . . . . . .
0.2 Description du stage . . . . . . . . . . . . . . .
0.2.1 Objectifs d´etaill´es du stage . . . . . . . .
0.2.2 Organisation du rapport . . . . . . . . .
1 Le probl`
eme de tourn´
ees de v´
ehicules avec livraisons divisibles
1.1 Introduction . . . . . . . . . . . . . . . . . . . .
1.2 D´efinition et formulation du probl`eme . . . . . .
1.3 Propri´et´es et complexit´e . . . . . . . . . . . . .
1.3.1 La complexit´e . . . . . . . . . . . . . . .
1.3.2 Les propri´et´es . . . . . . . . . . . . . . .
1.3.3 Analyse au pire cas . . . . . . . . . . . .
1.3.4 Un exemple . . . . . . . . . . . . . . . .
iv

1
1

2
3
4

6
6
7
10
10
11
14
14


`
TABLE DES MATIERES

v

2 G´
en´
eration de Colonnes et Reformulations
2.1 Introduction . . . . . . . . . . . . . . . . . . . .
2.2 La g´en´eration de colonnes . . . . . . . . . . . .
2.3 La reformulation du SDVRP . . . . . . . . . . .
2.3.1 La reformulation en g´en´eration de colonnes
2.3.2 L’algorithme de g´en´eration de colonnes .

16
16

18
21
21
23

3 Impl´
ementation et Test´
e
3.1 BAPCOD - a generic Branch-And-Price Code
3.2 Impl´ementation . . . . . . . . . . . . . . . . .
3.2.1 Codes . . . . . . . . . . . . . . . . . .
3.2.2 Instances . . . . . . . . . . . . . . . .
3.2.3 R´esultats . . . . . . . . . . . . . . . .

25
25
26
27
27
28

.
.
.
.
.

Conclusion et Perspectives

30


Bibliographie

32

A Un exemple d’instance

35

B Codes de SDVRP dans BapCod

36


Table des figures
0.1
0.2
0.3

Un exemple du TSP . . . . . . . . . . . . . . . . .
Un exemple du VRP . . . . . . . . . . . . . . . . .
Un exemple du SDVRP . . . . . . . . . . . . . . .

3
4
5

1.1
1.2


Un cycle 4-split . . . . . . . . . . . . . . . . . . . .
Un exemple de VRP et SDVRP . . . . . . . . . . .

12
15

2.1

L’algorithme de g´en´eration de colonnes . . . . . . .

24

3.1
3.2

R´esultats . . . . . . . . . . . . . . . . . . . . . . . 28
Le changement de borne duale dans l’instance ”test02” 28

vi


Introduction
0.1

Equipe REALOPT - Reformulations
et algorithmes pour l’Optimisation
combinatoire

Ce stage a ´et´e r´ealis´e au sein de l’´equipe REAOPT de l’INRIA.
Pr´

esentation de l’´
equipe de recherche
L’´equipe REALOPT commune avec le LaBRI (CNRS/Universit´e
de Bordeaux 1/ENSEIRB) et l’IMB (CNRS/Universit´es de Bordeaux 1 et 2). L’objectif de l’´equipe est de travailler sur la
qualit´e des formulations de probl`emes d’optimisation combinatoire. S’approche consiste a` combiner des techniques avanc´ees
telles que l’approche poly´edrale, l’approche de d´ecomposition
Lagrangienne, et les techniques venant de l’optimisation nonlin´eaire et de la th´eorie des graphes. En partenariat avec des
industriels, l’´equipe REALOPT travaille sur des applications
complexes en logistique (probl`emes de tourn´ees), en planification de la production et ordonnancement des tˆaches, conception
et gestion des r´eseaux et des horaires, et sur des probl`emes de
d´ecoupe et de placement.

1


TABLE DES FIGURES

2

Axes de recherche
Le projet de l’´equipe rassemble des expertises compl´ementaires en optimisation combinatoire : programmation en nombres
entiers (´etudes poly´edrales, m´ethode de ”branch-and-price-andcut ”), programmation quadratique (”semi-definite-programming”),
et th´eorie des graphes (mod´elisation dans les graphes et exploitation de r´esultats pour r´eduire l’espace des solutions). REALOPT d´eveloppe des solutions approch´ees aux probl`emes de
grande taille et des heuristiques primales bas´ees sur des approches de programmation math´ematiques.

0.2

Description du stage

Le sujet du stage

Le probl`eme du Voyageur de Commerce (Traveling Salesman Problem - TSP) est un des probl`emes d’optimisation combinatoire les plus connus, Il pose le probl`eme suivant; Avec seul
v´ehicule partir d’un d´epˆot, trouver un chemin de longueur totale minimale qui passe exactement une fois par chaque client
et revienne au d´epˆot. (voir figure 0.1).
Le probl`eme de tourne´es de v´ehicules (Vehicle Routing Problem - VRP) est une version tendue du Probl`eme du Voyageur
de Commerce, qui consiste visiter des clients partis d’un d´epˆot
et au moyen d’une flotte de v´ehicules, avec un coˆ
ut minimal
(voir figure 0.2).
Le probl`eme de tourn´ees de v´ehicules avec livraisons divisibles
(Split Delivery Vehicle Routing Problem - SDVRP) est un assouplissement du VRP o`
u il s’autorise que plusieurs v´ehicules
peuvent ˆetre utilis´es pour satisfaire la demande de chaque client
(voir figure 0.3), si elle r´eduit les coˆ
uts globaux. Cette relaxation est tr`es importante si la demande de chaque client peut


TABLE DES FIGURES

3

Fig. 0.1: Un exemple du TSP
ˆetre sup´erieure `a la capacit´e de v´ehicule.
Le SDVRP a ´et´e introduit par Dror et Trudeau ([13], [14]), qui
ont soulign´e les propri´et´es des solutions optimales et ont propos´es une heuristique de recherche locale. Depuis lors, plusieurs
heuristiques ont ´et´e d´evelopp´ees pour le SDVRP. Ce stage ´etudie une approche pour r´esoudre le SDVRP : la m´ethode de g´en´eration de colonnes.

0.2.1

Objectifs d´
etaill´

es du stage

Les objectifs d´etaill´es sont :
´
- Etudier
l’´etat de l’art du SDVRP, la formulation, les propri´et´es, la compl`exit´e...
- Comprendre la m´ethode de g´en´eration de colonnes, reformuler le probl`eme.
´
- Etudier
la plate-forme BapCod, sur laquelle, impl´ementer
l’algorithme de g´en´eration de colonnes propos´ee pour le SD-


TABLE DES FIGURES

4

Fig. 0.2: Un exemple du VRP
VRP.
- Tester et comparer la formulation originale et la reformulation de g´en´eration de colonnes.

0.2.2

Organisation du rapport

Le rapport est organis´e comme suit : Nous allons d’abord
adresser a` l’´etat de l’art du SDVRP, une formulation programmation math´ematique du SDVRP, la complexit´e et les propri´et´es du probl`eme. Nous allons pr´esenter, dans la chapitre 2, les
approches pour r´esoudre le SDVRP, et la m´ethode de g´en´eration de colonnes, sur laquelle nous avons une solution pour ce
probl`eme et reformuler le SDVRP selon cette m´ethode. Enfin,
dans la chapitre 3, nous allons examiner l’algorithme de g´en´eration de colonnes propos´es pour le SDVRP avec la plate-forme

BaPCod.


TABLE DES FIGURES

Fig. 0.3: Un exemple du SDVRP

5


Chapitre 1
Le probl`
eme de tourn´
ees de
v´
ehicules avec livraisons
divisibles
1.1

Introduction

Dans le probl`eme de tourn´ees de v´ehicules avec livraisons
divisibles une flotte de v´ehicules homog`enes capacit´es est disponible pour servir d’un ensemble de clients. Chaque client peut
ˆetre visit´e plusieurs fois, contrairement `a ce qui est g´en´eralement suppos´e dans le probl`eme de tourne´es de v´ehicules, et
la demande de chaque client peut ˆetre sup´erieure a` la capacit´e de v´ehicule. Chaque v´ehicule doit d´emarrer et terminer
son tour au d´epˆot. Le probl`eme consiste `a trouver un ensemble
d’routes v´ehicule qui servent tous les clients, telle que la somme
des quantit´es livr´ees dans chaque tour n’exc`ede pas la capacit´e
d’un v´ehicule et la distance totale voyag´ee est r´eduite.
Le SDVRP a ´et´e introduit dans la litt´erature il y a environ vingt ans par Dror et Trudeau ([13] et [14]) qui ont motiv´e l’´etude du SDVRP par prouver qu’il peut avoir des ´economies g´en´er´ees en permettant aux livraisons divisibles. Archetti,

Savelsbergh et Speranza [7] analysent les ´economies possibles
6


`
´
´
CHAPITRE 1. LE PROBLEME
DE TOURNEES
DE VEHICULES
AVEC LIVRAISONS DIVISIBLES
7

maximales obtenues par permettant des livraisons divisibles,
tandis que dans [8], des auteurs ont mˆeme pr´esent une ´etude
calcule afin de montrer comment les ´economies d´ependent les
caract´eristiques de l’instance. Les in´egalit´es valides pour le SDVRP sont d´ecrites par Dror, Laporte et Trudeau [14], tandis
que Belenguer, Martinez et Mota [4] propose une limite inf´erieure pour le cas o`
u la demande de chaque client n’exc`ede
pas la capacit´e de v´ehicule. Archetti, Mansini et Speranza [11]
analysent la complexit´e algorithmique du SDVRP et le cas des
v´ehicules avec petite capacit´e.
Les applications r´eelles de SDVRP ses trouvent dans le travail par Mullaseril, Dror et Leung [6], o`
u les auteurs consid`erent
le probl`eme de la gestion d’une flotte de camions pour distribuer d’aliment dans un ranch de b´etail et formulent comme
un SDVRP avec fenˆetres de temps (time windows). Sierksma
et Tijssen [5] consid`erent le probl`eme de d´eterminer l’horaire
de vol pour h´elicopt`eres aux plates-formes pour l’´echange de
l’´equipage personnes employ´ees sur ces plates-formes hors terre.
Dans ce chapitre, nous pr´esenterons la formulation de probl`eme dans section 1.2, puis les propri´et´es et la complexit´e de

SDVRP en section 1.3.

1.2

D´
efinition et formulation du probl`
eme

Rappel de la th´
eorie des graphes.
Rappelons quelques notions essentielles de la th´eorie des graphes.
D´
efinition 1.2.1. (Graphe simple non-orient´e) Un graphe simple
non-orient´e G est un couple (V,E), o`
u V est un ensemble dont
les ´el´ements sont les sommets, E est un ensemble de paires
(non ordonn´ees) de sommets, appel´ees arˆetes.


`
´
´
CHAPITRE 1. LE PROBLEME
DE TOURNEES
DE VEHICULES
AVEC LIVRAISONS DIVISIBLES
8

D´
efinition 1.2.2. (Chemin) Un chemin d’un noeud X `a un

noeud Y dans un graphe non-orient´e G est un ensemble d’arˆetes
A = (X1 ,X2 ),(X2 ,X3 ),...,(Xn−1 ,Xn ) tel que A ∈ V et X = X1
et Xn = Y ; la longueur du chemin A est |A|.
D´
efinition 1.2.3. (Chemin El´ementaire) Un chemin A = {(X1 ,X2 ),
(X2 ,X3 ),...,(Xn−1 ,Xn )} est ´el´ementaire si chacun des sommets
du parˆeteours est visit´e une seule fois : ∀i,j tels que 1 ≤ i,j ≤ n
et i = j on a : Xi = Xj . Un chemin ´el´ementaire est un chemin simple (chaque arˆete est emprunt´ee une seule fois) et sans
boucle.
Le SDVRP peut ˆetre d´efini sur un graphe G = (V,E) avec
l’ensemble de sommet V = {0,1,...,N }, o`
u 0 d´esigne le d´epˆot et les autres sommets repr´esentent les clients, et l’ensemble
d’arˆetes E. Le coˆ
ut cij (´egalement appel´ee longueur) du parˆeteours d’une arˆete (i,j) ∈ E, suppose qu’elle n’est pas n´egative
et satisfaite `a l’in´egalit´e triangulaire. Une demande di est associ´ee chaque client i ∈ V − {0}. Un nombre illimit´e de v´ehicules
sont disponible, chacune avec capacit´e Q ∈ Z. Nous supposons
qu’une limite sup´erieure M sur le nombre de v´ehicules n´ecessaires pour servir les clients est disponible.
Chaque v´ehicule doit d´emarrer et terminer son tour au d´epˆot. Les demandes de clients doivent ˆetre satisfaites, et la quantit´e livr´ee dans chaque visite ne peut pas d´epasser Q. L’objectif
est de r´eduire la distance totale voyag´ee par les v´ehicules.
Nous offrons ci-dessous une enti`ere mixte programmation
formulation (P) pour le SDVRP. Nous utilisons les notations
suivantes :
– xij est une variable binaire qui prend la valeur 1 si le
v´ehicule k voyage directement a` partir de i a` j et 0 sinon,
– aik est la quantit´e de la demande de i livr´ee par le v´ehicule


`
´
´

CHAPITRE 1. LE PROBLEME
DE TOURNEES
DE VEHICULES
AVEC LIVRAISONS DIVISIBLES
9

k.
– yik est une variable binaire qui prend la valeur 1 si le
v´ehicule k visite le client i et 0 sinon.
Le SDVRP est formul´e comme suit :
N

M

cij xijk

min P =
i,j

(1.1)

k

sous les contraints:
N

N

xj0k = 1


∀k,

(1.2)

xjik = yik

∀i = 0,∀k

(1.3)

aik ≤ di yik ,

∀i = 0,∀k

(1.4)

aik ≤ Q

∀k

(1.5)

di − (M − 1)Q

∀k

(1.6)

∀i


(1.7)

x0jk =
j

j
N

N

xijk =
j

j

N

i
N

N

aik ≥
i

i
M

aik = di
k


uik − ujk + (N + 1)xijk ≤ N ∀i = 0,∀j = 0,∀k,
xijk ,yik ∈ {0,1}

∀i,j,k,

aik ≥ 0,uik ≥ 0

∀i = 0,∀k.

(1.8)

La contrainte 1.2 assure que chaque v´ehicule d´emarre et
termine son tour au d´epˆot. Dans la contrainte 1.3, xijk = 1
indique que le v´ehicule k visite point j apr`es point i et yik = 1
` chaque
indique que le v´ehicule k visite point demande i. A
demande point i, la quantit´e de livraison aik ne doit pas d´epasser la demande, ce qui est assur´e par les contraintes 1.4. Les


`
´
´
CHAPITRE 1. LE PROBLEME
DE TOURNEES
DE VEHICULES
AVEC LIVRAISONS DIVISIBLES
10

contraintes 1.5 et 1.6 assurent que la livraison totale de la route

ne peut pas d´epasser la capacit´e de v´ehicule mais doit ˆetre au
moins N
i di − (M − 1)Q. Les contraintes 1.7 garante que la
demande est satisfaite pour tous les points. Enfin, on retrouve
les contraintes d’´elimination des sous-tours en 1.8.
On peut distinguer deux cas du SDVRP, la demande di de
chaque client i est discr`ete ou continue, c’est-`a-dire, dans le cas
que la demande est unitaire, aik est enti´ere, et inversement, aik
est continue. Dans ce rapport, nous ´etudions seulement le cas
que la demande est discr`ete.

1.3

Propri´
et´
es et complexit´
e

Dans cette section on r´esume les contributions a` la complexit´e du SDVRP et on vois aussi les certaines propri´et´es du
SDVRP.

1.3.1

La complexit´
e

Dans le cas Q = 2, nous montrer que toute instance du
SDVRP peut ˆetre transform´ee en une instance du ”minimum
weight b-matching problem”. On a un algorithme de polynˆome
pour r´esoudre ce probl`eme, qui est un cas particulier du ”matching problem” g´en´eral, le SDVRP peut ˆetre r´esolu en temps

polynˆomial. Le ”minimum weight b-matching problem” est d´e˜ = (V˜ ,E)
˜ un graphe non-orient´e, posfini comme suit. Laisser G
sible avec des boucles, c˜e le poids de l’arˆete e ∈ E et bi ∈ Z +
un param`etre associ´e a` vertex i ∈ V˜ . L’objectif est de trouver
˜
un vecteur int´egrante de poids minimum x ∈ Z |E| telles que
xe + l∈λi 2xl ≥ bi , i ∈ V˜ , o`
u δ(i) et λ(j) sont l’ensemble
d’arˆetes incidents `a i et l’ensemble de boucles a` i, i ∈ V˜ .
Th´
eor`
eme 1.3.1. [11] Le SDVRP avec Q = 2 peuvent ˆetre


`
´
´
CHAPITRE 1. LE PROBLEME
DE TOURNEES
DE VEHICULES
AVEC LIVRAISONS DIVISIBLES
11

r´esolus en temps polynˆ
omial.
´
Preuvu Etant
donn´e une instance du SDVRP avec Q = 2
d´efini sur graphe G = (V, E), nous construisons une instance
du ”minimum weight b-matching problem” comme suit. Nous

˜ = (V˜ ,E)
˜ o`
construisons un graphe compl`ete non-orient´e G
u
V˜ = V −{0}, c˜ij = min{c0i +cij +cj0 ,c0j +cji +ci0 }, i = j, i,j ∈ V˜
et nous d´efinissons bi = di , i ∈ V˜ . Alors, une boucle est ajout´ee
chaque sommet i ∈ V˜ avec coˆ
ut sur la boucle c˜ii = c0i + ci0 .
La solution optimale du SDVRP avec Q = 2 dans le cas de
coˆ
uts g´en´eraux sur G peut ˆetre obtenue en r´esolvant le ”mini˜ La valeur
mum weight b-matching problem” sur le graphe G.
de x sur l’arˆete (i,j) donne le nombre des routes qui visitent
des sommets i et j. La valeur de x sur une boucle sur le sommet i donne le nombre de routes directs du d´epˆot au sommet
i. Si la somme de x des bords incidents a` i et deux fois de x
des boucles sur i d´epasse di , il d´epasse di par une unit´e et cela
signifie que l’un des v´ehicules qui visite i comporte uniquement
une division.
Dans le cas Q ≥ 3, le SDVRP est NP-difficile.
Th´
eor`
eme 1.3.2. [11] Le SDVRP o`
u chaque client a la demande unitaire est NP-difficile pour Q ≥ 3.

1.3.2

Les propri´
et´
es


Dans l’article [10], Arhetti, Hertz et Speranza ont preuves
qu’il existe toujours une solution optimale enti`ere `a (P ).
Th´
eor`
eme 1.3.3. Si (P ) a les solutions r´ealisables alors il
existe toujours une solution optimale que les variables aik sont
enti`eres.
Dans le SDVRP, la demande de clients peut ˆetre sup´erieure
a` la capacit´e de v´ehicule. Il existe une classe d’instances o`
u nous


`
´
´
CHAPITRE 1. LE PROBLEME
DE TOURNEES
DE VEHICULES
AVEC LIVRAISONS DIVISIBLES
12

Fig. 1.1: Un cycle 4-split
savons comment de fa¸con optimale servir la partie de d´epasser
la capacit´e de v´ehicule de la demande.
´
D´
efinition 1.3.1 (k − split cycle). Etant
donn´e k clients et k
routes. La route 1 visite les clients i1 et i2 , la route 2 visite les
clients i2 et i3 , la route k − 1 visite les clients ik−1 et ik et la

route k visite les clients ik et i1 . Le sous-ensemble de clients
i1 ,i2 ,...,ik est appel´e k-split cycl´e.
On peut trouver un exemple d’un cycle 4-split dans la figure
1.1. Dror et Trudeau ont montr´e que, si les distances satisfont
l’in´egalit´e triangulaire, alors il existe toujours une solution optimale pour le SDVRP qui ne contient pas de cycles de k−split,
k ≥ 2.
Th´
eor`
eme 1.3.4. [14] Si la distance cij satisfait l’in´egalit´e triangulaire, alors il existe une solution optimale du SDVRP pour
laquelle il n’y a pas de k − split cycle (pour tout k)
Ce r´esultat est d’une grande importance puisqu’elle permet
une r´eduction du nombre de solutions examin´ees pour trouver
l’optimum, comme illustr´e dans le corollaire remarquable suivant.
Corollaire 1.3.0.1. [14] Si le coˆ
ut cij satisfait l’in´egalit´e triangulaire, il existe une solution optimale pour le SDVRP o`
u
aucun couple de routes n’a plus d’un client split´e en commun.


`
´
´
CHAPITRE 1. LE PROBLEME
DE TOURNEES
DE VEHICULES
AVEC LIVRAISONS DIVISIBLES
13

Une autre propri´et´e structurelle des solutions optimales au
SDVRP est d´eriv´ee d’Archetti, Savelsbergh et Speranza [7] qui

porte le nombre de divisions sur le nombre de routes. Laisser
ni ˆetre le nombre de livraisons re¸cues par client i, c’est-`a-dire
le nombre de routes que visite client i. Nous disons que client
i est un client avec une livraison divisible si ni > 1 et que le
nombre de divisions au client i est ni − 1. Par cons´equent, le
nombre total de divisions est ´egal `a ni=1 (ni − 1).
Th´
eor`
eme 1.3.5. [7] Si le coˆ
ut cij satisfait l’in´egalit´e triangulaire, il existe une solution optimale pour le SDVRP o`
u le
nombre de divisions est inf´erieur au nombre de routes.
Preuvu Par contradiction. Envisager un contre-exemple a` la
propri´et´e avec aucun cycle de k-split (une solution toujours
existe en raison de th`eor`eme 1.3.4) et le num´ero plus petit des
routes. Tout d’abord, nous constatons qu’il devra y avoir au
moins deux divisions par route. Supposons qu’il y a un route
avec un division unique. Puis nous peuvons r´eduire la demande
du client `a la livraison divisible par le nombre qu’il re¸coit sur
la route et supprimer tous les autres clients servis sur la route.
Nous avont r´eduit le nombre de divisions par un et nous avons
r´eduit le nombre de routes par un. Par cons´equent, nous avont
construit un contre-exemple avec un route moins, qui contredit
´
la minimality de la contre-exemple original. Etant
donn´e que
chaque visite a au moins deux divisions et en raison de corollaire 1.3.0.1, chaque tour est fait ”connect´e” grˆace `a ses clients
avec les livraisons divisibles au moins deux autres routes. Cela
signifie qu’il existe toutefois au moins un cycle de k-split, qui
est une contradiction. Par cons´equent, il existe toujours une solution optimale de SDVRP dans laquelle le nombre de divisions

est inf´erieur au nombre de routes.


`
´
´
CHAPITRE 1. LE PROBLEME
DE TOURNEES
DE VEHICULES
AVEC LIVRAISONS DIVISIBLES
14

1.3.3

Analyse au pire cas

Le coˆ
ut d’une solution optimale du VRP (z(V RP )) est compar´e avec le coˆ
ut d’une solution optimale du SDVRP (z(SDV RP ))
par calculer une limite sup´erieure de l’´ecart entre deux valeurs.
Dans le travail par Archetti, Savelsbergh Speranza [7] il est
d´emontr´e que :
z(V RP )
≤2
(1.9)
z(SDV RP )
et que cette limite est serr´ee, c’est-`a-dire il existe une instance
o`
u la solution optimale du VRP a une valeur qui est deux fois
aussi grand que la valeur de la solution optimale du SDVRP. Ce

r´esultat affirme que, avec ´egard pour une solution du VRP, les
livraisons divisibles peuvent ´economiser jusqu’`a 50 % du coˆ
ut.
Les instances utilis´es pour d´emontrer l’´etanch´eit´e de limite
ci-dessus, tous les v´ehicles ont grande capacit´e et la demande
est discr`ete. Par cons´equent, il est int´eressant d’analyser un cas
avec les v´ehicles de petite capacit´e. Dans le travail par Archetti,
Savelsbergh Speranza [7], il est montre que, lorsque la capacit´e
z(V RP )
3
est Q = 3, puis z(SDV
ee.
RP ) ≤ 2 et que cette limite est serr´

1.3.4

Un exemple

La figure 1.2 illustre les diff´erences entre les deux probl`emes,
le VRP et le SDVRP. On consid`ere un r´eseau non orient´e avec
des coˆ
uts sur les arˆetes, un d´epˆot central et quatre clients a,
b, c, d avec leurs demandes entre crochets. On dispose d’une
flotte de trois v´ehicules identiques. On a alors des v´ehicules
de capacit´e 18 et des demandes respectives de 7, 10, 6 et 13
pour les quatre clients. La solution optimale du VRP a un coˆ
ut
total de 22 et comprend trois tourn´ees : (a, b), (c) et (d). Pour
le SDVRP, la solution optimale a un coˆ
ut ´egal a` 19 et deux



`
´
´
CHAPITRE 1. LE PROBLEME
DE TOURNEES
DE VEHICULES
AVEC LIVRAISONS DIVISIBLES
15

tourn´ees (a, b, c) et (a, d). On visite deux fois le client a, pour
lui livrer 2 puis 5 unit´es de produit.

Fig. 1.2: Un exemple de VRP et SDVRP


Chapitre 2
G´
en´
eration de Colonnes et
Reformulations
2.1

Introduction

Pour r´esoudre le SDVRP, plusieurs heuristiques ont ´et´e d´evelopp´ees. Le premier algorithme heuristique pour le SDVRP
est une recherche locale et est introduit par Dror et Trudeau
[13]. Une recherche Tabou et une heuristique bas´ee optimisation
ont ´et´e r´ecemment propos´ees par Archetti, Hertz et Speranza

[10] et par Archetti, Savelsbergh, Speranza [12].
Belenguer, Martinez et Mota [4] ont ´etudi´es le Poly`edre du
SDVRP et ont trouv´es les in´egalit´es valides qui d´efinissent les
facettes. Les facettes ont ´et´e utilis´ees dans un ”cutting plane algorithme” pour chercher une limite inf´erieure pour le SDVRP.
Les exp´eriences informatiques pour tester l’efficacit´e de la limite inf´erieure ont ´et´e ex´ecut´ees sur des instances de la TSPLIB ∗ et sur instances g´en´er´ees al´eatoirement. De mesurer les
performances de la limite inf´erieure, les auteurs ont calcul´es a`
l’´ecart entre la limite inf´erieure et la limite sup´erieure obtenues
pour r´esoudre les instances par un algorithme heuristique pour
le VRP. Les r´esultats informatiques montrent que l’´ecart moyen
∗ />
16


´ ERATION
´
CHAPITRE 2. GEN
DE COLONNES ET
REFORMULATIONS

17

quant a` la limite sup´erieure est 3.05 % pour les instances TSPLIB et 7.81 % pour les instances al´eatoires.
Les meilleures de notre connaissance, trois approches exactes
ont ´et´e propos´ees pour le SDVRP. L’une est propos´e par Lee
et al. [16] qui formulent le SDVRP comme un probl`eme de programmation dynamique. Les tests de calcul montrent que l’algorithme est capable de r´esoudre les instances avec les clients
jusqu’`a 7 dans un d´elai raisonnable. Jin, Liu et Bowden [15]
proposent plutˆot une approche exacte de deux ´etapes pour r´esoudre le SDVRP. Dans la premi`ere phase un probl`eme de l’affectation est r´esolu pour d´eterminer les clusters de clients servis
par le mˆeme v´ehicule. La premi`ere ´etape fournit une limite inf´erieure. La deuxi`eme ´etape consiste a` r´esoudre une FST pour
chaque cluster ainsi d´eterminer une limite sup´erieure. Cette limite sup´erieure est utilis´ee pour g´en´erer des in´egalit´es valides
qui sont ins´er´ees dans le probl`eme d’affectation de la premi`ere

´etape a` l’it´eration suivante. La proc´edure est adapt´ee jusqu’`a
sup´erieur et inf´erieur limites co¨ıncider. Les tests montrent que
cette approche est capable de r´esoudre instances avec jusqu’`a
22 clients utilisant une fois calcule assez volumineux (plus de 13
heures pour les instances avec plus de 20 clients). L’algorithme
propos´e par Jin, Liu et Bowden [15] suppose qu’un nombre fixe
de v´ehicules.
Jin, Liu et Eksioglu [1] proposent un algorithme de g´en´eration de colonnes et comparent cette approche avec le ”cutting
plan algorithme” propos´e par Belenguer, Martinez et Mota [4].
La comparaison est faite sur la base de l’´ecart entre la limite
sup´erieure et inf´erieure `a la fin de l’heure en cours d’ex´ecution.
L’algorithme de g´en´eration de colonnes trouve mieux limites
sup´erieures dans six instances et mieux limites inf´erieures dans