Remerciements - École de gestion | Université Laval ... · 2.4.5. Multi-dépôts ... problème de tournées de véhicules (vehicle routing problem) est un autre problème étudié

II

Remerciements Tout d’abord, j’aimerais remercier mes deux directeurs de recherche M. Jacques Renaud

et M. Fayez F. Boctor qui m’ont épaulé et guidé tout au long de ce projet. Je tiens à les

remercier pour leur disponibilité, leur patience ainsi que leur savoir qu’ils ont su me

transmettre pour réaliser cet essai.

Je tiens aussi à remercier M. Jacques Dubois, propriétaire de Distributions Jacques

Dubois Inc. et Mehdi Aouididi pour leur précieuse collaboration ainsi que pour m’avoir

fourni les données nécessaires à cet essai.

Ce projet n’aurait été possible sans l’appui du CEntre de recherche des Technologies de

l’Organisation Réseau (CENTOR), de la faculté des Sciences de l’Administration (FSA)

de même que du Conseil de Recherche des Sciences Naturelles et Génies (CRSNG). Je

les remercie pour leur infrastructure, leur encadrement académique et leur soutien

financier.

Aussi, je tiens à remercier tous mes amis et mes collègues étudiants avec qui j’ai partagé

des moments très agréables au cours des dernières années. Le partage des connaissances

avec vous fût un réel plaisir.

Finalement, je ne saurais passer sous silence le support de mes proches. Un grand merci à

ma famille pour leur appui dans les moments les plus difficiles et ce malgré la distance

qui nous sépare. Je vous remercie de m’avoir toujours encouragé à poursuivre mes

études. Mes plus sincères remerciements à la famille de mon copain qui m’ont soutenu

durant mes études. Pour terminer, j’aimerais exprimer ma gratitude à mon copain,

Sébastien, pour son aide, sa compréhension et ses précieux conseils.

MERCI à vous tous et à tous ceux que j’ai malencontreusement oubliés, sans vous je

n’aurais pu mener à terme ce projet!

III

Table des matières

REMERCIEMENTS ....................................................................................................... II

TABLE DES MATIÈRES..............................................................................................III

LISTE DES TABLEAUX...............................................................................................VI

LISTE DES FIGURES ................................................................................................. VII CHAPITRE 1

INTRODUCTION .............................................................................................................. 1 1.1. MISE EN CONTEXTE ..............................................................................................................................1 1.2. PROBLÉMATIQUE ..................................................................................................................................3 1.3. MÉTHODOLOGIE ...................................................................................................................................4 1.4. ORGANISATION DE L’ESSAI ...................................................................................................................5

CHAPITRE 2

REVUE DE LA LITTÉRATURE...................................................................................... 6 2.1. INTRODUCTION .....................................................................................................................................6 2.2. DÉFINITION DU PROBLÈME....................................................................................................................7 2.3. PROBLÈMES DU VOYAGEUR DE COMMERCE ET GÉNÉRALISATIONS .......................................................8

2.3.1. Formulation mathématique..........................................................................................................9 2.3.2. Le TSP symétrique et asymétrique .............................................................................................10 2.3.3. Généralisation du problème du voyageur de commerce............................................................12

2.4. PROBLÈMES DE TOURNÉES DE VÉHICULES ET GÉNÉRALISATIONS........................................................19 2.4.1. Le problème de tournées de véhicules........................................................................................20 2.4.2. Algorithme pour le VRP standard.............................................................................................22 2.4.3. Composition de la flotte .............................................................................................................31 2.4.4. Fenêtres de temps.......................................................................................................................32 2.4.5. Multi-dépôts ...............................................................................................................................42 2.4.6. Autres généralisations du problème de tournées de véhicules...................................................43

2.5. APPLICATIONS PRATIQUES DES PROBLÈMES DE TOURNÉES DE VÉHICULES .........................................48 2.6. ALGORITHMES ....................................................................................................................................52

2.6.1. Méthode exacte .........................................................................................................................53 2.6.2. Heuristiques ...............................................................................................................................55 2.6.2.2. Heuristiques d’amélioration .................................................................................................57

2.7. CONCLUSION ......................................................................................................................................66

IV

CHAPITRE 3

DISTRIBUTIONS JACQUES DUBOIS INC. ............................................................... 67 3.1. INTRODUCTION ...................................................................................................................................67 3.2. DESCRIPTION GÉNÉRALE DE L’ENTREPRISE.........................................................................................67

3.2.1. Principales activités ...................................................................................................................68 3.2.2. Les clients et fournisseurs ..........................................................................................................68 3.2.3. Les produits................................................................................................................................69 3.2.4. Les camions................................................................................................................................70 3.2.5. Méthode actuelle ........................................................................................................................70 3.2.6. Le siège social............................................................................................................................71

3.3. DÉFINITION DU PROBLÈME..................................................................................................................71 3.3.1. Fenêtre de temps ........................................................................................................................72 3.3.2. Flotte hétérogène .......................................................................................................................73 3.3.3. Multi-produit..............................................................................................................................74 3.3.4. La récupération..........................................................................................................................75

3.4. CONCLUSION ......................................................................................................................................76

CHAPITRE 4

MÉTHODE DE RÉSOLUTION ..................................................................................... 77 4.1. INTRODUCTION ...................................................................................................................................77 4.2. PRÉSENTATION GÉNÉRALE..................................................................................................................77 4.3. PRÉSENTATION DÉTAILLÉE .................................................................................................................78

4.3.1. Préparation des données............................................................................................................78 4.3.2. Heuristique de construction .......................................................................................................78 4.3.3. Amélioration individuelle des routes..........................................................................................81 4.3.4. Amélioration collective des routes .............................................................................................82

4.4. PRÉSENTATION DU LOGICIEL ..............................................................................................................83 4.4.1. Résolution de problèmes de la littérature .................................................................................84 4.4.1. Résolution de problèmes réels ...................................................................................................85

4.5. CONCLUSION ......................................................................................................................................95

CHAPITRE 5

RÉSULTATS .................................................................................................................... 96 5.1. INTRODUCTION ...................................................................................................................................96 5.2. PRÉSENTATION DES DONNÉES.............................................................................................................96 5.3. RÉSULTATS.........................................................................................................................................98 5.4. CONCLUSION ....................................................................................................................................111

CHAPITRE 6

CONCLUSION............................................................................................................... 113

RÉFÉRENCES.............................................................................................................. 115

V

ANNEXES ..................................................................................................................... 123 ANNEXE A : ROUTES ET COMMANDES INITIALES PAR DISTRIBUTIONS JACQUES DUBOIS INC...............124 ANNEXE B : GUIDE D’UTILISATION MAPPOINT.....................................................................................133

1. Introduction à MapPoint................................................................................................................133 2. Les objets de MapPoint..................................................................................................................134 3. Situer deux points sur une carte.....................................................................................................136 4. Le calcul des paramètres de la route .............................................................................................138 5. Visualiser une route sur une carte MapPoint ................................................................................143

ANNEXE C : ARTICLE ASAC ................................................................................................................148

VI

Liste des tableaux

Tableau 2.1. : Comparaison des heuristiques pour le TSP avec retour à charge ..... 14 Tableau 2.2. : Résultats du CVRP ................................................................................. 25 Tableau 2.3. : Comparaison des métaheuristiques utilisées........................................ 27 Tableau 2.4. : Résultats sur les problèmes de Christofides et Eilon (1989) ............... 28 Tableau 2.5. : Problèmes par grappe ............................................................................ 28 Tableau 2.6. : Problèmes de grandes tailles.................................................................. 30 Tableau 2.7. : Meilleures solutions pour les problèmes C1......................................... 34 Tableau 2.8. : Meilleures solutions pour les problèmes C2......................................... 34 Tableau 2.9. : Meilleures solutions pour les problèmes R1......................................... 35 Tableau 2.10. : Meilleures solutions pour les problèmes R2....................................... 36 Tableau 2.11. : Meilleures solutions pour les problèmes RC1 .................................... 37 Tableau 2.12. : Meilleures solutions pour les problèmes RC2 .................................... 38 Tableau 2.13. : Comparaison des résultats moyens entre les publications................ 39 Tableau 2.14. : Résultats de Li et Lim (2003)............................................................... 40 Tableau 2.15. : Résultats de Berger et Barkaoui (2003) .............................................. 41 Tableau 2.16. : Résultats des problèmes tirés de Golden et al. (1983) ....................... 44 Tableau 2.17. : Résultats des problèmes tirés de Kiuchi et al. (1995) ........................ 44 Tableau 2.18. : Résultats des problèmes tirés de Benavent et al. (1992).................... 45 Tableau 2.19. : Résultat Osman et Wassan (2002)....................................................... 47 Tableau 3.1. : Répartition des activités selon la journée de la semaine ..................... 71 Tableau 3.2. : Caractéristiques des camions ................................................................ 73 Tableau 3.3. : Classement des produits......................................................................... 75 Tableau 3.4. : Classification des clients selon la quantité de recupération................ 76 Tableau 5.1. : Exemple d’une route et des commandes associées .............................. 97 Tableau 5.2. : Routes initiales par Distributions Jacques Dubois inc. ....................... 98 Tableau 5.3. : Routes initiales ........................................................................................ 99 Tableau 5.4. : Routes obtenues suite au 3-opt .............................................................. 99 Tableau 5.5. : Routes obtenues suite à l’amélioration inter-route ........................... 100 Tableau 5.6. : Routes finales ........................................................................................ 101 Tableau 5.7. : Routes finales obtenues avec critère nb clients/ distance parcourue 111

VII

Liste des figures

Figure 2.1. : Classification des problèmes du voyageur de commerce et ses généralisations .............................................................................................. 8

Figure 2.2. : Classification des problèmes de tournées de véhicules .......................... 19 Figure 3.1. : Localisation des clients de Distributions Jacques Dubois inc. .............. 69 Figure 4.1. : Organigramme de la méthode de résolution........................................... 80 Figure 4.2. : Un mouvement 3-opt ................................................................................ 81 Figure 4.3. : Les 11 échanges testées ............................................................................. 83 Figure 4.4. : Interface visuelle du logiciel ..................................................................... 84 Figure 4.5. : Sélection d’un problème classique ........................................................... 85 Figure 4.6. : Modification des caractéristiques des clients.......................................... 86 Figure 4.7. : Modification de la commande d’un client............................................... 87 Figure 4.8. : Sélection des clients ................................................................................... 88 Figure 4.9. : Sélection des clients par ville .................................................................... 88 Figure 4.10. : Identification des paramètres de l’entreprise ....................................... 89 Figure 4.11. : Optimisation des tournées ...................................................................... 90 Figure 4.12. : Feuille de route des camionneurs........................................................... 92 Figure 4.13. : Accès à MapPoint .................................................................................... 93 Figure 4.14. : Commande des clients............................................................................. 94 Figure 4.15. : Localisation des clients............................................................................ 94 Figure 5.1. : Illustration et description de la route 1 ................................................. 102 Figure 5.2. : Illustration et description de la route 2 ................................................. 103 Figure 5.3. : Illustration et description de la route 3 ................................................. 104 Figure 5.4. : Illustration et description de la route 4 ................................................. 105 Figure 5.5. : Illustration et description de la route 5 ................................................. 106 Figure 5.6. : Illustration et description de la route 6 ................................................. 107 Figure 5.7. : Illustration et description de la route 7 ................................................. 108 Figure 5.8. : Illustration et description de la route 8 ................................................. 109 Figure 5.9. : Illustration et description de la route 9 ................................................. 110

1

Chapitre 1

Introduction

Le transport permet le mouvement des produits

d’un endroit à un autre. Il est par conséquent

indispensable à notre économie. Ce chapitre est

composé d’une mise en contexte du transport

routier des marchandises au Canada où

l’importance du transport est démontrée et d’une

description de la problématique qui sera résolue dans cet essai. Suit la méthodologie qui

sera utilisée et finalement l’organisation de l’essai par chapitre.

1.1. Mise en contexte

Les opérations de transport sont essentielles au bon fonctionnement de notre économie de

marché. Effectivement, selon Statistiques Canada, les entreprises de transport routier

emploient plus de 200 000 personnes et génèrent des revenus annuels de plus de 36,9

milliards. Le transport routier des marchandises permet l’acheminement des matières et

des produits entre entreprises et vers les consommateurs. Il permet entre autres la

distribution de tous les produits vitaux tels que la nourriture, les vêtements, les meubles,

etc. Le transport joue un rôle clé dans la chaîne logistique puisqu’un produit est rarement

produit et consommé au même endroit. Pratiquement chaque produit acheté par un

consommateur est passé par un camion. Certains produits passent par quatre ou cinq

camions ou même plus avant d'aboutir entre les mains du consommateur final. Étant

donné l’étendue géographique du Canada, le transport routier des marchandises joue un

2

rôle économique primordial. Selon Statistiques Canada, l’infrastructure routière

canadienne compte plus de 900 000 kilomètres d’autoroutes et de routes pour supporter

l’industrie du camionnage et les transports en général.

Le nombre de camions sur les routes augmente d’années en années. Par ailleurs, les coûts

de carburant eux augmentent sans cesse constituant une part importante des frais

d’opération d’un transporteur. Par conséquent, la rentabilité d’une entreprise est

grandement affectée par les décisions relatives à l’assignation et à la séquence des

livraisons. La planification des tournées est donc un problème majeur pour les entreprises

de transport. Étant donné les conséquences économiques et stratégiques des problèmes

de transport, ces derniers ont attiré l’attention de nombreux chercheurs et ce, depuis

plusieurs années.

Le problème de base en transport, probablement celui le plus étudié, est le problème du

voyageur de commerce (traveling salesman problem ) qui permet de visiter un ensemble

de clients avec un seul camion. Le problème consiste donc à trouver l’ordre dans lequel

chacun des clients sera visité.

À ce problème, de nombreuses contraintes peuvent s’ajouter permettant ainsi de s’adapter

à des problèmes pratiques rencontrés dans l’industrie du camionnage. Par exemple, le

problème de tournées de véhicules (vehicle routing problem) est un autre problème étudié

par plusieurs chercheurs, il traite le cas où chacun des clients a une demande déterminée

et où la flotte est homogène.

Cet essai porte sur un problème de tournées de véhicules où plusieurs contraintes sont

présentes. La prochaine section permet de bien cerner l’ensemble de ces contraintes.

3

1.2. Problématique

Le problème rencontré chez Distributions Jacques Dubois inc. est un problème de

tournées de véhicules avec fenêtres de temps, flotte hétérogène et produits multiples.

Effectivement, il s’agit d’un problème de tournées de véhicules puisque les clients à

visiter requièrent une demande connue à l’avance et les véhicules sont limités par leur

capacité en terme de poids pour les produits et de volume pour la récupération. De plus,

chacun des clients a une fenêtre de temps à l’intérieur de laquelle il désire recevoir la

livraison. On dit que la flotte est hétérogène puisque la flotte de camions de l’entreprise

est constituée de camions ayant des capacités distinctes. De plus, l’entreprise distribue

plusieurs produits qui sont différents les uns des autres, ces derniers ont un poids

différents qui devra être pris en considération. Finalement, l’entreprise doit aussi

récupérer chez ses clients les bouteilles et cannettes vides.

Le problème consiste donc à visiter tous les clients une et une seule fois afin de leur livrer

la marchandise commandée et rapporter la récupération tout en respectant les contraintes

de temps, de volume et de capacité. L’objectif est de minimiser la distance parcourue

pour visiter tous les clients.

Pour résoudre ce problème, plusieurs étapes seront nécessaires. En premier lieu, la

construction de l’ensemble des routes. Ces routes devront respecter l’ensemble des

contraintes. Une fois l’ensemble des routes construit, une amélioration individuelle de

chacune de celle-ci sera effectuée à l’aide du 3-opt. Finalement, on évaluera deux à deux

les routes pour tenter de les améliorer en interchangeant les clients entre ces routes, tout

cela en s’assurant encore une fois que toutes les contraintes sont respectées.

4

1.3. Méthodologie

Les objectifs visés par cet essai consistent tout d’abord à bien identifier les problèmes de

tournées étudiés récemment par les scientifiques de la recherche opérationnelle. Par la

suite, en rapport avec ces problèmes, une approche adaptée aux contraintes de l’entreprise

Distributions Jacques Dubois inc. sera présentée.

Dans un premier temps, une revue des articles récents sera effectuée de manière à mettre

à jour les connaissances dans le domaine des tournées de véhicules et à définir les

algorithmes les plus en vogues ces dernières années. Les articles traitant du problème du

voyageur de commerce sont présentés puis le problème de tournées de véhicules est

ensuite abordé. Ces deux types de problèmes sont séparés en sous-groupes selon le type

de contraintes traitées.

Ensuite, l’entreprise Distributions Jacques Dubois inc. sera présentée plus en détail de

manière à bien situer le contexte du problème de tournées de véhicules. Ainsi, les

caractéristiques du problème rencontré et les contraintes inhérentes au problème seront

présentées.

Plusieurs méthodes de résolution seront proposées pour résoudre le problème de

voyageur de commerce et le problème de tournées de véhicules avec limites de capacité

et de durée. Par conséquent, chacune de ces dernières sera exposée de façon précise. Ces

algorithmes ont été intégrés à un logiciel qui sera présenté étape par étape à la manière

d’un guide d’utilisateur.

Finalement, une analyse des résultats obtenus sur des données réelles permettra d’évaluer

l’heuristique proposée sur le problème de Distributions Jacques Dubois inc.

5

1.4. Organisation de l’essai Après avoir effectué une brève introduction au chapitre 1, le chapitre 2 présente les

principaux problèmes de tournées, les algorithmes utilisés pour les résoudre ainsi que les

résultats obtenus. Cette revue est récente puisque seulement les articles parus au cours

des trois dernières années seront présentés.

Le chapitre 3 présente l’entreprise Distributions Jacques Dubois inc. Dans un premier

temps, une description générale de l’entreprise sera exposée. Puis, la problématique sera

abordée de façon plus détaillée.

Le chapitre 4 met en relief la méthode de résolution utilisée. Une description plus

générale est suivie d’une description détaillée des heuristiques utilisées. Pour terminer ce

chapitre, le logiciel d’optimisation ayant permis de résoudre la problématique est

présenté. Ce logiciel est en interaction avec une base de données Access et le logiciel de

cartographie MapPoint permettant de mieux visualiser les routes.

Le chapitre 5 évalue les heuristiques proposées pour ensuite proposer les routes à

l’entreprise Distributions Jacques Dubois inc.

En conclusion, les modifications qui pourraient être apportées ainsi que les objectifs

atteints seront discutés.

Finalement, il est possible de consulter en annexe un guide d’utilisation permettant

d’utiliser les fonctionnalités de MapPoint à partir de Visual Basic de même que l’article

rédigé pour le congrès de l’association des sciences administratives du Canada (ASAC).

6

Chapitre 2

Revue de la littérature (2000-2003)

2.1. Introduction

La recherche en transport a beaucoup évoluée au cours des dernières

années. Les entreprises ont découverts qu’une meilleure planification

des tournées permettrait d’épargner des coûts importants. Effectivement, les coûts de

transport effectués à travers la chaîne logistique et durant le processus de vente

représentent généralement 10 à 25% du coût total de production. Selon CASS Information

Systems, cela peut représenter jusqu’à 57% des coûts logistiques, surpassant ainsi les

coûts de stockage (31%) et d’entreposage (8%). Les problèmes étudiés en transports sont

variés. Ce chapitre effectuera un survol des plus récentes publications concernant les

problèmes du voyageur de commerce et de tournées de véhicules ainsi que leurs

principales généralisations. Chaque article est traité à la fois par rapport à sa

problématique et à l’algorithme utilisé pour trouver une solution. Ce chapitre permettra

d’explorer les grandes tendances des dernières années tant au niveau des problèmes que

des algorithmes utilisés. L’étude des problématiques étudiées permettra de cibler

l’avancement des recherches sur les problèmes de transport tandis que l’étude des

algorithmes permettra de déterminer les méthodes de résolutions les plus efficaces.

7

2.2. Définition du problème

La problématique du transport n’est pas un problème récent et de nombreuses entreprises

doivent confronter cette dernière à tous les jours. Le problème de base consiste à affecter

en ordre les clients à une seule route. Or, cela ne reflète qu’une minorité d’entreprises

puisque dans la majorité des cas, elles doivent prendre une panoplie de décisions à savoir

dans quel ordre desservir un ensemble de clients en utilisant une flotte de véhicule (ou un

seul véhicule) à partir d’un ou plusieurs entrepôts. À cela s’ajoute les décisions

d’affection des clients et des camions aux différentes routes.

Plusieurs variantes de ce modèle sont apparues dans la littérature. Effectivement,

plusieurs contraintes peuvent y être ajoutées ou retranchées. Ainsi, l’entreprise peut

posséder un seul ou plusieurs véhicules. Ces derniers peuvent être identiques ou

hétérogènes à des niveaux distincts, soit les coûts d’utilisation, la capacité de chargement,

les coûts fixes, etc. La demande peut se trouver sur les arcs ou sur les nœuds selon le type

de problème auquel nous faisons face. Chaque fois que l’on ajoute ou retranche une

contrainte, un nouveau problème apparaît. Tous ces ajouts permettront de se rapprocher

de la réalité à laquelle une entreprise peut être confrontée. Les sections suivantes

tenteront de faire la lumière sur tous ces types de problèmes apparaissant dans des articles

des trois dernières années.

Notons pour terminer que peu importe les contraintes du problème, il demeure toujours

NP-Dur ce qui signifie qu’aucun algorithme connu ne peut garantir de trouver dans un

temps polynomial la solution exacte à ce problème.

8

2.3. Problèmes du voyageur de commerce et généralisations

Le problème du voyageur de commerce, mieux connu sous le nom de Traveling

Salesman Problem (TSP), est un des problèmes les plus étudiés en recherche

opérationnelle. Effectivement, il est à la base de tous les problèmes de tournées et a une

multitude d’applications réelles. Ce problème consiste à trouver le chemin le plus court

qui visite toutes les villes une et une seule fois tout en revenant au point de départ. Le

problème du voyageur de commerce étant NP-Dur, le temps pour trouver la solution

optimale augmente de façon exponentielle en fonction de la taille du problème. Il se

définit mathématiquement comme ceci : soit G = (N, A) où G est un graphe, N= {v0,

v1,…,vn} représente l’ensemble des nœuds (villes). Par ailleurs, A ={(vi,vj)| vi,vj ε N, i

<j} représente les arrêtes reliant ces nœuds si les distances sont symétriques et A={(vi,vj)|

vi,vj ε N, i ≠ j} représente les arcs lorsqu’elles sont asymétriques. Dans le cas où le

problème est symétrique c’est-à-dire où le graphe est non orienté, on parlera d’un cycle et

dans le cas contraire on parlera d’un circuit.

Figure 2.1. : Classification des problèmes du voyageur de commerce et ses généralisations

Voyageur de commerce

TSP pur Généralisations

Symétrique Asymétrique Localisation de la demande sur les arcs

Autres généralisations

Cueillette et/ou livraison

- Shutler (2001) - Helsgaun (2000)

- Choi, Kim, Kim (2003)- Glover, Gutin, Yeo, v Zverovich (2001)

- Ghaziri,Osman (2003) - Renaud, Boctor, Laporte (2002) - Renaud, Boctor, Ouenniche (2000)

- Cabral, Gendreau, Ghiani, Laporte (2003)

- Bourgeois, Laporte, Semet (2003)

- Moon, Kim, Choi, Seo (2002)

- Schneider (2002) - Patterson,Rolland

(2003) - Paletta (2002)

9

Le problème du voyageur de commerce consiste à trouver le cycle Hamiltonien le plus

court. Un cycle Hamiltonien est un cycle qui relie tous les nœuds d’un réseau de façon à

ce que chaque nœud soit visité une et une seule fois.

Le problème du voyageur de commerce permet évidemment de résoudre des problèmes

de tournées mais il existe aussi une variété d’autres contextes auxquels il peut

s’appliquer. Tout d’abord, on peut l’appliquer dans la construction des cartes maîtresses

des ordinateurs afin de minimiser la longueur des fils de cuivre entres les puces. Par

ailleurs, les algorithmes de résolution du TSP peuvent également être utilisés pour

optimiser la coupe du papier peint de manière à minimiser les pertes. Aussi, il peut être

utilisé afin d’optimiser les opérations de perçage des feuilles métalliques, l’application du

TSP permet alors d’optimiser le temps de déplacement de la perceuse pour percer ces

trous. Le TSP peut aussi être utile en ordonnancement. Si n commandes doivent être

effectuées sur une seule machine et que le temps de mise en route dépend de l’ordre de

passage, le TSP permettra de minimiser le temps de mise en route des commandes en

déterminant l’ordre dans laquelle celles-ci doivent être effectuées. Une autre application

du TSP est possible en cristallographie afin de minimiser le temps qui sert à prendre les

mesures au rayon-X. Par conséquent, on peut facilement constater que ce problème est

présent dans l’optimisation de plusieurs problèmes de notre vie de tous les jours. Le

lecteur intéressé est invité à consulter l’excellent livre Lawler et al. (1985) et les revues

de Laporte (1991) et Laporte et Osman (1995).

2.3.1. Formulation mathématique

Définissons les différentes variables nécessaires pour effectuer la formulation

mathématique du problème du voyageur de commerce.

dij = Distance entre la ville i et la ville j

n = Nombre de villes

xij = Variable binaire qui prend la valeur 1 si la ville i est visité immédiatement

avant la ville j. Sinon, cette variable prend la valeur 0.

10

Le problème consiste à minimiser la longueur du cycle Hamiltonien. La fonction objectif est:

Minimiser : Z = ∑=

n

i 1∑=

n

jd

1ij xij (2.1)

Les contraintes sont les suivantes :

11

=∑=

n

jijx i = 1,…..,n (2.2)

11

=∑=

n

iijx j= 1,…..,n (2.3)

∑ ∑

∈ ∈SI SJijx ≤ | S| - 1 pour tout S de N (2.4)

La contrainte (2.2) s’assure qu’on ne sort qu’une seule fois de chacun des points tandis

que la contrainte (2.3) vérifie que l’on entre seulement une fois à chaque point. Ces

contraintes permettent donc de visiter tous les points une et une seule fois. Par contre, si

l’on n’ajoute pas la contrainte (2.4) des sous-tours se formeront. La troisième contrainte

élimine donc tous les sous-tours possibles. Dans cette contrainte |S| dénote la cardinalité

de l’ensemble S. Cette contrainte doit être décrite pour tous les sous-ensembles S de N.

2.3.2. Le TSP symétrique et asymétrique

Une première particularité de ce problème se situe au niveau des caractéristiques du

graphe. Effectivement, les arcs du graphe peuvent avoir un poids inégal selon le sens

dans lequel on le parcourt, dans ce cas on dira que la matrice de ce problème est

asymétrique. Dans le cas contraire, où la distance est la même peu importe le sens, alors

cette dernière sera symétrique. Un problème est symétrique si la condition suivante est

respectée : dij = dji i∀ , j∀ . Par ailleurs, les distances peuvent aussi respecter l’inégalité

11

du triangle. Dans ce cas, la condition suivante doit s’appliquer : dik ≤ dij + djk ijk∀ . Selon

cette équation, il n’est jamais plus court de passer par le point j si l’on désire se rendre au

point k à partir du point i.

2.3.2.1. Le cas symétrique Un seul article parmi ceux étudiés présente une approche de résolution pour le problème

du voyageur de commerce symétrique. Shutler (2001) présente une amélioration à un

algorithme de séparation et d’évaluation progressive afin de résoudre le problème de TSP

symétrique. Il résout des problèmes de l’ordre de 100 à 500 nœuds. Notons cependant

que la meilleure heuristique actuellement disponible est celle de Helsgaun (2000) basée

sur le Lin-Kernighan.

2.3.2.2. Le cas asymétrique L’article de Glover, Gutin, Yeo et Zverovich (2001) présente trois nouvelles heuristiques

de construction pour le TSP asymétrique. Les auteurs développent des heuristiques de

construction pour un graphe orienté dans lequel chacun des arcs a un poids différent. Ces

heuristiques ont été testés sur sept différentes familles de problèmes. Ainsi, pour tous les

problèmes asymétriques du TSPLIB présenté par Reinelt (1981), la première heuristique

basée sur le Karp-Steele patching est meilleure se situant en moyenne à 3,36% de

l’optimum. Étant donné que les résultats sont très distincts d’un problème à un autre, il

sera approprié de choisir l’heuristique selon la famille auquel ce problème appartient.

Choi, Kim et Kim (2003) étudient eux aussi le problème de TSP asymétrique. Les auteurs

ont testé leur algorithme génétique sur 23 problèmes de 17 à 170 nœuds. Cet heuristique

a permis de trouver pour 14 problèmes la solution optimale tandis que la méthode exacte

de séparation et d’évaluation progressive a permis de trouver la solution optimale pour 19

problèmes. Elle a échouée à quatre reprises étant donné une insuffisance de mémoire de

l’ordinateur.

12

2.3.3. Généralisation du problème du voyageur de commerce

La deuxième caractéristique majeure du problème du voyageur de commerce se situe au

niveau du type d’opération effectué. En modifiant le type d’opération, le problème n’est

plus un problème de TSP pur, il devient alors une généralisation du TSP. De ce fait,

l’entreprise concernée peut avoir à effectuer des cueillettes et/ou des livraisons selon le

contexte de l’industrie.

2.3.3.1. Le TSP avec cueillette et livraison Le problème de cueillette et livraison consiste à trouver le cycle Hamiltonien le plus court

permettant de desservir tous les clients, de manière à ce que chaque cueillette soit

effectuée avant sa livraison associée.

Pour résoudre ce problème, Renaud, Boctor et Ouenniche (2000) présente un algorithme

composite. Les auteurs ont testé leur heuristique composite sur un ensemble de 108

problèmes dérivés de 36 problèmes du TSPLIB de Reinelt (1981) ayant jusqu’à 441

points. Les résultats obtenus démontrent que la double insertion suivi du 4-opt* permet

de se situer en moyenne à 5,64 % de la meilleure solution connue tandis que la double

insertion suivi de l’insertion et la suppression simultanée permet de se situer à seulement

4,48 % de ces résultats. Le 3-opt permettrait d’obtenir de meilleurs résultats (3,87% au

dessus de la meilleure solution connue) mais ce dernier utilise beaucoup de temps de

résolution. En effet, le 3-opt prend en moyenne 1314,2 secondes tandis que le 4-opt* et la

suppression et réinsertion prennent respectivement 73,1 et 95,9 secondes.

Renaud, Boctor et Laporte (2002) décrivent et comparent sept algorithmes de

perturbations. Trois différents types de perturbations sont abordées : perturbation du

problème, perturbation de l’algorithme et perturbation de la solution. Les heuristiques de

perturbation ont été testées sur deux types de problèmes. Le premier ensemble de

problème a été généré à partir de 36 problèmes du TSPLIB (Reinelt 1981) de 51 à 441

nœuds. Les résultats pour ce type de problème permettent d’améliorer ceux de Renaud,

13

Boctor et Ouenniche (2000) d’approximativement 4%. Le deuxième ensemble de

problèmes comporte dix problèmes de 101 nœuds et dix problèmes de 201 nœuds pour

lesquels l’optimum est connu. Les résultats permettent d’obtenir ou de s’approcher

considérablement de cet optimum. Effectivement, l’optimum est obtenu pour douze des

vingt problèmes.

2.3.3.2. Le TSP avec retour à charge Le papier de Ghaziri et Osman (2003) considère une extension du problème classique de

TSP, il s’agit du problème avec retour à charge (backhaul). Les clients sont divisés en

deux types, les premiers clients devant être visités au début de la route sont ceux

nécessitant une cueillette et les seconds permettant un retour à charge (backhaul) qui

seront visités une fois que tous les clients avec livraisons auront été visités. Les premiers

clients requièrent une livraison à partir du dépôt tandis que les clients avec retour à

charge permettent de rapporter de la marchandise au dépôt. Les auteurs présentent donc

une nouvelle heuristique basée sur les réseaux de neurones, il s’agit du SOFM*. Ils

utilisent quatre types d’interactions : la première chaîne interagit avec les clients à

longues distances, la seconde chaîne interagit avec les clients nécessitant une cueillette,

les queues des chaînes interagissent ensembles et finalement la tête des deux chaînes

interagissent avec le dépôt. Les tests ont été effectués sur des problèmes ayant entre 100

et 1000 points.

Un autre article classique sur le problème est celui de Gendreau, Hertz et Laporte (1993)

qui traite lui aussi du problème du voyageur de commerce avec retour à charge. Ils

proposent une heuristique dont la pire performance est de 3/2 de l’optimum lorsque le

problème respecte l’inégalité du triangle et que les coûts sont symétriques. Par la suite, ils

ont proposé quatre différentes heuristiques. Les tests ont été effectués sur 30 problèmes

de 100, 200 et 300 points. Les résultats de ces heuristiques se situent en moyenne à 0,5%

de la borne inférieure. Cela signifie que la plupart des résultats obtenus sont optimaux car

cet écart est probablement dû à l’écart entre la borne inférieure par rapport à la solution

optimale. Tous ces résultats ont été obtenus avec un faible effort de calcul. Chacune des

14

heuristiques présentées a utilisé l’algorithme GENIUS pour le TSP développé par

Gendreau, Hertz et Laporte (1992). Cet algorithme est constitué d’une phase de

construction et d’une phase de post-optimisation. La phase d’insertion GENI

(GENeralized Insertion) se fait à partir de trois nœuds choisis aléatoirement à partir

desquels sont insérés d’autres sommets pour former un cycle Hamiltonien. La seconde

phase US (Unstringing and Stringing) considère le retrait de chaque nœud pour ensuite

tenter de les réinsérer dans le tour de façon à réduire le coût de la tournée.

Plus récemment, Mladenovic et Hansen (1997) ont utilisé GENIUS avec une structure de

recherche nommée GENIUS-VNS. Cette variante est meilleure que l’adaptation GENIUS

par Gendreau, Hertz et Laporte (1993) en moyenne de 0,4% avec une augmentation de

30% du temps de calcul. Le tableau 2.1. présente une comparaison des solutions et temps

de calcul entre SOFM* de Ghaziri et Osman et les deux variantes de GENIUS. Selon ce

tableau, on constate que l’heuristique GENIUS-VNS surpasse les autres heuristiques en

terme de qualité de solution tandis que l’heuristique GENIUS est celle qui utilise le

moins de temps de calcul. Quant à l’heuristique SOFM*, il peut être un bon compromis

pour les problèmes de grandes tailles.

Tableau 2.1. : Comparaison des heuristiques pour le TSP avec retour à charge

Solution moyenne obtenues Temps moyen (CPU) en secondes

Nb points SOFM* GENIUS GENIUS-

VNS

SOFM* GENIUS GENIUS-

VNS

100 1072,05 1070,05 1065,62 23,98 4,76 5,54

200 1493,65 1498,56 1491,86 66,86 34,24 36,02

300 1815,18 1818,01 1812,12 308,38 85,02 100,66

500 2328,60 2328,78 2321,09 805,86 342,54 354,66

1000 3269,46 3273,13 3258,44 1453,20 1197,72 1671,82

Tous 1951,87 1953,73 1946,08 844,47 303,03 391,05

Source : Ghaziri et Osman (2003)

15

2.3.3.3. Localisation de la demande sur les arcs

Il arrive parfois que la demande ne soit pas située sur les nœuds comme dans le cas

classique du TSP mais qu’elle se trouve sur les arcs comme, par exemple, lors de la

livraison de courrier, c’est le problème du postier chinois. Ainsi, Cabral, Gendreau,

Gianpaolo et Laporte (2003) ont adapté le hierarchical Chinese postman problem

(HCPP) en un problème équivalent du rural postman problem (RPP). La différence

majeure entre un RPP et un CPP est que lors du RPP ce n’est pas tous les arcs qui ont une

demande, le graphe est ainsi séparé en arcs nécessitant un service ou non. À l’inverse,

tous les arcs du Chinese postman problem requièrent un service, donc ils doivent tous

être visités au minimum une fois. L’intérêt de cette adaptation est dû à l’existence

d’heuristiques et d’algorithmes exacts permettant de résoudre le RPP. Le HCPP est défini

sur un graphe non orienté dans lequel les arcs sont séparés en groupes qui nécessitent un

service et possèdent des relations de précédence ou une hiérarchie entre ces différents

groupes. La transformation en RPP permet d’appliquer un algorithme exact de génération

de coupes sur ce problème transformé. De plus, deux objectifs sont considérés lors de cet

article soient l’objectif hiérarchique et l’objectif de minimisation du temps de la route.

Les auteurs ont testés leur méthode sur le graphe Albaida1 qui contient 113 nœuds et 171

arcs. Ces arcs ont été séparés selon trois types de service. De plus, quelques problèmes

ont été générés de façon aléatoire, le plus grand problème contenant 150 nœuds. L’écart

maximum obtenu par rapport à la solution trouvée par séparation et évaluation

progressive est de 0,8 %.

2.3.3.4. Autres généralisations du TSP Dans la littérature récente, plusieurs généralisations du TSP ont été étudiées. Parmi

celles-ci, notons l’ajout de contraintes de préséance entre les nœuds à visiter, ensuite, une

contrainte de changement de temps sur les arcs, une contrainte de cardinalité des nœuds

et une contrainte maximale de temps de route. Finalement une généralisation du TSP

nommé le black and white traveling salesman problem.

16

Le problème du voyageur de commerce avec contraintes de préséance (TSPPC) est

appliqué dans de nombreux problèmes industriels comme l’ordonnancement, les

décisions d’acheminement des marchandises et la planification de projet. Dans ces

problèmes, il y a un ordre prédéfini entre certains nœuds du graphe. Ainsi, certains nœuds

doivent être visités avant d’autres. Moon, Kim, Choi et Seo (2002) proposent de résoudre

le TSPC avec un algorithme génétique. Les auteurs ont effectué des tests sur des

problèmes de différentes tailles. Le nombre de points et de contraintes est respectivement

de 6 et 6 pour les problèmes de petite taille, de 20 et 29 pour les moyens et de 40 et 56

pour les problèmes de grande taille. Les résultats indiquent qu’une solution optimale est

trouvée pour les problème de petite et moyenne taille alors que les résultats sont proches

de l’optimum pour les grands problèmes.

Schneider (2002) propose une extension au problème du voyageur de commerce dans

lequel les distances entre les clients peuvent varier dans le temps. Par conséquent, la

matrice des distances devient dynamique. Cette extension permet de modéliser la

congestion routière puisque le temps entre deux villes peut être différent selon le moment

de la journée à lequel on effectue le trajet. L’auteur démontre que le recuit simulé est une

excellente méthode permettant de résoudre ce problème complexe. Il présente des

résultats sur la visite des 127 cafés de la région de Augsburg, en Allemagne, dans lequel

certaines zones présentent des bouchons de circulation en après-midi.

Patterson et Rolland (2003) présentent un nouveau problème qui consiste à séparer un

graphe en plusieurs sous-graphes Hamiltoniens ayant une cardinalité minimum et

maximum, c’est-à-dire leur nombre de noeuds. Ce type de problème est nommé

cardinality constrained covering traveling salesman problem (CCC-TSP). Il ajoute deux

paramètres, L et U, correspondant aux bornes minimales et maximales quant à la

cardinalité pour chacun des tours. Les problèmes d’affectation ainsi que le TSP sont des

cas spéciaux de ce problème. Effectivement, lorsque L est égal à U et aussi égal au

nombre de points, alors le problème à résoudre est en fait un TSP. Ce problème est utile

pour tous les cas où un minimum de service est requis par l’affectation d’un maximum de

17

clients à chaque route et en même temps un minimum de clients doit être desservie par

cette route. Un exemple pratique consiste à trouver de bonnes solutions pour une

« popotte roulante » qui aurait comme contrainte un temps de route maximal, un nombre

maximal de mets à servir et un minimum de clients à servir pour être rentable. Les

auteurs ont expérimenté leur heuristique sur 30 problèmes tirés de TSPLIB. La taille des

problèmes testés varie de 51 à 226 nœuds avec 24 problèmes ayant 100 points et plus.

Les tests démontrent que l’algorithme obtient régulièrement la solution optimale.

Effectivement, pour les problèmes ayant une densité de 15%, l’écart est de moins de

0,053% de l’optimum tandis que pour les problèmes d’une densité de 100% l’écart

moyen est de moins de 0,74%. Ces résultats sont trouvés dans un temps se situant entre

6,7 et 132 818 secondes.

Paletta (2002) propose une nouvelle heuristique permettant de résoudre un problème de

voyageur de commerce périodique. Ce type de problème est défini comme suit : un

voyageur de commerce doit visiter chaque ville un nombre prédéterminé de fois durant

une période de m jours. À chaque jour, le voyageur doit retourner à la maison. L’objectif

consiste à minimiser la distance totale parcourue par le voyageur de commerce durant la

période. L’heuristique proposée permet d’interrompre la construction du tour afin d’y

introduire une procédure d’amélioration. Les tests ont été effectués sur 33 problèmes de

48 à 288 nœuds. L’heuristique permet de trouver une solution optimale pour 25

problèmes et se situe en moyenne à 0,745% de l’optimum. Finalement, l’écart de la pire

solution obtenue se situe à 1,035% de l’optimum connu.

Finalement, Bourgeois, Laporte et Semet (2003) présentent une heuristique pour une

variante particulière du TSP. Leur article traite du Black and White Traveling Salesman

Problem (BWTSP) définit sur un graphe G dans lequel les points sont segmentés en

points noirs et blancs. L’objectif consiste à trouver le tour Hamiltonien le plus court dans

le graphe en respectant deux contraintes. La première contrainte restreint le nombre de

points blancs entre deux points noirs d’excéder un entier positif Q, il s’agit donc d’une

contrainte de cardinalité. La deuxième contrainte restreint la distance entre deux points

noirs consécutifs à être inférieure à L. Le BWTSP équivaut au TSP classique lorsque les

18

valeurs de Q et L sont égales et correspondent à l’infini. Le BWTSP a de nombreuses

applications lors des cédules des lignes aériennes et en télécommunication. Par exemple,

le BWTSP est utile en ordonnancement de lignes aériennes car les séquences de vols

(points blancs) doivent être séparé par des périodes de maintenance (points noirs). Cet

article traite et compare trois différentes heuristiques concernant le BWTSP. Chacune des

heuristique contient une phase de construction, de faisabilité et une dernière phase

d’amélioration. En moyenne, après amélioration et en respectant bien tous les contraintes

du problème, les solutions réalisables obtenues se situe entre 12 et 13% de l’optimum

pour les problèmes de 50 points, entre 14 et 19% pour les problèmes de 100 points et

finalement entre 16 et 23 % pour les problèmes de 200 points. Par ailleurs, les résultats

obtenus indiquent qu’il devient plus difficile d’identifier une solution réalisable lorsque le

nombre de points noirs devient plus élevé.

19

2.4. Problèmes de tournées de véhicules et généralisations

Le problème de tournées de véhicules et ses généralisations a été largement étudié au

cours des dernières années. La figure 2.2. illustre les articles les plus récents concernant

ce problème.

Figure 2.2. : Classification des problèmes de tournées de véhicules

Tournée de véhicules

1 dépôt Multi-dépôts

Fenêtre de temps

Autres généralisations

Flotte hétérogène

Standard

- Achuthan, Caccetta, Hill (2003) - Baker, Ayechew (2003) - Baker, Carreto (2003) - Prins (2001) - Reimann, Doerner, Hartl (2003) - Toth, Vigo (2002a) - Toth, Vigo (2002b)

- Renaud, Boctor (2002) - Tarantilis, Kiranoudis, Vassiliadis (2003)

- Berger, Barkaoui (2003) - Chen, Hsiao (2003) - Hwang (2002) - Ioannou, Kritikos, Prasracos (2003) - Lau, Sim,Teo (2003) - Li, Lim (2003)

- Chan, Carter, Burnes (2001)- Wu, Low, Bai (2002)

- Arunapuram, Mathur, Solow (2003) - Belenguer,Benavent (2003) - Beullens, Muyldermans, Cattrysse , Oudheusden (2003) - Gronalt, Hartl, Reimann (2003) - Osman, Wassan (2002)

20

2.4.1. Le problème de tournées de véhicules

Le premier papier traitant du problème de tournée de véhicules a été publié vers la fin des

années 1950 par Dantzig et Ramser (1959). Ce problème, plus souvent appelé Vehicle

Routing Problem (VRP) a ensuite attiré un grand nombre de chercheurs car il est

théoriquement très intéressant. De plus, les applications du VRP sont nombreuses. Ainsi,

la plupart des entreprises qui doivent livrer un produit à plusieurs clients font face à ce

problème. La littérature du problème VRP est par conséquent très volumineuse.

Le problème de tournées de véhicules peut être définit comme un problème où de

nombreux clients doivent être desservis à partir d’un unique dépôt avec des demandes

connues. Mathématiquement, le VRP se défini sur un graphe G = (V, A) où V = {v0,…,

vn} représente l’ensemble des points, c’est-à-dire des clients à visiter et A = {(vi, vj) : vi, vj

∈ V, i ≠ j} représentant l’ensemble des arcs possibles. Le point v0 représente le dépôt

qui est le point de départ et d’arrivée de toutes les routes. Une distances dij est associée à

chaque arc (i, j) A∈ , ces distance sont symétriques c’est-à-dire que dij = dji Aji ∈∀ , .

On pose comme hypothèse que les véhicules sont identiques avec une contrainte de

capacité Q et les clients ont une demande déterminée qi. Une limite L peut également être

imposée sur la durée maximale des routes. Dans quelques versions du problème, le

nombre de véhicules est déterminé à priori. Dans les autres, le nombre de véhicules est

une variable de décisions. Les routes doivent permettre de visiter tous les clients une et

une seule fois. De plus, la demande totale de tous les clients d’une route ne peut excéder

la capacité Q d’un véhicule. Les véhicules sont affectés aux routes de manière à

minimiser l’objectif qui peut être, par exemple, la distance parcourue pour visiter tous les

clients.

Il existe de nombreuses formulations du problème de tournée de véhicule. La formulation

suivante est tirée de Fisher et Jaikumar (1981). Définissons tout d’abord l’ensemble des

variables nécessaires pour effectuer la formulation mathématique.

21

Paramètres :

K : Nombre de camions disponibles.

N : Nombre de clients à visiter. Les clients sont numérotés de 1 à n et l’entrepôt a

le numéro 0.

Qk : Capacité du camion k.

qi : Demande du client i.

dij: Distance entre la ville i et j.

Variables de décision :

yik : Variable de décision binaire qui est égale à 1 si la commande du client i est livrée par

le camion k et à 0 autrement.

xijk :variable de décision binaire qui est égale à 1 si le camion k voyage de la ville i vers la

ville j et à 0 autrement.

Formulation :

Minimiser ijk

n

i

n

j

k

kij xd∑∑∑

= = =0 0 1 (4.1)

Sujet à des contraintes de problèmes d’affectation généralisé :

∑=

≤n

ikiki Qyq

1 k= 1,…,K (4.2)

∑=

=K

kiky

1

(4.3)

0=iky ou 1 i = 0,…,n; k=1,…, K (4.4)

K i = 0

1 i = 1,…, n

22

et à des contraintes du problème du voyageur de commerce (TSP)

∑=

=n

ijkijk yx

0 j = 0,…n; k = 1,…, K (4.5)

∑=

=n

jikijk yx

0 i = 0,…,n; k = 1,…, K (4.6)

∑ ∑∈ ∈SI SJ

ijkx ≤ | S| - 1 pour tout S de (1,…,n), (4.7)

2 ≤ | S| ≤ n -1, k = 1,…., K

ijkx = 0 ou 1 i = 0,…, n (4.8) j = 0,…, n

k = 1,…,K

Cette formulation permet de minimiser la distance parcourue par l’ensemble des camions.

La contrainte (4.2) permet de s’assurer que le chargement des véhicules respecte leur

capacité. La contrainte (4.3.) garantit que chacune des routes débute et se termine au

dépôt et que chacun des clients est affecté à un et un seul camion. Les contraintes (4.5) à

(4.8) permettent d’éviter les sous-tours et que chacun des clients est visité une et une

seule fois. Par conséquent, il s’agit des contraintes utilisées pour un TSP.

2.4.2. Algorithme pour le VRP standard

Quatre articles récents traitent le problème de tournées de véhicules à un seul dépôt avec

contrainte de capacité. Dans ce cas, un ensemble de clients avec une demande et une

adresse connues requièrent une livraison à partir d’un dépôt unique et avec une flotte de

véhicules identiques. La demande cumulée des clients se trouvant sur la même route ne

23

doit pas dépasser la capacité des véhicules utilisés. L’objectif consiste à minimiser la

distance parcourue par tous les véhicules pour visiter une et une seule fois tous les clients

puisque ce problème ne tient pas compte de la limite sur la durée des tournées, il est

nommé le « capacitated vehicle routing problem » (CVRP).

Toth et Vigo (2002a) présentent une revue des algorithmes exacts utilisés pour résoudre

le CVRP. Dans leur papier, seulement les restrictions sur la capacité des véhicules sont

imposées et l’objectif consiste à minimiser le coût total (i.e. le nombre de route et/ou leur

longueur ou le temps de route nécessaire pour servir tous les clients). Par conséquent, il

n’y a aucune contrainte concernant la durée maximale des routes. On considère 2 cas, soit

celui où les distances sont symétriques et le second où elles sont asymétriques. Les

auteurs présentent deux algorithmes de « branch and bound » pour résoudre ce

problème. Les algorithmes exacts permettent de résoudre des problèmes CVRP

asymétriques allant jusqu’à 300 points et quatre véhicules. Ces résultats sont obtenus en

1000 CPU secondes. Dans leur revue, Toth et Vigo (2002a) discutent des algorithmes

exacts permettant de résoudre le CVRP symétrique. Ils présentent les algorithmes de

Fisher (1994) et Miller (1995) en soulignant qu’il est difficile de comparer entre eux les

algorithmes puisque chacun des auteurs posent des hypothèses différentes sur les mêmes

problèmes. Par exemple, Fisher (1994) interdit les routes qui visitent un seul client tandis

que Miller (1995) les permet.

Pour résoudre le CVRP, Baker et Ayechew (2003) utilisent un algorithme génétique.

Après avoir trouvé des routes individuelles intéressantes, les tournées sont améliorées en

utilisant la méthode 2-opt suivie du 3-opt. Les distances obtenues par l’algorithme

génétique se situent en moyenne à 0,5% de l’optimum. Ces tests ont été effectués sur des

problèmes de 50 à 199 points dont les résultats optimaux de la littérature sont présentés

au tableau 2.2. Ils trouvent la solution optimale à quatre reprises.

L’article de Achuthan, Caccetta et Hill (2003) traite lui aussi du CVRP à l’aide de la

méthode génération de coupe. Plus spécifiquement, ils développent de nouvelles coupes

et une procédure de recherche permettant d’identifier les violations comme par exemple,

24

la création de sous-tour. Les tests ont tout d’abord été effectués sur 1 650 problèmes

générés aléatoirement. Par la suite, 24 problèmes standard de la littérature ont été testés.

Pour chacun des problèmes, le nombre de véhicules est fixé au nombre minimal de

camions requis. Le temps maximal imposé pour trouver une solution est d’une heure,

c’est pourquoi dans le tableau 2.2. quelques bornes supérieures ne sont pas disponibles

(N/A). Le nombre de clients est de 44 à 199. Le tableau 2.2. présente les résultats de 14

problèmes présenté par Achtuhan, Caccetta et Hill. Lorsque les routes à un seul client

sont permises, les problèmes 11, 18 et 19 ont été résolus optimalement en respectivement

487,4, 35,3 et 172,2 secondes. Pour le problème 17, une meilleure solution a été trouvée

mais il n’est pas prouvé que le résultat est optimal puisque la limite de temps de calcul a

été atteinte. Les temps de résolution pour les problèmes 11, 18, 19 et 17 sont de 488,7,

15,4, 176,3 et 458 secondes respectivement.

25

Tableau 2.2. : Résultats du CVRP

Routes à un seul

client permises

Routes à un seul

client interdit Fisher (1994)

No du

problème

Nb

de

client Borne

inférieure

Borne

supérieure

Borne

inférieure

Borne

supérieure

Meilleure

solution

connue Borne

inférieure

Borne

supérieure

Publication

11 50 514.58 524.61 514.58 524.61 524.61* 507.09 N/A Christofides,

Eilon (1969)

12 75 786.29 N/A 786.29 N/A 835.26 755.05 N/A Christofides,

Eilon (1969)

13 100 799.07 N/A 799.07 N/A 826.14 785.86 N/A Christofides,

Eilon (1969)

14 150 950.65 N/A 950.57 N/A 1028.14 932.68 N/A Christofides

et al (1979)

15 199 1114.17 N/A 1153.99 N/A 1298.79 1096.72 N/A Christofides

et al (1979)

16 120 862.98 N/A 862.98 N/A 1042.11 N/A N/A Christofides

et al (1979)

17 100 785.29 819.56 813.73 819.56 819.56* 817.77 819.56 Christofides

et al (1979)

18 44 721.88 723.54 723.54 723.54 723.54* 720.76 723.54 Fisher

(1994)

19 71 238.51 241.97 238.51 241.97 241.97* 237.76 241.97 Fisher

(1994)

20 134 1120.16 N/A 1120.16 N/A 1163.60 1133.73 1163.60 Fisher

(1994)

21 75 659.17 752.25 659.17 752.25 N/A N/A N/A Reinelt

(1981)

22 75 705.25 949.26 705.25 949.26 N/A N/A N/A Reinelt

(1981)

23 75 932.41 N/A 932.41 N/A N/A N/A N/A Reinelt

(1981)

24 100 1000.4 N/A 1003.17 1175.19 N/A N/A N/A Reinelt

(1981)

Source : Achuthan, Cacetta et Hill (2003)

26

Étant donné que les algorithmes exacts ne réussissent toujours pas à trouver des solutions

pour des problèmes de grandes tailles, plusieurs chercheurs se sont penchés vers des

heuristiques. D’énormes progrès ont été effectués ces dernières années concernant les

problèmes de tournées de véhicules. Taillard (1993) a apporté une grande contribution en

trouvant la meilleure solution pour la plupart des problèmes de la littérature. Son

heuristique consiste essentiellement à décomposer le problème en sous-problèmes et il

propose deux méthodes distinctes de partitionnement. Chacun des sous-problèmes est

résolu en utilisant une approche tabou. Après un certain nombre d’itérations, les sous-

problèmes sont réunis pour reformer le problème entier. Le tableau 2.3. présente une

comparaison de la performance des métaheuristiques utilisées au cours des dix dernières

années. Les heuristiques sont classées selon le pourcentage d’écart moyen par rapport à la

meilleure solution connue. On peut y remarquer que le type d’algorithme le plus utilisé

pour résoudre le problème de tournée de véhicule est celui de la recherche tabou.

Le tableau 2.4. présente les meilleures solutions connues sur les dix problèmes classiques.

Le tableau 2.5. présente les problèmes de la littérature pour lesquels les clients sont

groupés de façon à simuler la présence de villes. Tous ces tableaux démontrent

clairement que Taillard (1993) domine la course à l’optimum pour les problèmes de

petites tailles tirés de Christofides et Eilon (1989). Effectivement, ce dernier trouve la

meilleure solution pour 12 des 14 problèmes proposés. De plus, il se situe en moyenne à

0,05 % d’écart de la meilleure solution trouvée.

27

Tableau 2.3. : Comparaison des métaheuristiques utilisées

Algorithme

utilisé

% écart par

rapport à la

meilleure

solution

Nb de

meilleures

solutions

trouvées

Temps

moyen

(min)

Publication

Tabou 0,05 12 - Taillard (1993)

Algorithme

génétique 0,08 10 5,2 Prins ( 2001)

Tabou 0,1 5 103 Xu-Kelly (1996)

Tabou 0,2 9 - Gedreau et al. (1994)

Tabou 0,39 6 - Taillard (1993)

Tabou 0,55 6 - Rego et Roucairol (1996)

Tabou

granulaire 0,55 4 3.5 Toth et Vigo (2002b)

Tabou 0,68 5 - Gendreau et al. (1991)

Tabou 0,77 4 - Rego et Roucairol (1996)

Tabou 0,86 5 46,8 Gendreau et al. (1994)

Algorithme

génétique

(3000

croisements

max)

0,9 5 0,7 Prins (2001)

Tabou 1,01 4 26,1 Osman (1993)

Tabou 1,03 3 34 Osman (1993)

Recuit simulé 2,09 2 - Osman (1993)

Source : Prins (2003)

28

Tableau 2.4. : Résultats sur les problèmes de Christofides et Eilon (1989)

Nom Nb clients Capacité

véhicules

Longueur

max route

Temps de

service

Meilleure

solution Publication

C1 50 160 ∞ 0 524,61 Taillard (1993)

C2 75 140 ∞ 0 835,26 Taillard (1993)

C3 100 200 ∞ 0 836,14 Taillard (1993)

C4 150 200 ∞ 0 1028,42 Taillard (1993)

C5 199 200 ∞ 0 1291,45 Rochat et Taillard

(1995)

C6 50 160 200 10 555,43 Taillard (1993)

C7 75 140 160 10 909,68 Taillard (1993)

C8 100 200 230 10 865,94 Taillard (1993)

C9 150 200 200 10 1162,55 Taillard (1993)

C10 199 200 200 10 1395,85 Rochat et Taillard

(1995)

Source : Reimann, Doerner, Hart (2003)

Tableau 2.5. : Problèmes par grappe


véhicules

Longueur

max route

Temps de

service

Meilleure


C11 120 200 ∞ 0 1042,11 Taillard (1993)

C12 100 200 ∞ 0 819,56 Taillard (1993)

C13 120 200 720 50 1541,14 Taillard (1993)

C14 100 200 1040 90 866,37 Taillard (1993)


Deux autres articles présentent aussi des résultats très intéressant pour le problème de

VRP à un seul dépôt, il s’agit de Prins (2001) et Toth et Vigo (2002b). Prins (2001)

privilégie l’algorithme génétique tandis que Toth et Vigo (2002b) adoptent la recherche

taboue. Ces derniers proposent dans leur algorithme une réduction de l’espace de

recherche. Plus spécifiquement, Toth et Vigo réduise initialement le graphe en éliminant

29

tous les arcs qui excèdent un certain seuil. Ce seuil est déterminé par l’estimation de la

moyenne de la longueur des arcs d’une bonne solution réalisable c’est ce qu’ils appellent

un algorithme tabou granulaire.

D’autre part, Baker et Carreto (2003) présentent une interface qui a été développée afin

de résoudre les problèmes de VRP. Ils ont utilisé un heuristique basée sur une recherche

adaptative aléatoire gloutonne. Le système décrit permet de combiner les connaissances

et l’intuition avec la puissance de l’ordinateur afin de trouver de bonnes solutions. Ainsi,

l’utilisateur a un contrôle sur les routes finales ce qui est beaucoup plus acceptable en

pratique. Une séance interactive d’au plus 15 minutes permet de trouver des routes

intéressantes. Les tests effectués sur des problèmes de 50 à 199 points permettent

d’obtenir des résultats à moins de 1% de la meilleure solution connue.

Pour les problèmes de grande taille entre 240 et 483 clients, ce sont Reimann, Doerner et

Hartl (2003) qui obtiennent les meilleurs résultats. Ces derniers trouvent une meilleure

solution pour 10 des 20 problèmes. De plus, ils égalisent quatre autres résultats dont la

meilleure solution a déjà été trouvée. L’heuristique utilisée pour trouver ces solutions est

une heuristique composite inspirée de l’algorithme d’optimisation par colonie de fourmis.

Effectivement, Reimann, Doerner et Hartl ont utilisé le principe des phéromones lors de

la construction de leur heuristique. Par contre, d’autres algorithmes ont aussi été utilisés,

par exemple, on retrouve le 2-opt, l’algorithme de balayage de Gillet et Miller (1974) et

l’algorithme modifié de Miehle présenté par Spaeth (1977). Ces résultats sont résumés au

tableau 2.6.

30

Tableau 2.6. : Problèmes de grandes tailles


véhicules

Longueur

max route

Temps de

service

Meilleure


1 240 550 650 0 5644,02 Reimann, Doerner,

Hartl (2003)

2 320 700 900 0 8447,92 Prins (2001)

3 400 900 1200 0 11036,22 Prins (2001)

4 480 1000 1600 0 13624,52 Prins (2001)

5 200 900 1800 0 6460,98 Prins (2001)

6 280 900 1500 0 8412,80 Prins (2001)

7 360 900 1300 0 10195,59 Prins (2001)

8 440 900 1200 0 11828,78 Prins (2001)

9 255 1000 ∞ 0 586,87 Reimann, Doerner,

Hartl (2003)

10 323 1000 ∞ 0 746,56 Golden et al. (1998)

11 399 1000 ∞ 0 927,27 Reimann, Doerner,

Hartl (2003)

12 483 1000 ∞ 0 1133,79 Prins (2001)

13 252 1000 ∞ 0 865,07 Reimann, Doerner,

Hartl (2003)

14 320 1000 ∞ 0 1086,24 Prins (2001)

15 396 1000 ∞ 0 1358,21 Reimann, Doerner,

Hartl (2003)

16 480 1000 ∞ 0 1635,16 Reimann, Doerner,

Hartl (2003)

17 240 1000 ∞ 0 708,76 Reimann, Doerner,

Hartl (2003)

18 300 200 ∞ 0 998,83 Reimann, Doerner,

Hartl (2003)

19 360 200 ∞ 0 1367,20 Reimann, Doerner,

Hartl (2003)

20 420 200 ∞ 0 1822,94 Reimann, Doerner, Hartl (2003)


31

2.4.3. Composition de la flotte

Le problème général de tournée suppose que les camions d’une entreprise sont

homogènes. Pourtant, il est rare que tous les camions soient identiques. Ils existent

souvent des distinctions entre les camions, ils n’ont pas tous le même âge, donc ont des

coûts variables différents, la capacité de chargement n’est pas la même ou encore il peut

s’agir de différences concernant le type de véhicule (i.e. camions réfrigérés, camions

citernes). Cet aspect du problème a été traité récemment dans deux articles.

Le papier de Renaud et Boctor (2002) présente le problème de tournée avec une flotte de

véhicules hétérogènes. La flotte de véhicules peut être composée de véhicules avec des

capacités différentes. Aussi, les coûts fixes et variables des véhicules peuvent différer

d’un véhicule à l’autre. La location d’une partie ou de la totalité de la flotte est possible

procurant ainsi l’avantage d’une grande flexibilité puisque la composition de la flotte

peut varier fréquemment. L’objectif consiste à minimiser le coût total composé des coûts

fixes et variables de l’utilisation des véhicules. De plus, il faut trouver la meilleure

affectation des véhicules aux différentes routes. Dans la version étudiée, les arcs sont non

orientés puisque la matrice est symétrique. En plus de respecter les capacités des

véhicules tout en répondant aux demandes, une autre contrainte s’ajoute. Effectivement,

la durée totale de chacune des routes incluant le temps de parcours et le temps de service

ne doit pas excéder une durée maximale. Les auteurs utilisent une heuristique de balayage

pour générer différentes routes. Leur heuristique peut résoudre les problèmes Euclidiens

de même que les problèmes non-Euclidiens ce qui est une première pour les algorithmes

de balayage. Les résultats, tirés de tests effectués sur 20 problèmes de 50 à 100 points,

démontrent que cette heuristique fonctionne mieux que les heuristiques connues dans la

littérature. Les auteurs comparent d’ailleurs leurs résultats à ceux obtenus par Osman et

Salhi (1996), Taillard (1999) et Gendreau et al. (1999). L’heuristique proposée permet

d’obtenir un écart de 0,49% en moyenne par rapport à la meilleure solution obtenue par

recherche tabou et ce dans un temps de calcul égal moyen de 179 secondes. Aussi, les

auteurs proposent une version tronquée de cette heuristique qui permet de réduire le

temps de calcul à 154 secondes mais en acceptant une légère augmentation de l’écart se

32

situant maintenant à 0,63%. Cette dernière version peut représenter une alternative

intéressante lorsque l’on désire obtenir rapidement une solution.

Tarantilis, Kiranoudis et Vassiliadis (2003) approchent ce problème d’une autre façon.

Dans leur cas, la flotte comporte plusieurs type de véhicules ayant chacun une capacité

varié. Par contre, le nombre de véhicule de chaque type est limité. La flotte est donc fixe,

c’est-à-dire qu’on ne considère pas la possibilité pour les entreprises de varier la

composition de la flotte de véhicules. L’article décrit une méthode basée sur un seuil

d’acceptation appelé « backtracking adaptive treshold accepting » (BATA) décrit plus

précisément dans la section autres métaheuristiques. Les problèmes étudiés comportent

entre 50 et 100 points, localisé aléatoirement dans un graphe. Ce problème a peu été

étudié dans la littérature. Seulement, Taillard (1999) l’avait déjà présenté. La méthode

BATA donne des solutions en moyenne 0,31% meilleures que Taillard (1999). Cet

algorithme procure six nouvelles meilleures solutions.

2.4.4. Fenêtres de temps

Les problèmes de tournées de véhicules peuvent être complexifiés si on ajoute des

fenêtres de temps. En anglais ce problème est nommé Vehicle Routing Problem with

Time Windows (VRPTW) et il se définit de la façon suivante. Soit G = (V, A) où V =

{v0,…, vn} représente l’ensemble des points, c’est-à-dire des clients à visiter et A = {(vi,

vj) : vi, vj ∈ V, i ≠ j} représentant l’ensemble des arcs possibles. Le point v0 représente

le dépôt qui est le point de départ et d’arrivée de toutes les routes. On pose comme

hypothèse que les véhicules sont identiques avec une contrainte de capacité Q et que les

clients ont une demande déterminée qi. Chaque client a et un temps de service δi. Le

début de la visite du client vi doit être à l’intérieur de la fenêtre de temps [ei, fi]. Cela

signifie que le client désire être visité à une période déterminée de la journée. Ainsi, un

client peut préférer recevoir ses colis durant les heures d’ouverture de son entreprise. Cet

ajout au problème limite la flexibilité car deux clients voisins peuvent être disponibles à

deux périodes très différentes de la journée. Par contre, l’ajout de la contrainte de fenêtres

de temps est très utile pour un client qui sait ainsi à quelle heure son colis lui sera livré et

33

qui pourra donc prévoir cette réception dans la planification des tâches prévues à l’horaire

de la journée. Le coût considéré lors du VRPTW n’est pas seulement le coût de parcourir

la distance entre tous les clients mais également le coût associé au temps d’attente car

lorsqu’un véhicule arrive en avance chez un client il doit attendre que celui-ci soit prêt à

le recevoir.

Les problèmes tests reconnus sont sans aucun doute les 56 problèmes de Solomon (1987).

Ces problèmes sont séparés en 6 classes : C1, C2, R1, R2, RC1 et RC2. Ils possèdent

tous 100 clients, un dépôt, des contraintes de capacité pour les camions et des fenêtres de

temps pour chacun des clients. Dans ces problèmes, les coordonnées géographiques ont

été générées aléatoirement en utilisant une distribution uniforme (problèmes C1 et C2),

une distribution par grappe (problèmes R1 et R2) représentant la proximité des clients

dans une ville ou un mélange de ces deux problèmes (problèmes RC1 et RC2). De plus,

les problèmes C1, R1 et RC1 possèdent un court horizon de planification et seulement

quelques clients sont inscrits dans la même route dus à des contraintes de capacité et de

durées maximales. À l’opposé, les problèmes C2, R2 et RC2 se déroulent sur un plus

long horizon. Cette caractéristique jumelée avec de grandes capacités de chargement des

camions permet à plusieurs clients d’être desservis par le même camion. Les tableaux

2.7, 2.8, 2.9, 2.10, 2.11 et 2.12 présentent les meilleurs résultats obtenus pour ces

problèmes à ce jour. Finalement, le tableau 2.13 présente une comparaison entre les

publications pour tous les ensembles de problèmes.

34

Tableau 2.7. : Meilleures solutions pour les problèmes C1

Tests Nb véhicules Distances totales Références

C101 10 828,94 Rochat, Taillard (1995)








*Source : Berger et Barkaoui (2003) et Li et Lim (2003)

Tableau 2.8. : Meilleures solutions pour les problèmes C2











35

Tableau 2.9. : Meilleures solutions pour les problèmes R1


R101 19 1650,80 Rochat, Taillard (1995)


1292,85 Homberger, Gehring (1999) R103 13

1292,68 Li, Lim (2003)


1007,31 Li, Lim (2003)



1113,69 Cordeau, Laporte, Mercier (2000) R107 10

1104,66 Li, Lim (2003)

963,99 Shaw (1998) R108 9

960,88 Berger, Berkaoui (2003)

R109 11 1194,73 Homberger, Gehring (1999)

R110 10 1124,40 Rousseau, Gendreau, Pesant (2002)




36

Tableau 2.10. : Meilleures solutions pour les problèmes R2





849,62 Cordeau, Laporte, Mercier (2000) R204 2

849,05 Li, Lim (2003)



914,39 Rochat, Taillard (1995) R207 2

905,13 Li, Lim (2003)

R208 2 730,771 Baker et al (2000)


R210 3 939,373 Baker et al (2000)


906,19 Berger, Barkaoui (2003)


37

Tableau 2.11. : Meilleures solutions pour les problèmes RC1


RC101 14 1696,94 Taillard et al (1997)

RC102 12 1554,75 Taillard et al (1997)

RC103 11 1262,02 Rochat, Taillard (1995)

RC104 10 1135,48 Cordeau, Laporte, Mercier (2000)

1633,72 Rousseau, Gendreau, Pesant (2002) RC105 13

1629,44 Berger, Barkaoui (2003)

1427,13 Cordeau, Laporte, Mercier (2000)

RC106 11 1424,73

Berger, Barkaoui (2003) et Li, Lim

(2003)

RC107 11 1230,54 Taillard et al (1997)

RC108 10 1139,82 Taillard et al (1997)


38

Tableau 2.12. : Meilleures solutions pour les problèmes RC2



1389,57 Homberger, Gehring (1999) RC202 3

1374,27 Li, Lim (2003)

RC203 3 1060,45 Homberger, Gehring (1999)



RC206 3 1153,93 Rousseau, Gendreau, Pesant (2002)


RC208 3 829,69 Rousseau, Gendreau, Pesant (2002)


39

Tableau 2.13. : Comparaison des résultats moyens entre les publications

C1 C2 R1 R2 RC1 RC2 Publications Véh Dist. Véh Dist. Véh Dist. Véh Dist. Véh

Dist. Véh

Dist.

Rochat, Taillard (1995) 10 828,38 3 589,86 12,25 1208,50 2,91 961,72 11,88 1377,39 3,38 1119,59

Chiang, Russell (1997) 10 828,38 3 591,42 12,17 1204,19 2,73 986,32 11,875 1397,44 3,25 1229,54

Taillard et al (1997) 10 828,38 3 589,86 12,17 1209,35 2,82 980,27 11,50 1389,22 3,38 1117,44

Homberger, Gehring (1999) 10 828,38 3 589,86 11,92 1220,97 2,73 968,55 11,50 1388,24 3,25 1140,43

Cordeau, Laporte, Mercier

(2000) 10 828,38 3 589,86 12,08 1210,14 2,73 969,58 11,50 1389,78 3,25 1134.52

Baker et al (2000) 10 828,38 3 589,86 12,41 1200,54 3 936,51 12 1383,21 3,38 1116,51

Liu, Shen (1999) 10 830,06 3 591,03 12,17 1249,57 2,82 1016,58 11,88 1412,87 3,25 1204,87

Rousseau, Gendreau,

Pesant (2000) 10 828,38 3 589,86 12,08 1210,21 3 941,08 11,63 1382,78 3,38 1105,22

Li, Lim (2003) 10 828,38 3 589,86 12,08 1215,14 2,91 953,43 11,75 1385,47 3,25 1142,48

Berger, Berkaoui (2003) 10 828,38 3 589,93 11,92 1221,1 2,73 975,43 11,50 1389,89 3,25 1159,37


On observe ces dernières années une recrudescence de la recherche sur le problème de

tournées de véhicules avec fenêtres de temps. Effectivement, plusieurs auteurs traitent ce

problème sous différentes facettes dans la littérature. Tout d’abord, Hwang (2000)

présente dans son article une interface graphique permettant de résoudre des problèmes

VRPTW grâce à un algorithme génétique. L’interface développée par Hwang (2000)

permet de résoudre des problèmes de 10 à 99 villes. Comme il est possible de le constater

dans les tableaux précédents, la compétition entre chercheurs est forte pour trouver la

meilleure heuristique pour résoudre le VRPTW. Li et Lim (2003) utilisent, pour résoudre

ce problème, un algorithme de recuit simulé. Ils obtiennent 7 nouveaux meilleurs

résultats que ceux présentés dans la littérature précédente et 19 des résultats présentés

égalisent les meilleures solutions connues à ce jour. Quant aux autres solutions obtenues,

elles sont très près de la meilleure solution connue dans la littérature. Ces résultats sont

40

inculs dans les tableaux 2.9 à 2.12. Les améliorations apportés par Li et Lim (2003) sont

résumés au tableau 2.14.

Tableau 2.14. : Résultats de Li et Lim (2003)

Meilleure solution connue Nouvelle meilleure solution Problèmes

Nb véhicules Distance Référence Nb véhicules Distance

R103 13 1292,85 Homberger, Gehring (1999) 13 1292,68


R107 10 1113,69 Cordeau, Laporte,

Mercier (2000) 10 1104,66


Mercier (2000) 2 849,05

R207 2 914,39 Rochat, Taillard (1995) 2 905,13

RC106 11 1427,13 Cordeau, Laporte,

Mercier (2000) 11 1424,73

RC202 3 1389,57 Homberger, Gehring (1999) 3 1374,27

Berger et Barkaoui (2003) développent un nouvel algorithme génétique. L’approche est

basée sur l’évolution simultanée de deux populations de solutions et une relaxation

partielle de quelques contraintes. Ils ont effectués leurs tests sur les problèmes de

Solomon et ont trouvés cinq meilleures solutions que celles de la littérature. Ces

améliorations sont présentées au tableau 2.15 et inclus dans les tableaux 2.9 à 2.11.

41

Tableau 2.15. : Résultats de Berger et Barkaoui (2003)

Meilleure solution connue Nouvelle meilleure solution Problèmes

Nb véhicules Distance Référence Nb véhicules Distance

R108 9 963,99 Shaw (1998) 9 960,88


Mercier (2000) 10 1119,00

RC105 13 1633,72 Rousseau, Gendreau,

Pesant (2002) 13 1629,44

RC106 11 1427,13 Cordeau, Laporte,

Mercier (2000) 11 1424,73


Les auteurs Lau, Sim et Teo (2003) traitent d’une variante du problème VRP avec

fenêtres de temps dans lequel un nombre limité de véhicules est disponible (m-VRPTW).

Les auteurs proposent une approche tabou avec une liste permettant de conserver les

clients non visités ainsi qu’un mécanisme introduisant un nouveau véhicule afin de

maximiser le nombre de clients visités dans cette route tout en respectant la capacité du

véhicule. De plus, ils relaxent les fenêtres de temps en permettant des retards mais avec

un coût de pénalité associé à ce retard. Lau, Sim et Teo (2003) ont testé leur algorithme

sur les 56 problèmes proposé par Solomon (1987). Ils parviennent à battre l’optimum

connu dans huit cas et égalise ce dernier pour sept problèmes.

Lorsqu’il est possible de violer la contrainte des fenêtres de temps on parle du problème

de tournées avec fenêtres de temps souples mieux connu sous le nom de Vehicle Routing

Problem with Soft Time Window contraints (VRPSTW). La contrainte de fenêtre de temps

est alors relaxée permettant de livrer avant ou après le début et la fin de la fenêtre de

temps. Par contre, une pénalité sera alors encourue reflétant l’insatisfaction des clients

42

non desservis dans leur fenêtre de temps. Ioannou, Kritikos et Parastacos (2003) aborde

ce problème dans leur papier. Ils proposent un générateur de problèmes de tournées de

véhicules où chaque problème est caractérisé par un certain nombre de clients pour

lesquels on peut violer la fenêtre de temps. Chacun des problème est résolu avec un

approche de construction soit le voisinage le plus près. L’heuristique proposée permet de

réduire le nombre de véhicules requis avec un faible degré de violation des fenêtres de

temps et une durée des parcours intéressante.

.

Chen et Hsiao (2003) proposent que non seulement les nœuds aient des fenêtres de temps

mais aussi les arcs. Effectivement, les voyageurs et les véhicules ne sont pas toujours

disponibles pour effectuer un trajet entre deux villes. Cette contrainte nommée « body

clock » vient du fait que les voyageurs ont un horaire de travail et doivent s’arrêter pour

manger. Par ailleurs, les équipements nécessitent des opérations cycliques tel que les

opérations de maintenance. Durant ces opérations, ils ne sont pas disponibles pour

desservir un client. Les auteurs présentent donc deux algorithmes de construction pour

les problèmes de livraison avec contraintes « body clock ».

2.4.5. Multi-dépôts Wu, Low et Bai (2002) présentent une méthode pour résoudre le problème de localisation

et de tournées à partir de dépôts multiples (MDLRP). Les problèmes généraux de

localisation et de tournées (LRP) permettent de trouver le nombre optimal de centres de

distributions simultanément avec les cédules des véhicules et les routes de distribution

dans le but de minimiser le coût total du système. Étant donné la complexité inhérente à

ce problème, les auteurs proposent une décomposition de ce dernier en un problème de

localisation allocation (LAP) et en un VRP. Chaque sous-problème est résolu avec un

algorithme de recuit simulé. La taille des problèmes étudiés varie de 75 à 150 nœuds.

Le deuxième article compose avec des dépôts multiples et des demandes stochastiques.

Dans ce cas, ce n’est qu’une fois arrivé à un point de vente que le livreur découvre la

demande réelle. Ainsi, Chan, Carter et Burnes (2001) traitent du problème de multi-

43

dépôts, multi-véhicules, de localisation et d’acheminement avec demandes stochastiques

(MDMVRLP). Le ravitaillement d’une usine à partir de plusieurs dépôts nécessite

plusieurs études. Tout d’abord, il est nécessaire de bien localiser les centres de

distribution. Ensuite, une flotte de véhicules de livraison de la bonne taille doit être

associée à chacun de ces centres. Finalement, les livraisons doivent être faites à temps et

en fonction des matières premières disponibles. De nos jours, avec les livraisons juste-à-

temps, on souhaite répondre exactement à la demande en évitant le plus possible les

surplus d’inventaire et les pénuries. Les auteurs proposent un modèle et une solution pour

ce type de problème. Ils utilisent une adaptation de l’algorithme de Clarke et Wright afin

de résoudre ce problème. Cette heuristique a été préférée puisqu’il est plus flexible

permettant de mieux s’ajuster aux nombreuses contraintes de ce problème.

Notons finalement que Renaud, Laporte et Boctor (1996) ainsi que Cordeau, Gendreau et

Laporte (1997) ont proposé un algorithme de recherche tabou pour le problème de

tournées de véhicules avec plusieurs dépôts.

2.4.6. Autres généralisations du problème de tournées de véhicules

2.4.6.1. Le problème de tournées sur les arcs

Lors de problèmes de tournées de véhicules, il est aussi possible que la demande soit

située sur les arcs et non sur les nœuds. Plusieurs applications réelles de ce type de

problème sont possibles tel que la collecte des ordures, le déneigement des routes et le

balayage des routes. D’ailleurs deux articles traitant de cas réels de localisation de la

demande sur les arcs sont présentés à la section 2.5.

Le problème de tournée avec capacités sur les arcs est défini sur un graphe connexe non

orienté avec des demandes connues et des coûts sur chacun des arcs. Les véhicules sont

identiques. Chacune des routes débute et se termine au dépôt. De plus, leur demande

totale ne doit en aucun cas excéder la capacité du véhicule. Il suffit de trouver le coût

44

minimum des routes pour les véhicules qui doivent parcourir tous les arcs. Les auteurs

Belenguer et Benavent (2003) ont utilisé un algorithme de plan de coupe pour résoudre ce

problème particulier. Par contre, Beullens, Muyldermans, Catrysse et Oudheusden (2003)

ont préféré une heuristique de recherche non déterministe.

Les tableaux suivants permettent de comparer les résultats obtenus par les deux articles

traitant du problème de tournée avec capacités sur les arcs, puisque les tests ont été

effectués sur les mêmes problèmes tirés d’articles de la littérature. Pour les 23 problèmes

tirés de Golden et al. (1983), l’heuristique de Beulens et al. (2003) génère en moyenne

des résultats légèrement meilleurs que Belenguer et Benavent (2003) mais nécessite un

temps de calcul plus élevé. Par contre, en ce qui concerne les 6 problèmes tirés de Kiuchi

et al. (1995), il est possible de constater au tableau 2.17 que les résultats de Beulens et al.

sont sans contredit les meilleurs puisque tous les problèmes sont résolus de façon

optimale. Finalement, les résultats des tests effectués sur les 34 problèmes de Benavent et

al. (1992). sont présentés au tableau 2.18. Les résultats démontrent que l’heuristique

proposée par Belenguer et Benavent (2003) permet en moyenne d’obtenir un moindre

écart par rapport à l’optimum et ce dans un temps de calcul moins élevé mais le nombre

de problèmes résolus de manière optimale est moins élevé comparativement à Beulens et

al. (2003).

Tableau 2.16. : Résultats des problèmes tirés de Golden et al. (1983)

Écart moyen (%) Écart maximum

(%) Nb de problèmes

optimaux Temps de calcul

moyen (secondes) Belenguer et

Benavent 0,14 1,75 20 0,13

Beulens et al. 0,13 2,99 22 1,75

Tableau 2.17. : Résultats des problèmes tirés de Kiuchi et al. (1995)

Écart moyen (%) Écart maximum (%)

Nb de problèmes optimaux

Temps de calcul moyen (secondes)

Belenguer et Benavent

0,58 3,48 5 0,06

Beulens et al. 0 0 6 0

45

Tableau 2.18. : Résultats des problèmes tirés de Benavent et al. (1992)

Écart moyen (%) Écart maximum (%)

Nb de problèmes optimaux

Temps de calcul moyen (secondes)

Belenguer et Benavent

0,41 3,13 20 2,18

Beulens et al. 1,58 11,24 23 18,49

2.4.6.2. Le VRP avec charges pleines

Dans la plupart des problèmes de VRP, on suppose que les chargements sont partiels (less

than truckload) c’est-à-dire que l’on doit visiter plusieurs clients pour charger le camion.

Un chargement complet plus souvent appelé « full truckload » (TL) signifie que la

commande d’un seul client permet de remplir la capacité du camion. Arunapum, Mathur

et Solow (2003) abordent une variante du VRP considérant des chargements complets, il

s’agit du « vehicle routing with full truckload » (VRPFL). Ce problème consiste à

déterminer les routes ayant un coût minimum et permettant de livrer un nombre

prédéterminé de chargements complets entre des paires de villes spécifiées en utilisant

une flotte de véhicule situé à un ou plusieurs dépôts. Chaque route doit satisfaire des

fenêtres de temps à chacune des villes où un chargement est effectué. Ainsi, les camions

visitent des paires de villes contrairement au VRP qui visite seulement des villes.

L’algorithme utilisé prend aussi en considération des contraintes de fenêtres de temps.

Finalement, lorsqu’un camion sur la route n’est pas en mouvement, une pénalité de temps

d’attente est imposée. L’objectif est donc de minimiser les mouvements de véhicules

vides puisqu’ils n’offrent aucune valeur ajoutée au produit final.

Arunapum, Mathur et Solow (2003) utilisent une méthode exacte de séparation et

évaluation progressive pour résoudre le problème. Les tests ont été effectués sur des

problèmes aléatoires. Le nombre maximal de villes a été restreint à 200. Le temps de

résolution est évalué selon différents aspects soient l’effet d’une augmentation du nombre

46

de paires de villes, du nombre de dépôts, de la largeur des fenêtres de temps et du coût de

pénalité associé au temps d’attente. Plusieurs conclusions ont été tirées des résultats

obtenus. Premièrement, le temps d’exécution tend à augmenter avec l’augmentation du

nombre de paires de villes malgré que pour quelques problèmes, le temps de résolution a

été plus rapide pour un plus gros problème. Cela s’explique par le fait que le nombre

d’itérations est tout à fait arbitraire. Deuxièmement, le temps d’exécution est indépendant

du nombre de dépôts. Ensuite, la largeur des fenêtre de temps c’est-à-dire la différence

entre l’heure maximal de livraison et l’heure minimale augmente considérablement le

temps de résolution du problème. Cela est certainement dû au fait que le nombre de

routes réalisables chute dramatiquement avec la diminution de la largeur des fenêtres de

temps. Finalement, aucune tendance n’a pu être décernée concernant le temps

d’exécution lors de l’augmentation du coût associé au temps d’attente. Gronalt, Hartl et

Reimann (2003) résolvent eux aussi ce problème avec un algorithme de séparation et

évaluation progressive. Par ailleurs, ils proposent une relaxation du problème pour

générer des bornes inférieures utilisées pour évaluer quatre nouvelles heuristiques. Leurs

tests démontrent que l’utilisation d’un coût d’opportunité améliore significativement la

qualité des solutions. De plus, les auteurs ont évalué l’impact de l’augmentation de la

largeur des fenêtres de temps.

2.4.6.3. Le VRP avec retour à charge

Le VRP avec retour à charge signifie qu’après avoir effectué ses livraisons, le retour au

dépôt doit se faire en transportant de la marchandise. Osman et Wassan (2002) décrivent

deux heuristiques de construction de routes permettant de générer une solution initiale.

Ces routes sont améliorées grâce à une méta-heuristique de recherche réactive tabou. Le

concept réactif permet de déclencher un échange entre structures de voisin afin

d’intensifier et diversifier les phases de la recherche. Deux ensembles de problèmes ont

été évalués. Le premier ensemble est composé de 62 problèmes avec une demande

distribuée normalement de moyenne 500 et une variance de 200 unités. La taille de ces

problèmes est de 25 à 150 clients avec 25 à 50% de retour à charge. On note un écart par

rapport à l’optimum de 22,02% pour la première heuristique et 18,02% pour la deuxième.

47

Le deuxième ensemble de problèmes est constitué de 33 problèmes avec entre 21 et 100

clients. Le pourcentage de retour à charge est, pour ces problèmes, de 50% à 80%. Ces

problèmes sont tirés de la littérature des problèmes de tournées de véhicules. Pour cet

ensemble de problèmes, la déviation par rapport à l’optimum est de 18,45% pour la

première heuristique et de 19,22% pour la deuxième. L’ensemble de ces résultats est

résumé dans le tableau 2.19.

Tableau 2.19. : Résultat Osman et Wassan (2002)

Ensemble Nb

problèmes

Nb clients % Retour à

charge

% Écart

Heuristique 1

% Écart

Heuristique 2

1 62 25 à 150 25-50 22,02% 18,02%

2 33 21 à 100 50-80 18,45% 19,22% Source : Osman et Wassan (2002)

Bolduc (2003) a également étudiée ce problème. L’algorithme est basé sur les économies

de Clarke et Wright (1984) et inclus plusieurs autres phases d’amélioration locale.

L’algorithme est testé sur des problèmes réels et permet d’améliorer les solutions

obtenues par des répartiteurs d’expérience.

2.4.6.5. Le VRP avec cueillette et livraison avec charges pleines

Tout comme le problème de voyageur de commerce, le VRP peut lui aussi permettre

d’effectuer différents types d’opérations. Ces opérations peuvent être des cueillettes et/ou

livraisons. Lorsque ces deux types d’opérations sont combinés, on doit effectuer les

cueillettes avant les livraisons associées. Par ailleurs, il est possible que les chargements

soient complets ou partiels selon le poids ou l’espace utilisé dans le camion. Aussi, des

contraintes de livraison avec cueillettes au retour peuvent être imposées.

Un seul article traite du cas des cueillettes et livraisons dans un contexte de charges

pleines (full truckload). Il s’agit du papier de Gronalt, Hartl et Reimann (2003). Les

cueillettes sont effectuées à quelques centres de distributions et des commandes sont

48

livrées aux clients. Ces derniers tentent de minimiser le mouvement des véhicules n’ayant

aucune charge, donc n’ayant aucune valeur ajoutée pour le produit. Ils se sont basés sur le

problème de cueillette et livraison avec des contraintes de fenêtre de temps pour

développer quatre différentes heuristiques d’économies basés sur Clarke et Wright (1964)

pour résoudre le problème. Ils introduisent ainsi les notions de coûts d’opportunité et

valeurs de regret dans le calcul des économies de cet algorithme. Une borne inférieure est

définie, cette dernière représente une solution ne comportant aucun mouvement de

véhicules vides. La meilleure des quatre heuristiques présentées obtient des résultats à

5,94% de la borne inférieure tandis que la pire des heuristiques permet d’obtenir des

résultats à 7,99% de cette borne. Les problèmes possèdent les caractéristiques suivantes :

8 centres de distributions, 512 commandes, une longueur maximale de la route de 2

périodes, un horizon de planification de 8 périodes.

2.5. Applications pratiques des problèmes de tournées de véhicules

Plusieurs articles de la littérature concernent des applications réelles. Les auteurs doivent

alors prendre en considération toutes les contraintes inhérentes au cas traité. Six papiers

présentent des cas réels. Cette section présente un résumé de ces articles.

L’article de Avella, Boccia et Sforza (2003) traite d’un cas réel d’un problème de

livraison. Une compagnie doit livrer différents types de carburant à plusieurs stations

d’essences à partir d’un seul entrepôt. La flotte de véhicule comporte des véhicules de

différentes capacités. Plusieurs autres contraintes ont été considérées lors de l’étude tel

que la variabilité des commandes. Deux types d’approches sont présentés. La première

est une heuristique best fit decreasing basé sur le packing/routing. La deuxième est une

approche basée sur la formulation d’un problème de partition résolu à partir d’un

algorithme de Branch-and-Price.

49

Le second article considère le cas de cueillettes et livraisons. Par contre, plusieurs autres

contraintes y sont aussi intégrées. Ainsi, Xu, Chen, Rajagopal et Arunapuram (2003)

étudient un problème très souvent rencontré en pratique mais ayant reçu peu d’attention

dans la littérature. Ce problème est composé de plusieurs dépôts ayant chacun plusieurs

types de véhicules disponibles pour effectuer un ensemble de cueillettes et livraisons.

Chacune de ces commandes, cueillettes ou livraisons, a plusieurs fenêtres de temps. De

plus, certaines contraintes de compatibilités doivent être respectées. Un type de véhicule

ne peut transporter que les commandes compatibles avec ce type. Par exemple, les

produits réfrigérés peuvent être transportés uniquement par un camion qui est réfrigéré.

D’autres produits ne peuvent êtres transportés ensemble dans le même véhicule, comme

la nourriture et les produits chimiques. Finalement chacun des voyages effectués doit

respecter le temps de travail maximal pour les conducteurs. Le coût de tournée à

minimiser est déterminé par plusieurs facteurs incluant un coût fixe, la distance

parcourue, le temps d’attente total et les haltes effectués par les chauffeurs pour respecter

le nombre d’heures maximal de conduite. Les auteurs appliquent une génération de

colonnes pour résoudre ce problème. Les sous-problèmes générés sont résolus par une

heuristique. L’approche proposée permet de résoudre des problèmes avec plus de 200

commandes.

Brotcorne, Laporte et Semet (2003) dressent une revue littéraire des modèles ayant été

développés pour traiter le problème de localisation et relocalisation des ambulances. Les

modèles déterministes sont utilisés lors de l’étape de la planification et ignorent si les

ambulances sont disponibles ou non. Les modèles probabilistes reflètent le fait que les

ambulances opèrent selon un système de file d’attente et ne peuvent pas toujours

répondre à un appel. Finalement, des modèles dynamiques ont été développés afin de

relocaliser rapidement les ambulances au cours d’une journée.

Chian et Russel (2003) intègrent les activités d’achat et distribution du gaz propane dans

la chaîne logistique. Les méthodes permettant de trouver des solutions sont le

partitionnement et la recherche tabou. Les solutions proposées ont été appliqués dans un

50

contexte réel et permettent d’épargner des coûts importants. Une chaîne logistique

typique est défini comme suit : un producteur, des terminaux régionaux, des usines qui

sont distributeurs et des clients possédant un réservoir à gaz propane. Les distributeurs de

propane sont responsables de l’achat et de l’acheminement du propane à partir des

terminaux régionaux jusqu’à leur usine de stockage.

Deux articles tentent de résoudre des cas réels de localisation de la demande sur les arcs.

Ainsi, Baptista, Carvalho et Zùquette (2002) présentent une application réelle du

problème de tournée de véhicule périodique. Cela signifie que l’on combine à la fois

l’aspect temporel et spatial du VRP. Les auteurs présentent le cas réel du ramassage du

papier recyclé effectué dans la ville de Almada située au Portugal. Ce problème comporte

de nouveaux attributs comme par exemple la fréquence des visites ne peut être établi à

priori puisque le volume de papier est aléatoire. Une autre particularité de ce problème se

trouve dans la fonction objectif qui maximise les profits. De plus, la matrice des distances

est asymétrique. La méthode proposée est basée sur un choix initial de collecte du papier,

suivi par certains changements permettant d’augmenter le profit.

Par ailleurs, dans l’article de Jaszkiewicz et Kominek (2003), le problème réel concerne

une compagnie de cueillette de déchets d’une ville de 600 000 habitants. La compagnie

s’occupe de 60% de la cueillette de cette ville. Ainsi, il y a environ 30 000 conteneurs à

déchet, groupés en secteur, qui doivent être vidés à des fréquences différentes. Chacun de

ces secteurs doit être visité par un seul véhicule. Les distances et le temps de route ne

sont pas symétriques. De plus, la flotte de véhicules est hétérogène, les véhicules

diffèrent par leur capacité ainsi que leur coût d’utilisation. Habituellement, 30 véhicules

sont disponibles pour la cueillette des déchets et en moyenne ils visitent le dépotoir deux

fois par jour. À la fin de la journée, ils doivent retourner au dépôt vide afin d’être prêt

pour le lendemain matin. Les décisions portent sur l’affectation des véhicules aux routes

visitant les secteurs et les dépotoirs. L’objectif consiste à minimiser les coûts totaux

d’opérations c’est-à-dire la somme des coûts reliés à la distance et aux temps de travail de

chaque véhicule opérant dans une journée. L’approche de résolution se base sur un

algorithme génétique.

51

Bien que cet article ne soit pas récent, Golden et Wasil (1987) décrivent une application

dans l’industrie des boissons gazeuses. Cette application nous intéresse puisqu’elle est

celle qui est la plus près du sujet que nous traitons dans cet essai.

2.6. Algorithmes

Algorithmes

Exacts Heuristiques

Constructions et composites Amélioration

Déterministe Non Déterministe

Branch and Bound Branch and Cut

Tabou Recuit simulé Génétique

- Chian, Russel (2003) - Lau, Sim,Teo (2003) - Osman, Wassan (2002) - Toth, Vigo (2002b)

- Baker, Ayechew (2003) - Berger, Barkaoui (2003) - Choi, Kim, Kim (2003) - Hwang (2002) - Jaszkiewicz, Kominek (2003) - Moon, Kim, Choi, Seo (2002) - Moin (2002) - Prins (2001)

-Li, Lim (2003) -Schneider (2002)

-Wu, Low, Bai (2002)

- Achuthan, Caccetta, Hill (2003) - Belenguer, Benavent (2003) - Cabral, Gendreau, Ghiani, Laporte (2003)

- Avella, Boccia, Sforza (2003) - Bourgeois, Laporte, Semet (2003) - Chan, Carter, Burnes (2001) - Chen, Hsiao (2003) - Chian, Russel (2003) - Glover, Gutin, Yeo, Zverovich (2001) - Gronalt, Hartl, Reimann (2003) - Ioannou, Kriticos, Prastacos (2003) - Paletta (2002) - Patterson,Rolland (2003) - Renaud, Boctor (2002) - Renaud,Boctor, Ouenniche (2000) - Xu, Chen, Rajagopal ,Arunapuram (2003)

-Baptista, Oliviera, Zùquete (2002) -Bourgeois, Laporte, Semet (2003) -Renaud, Boctor, Ouenniche (2000)

- Avella,Boccia, Sforza (2003) - Arunapuram, Mathur, Solow (2003) - Gronalt, Hartl, Reimann (2003) - Shutler (2001) - Toth, Vigo (2002a)

Autres

- Baker, Carreto (2003) - Beullens, Muyldermans,

Cattrysse and Oudheusden (2003) - Ghaziri,Osman (2003) - Renaud, Boctor, Laporte (2002) - Tarantilis, Kiranoudis, Vassiliadis

(BATA) (2003)

Colonie de fournis

- Reimann, Doerner, Hartl (2003)

53

Dans le but de résoudre efficacement les problèmes présentés dans les sections

précédentes, divers algorithmes ont été proposés. Le choix d’un algorithme repose

évidemment sur le type de problème mais il est aussi primordial de considérer le temps

de calcul et l’effort disponible pour trouver une solution. Dépendamment du choix de

l’algorithme utilisé, nous obtiendrons une solution de qualité différente demandant un

effort différent. Habituellement, la qualité de la solution est corrélée avec l’effort

nécessaire pour l’obtenir.

Premièrement, nous pouvons séparer les algorithmes en deux catégories soit : les

algorithmes exacts et les heuristiques. La principale distinction à faire entre ces deux

approches est la suivante, l’algorithme exact permet de trouver l’optimum tandis que

l’heuristique s’en approche sans garantir de le trouver mais avec un moindre effort.

Les prochaines sections présentent brièvement les tendances dans le développement des

algorithmes pour les problèmes de tournées. Nous nous sommes restreints aux

publications des années 2000 à aujourd’hui.

2.6.1. Méthode exacte

Comme il a été mentionné précédemment, un algorithme exact permet de trouver la

solution optimale. Or, cela exige un temps de calcul important puisque implicitement elle

consiste à énumérer l’ensemble des solutions possibles. Ainsi, comme le temps de calcul

risque d’augmenter exponentiellement avec la taille du problème, il n’est pas rare que ces

méthodes rencontrent des difficultés lorsque la taille du problème augmente. On peut

diviser les méthodes exactes selon trois différentes approches soient la séparation et

l’évaluation progressive, la méthode de plan de coupe et la programmation dynamique.

Cette dernière n’a été retrouvée dans aucun des articles étudiés alors nous nous

pencherons seulement sur les deux premières approches.

54

2.6.1.1. Séparation et évaluation progressive L’algorithme de séparation et évaluation progressive, mieux connue sous le nom de

« branch and bound » se base sur l'énumération et l'évaluation des solutions possibles.

Cet algorithme construit une arborescence et évalue, pour chacune des branches, la

possibilité de trouver la solution optimale. Ensuite, seuls les sommets qui semblent

pouvoir mener à une solution intéressante sont examinés, évitant par le fait même de

parcourir entièrement l’arbre des solutions. Cet algorithme peut être utilisé pour résoudre

plusieurs types de problèmes. Quatre papiers récents utilisent la séparation et l’évaluation

progressive.

Avella, Boccia et Sforza (2003) ont utilisé cette approche pour résoudre le problème réel

de livraison de carburant. Dans son papier, Shutler (2001), présente une amélioration à un

algorithme de séparation et évaluation progressive afin de résoudre le problème de TSP

symétrique. L’auteur définit une nouvelle règle de séparation qui permet de réduire le

nombre de décisions requises à chacun des nœuds pour trouver une solution au problème.

Les problèmes résolus ont de 100 à 500 nœuds. Arunapuram, Mathur et Solow (2003)

traitent du problème de tournées de véhicules avec chargement complet. Finalement Toth

et Vigo (2002a) abordent le problème de tournée de véhicules avec restriction de

capacité. La taille des problèmes résolus a grandement évoluée, Toth et Vigo (2002a) ont

réussi à faire passer le nombre de clients, pour lequel il était possible de résoudre le

problème de tournées de véhicules avec contraintes de capacité, de 25 à 100 clients, ce

qui représente un progrès considérable.

2.6.1.2. Génération de coupe

La génération de coupe, en anglais « branch and cut », est une généralisation de la

séparation et l’évaluation progressive dans lequel plusieurs coupes sont générées afin de

restreindre l’espace des solutions et ainsi augmenter la valeur de la relaxation linéaire.

Cet algorithme a été utilisé dans deux articles traitant de localisation de la demande sur

les arcs.

55

Cabral, Gendreau, Ghiani et Laporte (2003) présentent une solution pour le «

hierarchical Chinese postman problem ». Ils réussissent à résoudre des problèmes avec

150 nœuds dans le cas où l’objectif consiste à minimiser le temps de route et de 50 nœuds

lorsqu’il s’agit d’un objectif hiérarchique. L’article Belenguer et Benavent (2003) traite

aussi d’un problème où les demandes sont sur les arcs, par contre, ils considèrent

plusieurs véhicules et non un seul. Dans leurs cas, des problèmes de 50 nœuds et 97 arcs

pour lesquels un service est requis ont été solutionnés.

L’article de Achuthan, Caccetta et Hill (2003) aborde le problème de tournées de

véhicule classique. Les auteurs utilisent la méthode de génération de coupe. Les auteurs

développent une nouvelle génération de coupes et une procédure de recherche permettant

d’identifier les contraintes qui sont violées. Les tests ont été effectués sur 1650 problèmes

de 15 à 100 clients.

2.6.2. Heuristiques

Les heuristiques ne garantissent pas l'obtention d'une solution optimale mais fournissent

en général, dans un laps de temps raisonnable et à un coût acceptable, une solution dont

les performances sont assez bonnes. Ils constituent donc une alternative intéressante

lorsque l’optimalité n’est pas primordiale. Les heuristiques de construction permettent de

former pas à pas une solution initiale qui pourra par la suite être améliorée grâce aux

heuristiques d’amélioration. La solution initiale influence grandement la qualité de la

solution finale qui sera trouvé, c’est pourquoi la recherche d’heuristique de construction

est très importante. Par ailleurs, lorsqu’un algorithme est composé de plusieurs

heuristiques, on dit alors qu’il s’agit d’une heuristique composite. L’article de Laporte,

Gendreau, Potvin et Semet (2000) présente une revue de la littérature des plus

importantes familles d’heuristiques utilisées pour résoudre le VRP. Les auteurs

présentent entres autres la plus populaire technique de construction, c’est-à-dire la

méthode des économies développée par Clarke et Wright (1964). Par ailleurs, cet article

traite des différentes approches tabous.

56

2.6.2.1. Heuristiques de construction et composites

Les heuristiques de construction et les heuristiques composites occupent une place

importante en optimisation, un nombre important d’auteurs présentent des articles

utilisant ce type d’heuristique pour tous les problèmes de tournées. Effectivement, treize

articles présentent une heuristique de construction et couvrent presque l’ensemble des

problèmes de tournées. Souvent, ces articles présentent une heuristique de construction

pour ensuite proposer une heuristique d’amélioration. Les problèmes solutionnés sont très

variés. Les problèmes étudiés couvrent le problème de voyageur asymétrique (Glover,

Gutin, Yeo et Zverovich, 2001) au problème de tournées de véhicules avec dépôts

multiples (Chan, Carter et Burnes, 2001) en passant par le problème de tournées avec

fenêtres de temps (Chen et Hsiao, 2003 et Ioannou, Kriticos et Prastacos, 2003). De plus,

les heuristiques présentées sont tout aussi variés passant de l’heuristique de balayage par

Renaud et Boctor (2002) pour le problème de flotte hétérogène, à l’heuristique

d’économie par Gronalt, Hartl et Reimann (2003) au « best fit decreasing » par Glover,

Gutin, Yeo et Zverovich (2001).

Pour résoudre le problème de cueillettes et livraisons pour le problème de voyageur de

commerce (PDTSP) Renaud, Boctor et Ouenniche (2000) présentent un algorithme

composite. Il est composé de deux phases, la première est une phase de construction à

double insertion qui permet une optimisation locale. La seconde est une phase

d’amélioration où les auteurs proposent de travailler avec une paire de clients cueillette-

livraison pour laquelle on effectue la suppression et l’insertion simultanément. Les

auteurs ont testés leur heuristique composite sur un ensemble de 108 problèmes dérivés

de 36 problèmes du TSPLIB de Reinelt (1981) ayant jusqu’à 441 points. Les résultats

obtenus démontrent que la double insertion suivi du 4-opt* permet de se situer en

moyenne à 5,64 % de la meilleure solution connue tandis que la double insertion suivi de

l’insertion et la suppression simultanée permet de se situer à seulement 4,48 % de ces

résultats. Le 3-opt permettrait d’obtenir de meilleurs résultats (3,87% au dessus de la

meilleure solution connue) mais ce dernier utilise beaucoup de temps de résolution. En

57

effet, le 3-opt demande 1314,2 secondes tandis que le 4-opt* et la suppression et

réinsertion demandant respectivement 73,1 et 95,9 secondes.

L’article de Glover, Gutin, Yeo and Zverovich (2001) présente deux nouvelles

heuristiques de construction d’un TSP asymétrique et une troisième basée sur la

combinaison des deux premières. Les auteurs développent des heuristiques de

construction pour un graphe orienté dans lequel chacun des arcs a un poids différent.

Sept familles de problèmes ayant des caractéristiques différentes ont été étudiées afin de

déterminer la performance de ces algorithmes sur différents types de problèmes. Les

résultats obtenus sont par conséquent différents d’une famille à une autre. Ainsi, pour

tous les problèmes asymétriques du TSPLIB, la première heuristique basée sur le Karp-

Steele patching est meilleure se situant en moyenne à 3,36% de l’optimum. Par contre, si

l’on considère la troisième famille dans laquelle des poids sont attribués aux arcs alors la

troisième heuristique est préférée aux deux autres, et elle se situe à 1,88% de l’optimum.

Étant donné que les résultats sont très distincts d’un problème à un autre, il sera approprié

de choisir l’heuristique selon la famille auquel ce problème appartient et ce même si

généralement, la troisième heuristique donne de meilleurs résultats.

Ioannou, Kriticos et Prastacos (2003) étudient le cas du problème de tournées avec

fenêtres de temps souples. Ils proposent un générateur de problèmes de tournées de

véhicules dont chacun est caractérisé par un certain nombre de clients pour lesquels on

peut violer la fenêtre de temps. Chacun des problème est résolu avec un approche de

construction, soit le voisinage le plus près. Cette approche a été transformée pour prendre

en considération l’effet d’une violation d’une fenêtre de temps. L’heuristique proposée

permet de réduire le nombre de véhicules requis avec un faible degré de violation des

fenêtres de temps et une durée des parcours intéressante.

2.6.2.2. Heuristiques d’amélioration

Les heuristiques d’amélioration débutent avec une solution initiale, générée par une autre

méthode, et à l’aide de divers échanges tentent de trouver une meilleure solution. Ce type

58

d’heuristique peut être divisé en deux selon qu’elle soit ou non déterministe. Les

heuristiques non déterministes peuvent aussi être subdivisé en plusieurs méthodes. Toutes

ces méthodes seront traitées dans la prochaine section.

Méthodes déterministes

Une heuristique est dite déterministe lorsque à toutes les fois que l’on exécute cette

heuristique sur le même problème à partir d’une même solution initiale, on trouve une

solution identique. Le hasard n’intervient en aucun cas dans ce type de d’heuristique. La

recherche dans le voisinage est systématique et déterministe. Baptista, Oliviera et

Zùquete (2002) utilisent une méthode déterministe pour résoudre un cas réel de tournées

de véhicules, tandis que Bourgeois, Laporte et Semet (2003) et Renaud, Boctor et

Ouenniche (2000) utilise des échanges 2-opt et le 3-opt afin d’améliorer l’heuristique de

construction qu’ils ont présentés. Dans ces deux derniers cas, les auteurs tentent de

résoudre différentes versions du voyageur de commerce. Bourgeois, Laporte et Semet

(2003) l’utilisent pour résoudre le problème de BWTSP pour des tailles d’au plus 200

points et Renaud, Boctor et Ouenniche (2000) pour résoudre un problème de cueillette et

livraison pour le voyageur de commerce ayant au maximum 441 noeuds.

Méthodes non déterministes

Les méthodes non déterministes peuvent être définies comme des méthodes qui utilisent

l’aléatoire dans la sélection des voisinages à explorer ce qui aide à diversifier la

recherche. Certaines se basent sur des phénomènes existant dans la nature pour explorer

l’ensemble des solutions possibles. Aussi, elles utilisent un processus itératif qui se

termine lorsqu’il atteint un critère d’arrêt prédéfini. Il existe une panoplie de critère

d’arrêt. Par exemple, ce critère peut être l’obtention de la solution optimale si cette

dernière est connue, un nombre maximum d’itérations, un temps de calcul écoulé, un

nombre d’itérations dans amélioration de la meilleure solution obtenue, etc. Le succès de

ces méthodes dépend de plusieurs facteurs, comme la facilité d’implantation, l’habilité à

59

adapter les contraintes d’applications réelles et la qualité des solutions produites. Les

méthodes non déterministes ont été regroupés selon quatre catégories: la recherche tabou,

l’algorithme génétique, le recuit simulé et les autres métaheuristiques.

La recherche tabou

Plusieurs auteurs ont utilisé l’approche tabou. Cette métaheuristique, apparu au milieu

des années 1980, a été proposée par Glover (1986). La recherche tabou accepte que la

fonction se dégrade avec le moins pire des voisins même si ce dernier est moins bon que

la solution connue. Elle restreint également l’accès à des solutions déjà rencontrées et

force l’exploration de nouvelles régions en conservant les informations sur les solutions

déjà visitées dans une liste tabou. Cela a pour effet d’éviter de cycler et de retourner trop

rapidement dans des optimums locaux déjà visités. La recherche tabou se décrit plus

précisément comme suit :

Générer une solution initiale s0; initialiser la mémoire; k = 0; s* = s0.

Tant que le critère d’arrêt n’est pas atteint :

o Choisir sk+1, une solution voisine de sk, en utilisant les données de

la mémoire tabou. Une solution voisine est admissible si il s’agit

d’une solution sans statut tabou ou dont le statut a été révoqué par

le critère d’aspiration

o Si sk+1 est meilleur que s* alors s* = sk+1

o k = k+1

o Mettre à jour la mémoire tabou. Les derniers tabous sont éliminés

pour faire place aux nouveaux tabous

Au cours des dernières années, la recherche tabou a été appliquée au problème de

tournées par plusieurs auteurs. Effectivement, en consultant le tableau 2.3. il est possible

de remarquer que pour le VRP, le tabou est souvent à l’origine de la meilleure solution

trouvée pour des problèmes de tournées de véhicules. Ainsi, des auteurs tels que Taillard

60

(1993), Osman (1993), Gendreau et al. (1994), Rego et Roucairol (1996), Xu-Kelly

(1996) et Toth et Vigo (1998) se sont inspirés du tabou pour développer des méthodes de

résolutions efficaces.

Plus récemment, Chian et Russel (2003) ont effectué une recherche tabou pour permettre

d’intégrer les activités d’achat et distribution du gaz propane dans la chaîne logistique.

Lau, Sim et Teo (2003) proposent une approche tabou avec une liste permettant de

conserver les clients non visités ainsi qu’un mécanisme introduisant par étape un nouveau

véhicule afin de maximiser le nombre de client visités dans cette route tout en respectant

la capacité du véhicule et les fenêtres de temps. Pour terminer, Osman et Wassan (2002)

introduisent un concept réactif à la recherche tabou permettant de déclencher un échange

entre structure de voisin afin d’intensifier et diversifier les phases de la recherche. Avec

cette approche, ils tentent de résoudre un problème de tournées de véhicules avec

cueillette au retour avec au plus 150 clients.

2.6.3.2.2. L’algorithme génétique L’algorithme génétique a été développé initialement par John Holland (1975) et ses

étudiants à l’université du Michigan. Leurs recherches avaient pour but premier de

concevoir des systèmes artificiels possédant certaines propriétés des systèmes naturels.

La génétique a été très populaire au cours des dernières années pour les problèmes de

tournées. En effet, huit articles se servent de cette approche. Le principe de l’algorithme

génétique est très connu, il imite le principe de l’évolution des espèces. Une population

de solutions est maintenue et un procédé de reproduction permet aux solutions parents

d’être sélectionnées parmi la population. Cette sélection est souvent en relation avec la

qualité de la solution obtenue par ces parents. On effectue alors un croisement entre les

parents afin de produire une descendance. Les solutions enfants présentent ainsi des

caractéristiques des parents. Les meilleures solutions enfants ont de meilleures chances

de survie puisqu’on élimine les individus ayant une moins bonne valeur. À l’occasion,

une mutation est appliquée afin d’ajouter des nouvelles propriétés et de la diversité dans

l’ensemble des solutions générées. Cette analogie entre l’évolution des espèces et

61

l’algorithme génétique a été proposé par Holland (1975) qui à l’origine utilisait un

vecteur binaire pour encoder les solutions.

La procédure de l’algorithme génétique se décrit comme suit :

Générer une population de vecteur

Tant que le critère d’arrêt n’est pas atteint:

o Sélectionner dans la population courante l’ensemble des parents

o Classer au hasard deux à deux tous les parents et appliquer un

croisement afin de produire les vecteurs enfants

o Appliquer une mutation, c’est-à-dire un changement aléatoire, à un

nombre aléatoire de progénitures

o Évaluer la descendance

o Créer la nouvelle population à partir de la population précédente et

des enfants

o Éventuellement, retirer des individus offrant une moins bonne

performance.

La procédure se termine généralement lorsque le nombre d’itérations fixés, ici le nombre

de génération créé, est atteint ou lorsque la population ne peut être améliorée.

Moon, Kim, Choi et Seo (2002) tentent de résoudre le problème de voyageur de

commerce avec contraintes de précédences. Ils ont formulé le TSPPC à l’aide d’un

modèle de réseau. Afin de conserver les contraintes de préséance, un nouveau canevas

d’encodage est développé, le concept clé consiste à utiliser un tri topologique qui consiste

à ordonner les nœuds dans un graphe orienté. Les auteurs ont effectués des tests sur des

problèmes de tailles distinctes. Le nombre de points et de contraintes sont respectivement

de 6 et 6 pour les problèmes de petite taille, de 20 et 29 pour les moyens et de 40 et 56

pour les problèmes de grande taille. Les résultats indiquent qu’une solution optimale est

trouvée pour les problème de petite et moyenne taille tandis qu’il s’approche

considérablement de celui-ci pour le problème de grande taille. Les différents paramètres,

62

soient le nombre maximum de générations, la taille de la population, la probabilité de

croisement et la probabilité de mutation, varient selon la taille du problème traité.

Jaszkiewicz et Kominek (2003) traitent un cas réel de cueillette de déchets. Ils proposent

lors de leur algorithme génétique d’utiliser une corrélation entre la qualité des solutions et

la distance dans le but de trouver les caractéristiques significatives de la bonne solution.

Le problème du voyageur de commerce a également été traité à l’aide de l’algorithme

génétique. Choi, Kim et Kim (2003) présentent un algorithme génétique permettant de

résoudre des TSP asymétriques. Ils insèrent des solutions non réalisables, qui créent des

sous-tours, dans la nouvelle génération afin de générer plus tard de meilleures solutions.

Les paramètres utilisés pour effectuer l’expérimentation sont les suivants : le nombre de

chromosomes est égal à 200 et le nombre maximum de génération à explorer est de 1000.

Les auteurs ont testé leur algorithme génétique sur 23 problèmes de 17 à 170 nœuds.

L’article de Baker et Ayechew (2003) traite du problème de tournées de véhicules. Dans

leur algorithme, deux méthodes ont été utilisées pour générer la population. La première

consiste à trier les clients selon l’angle par rapport au dépôt. Ensuite, pour générer la

population, un client est choisi au hasard afin de débuter le processus d’attribution des

clients aux véhicules. Les clients sont attribués à ce véhicule dans l’ordre jusqu’à la

violation d’une contrainte. La seconde méthode utilise une approximation des distances à

parcourir. Un point fictif est situé sur un rayon qui coupe l’angle du véhicule

correspondant en deux. Une population de taille 30 a été utilisée pour les petits problèmes

tandis qu’une population de 50 a été utilisée pour les problèmes de plus grande

envergure. Les distances obtenues par leur algorithme se situent en moyenne à 0,5% de

l’optimum sur des problèmes connus de la littérature dont les résultats optimaux sont

présentés au tableau 2.2.

D’autres auteurs s’attaquent aussi au problème de tournées de véhicules à l’aide

d’algorithmes génétiques. Effectivement, Moin (2002) et Hwang (2002) traitent le

problème particulier où des fenêtres de temps sont imposées. Moin (2002) se concentre

63

sur les problèmes de Solomon de 30 à 50 clients tandis que Hwang tente de résoudre des

problèmes ayant de 10 à 99 clients.

Le recuit simulé

Le recuit simulé s’appuie sur un principe physique en métallurgie. On chauffe un métal

puis on le laisse refroidir lentement ce qui permet d’augmenter le degré de liberté des

atomes dans le but d’atteindre un nouvel état dynamique. Basé sur ce principe, la

méthode du recuit simulé augmente le degré de liberté en permettant une dégradation de

la solution. L’idée consiste à partir d’une solution initiale choisie au hasard puis à tester

si cette dernière respecte toutes les contraintes. Si cela n’est pas le cas, on modifie

légèrement la solution pour qu’elle les respecte. Ensuite, on examine les solutions

voisines. Afin de pouvoir sortir éventuellement de l’optimum local, on accepte une

dégradation de la solution dans une probabilité inversement proportionnelle à l’amplitude

de cette dégradation. Ainsi, plus la dégradation est importante moins la chance de retenir

cette solution est élevée. Puis, au fur et à mesure que l’on avance dans le temps, il

devient de plus en plus improbable d'accepter une dégradation. Le fait qu'un point peut

être accepté parfois même s'il donne une valeur de la fonction plus grande que la valeur

précédente permet à l'algorithme de quitter les minimums locaux et éventuellement de

converger vers le minimum global. L’algorithme se termine lorsqu’un critère d’arrêt

prédéfini est atteint.

Wu, Low et Bai (2002) proposent une décomposition du problème de tournées à plusieurs

dépôt en un problème de localisation allocation (LAP) et en un VRP. Chaque sous-

problème est résolu avec un algorithme de recuit simulé. La taille des problèmes traités

est de 150 nœuds. Par ailleurs, Li et Lim (2003) apportent une solution au problème de

tournées de véhicules avec restriction de fenêtres de temps. Tous les problèmes sont tirés

de Solomon (1987) et ont 100 clients à visiter avec des fenêtres de temps et un dépôt. Le

troisième article traitant de recuit simulé est celui de Scheider (2002) qui applique le

recuit simulé au problème du voyageur de commerce où les distances sont variables dans

le temps.

64

L’optimisation par colonie de fourmis L’optimisation par colonie de fourmis est un algorithme très récent qui a été proposé pour

la première fois en 1991 par Colorni, Dorigo et Maniezzo (1991). Elle est inspirée du

comportement des fourmis. Ces insectes qui sont presque aveugles réussissent malgré

tout à trouver le plus court chemin entre leur point de départ et la nourriture grâce à une

forme d’apprentissage et à un moyen de communication : le phéromone. Le phéromone

est une substance déposée en quantité variable par une fourmi en déplacement. Ainsi,

plus il y a de fourmis qui utilisent le même trajet, plus il y aura de phéromones sur ce

dernier et plus il y a de chance que celui-ci soit choisi par les prochaines fourmis qui

passeront.

Un seul article traite de l’algorithme de colonie de fourmis. Reimann, Doerner et Hartl

(2003) s’inspirent de cet algorithme avec succès pour résoudre le problème de tournées

de véhicules. Effectivement, les auteurs ont utilisé le principe des phéromones lors de la

construction de leur heuristique. Par contre, d’autres algorithmes ont aussi été utilisés, par

exemple, on retrouve le 2-opt, l’algorithme de balayage de Gillet et Miller (1974) et

l’algorithme modifié de Miehle présenté par Spaeth (1977). L’idée principale de cette

heuristique composite est de décomposer le problème en plusieurs sous-problèmes et à

les regrouper après avoir trouvé une solution pour tous les sous-problèmes.

Autres métaheuristiques

Quelques autres métaheuristiques ont été rencontrées dans la littérature des dernières

années. Par exemple, Renaud, Boctor et Laporte (2002) effectuent un algorithme de

perturbation pour résoudre le problème de cueillettes et livraisons pour le voyageur de

commerce. Aussi, Tarantilis, Kiranoudis et Vassiliadis (2003) présente le backtracking

adaptive threshold accepting (BATA) qui est une métaheuristique avec un seuil

d’acceptation. L’idée fondamentale est de permettre un mouvement vers une solution en

imposant une déviation maximale de la valeur de l’objectif dans le but d’échapper à

65

l’optimum local. Le seuil est réduit au cours de la procédure de recherche ce qui leur

permet de converger.

On constate que la recherche sur les problèmes de tournées explore diverses méthodes de

recherche. Bien que les algorithmes de construction et composites occupent encore la

majeure partie des recherches, d’autres algorithmes leur font concurrence. À cet effet,

notons un retour important des applications de l’algorithme génétique qui sont plus

nombreuses que la toujours populaire recherche tabou. Les récents succès de l’algorithme

génétique et d’approches comme la perturbation laissent présager d’autres recherches en

ce sens.

66

2.7. Conclusion Les problèmes de tournées sont malgré de nombreuses années de recherche un sujet

d’actualité qui passionne toujours les chercheurs. Suite à la lecture de ces articles, il est

possible de conclure qu’autant les problèmes de tournées de véhicules que le problème de

voyageur de commerce sont encore très présents dans la littérature. Par contre, la

littérature laisse entrevoir une légère tendance vers les problèmes de tournées de

véhicules qui sont plus complexes à résoudre. Par ailleurs, de nouveaux problèmes font

surface grâce à l’ajout de contraintes supplémentaires. Ces contraintes permettront de se

rapprocher de plus en plus de la réalité. Nous pouvons dire que le problème de tournées

qui a été préféré dans les dernières années est celui de tournées de véhicules avec fenêtres

de temps. En ce qui concerne les algorithmes utilisés, ils sont très diversifiés.

L’utilisation d’algorithmes exacts se fait de plus en plus rare, les auteurs préférant se

pencher vers les heuristiques de construction et les métaheuristiques, en particulier vers

l’algorithme génétique. Finalement, il est possible d’affirmer que la recherche sur les

problèmes de tournées continuera sans aucun doute à performer et à s’améliorer au cours

des années futures.

67

Chapitre 3

Distributions Jacques Dubois inc.

3.1. Introduction

Avant de résoudre un problème, il est essentiel de bien comprendre le contexte dans

lequel il se trouve. Ce chapitre présente une description générale de l’entreprise

Distributions Jacques Dubois inc.. Cette dernière permettra de mieux connaître

l’envergure du problème étudié qui sera présenté en deuxième partie de ce chapitre.

3.2. Description générale de l’entreprise

Fondée le 22 janvier 2001, l’entreprise Distributions Jacques Dubois inc. est encore au

tout début de ses activités. Elle se spécialise dans deux différentes activités soient la

distribution de breuvages et la récupération des bouteilles et cannettes vides. Elle livrait à

sa constitution près de 33 000 caisses, quantité qui a pratiquement doublée puisque

l’objectif de l’année 2003 était de 52 000 caisses. Malgré son jeune âge, elle dessert tout

le territoire de la Rive-Sud et le comté de Portneuf. Distributions Jacques Dubois inc. est

composé de seulement 5 employés dont 3 sont des chauffeurs de camions responsables de

la distribution. Depuis quelques mois, un magasin de détail est ouvert conjointement à

l’entrepôt situé sur la Rive-Sud à Lévis. De plus, l’entreprise prendra de l’expansion au

cours de la prochaine année puisque qu’elle desservira le territoire de la région de

Québec, c’est-à-dire la ville de Québec et ses environs.

68

3.2.1. Principales activités

Les principales activités de l’entreprise sont les suivantes :

1) Distribution de breuvages non alcoolisés,

2) Cueillette de bouteilles consignées.

Par conséquent, sa mission consiste à effectuer la livraison de liqueur, jus et eau de même

que la récupération des cannettes et des bouteilles en plastiques tout en répondant le plus

efficacement aux besoins des clients.

3.2.2. Les clients et fournisseurs

La majorité des clients de l’entreprise est située sur la Rive-Sud de Québec, couvrant

entièrement la région Chaudières-Appalaches. Effectivement, les clients sont situés à

partir du fleuve St-Laurent jusqu’aux frontières des États-Unis et de Plessisville à

Montmagny. De plus, le comté de Portneuf s’est dernièrement ajouté. Ces deux territoires

permettent à l’entreprise de livrer à plus de 500 clients. Les clients sont très variés, les

livraisons sont effectuées aux épiceries, dépanneurs, pharmacies, marchés indépendants

de même qu’aux supermarchés. L’entreprise compte ainsi parmi ses clients la plupart des

Couche-Tard, Jean Coutu, IGA, Maxi présents sur son territoire. La livraison des

commandes est effectuée aux deux semaines pour la majorité des clients. L’ensemble des

clients visités est illustré sur la carte de la figure 3.1.

69

Figure 3.1. : Localisation des clients de Distributions Jacques Dubois inc.

L’entreprise fait affaires avec deux fournisseurs soient Colt et Verchères. Les produits

sont livrés à l’entrepôt 24 heures seulement après la commande par téléphone qui est

généralement effectuée à tous les jeudis.

3.2.3. Les produits

Les produits livrés par Distributions Jacques Dubois inc. sont des breuvages de toutes

sortes. Ainsi, l’entreprise compte plus de 125 produits distincts c’est-à-dire de saveurs et

de dimensions différentes. Parmi les produits, on retrouve de l’eau Verchères et

Montclair en différents formats et l’eau gazéifiée Perrier. Aussi, des boissons gazeuses

Cott sont disponibles en 2 litres, en cannettes et en bouteilles 591 ou 600 millilitres. Les

boissons gazeuses Chubby sont aussi disponibles de même que les jus Snapple, Fresh and

Tasty et le soda Stewart. Finalement, un nouveau produit s’est récemment ajouté à ces

derniers soit le lait Grand Pré.

70

3.2.4. Les camions

Bien qu’il arrive à l’occasion que Distributions Jacques Dubois inc. loue des camions

pour la livraison, l’entreprise possède trois véhicules de capacité différente pour assurer

la distribution des boissons et la cueillette de bouteilles vides. Aucun camion n’est dédié

à une route en particulier, ils sont attribués aux routes selon la capacité nécessaire.

3.2.5. Méthode actuelle

Un représentant de Colt, fournisseur de Distributions Jacques Dubois inc. se présente aux

clients environ à toutes les deux semaines. Celui-ci fait part des nouveaux produits et des

promotions en cours, pour ensuite recueillir les commandes des clients. Ces commandes

sont alors inscrites sur les feuilles de commandes et remises au responsable qui est

Jacques Dubois. Ces commandes seront alors chargées dans le camion qui est attribué à

la route du client. Les tournées des véhicules sont très semblables, elles sont répétées

toutes les deux semaines, visitant d’une fois à l’autre les clients qui ont effectués une

commande.

Les activités sont présentement séparées selon la journée de la semaine. Ainsi, le lundi

tous les camions sont affectés à la récupération, le mardi la récupération est effectuée par

un camion, les autres effectuent la livraison et un peu de récupération. Les mercredis et

jeudis sont entièrement réservés à la distribution de breuvages. Finalement, le vendredi,

deux camions sont affectés à la récupération et l’autre camion dessert les clients non

visités au cours de la semaine. L’ensemble des activités est présenté de manière plus

précise est présenté dans le tableau ci-dessous.

71

Tableau 3.1. : Répartition des activités selon la journée de la semaine

Jour de la semaine Camion 1 Camion 2 Camion 3

Lundi Récupération Récupération Récupération

Mardi Récupération Principalement

distribution

Principalement

distribution

Mercredi Distribution Distribution Distribution

Jeudi Distribution Distribution Distribution

Vendredi Récupération Récupération Distribution

3.2.6. Le siège social Le siège social de l’entreprise de même que l’entrepôt et le magasin de détail sont situés à

Lévis. C’est de cet endroit que les camions de l’entreprise débutent et terminent leurs

tournées. Il est situé à l’adresse suivante :

Distributions Jacques Dubois inc. 5205 boul. Rive-Sud

Lévis G6V 4Z4

Téléphone : (418) 834-1736

3.3. Définition du problème

L’entreprise doit assurer la distribution de boissons non alcoolisées et la cueillette de

bouteilles vides pour tous les clients qui en expriment le besoin par le biais d’une

commande. Par contre, de nombreuses contraintes sont présentent et doivent être

considérées. Cette partie du chapitre explique ces contraintes et la façon dont elles ont été

considérées.

72

Le problème rencontré est une généralisation du problème de tournées de véhicules. Il

s’agit d’un problème de tournées de véhicules avec fenêtres de temps, flotte hétérogène et

produits multiples avec livraison et récupération simultanées. Le problème consiste à

déterminer l’ordre des clients à visiter, les camions à utiliser et les routes à parcourir.

Le problème de Distributions Jacques Dubois inc. peut être définit comme un problème

comportant de nombreux clients à desservir à partir d’un unique dépôt avec des

demandes connues de produits distincts et des camions hétérogènes. Mathématiquement,

le problème se décrit sur un graphe G = (V, A) où V = {v0, v1, …, vn} représente

l’ensemble des points et A = {(vi, vj) : vi, vj ∈ V, i ≠ j} représente l’ensemble des arcs

possibles. Les distances sont symétriques c’est-à-dire qu’on utilise une matrice de

distance D où dij = dji. Le point v0 représente le dépôt qui est le départ et l’arrivée pour

toutes les routes. Les points v1, …, vn représentent les n clients à desservir. La flotte est

composée de K véhicules dont la capacité de chargement est Qk pour la livraison des

produits et qui disposent d’un volume Vk pour la récupération. La durée maximale d’une

route est dmax. La demande du client vi pour le produit j est qij (i = 1, …, n et j = 1, …, P).

Chaque client possède une quantité de récupération ri et un temps de service si. De plus,

chacun des clients a une fenêtre de temps [ei, li] qui lui est associée où ei représente le

temps au plus tôt et li le temps au plus tard pour effectuer la visite. Le problème consiste

donc à visiter tous les clients une et une seule fois afin de leur livrer la marchandise

commandée et rapporter la récupération tout en respectant les contraintes de temps, de

volume et de capacité. L’objectif est de minimiser la distance parcourue pour visiter tous

les clients.

3.3.1. Fenêtre de temps

La contrainte de fenêtres de temps indique que tous les clients ne peuvent être visités à

n’importe lequel moment de la journée. Cela permet au client de mieux prévoir la

réception de la commande. Par contre, cette contrainte peut entraîner des changements

importants dans les tournées des véhicules puisque deux clients voisins peuvent vouloir

être visités à des moments distincts de la journée.

73

Étant donné la diversité des clients, les contraintes rencontrées sont différentes selon la

nature du client. Les supermarchés sont les clients ayant le plus de contraintes puisqu’ils

reçoivent des marchandises de plusieurs distributeurs. Ils acceptent les livraisons

seulement si elles sont livrées avant midi. La fenêtre de temps est par conséquent de six

heures à midi. De plus, il n’est pas rare que le débarcadère soit déjà occupé lors de

l’arrivée du camion. Dans ce cas, le chauffeur doit alors attendre qu’une place se libère.

À l’exception des supermarchés, les livraisons doivent être effectuées en avant-midi entre

six heures et midi et en après-midi entre treize heures et quinze heures. Peu de clients ont

des fenêtres de temps. En effet, seulement 19 clients ce qui représente 11,59% de

l’ensemble des clients imposent des fenêtres de temps.

3.3.2. Flotte hétérogène

L’entreprise possède trois camions différents qui ont été décrit à la section précédente.

Deux contraintes importantes concernent la flotte hétérogène. Tout d’abord, la capacité

des véhicules dépend du type de camion qui est utilisé. Évidemment, selon le volume du

camion, le nombre de palettes pouvant être livré par un camion sera différent. Le tableau

3.2. présente les capacités des véhicules en terme de poids et de sacs de récupération.

Tableau 3.2. : Caractéristiques des camions

Camions Longueur (pieds) Nb essieu Poids maximum

(livres)

Nb de sacs de

récupération

Camion 1 16 1 6000 120

Camion 2 20 2 8000 150

Camion 3 26 2 16000 220

74

3.3.3. Multi-produit

Le catalogue de produits de l’entreprise compte plus de 125 produits de saveurs et de

formats différents offerts à tous les clients. Il est essentiel de prendre en considération

cette grande variété de produits puisque selon le format, les produits ont un poids

différents. Cette caractéristique est primordiale puisque le poids total de la commande ne

peut dépasser la limite autorisée par le guide des normes de charges et dimensions des

véhicules publié par Transport Québec.

Il a été possible de classer les 125 produits en 6 produits types qui sont le plus souvent

commandés par les clients. Le tableau 3.3. présente ces produits ainsi que leur poids et le

nombre de produits qu’il est possible de mettre sur une palette. Étant donné que le poids

d’une palette (76 livres) n’est pas un facteur à négliger, il est important de savoir le

nombre exact de produits qu’il est possible de charger sur cette palette. Chaque fois que

l’on dépasse ce nombre, une nouvelle palette doit être utilisée. Par contre, pour ajouter

une nouvelle palette, il doit y avoir plus de 30 unités pour l’eau de 18 litres, les bouteilles

de 2 litres, les canettes et le 600 millilitres et plus de 50 unités pour les Chubby et l’eau

de 5 litres. Par exemple, si l’ensemble des clients ont commandé soixante 18 litres d’eau

alors une seule palette sera nécessaire. Par contre, si ce le nombre de 18 litres s’élève à

plus de 84 alors deux palettes seront nécessaires. Il est à noter que les articles sont livrés

en caisse. Par exemple, il est impossible de commander une seule bouteille de 2 litres

puisque ces dernières sont livrées en caisse de huit bouteilles. Le tableau suivant présente

les poids des produits par caisse et non par unité.

75

Tableau 3.3. : Classement des produits

Nom Poids (livres) Nb par palette

Eau (18 litres) 40 54

2 litres 40 50

Canettes 22 60

Chubby 21 120

600 millilitres 34 72

Eau (5 litres) 12 144

Autres 20 ---

Comme il est possible de le constater dans le tableau ci-dessus, les articles « Autres » ne

peuvent pas être chargé en palette. Effectivement, il est rare que ces articles soient

commandés en grande quantité, il n’est donc pas nécessaire d’utiliser une palette pour les

transporter.

3.3.4. La récupération

En plus de la livraison de breuvages de toutes sortes, l’entreprise Distributions Jacques

Dubois inc. doit aussi récolter des sacs contenant des bouteilles ou de canettes vides. Par

contre, dans ce cas la quantité à récupérer n’est pas toujours connue à l’avance. Chez la

plupart des clients, la quantité de bouteilles à récupérer est connue au moment où l’on

effectue la livraison des breuvages. Cependant, il est possible de regrouper les clients

selon la moyenne des sacs de récupération à recueillir. Il est évident que les plus grosses

entreprises auront plus de sacs de récupération que les petits dépanneurs. De plus, les

pharmacies, les cabanes à sucre et les campings ne recueillent généralement pas la

récupération. Suivant cette tendance, le tableau 3.4. présente la classification des clients

et le nombre de sacs de récupération amassés.

76

Tableau 3.4. : Classification des clients selon la quantité de recupération

Type Entreprises (exemples) Nb de sacs de

récupération

1 Supermarché, IGA, Co-op, Provigo, Sobeys 20-30

2 Couche-Tard, marché, petite épicerie 7-15

3 Dépanneur, Accommodation 0-10

4 Camping, Cabane à sucre, pharmacie 0

3.4. Conclusion

Ce chapitre a permis de mieux cerner toutes les caractéristiques du problème de

Distributions Jacques Dubois inc. Ainsi, une présentation générale de l’entreprise a été

effectuée suivie d’une description du problème à traiter.

77

Chapitre 4

Méthode de résolution

4.1. Introduction

Ce chapitre est consacré à la présentation de la méthode de

résolution utilisée. Dans un premier temps, une présentation générale

de l’approche utilisée est effectuée suivie par une présentation plus détaillée des

heuristiques. Finalement, une présentation du logiciel développé permettant de résoudre

le problème est effectuée.

4.2. Présentation générale

Plusieurs étapes ont été nécessaires pour résoudre le problème rencontré par l’entreprise

Distributions Jacques Dubois inc. Premièrement, la cueillette des informations a permis

de recueillir l’ensemble des clients visités et avoir un exemplaire des commandes

effectuées pour une période de livraison de deux semaines. Cent soixante-quatre clients

parmi les cinq cents clients actifs de l’entreprise avaient passé une commande pour un ou

plusieurs produits. L’ensemble des données tels que noms, adresses, code postaux et le

détail des commandes de chacun de ces clients ont été classés dans une base de données à

l’aide du logiciel Acess.

En deuxième lieu, la distance entre chacun des clients a dû être calculée. Pour ce faire, les

codes postaux ont été situés sur une carte à l’aide du logiciel MapPoint. De là, ce

logiciel de cartographie numérique a permis de trouver les distances réelles entre chacun

des clients.

78

Les données sont maintenant prêtes à être traitées pour trouver les meilleures routes à

emprunter tout en respectant l’ensemble des contraintes. Ainsi, la première heuristique

utilisée permet la construction de chacune des routes. Il s’agit de l’heuristique du plus

proche voisin adaptée aux contraintes du problème. L’amélioration des routes se fera à

l’aide de deux heuristiques. Tout d’abord, nous effectuons une amélioration individuelle

de chacune des routes suivie d’une phase d’amélioration qui échange des clients entre

deux routes.

4.3. Présentation détaillée

4.3.1. Préparation des données La façon de définir la distance est primordiale dans ce type de problème puisque le critère

d’optimisation le plus souvent utilisé est celui de la minimisation de la distance. Les

distances réelles ont donc été utilisées tel que mentionné. Ces distances ont été obtenues

par le logiciel MapPoint. Étant donné, que les heuristiques utilisées se basent sur des

distances symétriques et que les routes du Québec ne permettent pas toujours d’obtenir ce

type de distances ( dij ≠ dji), il a été nécessaire de faire une moyenne entre les deux

distances.

+==

2jiij

jiij

dddd . Il s’agit d’une approximation très raisonnable.

4.3.2. Heuristique de construction La figure 4.1. présente l’heuristique développée afin de construire les routes et déterminer

les camions à utiliser. Les principales étapes de cette heuristique se décrivent comme

suit :

1. Initialement, tous les clients sont considérés. L’ensemble ε est ainsi composé de tous les clients qui ont une commande à livrer. (ε = V \ {v0}).

79

2. Répéter l’étape 3 pour tous les véhicules k = 1…K.

3. Appliquer l’heuristique d’insertion du plus proche voisin avec le véhicule k et conserver la première tournée trouvée notée Tk.

4. Parmi les K tournées trouvées, conserver la tournée *

kT qui maximise le critère

parcourue distanceée transportquantité . Ajuster l’ensemble des clients à visiter, ε = ε \

*kT .

5. Si ε = Ø terminer, sinon retour à l’étape 2.

Détaillons maintenant l’implantation de l’algorithme d’insertion du plus proche voisin

utilisé (voir Rosenkrantz et al. 1977 pour la description originale). Partant d’un sous tour

initial composé uniquement du dépôt, l’heuristique ajoute un à un des points en

sélectionnant celui qui est le plus près de l’ensemble des points de la tournée. Ce point est

ensuite inséré à l’endroit réalisable minimisant la distance ajoutée. Une insertion est

réalisable si elle respecte les contraintes de capacité (Qk) correspondant au poids des

produits, de volume (Vk) utilisé par les sacs de récupération, de distance maximale (dmax)

et de fenêtres de temps ([ei,li]) pour tous les clients sur la route modifiée. Si une

contrainte n’est pas respectée, on cherche le prochain client le plus près des clients

actuels sur la route. Lorsqu’il n’y a plus de client qui peuvent être insérés tout en

respectant les contraintes, la route est terminée.

80

Figure 4.1. : Organigramme de la méthode de résolution

Ajuster ε ( ε = ε \ *kT )

ε = V \ {v0}

Route 6000 Noter la route Évaluer R6000



Parmi les tournées trouvées, conserver la tournée *

kT qui maximise la quantité livrée/distance parcourue

ε = Ø Non

Amélioration individuelle des routes

Amélioration inter-route

FIN

Oui

81

4.3.3. Amélioration individuelle des routes L’heuristique du 3-opt (Lin 1965) est utilisée pour améliorer individuellement chacune

des routes construites par l’heuristique de construction. Ainsi, si la distance totale

parcourue pour visiter tous les points d’une route est inférieure à celle trouvée

auparavant, la route est modifiée. Sinon, aucun changement ne sera apporté à cette route.

3-opt

Le 3-opt a été présenté par Lin en 1965. Lors du 3-opt les trois arcs suivants sont

considérés : (a,b), (c,d), (e, f), ils seront échangés et replacés de façon à réduire au

maximum la distance parcourue. Il y a huit façons de reconnecter le tour, l’une de celles-

ci serait de remplacer les arcs initiaux par les arcs (a, d), (f, b), (c, e) ce qui est illustré à la

figure 4.2. Lorsqu’il n’y aura plus aucune amélioration possible avec l’échange de trois

arcs la solution sera appelée 3-optimale. Cet algorithme requiert O(n³) opérations à

chaque itération.

Figure 4.2. : Un mouvement 3-opt

Pour chacune des routes, tous les mouvements du 3-opt sont analysés. Si un mouvement

3-opt permet d’améliorer le tour, alors la contrainte des fenêtres de temps est vérifiée. Si

elle est respectée, alors le mouvement est appliqué et la route est modifiée. Les

82

contraintes de capacité et d’espace n’ont pas à être vérifiée puisqu’elles l’ont été lors de

la formation des routes avec l’heuristique de construction.

4.3.4. Amélioration collective des routes Par ailleurs, il est possible d’effectuer d’autres améliorations en échangeant des clients

entre deux routes. L’heuristique utilisée permet d’améliorer deux routes à la fois. Après

avoir sélectionné deux routes, on considère toutes les paires de points consécutifs et on

teste les 11 échanges illustrés à la figure 4.3. Un échange est implanté s’il réduit la

distance totale et que toutes les contraintes sont respectées. Notons qu’en échangeant les

clients de routes, la demande des routes est affectée. L’algorithme est appliqué de façon

séquentielle à toutes les paires de routes tant que des améliorations sont possibles.

Les tournées de départ

Échange 1 Échange 2 Échange 3

83



Échange 10 Échange 11

Figure 4.3. : Les 11 échanges testées

4.4. Présentation du logiciel

Les heuristiques présentées précédemment ont tous été intégrées dans un logiciel de

planification de tournées programmé en Visual Basic. Ce logiciel permet ainsi de

résoudre à la fois des problèmes de la littérature de même que des problèmes de tournées

réels. Cette section du chapitre sera consacrée à la présentation du logiciel qui a été

développé pour résoudre la problématique. Il expliquera toutes les fonctionnalités du

logiciel, c’est-à-dire toutes les heuristiques utilisées, les contraintes pris en compte et la

visualisation des résultats.

84

Figure 4.4. : Interface visuelle du logiciel

4.4.1. Résolution de problèmes de la littérature Les problèmes de la littérature ont été recueillis sur TSPLIB (http://www.iwr.uni-

heidelberg.de/groups/comopt/software/TSPLIB95/). Pour résoudre un problème, il est

essentiel que les données soient contenues dans un fichier texte. Le logiciel permet de

résoudre des problèmes de la littérature, qu’ils soient des problèmes du voyageur de

commerce (TSP) ou des problèmes de tournées (VRP). Il existe deux façons d’ouvrir un

fichier pour sa résolution, soit en cliquant sur l’enveloppe correspondante ou par le

menu Fichier. L’interface suivante apparaîtra alors à l’écran permettant de sélectionner

le bon fichier.

85

Figure 4.5. : Sélection d’un problème classique

L’ensemble des données du fichier est ensuite lu par le logiciel. Pour résoudre le

problème, l’utilisateur doit sélectionner l’algorithme désiré. Pour le TSP, les algorithmes

disponibles sont l’heuristique de l’insertion du point le plus éloigné (FITSP), le 2-opt et

le 3-opt. Quant au VRP, les heuristiques du voisin le plus près et de l’insertion du point le

plus éloigné sont disponibles. Les résultats seront ensuite affichés à l’écran.

4.4.1. Résolution de problèmes réels

Le menu Client de la figure 4.4. permet d’accéder à deux interfaces très importante du

logiciel : l’interface de modification des caractéristique d’un client et l’interface de

sélection des clients.

4.4.1.1. Modification des paramètres des clients Toutes les données sur le problème de Distribution Jacques Dubois inc. sont initialement

entrées dans une base de données Access. Il est toutefois possible d’accéder directement à

cette base de données via le logiciel. Toutes les données seront alors modifiables. En

enregistrant les modifications c’est-à-dire en cliquant sur l’icône ,les informations du

client en question seront mises à jour dans la base de données Access.

86

Figure 4.6. : Modification des caractéristiques des clients

L’interface de modification des caractéristiques des clients permet d’éditer les paramètres

en inscrivant directement les nouvelles données en plus, d’ajouter ou de supprimer

un client. Par ailleurs, l’utilisateur peut se déplacer d’un client à l’autre grâce à la

barre de défilement mais il est aussi possible de rechercher un client par son numéro

client ou son nom. Aussi, l’interface permet d’accéder aux commandes des clients en

sélectionnant dans le menu commande le sous-menu modification. La figure 4.7. présente

l’interface permettant de modifier la commande d’un client.

87

Figure 4.7. : Modification de la commande d’un client

4.4.1.2.. Sélection des clients et construction des routes

La figure 4.8. présente les données concernant les clients de l’entreprise. Il s’agit en fait

des résultats d’une requête effectuée sur Access concernant tous les clients qui ont une

commande active. Cette interface permet de bien visualiser toutes les informations sur les

clients et leurs commandes et sélectionner les clients pour qui l’utilisateur désire prévoir

une tournée. Pour ce faire, l’utilisateur doit cliquer sur la colonne Sélection correspondant

au client désiré. Le chiffre 1 apparaîtra dans cette colonne si le client est sélectionné,

autrement le chiffre 0 est indiqué. Dans la barre des tâches, le menu Sélectionner est

disponible. Les options disponibles permettent de sélectionner tous les clients ou alors de

les sélectionner selon une ville (voir figure 4.9.)

88

Figure 4.8. : Sélection des clients

Figure 4.9. : Sélection des clients par ville

Par ailleurs, le logiciel permet de configurer la flotte de véhicules afin de tenir compte

des contraintes pratiques (figure 4.10). Ainsi, sous l’onglet Paramètres il est possible de

déterminer la capacité des véhicules, le nombre de véhicules à la disposition de

l’entreprise de même que le temps de déchargement chez les clients. De la même

manière, l’horaire de travail des camionneurs ainsi que la vitesse moyenne sont des

89

paramètres modifiables. Cette interface permet aussi d’identifier la localisation de

l’entrepôt qui sert de point de départ et d’arrivée pour l’ensemble des camions.

Figure 4.10. : Identification des paramètres de l’entreprise

Une fois tous les paramètres configurés et les clients à visiter sélectionnés, avant de

trouver les routes à parcourir, il est primordial de calculer les distances entre les clients.

En cliquant sur le bouton , le logiciel dresse une matrice des distances routières réelles

entre les clients sélectionnés. Toutes les distances sont alors calculées par l’entremise de

MapPoint et ensuite conservées en mémoire dans une table de données Access. Par la

suite, l’utilisateur peut cliquer sur l’icône pour la construction des routes. À ce

moment, le logiciel utilise un algorithme TSP si tous les clients peuvent être visités par

un seul camion en respectant les contraintes de capacité, d’espace, de durée et de fenêtres

de temps. Sinon, l’heuristique de construction privilégiée est celle de l’insertion du voisin

le plus près tentant de minimisant la distance totale à parcourir. La figure 4.11. apparaîtra

alors à l’écran permettant de visualiser un sommaire des routes.

90

4.4.1.3. Détails et optimisation des routes

L’interface VRP présentée à la figure 4.11. permet à l’utilisateur d’accéder à de

nombreuses options. Elle donne accès à toutes les méthodes d’amélioration des routes

disponibles. De plus, elle permet d’accéder à la visualisation des routes sur le logiciel de

cartographie MapPoint et elle donne le détail des routes et des commandes à livrer à tous

les clients.

Figure 4.11. : Optimisation des tournées

Le tableau apparaissant au départ donne un sommaire des caractéristiques des routes.

D’un seul coup d’œil, l’utilisateur peut voir le nombre de routes et pour chacune des

routes, la longueur, le temps de trajet, la capacité utilisée, le nombre de sacs de

récupération prévus et le nombre de clients de chacune de celles-ci. La longueur

représente le nombre de kilomètres parcourus par le véhicule du départ à l’entrepôt en

91

passant par chacun des clients et revenant à destination. En calculant le temps de

déchargement et le temps de route pour chacune, on retrouve le temps nécessaire présenté

à la deuxième ligne du tableau. Ce temps est donné en minutes. La capacité est celle

utilisée par les commandes à livrer pour cette route et la limite maximum est aussi

indiquée. Le nombre de sacs de récupération à recueillir est prend en considération la

moyenne su type de client visité. Ainsi, un dépanneur aura moins de sacs de bouteilles

vides qu’un supermarché. L’utilisateur peut aussi visualiser le nombre de client de

chacune des routes à parcourir.

Menu Algorithme

Le menu Algorithme présente les méthodes d’amélioration possibles pour un problème

TSP c’est-à-dire l’insertion du point le plus éloigné et le 3-opt. Ces fonctionnalités sont

disponibles uniquement lorsqu’une seule route visite tous les clients. Elle est aussi

accessible pour les problèmes TSP de la littérature.

Menu Optimisation

Le menu Optimisation est utile pour améliorer les routes d’un VRP, c’est-à-dire lorsque

plusieurs routes sont nécessaires pour livrer toutes les commandes aux clients. Le 3-opt

améliore individuellement chacune des routes tandis que l’algorithme « improve »

améliore simultanément plusieurs routes en interchangeant des clients de route.

Menu Détails

Le menu Détails est donne accès à toutes les routes. Il permet d’afficher les clients à

visiter pour la route sélectionnée. Pour plus de détails, l’utilisateur peut cliquer sur

l’icône qui lui permettra d’accéder à l’interface illustré à la figure 4.12.

92

Figure 4.12. : Feuille de route des camionneurs

Cette interface décrit en détail toutes les caractéristique de la route. Il s’agit en quelque

sorte de la feuille de route des livreurs. Ces derniers peuvent suivre en ordre les clients à

visiter puisque l’adresse de chacun est indiquée. La composition des commandes de

chacun des clients est décrite. De plus, le total de chacun des produits est inscrit de

manière à faciliter le chargement initial du camion. Le poids total permet de vérifier s’il

respecte le chargement maximal en vertu du guide des normes de charges et dimensions

des véhicules publié par transport Québec. Finalement, la durée de la route de même que

la distance parcourue pour visiter tous les clients sont calculées. Ces dernières sont les

distances réelles sans aucune approximation recalculées à l’aide de MapPoint. Rappelons

que pour utiliser les algorithmes, des distances symétriques avaient été utilisées.

La sélection de l’icône MapPoint permet de visualiser sur une carte la route à

parcourir. Ainsi, on accède directement à l’interface utilisée dans MapPoint.

93

Menu Visualiser En sélectionnant une route sous le menu Visualiser, l’utilisateur accède à MapPoint. La

plupart des fonctionnalités de MapPoint sont alors disponibles. Il peut donc ajouter ou

supprimer un client, agrandir ou diminuer la sélection, etc. De plus, le logiciel MapPoint

fournit les indications routières pour se rendre d’un client à un autre sans problème. La

figure 4.13. illustre un exemple d’une route obtenue grâce au logiciel.

Figure 4.13. : Accès à MapPoint

Le menu Visualiser contient aussi l’élément Toutes les routes qui permet de voir sur

MapPoint l’ensemble des routes à parcourir.

94

4.4.1.4. Fonctionnalités supplémentaires D’autres options sont aussi disponibles. Plusieurs de ces options sont présentes dans le

menu option de l’interface sélection des clients présentée précédemment à la figure 4.9.

Entres autres, il est possible pour l’utilisateur d’obtenir la distance entre deux villes à

l’aide des codes postaux. Aussi, une fois les clients sélectionnés, l’utilisateur peut

visualiser les commandes détaillées des clients tel qu’illusté à la figure 4.14. grâce à

l’option commande.

Figure 4.14. : Commande des clients

De plus, l’utilisateur peut voir la localisation de l’ensemble des clients en utilisant

l’option pushpin comme présenté à la figure 4.15.

Figure 4.15. : Localisation des clients

95

Finalement à chacune des interfaces, il est toujours possible de quitter par le menu

déroulant Fichier où se retrouve l’option Quitter ou en cliquant sur l’icône .

4.5. Conclusion

Ce chapitre a présenté l’approche de résolution développée pour résoudre le problème de

Distributions Jacques Dubois inc. Afin de supporter les approches, un logiciel complet a

été développé. Le logiciel, développé en Visual Basic, interagit avec Access et MapPoint.

Finalement, l’ensemble des fonctionnalités ont été illustrées.

96

Chapitre 5

Résultats

5.1. Introduction

Ce chapitre présente l’ensemble des données utilisées de même

que les routes obtenues suite à leur optimisation par le logiciel.

Une analyse des résultats obtenus permettra d’évaluer l’heuristique proposée pour

résoudre le problème de Distributions Jacques Dubois inc.

5.2. Présentation des données

L’approche proposée a été évaluée à partir de données réelles de deux semaines

typiques. À des fins de comparaisons, ces données ont été compilées et les distances

évaluées par le logiciel MapPoint. La planification de ces routes a été effectuée

manuellement et reflètent les routes de l’entreprise. Le tableau 5.1. présente un exemple

d’une route et des commandes des clients de cette route. Les autres routes sont présentées

en annexe A.

Pour la construction de ces routes, plusieurs contraintes doivent être respectés.

L’ensemble des routes permet de visiter 164 clients dont 19 imposent une fenêtre de

temps. Chacune des routes respecte la capacité du camion en terme de poids et de volume

utilisé tel que présenté au tableau 3.2. Le temps de service est de 10 minutes chez chacun

des clients et chacun des camions débutent à 6h et doit revenir à l’entrepôt à 14h. À des

fins de comparaison, la moyenne de sacs de récupération amassés a été utilisée selon le

type de client tel que présenté précédemment au tableau 3.4.

97

Tableau 5.1. : Exemple d’une route et des commandes associées

Route 1 Secteur Lévis

#client Nom Ville Code Postal 18 l 2 l Can. Chubby 600 ml 5l Autres Type

9112 Couche-Tard #2145795 Lévis G6V 6C6 9 2

127321 Dépan-Escompte Couche-Tard Lévis G6V 9H5 7 2

199170 Couche-Tard Lévis G6V 6S5 5 2 183580 Pharmaprix #16 Lévis G6V 6Y8 12 4

174391 Alimentation M S Nadeau inc. Lévis G6V 1Z4 18 6 3 2

45030 Accommodation 89 inc. Lévis G6V 1B6 12 1 3

442450 Dépanneur Chez Major enr. Lévis G6V 3Z4 6 5 3

8371633 Dépanneur Tout-Près inc. Lévis G6V 3Y7 6 1 1 3

439682 Dépanneur Beaudoin enr. Lévis G6V 5S7 12 1 3

438596 Alimentation Brochu Lévis G6V 4M6 6 1 2

8374857 Accommodation Saint-Georges enr. Lévis G6V 4L4 6 3

441330 Supermarché I G A Lévis G6V 2B2 12 3 1 199131 Couche-Tard Lévis G6V 5T3 11 2

8375805 Dépanneur R.Leclerc Lévis G6V 4Z3 1 3

442280 Dépanneur Couche-Tard Lévis G6V 4Z3 8 2

127550 Dépan-Escompte Couche-Tard St-David G6W 6M7 4 2

8377879 Pharmacie Francis Couillard Lévis G6W 1H7 6 4

443469 Dépanneur Couche Tard (Irving)

Saint-Romuald G6W 2R8 3 2

199127 Couche-Tard Saint-

Romuald G6W 2S5 4 2

8344774 Accomodation Danny

Saint-Romuald G6W 2M1 6 1 3

438427 Gestion mon Loup Saint-

Romuald G6W 3J3 12 1 3

88391341 Promutuel Lévisienne-Orléans

Saint-Romuald G6W 5M6 5 4

88355050 Lévis Suzuki Lévis G6V 7M5 2 4

98

5.3. Résultats

Le tableau 5.2. présente les caractéristiques principales des routes telles que planifiées par

Distributions Jacques Dubois inc. Pour construire ces routes, l’entreprise regroupe

généralement tous les clients d’un même secteur et décide ensuite du camion en fonction

de la demande et finalement de la tournée. Les commandes nécessitent quatre tournées

pour le camion de 16 000 livres, cinq tournées pour le camion de 8 000 livres et une

tournée pour le camion de 6 000 livres. La distance totale pour visiter tous les clients est

de 2 439 kilomètres tandis que la durée totale est de 3 597 minutes.

Tableau 5.2. : Routes initiales par Distributions Jacques Dubois inc.

Nb_route Distance Durée (min) Nb client Chargement Récupération Camion 1 64,2 297 23 7 170 175 16 000 2 230 350 17 8 252 170 16 000 3 299,5 362 12 7 472 137 16 000 4 287,9 366 15 7 196 149 8 000 5 170,7 388 24 7 428 244 16 000 6 239,8 369 17 6 682 138 8 000 7 293,5 385 14 4 211 100 6 000 8 279,5 369 15 7 472 108 8 000 9 310,6 382 15 6 198 57 8 000

10 263,6 329 12 4 676 121 8 000 Total 2 439,3 3 597 164 66 757 1 399

Moyenne 243,93 359,7 16,4 6 675,7 139,9

Le tableau 5.3. présente les résultats obtenus par l’heuristique de construction. Ces

routes ont été obtenus avec le critère

parcourue distanceée transportquantité . Les résultats

obtenus permettent d’améliorer la distance parcourue par l’ensemble des véhicules. Ces

résultats démontrent une amélioration significative. Une route a été éliminée ce qui

permet entre autres de réduire le nombre de camionneurs requis. De plus, la distance

totale a été réduite de 6,89 % passant de 2 439 à 2 271 kilomètres. Par ailleurs, la durée a

été réduite de 2,47%. Les commandes étant les mêmes, nous pouvons conclure que le

chargement est mieux distribué. Effectivement, le poids total (66 489) est moindre avec

l’approche proposée qu’avec la solution manuelle (66 757).Cela s’explique par

99

l’utilisation de moins de palettes. Finalement, pour visiter ces clients nous avons besoin

de six tournées pour le camion de 16 000 livres, d’une tournée pour le camion de 8 000

livres et deux tournées pour le camion de 6 000 livres.

Tableau 5.3. : Routes initiales

Nb_route Distance Durée (min) Nb client Chargement Récupération Camion

1 90,4 422 33 9 080 248 16 000 2 239,4 422 21 7 506 227 16 000 3 221,4 404 22 9 182 169 16 000 4 255,4 420 20 8 700 170 16 000 5 319,3 392 14 6 404 118 8 000 6 243,8 402 21 9 880 125 16 000 7 254,6 413 20 8 615 199 16 000 8 314,2 324 6 3 790 69 6 000 9 333,2 309 7 3 332 74 6 000

Total 2 271,57 3 508 164 66 489 1 399 Moyenne 252,40 389,78 18,22 7387,67 155,44

Suite à la construction des routes, le 3-opt a été appliqué à chacune des routes. Les

résultats obtenus sont présentés au tableau 5.4. Cette heuristique permet d’améliorer

quatre routes parmi les neuf proposées soient les routes 1, 2, 3 et 8. Les autres tournées

sont demeurées exactement les mêmes. Les améliorations apportées à ces routes

permettent de réduire la distance de 3,74 % et la durée de 2,21% par rapport aux routes

initiales obtenues précédemment.

Tableau 5.4. : Routes obtenues suite au 3-opt


1 77,4 413 33 9 080 248 16 0002 211,2 403 21 7 506 227 16 0003 206,8 395 22 9 182 169 16 0004 255,4 420 20 8 700 170 16 0005 319,3 392 14 6 404 118 8 0006 243,8 402 21 9 880 125 16 0007 254,6 413 20 8 615 199 16 0008 285 285 6 3 790 69 6 0009 333,2 309 7 3 332 74 6 000

Total 2 186,74 3 432 164 66 489 1 399 Moyenne 242,97 381,33 18,22 7 387,67 155,44

100

L’heuristique d’amélioration inter-route permet d’échanger entre deux routes des clients

afin d’améliorer la tournée. Cette méthode a aussi apportée des résultats intéressants. Tel

que présenté au tableau 5.5., la route 1 peut désormais être visité par un camions de 6 000

livres. Ainsi, le camion de 6 000 livres effectue trois tournées, le camion de 8 000 livres

en effectue encore une seule et le camion de 16 000 livres en parcourt cinq. De plus,

l’apport marginal de cette méthode est de 5,04% en ce qui concerne la distance à

parcourir et de 1,81% pour la durée totale.

Tableau 5.5. : Routes obtenues suite à l’amélioration inter-route


1 27,7 173 14 4 534 96 6 000 2 199,9 430 24 8 292 244 16 000 3 206,8 395 22 9 182 169 16 000 4 255,4 420 20 8 700 170 16 000 5 320,9 414 16 6 988 128 8 000 6 191,4 389 23 10 456 156 16 000 7 259,3 435 22 9 013 230 16 000 8 283,1 328 10 4 638 96 6 000 9 332,1 386 13 4 838 110 6 000

Total 2 076,47 3 370 164 66 641 1 399 Moyenne 230,72 374,44 18,22 7 404,56 155,44

Le 3-opt et l’amélioration inter-route sont appliqués à nouveau tant que des gains sont

réalisables. Ainsi, une autre itération a été nécessaire pour une réduction de distance

additionnelle de 1,2 %. Les routes finales pour lesquelles plus aucune amélioration n’est

possible sont présentées au tableau 5.6. Pour plus de détails, consulter l’annexe B qui

contient toutes les commandes de même qu’une représentation sur MapPoint. Par

rapport aux routes de Distributions Jacques Dubois inc., ces routes représentent une

amélioration considérable de 15,91%. Effectivement, la distance totale parcourue passe

de 2 439 à 2 051 kilomètres. De plus, la durée totale de l’ensemble des routes est

diminuée de 7,65 %. Or, chacune des routes est en moyenne 10 minutes plus longue

puisque le nombre de routes est moindre. Les camions sont aussi distribués autrement.

Ainsi, trois tournées sont effectuées par le plus petit camion (6 000 livres), une tournée

101

est parcourue par le camion de 8 000 livres et le camion de 16 000 livres parcourt cinq

tournées au total. Les figures 5.1. à 5.9. illustrent respectivement ces routes finales.

Tableau 5.6. : Routes finales


1 10,9 97 8 3 534 58 6 000 2 198,3 418 23 7 758 228 16 000 3 206,9 425 25 9 758 196 16 000 4 253,5 434 22 9 068 181 16 000 5 320,9 414 16 6 988 128 8 000 6 189,5 386 23 10 456 156 16 000 7 259,9 438 22 9 057 230 16 000 8 279,1 350 12 5 260 112 6 000 9 332,1 360 13 4 838 110 6 000

Total 2 051,02 3 322 164 66 717 1 399 Moyenne 227,89 369,11 18,22 7 301,89 155,44

102

Figure 5.1. : Illustration et description de la route 1


174391 Alimentation M S Nadeau inc. Lévis G6V 1Z4 18 6 3 2

45030 Accommodation 89 inc. Lévis G6V 1B6 12 1 3

8374857 Accommodation Saint-Georges enr. Lévis G6V 4L4 6 3

438596 Alimentation Brochu Lévis G6V 4M6 6 1 2

442450 Dépanneur Chez Major enr. Lévis G6V 3Z4 6 5 3

8371633 Dépanneur Tout-Près inc. Lévis G6V 3Y7 6 1 1 3

439682 Dépanneur Beaudoin enr. Lévis G6V 5S7 12 1 3

199131 Couche-Tard Lévis G6V 5T3 0 11 2

103

#client Nom Ville Code Postal 18 l 2 l Can. Chubby

600 ml 5l Autres Type

88355050 Lévis Suzuki Lévis G6V 7M5 2 4 125571 Dépan-Escompte Couche-Tard #525 Charny G6X 1X6 5 2

88322925 Promutuel Lévisienne-Orléans Charny G6X 1X7 3 4 147967 Dépanneur Sertard Charny G6X 2G6 18 2 152941 Epicerie Dumont Charny G6X 2T6 12 3 1 3 199091 Couche-Tard acc. Des Chutes Charny G6X 1B7 10 2

148450 Métro Morneau Saint-Nicolas G7A 2N9 16 1 190479 Supermarché R.Martin (IGA) Saint-Nicolas G7A 3S8 6 1 199146 Couche-Tard Saint-Nicolas G7A 1N3 3 2

88316556 Dépanneur le p'tit creux Saint-Nicolas G7A 2M9 1 6 6 1 3 437934 Accommodation de l'Erablière Saint-Nicolas G7A 2J6 6 3 442320 Dépanneur Couche-Tard Saint-Apollinaire G0S 2E0 2 2

88812401 9008-0474 Québec inc. (Petro-Canada) Saint-Apollinaire G0S 2E0 6 8 3 196316 Marché I.G.A St-Apollinaire Saint-Apollinaire G0S 2E0 5 1

87282926 Épicerie Denise Tanguay Saint-Flavien G0S 2M0 6 2 148770 Supermarché Laroche inc. Laurier-Station G0S 1N0 3 1

87282227 Épicerie A. Bergeron Saint-Janvier-de-

Joly G0S 1M0 6 2

87443323 Dépanneur Johanne Laroche enr. Val-Alain G0S 3H0 12 1 3

155510 Marché A H Fournier inc. (Provigo) Lyster G0S 1V0 6 3 178134 Alimentation Adrien Bisson Dosquet G0S 1H0 30 2 5 2

88883924 Dépanneur Super Soir St-Agapit G0S 1Z0 6 3

88360598 Dépanneur 610 enr. Saint-Etienne-de-

Lauzon G6J 1H2 6 1 3 88314427 Tabagie le Faubourg enr. Saint-Rédempteur G6K 1J4 6 8 4


104


#client Nom Ville Code Postal 18 l 2 l Can. Chubby 600 ml 5l Autres Type8375805 Dépanneur R.Leclerc Lévis G6V 4Z3 1 3 127321 Dépan-Escompte Couche-Tard Lévis G6V 9H5 7 2 199170 Couche-Tard Lévis G6V 6S5 5 2 138690 Épicerie Boucherie Marquis La Durantaye G0R 1W0 11 4 131068 R Campagna inc. La Durantaye G0R 1W0 11 6 3 442693 Alimentation Berthier Berthier-sur-Mer G0R 1E0 6 7 1 2

82481230 IGA Co-op Montmagny G5V 3A4 10 1 201443 Epicerie Léopold Fortin inc. Montmagny G5V 3N9 6 2 131471 Alimentation Léon Collin Montmagny G5V 1Y1 8 2

82481588 Marché Morency inc. Montmagny G5V 1E1 2 3 2 443100 Dépanneur Escompte Couche Tard Montmagny G5V 1B7 3 2 174427 Dépanneur Ultra Saint-François enr Saint-François-Montmagny G0R 3A0 6 3 3

82432022 Gestion Pat Saint-Raphaël G0R 4C0 6 3 131072 Marché Saint-Raphaël enr. Saint-Raphaël G0R 4C0 22 2 2 439794 Marché Côté enr. Armagh G0R 1A0 22 2 195462 Servis plus Andre Roy Saint-Philémon G0R 4A0 6 6 1 3 202219 Boucherie Pierre Picard Saint-Philémon G0R 4A0 8 4 146735 Bissonnette Ernest Saint-Damien-de-Buckland G0R 2Y0 10 1 3

87892972 Epicerie Boucherie Labrecque Saint-Damien-de-Buckland G0R 2Y0 8 4 132952 Alimentation Côté & Morin inc. Saint-Lazare-De-Bellechasse G0R 3J0 11 1 2 174412 Duquet Guy Sainte-Claire G0R 2V0 11 8 1 3

88833988 Alimentation Carrier inc. Sainte-Claire G0R 2V0 3 6 2131355 Dépanneur Etchemin Saint-Anselme G0R 2N0 11 8 1 3

88854031 Dépanneur Express Saint-Anselme G0R 2N0 6 3438465 Dépanneur Super-Soir enr. Saint-Anselme G0R 2N0 6 8 1 2 2 3

105


127550 Dépan-Escompte Couche-Tard St-David G6W 6M7 4 2

431037 Jean-Guy Fontaine inter-marché Pintendre G6C 1C8 6 10 1 88351479 Promutuel Lévisienne-Orléans Pintendre G6C 1C9 2 4 141133 Marché L Fournier inc. Sainte-Hénédine G0S 2R0 22 3 3 442674 Épicerie Guy Berthiaume inc. Scott G0S 3G0 33 2 148390 Métro Labonté inc. Sainte-Marie G6E 1N7 8 10 1 442465 Super Soir Sainte-Marie G6E 1M9 6 2

142175 Alimentation Nadeau & Vallée inc.

(Marché) Saint-Elzéar G0S 2J0 6 2

141100 Alimentation Lachance & Roy enr. Vallée-Jonction G0S 3J0 6 3

152620 Alimentation Saint-Joseph-de-

Beauce Saint-Joseph-de-

Beauce G0S 2V0 9 2 176783 Dépanneur Servis Express Saint-Joseph G0S 2V0 6 8 1 3

433735 Accommodation Jacques enr. Saint-Joseph-de-

Beauce G0S 2V0 6 3

444540 IGA Co-op Saint-Joseph-de-

Beauce G0S 2V0 12 1 145712 Lessard J T & Fils Tring-Jonction G0N 1X0 40 3 172415 Roy Denis Tring-Jonction G0N 1X0 1 5 3 440472 Gas Bar Drouin East Broughton G0N 1G0 2 4

83380844 Boucherie Ré-Jo inc. Robertsonville G0N 1L0 12 4 436468 Alimentation Chez Yves enr. Pontbriand G0N 1K0 6 2 441880 Placement G.R. Gilbert Thetford Mines G6G 1J6 12 8 4 183220 Jean Coutu #160 Thetford Mines G6G 2A8 6 4 439513 Dépanneur Chez Pee-Wee inc. Thetford Mines G6G 1Z2 6 2 1 3

83356353 Accommodation Chez Guy enr. Thetford Mines G6G 2W2 6 3


106



103659 Epicerie Centre Matic inc.

(IGA) Saint-Lambert-de-

Lauzon G0S 2W0 6 1

142160 S C A la Seigneurie Saint-Narcisse-de-

Beaurivage G0S 1W0 6 4

85962353 Marché Beaurivage Saint-Patrice-de-

Beaurivage G0S 1B0 6 2

85962809 Accommodation Cybel

Air Saint-Patrice-de-

Beaurivage G0S 1B0 6 1 3

451366 Dépanneur Bécancour

enr. Lyster G0S 1V0 6 1 2 3 102904 IGA Coop Plessisville Plessisville G6L 3J1 6 1

145556 Alimentation M R enr. Plessisville G6L 1K6 12 1 3 93626766 Dépanneur l'Oriental Plessisville G6L 2N8 6 3

93627298 Épicerie Boucherie

Thibault Plessisville G6L 2E3 6 8 2

93854236 Dépanneur de Lourdes Lourdes G0S 1T0 12 3

93854799 Dépanneur Villeroy enr. Villeroy G0S 1T0 2 3 3

173311 Marché Raymond Minot Manseau G0X 1V0 40 2 2 93562353 ADG Tanguay Manseau G0X 1V0 12 8 1 4

440468 Dépanneur M.B. Sainte-Françoise-de-

Lotbinière G0S 2N0 12 3

149979 Morasse Michel Sainte-Sophie-de-

Lévrard G0X 3C0 11 2 3

92632818 Dépanneur Roger

Deschênes Sainte-Cécile-de-

Lévrard G0X 2M0 12 8 3

107



442280 Dépanneur Couche-Tard Lévis G6V 4Z3 8 2 441330 Supermarché I G A Lévis G6V 2B2 12 3 1 443469 Dépanneur Couche Tard (Irving) Saint-Romuald G6W 2R8 0 3 2

88762396 Gaz Bar S B L Neuville G0A 2R0 6 4 88762733 Accommodation Goguen Neuville G0A 2R0 2 2 3 102942 Supermarché J.C. Bédard (IGA) Pont-Rouge G0A 2X0 25 12 1 6680 Dépanneur Pont-Rouge Pont-Rouge G0A 2X0 12 0 0 0 2 18 3

205657 Épicerie JP Cormier Saint-Basile G0A 3G0 2 12 6 3 2 83292024 Épicerie Strasbourg Saint-Basile G0A 3G0 1 4 1 2 83292848 Aliments J. Plamondon Saint-Basile G0A 3G0 12 2 2 145235 Marché Richelieu Saint-Basile G0A 3G0 11 2 137401 Dépanneur Club Vidéo Portneuf Portneuf G0A 2Y0 12 1 4

82863655 Camping Portneuf enr. Portneuf G0A 2Y0 4 4 82864881 Industries Portneuf Portneuf G0A 2Y0 23 4

82683598 Dépanneur Patrice Perreault Saint-Marc-

des-Carrières G0A 4B0 12 3 82864950 Pro-Métal Plus Deschambault G0A 1S0 12 4 131170 Magasin Paré enr. Deschambault G0A 1S0 1 3 144932 Dépanneur Shell Cap-Santé Cap-Santé G0A 1L0 12 3

82851717 Accommodation Cap-Santé Cap-Santé G0A 1L0 6 4 3 82850375 Dépanneur l'Imprévu enr. Donnacona G0A 1T0 18 2 2 3 82852171 Accommodation rayon de soleil Donnacona G0A 1T0 6 1 1 3 82853220 Auto Franck et Michel Donnacona G0A 1T0 2 4 88391341 Promutuel Lévisienne-Orléans Saint-Romuald G6W 5M6 5 4

108


#client Nom Ville Code Postal 18 l 2 l Can. Chubby 600 ml 5l Autres Type183580 Pharmaprix #16 Lévis G6V 6Y8 12 4 103211 Co-Op Magasin (IGA) St-Anselme G0R 2N0 6 1

86422814 Epicerie Luno enr. Saint-Malachie G0R 3N0 6 2 2 3

149263 Alfred Couture ltée Saint-Léon-de-

Standon G0R 4L0 7 3 3

148688 Marché Métro (Ofrigidaire

Alimentation) Lac-Etchemin G0R 1S0 4 1 86252921 Dépanneur Chez Ben Lac-Etchemin G0R 1S0 4 3

153721 Dépanneur Charly enr. Beauceville G0S 1A0 12 1 3

176356 Alimentation Beauceville inc.

(Métro) Beauceville G0S 1A0 8 1 150127 Accommodation 120 Saint-Georges G5Y 2Z9 40 3 126390 Dépan-Escompte Couche-Tard Saint-Georges G5Y 3W5 12 2 130269 Marché Fecteau & Frère inc. Saint-Georges G5Y 3W7 6 2 143428 Gaz Bar Bérubé inc. Saint-Georges G5Y 5X7 12 1 4 147948 Alimentation Fortin Saint-Georges G5Y 3V9 40 3 2

82286571 Dépanneur E. Jacques enr. Saint-Georges G5Y 3X7 6 3

439167 Marché Roger Rodrigue (IGA) Saint-Georges G5Y 3X8 6 6 1 148542 Marché Laval Veilleux & Fils Saint-Georges G5Y 8G9 8 5 2 150170 Le P'tit Dépanneur Saint-Georges G5Y 1C6 3 3 202870 Accommodation 127 enr. Saint-Georges G5Y 7A6 8 3

82280430 Dépanneur l'Express Saint-Georges G5Y 5H1 6 3 82287925 Dépanneur Rapido Saint-Georges G5Y 1Z3 6 1 3

103488 Marché Gaston Paquet

inc.(IGA) Saint-Georges G5Y 1S5 18 1 204254 Alimentation Gilbert Saint-Georges G5Y 1S4 11 8 1 2

109


199112 Couche-Tard #2145795 Lévis G6V 6C6 9 2 199127 Couche-Tard Saint-Romuald G6W 2S5 4 2

151363 Épicerie Denis Filteau

Ltée Saint-Ubalde G0A 4L0 3 2

437286 Épicerie Chez Nicole Notre-Dame-

de-Montauban G0X 1W0 22 2 83232929 Épicerie Joanne Dery Rivière-à-Pierre G0A 3A0 12 1 6 1 2

83232233 Epicerie Boucherie Lam-

Bher inc. Rivière-à-Pierre G0A 3A0 24 4 4 83372212 Epicerie Gingras enr. Saint-Raymond G3L 3Y5 6 2 1 2

83372944 Accomodation St-

Jacques Saint-Raymond G3L 3Y3 2 1 3

129601 Voyer & Jobin ltée

(Provigo) Saint-Raymond G3L 1J4 24 1 130482 Omni #4125 Saint-Raymond G3L 3S6 12 2

8344774 Accomodation Danny Saint-Romuald G6W 2M1 6 1 3

8377879 Pharmacie Francis

Couillard Lévis G6W 1H7 6 4


110

#client Nom Ville Code Postal 18 l 2 l Can. Chubby 600 ml 5l Autres Type438427 Gestion mon Loup Saint-Romuald G6W 3J3 12 1 3

435751 Accommodation Vanier

enr. Saint-Jean-

Chrysostome G6Z 1Z9 6 3

445071 Dépanneur Escompte Couche Tard (Irving)

Saint-Jean-Chrysostome G6Z 2C1 2 2

88391705 Dépanneur Mari-Pier enr. Saint-Jean-

Chrysostome G6Z 2A4 6 3

199108 Couche-Tard Saint-Jean-

Chrysostome G6Z 3G8 5 2

145220 Dépanneur Piermont enr. Saint-Jean-

Chrysostome G6Z 2E8 2 3

84274288 René Composite Sainte-Clotilde-

de-Beauce G0N 1C0 15 4

84275246 Dépanneur Mymi Sainte-Clotilde-

de-Beauce G0N 1C0 24 1 3 443074 IGA #407 Thetford Mines G6G 6H1 18 1 126406 Dépanneur Couche Tard Thetford Mines G6G 6X9 9 2

125888 Dépan-Escompte Couche-

Tard Black Lake G6H 2A3 7 2 84235727 Alimentation Denis inc. Black Lake G6H 2B4 6 1 2 82287129 Économie Ti-Pier Saint-Georges G5Y 4V9 6 3


111

En modifiant le critère de résolution des routes ( voir étape 4 de la méthode présentée à la

section 4.3.2) , il est possible d’obtenir des résultats différents. Ainsi, le critère

parcourue distanceclients de nombre amène les routes finales présentées au tableau 5.7. Ce

nouveau critère amène des résultats moins performants que les précédents mais il permet

tout de même d’améliorer la distance des routes initiales de 9,31% et la durée de 1,89%

par rapport aux routes parcourues initialement par Distributions Jacques Dubois inc. Par

ailleurs, avec ces résultats, le camion de 8 000 livres n’est plus utilisé. Le camion de

6 000 livres parcourt quatre routes tandis que le camion de 16 000 livres en parcourt cinq.

Finalement, le chargement est légèrement inférieur, 66 641 par rapport à 66 757,

indiquant une meilleure distribution des commandes dans chacun des camions.

Effectivement, les commandes sont exactement les mêmes que celles effectués par

l’entreprise.

Tableau 5.7. : Routes finales obtenues avec critère nb clients/ distance parcourue


1 13,0 131 11 4 394 94 6 000 2 211,7 469 27 9 228 243 16 000 3 206,9 425 25 9 758 196 16 000 4 255,4 420 20 8 700 170 16 000 5 317,8 402 14 5 684 118 6 000 6 218,6 477 26 11 486 180 16 000 7 260,0 437 22 7 551 224 16 000 8 397,7 388 6 3 966 63 6 000 9 330,8 380 13 5 874 111 6 000

Total 2 211,95 3 529 164 66 641 1 399 Moyenne 245,77 392,11 18,22 7404,55 155,44

5.4. Conclusion

Ce chapitre a présenté les résultats de l’approche développée. En prenant comme

comparaison les routes utilisées par Distributions Jacques Dubois inc., les routes

générées sont 15,91% plus courtes en terme de distance, soit une réduction de 388

112

kilomètres. Il faut cependant mentionner que la solution retenue nécessite un véhicule de

moins ce qui peut représenter une économie importante pour l’entreprise.

113

Chapitre 6

Conclusion

Les problèmes de tournées sont très présents autant dans la littérature que dans la réalité.

Cet essai a permis de mieux connaître les problèmes de tournées de même que leurs

applications dans des cas réels. Nous avons recensé les articles récents de la littérature

traitant du problème du voyageur de commerce et du problème de tournées de véhicules.

Bien que ces problèmes ne soient pas nouveaux, ils sont encore aujourd’hui très présents

dans la littérature. Les articles étudiés démontrent une tendance vers les problèmes de

tournées avec restrictions sur les fenêtres de temps. Par ailleurs, l’algorithme génétique

est très populaire au cours des dernières années.

L’entreprise étudiée, soit Distributions Jacques Dubois inc. fait face à un problème de

tournées de véhicules avec fenêtres de temps, flotte hétérogène et produits multiples.

L’approche dévelopée a permis de proposer de nouvelles routes à l’entreprise. Cette

approche est composée d’une heuristique de construction suivie de deux heuristiques

d’amélioration. Les résultats démontrent que l’approche proposée permet d’améliorer

considérablement les routes généralement utilisées par l’entreprise Distribution Jacques

Dubois inc. Chacune des étapes a été étudiée séparement de manière à démontrer leur

apport marginal. Ainsi, les résultats obtenus permettent de réduire de 15,91% la distance

soit 388 kilomètres pour deux semaines typiques. Par ailleurs, la durée est améliorée de

7,65%. Sur une base annuelle, cela se traduirait par des économies considérables et

permettrait entres autres d’améliorer l’efficacité de la flotte de véhicules.

Plusieurs améliorations pourraient être éventuellement apportés à cet essai de manière à

améliorer les résultats obtenus. Effectivement, il serait possible de modifier le type de

véhicule utilisé lors de l’amélioration inter-route. De plus, dans cet essai, les distances

sont considérées à partir des codes postaux, une étude plus poussée pourrait permettre de

considérer l’adresse exacte des clients.

114

Finalement, tout porte à croire que cette approche de résolution pourrait être utile pour

d’autres entreprises de transport. Elle permettrait alors d’améliorer la planification des

tournées et par le fait même réduire les coûts de transport et améliorer leur niveau de

rentabilité et de compétitivité.

115

Références 1. Achuthan N.R., Caccetta L. & Hill S.P., “An improved branch-and-cut algorithm for

the capacited vehicle routing problem.” Transportation Science (2003), 37; 2: 153-169.

2. Arunapuram Sundararajan, Mathur Kamlesh & Solow Daniel, “Vehicle Routing and

scheduling with full truckloads.” Transportation Science (2003), 37; 2: 170-182. 3. Avella Pasquale, Boccia Maurizio & Sforza Antonio., “Solving a fuel delivery

problem by heuristic and exact approaches.” European Journal of Operational Research (2003), À paraître.

4. Baker Barrie M.& Ayechew M. A., “A genetic algorithm for the vehicle routing

problem.” Computers & Operations Research (2003), 30; 5: 787-800. 5. Baker Barrie M. & Carreto Carlos A. C., “A visual interactive approach to vehicle

routing.” Computers & Operations Research (2003), 30; 3: 321-337. 6. Baker B., Furnon V., Shaw P., Kilby P. & Prosser P., “Solving vehicle routing

problem using constraint programming and metaheuristics.” Journal of heuristics (2000), 6: 501-523.

7. Baptista Susana, Carvalho Rui Oliveira & Zúquete Eduardo., “A period vehicle

routing case study.” European Journal of Operational Research (2002), 139; 2: 220-229.

8. Belenguer José M. & Benavent Enrique. “A cutting plane algorithm for the

capacitated arc routing problem.” Computers & Operations Research (2003), 30; 5: 705-728.

9. Benavent E, Campos V, Corberan A & Mota E., “The capacitated arc routing

problem.” Networks (1992), 22: 669-690. 10. Berger Jean & Barkaoui Mohamed. “A parallel hybrid genetic algorithm for the

vehicle routing problem with time windows.” Computer & Operations Research (2003), À paraître.

11. Beullens Patrick, Muyldermans Luc, Cattrysse Dirk & Oudheusden Dirk Van. “A

guided local search heuristic for the capacitated arc routing problem.” European Journal of Operational Research (2003), 147; 3: 629-643.

116

12. Bolduc, Marie-Claude, Planification du transport de charges partielles d'un dépôt : répartition, livraison et revenu de retour. Essai de maîtrise (2003), Faculté des sciences de l'administration, Université Laval, Québec, Canada.

13. Bourgeois Mélanie, Laporte Gilbert & Semet Frédéric. “Heuristics for the black and

white traveling salesman problem.” Computers & Operations Research (2003), 30; 1: 75-85.

14. Brotcorne Luce, Laporte Gilbert & Semet Frédéric. “Ambulance location and

relocation models.” European Journal of Operational Research (2003). À paraître. 15. Cabral Edgar Alberto, Gendreau Michel, Gianpaolo Ghiani & Laporte Gilbert.

“Solving the hierarchical Chinese postman problem as a rual postman problem.” European Journal of Operational Research (2003). À paraître.

16. Chan Yupo, Carter William B. & Burnes Michael D. “A multiple-depot, multiple-

vehicle, location-routing problem with stochastically processed demands.” Computers & Operations Research (2001), 28; 8: 803-826.

17. Chen Yen-Liang & Hsiao Li-Jen. “Shipping problems with body clock constraints.”

Computers & Operations Research (2003), 30; 7: 1037-1049. 18. Chian Wen-Chyuan & Russell Robert A., “A reactive tabu search metaheuristic for

the vehicle routing problem with time windows.” INFORMS Journal on Computing (1997), 9: 417-430.

19. Chian Wen-Chyuan & Russell Robert A. Integrating purchasing and routing in a

propane gas supply chain. European Journal of Operational Research (2003). À paraître.

20. Choi In-Chan, Kim Seong-In & Kim Hak-Soo. A genetic algorithm with a mixed

region search for the asymmetric traveling salesman problem. Computers & Operations Research (2003); 30; 5: 773-786.

21. Christofides N. & Eilon S., An algorithm for the vehicle dispatching problem.

Operation Research Quart.( 1969); 20; 309-318. 22. Christofides N. Mingozzi A. & Toth P., The vehicle routing problem. N. Christofides,

A. Mingozzi, P. Toth, M. sandi, eds. Combinatorial Optimization (1979): 315-338. 23. Clarke G. & Wright J. W., Scheduling of vehicles from a central depot to a number of

delivery points. Operation Research (1964); 11: 568-581.

117

24. Colorni A., Dorigo M. & Maniezzo V.,. « Distributed Optimization by Ant Colonies », Proceedings of the First European Conference on Artificial Life (1991), MIT Press/Bradford Book, Paris: 134-142.

25. Cordeau J., Laporte G. & Mercier A., A unified tabu search heuristic for vehicle

routing problems with time windows, Technical report CRT-00-03 (2000); Centre de recherche sur les transport, Montréal, Canada.

26. Cordeau Jean-François, Gendreau Michel et Laporte Gilbert, A tabu search heuristic for

periodic and multi-depot vehicle routing problems. Networks (1997); 30: 105-119. 27. Dantzig G. B. & Ramser R.H. "The Truck Dispatching Problem". Management Science

(1959); 6: 80–91. 28. Fisher M.L., Optimal solution of vehicle routing problems using minimum k-trees,

Operation Research (1994); 42: 626-642. 29. Fisher M. & Jaikumar R., A generalized assignement heuristic for vehicle routing,

Networks (1981); 11: 109-124. 30. Gillett B. & Miller L., A heuristic algorithm for the vehicle dispatch problem,

Operations Research (1974); 22 : 340-349. 31. Gendreau Michel, Hertz Alain & Laporte Gilbert. New insertion and postoptimization

procedures for the traveling salesman problem. Operation Research (1992), 40; 1086-1094.

32. Gendreau Michel, Hertz Alain & Laporte Gilbert. The traveling salesman problem

with backhauls. Working paper CRT-912 (1993)., Centre de recherche en transport, Université de Montréal, Québec, Canada

33. Gendreau Michel, Hertz Alain & Laporte Gilbert. A tabu search heuristic for the

vehicle routing problem. Management Science (1994); 40: 1276-1290. 34. Gendreau M., Laporte, G., Musaraganyi, Ch., Taillard, E., A tabu search heuristic for

the heterogeneous fleet vehicle routing problem. Computer and Operations Research (1999); 26: 1153-1173.

35. Ghaziri Hassan & Osman Ibrahim H. A neural network algorithm for the traveling

salesman problem with backhauls. Computers & Industrial Engineering (2003); 44; 2: 267-281.

36. Glover Fred, Future paths for integer programming and links to artificial intelligence.

Computer and Operation Research (1986); 13: 533-549.

118

37. Glover Fred, Gutin Gregory, Yeo Anders & Zverovich Alexey. Construction heuristics for the asymmetric TSP, European Journal of Operational Research (2001); 129; 3: 555-568.

38. Golden B.L., DeArmon JS & Baker EK. Computational experiments with algorithms

for a class of routing problems. Computers and Operations Research (1983); 10: 47-59.

39. Golden B.L. & Wasil, E.A Computerized vehicle routing in the soft drink industry.

Operation Research (1987); 35;1: 6-17 40. Golden, B.L., Wasil, E.A., Kelly, J.P. & Chao, I.M. The impact of metaheuristics on

solving the vehicle routing problem: algorithms, problem sets, and computational results. Fleet management and logistics Kluwer (1998).

41. Gronalt Manfred, Hartl Richard F. & Reimann Marc. New savings based algorithms

for time constrained pickup and delivery of full truckloads. European Journal of Operational Research (2003). À paraître.

42. Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman

heuristic, European Journal of Operational Research (2000), 126, 1: 106. 43. Holland J.H. Adaptation in natural and artificial systems. The University of Michigan

Press (1975), Ann Arbor, MI. 44. Homberger J.& Gehring H. Two evolutionary metaheuristics for the vehicle routing

problem with time windows, INFOR (1999) ; 37: 297-318. 45. Hwang Heung-Suk. An improved model for vehicle routing problem with time

constraint based on genetic algorithm. Computers & Industrial Engineering (2002); 42; 2-4: 361-369.

46. Ioannou Georges, Kriticos Manolis & Prastacos Gregory. A problem generator-solver

heuristic for vehicle routing with soft time windows. Omega (2003); 31: 41-53. 47. Jaszkiewicz Andrzej & Kominek Pawel. Genetic local search with distance

preserving recombination operator for a vehicle routing problem. European Journal of Operational Research (2003). À paraître.

48. Kiuchi M, Shinano Y, Hirabayashi R & Saruwatari Y. An exact algorithm for the

capacitated arc routing problem using Parallel Branch and Bound method. Abstracts of the 1995 Spring National Conference of the Operational Research Society of Japan (1995): 28-29.

49. Laporte, G. The Traveling Salesman Problem: An overview of exact and approximate

algorithms; European Journal of Operational Research (1992); 59; 231-247.

119

50. Laporte G., Gendreau M., Potvin J-Y & Semet F. Classical and modern heuristics for the vehicle routing problem. International transactions in operational research (2000); 7: 285-300.

51. Laporte G. & Osman I. H. Routing Problems : A Bibliography. Annals of Operations

Research (1995) ; 61 : 227-262. 52. Lau Hoong Chuin, Sim Melvyn & Teo Kwong Meng. Vehicle routing with time

windows and a limited number of vehicles. European Journal of Operational Research (2003). À paraître.

53. Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. & Shmoys D. B. The traveling

salesman problem. A guided tour of combinatorial optimisation. John Wiley & Sons (1985).

54. Li Haibig & Lim Andrew. Local search with annealing-like restarts to solve VRPTW.

European Journal of Operational Research (2003). À paraître. 55. Liu F-H & Shen S-Y., A route-neighborhood-based metaheuristic for the vehicle

routing problem with time windows. Journal of Operational Research (1999); 118: 485-504.

56. Miller D.L., A matching based exact algorithm for capacitated vehicle routing

problems, ORSA J. Comput. (1995); 7; 1: 1-9. 57. Mladenovic N. & Hansen P. Variable neighbourhood search. Computer and

Operations Research (1997), 24: 1097-1100. 58. Moin Noor Hasnah. Hybrid Genetic Algorithms for Vehicle Routing Problem with

Time Windows. International Journal of the Computer, the Internet and Management (2002); 10:1-17.

59. Moon Chiung, Kim Jongsoo, Choi Gyunghyun & Seo Yoonho. An efficient genetic

algorithm for the traveling salesman problem with precedence constraints. European Journal of Operational Research (2002); 140; 3: 606-617.

60. Osman Ibrahim H. Metastrategy simulated annealing and tabu search algorithms for

the vehicle routing problem. Annals of Operations Research (1993) ; 41: 421-451. 61. Osman Ibrahim H. & Wassan Niaz. A reactive tabu search meta-heuristic for the

vehicle routing problem with back-hauls. Journal of Scheduling (2002); 5: 263-285. 62. Osman I. & Salhi S. Local search strategies for the vehicle fleet mix problem. In:

rayward-Smith, V.J., Osman, I.H., Reeves, C.R., Smith, G.D. (Eds.), Modern Heuristic Search Methods. (1996) Wiley, New York : 131-153.

120

63. Paletta Giuseppe. The period traveling salesman problem: a new heuristic algorithm. Computers & Operations Research (2002); 29; 10: 1343-1352.

64. Patterson R. & Rolland E. The cardinality constrained covering traveling salesman

problem. Computers & Operations Research (2003); 30; 1: 97-116. 65. Prins Christian. A simple and Effective Evolutionary Algorithm for the Vehicle

Routing Problem. Research report (2001). University of Technology of Troyes. 66. Prins Christian. A simple and Effective Evolutionary Algorithm for the Vehicle

Routing Problem. Computer and operations Research (2003), À paraître. 67. Rego C. & Roucairol C. A parallel tabu search algorithm using ejection chains for the

vehicle routing problem. In: Osma, I.H., Kelly J. (Eds.):Meta-Heuristics: Theory and Applications (1996).

68. Reimann M., Doerner K. & Hart F.R., D-Ants: Savings based Ants divide and

conquer the Vehicle Routing Problem, Department of Production and Operations Management, Institute on Management Science, University of Vienna, A-1210, Vienna, Austria. 1-39.

69. Reinelt, G. A traveling salesman problem library, ORSA J. Comput. (1981); 3: 376-

384. 70. Renaud Jacques & Boctor Fayez F. A sweep-based algorithm for the fleet size and

mix vehicle routing problem. European Journal of Operational Research (2002); 140; 3: 618-628.

71. Renaud Jacques & Boctor Fayez F., Laporte Gilbert. Perturbation heuristics for the

pickup and delivery traveling salesman problem. Computers & Operations Research (2002); 29; 9: 1129-1141.

72. Renaud Jacques, Boctor Fayez F. & Ouenniche Jamal. A heuristic for the pickup and

delivery traveling salesman problem. Computers & Operations Research (2000); 27; 9: 905-916.

73. Renaud Jacques, Laporte Gilbert et Boctor Fayez F., « A tabu search heuristic for the

multi-depot vehicle routing problem ». Computers and Operations Research (1996); 23; 3: 229-235.

74. Rochat, Y. & Taillard, Éric D. Probabilistic Diversification and Intensification in

Local Search for Vehicle Routing. Journal of Heuristics (1995); 1; 147-167. 75. Rosenkrantz D. J., Stearns R. E. & LEWIS II P. M., An analysis of several heuristics

for the traveling salesman problem. SIAM Journal on Computing (1977); 6, 3, 563-581.

121

76. Rousseau L., Gendreau P. & Pesant G., Using constraint-based operators to solve vehicle routing problem with time windows, Journal of Heuristics (2002); 8: 43-58.

77. Schneider Johannes. The time-dependent traveling salesman problem. Physica A:

Statistical Mechanics and its Applications (2002); 314; 1-4: 151-155. 78. Shaw P., Using constraint programming and local search methods to solve vehicle

routing problems. In: Maher M, Puget J-FF, editors. Principles and practice of constraint programming, Lecture Notes in Computer Science (1998); Springer: 417-431.

79. Shutler P M E. An improved branching rule for the symmetric traveling salesman

problem. The Journal of the Operational Research Society (2001); 52; 2. 80. Solomon, M. Marius. Algorythms for the vehicle routing and scheduling problems

with time window constraints. Operations Research Society of America (1987); 35; 2: 254-265.

81. Spaeth, H., Cluster-Analyse-Algorithmen zur Objektklassifizierung und

Datenreduktion, Oldenbourg, Muenchen (1977). 82. Taillard E. D. A heuristic column generation method for heterogeneous fleet VRP.

(1999), RAIRO 33 (1), 1-14. 83. Taillard E. D. Parallel iterative search methods for vehicle routing problems.

Networks (1993); 23; 661-673. 84. Taillard E. D., Badeau P., Gendreau M., Geurtin F. & Potvin J., A tabu search

heuristic for the vehicle routing problem with time windows, Transportation Science (1997); 31: 170-186.

85. Taillard E.D., A heuristic column generation method for the heterogeneous fleet

VRP. RAIRO (1999); 33: 1-34. 86. Taillard E. D., Gambardella Luca M., Gendreau Michel & Potvin Jean-Yves.

Adaptive memory programming: A unified view of metaheuristics. European Journal of Operational Research (2001); 135: 1-16.

87. Tarantilis C. D., Kiranoudis C. T. & Vassiliadis V. S. A threshold accepting

metaheuristic for the heterogeneous fixed fleet vehicle routing problem. European Journal of Operational Research (2003). À paraître.

88. Toth P.& Vigo D. Models, relaxations and exact approaches for the capacitated

vehicle routing problem. Discrete Applied Mathematics (2002a); 123; 1-3: 487-512.

122

89. Toth, P.& Vigo D. The Granular Tabu Search and its Applications to the Vehicle Routing Problem. INFORMS Journal on Computing (2002b).

90. Wu Tai-Hsi, Low Chinyao & Bai Jiunn-Wei. Heuristic solutions to multi-depot

location-routing problems. Computers & Operations Research (2002); 29; 10: 1393-1415.

91. Xu Hang, Chen Zhi-Long, Rajagopal Srinivas & Arunapuram Sundar. Solving a

practical pickup and delivery problem. Transportation Science (2003); 37 : 347-364. 92. Xu J. & Kelly J. A network flow-based tabu search heuristics for the vehicle routing

problem. Transportation Science (1996); 30 : 379-393.

Références internet

www.statcan.ca (consulté le 10 août 2003)

www.strategis.ic.gc.ca (consulté le 15 août 2003)

http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ (consulté le 11 novembre 2003)

123

Annexes

124

ANNEXE A : Routes et commandes initiales par Distributions Jacques Dubois inc.

Route 2 : Secteur St-Georges

#client Nom Ville Code Postal 18 l 2 l Can Chubby


176356

Alimentation Beauceville inc. (Métro) Beauceville G0S 1A0 8 1

153721 Dépanneur Charly enr. Beauceville G0S 1A0 12 1 3

147948 Alimentation Fortin Saint-Georges G5Y 3V9 40 3 2

82287129 Économie Ti-Pier Saint-Georges G5Y 4V9 6 3

439167 Marché Roger Rodrigue (IGA) Saint-Georges G5Y 3X8 6 6 1

82286571 Dépanneur E. Jacques enr. Saint-Georges G5Y 3X7 6 3

143428 Gaz Bar Bérubé inc. Saint-Georges G5Y 5X7 12 1 4

130269 Marché Fecteau & Frère inc. Saint-Georges G5Y 3W7 6 2

126390 Dépan-Escompte Couche-Tard Saint-Georges G5Y 3W5 12 2

148542 Marché Laval Veilleux & Fils Saint-Georges G5Y 8G9 8 5 2

204254 Alimentation Gilbert Saint-Georges G5Y 1S4 11 8 1 2

103488 Marché Gaston Paquet inc.(IGA) Saint-Georges G5Y 1S5 18 1

150170 Le P'tit Dépanneur Saint-Georges G5Y 1C6 3 3

202870 Accommodation 127 enr. Saint-Georges G5Y 7A6 8 3

82280430 Dépanneur l'Express Saint-Georges G5Y 5H1 6 3

82287925 Dépanneur Rapido Saint-Georges G5Y 1Z3 6 1 3

150127 Accommodation 120 Saint-Georges G5Y 2Z9 40 3

125

Route 3 : Secteur Saint-Raymond

#client Nom Ville Code Postal 18 l 2 l Can Chubby 600 ml 5l Autres Type

130482 Omni #4125 Saint-

Raymond G3L 3S6 12 2

129601 Voyer & Jobin ltée (Provigo)

Saint-Raymond G3L 1J4 24 1

83372212 Epicerie Gingras enr.

Saint-Raymond G3L 3Y5 6 2 1 2

83372944 Accomodation St-Jacques

Saint-Raymond G3L 3Y3 2 1 3

83232233 Epicerie Boucherie Lam-Bher inc.

Rivière-à-Pierre G0A 3A0 24 4 4

83232929 Épicerie Joanne Dery

Rivière-à-Pierre G0A 3A0 12 1 6 1 2

102942 Supermarché J.C. Bédard (IGA) Pont-Rouge G0A 2X0 25 12 1

6680 Dépanneur Pont-Rouge Pont-Rouge G0A 2X0 12 0 0 0 2 18 3

205657 Épicerie JP Cormier Saint-Basile G0A 3G0 2 12 6 3 2

83292848 Aliments J. Plamondon Saint-Basile G0A 3G0 12 2 2

145235 Marché Richelieu Saint-Basile G0A 3G0 11 2

83292024 Épicerie Strasbourg Saint-Basile G0A 3G0 1 4 1 2

126

Route 4 : Secteur St-Joseph-de-Beauce


142175

Alimentation Nadeau & Vallée inc. (Marché) Saint-Elzéar G0S 2J0 6 2

103659 Epicerie Centre Matic inc. (IGA)

Saint-Lambert-de-Lauzon G0S 2W0 6 1

442674 Épicerie Guy Berthiaume inc. Scott G0S 3G0 33 2

442465 Super Soir Sainte-Marie G6E 1M9 6 2

148390 Métro Labonté inc. Sainte-Marie G6E 1N7 8 10 1

152620 Alimentation Saint-Joseph-de-Beauce

Saint-Joseph-de-Beauce G0S 2V0 9 2

444540 IGA Co-op Saint-Joseph-de-

Beauce G0S 2V0 12 1

433735 Accommodation Jacques enr.

Saint-Joseph-de-Beauce G0S 2V0 6 3

176783 Dépanneur Servis Express

Saint-Joseph-de-Beauce G0S 2V0 6 8 1 3

172415 Roy Denis Tring-Jonction G0N 1X0 1 5 3

145712 Lessard J T & Fils Tring-Jonction G0N 1X0 40 3 842752

46 Dépanneur Mymi Sainte-Clotilde-de-

Beauce G0N 1C0 24 1 3 842742

88 René Composite Sainte-Clotilde-de-

Beauce G0N 1C0 15 4 440472 Gas Bar Drouin East Broughton G0N 1G0 2 4

141100

Alimentation Lachance & Roy enr. Vallée-Jonction G0S 3J0 6 3

127

Route 5 : Secteur Saint-Nicolas, Charny et St-Jean-Chrysostome


88360598 Dépanneur 610 enr.

Saint-Etienne-de-

Lauzon G6J 1H2 6 1 3

88314427 Tabagie le Faubourg enr.

Saint-Rédempteur G6K 1J4 6 8 4

199146 Couche-Tard Saint-Nicolas G7A 1N3 3 2148450 Métro Morneau Saint-Nicolas G7A 2N9 16 1

190479 Supermarché R.Martin (IGA) Saint-Nicolas G7A 3S8 6 1

88316556 Dépanneur le p'tit creux Saint-Nicolas G7A 2M9 1 6 6 1 3

437934 Accommodation de l'Erablière Saint-Nicolas G7A 2J6 6 3

88812401 9008-0474 Québec inc. (Petro-Canada)

Saint-Apollinaire G0S 2E0 6 8 3

196316 Marché I.G.A St-Apollinaire

Saint-Apollinaire G0S 2E0 5 1

88883924 Dépanneur Super Soir St-Agapit G0S 1Z0 6 3

178134 Alimentation Adrien Bisson Dosquet G0S 1H0 30 2 5 2

87282926 Épicerie Denise Tanguay Saint-Flavien G0S 2M0 6 2

148770 Supermarché Laroche inc.

Laurier-Station G0S 1N0 3 1

442320 Dépanneur Couche-Tard

Saint-Apollinaire G0S 2E0 2 2

199091 Couche-Tard acc. Des Chutes Charny G6X 1B7 10 2

152941 Epicerie Dumont Charny G6X 2T6 12 3 1 3147967 Dépanneur Sertard Charny G6X 2G6 18 2

88322925 Promutuel Lévisienne-Orléans Charny G6X 1X7 3 4

125571 Dépan-Escompte Couche-Tard #525 Charny G6X 1X6 5 2

145220 Dépanneur Piermont enr.

Saint-Jean-Chrysostome G6Z 2E8 2 3

199108 Couche-Tard Saint-Jean-

Chrysostome G6Z 3G8 5 2

88391705 Dépanneur Mari-Pier enr.

Saint-Jean-Chrysostome G6Z 2A4 6 3

435751 Accommodation Vanier enr.

Saint-Jean-Chrysostome G6Z 1Z9 6 3

445071 Dépanneur Escompte Couche Tard (Irving)

Saint-Jean-Chrysostome G6Z 2C1 2 2

128

Route 6 : Secteur Montmagny

#client Nom Ville Code Postal 18 l 2 l Can Chubby


131072 Marché Saint-Raphaël enr. Saint-Raphaël G0R 4C0 22 2 2

132952 Alimentation Côté & Morin inc.

Saint-Lazare-De-Bellechasse G0R 3J0 11 1 2

87892972 Epicerie Boucherie Labrecque

Saint-Damien-de-Buckland G0R 2Y0 8 4

146735 Bissonnette Ernest Saint-Damien-de-Buckland G0R 2Y0 10 1 3

202219 Boucherie Pierre Picard Saint-Philémon G0R 4A0 8 4 195462 Servis plus Andre Roy Saint-Philémon G0R 4A0 6 6 1 3 439794 Marché Côté enr. Armagh G0R 1A0 22 2

82432022 Gestion Pat Saint-Raphaël G0R 4C0 6 3 131068 R Campagna inc. La Durantaye G0R 1W0 11 6 3 442693 Alimentation Berthier Berthier-sur-Mer G0R 1E0 6 7 1 2 131471 Alimentation Léon Collin Montmagny G5V 1Y1 8 2

82481588 Marché Morency inc. Montmagny G5V 1E1 2 3 2 201443 Epicerie Léopold Fortin inc. Montmagny G5V 3N9 6 2

443100 Dépanneur Escompte Couche Tard Irving Montmagny G5V 1B7 3 2

82481230 IGA Co-op Montmagny G5V 3A4 10 1

174427 Dépanneur Ultra Saint-François enr

Saint-François-Montmagny G0R 3A0 6 3 3

138690 Épicerie Boucherie Marquis La Durantaye G0R 1W0 11 4

129

Route 7 : Secteur Plessisville


87282227 Épicerie A. Bergeron Saint-Janvier-de-Joly G0S 1M0 6 2

87443323 Dépanneur Johanne Laroche enr. Val-Alain G0S 3H0 12 1 3

93854799 Dépanneur Villeroy enr. Villeroy G0S 1T0 2 3 3

440468 Dépanneur M.B.

Sainte-Françoise-de-Lotbinière G0S 2N0 12 3

92632818 Dépanneur Roger Deschênes

Sainte-Cécile-de-Lévrard G0X 2M0 12 8 3

149979 Morasse Michel Sainte-Sophie-de-Lévrard G0X 3C0 11 2 3

173311 Marché Raymond Minot Manseau G0X 1V0 40 2 2

93562353 ADG Tanguay Manseau G0X 1V0 12 8 1 4

93854236 Dépanneur de Lourde Lourdes G0S 1T0 12 3

102904 IGA Coop Plessisville Plessisville G6L 3J1 6 1

93627298 Épicerie Boucherie Thibault Plessisville G6L 2E3 6 8 2

145556 Alimentation M R enr. Plessisville G6L 1K6 12 1 3

93626766 Dépanneur l'Oriental Plessisville G6L 2N8 6 3

451366 Dépanneur Bécancour enr. Lyster G0S 1V0 6 1 2 3

155510 Marché A H Fournier inc. (Provigo) Lyster G0S 1V0 6 3

130

Route 8 : Secteur Portneuf


82864950 Pro-Métal Plus Deschambault G0A 1S0 12 4

82863655 Camping Portneuf enr. Portneuf G0A 2Y0 4 4

82864881 Industries Portneuf Portneuf G0A 2Y0 23 4

137401 Dépanneur Club Vidéo Portneuf Portneuf G0A 2Y0 12 1 4

82851717 Accommodation Cap-Santé Cap-Santé G0A 1L0 6 4 3

144932 Dépanneur Shell Cap-Santé Cap-Santé G0A 1L0 12 3

82853220 Auto Franck et Michel Donnacona G0A 1T0 2 4

82852171 Accommodation rayon de soleil Donnacona G0A 1T0 6 1 1 3

82850375 Dépanneur l'Imprévu enr. Donnacona G0A 1T0 18 2 2 3

88762396 Gaz Bar S B L Neuville G0A 2R0 6 4

88762733 Accommodation Goguen Neuville G0A 2R0 2 2 3

437286 Épicerie Chez Nicole

Notre-Dame-de-Montauban G0X 1W0 22 2

151363 Épicerie Denis Filteau Ltée Saint-Ubalde G0A 4L0 3 2

82683598 Dépanneur Patrice Perreault

Saint-Marc-des-Carrières G0A 4B0 12 3

131170 Magasin Paré enr. Deschambault G0A 1S0 1 3

131

Route 9 : Secteur Saint-Anselme


88351479 Promutuel Lévisienne-Orléans Pintendre G6C 1C9 2 4

141133 Marché L Fournier inc.

Sainte-Hénédine G0S 2R0 22 3 3

86252921 Dépanneur Chez Ben Lac-Etchemin G0R 1S0 4 3

174412 Duquet Guy Sainte-Claire G0R 2V0 11 8 1 3

88833988 Alimentation Carrier inc. Sainte-Claire G0R 2V0 3 6 2

86422814 Epicerie Luno enr. Saint-Malachie G0R 3N0 6 2 2 3

148688

Marché Métro (Ofrigidaire Alimentation) Lac-Etchemin G0R 1S0 4 1

88854031 Dépanneur Express Saint-Anselme G0R 2N0 6 3

131355 Dépanneur Etchemin Saint-Anselme G0R 2N0 11 8 1 3

103211 Co-Op Magasin (IGA) Saint-Anselme G0R 2N0 6 1

438465 Dépanneur Super-Soir enr. Saint-Anselme G0R 2N0 6 8 1 2 2 3

431037 Jean-Guy Fontaine inter-marché Pintendre G6C 1C8 6 10 1

132

Route 10 : Secteur Thetford Mines


142160 S C A la Seigneurie Saint-Narcisse-de-Beaurivage G0S 1W0 6 4

85962809 Accommodation Cybel Air

Saint-Patrice-de-Beaurivage G0S 1B0 6 1 3

85962353 Marché Beaurivage Saint-Patrice-de-Beaurivage G0S 1B0 6 2

436468 Alimentation Chez Yves enr. Pontbriand G0N 1K0 6 2

443074 IGA #407 Thetford Mines G6G 6H1 18 1

84235727 Alimentation Denis inc. Black Lake G6H 2B4 6 1 2

125888 Dépan-Escompte Couche-Tard Black Lake G6H 2A3 7 2

126406 Dépanneur Couche Tard Thetford Mines G6G 6X9 9 2

439513 Dépanneur Chez Pee-Wee inc. Thetford Mines G6G 1Z2 6 2 1 3

183220 Jean Coutu #160 Thetford Mines G6G 2A8 6 4

83356353 Accommodation Chez Guy enr. Thetford Mines G6G 2W2 6 3

441880 Placement G.R. Gilbert Thetford Mines G6G 1J6 12 8 4

83380844 Boucherie Ré-Jo inc. Robertsonville G0N 1L0 12 4

149263 Alfred Couture ltée Saint-Léon-de-Standon G0R 4L0 7 3 3

133

ANNEXE B : Guide d’utilisation MapPoint 1. Introduction à MapPoint Le logiciel de cartographie MapPoint est utilisé pour calculer les distances entre

différents endroits à travers l’Amérique du Nord. De plus, il permet de calculer le temps

de route et le coût de transport en tenant compte des limites de vitesse et du coût du

carburant. Par ailleurs, il détermine la route à suivre avec des indications précisant les

routes et autoroutes à emprunter pour se rendre à destination. Ce logiciel est très utile

pour la gestion d’une entreprise ayant à effectuer des cueillettes et livraisons. MapPoint

comporte une multitude d’outils permettant de visualiser une route à parcourir d’une

façon extrêmement précise. Un des intérêt de MapPoint est qu’il est possible de l’appeler

à partir d’une application développée en Visual Basic. Ce guide présente comment

effectuer la connexion entre Visual Basic et MapPoint et présente les principales

fonctions.

1.1. Configuration Ce guide d’utilisation vous permettra d’accéder à MapPoint à partir de Visual Basic pour

trouver des informations réelles sur la route à suivre entre différentes destinations. Par

contre, il est tout d’abord nécessaire de configurer la connection à MapPoint dans Visual

Basic. Cela permettra à Visual Basic de se lier à MapPoint et reconnaître le code y faisant

134

référence. Pour ce faire, il faut tout d’abord ajouter MapPoint dans les références de

Visual Basic. Ainsi, l’ajout d’une référence peut être effectué en ouvrant le menu

déroulant « Project » et en choisissant l’option « Références ». La boîte de dialogue

suivante apparaîtra à l’écran :

Il suffit alors d’activer la case à cocher correspondant à la référence « Microsoft

MapPoint 8.0 Object Library » avant de refermer la boîte de dialogue en cliquant sur le

bouton OK. Cette procédure permettra à Visual Basic de reconnaître l’existence de

MapPoint lorsque vous lui ferez appel par la suite.

2. Les objets de MapPoint Avant de commencer, il est essentiel de bien comprendre les objets qui seront nécessaires

pour récupérer les données utiles à votre projet. MapPoint comprend des variables

permettant d’activer l’application MapPoint, d’ouvrir une carte et finalement de localiser

certains points sur la carte.

135

2.1. Variable d’appel et d’activation de MapPoint Tout d’abord, vous devez déclarer une variable qui fera appel à MapPoint. Cette variable

aura pour tâche de faire le lien entre MapPoint et Visual Basic. Elle permettra d’activer le

lien entre les deux logiciels. De plus, elle permettra de pouvoir éventuellement ouvrir une

carte, calculer une route et quitter l’application. Dans l’exemple suivant la variable

objapp permettra de faire ce lien. Pour déclarer cette variable, on doit utiliser un code

semblable à celui-ci :

Dim objApp as New mapPoint.Application

2.1.1. Activer l’application Avant de débuter un projet, vous devez absolument activer l’application. Pour ce faire,

vous pouvez suivre l’exemple suivant :

objApp.Activate

2.1.2. Quitter l’application De la même façon, lorsque vous désirerez quitter l’application, vous devrez alors

inscrire le code suivant permettant ainsi de désactiver l’application :

ObjApp.quit

2.2. Variable déclarant une carte Ensuite, vous devez déclarer une variable faisant référence à une carte dans MapPoint.

Ainsi, Visual Basic saura que la carte doit être ouverte dans MapPoint. Il est à noter que

MapPoint a seulement une carte ouverte à la fois. Il n’est pas possible d’ouvrir deux

136

cartes. L’objet Map permettra d’accéder aux méthodes find, findaddress et getlocation

permettant de situer un endroit sur la carte et ensuite de les ajouter à une route :

Dim objMap as New mapPoint.Map

2.3. Variable de localisation L’objet de localisation permet d’accéder au résultat d’une requête recherchant une

localisation. Cette localisation peut être repérée en déterminant un endroit, une adresse ou

des coordonnées de longitude et latitude. Par contre, pour utiliser cet objet il est

nécessaire d’avoir préalablement activé une carte. Le nombre de points maximal à situer

sur la carte est indiqué entre les parenthèses. Dans l’exemple suivant, le nombre de points

à situer sur la carte sera dans l’intervalle de un à cinq :

Dim objloc(1 To 5) As mappoint.Location

3. Situer deux points sur une carte

3.1. Déclaration des variables Tout d’abord, vous devez situer les deux points sur la carte. Pour ce faire, vous devez

vous connecter à MapPoint comme décrit précédemment. Ensuite, vous devez déclarer

une variable permettant d’ouvrir une carte et l’activer comme suit :

Dim objMap As mappoint.Map Set objMap = objapp.ActiveMap

137

3.2. Méthodes de localisation Find, Findaddress et Get location Il existe 3 façons différentes permettant de situer les points désirés sur une carte. Il y a la

méthode find, findaddress, et getlocation. Les trois méthodes ont le même

fonctionnement mais avec des données de départ différentes.

La méthode find utilise un nom endroit dans son contexte. Par exemple, vous pourriez

utiliser "Seattle, WA, United States" ou "G8M 3Y4 " pour indiquer l’endroit désiré. Les

indications doivent être précises sinon le résultat reçu sera « nothing » indiquant qu’il a

trouvé plusieurs ou aucun endroit portant les indications données précédemment. Cette

dernière méthode est aussi utile si vous désirez trouver un endroit à l’aide seulement du

code postal.

La méthode findaddress utilise l’adresse complète pour situer un endroit précis. Vous

pouvez alors inscrire dans l’ordre le nom de la rue (précédé du numéro civique si désiré),

la ville, la province, le code postal et finalement le nom du pays ( geocountryCanada ou

geocountryUnitedStates). Par contre la seule indication qui est obligatoire est le nom de

la rue, les autres sont optionnelles.

La méthode getlocation utilise la latitude, la longitude et l’altitude d’un endroit. La

latitude est une coordonnée numérique indiquant à quelle distance de l’équateur se situe

l’endroit désiré. On indique le nord avec le signe « + » et le sud par « - ». Quant à la

longitude, elle indique la distance par rapport au méridien. De la même manière, l’est est

désigné par « + » et l’ouest par « - ». L’altitude est optionnelle, si vous ne connaissez pas

l’altitude vous pouvez donc ne rien inscrire ou inscrire le nombre 100. Par exemple, vous

pouvez trouver Los Angeles avec (47.75399, -121.97436, 100).

La marche à suivre pour les trois méthodes est presque identique. Pour situer deux points

sur une carte, il est nécessaire de définir une variable de localisation. On inscrit le nombre

maximal de points que l’on veut situer entre parenthèses.

138

Dim objloc(1 To 2) As mappoint.Location Ensuite on peut situer les deux endroits désirés. C’est à cet endroit qu’on apercevra une

petite différence entre les méthodes utilisées. Effectivement, vous devrez inscrire la

méthode que vous désirez utiliser et décrire l’endroit selon les indications décrites

précédemment. Dans cet exemple, nous avons utilisé la méthode find. Voici toutes les

écritures nécessaires pour situer les points sur la carte.

Dim objapp As New mappoint.Application

Dim objMap As mappoint.Map Dim objloc(1 To 2) As mappoint.Location

Set objapp = New mappoint.Application

'Activer l'application objapp.Activate

'Activer une carte Set objMap = objapp.ActiveMap

'Situer les points sur la carte With objapp.ActiveMap

Set objloc(1) = objMap.Find("Seattle, WA, United States")

Set objloc(2) = objMap.Find("Université Laval, Québec,Canada")

End With

4. Le calcul des paramètres de la route

4.1. Ajouter les points à la route Par la suite, vous devez ajouter ces points à la route. Ainsi, vous devez activer une carte

et une route pour placer ces points sur celle-ci. Les écritures suivantes présentent l’ajout à

139

faire aux écritures permettant de situer les points sur la carte. Les noms de Seattle et

Université Laval sont optionnels, ils permettent d’indexer les points.

With objapp.ActiveMap.ActiveRoute .Waypoints.Add objloc(1), "Seattle"

.Waypoints.Add objloc(2), "Université Laval" End With

4.2. Trouver la route Par la suite, vous devez trouver la route entre ces deux points. Cette fonction sera remplie

par la propriété calculate. Cette dernière fonction est utilisée de la même façon que

l’ajout des points c’est-à-dire en activant une route et une carte. Elle tracera la route entre

les deux points inscrits à la route :

Objapp.activemap.activeroute.calculate

4.3. Trouver la distance, le temps de route ou le coût entre deux points Finalement, on peut maintenant trouver la distance, le temps de route ou le coût entre ces

points. La distance est récupérée à l’aide de la propriété distance, le temps de route avec

la propriété driving time et le coût avec la propriété cost. Ces données seront lues

seulement en double, il faut donc tenir compte de cette particularité en définissant nos

variables permettant de récupérer la distance, le coût ou le temps de conduite. La distance

est donnée en GeoUnits et est souvent établie par défaut en miles. Il faut donc ajuster ce

paramètre si l’on désire obtenir une distance en kilomètres. Par ailleurs, il est à noter que

le temps de route écoulé est donné en jour. Par exemple, une heure sera égale à 1/24

c’est-à-dire 0,041666. Dans l’exemple suivant, le message box a été utilisé pour

récupérer la distance à parcourir en kilomètres.

140

Dim objapp As New mappoint.Application Dim objMap As mappoint.Map Dim objloc(1 To 50) As mappoint.Location Dim objRoute As mappoint.Route Dim tweight As Double Dim dblDistance As Double 'Activer l'application objapp.Activate 'Activer une carte Set objMap = objapp.ActiveMap ‘Trouver les distances en kilomètres If objapp.Units=geoMiles Then Objapp.Units=geoKm End if 'Situer les points sur la carte With objapp.ActiveMap Set objloc(1) = objMap.Find("Seattle, WA, United States") Set objloc(2) = objMap.Find("Université Laval,Québec,Canada") End With 'Ajouter l'endroit à la route With objapp.ActiveMap.ActiveRoute .Waypoints.Add objloc(1), "Seattle" .Waypoints.Add objloc(2), "Université Laval" 'Calculer la route .Calculate End With

'Récupérer la distance tweight = objapp.ActiveMap.ActiveRoute.Distance x = MsgBox(tweight, , "Distance")

4.4. Calculer la distance entre deux points sur la route Il n’est pas obligatoire de calculer la distance de la route complète si on a plus de deux

points. On pourrait indiquer le point de départ et le point d’arrivée entre parenthèse

comme ceci :

141

MsgBox objMap.Distance(objLoc(1), objLoc(2))

4.5. Effacer une route ou des points La méthode clear est très utile puisqu’elle permet de supprimer une route ou des points

sur une route. Il est souvent essentiel de trouver plusieurs routes, la méthode clear permet

de supprimer la route précédente et ainsi s’assurer que nos points sont situés sur une

nouvelle route.

Dim objApp As New MapPoint.Application Dim objRoute As MapPoint.Route Set objRoute = objApp.OpenMap("Deliveries.ptm").ActiveRoute objRoute.Clear

4.6. Calculer plusieurs distances entre différents points Il est maintenant possible de calculer toutes les distances entre chacun des points de la

route. Dans l’exemple suivant, il s’agit d’une partie du code. Nous avons précédemment

définit nos variables et localisé chacun des points. Nous avons définit tweightclient

comme un vecteur permettant de récupérer la distance entre les points i et j. Nous

commençons par ajouter chacun des points désirés c’est-à-dire les points i et j. Ensuite,

nous calculons la route et gardons en mémoire la distance dans le vecteur

« tweightclient ». Par la suite, nous effaçons cette route de façon à pouvoir en calculer

une nouvelle à chacune des itérations.

With objapp.ActiveMap.ActiveRoute For i = 1 To nbclients - 1 For j = i + 1 To nbclients .Waypoints.Add objloc(i) .Waypoints.Add objloc(j) 'permet de calculer la route

142

.Calculate

‘permet de calculer la distance et la garder en mémoire dans un array tweightclient représentant la distance entre les points i et j

tweightclient(i, j) = objapp.ActiveMap.ActiveRoute.Distance ‘permet d’effacer la route .Clear Next j Next i End With

4.7. Enregistrer une carte Par défaut, lorsque vous activez une carte pour y trouver un ou plusieurs points, la boîte

de dialogue suivante apparaîtra à l’écran vous demandant si vous désirez ou non

enregistrer les modifications apportées à la carte.

En répondant « yes », vous pourrez alors enregistrer à l’endroit désirer la carte. Par

contre, si vous ne désirez pas voir apparaître cette boîte de dialogue, vous pouvez

enregistrer la carte directement dans votre code en utilisant la propriété saveas :

objmap.SaveAs "test", geoFormatMap, True

Par contre, si vous ne désirez pas sauvegarder la nouvelle carte, vous pouvez simplement

utiliser la propriété saved qui permettra de quitter l’application sans enregistrer les

changements effectués à la carte :

143

Objmap.saved = true

5. Visualiser une route sur une carte MapPoint Tout d’abord, la visualisation d’une carte peut être effectué seulement à partir de l’édition

2002 de MapPoint car cette version du logiciel inclus un nouveau contrôle ActiveX (plus

communément nommé « MapPoint Control »). Ce contrôle permet d’intégrer dans votre

projet Visual Basic une carte MapPoint. Cette carte pourra contenir toutes les

fonctionnalités qu’il est possible de retrouver habituellement lors de l’utilisation de

MapPoint.

5.1. L’objet MapPoint Control Premièrement, vous devez avoir préalablement configurer MapPoint dans Visual Basic

comme décrit au point 1.1. Ensuite, vous devez ajouter l’objet MapPoint Control dans

votre boîte à outils. Pour cela cliquez avec le bouton droit de la souris dans la boîte à

outils, sélectionnez la commande Components dans le menu contextuel, allez sur l’onglet

Controls, puis activez la case à cocher correspondant à l’entrée Microsoft MapPoint

Control 9.0. Vous pouvez maintenant refermer la boîte de dialogue en cliquant sur le

bouton OK.

144

L’objet MappointControl devient alors disponible dans votre boîte à outils. Vous pouvez

alors sélectionner ce dernier et ajuster les dimensions selon lesquels vous désirez faire

apparaître votre carte dans votre formulaire. Vous devriez alors voir apparaître une image

comme la suivante. Évidemment, en mode création, l’objet MappointControl est

représenté par un carré blanc avec au milieu de ce dernier l’icône MapPoint. Dans la

figure suivante, il est possible de voir que l’objet MapPoint Control a bien été ajouté à la

boîte à outils puisqu’on y retrouve l’icône de MapPoint. De plus, l’utilisateur a créé son

formulaire sur lequel la carte apparaîtra selon les dimensions désirées.

145

.

5.2. Coder avec MapPointControl

Une fois que l’objet MappointControl se trouve sur votre formulaire vous pouvez

commencer à coder avec celui-ci. La première chose à faire est de coder le type de carte

vous voulez faire apparaître c’est-à-dire probablement la carte nord-américaine.

Set objMap = Mappointcontrol1.NewMap(geoMapNorthAmerica)

L’objet MapPointControl permet de nombreuses possibilités, ainsi vous pouvez

déterminer l’image exacte que vous désirez obtenir à l’écran. Par exemple, vous pouvez

sélectionner les barres d’outils que vous désirez voir apparaître. MapPoint possède quatre

barres d’outils: Dessin, Location et échelle de distance, Navigation, et Standard. De plus,

il est possible d’effectuer un zoom sur votre carte de manière à ce que celle-ci soit plus

grande lors de son ouverture. Il faut aussi déterminer le style de carte vous désirez

obtenir, dans le cas présent le style route et données sera adopté mais il existe aussi

quatre types de style de carte : Data Map, Political map, Road map, Road et data map, et

146

finalement terrain map. Voici donc un exemple d’écritures possibles faisant apparaître

une carte. À noter que dans cet exemple le mappointControl a été appelé MPC.

Private Sub Form_Load() Dim DistanceMapPoint As Double Dim objMap As MapPointCtl.Map Dim objloc(1 To 4) As MapPointCtl.Location ‘utiliser la carte nord-américaine Set objMap = MPC.NewMap(geoMapNorthAmerica) Set objMap = MPC.ActiveMap ‘Permet de quitter la procedure si la carte ne contient rien If objMap Is Nothing Then

Exit Sub End If

'Zoom sur la carte objMap.ZoomIn

‘Déterminer le sytle désiré objMap.MapStyle = geoMapStyleRoadData

‘Déterminer les barres d’outils voulus MPC.Toolbars(1).Visible = True MPC.Toolbars(2).Visible = True With objMap

Set objloc(1) = .GetLocation(38.258384, -85.47502099, 100) Set objloc(2) = .GetLocation(22.258384, -85.47502099, 100) Set objloc(3) = .FindResults("G1k7p4").Item(1) Set objloc(4) = .FindResults("G1k1p5").Item(1)

End With With objMap.ActiveRoute

.Waypoints.Add objloc(1)




'Calculer la route .Calculate

End With

147

'Récupérer la distance DistanceMapPoint = objMap.ActiveRoute.Distance End Sub

Ce guide d’utilisation ne contient pas une liste exhaustive de toutes les fonctionnalités

offertes par MapPoint. Pour plus d’informations, consultez l’aide de MapPoint situé dans

la barre d’outil principale du logiciel.

148

ANNEXE C : Article ASAC Congrès ASAC 2004 Julie Privé Québec, QUÉBEC Jacques Renaud Fayez F. Boctor Centre de recherche sur les technologies de l’organisation réseau (CENTOR) Université Laval ÉLABORATION D’UN SYSTÈME INTÉGRÉ DE PLANIFICATIONS DE TOURNÉES :

UNE APPLICATION DANS LE SECTEUR DE LA DISTRIBUTION 1

Cet article étudie un problème de tournées présent dans une entreprise de distributions de boissons de la région de Québec. Nos résultats démontrent que l’application de l’approche proposée permet d’améliorer les opérations de transport de l’entreprise.

Introduction

Les opérations de transport sont essentielles au bon fonctionnement de notre économie de marché. Effectivement, selon Statistiques Canada, les entreprises de transport routier emploient plus de 200 000 personnes et génèrent des revenus annuels de plus de 36,9 milliards. Le transport routier des marchandises permet l’acheminement des matières et des produits entre les entreprises et vers les consommateurs. Étant donné l’étendue géographique du Canada, le transport routier des marchandises joue un rôle économique primordial. Selon Statistiques Canada, l’infrastructure routière compte plus de 900 000 kilomètres d’autoroutes et de routes pour supporter l’industrie du camionnage. Le nombre de camions sur les routes augmente d’années en années et les coûts du carburant augmentent sans cesse constituant une part importante des frais d’opérations d’un transporteur. Par conséquent, la rentabilité d’une entreprise de distribution est grandement affectée par les décisions relatives aux tournées de livraison. La planification des tournées est donc un problème majeur pour les entreprises de transport. Étant donné les conséquences économiques et stratégiques des problèmes de transport, ces derniers ont attiré l’attention de nombreux chercheurs et ce, depuis plusieurs années.

Dans ce qui suit, nous proposons un système intégré de planification de tournées et l’appliquons chez Distributions Jacques Dubois inc; une entreprise de distributions de boissons située dans la région de Québec. La suite de cet article est organisée comme suit. Tout d’abord, nous présentons l’entreprise étudiée puis révisons les principaux problèmes de tournées étudiés dans la littérature. La section suivante aborde les approches de résolution développées. Finalement, l’évaluation de l’approche proposée est effectuée à partir des résultats obtenus sur un problème réel rencontré 1 Nous tenons à remercier Jacques Dubois et Mehdi Aouididi pour leur précieuse collaboration ainsi que pour avoir voulu nous fournir les données nécessaires à cette étude.

149

Présentation de l’entreprise

Distributions Jacques Dubois inc. est une entreprise de distribution de boissons non alcoolisés située dans la région de Québec. L’entreprise doit livrer à des clients qui commandent des quantités connues à l’avance et les véhicules de livraison sont limités par leur capacité en terme de poids et d’espace. De plus, plusieurs clients ont une fenêtre de temps à l’intérieur de laquelle ils désirent être visités. La flotte de véhicules de l’entreprise est constituée de camions de capacités distinctes. L’entreprise distribue plusieurs produits qui sont différents les uns des autres, ces derniers ont un poids et occupent un espace différent qui devra être pris en considération. Finalement, l’entreprise doit aussi récupérer chez ses clients les bouteilles et cannettes vides. Il s’agit donc d’un problème de tournées de véhicules hétérogènes avec fenêtres de temps où on livre plusieurs produits.

Mathématiquement, le problème étudié se décrit sur un graphe G = (V, A) où V = {v0, v1, …, vn} représente l’ensemble des sommets (dépôt et clients) et A = {(vi, vj) : vi, vj ∈ V, i ≠ j} représente l’ensemble des arcs possibles. La matrice de distances est symétrique c’est-à-dire que dij = dji. Le point v0 représente le dépôt qui est le point de départ et d’arrivée pour toutes les routes. Les points v1, …, vn représentent les n clients à desservir. La flotte est composée de K véhicules dont la capacité de chargement est Qk pour la livraison des produits et qui disposent d’un volume Vk pour la récupération. La durée maximale d’une route est dmax. La demande du client vi pour le produit j est qij (i = 1, …, n et j = 1, …, P). Chaque client possède une quantité de récupération ri et requiert un temps de service si. De plus, chacun des clients a une fenêtre de temps [ei, li] qui lui est associée où ei représente le temps au plus tôt et li le temps au plus tard pour effectuer la visite.

Le problème consiste donc à visiter tous les clients une et une seule fois afin de leur livrer la marchandise commandée et rapporter la récupération tout en respectant les contraintes de fenêtres de temps, de capacité exprimé en volume et poids. L’objectif est de minimiser la distance parcourue pour visiter tous les clients. Revue de la littérature

Le problème étudié s’apparente à un problème de tournées de véhicules avec véhicules hétérogènes qui a été adapté de manière à prendre en compte les fenêtres de temps, les besoins en capacité des différents produits et de la récupération. Le problème classique de tournées de véhicules (vehicle routing problem) est un problème qui a fait l’objet de nombreuses recherches, il traite le cas où chacun des clients a une demande déterminée et où la flotte est homogène. Taillard (1993) a apporté une grande contribution à ce problème par son heuristique de partitionnement. Au cours des dernières années, la méthode de recherche tabou a été appliquée au problème de tournées par plusieurs auteurs. Ainsi, des auteurs tels que Osman (1993), Gendreau et al. (1994), Rego et Roucairol (1996) et Xu et Kelly (1996) se sont inspirés du la méthode tabou pour développer des approches de résolutions efficaces. Par ailleurs, Prins (2001) obtient des résultats très intéressant en utilisant l’algorithme génétique.

On observe ces dernières années une recrudescence de la recherche sur le problème de tournées de véhicules avec fenêtres de temps. Les auteurs suivants ont contribué à la résolution de ce problème : Rochat et Taillard (1995), Taillard et al. (1997), Cordeau, Laporte, Mercier (2000), Rousseau, Gendreau et Pesant (2000), Li et Lim (2003) et Berger et Berkaoui (2003). En

150

ce qui concerne la contrainte de flotte hétérogène elle a été étudiée récemment par Renaud et Boctor (2002).

L’amélioration individuelle des routes se fait à l’aide des méthodes d’amélioration conçues pour le problème du voyageur de commerce (traveling salesman problem ). Ce problème a été largement étudié. Parmi les méthodes d’amélioration les plus efficaces disponibles actuellement notons celui de Helsgaun (2000).

Un très grand nombre d’applications pratiques sont rapportées dans la littérature. Par contre, les applications du problème de tournées à l’industrie des boissons sont très rares. Au meilleur de nos connaissances, seul Golden et Wasil (1987) ont étudié l’industrie de la boisson gazeuse, mais ces auteurs considéraient le cas où la demande des clients n’était pas connue avant la livraison.

Finalement, le lecteur intéressé par la littérature concernant les problèmes de tournées de véhicules consultera les revues de Cordeau et al. (2002), Toth et Vigo (2002), Laporte et al. (2000), Laporte et Osman (1995) de même que celles de Laporte (1992a, 1992b, 1993). Approche de résolution

La figure 1 présente l’approche développée afin de résoudre le problème. L’approche que nous proposons est composée d’une heuristique de construction suivie d’une phase d’amélioration individuelle des routes et d’une amélioration inter-route. Afin d’être le plus précis possible, les distances ont été obtenues par le logiciel MapPoint. Heuristique de construction

Pour construire les routes et déterminer les camions à utiliser l’heuristique suivante dont les principales étapes se décrivent comme suit :

1. Pour débuter, tous les clients sont considérés. L’ensemble ε est ainsi composé de tous les clients qui ont une commande à livrer. (ε = V \ {V0}).

2. Répéter l’étape 3 pour tous les véhicules k = 1…K. 3. Appliquer l’heuristique d’insertion du plus proche voisin avec le véhicule k et

conserver la première tournée trouvée notée Tk. 4. Parmi les K tournées trouvées, conserver la tournée *

kT qui maximise le critère

parcourue distanceée transportquantité . Ajuster l’ensemble des clients à visiter, ε = ε \

*kT .

5. Si ε = Ø terminer, sinon retour à l’étape 2.

Détaillons maintenant l’implantation de l’algorithme d’insertion du plus proche voisin utilisée (voir Rosenkrantz et al. 1977 pour la description originale). Partant d’un sous tour initial composé uniquement du dépôt, l’heuristique ajoute un à un des points en sélectionnant celui qui est le plus près de l’ensemble des points de la tournée. Ce point est ensuite inséré à l’endroit réalisable minimisant la distance ajoutée. Une insertion est réalisable si elle respecte les contraintes de capacité (Qk) correspondant au poids des produits, de volume (Vk) utilisé par les

151

sacs de récupération, de distance maximale (dmax) et de fenêtres de temps ([ei,li]) pour les clients. Si une contrainte n’est pas respectée, on cherche le prochain client le plus près des clients actuellement sur la route. Lorsqu’il n’y a plus de client qui respecte les contraintes, la route est terminée.

Figure 1. : Organigramme de l’approche de résolution

Heuristiques d’amélioration

L’amélioration des routes se fera à l’aide de deux heuristiques. Tout d’abord, nous effectuons une amélioration individuelle de chacune des routes suivie d’une phase d’amélioration qui échange des clients entre deux routes.

ε = V \ {v0}




Parmi les tournées trouvées, conserver la tournée *

kT qui maximise la quantité livrée/distance parcourue

ε = Ø Non

Amélioration individuelle des routes

Amélioration inter-route

FIN

Oui

152

Amélioration individuelle des routes. L’heuristique classique du 3-opt (Lin 1965) est appliquée à chacune des routes de manière à diminuer la longueur de la route. Pour chacune des routes, tous les mouvements du 3-opt sont analysés. Si un de ceux-ci permet d’améliorer la route tout en respectant l’ensemble des contraintes, celui-ci est appliqué et la route est améliorée.

Amélioration inter-route. Souvent, il est possible d’effectuer d’autres améliorations en échangeant des clients entre deux routes. L’heuristique utilisée permet d’améliorer deux routes à la fois. Après avoir sélectionné deux routes, on considère toutes les paires de points consécutifs et on teste les 11 échanges illustrés à la figure 2. Un échange est implanté s’il réduit la distance totale et que toutes les contraintes sont respectées. Notons qu’en échangeant les clients de routes, la demande des routes est affectée. L’algorithme est appliqué de façon séquentielle à toutes les paires de routes tant que des améliorations sont possibles.

Les tournées de départ




153

Échange 10 Échange 11

Figure 2 : Les échanges inter-route testées

Évaluation de l’approche proposée

L’approche proposée a été codée en Visual Basic 6.0 et est relié à une base de données Access ainsi qu’au logiciel de cartographie MapPoint afin d’obtenir les distances réelles les plus précises possible.

Nous avons utilisé les données réelles de l’entreprise Distributions Jacques Dubois inc. Comme le montre la figure 3, la majorité des clients de l’entreprise est située sur la Rive-Sud de Québec, couvrant entièrement la région Chaudières-Appalaches. Les tests ont été effectués sur 164 clients dont la demande était connue. Parmi ces clients, 19 imposaient des fenêtres temps.

Figure 3. : Localisation des clients de Distributions Jacques Dubois inc.

Les produits livrés par Distributions Jacques Dubois inc. sont des boissons de toutes

sortes. Ainsi, l’entreprise compte plus de 125 produits distincts c’est-à-dire de saveurs, de dimensions et de poids différents. Il a été possible de grouper les 125 produits en 6 produits types. Ces produits sont ceux qui sont le plus souvent commandés par les clients. Le tableau 1 présente ces produits ainsi que leur poids et le nombre d’unités de produits qu’il est possible de mettre sur une palette. Étant que le poids d’une palette (76 livres) n’est pas un facteur à négliger, il est important de savoir le nombre exact de produit qu’il est possible de charger sur cette palette. Chaque fois que l’on dépasse ce nombre, une nouvelle palette est ajoutée. Il est à noter que la plupart des articles sont livrés en caisse. Par exemple, il est impossible de commander une seule

154

bouteille de 2 litres puisque ces derniers sont livrés en caisse de huit bouteilles. Par conséquent, le tableau suivant présente les poids des produits par caisse excepté pour les bouteilles d’eau qui sont par unité.

Tableau 1 Classification et caractéristiques des produits

Nom Poids (livres) Nb par palette Eau (18 litres) 40 54 2 litres 40 50 Canettes 22 60 Chubby 21 120 600 millilitres 34 72 Eau (5 litres) 12 144 Autres 20 ---

En plus de la livraison de boissons, l’entreprise Distributions Jacques Dubois inc. doit aussi récupérer des sacs contenant les bouteilles vides. Notons que la quantité à récupérer n’est pas toujours connue à l’avance. Chez la plupart des clients, la quantité de bouteilles à récupérer est connue au moment où l’on effectue la visite. Cependant, il est possible de regrouper les clients selon la moyenne des sacs de récupération généralement recueillis. Il est évident que les plus grosses supermarchés auront plus de sacs de récupérations que les petits dépanneurs. De plus, les pharmacies, les cabanes à sucre et les campings ne recueillent généralement pas la récupération. Le tableau 2 présente les groupes des clients et le nombre de sacs généralement recueillis.

Tableau 2 Classification des clients selon le nombre de sacs de récupération

Groupe Entreprises (exemples) Nombre de sacs de

récupération 1 Supermarché, IGA, Co-op, Provigo, Sobeys 20-30 2 Couche-Tard, marché, petite épicerie 10-20 3 Dépanneur, Accommodation 0-10 4 Camping, Cabane à sucre, pharmacie 0

Bien qu’il arrive à l’occasion que Distributions Jacques Dubois inc. loue des camions pour la livraison, l’entreprise possède trois véhicules pour assurer la distribution des boissons et la cueillette de bouteilles vides. Aucun camion n’est dédié à une route en particulier, ils sont attribués aux routes selon la capacité nécessaire. Le tableau 3 présente les capacités des véhicules en terme de poids et de sacs de récupération.

155

Tableau 3 Caractéristiques des camions

Camions Longueur

(pieds) Nb essieux Poids maximum

(livres) Nb de sacs de récupération

Camion 1 16 1 6 000 100 Camion 2 20 2 8 000 120 Camion 3 26 2 16 000 220

Résultats obtenus

L’approche proposée a été évaluée à partir de données réelles de deux semaines typiques. À des fins de comparaisons, les routes de l’entreprise ont été compilées et les distances évaluées par le logiciel MapPoint. Dans un premier temps, le tableau 4 présente les routes tels que planifiées par Distributions Jacques Dubois inc. Pour construire ces routes, l’entreprise regroupent généralement tous les clients d’un même secteur et décide ensuite du camion en fonction de la demande et finalement de la tournée.

Tableau 4 Routes planifiées par Distributions Jacques Dubois inc.

Nombre de

routes Distance

(Km) Durée (min.)

Nombre de clients Chargement Récupération Camion

1 64,2 297 23 7 170 179 8 000 2 230 350 17 8 252 170 16 000 3 299,5 362 12 7 472 137 16 000 4 287,9 366 15 7 196 149 8 000 5 170,7 388 24 7 428 244 16 000 6 239,8 369 17 6 682 138 8 000 7 293,5 385 14 4 211 100 6 000 8 279,5 369 15 7 472 108 16 000 9 310,6 382 15 6 198 57 8 000

10 263,6 329 12 4 676 121 6 000 Total 2 439,3 3 597 164 66 757 1403

Moyenne 243,93 359,7 16,4 6 675,7 140,3

Les résultats obtenus permettent d’améliorer la distance parcourue par l’ensemble des véhicules. Le tableau 5 présente les résultats obtenus par l’approche développée. Ces résultats démontrent une amélioration significative. Tout d’abord, une route a été éliminée ce qui permet entre autres de réduire le nombre de camionneurs requis. De plus, la distance totale a été réduite de 12,83% passant de 2 439 à 2 126 kilomètres.

156

Tableau 5 Routes améliorées

Nombre de

routes Distance

(Km) Durée (min.)

Nombre de clients Chargement Récupération Camion

1 42 242 20 5 886 156 16 000 2 222 452 23 7 648 230 16 000 3 221 441 22 8 794 175 16 000 4 254 444 19 8 356 156 16 000 5 300 470 17 7 246 144 8 000 6 246 466 22 10 508 138 16 000 7 253 453 20 8 615 225 16 000 8 289 399 11 5 038 143 6 000 9 299 399 10 4 398 103 6 000

Total 2 126 3 766 164 66 489 1 470 Moyenne 236,22 418,44 18,22 7387,67 163,33

Les commandes étant les mêmes, nous pouvons conclure que le chargement est mieux

distribué. Effectivement, le poids total (66 489) est moindre avec l’approche proposée. Ceci s’explique par le fait que le nombre de palettes nécessaires est réduit. En plus de réduire le poids total pour livrer les commandes aux clients, ces nouvelles routes permettent aussi de recueillir une plus grande quantité de sacs de récupération. Conclusion

L’approche proposée permet d’améliorer considérablement les routes généralement utilisées par l’entreprise. Sur une base annuelle, cela se traduirait par des économies considérables pour l’entreprise et permettrait entres autres d’augmenter l’efficacité de ses opérations. Références Berger J. & Barkaoui M., “A parallel hybrid genetic algorithm for the vehicle routing problem with time windows”, Computer & Operations Research (2003), À paraître. Cordeau J., Laporte G. & Mercier A., “A unified tabu search heuristic for vehicle routing problems with time windows”, Technical report CRT-00-03 (2000), Centre de recherche sur les transport, Montréal, Canada. Cordeau J.-F., Gendreau M., Laporte G., Potvin J.-Y. & Semet F., “A guide to vehicle routing heuristics”, Journal of the Operational Research Society, (2002), 53: 512-522. Gendreau M., Hertz A. & Laporte G., “A tabu search heuristic for the vehicle routing problem”, Management Science (1994), 40: 1276-1290. Golden L. B. & Wasil A. E., “Computerized vehicle routing in the soft drink industry”, Operation Research (1987), 35, 1: 6-17.

157

Helsgaun K., “An effective implementation of the Lin-Kernighan traveling salesman heuristic”, European Journal of Operational Research (2000), 126 , 1: 106.

Laporte E G., “The traveling salesman problem: An overview of exact and approximate algorithms”, European Journal of Operational Research (1992), 59: 231-247. Laporte G., “The vehicle routing problem: An overview of exact and approximate algorithms”, European Journal of Operational Research (1992), 59 : 345-358. Laporte G., “Recent algorithmic Developments for the traveling salesman problem and the vehicle routing problem”, Ricerca Operativa (1993), 23, 68: 5-27. Laporte G. & Osman I. H., “Routing Problems : A Bibliography”, Annals of Operations Research (1995), 61: 227-262. Laporte G., Gendreau M., Potvin J.-Y. & Semet F., “Classical and modern heuristics for the vehicle routing problem”,International Transactions in Operational Research (2000); 7: 285-300. Li H. & Lim A., “Local search with annealing-like restarts to solve VRPTW”, European Journal of Operational Research (2003). À paraître. Lin S., “Computer solutions of the traveling salesman problem”, The Bell System Technical Journal (1965): 2245-2269. Osman I. H., “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem”, Annals of Operations Research (1993), 41: 421-451. Prins C., “A simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem”, Research report (2001). University of Technology of Troyes. Rego C. & Roucairol C., “ A parallel tabu search algorithm using ejection chains for the vehicle routing problem”, In: Osma, I.H., Kelly J. (Eds.):Meta-Heuristics: Theory and Applications (1996). Rochat Y. & Taillard E. D., “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing”, Journal of Heuristics (1995), 1 :147-167. Rosekrantz D. J., Stearns R. E. & Lewis II P. M., “An analysis of several heuristics for the traveling salesman problem”, SIAM Journal on Computing (1977), 6, 3, 563-581. Renaud J. & Boctor F. F., “A sweep-based algorithm for the fleet size and mix vehicle routing problem”, European Journal of Operational Research (2002), 140, 3: 618-628. Rousseau L., Gendreau P. & PESANT G., “Using constraint-based operators to solve vehicle routing problem with time windows”, Journal of Heuristics (2002), 8: 43-58. Taillard E. D., “Parallel iterative search methods for vehicle routing problems”, Networks (1993), 23, 661-673.

158

Taillard E. D., Badeau P., Gendreau M., Geurtin F. & Potvin J., “A tabu search heuristic for the vehicle routing problem with time windows”, Transportation Science (1997), 31: 170-186. Toth P. & Vigo D., “Models, relaxations and exact approaches for the capacitated vehicle routing problem”, Discrete Applied Mathematics (2002), 123, 1-3: 487-512. Xu J. & Kelly J., “A network flow-based tabu search heuristics for the vehicle routing problem.” Transportation Science (1996), 30 : 379-393. Autres références: www.statcan.ca (consulté le 10 août 2003)

Documents

Remerciements - École de gestion | Université Laval ... · 2.4.5. Multi-dépôts ... problème de tournées de véhicules (vehicle routing problem) est un autre problème étudié