Embed Size (px)
Citation preview
APPROCHES DE RÉSOLUTION EN DEUX PHASES POUR LE PROBLÈME DE TOURNÉES DE
VÉHICULES EN RÉGION SINISTRÉE
Mémoire
SAMIR GHOUDI
Maîtrise en Sciences de l’Administration Maître ès sciences (M.Sc)
Québec, Canada
© Samir GHOUDI, 2013
iii
RÉSUMÉ
Le présent mémoire traite du problème de distribution de l’aide humanitaire en région
sinistrée. L’objectif est de distribuer l’aide humanitaire à des zones sinistrées à partir d’un
ensemble de centres de distribution via une flotte de véhicules hétérogène. Étant donné le
contexte particulier d’urgence, la distribution est planifiée pour satisfaire la demande des
zones touchées pour chaque type d’aide humanitaire dans les plus brefs délais, tout en
tenant compte à la fois de la durée de déplacement et de la durée de chargement et de
déchargement. Dans ce mémoire, nous proposons une approche itérative à deux phases afin
d’améliorer la qualité de la solution obtenue par une approche heuristique déjà proposée par
Berkoune et al. (2011). Des séries d’expérimentations basées sur des problèmes tests ont
été effectuées pour évaluer la qualité de la solution obtenue avec l’algorithme développé.
La synthèse des résultats obtenus a démontré que l’approche développée permet de
résoudre à l’optimalité des problèmes de taille réduite en évitant d’énumérer de façon
exhaustive toutes les combinaisons possibles. Une évaluation du choix de la condition
d’arrêt ainsi que trois variantes de l’algorithme développé ont été également proposées. Les
résultats obtenus nous ont menés à conclure que lorsque la taille du problème devient
importante, les améliorations proposées présenteraient une bonne alternative pour réduire le
temps total de calcul et raffiner la qualité de la solution obtenue.
Mots clés : Logistique humanitaire, tournées de véhicules, livraison partagée, modélisation
mathématique et heuristiques.
v
ABSTRACT
This thesis addresses the problem of distribution of humanitarian aid in disaster areas. The
objective is to deliver humanitarian aid to the affected areas from a set of distribution
centers, by using a fleet of heterogeneous vehicles. Given the particular emergency
situation, the distribution is planned to meet the demand of affected areas for each type of
humanitarian aid in the shortest possible time, taking into account both the travel and
products loading and unloading times. In this thesis, we propose a two-phase solution
approach in order to improve the quality of the solution obtained using the heuristic
approach previously proposed by Berkoune et al. (2011). A series of experiments are run to
assess the quality of the solutions obtained with the developed algorithm. The obtained
results showed that the developed approach can solve the problem to optimality for the
majority of the instances, avoiding an exhaustive enumeration of all possible combinations.
An evaluation of the choice of stopping condition and three Variants of the developed
algorithm are also proposed. The obtained results show that when the problem size
becomes large, the proposed improvements provide a good alternative to reduce the total
computation time and improve the quality of the obtained solution.
Keywords: Emergency logistics, vehicle routing, split delivery, mathematical modeling and
heuristics.
vii
REMERCIEMENT
C’est un devoir bien agréable de venir rendre hommage au terme de ce travail à ceux
sans lesquels il n’aurait pu être fait.
Tout d'abord, je tiens à remercier Dieu le Tout-Puissant qui m'a donné la force, la
volonté et la santé jusqu’à ce jour.
Je tiens à remercier sincèrement mon directeur de recherche, Madame Monia
REKIK, pour son soutien, son support et ses précieux conseils. Je tiens également à
remercier mon codirecteur, Monsieur Jacques RENAUD, pour son apport à cette
recherche et pour m'avoir fait profiter de son expérience et de son expertise.
Également, je voudrais bien exprimer mes profondes reconnaissances au CIRRELT
qui m'a permis d'avoir accès à des installations de qualité et qui m'a supporté
financièrement à plusieurs occasions.
Je remercie aussi tous mes professeurs et tous les cadres enseignants de FSA ULaval
pour leurs efforts qu’ils ont déployés pour nous assurer une formation de bonne
qualité.
ix
DÉDICACES
À ma chère mère Salma
Pour ses sacrifices démesurés et son amour infini.
Que Dieu puisse la garder afin que ses prières me protègent et que ses regards suivent
ma destinée.
J’espère pouvoir réaliser aujourd’hui l’un de ses rêves et être toujours à la hauteur de
ses espérances.
À mon cher père Khalifa
Qui n’a jamais cessé de me soutenir et m’encourager,
Qui a impatiemment attendu ce jour,
Aucun mot ne serait assez loquace pour témoigner les sentiments de reconnaissance
que j’éprouve à son égard.
À ma chère sœur Fatma,
À mes chers frères Mounir, Yahya, Mahjoub et Mohamed,
À mes chers amis Dr. Fawzi, Dr. Anis et Saber,
À tous ceux qui me sont chers,
Je dédie ce projet de fin d’études et qu’ils trouvent dans ce modeste travail le
témoignage de ma profonde gratitude et mon infini dévouement.
Sincèrement,
SAMIR
xi
TABLE DES MATIÈRES RÉSUMÉ ............................................................................................................................. iii ABSTRACT ........................................................................................................................... v REMERCIEMENT ........................................................................................................... vii DÉDICACES ........................................................................................................................ ix TABLE DES MATIÈRES ................................................................................................... ix LISTE DES TABLEAUX ................................................................................................. xiii LISTE DES FIGURES ..................................................................................................... xiii CHAPITRE 1 : INTRODUCTION ..................................................................................... 1 CHAPITRE 2 : REVUE DE LA LITTÉRATURE ............................................................ 7
2.1. Problème du voyageur de commerce .......................................................................... 8 2.2. Problème de tournées de véhicules ........................................................................... 10
2.2.1. Heuristique de construction ................................................................................ 12 2.2.2. Heuristiques d’amélioration ................................................................................ 13 2.2.3. Méta-heuristiques ................................................................................................ 13
2.3. Problèmes de tournées de véhicules en région sinistrée ........................................... 15 2.4. Conclusion ................................................................................................................ 18
CHAPITRE 3 : DÉFINITION DU PROBLÈME ............................................................ 20 3.1. Définition de la problématique ................................................................................. 20
3.1.1. Centre de distribution d’aide humanitaire (CDAH) ........................................... 21 3.1.2. Les clients .......................................................................................................... 22 3.1.3. La flotte de véhicules ......................................................................................... 22 3.1.4. Temps d’accès maximum et temps de distribution ............................................ 23 3.1.5. Exemple illustratif .............................................................................................. 23
3.2. Modèle mathématique ............................................................................................... 25 3.3. Conclusion ................................................................................................................ 28
CHAPITRE 4 : APPROCHES DE RÉSOLUTION ........................................................ 30 4.1. Approche heuristique proposée par Berkoune et al. (2011) ..................................... 31
4.1.1. Étape 1 : Énumération partielle .......................................................................... 31 4.1.2. Étape 2 : Chargement et sélection des tournées ................................................. 33
4.2. Motivations ............................................................................................................... 33 4.3. Approche de base ...................................................................................................... 34
4.3.1. Critère d’arrêt ..................................................................................................... 36 4.3.2. Les étapes de l’approche proposée .................................................................... 36
xii
4.4. Variantes de l’approche de base ............................................................................... 41 4.4.1. Variante 1 .......................................................................................................... 41 4.4.2. Variante 2 .......................................................................................................... 42 4.4.3. Variante 3 .......................................................................................................... 43
4.4. Conclusion ................................................................................................................ 45 CHAPITRE 5 : RÉSULTATS ET EXPÉRIMENTATION ........................................... 48
5.1. Matériels de développement utilisés ........................................................................ 49 5.2. Problèmes tests ......................................................................................................... 49 5.3. Étude de l’impact du nombre de split ....................................................................... 51 5.4. Étude de la condition d’arrêt .................................................................................... 60
5.4.1. Effet de la variation du temps de résolution maximal sur les performances de l’approche de base ........................................................................................................ 62 5.4.2. Effet de la variation du nombre d’itérations sans amélioration sur les performances de l’approche base ................................................................................. 62 5.4.3. Comparaison des deux critères d’arrêt .............................................................. 66
5.5. Étude comparative entre l’approche de base proposée et ses variantes .................... 67 5.6. Plan d’expérience comparatif ................................................................................... 73
5.6.1. Comparaison de la qualité de la solution ........................................................... 74 5.6.2. Effet de la variation du nombre de CDAH(s) sur la qualité de la solution obtenue ......................................................................................................................... 79 5.6.3. Effet de la variation du nombre de clients sur la qualité de la solution obtenue 82 5.6.4. Comparaison du temps de résolution ................................................................ 83
5.7. Conclusion ................................................................................................................ 88 CHAPITRE 6 : CONCLUSION........................................................................................ 91 BIBLIOGRAPHIES ........................................................................................................... 96
xiii
LISTE DES TABLEAUX
Tableau 1 : Paramètres des instances .................................................................................... 50
Tableau 2 : Effet de la variation du nombre de split sur la qualité de la solution obtenue ... 53
Tableau 3 : Effet de la variation du nombre de split sur les temps de résolution ................. 57
Tableau 4 : Paramètres de 10 instances sélectionnées .......................................................... 60
Tableau 5 : Solution obtenue avec les deux approches proposées par Berkoune et al. (2011) ...................................................................................................................................... 61
Tableau 6 : Temps de résolution obtenu avec les deux approches de Berkoune et al. (2011) ...................................................................................................................................... 61
Tableau 7 : Effet de la variation du nombre d’itérations sans amélioration sur la qualité de la solution obtenue ........................................................................................................ 63
Tableau 8 : Effet de la variation du nombre d’itérations sans amélioration sur le temps de résolution ...................................................................................................................... 64
Tableau 9 : Variation des temps de résolution en fonction du critère d’arrêt ....................... 67
Tableau 10 : Impact des changements effectués sur l’approche de base sur la qualité de la solution obtenue ............................................................................................................ 69
Tableau 11 : Impact des changements effectués sur l’approche de base sur le temps de résolution ...................................................................................................................... 69
Tableau 12 : Paramètres des 54 problèmes tests ................................................................... 73
Tableau 13 : Nombre de routes et écart d’optimalité correspondants aux solutions obtenues ...................................................................................................................................... 75
Tableau 14 : Comparaison de la qualité de la solution obtenue par les quatre approches .... 77
Tableau 15 : Comparaison du temps de résolution de quatre approches .............................. 84
xv
LISTE DES FIGURES
Figure 1 : Principe de fonctionnement des méta-heuristiques .............................................. 14
Figure 2 : Exemple du problème VRP-RS (10 points de demande, 2 CDAHs) ................... 24
Figure 3 : Différentes étapes de la méthode de résolution .................................................... 35
Figure 4 : Exemple de sélection de routes ............................................................................ 38
Figure 5 : Diagramme de la Troisième variante ................................................................... 44
Figure 6 : Variation de l’écart en pourcentage en fonction du nombre de split (3 clients/route) ................................................................................................................. 55
Figure 7 : Variation du ‘T_Sol’ en fonction du nombre de split .......................................... 59
Figure 8 : Variation du temps total de résolution en fonction du nombre d'itérations sans amélioration .................................................................................................................. 66
Figure 9 : variation de l’écart en pourcentage par rapport au numéro du test ...................... 72
Figure 10 : Variation de l’écart d’optimalité en fonction du nombre de CDAHs (Premier cas) ................................................................................................................................ 80
Figure 11 : Variation de l’écart d'optimalité en fonction du nombre de CDAHs (Deuxième cas) ................................................................................................................................ 80
Figure 12 : Variation de l’écart en pourcentage en fonction du nombre de CDAHs (Premier cas) ................................................................................................................................ 81
Figure 13 : Variation de l’écart en pourcentage en fonction du nombre de CDAHs (Deuxième cas) ............................................................................................................. 81
Figure 14 : Variation de l'écart d'optimalité en fonction du nombre de clients (3 Clients/route) ................................................................................................................ 82
Figure 15 : Variation de l'écart d'optimalité en fonction du nombre de clients (4 clients/route) ................................................................................................................. 82
Figure 16 : Variation de l’écart en pourcentage en fonction du nombre de clients (3 clients/route) ................................................................................................................. 83
Figure 17 : Variation de l’écart en pourcentage en fonction du nombre de clients (4 clients/route) ................................................................................................................. 83
Figure 18 : Variation du temps total de résolution (4 CDAHs) ............................................ 87
Figure 19 : Variation du temps total de résolution (5 CDAHs) ............................................ 87
1
CHAPITRE 1
INTRODUCTION
Les catastrophes, qu’elles soient d’origine naturelle ou humaine, entraînent d’importantes
pertes que ce soit sur le plan humain ou matériel. Il a été établi que les catastrophes, que ce
soit des tremblements de terre, des accidents nucléaires, des accidents maritimes ou autre
sont de plus en plus fréquentes. En effet, plusieurs pays ont été touchés par des sinistres
dans des zones ayant une densité démographique élevée, exposant des populations entières
à de tels phénomènes et provoquant des bouleversements importants. Ainsi, elles
représentent un facteur générateur d’instabilité de la population humaine, obligeant les
agglomérations d’individus sinistrés à des déplacements à grande ou moyenne échelle,
fuyant une éventuelle pénurie en eau et d’alimentation, et à la recherche d’une meilleure
accessibilité aux services de bases.
2
Les données disponibles1 montrent très clairement une augmentation remarquable du
nombre de catastrophes au cours des dernières décennies, ainsi que des personnes affectées
et des dommages économiques qui en résultent. Lors des années 2000 à 2005, en moyenne
près de 300 millions de personnes ont été affectées chaque année par les catastrophes et
près de 78 000 y ont trouvé la mort (CRED, 01/2007). Si on se base sur les statistiques
réalisées en 2011, on a chiffré sur le plan des pertes économiques subits, un coût total des
dommages assurés liés aux catastrophes naturelles à la hauteur de 366 milliards de dollars2.
Aussi en 2011 et selon l’ONU, 29 782 personnes ont trouvé la mort lors de 302
catastrophes dans le monde et près de 260 millions d’êtres humains ont été affectés. À titre
d’exemple, un tremblement de terre d’une magnitude de 7,0 à 7,3 survenu le 12 janvier
2010 près du Port-au-Prince, la capitale d’Haïti, a fait plus de 100 000 morts. Le séisme de
Fukushima, du 12 mars 2011, a entrainé un accident nucléaire majeur classé au niveau 7 (le
plus élevé) de l’échelle internationale des événements nucléaires. Cet accident, combinant
les effets d’un accident nucléaire et d’un tremblement de terre, a transformé la ville de
Namie (Japon) en une ville de fantôme par l’évacuation de plus de 22 000 habitants. De
même, on trouve des catastrophes d’origine humaine comme l’explosion à Bhopal (une
ville au nord de l’Inde) dans une usine d’Union Carbide (maintenant Dow Chemical) de
pesticides qui a dégagé des tonnes de polluant dans l’atmosphère de la ville et qui a tué
entre 16 000 et 30 000 personnes, dont huit mille la première nuit3.
"Les désastres en 2011 ont montré que les pays développés ainsi que les pays à revenu
moyen ne sont pas protégés contre les catastrophes dévastatrices4 ". En effet, ces situations
d’urgence soulèvent l’existence de menaces majeures dont on est obligé de réduire les
impacts néfastes et dévastateurs à travers une amélioration du temps de réponse, une bonne
adaptation à la nature du sinistre et une meilleure exploitation des ressources mises à
dispositions des sinistrés, couplée à une coordination efficace des opérations
d’interventions.
1 EM-DAT : The international Disaster Database (http://www.emdat.be/) 2 L’ONU dans sa dernière étude annuelle sur le sujet publiée mercredi 18 janvier 2012 3 http://www.lemonde.fr/planete/article/2012/10/01/a-bhopal-l-impossible-decontamination_1768230_3244.html 4 Directrice du Centre de recherche sur l'épidémiologie des désastres (CRED), Debarati Guha-Sapir
3
Vu leurs caractères aléatoires, aucun pays n’est à l’abri des catastrophes, il s’avère alors
utile d’agir d’une manière préventive en exploitant l’ensemble des connaissances établies
dans diverses disciplines de recherche scientifique pour mieux coordonner les efforts
déployés et diminuer en conséquence l’impact dévastateur et brutal de ces catastrophes.
Tout ceci passe nécessairement par une gestion plus efficiente des situations de crises, à
travers le développement d’outils robustes et rapides capable de venir en aide au preneur de
décision. Les défis majeurs dont on fait face dans de telles situations sont liés
essentiellement aux déploiements logistiques permettant d’assurer la distribution de l’aide
humanitaire aux populations à l’intérieur de la région sinistrée, alors que l’infrastructure et
les voies d’accès peuvent être gravement affectées ou complètement détruites. Ces
préoccupations nous ont amenés à étudier la gestion des opérations logistique dans des
situations de crises, qui est le sujet de ce présent mémoire.
La gestion des urgences peut être divisée en quatre principales phases : l’atténuation, la
préparation, l’intervention et le rétablissement (Haddow, Bullock et Coppola, 2008).
L’atténuation et la préparation sont deux phases d’anticipation qui entre dans un registre
préventif lorsque la situation de crise est prévisible. Ces deux phases permettent de définir
au préalable les mesures nécessaires pour réduire, atténuer ou prévenir les impacts des
sinistres et développer des plans d’action qui seront mis en place pendant un sinistre. Lors
de l’occurrence de la crise, les phases de réponse et de récupération commencent par la
mobilisation et le déploiement des services d’urgence à l’intérieur de la zone sinistrée dans
le but de protéger la population et réduire les dommages humains et matériels. La phase de
récupération, ou de rétablissement, conduit à définir les mesures nécessaires pour ramener
le niveau de vie à sa qualité initiale (avant sinistre).
Dans ce travail, nous nous concentrons sur l’étude de la phase d’intervention et plus
précisément au problème de distribution de l’aide humanitaire en régions sinistrées. Les
clients ou les demandeurs d’aide peuvent être des individus, une agrégation d’individus
(une rue, un secteur), des organismes (un hôpital ou un centre de soins), ou encore un point
de service quelconque (un pont ou une autoroute à rétablir). Le problème de distribution
étudié concerne l’acheminement des produits et/ou services de première nécessité aux
clients dans les plus courts délais. Les produits et les services sont supposés disponibles en
4
tout temps dans des localisations spécialisées. Ces localisations sont déployées par les
gestionnaires de crise à l’intérieur de la région sinistrée et sont considérées comme des
dépôts provisoires, généralement appelés Centre de Distribution d’Aide Humanitaire
(CDAH). Chacun de ces centres dispose d’une flotte limitée de véhicules hétérogènes avec
des capacités (en volume et en poids), des règles d’utilisation (temps total de travail) et des
caractéristiques (temps de chargement et de déchargement) différentes.
Vu le contexte particulier d’urgence, notre objectif sera de proposer un déploiement
capable de satisfaire la demande des clients touchés sous les contraintes d’offre tout en
minimisant la durée de distribution maximale. Cette durée de distribution tient en compte à
la fois des temps de déplacement et des temps de chargement et déchargement des
véhicules utilisés. La flotte de véhicules est supposée disponible aux centres de distribution
et doit être exploitée au maximum. Finalement, le problème considéré suppose que chaque
client peut être visité par plusieurs tournées ce qui correspond au principe de la livraison
partagée.
Le reste du présent mémoire est organisé comme suit. Dans le CHAPITRE 2, nous
exposerons une revue de littérature permettant de positionner les axes de notre sujet de
recherche à savoir la logistique dans une situation d’urgence. Ce chapitre comportera une
synthèse des travaux les plus pertinents portant sur le problème du voyageur de commerce,
le problème classique de tournées de véhicules ainsi que les problèmes de tournées de
véhicules en régions sinistrées. Dans CHAPITRE 3, nous exposerons la problématique,
ensuite nous reviendrions plus en détail sur le modèle mathématique proposé par Berkoune
et al. (2011). Le CHAPITRE 4 sera consacré à la définition détaillée de l’approche
heuristique proposée par Berkoune et al. (2011). Ensuite, nous allons décrire l’approche de
base qui nous avons adoptée pour résoudre le problème, l’algorithme de résolution ainsi
que les trois variantes modifiées de l’approche proposée. Le CHAPITRE 5 comportera une
évaluation de l’impact de la variation de la valeur et de la nature de la condition d’arrêt.
Ensuite, une étude comparative entre les trois variantes et l’approche de base que nous
avons développée en termes de la qualité de la solution obtenue et du temps de résolution.
Finalement, une série de tests expérimentaux pour illustrer la valeur ajoutée des
modifications apportées sur l’algorithme de résolution d’un point de vue qualité de la
5
solution obtenue. Cette série de tests présente une étude comparative des algorithmes
développés dans le cadre de ce mémoire et le travail déjà réalisé par Berkoune et al. (2011)
en termes de qualité de la solution obtenue et de temps de résolution. Le CHAPITRE 6
conclut en offrant un aperçu général des résultats obtenus ainsi que des recommandations et
perspectives pour des travaux futurs.
7
CHAPITRE 2
REVUE DE LA LITTÉRATURE
Ce chapitre vise à présenter les principaux éléments de la littérature se rapportant au
problème de transport et qui ont servi au développement de nos travaux. Il permet
essentiellement d’introduire les travaux antérieurs les plus pertinents en association avec
notre sujet, et de positionner en même temps nos axes de recherche par apport à celle-ci.
Il existe une littérature vaste et prolifique sur les problèmes de tournées de véhicules,
témoignant de l’intention particulière accordée à cette problématique essentiellement durant
les dernières décennies. De ce fait, nous avons jugé essentiel de nous limiter aux travaux
possédants des aspects spécifiques reliés à notre étude au lieu de nous attarder sur des
généralités. En effet, nous allons nous intéresser au problème du voyageur de commerce
(Traveling Salesman Problem – TSP), le problème classique de tournées de véhicules
(Vehicle Routing Problem – VRP) et les problèmes de tournées de véhicules en région
sinistrée.
8
2.1. Problème du voyageur de commerce
Le problème du voyageur de commerce (Traveling Salesman Problem - TSP) a été traité
pour la première fois par Euler en 1736. Lawler et al. (1985) ont répertorié près de 600
références depuis le début de l’étude du problème TSP, témoignant du rôle central que joue
ce problème que ce soit dans les domaines de la distribution, de la logistique ou dans des
domaines connexes. Par définition, le problème du voyageur de commerce consiste à
minimiser la distance totale du cycle (graphe non orienté) ou du circuit (graphe orienté)
permettant de visiter chacun des nœuds (clients) une seule fois. Un graphe peut être désigné
par la notation suivante : G (V, A), où V = {v1,...,vn} représente l’ensemble de sommets
représentant les villes avec le dépôt situé au sommet v1 et A = {(i, j) : i, j ∈ V, i ≠ j} est
l’ensemble des arcs (graphe orienté). On associe à chaque ensemble d’arcs la matrice de
distances (ou de coûts) C = (cij). C peut être symétrique (cij = cji, ∀ i, j ∈ V) ou asymétrique
(∃ i, j ∈ V | cij ≠ cji) selon le cas étudié (Laporte, 1992a).
Dantzig, Fulkerson et Johnson (1954) ont développé la première modélisation pour
résoudre le problème TSP d’une façon exacte. Ils ont défini xij comme étant une variable
binaire dont la valeur est 1 lorsque le client j est visité immédiatement après le client i. Ils
ont formulé le problème comme suit :
Minimise �𝑐𝑖𝑗𝑥𝑖𝑗𝑖≠𝑗
(1)
Sujet à �𝑥𝑖𝑗
𝑛
𝑗=1
= 1 (i∈ {1,..., n}) (2)
�𝑥𝑖𝑗
𝑛
𝑖=1
= 1 (j∈ {1,..., n}) (3)
� 𝑥𝑖𝑗
𝑛
𝑖,𝑗 ∈𝑆
≤ |𝑆| − 1 S ⊂ 𝑉, 2 ≤ |𝑆| ≤ 𝑛 − 2 (4)
𝑥𝑖𝑗 ∈ {0, 1} (i, j ∈ {1,..., n}, i ≠ j) (5)
L’objectif est de minimiser le coût de la tournée (1). Les contraintes (2) et (3) assurent qu’il
y a une arrivée et un départ de chacun des clients. Les contraintes (4) permettent d’éliminer
les sous-tours possibles dans la tournée (une tournée devra obligatoirement débuter et
9
terminer au dépôt). |𝑆| est le nombre de sommets inclus dans un sous-tour potentiel
composé des clients de l’ensemble S. La contrainte (4) exige 2n contraintes ce qui en fait
une formulation pratiquement inutilisable. Les contraintes (5) exigent que les variables
soient binaires.
De nombreux algorithmes ont été développés pour résoudre ce problème d’une façon
exacte. À titre d’exemple, nous citons la théorie polyédrale, l’algorithme de séparation et
d’évaluation progressive (branch-and-bound), l’algorithme de génération de coupes
(branch-and-cut) et la génération de colonnes. Dans la pratique, nous trouvons deux
catégories de problèmes TSP : symétrique et asymétrique. Les problèmes asymétriques ont
généralement été résolus beaucoup plus facilement bien que des approches soient
également maintenant très performantes pour le cas symétrique. La plus importante
solution dans cette ligne de recherche est le développement de l’algorithme Concorde par
Applegate et al. (2003, 2006) et qui représente aujourd’hui le meilleur solveur de TSP
symétrique (Laporte, 2010). Applegate et al. (2007) utilisent un branch-and-cut-and-price
qui repose sur une méthode de génération de coupes particulièrement efficace appelée
tentative branching pour sélectionner plusieurs candidats pour chacun desquels une étape
de branchement est tentée en plus d’appliquer une version restreinte des plans de coupes.
Dépendamment de la taille du problème, le temps du calcul pour générer une solution
exacte augmente d’une façon exponentielle en fonction de la taille. Ceci mène beaucoup de
chercheurs à développer des solutions par d’autres moyens. Parmi les méthodes
développées, nous trouvons les heuristiques simples de construction telles que l’insertion la
moins coûteuse ou le plus proche voisin (Rosenkrantz, Stearns et Lewis II, 1977) qui
malheureusement ne génèrent pas de bons résultats. Les heuristiques d’amélioration comme
le r-opt de Lin (1965), l’heuristique de Lin et Kernighan (1973) reprise par Helsgaun
(2000) et par Applegate, Cook et Rohe (2003) dans une version dite « enchaînée », l’Or-opt
(Or, 1976; Babin, Deneault et Laporte, 2007) et le 4-opt* (Renaud, Boctor et Laporte,
1996) sont des méthodes plus rapides et très efficaces. L’algorithme de Helsgaun (2000)
demeure jusqu’à aujourd’hui la meilleure heuristique disponible pour la résolution du
problème de TSP. De nombreuses heuristiques hybrides ont été développées, dont
l’algorithme génétique introduit par John Holland en 1960 dans son livre « Adaptation in
10
Natural and Artificial Systems », le réseau de neurones et l’algorithme de fourmis, etc. Pour
le TSP, ces algorithmes ne sont pas vraiment performants, le champion incontesté
demeurant toujours l’algorithme de Helsgaun.
2.2. Problème de tournées de véhicules
Le problème de tournées de véhicule VRP joue un rôle très important dans la gestion de la
distribution. Il a été abordé pour la première fois en 1959 par Dantzig et Ramser. Laporte et
Osman (1995) ont rapporté dans une revue bibliographique près de 500 références et ils ont
indiqué que même avec un tel nombre d’articles qui ont traité le problème VRP, ce dernier
reste encore mal résolu. Dans un ouvrage plus récent, Toth et Vigo (2002) ont exploré l’état
de l’art des deux méthodes exactes et heuristiques développées au cours des dernières
décennies pour résoudre le problème de VRP et certaines de ses principales variantes. Par
ailleurs, ils ont consacré une partie considérable de l’ouvrage à la discussion des questions
pratiques.
En général, le problème de tournées de véhicule consiste à concevoir un plan de
distribution optimal, ou des circuits de collecte, à partir d’un dépôt central vers un
ensemble de clients géographiquement dispersés et soumis à diverses contraintes, tels que
la capacité du véhicule, la longueur de la route, les relations de précédence, etc. Il est défini
sur un graphe G (V, A) où V = {v0,..., vn} est l’ensemble des n +1 sommets (v0 est le dépôt
et {v1,..., vn} est l’ensemble des clients) et A = {(i, j): i, j ∈V, i ≠ j} est l’ensemble des arcs
(graphe orienté). C = (cij) est la matrice de distances ou de coûts associée à A. selon le cas
étudié, C peut être symétrique (cij = cji, ∀ i, j ∈ V) ou asymétrique (∃ i, j ∈ V | cij ≠ cji).
Dans le cas où C est symétrique, A = {(i, j) : i, j∈V,i < j} représente l’ensemble des arêtes
(graphe non orienté). Une flotte de véhicules k = {1,..., m} de capacité Q est basée au dépôt
(le VRP classique suppose que les véhicules sont identiques et que m est non borné). La
demande de chaque client vi est notés qi. Cordeau et al. (2005) a défini le VRP comme étant
la conception d’un ensemble de routes au moindre coût dans le but de satisfaire la demande
des clients tout en respectant la capacité des véhicules et la durée totale maximale D pour
chacune des routes.
11
De nombreuses modélisations mathématiques ont été proposées afin de résoudre ce
problème, passant de la formulation par flux à la formulation par ensemble de
partitionnement. Pour bien distinguer la formulation du TSP de celle du VRP, nous
proposons ci-dessous une formulation similaire à celle présentée dans la section précédente.
Dans ce cas de figure xij devient xijk qui est une variable binaire égale à 1 si le client j est
visité immédiatement après le client i avec le véhicule k. Le VRP est alors modélisé comme
suit :
Minimise ���𝑐𝑖𝑗𝑥𝑖𝑗𝑘
n
j=0j≠i
n
i=0
m
k=0
(6)
Sujet à ��𝑥𝑖𝑗𝑘
𝑛
𝑗=1
𝑚
𝑘=1
= 1 (i∈ {1,..., n}) (7)
��𝑥𝑖𝑗𝑘
𝑛
𝑖=1
𝑚
𝑘=1
= 1 (j∈ {1,..., n}) (8)
�𝑥𝑖ℎ𝑘
𝑛
𝑖=1
−�𝑥ℎ𝑗𝑘
𝑛
𝑗=1
= 0 (h∈ {1,..., n}, k∈ {1,..., m}) (9)
��𝑞𝑖𝑥𝑖𝑗𝑘
𝑛
𝑗=1𝑗≠𝑖
𝑛
𝑖=1
≤ 𝑄 (k∈ {1,..., m}) (10)
��𝑐𝑖𝑗𝑥𝑖𝑗𝑘
𝑛
𝑗=1𝑗≠𝑖
𝑛
𝑖=1
≤ 𝐷 (k∈ {1,..., m}) (11)
𝑢𝑖𝑘 − 𝑢𝑗𝑘 + (𝑛 − 1)𝑥𝑖𝑗𝑘 ≤ 𝑛 − 2 (i, j ∈ {2,..., n}, i ≠ j, k) (12)
𝑥𝑖𝑗𝑘 ∈ {0, 1} (i, j ∈ {1,..., n}, i ≠ j, k) (13)
𝑢𝑖𝑘 ≥ 0 (i ∈ {1,..., n}, k) (14)
Les contraintes (12) et (14) permettent d’éliminer les sous-tours possibles dans la tournée,
elles peuvent être remplacées par la contrainte (2) de la section précédente. Récemment,
Kara, Laporte et Bektas (2004) ont développé un autre modèle incluant une contrainte qui
peut renforcer la contrainte (14) en la réécrivant comme suit :
𝑢𝑖𝑘 − 𝑢𝑗𝑘 + 𝑄𝑥𝑖𝑗𝑘 + (𝑄 − 𝑞𝑖 − 𝑞𝑗)𝑥𝑖𝑗𝑘 ≤ 𝑄 − 𝑞𝑗 (i, j ∈ {1,..., n}, i ≠ j, k) (12)
12
En comparant avec le problème TSP, le problème de tournées de véhicules est beaucoup
plus complexe, car il implique la gestion d’une flotte de véhicules (homogène ou
hétérogène) et doit tenir compte de plusieurs tournées. En effet, la résolution optimale est
quasi impossible pour les problèmes de grande taille. A nouveau deux types d’approches
sont disponibles pour résoudre ce problème à savoir la programmation dynamique et la
programmation linéaire. Cette dernière intègre la génération de colonnes, la génération de
coupes (branch-and-cut) et la séparation et évaluation progressive (branch-and-bound).
Plusieurs revues de littératures sur les méthodes exactes sont citées par Laporte et Nobert
(1987), Laporte (2007) et Baldacci, Toth et Vigo (2007). Les meilleurs algorithmes
disponibles sont ceux de Fukasawa et al. (2006) et de Baldacci, Christofides et Mingozzi,
(2008) qui permettent de résoudre sur une base régulière des problèmes composés d’au plus
135 nœuds. Ce sont les plus performants des algorithmes exacts.
Par ailleurs, les chercheurs ont développé des méthodes heuristiques pour résoudre les
problèmes de grande taille plus rapidement que les méthodes exactes. Nous distinguons
plusieurs catégories d’heuristiques, d’une façon très simpliste nous pouvons les diviser en
heuristiques de construction, procédures d’amélioration et méta-heuristiques.
2.2.1. Heuristique de construction
Les heuristiques de construction d’une solution initiale sont généralement simples et
rapides, mais les résultats générés sont plus au moins bons par rapport à la solution
optimale. Les heuristiques de construction élaborent la solution en agrandissant la tournée
par une ville (nœud) à chaque itération. Ces dernières s’arrêtent lorsque la solution est
obtenue et n’essayent pas de l’améliorer. Dans cette catégorie, on trouve l’heuristique du
plus proche voisin, un algorithme glouton.
Plusieurs heuristiques ont été développées, mais l’algorithme d’économies (savings
algorithms) demeure parmi les plus populaires algorithmes grâce à sa simplicité et sa
rapidité de mise en œuvre. Cet algorithme, présenté par G. Clarke et J.V. Wright (1964) est
une méthode qui sélectionne à chaque itération la meilleure économie (sij = ci0 + c0j – cij, ∀
i, j, i ≠ j) et fusionne les tournées associées. Comme décrit dans l’article de Laporte et
Semet (2002), plusieurs versions améliorées de l’algorithme d’économies ont été proposées
13
par les chercheurs, à savoir Nelson et al. (1985), Wark et Holt (1994), Altinel et Öncan
(2005) et Girard, Renaud et Boctor (2005).
D’autres types d’algorithmes basés sur la génération de routes ont également été présentés.
Notons l’algorithme de balayage par Gillett et Miller (1974), les algorithmes par pétales qui
sont une extension des algorithmes de balayage par Ryan, Hjorring & Glover (1993) et les
algorithmes cluster-first, route-second qui traitent au début un problème d’affectation
généralisée (Generalized Assignment Problem - GAP) suivi de TSP individuels (Fisher et
Jaikumar, 1981).
2.2.2. Heuristiques d’amélioration
Les heuristiques d’amélioration ont pour objectif la correction des tournées initialement
créées. Nous distinguons deux types d’algorithmes qui peuvent être appliqués aux
problèmes VRP : les heuristiques intra-route et les heuristiques inter-route. Les algorithmes
d’amélioration intra-route permettent l’optimisation de chaque route toute seule en utilisant
les heuristiques d’amélioration des problèmes TSP (2-opt ou 3-opt par exemple). D’autre
part, les améliorations inter-route échangent les points entre les routes. La plus connue est
la méthode d’échanges-λ (λ-inter-change), proposée par Osman (1993), qui consiste à
tester toutes les combinaisons d’échanges d’au plus λ nœuds appartenant à une première
route avec toutes les combinaisons d’au plus λ nœuds appartenant à une seconde route.
D’autres heuristiques plus complexes impliquant plusieurs routes ont été détaillées, à savoir
les échanges cycliques de Thompson et Psaraftis (1993), les chaînes d’éjection (Xu et
Kelly, 1996; Rego et Roucairol, 1996) et les schémas d’arcs d’échanges (Kinderwater et
Savelsbergh, 1997).
2.2.3. Méta-heuristiques
Au cours de 15 dernières années, des améliorations significatives ont été observées dans le
développement des méta-heuristiques. En outre, les méta-heuristiques permettent
l’exploration de l’espace des solutions au-delà du premier minimum local rencontré, ceci
permet de résoudre les problèmes plus efficacement par rapport aux heuristiques classiques
de descente en termes de qualité de solutions, puisque ces dernières s’arrêtent lorsqu’elles
14
trouvent un optimum local. Par contre, la recherche dans les voisinages demande un temps
de résolution beaucoup plus grand que les heuristiques classiques. Les méta-heuristiques
incluent plusieurs types de mécanismes à savoir la recherche locale, les mécanismes
d’apprentissages et les mécanismes de gestion des populations (Cordeau et al. 2005 et
Laporte, 2007).
Figure 1 : Principe de fonctionnement des méta-heuristiques
La Figure 1 illustre le principe de fonctionnement des méta-heuristiques. En effet, les méta-
heuristiques tentent de trouver l’optimum global (G) d’un problème d’optimisation difficile
(avec des discontinuités D, par exemple), sans être piégé par les optima locaux (L)5.
Les mécanismes de recherche locale ont pour objectif l’obtention d’une solution de bonne
qualité, en parcourant le plus efficacement possible une partie des voisins existants. Au
cours des dernières années, plusieurs mécanismes de recherche locale ont été détaillés et
parmi eux figurent le recuit simulé (simulated annealing - SA), le recuit déterministe
(deterministic annealing – DA), la méthode de recherche tabou (tabu search – TS), les
algorithmes de recherche dans de très grands voisinages (very large neighborhood search)
et l’algorithme des attributs (attribute based hill climber – ABHC).
Les mécanismes de populations sont nombreux, dont le plus connu est l’algorithme
génétique (genetic algorithm - GA), développé par Holland (1975). Cet algorithme
fonctionne en simulant l’évolution naturelle, c’est-à-dire chacun des parents transmet une
partie de leurs gènes à la nouvelle génération. Le but principal de l’algorithme génétique est
de parvenir à de meilleurs résultats en suppriment les mauvaises solutions lors de la
production des enfants (nouvelle génération). Des autres mécanismes de populations ont été 5 http://fr.academic.ru/dic.nsf/frwiki/1211975
15
étudiés et développés par plusieurs chercheurs, à savoir Prins (2004) qui a développé des
algorithmes hybrides, Rochat et Taillard (1995) qui ont proposé une méthode de recherche
tabou avec une procédure de mémoire adaptative (adaptative memory procedure) et plus
récemment Tarantilis et Kiranoudis (2005).
On distingue deux types de mécanismes d’apprentissage : les réseaux de neurones (neural
networks - NN) et les algorithmes de colonies de fourmis (ant systems - AS). Les réseaux
de neurones représentent des ensembles d’unités liées par des connections pondérées
transmettant l’information et permettant un apprentissage. Les premières applications des
réseaux de neurones pour le VRP ont été plutôt infructueuses (Ghaziri (1991) et Schumann
& Retzko (1995)). Les algorithmes de colonies de fourmis tentent d’imiter le comportement
des fourmis qui détectent les chemins contenant des phéromones et les renforcent par leur
propre phéromone. Cela conduit à l’émergence de plus courts chemins sur lesquels
phéromones s’accumulent plus vite. Plusieurs articles ont utilisé les algorithmes de colonies
de fourmis : Colorni, Dorigo et Maniezzo (1991) et Reimann, Doerner et Hartl (2004) qui
ont développé l’heuristique D-Ants (Decompostion-Ants) en proposant un algorithme
d’économies dont l’idée est de décomposer le problème en sous-problèmes disjoints puis de
les résoudre en utilisant l’algorithme de colonies de fourmis.
2.3. Problèmes de tournées de véhicules en région sinistrée
Ces dernières années, les chercheurs se sont tournés vers le traitement de problèmes moins
connus et plus complexes comme les problèmes dynamiques (Wen et al. 2010) et les
problèmes de tournées de véhicules avec fenêtres de temps (Cornillier et al. 2009). Ces
axes de recherches permettent de se rapprocher d’un contexte plus fidèle à la réalité des
problèmes traités. C’est dans cette optique que les problèmes de tournées de véhicules en
région sinistrée VRP-RS représentent un axe de recherche émergeant et conduisant à de
nombreux défis.
Tufekci et Wallace (1998) ont suggéré que la gestion de l’intervention d’urgence soit
divisée en deux étapes : la gestion en amont et la gestion en aval par rapport à la
catastrophe. Les tâches de la gestion en amont comprennent la prévision et l’analyse des
dangers potentiels et l’élaboration des plans d’action nécessaires à l’atténuation. Ainsi, la
16
phase de gestion en aval commence lorsque la catastrophe est toujours en cours. Cette
phase englobe les problématiques reliées à la localisation, l’allocation, la coordination et la
gestion des ressources disponibles afin d’intervenir et de rétablir les pertes. Les auteurs
considèrent également que pour qu’un plan d’intervention d’urgence soit efficace, il doit
intégrer à la fois les deux étapes dans son objectif. Dans la même optique, Altay et Green
(2006) décomposent les activités de gestion des catastrophes en quatre phases : prévention,
préparation, intervention et rétablissement. Ils ont montré que la plupart des recherches ont
été effectuées dans les phases de prévention et de préparation et que la planification des
tournées pour distribuer l’aide n’a attiré encore que peu d’attention.
Yi et Ozdamar (2007) proposent un modèle intégré de localisation-distribution permettant
la coordination du soutien logistique et l’évacuation des blessées pendant les activités de
réponse aux catastrophes. Le modèle traité maximise le niveau de service en permettant
l’accès rapide aux zones touchées, la localisation des unités d’urgences dans des sites
appropriés et la répartition du personnel médical entres les différentes unités. Yi et Kumar
(2007) ont utilisé le modèle de Yi et Ozdamar (2007) pour effectuer la distribution, mais
sans tenir compte de la composante localisation.
Sheu (2010) a développé un modèle de gestion dynamique des activités logistiques
d’urgence dans des conditions d’informations imparfaites. La méthodologie proposée se
compose de trois étapes : la fusion de données pour prévoir la demande de secours dans de
multiples domaines, le découpage de la zone affectée en groupes, et l’aide multicritère pour
établir l’ordre de priorité des groupes. Sheu exprime aussi que ce modèle permet non
seulement de rapprocher les exigences d’urgences en temps réel avec des informations
incertaines, mais aussi l’allocation dynamique des secours en fonction du degré d’urgence
identifié de chaque zone touchée.
Tzeng et al. (2007) décrivent un modèle multi-objectifs pour la conception d’un système de
distribution d’aide dans un cas réel dont les objectifs sont la minimisation de la somme du
coût total et du temps des voyages et la maximisation de la satisfaction minimale des points
de livraison. Le cas étudié renferme cinq points de collecte, huit points de demande et
quatre dépôts de transfert. Chern et al. (2009) ont introduit un algorithme heuristique
composé de deux étapes : le regroupement et le tri des exigences en fonction de plusieurs
17
facteurs (des produits demandés, des dates prévues pour chaque type de demande, des
capacités possibles partagées, des distances des nœuds de demande aux dépôts), puis la
planification des demandes individuellement en utilisant le plus faible temps de
déplacement et le coût minimal. Le réseau étudié est composé de quatre nœuds
d’approvisionnement, quatre nœuds de distribution, huit nœuds de demande et également
des stations de carburant.
Balcik et al. (2008) considère un problème de distribution d’aide humanitaire dans un
réseau composé d’un seul dépôt et de différents types de véhicules. Les principaux objectifs
sont l’allocation des fournitures de secours disponibles dans le dépôt aux demandeurs et de
déterminer les délais de livraison par route pour chaque véhicule tout au long de l’horizon
de planification. Balcik propose une solution approchée à deux phases dont la première
phase permet la génération de toutes les routes possibles pour chaque véhicule et la
deuxième phase consiste, en fonction des routes candidates trouvées, à résoudre un modèle
de programmation en nombres entiers mixte qui détermine les délais de livraison pour les
véhicules et répartit équitablement les ressources, sur la base de l’offre, de la capacité des
véhicules, et des restrictions de temps de livraison. L’objectif est de minimiser la somme
des coûts de transport et les frais de pénalité de la demande insatisfaite. Le but de cette
étude est de montrer comment le modèle proposé permet d’optimiser l’allocation des
ressources et les décisions de routage, puis de discuter les compromis entre les décisions
obtenues sur un certain nombre de problèmes de test.
Jotshi et al. (2009) ont développé une méthodologie pour l’allocation des véhicules
d’urgence dont l’objectif est de créer de meilleures liaisons entre les zones touchées où se
trouvent les victimes et les hôpitaux. Plus récemment, Berkoune et al. (2011) ont proposé
deux approches de résolution, une exacte et une heuristique, pour le problème de
distribution de l’aide humanitaire en région sinistrée. L’objectif visé est de satisfaire la
demande des différents points de demande pour les différents produits et services à partir
des différents CDAH dans les plus brefs délais, en tenant compte de toutes les contraintes
de disponibilités. Les auteurs constatent que les algorithmes proposés produisent de très
bonnes solutions dans un temps de calcul relativement court.
18
2.4. Conclusion
Dans ce chapitre, nous nous sommes concentrés essentiellement sur les travaux de
recherche antérieurs les plus pertinents en relation avec notre sujet, dans le but de saisir la
position de nos axes de recherche par apport à celle-ci. Pour ce faire, nous avons effectué
un survol d’une revue de littérature des problèmes de tournées de véhicules possédants des
aspects spécifiques reliés à la logistique dans une situation d’urgence. Dans cette revue,
nous nous sommes intéressés essentiellement au problème du voyageur de commerce, le
problème classique de tournées de véhicules et les problèmes de tournées de véhicules en
région sinistrée.
Dans le prochain chapitre, nous allons définir la problématique abordée, l’approche adoptée
pour résoudre le problème, ainsi que l’algorithme de résolution proposé.
20
CHAPITRE 3
DÉFINITION DU PROBLÈME
On se propose dans ce chapitre de définir sur le plan théorique la problématique abordée.
Pour ce faire, nous reviendrions en détail sur les principaux éléments du problème à traiter.
Par la suite, nous exposerons le modèle mathématique de résolution proposé par Berkoune
et al. (2011) et qui sera notre base de travail.
3.1. Définition de la problématique
Le problème étudié est une variante du Problème de Tournées de Véhicules (Vehicle
Routing Problem : VRP). Il peut être représenté sous forme d’un graphe dans lequel les
nœuds d’offre représentent les centres de distribution d’aide humanitaire (CDAH) et les
nœuds de demande représentent les points de la région sinistrée vers laquelle une aide
devrait être acheminée. L’ensemble des arcs du graphe représente les routes reliant les
21
différents nœuds du réseau. On définit la durée de déplacement associée à chacun des arcs
en fonction de l’état de la route (route inondée, inaccessible, etc.).
Contrairement aux problèmes de tournées de véhicules classiques où l’objectif consiste
généralement à minimiser la durée totale de déplacement sous des contraintes de capacité
en utilisant le moins de véhicules possibles, notre objectif est la minimisation de la durée de
distribution maximale (à partir des CDAH(s) vers les points de demande), sous des
contraintes de disponibilité des véhicules, de leurs types, de leurs capacités en poids et en
volume, de la durée maximale d’opération incluant le temps de déplacement, les temps de
chargement et déchargement ainsi que de la disponibilité des produits et services dans
chaque CDAH et ceci indépendamment du nombre de véhicules utilisés. En effet, dans les
situations d’urgence, l’objectif principal est d’acheminer l’aide nécessaire à tous les points
de demande dans les plus courts délais surtout dans les premières heures suivant le sinistre.
Ces premières heures sont considérées critiques et à ces instants on ignore généralement
l’ampleur des dégâts provoqués par le sinistre. Un autre élément important de
différenciation avec les problèmes de VRP classiques se situe au niveau du calcul des
temps des opérations de manutention. Ce temps prend en considération le type de
véhicules, le type de produits et l’infrastructure disponible dans les CDAH(s) et les points
de livraison.
Dans les sous-sections qui suivent, nous allons définir les éléments principaux du problème
traité, avant de passer ensuite au modèle mathématique.
3.1.1. Centre de distribution d’aide humanitaire (CDAH)
Les centres de distribution d’aide humanitaire (CDAHs) représentent des dépôts
temporaires pendant la période de la catastrophe. Ces centres permettent généralement
l’entreposage des ressources humanitaires nécessaires dans les situations d’urgences et qui
peuvent correspondre à des produits tangibles tels que la nourriture, des produits sanitaires,
des médicaments, eau, lits, etc., et/ou à des services tels que le renforcement d’un pont, le
rétablissement d’une ligne électrique, etc. Dans notre contexte d’étude, nous supposons que
les différentes décisions concernant le nombre, l’emplacement et la dotation en produits et
services des CDAH(s) ont été prises au préalable et ne seront pas modifiées au cours de
22
l’horizon de planification. Dépendamment de l’état d’urgence décrété et l’ampleur de la
catastrophe, cet horizon peut s’étaler sur quelques heures ou sur une journée entière.
3.1.2. Les clients
Les clients sont les demandeurs d’aide. Ils varient entre les individus d’une population, une
agrégation d’individus (une rue, un secteur), des organismes (un hôpital ou un centre de
soins), ou encore un point de service quelconque (un pont ou une autoroute à rétablir).
Suivant la gravité des dommages, la quantité et la nature de l’aide demandée peuvent
changer d’un client à un autre. Par ailleurs, le problème traité suppose que la demande reste
fixe pour un client donné et ceci pendant l’horizon de planification considéré. Nous
supposons qu’un client peut être servi par plusieurs CDAH(s) afin de satisfaire sa demande
dans le plus court délai. En d’autres termes, la livraison partagée (split delivery) est
permise.
3.1.3. La flotte de véhicules
En situation d’urgence, le transport de l’aide humanitaire à partir des différents CDAH(s)
vers les différents points de demande s’effectue à l’aide d’une flotte de véhicules, s’il s’agit
de produits, ou de fournisseurs de services lorsqu’il s’agit de services. La flotte de véhicule
disponible dans chaque CDAH peut être très fortement hétérogène (des véhicules légers,
des remorques, des semi-remorques, des citernes, etc.). Cette variété de véhicules dépend
de la diversité des besoins à combler pendant la période de catastrophe. En outre, les
véhicules disponibles dans les CDAH(s) peuvent être équipés avec des engins spécifiques à
savoir des grues, des ouvertures des portes, des systèmes de réfrigération, etc. En
contrepartie, ces équipements peuvent limiter la gamme de produits à livrer. On suppose
que lors de la planification des opérations de transport, il existe des restrictions associées à
la capacité des véhicules (volume, poids) et à la durée des tournées (Toth et Vigo, 2002).
On suppose également qu’un véhicule devra revenir à son CDAH d’origine après sa
tournée.
23
Étant donné la particularité du contexte d’urgence, on tolère l’exploitation maximale de la
flotte de véhicules disponible aux centres de distributions et on accepte aussi qu’un client
soit visité par plusieurs véhicules.
3.1.4. Temps d’accès maximum et temps de distribution
On définit un temps d’accès maximum afin d’assurer que chaque point de demande est
servi à l’intérieur d’un temps jugé raisonnable par les gestionnaires de crise. Rappelons que
le calcul du temps total de distribution tient en compte les temps de déplacement des
véhicules ainsi que les temps nécessaires pour effectuer les opérations de chargement des
véhicules aux CDAH(s) et les temps de déchargement de ces véhicules aux divers points de
livraison. Considérer les temps des opérations de manutention (chargement et
déchargement) est important dans le cas d’une forte hétérogénéité des véhicules
disponibles, des produits à transporter et des infrastructures disponibles aux CDAH(s) et
aux points de livraison.
Il ressort de ce qui précède que le problème de distribution d’aide humanitaire en région
sinistrée (VRP-RS) que nous traitons correspond à un problème de tournées de véhicules
multi-produits, multi-dépôts avec flotte hétérogène et livraison partagée (split delivery), qui
est réputé être un problème très complexe.
3.1.5. Exemple illustratif
24
Figure 2 : Exemple du problème VRP-RS (10 points de demande, 2 CDAHs)
La Figure 2 illustre un exemple du problème VRP-RS étudié. Dans cet exemple, nous
avons dix points de demande qui doivent être livrés à partir de 2 CDAH(s) via les véhicules
de différents types disponibles à chaque CDAH. Nous supposons que le réseau routier
définit un graphe complet impliquant ainsi que tous les nœuds (points de demande et
CDAHs) sont reliés entre eux par des arcs (représentés partiellement sur le graphe pour
alléger sa représentation). Le temps d’accès maximum prédéfini par les gestionnaires de
crise est représenté par des cercles en pointillés entourant chaque CDAH. Par exemple, les
points de demande 1, 3, 6, 9 et 10 sont accessibles à partir du CDAH 1 dans une fenêtre du
temps inférieure ou égale au temps d’accès maximum pour un aller-simple partant de ce
CDAH et allant directement à ces points. Par conséquent, le point 1 ne pourra être livré
qu’à partir du CDAH 1. Le point 4 étant à l’intérieur des rayons de couverture des CDAH 1
et 2, il pourra être livré à partir de ces deux CDAH(s). Étant donné que la livraison partagée
est tolérée, la demande du point 4 pour un produit donné pourra être satisfaite par deux
voyages différents utilisant possiblement des véhicules différents et partants possiblement
de CDAH différent (CDAH 1 et/ou 2).
CDAH
Client
25
3.2. Modèle mathématique
Cette section décrit le modèle de programmation linéaire mixte en nombres entiers MIP
considéré dans notre travail. Ce dernier a été développé par Berkoune et al. (2011).
Rappelons que l’objectif de ce modèle est de proposer un chargement d’un ensemble de
tournées vides et de retenir les meilleures tournées chargées afin de minimiser le temps de
distribution maximal entre les centres de distributions et les points de demandes. Nous
supposons dans cette section que l’ensemble de tournées à introduire dans le modèle est
généré d’une façon exhaustive (voir Exemple).
Exemple : Soit un réseau composé d’un CDAH {0} et trois clients {1, 2, 3}
L’ensemble de tournées vides = {(0-1-2-3-0) ; (0-1-3-2-0) ; (0-2-1-3-0) ; (0-2-3-1-0) ; (0-3-
1-2-0) ; (0-3-2-1-0)}.
Notations et terminologies
I : l’ensemble des points de livraison (clients) ;
J : l’ensemble des produits à livrer ;
L : l’ensemble des CDAH ;
K : l’ensemble des véhicules ;
dij : la demande du client i pour le produit j ;
Pjl : la quantité du produit j disponible au CDAH l ;
Kl : l’ensemble des véhicules disponible au CDAH l ;
Jk : l’ensemble des produits pouvant être servis par un véhicule k ;
Dk : le temps d’opération maximum toléré pour un véhicule k ;
Vk : la capacité maximale en volume du véhicule k ;
Wk : la capacité maximale en poids du véhicule k ;
vj : le volume occupé par une unité du produit j ;
wj : le poids relatif à une unité du produit j ;
tli : la durée de déplacement entre deux points l et i ;
Τ : le temps d’accès maximum.
26
Paramètres et ensembles
R : l’ensemble des tournées vides générées exhaustivement ;
r = (𝑙,𝑘, 𝑆) : Une tournée dans R partant du CDAH l, utilisant le véhicule k et
visitant les clients selon l’ordre défini dans S ;
𝛿𝑟𝑙 = 1, si la tournée r part du CDAH l ; 0 sinon ;
𝛼𝑟𝑘 = 1, si la tournée r utilise le véhicule k ; 0 sinon ;
𝛽𝑟𝑖 = 1, si la route r visite le point de livraison i ; 0 sinon ;
𝜌𝑟𝑗𝑖 : le temps de déchargement du véhicule k au point de livraison i d’une unité du
produit j à la route r ;
𝑇𝑟𝑑 : le temps de déplacement (sans les temps de chargement et de déchargement)
correspondant à la tournée r ;
𝑇�𝑟𝑑 : le temps de déplacement nécessaire pour la tournée r (sans les temps de
chargement et de déchargement) pour accéder au dernier client de la tournée (ce
temps est différent de 𝑇𝑟𝑑 dans la mesure où il ne tient pas compte du temps de
retour au dépôt).
Hypothèses
- Les camions présents à un CDAH sont tous de type différent (notons que l’on
pourra toujours se ramener à un tel contexte en dupliquant le nombre de types de
véhicules dans le cas où deux véhicules d’un même type sont disponibles à un
CDAH);
- Un véhicule k se trouvant au départ à un CDAH l doit toujours revenir à son point
d’origine l;
- Le VRP-RS est défini sur le graphe (𝐿 ∪ 𝐼, A), où A désigne l'ensemble des arcs
disponibles sur le réseau routier reliant les différents sommets;
- À chaque arc (l, i) ∈ A est associée une durée de déplacement tli. Cette durée fixe sur
tout le long de l’horizon de planification tient compte de l’état des routes suite au
sinistre
27
Variables de décision
𝑥𝑟 = �1, si la route 𝑟 est retenue,0, sinon. ∀ 𝑟 ∈ 𝑅
𝑦𝑟𝑗𝑖 : la quantité du produit j livrée par la tournée r au client i,∀ 𝑟 = (𝑙,𝑘, 𝑆) ∈
𝑅, ∀ 𝑗 ∈ 𝐽𝑘, ∀ 𝑖 ∈ 𝑆 ;
𝐿𝑀𝑎𝑥 : le temps de distribution maximal.
Modèle mathématique
(P) 𝑀𝑖𝑛 (𝐿Max) (15)
Sujet à : �𝛽𝑟𝑖𝑟∈𝑅
𝑦𝑟𝑗𝑖 = 𝑑𝑖𝑗 ∀𝑖 ∈ 𝐼, 𝑗 ∈ 𝐽 (16)
��𝛿𝑟𝑙𝛽𝑟𝑖𝑖∈𝐼
𝑦𝑟𝑗𝑖𝑟∈𝑅
≤ 𝑝𝑗𝑙 ∀𝑙 ∈ 𝐿, 𝑗 ∈ 𝐽 (17)
���𝛼𝑟𝑘𝛽𝑟𝑖𝑤𝑗𝑗∈𝐽
𝑦𝑟𝑗𝑖𝑖∈𝐼𝑟∈𝑅
≤ 𝑊𝑘 ∀𝑘 ∈ 𝐾 (18)
���𝛼𝑟𝑘𝛽𝑟𝑖𝑣𝑗𝑗∈𝐽
𝑦𝑟𝑗𝑖𝑖∈𝐼𝑟∈𝑅
≤ 𝑉𝑘 ∀𝑘 ∈ 𝐾 (19)
��𝛽𝑟𝑖𝜌𝑟𝑗𝑖𝑦𝑟𝑗𝑖𝑖∈𝐼𝑗∈𝐽
+ 𝑇𝑟𝑑𝑥𝑟 ≤ �𝛼𝑟,𝑘𝑘∈𝐾
𝐷𝑘𝑥𝑟 ∀ 𝑟 ∈ 𝑅 (20)
��𝛽𝑟𝑖𝜌𝑟𝑗𝑖𝑦𝑟𝑗𝑖𝑖∈𝐼𝑗∈𝐽
+ 𝑇�𝑟𝑑𝑥𝑟 ≤ 𝐿𝑀𝑎𝑥 ∀𝑟 ∈ 𝑅 (21)
�𝛼𝑟𝑘𝑥𝑟𝑟∈𝑅
≤ 1 ∀𝑘 ∈ 𝐾 (22)
𝐿𝑀𝑎𝑥 ≥ 0; 𝑥𝑟 = 0,1 ; ∀𝑟 ∈ 𝑅; 𝑦𝑟𝑗𝑖 ≥ 0 ∀𝑟 ∈ 𝑅, 𝑗 ∈ 𝐽, 𝑖 ∈ 𝐼 (23)
La fonction-objectif (15) minimise le temps de distribution maximal. La contrainte (16)
exige que la demande de chaque client pour chaque produit soit satisfaite avec les tournées
sélectionnées. La contrainte (17) assure que la quantité totale d’un produit j livrée à partir
d’un CDAH l via les tournées partant de l soit inférieur ou égale à la quantité disponible de
ce produit au CDAH l. Les contraintes (18), (19), garantissent respectivement que le poids
et le volume total des produits chargés dans une tournée effectuée par un véhicule k soit
inférieure à la capacité maximale du véhicule en termes de poids et de volume. La
contrainte (20) assure que la durée totale d’une tournée 𝑟 = (𝑙,𝑘, 𝑆) soit inférieure ou égale
à la durée maximale d’opération permise pour le véhicule k correspondant. Cette contrainte
28
permet également de lier les variables de chargement 𝑦𝑟𝑗𝑖 aux variables de tournées 𝑥𝑟. Par
conséquent, si une tournée r n’est pas sélectionnée (𝑥𝑟 = 0), toutes les variables de
chargement correspondantes sont nulles. La contrainte (21) fixe la borne supérieure du
temps de distribution (accès maximum) pour tous les clients à LMax. La contrainte (22)
assure qu’un véhicule k soit utilisé par une et une seule tournée. Finalement, la contrainte
(23) définis la nature des variables de décision du modèle.
Le modèle développé par Berkoune et al. (2011), suppose qu’un point de demande a la
possibilité d’être livré par plusieurs routes différentes (split delivery). Par ailleurs, les
auteurs ont recommandé de limiter le nombre de fois qu’un point de demande est livré afin
d’alléger la gestion des opérations de collecte et de livraison et de réduire le nombre
d’accès à certaines zones très touchées ou à risque. Dans ce cas de figure, ils préconisent de
rajouter au modèle présenté précédemment la contrainte suivante :
�𝛽𝑟𝑖𝑥𝑟𝑟∈𝑅
≤ 𝑁𝑖 ∀𝑖 ∈ 𝐼 (24)
où 𝑁𝑖 représente le nombre maximum de visites permises pour un point de livraison i.
3.3. Conclusion
Dans ce chapitre, nous avons défini la problématique abordée. Puisque le problème traité se
ramène à une variante du Problème de Tournées de Véhicules (VRP) dans un contexte
d’urgence, nous avons défini en détail les principales composantes liées à cette
problématique. Par la suite, nous avons présenté le modèle mathématique (P) proposé par
Berkoune et al. (2011) sur lequel nous avons basé notre travail. Le chapitre suivant sera
dédié à la définition de l’approche de résolution développée ainsi qu’aux améliorations
proposées pour améliorer la qualité de la solution obtenue.
30
CHAPITRE 4
APPROCHES DE RÉSOLUTION
Ce chapitre sera consacré à la définition détaillée de l’approche heuristique proposée par
Berkoune et al. (2011). Ensuite, nous exposerons les différentes méthodes que nous avons
adoptées pour résoudre le problème. Nous verrons plus loin que les méthodes que nous
proposerons dérivent d’une même approche, dite approche de base, chaque méthode
modifiant quelques petits ingrédients de cette approche. Dans ce qui suit, nous
commençons par présenter l’approche de Berkoune et al. (2011). Ensuite, nous détaillerons
notre approche de base et nous finirons par présenter les différents méthodes qui en
dérivent.
Les méthodes proposées visent à améliorer la qualité de la solution obtenue avec l’approche
heuristique proposée par Berkoune et al. (2011). Ces améliorations sont basées sur la
variation de l’ensemble de routes semi-réalisables générées dans chaque itération. En effet,
nous proposons dans le présent travail des approches basées sur une méthode itérative de
31
type recherche locale. Ces méthodes consistent généralement à élargir le nombre de
tournées semi-réalisables d’une itération à l’autre, puis l’introduction et la résolution de
l’ensemble des tournées vides générées jusqu’à la dernière itération, ce qui entraine une
amélioration en terme de la qualité des solutions obtenues.
4.1. Approche heuristique proposée par Berkoune et al. (2011)
Rappelons que l’objectif principal du présent travail est l’amélioration de la solution
obtenue avec l’approche heuristique proposée par Berkoune et al. (2011). Les auteurs ont
développé une méthode heuristique composée de deux étapes. La première étape consiste
en une énumération restreinte des tournées semi-réalisables (ou vides) basée sur la méthode
de balayage. La deuxième permet le chargement et la sélection simultanée des meilleures
routes réalisables en utilisant un modèle linéaire mixte en nombres entiers (P). Les
notations et le modèle (P) qui ont été détaillés dans le chapitre précédent, seront utilisés
dans la description de l’approche proposée par Berkoune et al. (2011) et celle que nous
avons développée.
4.1.1. Étape 1 : Énumération partielle
Cette approche permet l’énumération partielle des tournées semi-réalisables en se basant
sur la méthode de balayage. Elle permet de restreindre le nombre de sous-ensembles de
l’ensemble de points de demande pouvant être atteints à partir d’un CDAH donné.
Rappelons qu’une tournée semi-réalisable (l, k, S) est définie par : (1) son CDAH d’origine
l, (2) le véhicule k (parmi ceux disponibles au CDAH) auquel elle est affectée et (3) la
séquence des points de livraison 𝑆 qu’elle visite. Les tournées générées sont des
tournées vides et tiendront compte uniquement des temps de déplacement (sans chargement
et déchargement). Ces temps seront pris en considération pour générer des tournées avec
des durées totales qui respectent les contraintes sur les durées maximales (i.e., les Dk). Pour
respecter la contrainte sur le temps d’accès maximum (𝑇), les points de livraison d’une
tournée sont limités à ceux pouvant être visités en un temps inférieur ou égal au temps
d’accès maximum 𝑇 pré-spécifié.
32
Pour décrire l’algorithme d’énumération, les notations suivantes ont été adoptées:
Il : l’ensemble des points de demande pouvant être atteints à partir du CDAH l en
un temps inférieur ou égal au temps d’accès maximum 𝑇 avec un voyage direct
(𝐼𝑙 = {𝑖 ∈ 𝐼: 𝑡𝑙𝑖 ≤ 𝑇}) ;
𝐼𝑙𝑢 : un sous-ensemble non vide de Il ;
𝑆𝑙𝑢 : la séquence optimale de visite des points dans 𝐼𝑙𝑢 qui minimise le temps
d’accès maximal au dernier point visité dans 𝐼𝑙𝑢 (en tenant compte uniquement
des temps de déplacement).
L’algorithme d’énumération partielle est alors décrit comme suit :
Pour chaque CDAH l ϵ L
1. Déterminer l’ensemble 𝐼𝑙 ;
2. Ordonner les éléments de 𝐼𝑙 dans un ordre croissant par rapport à leurs
coordonnées polaires. Soit 𝐼𝑙𝑜𝑟𝑑cet ensemble ordonné ;
3. Définir tous les sous-ensembles non vides 𝐼𝑙𝑢,𝑜𝑟𝑑(𝑢 = 1, . . , |𝐼𝑙|!) de 𝐼𝑙𝑜𝑟𝑑 incluant
m (m=1,…,|𝐼𝑙|) éléments consécutifs de 𝐼𝑙𝑜𝑟𝑑;
4. Pour chaque sous-ensemble 𝐼𝑙𝑢,𝑜𝑟𝑑, déterminer la séquence optimale de visite des
clients (départ du dépôt et retour au dépôt) qui permet de minimiser le temps
d’accès maximal au dernier point visité parmi ces clients (en tenant compte
uniquement des temps de déplacement). Ce problème se ramène à la résolution
d’un TSP à l’ensemble 𝐼𝑙𝑢,𝑜𝑟𝑑.
Soit 𝑆𝑙𝑢 la séquence optimale ainsi obtenue. Si la séquence 𝑆𝑙𝑢 respecte la
contrainte sur le temps d’accès maximum, retenir cette séquence ; sinon la rejeter ;
5. Pour chaque véhicule k se trouvant au CDAH l (k ∈ Kl), et pour chaque séquence
𝑆𝑙𝑢 retenue à l’étape 4, générer la tournée (𝑙,𝑘, 𝑆𝑙𝑢) si la séquence 𝑆𝑙𝑢 respecte la
durée maximale de tournée tolérée pour le véhicule k.
33
4.1.2. Étape 2 : Chargement et sélection des tournées
Cette étape permet le chargement et la sélection simultanés des tournées semi-réalisables
générées avec l’algorithme d’énumération partielle. Une solution est obtenue en résolvant
le modèle (P) restreint à ces routes.
4.2. Motivations
Dans leur travail, Berkoune et al. (2011) ont conclu que l’approche exacte proposée est
capable de résoudre les problèmes de petite taille à l’optimalité en des temps relativement
courts. Cependant, une énumération complète de toutes les routes ne serait pas envisageable
lorsque le nombre de tournées semi-réalisables est grand. Plus encore, dans un contexte de
livraison partagée (split delivery), le nombre de routes admissibles est susceptible
d’exploser rapidement. De ce fait, les auteurs ont proposé une approche heuristique basée
sur la méthode de balayage et qui est développée dans le but de restreindre l’ensemble de
tournées générées dans la première étape et par conséquent minimiser le temps requis pour
résoudre le modèle (P). Les auteurs ont conclu que l’approche heuristique paraît
prometteuse lorsque la taille des problèmes devient plus importante. Ils ont suggéré aussi
d’effectuer une étude expérimentale plus poussée pour appuyer de telles affirmations. Or,
tel qu’on va le voir dans notre étude expérimentale, l’heuristique proposée par Berkoune et
al. (2011), bien que relativement peu coûteuses en termes de temps de calcul, peut résulter
en des solutions de mauvaise qualité. Nous avons également remarqué que dans plusieurs
cas ceci ne vient pas du fait que le modèle (P) de la deuxième étape n’est pas résolu à
l’optimalité mais plus du fait que l’ensemble des routes semi-réalisables passé au modèle
est de qualité médiocre.
Étant donnée ces observations, nous proposons dans le présent travail un algorithme de
résolution permettant l’amélioration d’une solution initiale réalisable, obtenue à partir de
l’approche heuristique basée sur la méthode de balayage déjà développée par Berkoune et
al. (2011). Cette amélioration se situe au niveau de la mise à jour de l’ensemble des routes
semi-réalisables. En effet, l’approche proposée permet l’énumération des routes semi-
réalisables prometteuses, autres que les routes déjà créées avec l’énumération partielle de
Berkoune et al. (2011), en utilisant une boucle répétitive qui sert à élargir le nombre de
34
tournées vides d’une itération à l’autre. L’ensemble de tournées mis à jour est par la suite
injecté dans le modèle (P) afin de charger et de sélectionner les meilleures tournées
réalisables.
4.3. Approche de base
Rappelons que l’objectif du VRP-RS consiste à produire des tournées réalisables à partir
des CDAH(s) vers les différents points de demande afin de satisfaire leurs besoins en
produits et services dans les plus courts délais possible. Chaque tournée générée doit
respecter les contraintes de capacité et de durée relatives au véhicule auquel elle est
affectée. En effet, ces contraintes dépendent du type du véhicule utilisé, de la nature et de la
quantité du produit livré par cette tournée (temps de chargement et déchargement), et des
emplacements du point origine (le CDAH) et des points de livraison (les clients) constituant
la tournée.
Le diagramme de la Figure 3 résume les différentes étapes de l’approche de base proposée.
35
Lecture de données
Étape 1.1 :Énumération partielle
Étape 1.2 :Chargement et sélection des tournées
Condition d’arrêt est vérifiée
Non
FinOui
Admissibilité du client est vérifiée
Étape 2.3 :Sélection d’une nouvelle routeNon
Étape 2.2 :Énumération exhaustive conditionnelle
Oui
Étape 2.1 :Sélection de la 1ère route
Figure 3 : Différentes étapes de la méthode de résolution
Notre approche de résolution est composée de deux phases. Une première phase qui
consiste à générer une solution initiale et une deuxième phase qui a pour but l’amélioration
itérative de la solution courante. Quand la procédure est lancée, les étapes (1.1) et (1.2)
permettent la génération d’une solution initiale réalisable. Dans nos expérimentations, la
solution initiale est construite en utilisant l’approche heuristique développée par Berkoune
36
et al. (2011). Ensuite, à une itération donnée, deux principales étapes sont exécutées : la
première étape consiste en ce que nous avons appelé ‘’énumération exhaustive
conditionnelle (2.2)’’. Nous détaillerons cette étape dans ce qui suit mais grosso modo elle
vise à mettre à jour l’ensemble des routes semi-réalisables considérées dans la solution
courante selon certaines règles. La deuxième étape est identique à la 2ème phase de
l’approche proposée par Berkoune et al. (2011) et consiste en la résolution du modèle (P)
en se restreignant à l’ensemble des tournées mis à jour à l’étape précédente. Le critère
d’arrêt et les différentes étapes seront détaillés ci-dessous.
4.3.1. Critère d’arrêt
Dans notre algorithme de résolution, nous avons opté pour un critère d’arrêt basé sur le
temps d’exécution maximal, noté TMax. Ce choix s’aligne bien avec le contexte d’urgence
traité où le preneur de décision dispose d’une certaine marge de temps pour proposer des
alternatives de distribution de l’aide humanitaire. Si le temps d’exécution total atteint TMax
alors la boucle prend fin, sinon on passe à l’itération suivante. Il est à noter que lors de nos
expérimentations, l’atteinte de ce temps maximal est vérifiée avant d’entamer la résolution
du modèle (P). Par conséquent, la durée cumulée de résolution pourrait dépasser TMax si la
résolution du modèle (P) prend trop de temps. Cette façon de faire pourrait être modifiée
dans le code pour arrêter la résolution du modèle (P) dès que le temps cumulé dépasse TMax.
Dans ce cas, on pourrait se retrouver sans aucune solution réalisable et on serait alors obligé
de retenir la solution de l’itération précédente.
Dans notre plan d’expérience, nous avons d’abord fixé la valeur de TMax à 1 heure. Afin de
valider ce choix, nous avons étudié l’effet de la variation de la valeur de TMax sur la qualité
de la solution obtenue. Nous avons aussi testé la pertinence de considérer une autre
condition d’arrêt basée sur le nombre d’itérations sans amélioration de la solution. Nous
reviendrons sur ces points plus en détail au chapitre 5.
4.3.2. Les étapes de l’approche proposée
Cette section permet la description de différentes étapes qui définissent l’algorithme
proposé.
37
4.3.2.1. Lecture des données
La lecture des données se fait à partir d’un fichier de type XML, les données récupérées
sont : les coordonnées des CDAH(s) et des clients, les demandes de chaque client, le type
de produit demandé (volume, poids), les produit disponibles dans les CDAH(s), le type de
véhicules nécessaires pour transporter les produits vers les points de demande, le nombre
de véhicules disponibles dans chaque CDAH, les temps de chargement et déchargement
associés à chaque type de véhicule, et la capacité en poids et en volume de chaque type de
véhicule.
4.3.2.2. Phase 1 : Construction d’une solution initiale
La phase de construction permet la création d’une solution initiale afin d’amorcer le
lancement de la phase d’amélioration. Cette phase correspond à la méthode heuristique
développée par Berkoune et al. (2011) telle que décrite à la section 4.1.
4.3.2.3. Phase 2 : Boucle d’amélioration
Cette deuxième phase constitue une boucle itérative permettant l’amélioration de la
solution obtenue à la phase précédente. Nous allons détailler les principales étapes de cette
phase à une itération n.
Étape 2.1 : Sélection de la 1ère route
Puisque notre objectif est de minimiser LMax, qui représente la durée de distribution
maximale, on calcule après l’étape de chargement et de sélection avec le modèle (P) de
l’itération n-1, l’écart entre le temps de distribution jusqu’au dernier client de chaque route
sélectionnée et la valeur de LMax. Ensuite, on détermine l’ensemble de tournées semi-
réalisables qui ont un écart nul, en d’autres termes, les routes qui ont engendré cette valeur
de LMax. Finalement, on prend en considération, au début de l’itération n, seulement la
première tournée r = (l, k, S) qui apparaît dans l’ensemble déjà déterminé. À partir de la
tournée en question, on sélectionne le CDAH l à partir duquel l’aide sera acheminée et le
dernier client i qui apparaît dans la séquence S.
38
Figure 4 : Exemple de sélection de routes
La Figure 4 représente un exemple illustratif qui explique la méthode de sélection de la
route qui détermine la valeur de LMax (la route qui a un écart égale à zéro). En effet, la
droite en rouge et les rectangles en bleu représentent respectivement la valeur de LMax et
celle du temps de distribution maximal pour chaque route (X). Ce temps de distribution
représente le temps nécessaire pour accéder au dernier client à servir et cela pour chaque
route (X1 ... X11) sélectionnée et chargée pendant cette même étape. D’après la Figure 4, la
route ‘X6’ ayant pour paramètres (l, k, S) est la route qui détermine la valeur de LMax. Il
convient noter qu’on peut avoir à une itération quelconque plusieurs routes qui déterminent
la valeur de LMax. Dans ce cas, un choix arbitraire est fait.
Test : Admissibilité du client
À l’itération n, et une fois que la première route (avec un écart nul) est déterminée après
l’étape de chargement et de sélection à savoir l’étape finale de l’itération n-1, on récupère
les paramètres (l, k, S) de la route en question, puis on sélectionne le dernier client de la
séquence, S, ainsi que le CDAH, l, associé. Ce client, noté i dans ce qui suit, est alors
admissible, si et seulement si, il existe encore un CDAH qui peut le couvrir. Deux cas de
figure peuvent se présenter : (1) le client i est sélectionné pour la première fois, dans les n-1
05
10152025303540455055606570
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
Seco
ndes
Routes
LMax
39
itérations précédentes de l’approche. Dans ce cas, on garde le même CDAH l, déterminé
initialement. (2) le client i a déjà été sélectionné dans les n-1 itérations précédentes. Dans
ce cas, on choisit le CDAH l’ le plus proche qui soit capable de couvrir le client i. le CDAH
l’ doit être différent des CDAH(s) déjà sélectionnés pendant les itérations précédentes.
Dans le cas où le test d’admissibilité du client est valide, on passe à l’étape d’énumération
exhaustive conditionnelle. Dans le cas contraire, i.e., tous les CDAH(s) capables de servir
le client i sont épuisés, on passe à l’étape de sélection d’une nouvelle route (étape 2.3).
Étape 2.2 : Énumération exhaustive conditionnelle
Étant donnée une route r=(l, k, S), un client i admissible et un CDAH l’ (qui peut être le
même que l) tels que fournis par l’étape précédente 2.1, l’étape 2.2 consiste à énumérer un
ensemble de nouvelles routes semi-réalisables visitant le client i à partir du CDAH l’. Ces
routes sont nouvelles dans la mesure où elles ne figurent pas dans l’ensemble R des routes
semi-réalisables considéré par le modèle (P) à l’itération courante. Soit :
Il’ : l’ensemble des points de demande qui peuvent être atteints à partir du CDAH
l’ en un temps inférieur ou égal au temps d’accès maximum 𝑇 avec un voyage
direct (𝐼𝑙′ = {𝑖′ ∈ 𝐼: 𝑡𝑙′𝑖 ,≤ 𝑇}). Notons que cet ensemble contient
obligatoirement le point i.
𝐼𝑙′𝑖𝑢 : un sous-ensemble non vide de Il’ qui contient le client i;
𝑆𝑙′𝑖𝑢 : la séquence optimale de visite des points dans 𝐼𝑙′𝑖𝑢 qui minimise le temps
d’accès maximal au dernier point visité dans 𝐼𝑙′𝑖𝑢 (en tenant compte uniquement
des temps de déplacement).
Pour un CDAH l’ et un client i donnés
1. Déterminer l’ensemble 𝐼𝑙′ ;
2. Déterminer tous les nouveaux sous-ensembles 𝐼𝑙′𝑖𝑢 : ces sous-ensembles ne peuvent
pas contenir des tournées déjà créées durant les itérations précédentes. En fait, vu
notre test d’admissibilité du client (étape 2.1), il suffit de garantir que lorsqu’un
client et un CDAH sont sélectionnés pour la première fois, les ensembles générés
40
sont différents de ceux considérés dans la solution initiale. Pour ce faire, nous avons
utilisé la méthode suivante :
i. Ordonner les éléments de 𝐼𝑙′𝑖 dans un ordre croissant par rapport à leurs
coordonnées polaires ;
ii. Déterminer la position p du client i, le client i-1 immédiatement en amont et le
client i+1 immédiatement en aval ;
iii. Éliminer tous les sous-ensembles contenant les clients i-1, i et i+1.
3. Pour chaque sous-ensemble 𝐼𝑙′𝑖𝑢 , déterminer la séquence optimale 𝑆𝑙′𝑖𝑢
correspondante. Ce problème se ramène à la résolution d’un TSP restreint à
l’ensemble 𝐼𝑙′𝑖𝑢 . Si la séquence 𝑆𝑙′𝑖𝑢 respecte la contrainte sur le temps d’accès
maximum, retenir cette séquence ; sinon la rejeter.
4. Pour chaque véhicule k se trouvant au CDAH l’ (k ∈ Kl’), et pour chaque séquence
𝑆𝑙′𝑖𝑢 retenue à l’étape 3, générer la tournée (𝑙′,𝑘, 𝑆𝑙′𝑖𝑢 ) si la séquence 𝑆𝑙′𝑖𝑢 respecte la
durée maximale de tournée tolérée pour le véhicule k.
Étape 2.3 : Sélection d’une nouvelle route
Cette étape est déclenchée dans le cas où il n’existe plus de nouvelle route servant le client
i. Autrement dit, toutes les routes visitant i ont déjà été incorporées à l’ensemble R
considéré par le modèle (P). Dans ce cas, on sélectionne la route suivante qui apparaît dans
l’ensemble de routes caractérisées par un écart nul entre leur durée de distribution maximal
et la valeur optimale de LMax. Puis, on récupère les différents paramètres de la nouvelle
route (l’, k’, S’), on effectue le test d’admissibilité du client pour le client i’ retenu à partir
de la route (l’, k’, S’), etc. Dans le cas où le test d’admissibilité échoue pour toutes les
routes ayant une durée de distribution maximale égale à la valeur optimale de LMax,
l’algorithme prend fin et on retient la dernière solution obtenue.
Dans ce qui suit, nous présentons différentes variantes de l’approche de base obtenues en
variant certains paramètres. Le but est de voir si des améliorations sont possibles.
Rappelons que la procédure d’énumération exhaustive conditionnelle, proposée dans
l’approche de base développée, consiste à générer toutes les tournées semi-réalisables qui
41
doivent partir d’un CDAH donné et visiter obligatoirement un client prédéterminé. Afin
d’améliorer cette approche de génération de routes, nous exposons trois autres méthodes.
Les deux premières méthodes permettent d’élargir la taille de l’ensemble des routes
générées à chaque itération : dans ce cas on obtiendrait des modèles (P) de plus grande
taille à la phase 2 mais on serait peut être capable d’améliorer la qualité de la solution plus
rapidement. La troisième méthode évite de se retrouver avec des modèles (P) de trop
grandes tailles au fil des itérations en se débarrassant des tournées qui n’ont pas été
retenues dans une solution optimale du modèle (P) pendant un certain nombre d’itérations.
Dans la suite de ce rapport, nous allons définir la Variante 1 (D), la Variante 2 (E) et la
Variante 3 (F) comme étant la première, la deuxième et la troisième variante de l’approche
de base que nous avons développée.
4.4. Variantes de l’approche de base
Dans cette section, nous allons proposer trois variantes de l’approche de base que nous
avons développée. Ces variantes représentent un ensemble de changements sur l’approche
de base, dans le but d’améliorer cette dernière. En effet, nous avons opté à élargir
graduellement le nombre de routes générées pendants l’étape d’énumération pour les
variantes 1 et 2. Par ailleurs pour la variante 3, nous avons ajouté une nouvelle étape
permettant de restreindre l’ensemble des routes semi-réalisables dans certaines itérations de
l’approche de base.
4.4.1. Variante 1
Pour cette variante, le changement au niveau de l’approche de base se situe au niveau de
l’étape (2.2.) d’énumération exhaustive conditionnelle. Dans l’approche de base, nous
exigeons que les nouvelles routes générées pour un client i admissible commencent à partir
d’un seul CDAH admissible. Pour cette variante 1, nous proposons d’énumérer toutes les
routes semi-réalisables qui partent de tous les CDAH(s) admissibles pour le client i.
Formellement, les changements apportés à l’approche de base se situent au niveau du test
d’admissibilité du client et de l’étape de chargement et de sélection.
42
Test d’admissibilité du client
À l’itération n, et une fois la première route r = (l, k, S) (avec un écart nul) est déterminée
après l’étape de chargement et de sélection à l’itération n-1, on sélectionne le dernier client
i de la séquence, S. Ce client est alors admissible, si et seulement si, il apparaît pour la
première fois pendant les n-1 itérations. Dans le cas où le test d’admissibilité du client est
valide, on passe à l’étape d’énumération exhaustive conditionnelle. Dans le cas contraire,
c’est-à-dire le client a déjà été sélectionné durant les n-1 itérations précédentes, on passe à
l’étape de sélection d’une nouvelle route.
Étape 2.2 : Énumération exhaustive conditionnelle
L’étape d’énumération exhaustive conditionnelle est déclenchée lorsque le client
sélectionné i est admissible. L’étape est décrite comme suit :
Pour tous CDAH(s) l capables de livrer i
1. Déterminer l’ensemble 𝐼𝑙 ;
2. Déterminer tous les sous-ensembles 𝐼𝑙𝑖𝑢 : ces ensembles ne peuvent pas contenir des
tournées déjà crées pendant la première itération (l’algorithme énumération
partielle). Pour ce faire, nous avons utilisé la même méthode que pour l’approche de
base.
3. Pour chaque sous-ensemble 𝐼𝑙𝑖𝑢, déterminer la séquence optimale 𝑆𝑙𝑖𝑢 correspondante.
Ce problème se ramène à la résolution d’un TSP restreint à l’ensemble 𝐼𝑙𝑖𝑢. Si la
séquence 𝑆𝑙𝑖𝑢 respecte la contrainte sur le temps d’accès maximum, retenir cette
séquence ; sinon la rejeter.
4. Pour chaque véhicule k se trouvant au CDAH l (k ∈ Kl), et pour chaque séquence 𝑆𝑙𝑖𝑢
retenue à l’étape 3, générer la tournée (𝑙,𝑘, 𝑆𝑙𝑖𝑢) si la séquence 𝑆𝑙𝑖𝑢 respecte la durée
maximale de tournée tolérée pour le véhicule k.
4.4.2. Variante 2
Rappelons que dans l’approche de base, nous calculons l’écart entre LMax et la durée de
distribution de chaque tournée chargée à la fin de l’étape de chargement et de sélection de
43
chaque itération. Ensuite, nous sélectionnons la première route (l, k, S) parmi les routes qui
ont un écart nul. Dans cette Deuxième variante de l’approche de base, nous proposons de
sélectionner les deux premières routes qui apparaissent dans l’ensemble des tournées ayant
un écart nul (si la deuxième route existe). Puis, pour chacune de deux routes, nous générons
toutes les tournées semi-réalisables partantes de tous les CDAH(s) et qui visitent le client
sélectionné (donc le même principe que la variante 1). Il est important de noter que dans
certaines itérations, on trouve plus que deux routes ayant un écart nul. Nous avons choisi de
nous limiter aux deux premières routes dans le but d’augmenter graduellement la taille des
modèles (P). Les changements apportés à la Première variante se situent au niveau de
l’étape d’énumération exhaustive conditionnelle.
4.4.3. Variante 3
Cette variante consiste à restreindre l’ensemble des routes semi-réalisables à certaines
itérations de l’approche de base. Les routes vides à supprimer ne doivent pas figurer dans
l’ensemble des tournées définissant la solution obtenue avec le modèle (P), pendant un
grand nombre d’itérations. Ceci permet la réduction du nombre de tournées semi-
réalisables et par conséquent la diminution du temps requis pour résoudre le modèle (P). Le
changement par rapport à l’algorithme de résolution présenté à la section (4.3.) se situe au
niveau de l’ajout d’une nouvelle étape ‘Suppression des tournées vides’ après l’étape
d’énumération exhaustive conditionnelle tel qu’illustré à la Figure 5.
44
Lecture de données
Étape 1.1 :Énumération partielle
Étape 1.2 :Chargement et sélection des tournées
Condition d’arrêt est vérifiée
Non
FinOui
Admissibilité du client est vérifiée Étape 2.3 :Sélection d’une nouvelle routeNon
Étape 2.2 :Énumération exhaustive conditionnelle
Oui
Étape 2.1 :Sélection de la 1ère route
Étape 2.4 :Suppression des tournées vides
Figure 5 : Diagramme de la Troisième variante
45
Étape 2.4 : Suppression des tournées vides
Cette étape consiste à éliminer un sous-ensemble des routes vides qui n’apparaissent pas
dans les tournées définissant la solution obtenue pendant un grand nombre d’itérations.
Nous avons choisi un nombre Nb_Min = 3 itérations, qui définit le nombre minimum
d’itérations au-delà duquel les routes peuvent être supprimées. De plus, nous avons opté à
éliminer, pendant la même itération, un nombre de routes à éliminer Nb_Elim = 0,1*Card
(sous-ensemble de tournées semi-réalisables mis à jour pendant l’itération n). Card
(cardinalité) représente le nombre d’occurrences (aucune, une ou plusieurs) d’une entité. Le
choix de ces deux paramètres était arbitraire. Par ailleurs, nous ne pouvons pas éliminer
toutes les routes, car on risque de détruire le domaine de recherche de notre problème et par
conséquent on ne peut pas améliorer davantage la solution obtenue. L’étape est décrite
comme suit :
Soit Un : l’ensemble de tournées qui n’apparaissent pas dans les tournées définissant la
solution obtenue à l’itération n plus que Nb_Min fois (c’est un tableau dont les indices sont
compris entre 0 et (Card (Un) -1)).
1. Déterminer l’ensemble Un ;
2. Générer Nb_Elim nombres aléatoires entre 0 et (Card (Un) -1) ;
3. Éliminer les tournées qui ont des indices dans le tableau Un égales aux nombres
générés aléatoirement de l’ensemble de routes initialement ;
4. Mettre à jour l’ensemble de routes semi-réalisables.
4.4. Conclusion
L’approche de résolution de base proposée et ses différentes variantes proposent des pistes
d’amélioration d’une solution initiale réalisable telle que proposée avec l’approche
heuristique de Berkoune et al. (2011). Cette amélioration peut être obtenue à travers la
modification de la procédure de génération des routes semi-réalisables. Les méthodes
proposées sont basées sur un processus itératif qui permet d’élargir efficacement
l’ensemble de tournées semi-réalisables. Dans le prochain chapitre, nous exposerons les
résultats numériques obtenus à partir des approches proposées. Nous procèderons ensuite à
46
une évaluation comparative de nos résultats avec ceux obtenus à partir des algorithmes
proposés par Berkoune et al. (2011). Cette étude comparative sera élaborée à travers un
plan d’expérience basé sur des instances choisies aléatoirement du travail de Berkoune et
al. (2011).
48
CHAPITRE 5
RÉSULTATS ET EXPÉRIMENTATION
Rappelons que le but principal de ce projet de maîtrise est de proposer une approche de
résolution capable d’améliorer la qualité de la solution obtenue avec la méthode heuristique
développée par Berkoune et al. (2011). Les différentes étapes de l’approche heuristique
proposée par Berkoune et al. (2011) ainsi que les phases de l’approche que nous avons
proposée, que ce soit dans sa version de base ou dans ses variantes, ont été détaillées dans
le chapitre précèdent. Afin d’évaluer la qualité de la solution obtenue avec les méthodes
proposées, nous proposons dans ce chapitre des séries d’expérimentations basées sur des
problèmes tests.
Nous procèderons dans un premier temps à étudier l’effet du nombre de split sur la qualité
de la solution et les temps de résolution. Tel que discuté au chapitre 3, il pourrait être
bénéfique dans certains cas de limiter le nombre de visites à un client donné afin de faciliter
la gestion des opérations de livraison, réception entreposage, etc. Pour les approches de
49
résolution discutées dans ce document, cela se fait en ajoutant une contrainte au MIP de la
2ème phase (cf Chapitre 3). L’étude de l’impact du nombre de split se fera pour notre
approche de base.
En un deuxième temps, nous étudierons l’impact de la variation de la condition d’arrêt sur
la performance de l’approche de base. Pour cela, nous considérons deux critères d’arrêt : le
temps de résolution maximal et le nombre d’itérations sans amélioration de la solution. Par
la suite, nous présenterons un plan d’expériences comparatif entre les différentes variantes,
afin de déterminer la meilleure approche de résolution. Ensuite, nous allons comparer la
meilleure variation et l’approche de base proposées aux deux approches développées par
Berkoune et al. (2011) à savoir l’approche exacte et l’approche heuristique. La
comparaison se fera au niveau: (1) de la qualité de la solution obtenue et, (2) du temps de
résolution.
5.1. Matériels de développement utilisés
La plateforme utilisée pour le développement notre algorithme fut Microsoft Visual Studio
2010, version 4.0 et CPLEX 12.0 a été utilisé pour la résolution des modèles
mathématiques.
Afin d’évaluer les algorithmes, nous avons utilisé un PC avec les caractéristiques
suivantes :
• Système d’exploitation : Windows 7 professionnel (SP1) ;
• Processeur : Intel Core 2 Duo @ 3.00 GHz ;
• Mémoire RAM : 4 Gb ;
• Type de système : 64 bits.
5.2. Problèmes tests
Pour mener à terme notre étude expérimentale, nous avons fait appel à des problèmes tests
aléatoires développés par Berkoune et al. (2011) et pour lesquels une solution optimale est
connue (méthode exacte de Berkoune et al. (2011)). Pour chaque instance, nous avons les
informations suivantes : le nombre de CDAH (|L|= {2, 3, 4, 5}), le nombre de véhicules
50
disponibles par CDAH (|Kl|= {2, 3, 4, 5}), les points de livraison (|I|= {15, 20, 25}) et les
types de produits (|J|= 2). Il est aussi important de signaler que le temps de chargement et
de déchargement d’une unité de produit est supposé dépendant du type de véhicule et de
produit. Dans ce qui suit, chaque ensemble d’instances est représenté par la paire (|L|, |I|).
Au total, nous avons sélectionné 27 problèmes tests (colonne ‘ELDS’) du travail de
Berkoune et al. (2011). En effet, nous avons choisi arbitrairement neuf paires distinctes de
problèmes (|L|, |I|), ensuite nous avons sélectionné 3 instances différentes pour chaque
paire. Chacun des 27 problèmes a été résolu en limitant le nombre de visites par route à 3
puis à 4, ce qui donne un total de 54 problèmes. Le Tableau 1 résume les paramètres de
chaque instance utilisée.
Tableau 1 : Paramètres des instances
ELDS (|L|, |I|) |Kl| 1
(2, 15) 5
2 5 3 5 4
(3, 15) 4
5 2 6 2 7
(3, 20) 3
8 3 9 3 10
(4, 15) 4
11 5 12 3 13
(4, 20) 5
14 5 15 2 16
(4, 25) 3
17 3 18 3 19
(5, 15) 2
20 2 21 2 22
(5, 20) 2
23 2 24 2 25 (5, 25) 4
51
26 4 27 3
Il convient de noter que le nombre de clients visités au maximum par une tournée ne
dépasse pas quatre. Par conséquent, les problèmes de TSP (l’étape de génération de routes)
peuvent être résolus à l’optimalité par une simple énumération de toutes les séquences
possibles.
5.3. Étude de l’impact du nombre de split
Dans cette section, nous proposons d’étudier l’effet de la variation du nombre de split sur la
qualité de la solution obtenue. Cette évaluation de la qualité de la solution obtenue sera
basée sur une série d’expérimentations comparatives entre les deux approches proposées
par Berkoune et al. (2011) et l’approche de base que nous avons développée. Le but
principal de cette étude est de déterminer le nombre de split qui offre le bon compromis
temps de résolution/ qualité de la solution. Ce nombre sera fixé par la suite pour le reste de
notre étude expérimentale.
Rappelons que le split représente le nombre de livraisons faites pour un client donné. Afin
d’étudier l’effet de la variation de ce paramètre sur les performances de l’approche
développée, nous avons sélectionné un ensemble d’instances (5, 11, 13 et 25) qui sont
résolues à l’optimalité avec la Méthode exacte. Ensuite, nous avons fait varier, pour chaque
instance, le paramètre Split entre les valeurs 1, 2, 3 et 4. La valeur 1 signifie qu’aucun split
n’est autorisé, une valeur de 2, respectivement, 3 et 4, suppose que le client peut être visité
par 2, respectivement, 3 et 4, tournées différentes. Le Tableau 2 illustre les résultats obtenus
en termes de qualité de solution.
Dans le Tableau 2, la colonne ‘Nb_Rte’ représente le nombre des routes générées dans
toutes les itérations. En effet, dans l’approche que nous avons proposée, le nombre de
routes générées est mis à jour à chaque itération, contrairement aux approches développées
par Berkoune et al. (2011) où les routes sont générées seulement à la première étape (la
colonne ‘Nb_Rte’ représente le nombre de routes générées dans la première étape). La
colonne ‘Sol’ donne la valeur de la fonction-objectif donnée dans la deuxième étape par
CPLEX au bout d’un temps limite de résolution de 3600 seconds. L’écart d’optimalité
52
correspondant à chaque solution obtenue tel que fourni par CPLEX est représenté à la
colonne ‘Gap’. Par définition, l’écart d’optimalité est calculé par rapport à la meilleure
borne inférieure. Ces trois statistiques sont obtenues pour chaque instance et chaque
méthode de résolution. Les colonnes ‘ ( ) /C A A− ’ et ‘ ( ) /C B B− ’ expriment
respectivement l’écart en pourcentage entre la solution générée par l’approche de base que
nous avons proposée (C) et celle obtenue par la méthode exacte (A) de Berkoune et al.
(2011), et entre notre approche de base et l’approche heuristique (B) de Berkoune et al.
(2011).
Dans le tableau 2, nous exposons les résultats qui illustrent l’impact de la variation du
nombre de split sur la qualité de la solution obtenue.
53
Tableau 2 : Effet de la variation du nombre de split sur la qualité de la solution obtenue
Test ELDS Max Visite Split Méthode exacte (A) Méthode heuristique (B) Approche de base (C) (C-A)/A (C-
B)/B Nb_Rte Sol Gap Nb_Rte Sol Gap Nb_Rte Sol Gap 1
5
3
1
1195
66,20 0%
119
74,38 0% 175 74,38 0% 12,37% 0,00% 2 2 66,20 0% 69,71 0% 172 68,66 0% 3,72% -1,50% 3 3 66,20 0% 69,71 0% 172 68,66 0% 3,72% -1,50% 4 4 66,20 0% 69,71 0% 172 68,66 0% 3,72% -1,50% 5
4
1
2636
66,20 0%
151
66,20 0% 158 66,20 0% 0,00% 0,00% 6 2 65,91 0,01% 66,20 0% 158 66,20 0% 0,43% 0,00% 7 3 65,91 0% 66,20 0% 158 66,20 0% 0,43% 0,00% 8 4 65,91 0,01% 66,20 0% 158 66,20 0% 0,43% 0,00% 9
11
3
1
266
48,41 0%
102
48,41 0,00% 105 48,41 0,00% 0,00% 0,00% 10 2 47,32 0% 47,32 0,00% 116 47,32 0,00% 0,00% 0,00% 11 3 47,32 0% 47,32 0,00% 122 47,32 0,00% 0,00% 0,00% 12 4 47,32 0% 47,32 0,00% 122 47,32 0,00% 0,00% 0,00% 13
4
1
324
48,41 0%
111
48,41 0,00% 114 48,41 0,00% 2,31% 0,00% 14 2 47,32 0% 47,32 0,00% 122 47,32 0,00% 0,00% 0,00% 15 3 47,32 0% 47,32 0,00% 133 47,32 0,00% 0,00% 0,00% 16 4 47,32 0% 47,32 0,00% 129 47,32 0,00% 0,00% 0,00% 17
13
3
1
447
46,86 0%
132
46,86 0,00% 138 46,86 0,00% 0,00% 0,00% 18 2 44,21 0,01% 45,81 0,00% 151 45,35 0,00% 2,57% -1,02% 19 3 44,21 0% 45,56 0,00% 152 45,28 0,00% 2,42% -0,61% 20 4 44,21 0,01% 45,56 0,00% 148 45,28 0,00% 2,42% -0,61% 21
4
1
563
46,86 0%
143
46,86 0,00% 157 46,86 0,00% 0,00% 0,00% 22 2 44,21 0,01% 45,81 0,01% 163 45,35 0,00% 2,57% -1,02% 23 3 44,21 0% 45,56 0,00% 164 45,28 0,00% 2,42% -0,61% 24 4 44,21 0,01% 45,56 0,00% 174 45,28 0,00% 2,42% -0,61% 25 25 3 1 2451 50,45 0% 278 50,45 0,00% 304 50,45 0,00% 0,00% 0,00%
54
26 2 47,54 0% 47,69 0,01% 590 47,69 0,00% 0,32% 0,00% 27 3 47,54 0% 47,69 0,01% 589 47,69 0,00% 0,32% 0,00% 28 4 47,54 0% 47,69 0,01% 312 47,69 0,01% 0,32% 0,00% 29
4
1
4529
50,45 0%
321
50,45 0,00% 363 50,45 0,00% 0,00% 0,00% 30 2 47,54 0% 47,69 0,01% 700 47,59 0,01% 0,11% -0,21% 31 3 47,54 0,01% 47,69 0,01% 751 47,59 0,00% 0,11% -0,21% 32 4 47,54 0% 47,69 0,00% 915 47,59 0,00% 0,11% -0,21%
55
D’après les résultats rapportés dans le Tableau 2, nous remarquons que l’augmentation du
nombre de visites permises pour un client (la colonne ‘Split’) permet dans certains cas de
réduire le temps de distribution maximum. Pour cela, on s’est référé au Tableau 2 à la
solution optimale fournie par la méthode exacte de Berkoune et al. (2011). Ceci est
expliqué par le fait que l’augmentation du nombre de split permet l’accroissement du
nombre d’alternatives de livraison ce qui a pour effet d’améliorer la qualité des solutions
obtenues. Cependant, on remarque que la réduction la plus importante du temps de
distribution maximum est obtenue lorsqu’on passe de la valeur 1 à 2 split.
Pour ce qui est de la performance de notre approche de base, on observe que là aussi la
qualité des solutions obtenues (en comparaison avec les deux méthodes de Berkoune et al.
(2001)) s’améliore peu en moyenne lorsque le nombre de split passe de 2 à 3 et de 3 à 4.
Dans le but mieux illustrer cela, nous présentons dans la Figure 6, le gain moyen en
pourcentage de la durée de livraison maximum obtenue avec notre approche de base par
rapport à celles obtenues avec les méthodes développées par Berkoune et al. (2011).
Figure 6 : Variation de l’écart en pourcentage en fonction du
nombre de split (3 clients/route)
Les résultats relatifs à l’impact de la variation du nombre de split sur le temps de résolution
sont résumés dans le Tableau 3.
Pour les trois approches de résolution, nous avons rapporté le temps de génération des
tournées semi-réalisables (colonne ‘Étape_1’), le temps de résolution du modèle (P) de la
-0.1%
0.0%
0.1%
0.2%
0.3%
0.4%
1 2 3 4
Nombre de split
(C-A)/A (C-B)/B
56
deuxième étape à l’intérieur du temps limite d’une heure (colonne ‘Étape_2’) et la somme
des deux temps (colonne ‘1+2’). Par ailleurs, la colonne ‘T_Sol’ exprime le temps cumulé
(incluant le temps de génération des routes et le temps de résolution du modèle P) auquel la
meilleure solution a été obtenue.
57
Tableau 3 : Effet de la variation du nombre de split sur les temps de résolution
Test ELDS (|L|, |I|) |Kl| Max Visite Split Méthode exacte (A) Méthode heuristique (B) Approche de base (C)
Étape 1 Étape 2 1+2 Étape 1 Étape 2 1+2 Étape 1 Étape 2 1+2 T_Sol 1
5 (3, 15) 2
3
1
58,8
20,9 79,8 3,0 1,0 4,0 17,1 1,6 18,7 4,0 2 2 18,3 77,2 3,4 1,3 4,7 19,9 7,6 27,5 9,0 3 3 5,7 64,6 3,4 1,2 4,5 19,9 6,8 26,7 8,9 4 4 12,3 71,1 3,4 1,0 4,4 19,9 6,9 26,7 8,4 5
4
1
862,0
47,9 909,8 8,6 0,6 9,2 289,2 1,2 290,3 9,2 6 2 1636,0 2497,9 8,6 3,7 12,3 289,0 5,4 294,4 12,3 7 3 1397,0 2258,9 8,6 2,0 10,6 288,4 3,2 291,6 10,6 8 4 1598,9 2460,8 8,6 0,7 9,3 288,9 8,9 297,7 9,3 9
11 (4, 15) 5
3
1
66,3
0,6 66,9 4,0 1,0 4,9 28,5 1,6 30,0 4,9 10 2 0,4 66,7 3,8 0,8 4,6 25,9 3,7 29,6 4,6 11 3 0,6 66,9 4,0 1,0 5,0 24,3 4,1 28,3 5,0 12 4 0,6 66,9 4,0 0,6 4,6 26,5 3,7 30,2 4,6 13
4
1
798,1
0,6 66,9 10,2 0,6 10,8 375,5 1,2 376,7 10,8 14 2 0,4 66,6 10,2 0,6 10,8 347,9 3,0 350,9 10,8 15 3 0,4 66,7 10,0 0,8 10,8 299,5 3,1 302,6 10,8 16 4 0,4 66,6 10,0 0,7 10,7 253,7 3,2 257,0 10,7 17
13 (4, 20) 5
3
1
103,2
0,8 104,0 5,2 0,8 6,0 45,3 1,6 46,9 6,0 18 2 14,7 117,9 5,0 1,4 6,3 31,5 7,2 38,7 12,4 19 3 5,8 109,1 5,2 1,5 6,6 34,8 10,9 45,7 13,0 20 4 40,1 143,3 5,0 1,5 6,5 29,0 5,9 35,0 12,7 21
4
1
1562,5
1,2 1563,7 14,0 0,6 14,6 1167,0 2,2 1169,2 14,6 22 2 21,9 1584,4 14,0 2,7 16,7 397,1 9,2 406,2 51,0 23 3 83,7 1646,2 14,0 1,8 15,8 397,7 8,8 406,5 50,8 24 4 168,8 1731,3 14,0 1,6 15,6 468,4 12,5 480,9 50,3 25 25 (5, 25) 4 3 1 475,2 17,9 493,0 9,6 0,6 10,1 100,4 1,7 102,2 50,3
58
26 2 1373,8 1849,0 9,6 119,8 129,4 146,1 1100,2 1246,2 1009,7 27 3 651,0 1126,2 9,6 152,6 162,2 157,4 1274,6 1432,0 930,2 28 4 978,2 1453,4 9,6 27,0 36,7 18,4 3627,1 3645,5 930,2 29
4
1
10406,2
128,0 10534,2 26,5 1,9 28,5 2450,8 2,7 2453,5 930,2 30 2 762,6 11168,8 26,6 29,9 56,5 2054,5 4103,6 6158,1 2119,8 31 3 63,0 10469,2 26,5 32,2 58,7 1598,4 2475,9 4074,3 4074,3 32 4 214,4 10620,6 26,7 16,0 42,7 2726,3 1035,7 3762,0 2066,5
59
Les résultats du Tableau 3 montrent que les temps nécessaires pour résoudre chacune des
approches étudiées augmentent lorsque le nombre de split augmente. De plus,
l’identification de la solution optimale devient plus difficile pour les splits de grande valeur.
En effet, l’augmentation du nombre de split permet l’accroissement du nombre
d’alternatives de livraison et par conséquent l’augmentation du temps de génération de
routes et celui de résolution du MIP.
Par ailleurs, nous remarquons que le temps nécessaire pour générer la meilleure solution
avec l’approche de base ‘T_Sol’ est presque égal au temps total de résolution avec la
méthode heuristique pour les instances de petite taille. La valeur retenue dans la colonne
‘T_Sol’ est égale à celle de la colonne (‘1+2’) de la Méthode heuristique dans le cas où la
solution obtenue par cette dernière n’est pas améliorée. Par contre lorsque la taille des
instances devient plus importante, le temps ‘T_Sol’ de l’approche de base devient plus
accentué. Ce temps demeure toujours plus faible que celui de la colonne (‘1+2’) de la
méthode exacte.
La Figure 7 représente l’impact de la variation du nombre de split sur le temps total de
génération de la meilleure solution avec l’approche de base que nous avons proposée.
Figure 7 : Variation du ‘T_Sol’ en fonction du nombre de split
0
100
200
300
400
500
600
700
0 1 2 3 4 5
Seco
nds
Split
T_Sol
60
La Figure 7 montre que le temps ‘T_Sol’ augmente lorsque le nombre de split devient plus
accentué. Par ailleurs, au-delà des trois visites permises pour un client donné, nous
remarquons que le temps de génération de la meilleure solution décroit. Ceci est dû au fait
qu’à partir d’un certain nombre de livraison permise pour un client donné, les alternatives
de chevauchements des tournées augmentent et par conséquent le modèle (P) peut être plus
facile à résoudre.
5.4. Étude de la condition d’arrêt
Dans le but de sélectionner la meilleure condition d’arrêt, nous allons étudier l’effet de la
variation de la condition d’arrêt sur les performances de la méthode que nous avons
initialement proposée. Cette étude sera subdivisée en deux parties. La première partie
portera sur l’effet de la variation du temps de résolution maximal sur les performances de
l’approche proposée en termes de qualité de la solution obtenue et de temps de résolution.
Dans la deuxième partie, nous proposons une nouvelle condition d’arrêt basée sur le
nombre d’itérations sans amélioration de la solution.
Dans le but d’alléger les temps du calcul qui deviennent rapidement excessivement élevés,
nous avons sélectionné un sous-ensemble de 10 instances sur lesquels les analyses seront
effectuées.
Tableau 4 : Paramètres de 10 instances sélectionnées
Test ELDS (|L|, |I|) |Kl| Max Visite
1 1 (2, 15) 5
3 2 3 3 3 5
(3, 15) 2 3
4 6 4 5 8 (3, 20) 3 4 6 12 (4, 15) 3 3 7 19
(5, 15) 2 3
8 20 4 9 22 (5, 20) 2 3 10 25 (5, 25) 4 3
61
Les tableaux 5 et 6 résument la solution obtenue avec les deux approches proposées par
Berkoune et al. (2011) et les temps de résolution correspondants pour les 10 instances déjà
sélectionnées. Nous allons utiliser les résultats illustrés dans ces deux tableaux afin
d’évaluer la variation des performances de l’approche que nous avons développée.
Tableau 5 : Solution obtenue avec les deux approches proposées par Berkoune et al. (2011)
Test Méthode exacte (A) Méthode heuristique (B)
Nb_Rte Sol Gap Nb_Rte Sol Gap 1 261 55,41 0,01% 65 64,4 0,01% 2 130 71,56 0,01% 47 75,36 0,00% 3 1195 66,20 0,00% 119 69,71 0,00% 4 3922 72,70 4,89% 166 76,45 0,00% 5 6441 64,75 94,78% 215 65,74 0,01% 6 811 36,24 0,00% 129 36,36 0,00% 7 359 45,08 0,00% 135 51,17 0,00% 8 945 61,34 0,00% 180 68,17 0,01% 9 848 69,40 7,01% 189 75,16 0,01% 10 2451 47,54 0,00% 278 47,69 0,01%
Tableau 6 : Temps de résolution obtenu avec les deux approches de Berkoune et al. (2011)
Test Méthode exacte (A) Méthode heuristique (B)
Étape 1 Étape 2 1+2 Étape 1 Étape 2 1+2 1 36,3 34,2 70,5 2,0 10,6 12,6 2 18,4 9,7 28,1 1,8 1,0 2,7 3 59,0 18,1 77,1 3,2 1,4 4,5 4 758,0 3600,0 4358,0 9,0 6,4 15,4 5 3058,3 3600,9 6659,2 13,8 839,4 853,2 6 73,0 769,2 842,2 4,2 2,0 6,2 7 78,1 300,4 378,5 5,3 81,6 86,8 8 1403,3 12,7 1416,0 16,4 59,1 75,5 9 249,5 3600,0 3849,6 7,2 24,5 31,7 10 474,9 1396,8 1871,7 9,3 119,8 129,1
62
5.4.1. Effet de la variation du temps de résolution maximal sur les
performances de l’approche de base
Dans le but d’étudier l’effet de variation du temps de résolution maximal sur les
performances de l’approche de base proposée, nous avons fait varier le temps de résolution
maximal dans l’intervalle [½ heure, 2 heures] avec un pas de demi-heure. L’étude
expérimentale menée sur ce critère d’arrêt montre que la variation du temps de résolution
maximal n’a pas d’effet sur la l’écart en pourcentage de la solution obtenue avec l’approche
que nous avons proposée par rapport à celle obtenue avec la méthode exacte. En effet, cet
écart reste inchangé quel que soit la valeur de la condition d’arrêt. De plus, nous avons
remarqué que le temps d’obtention de la meilleure solution est inférieur à 1800 seconds,
ceci est vrai pour toutes les valeurs du temps de résolution maximal et toutes les instances
considérées. Ce qui explique le fait que qualité de la solution obtenue ne dépende pas de la
valeur de la condition d’arrêt.
5.4.2. Effet de la variation du nombre d’itérations sans amélioration sur
les performances de l’approche base
Dans cette section, nous avons substitué la condition d’arrêt basé sur le temps de résolution
maximal par une nouvelle condition basée sur le nombre d’itérations sans amélioration de
la solution obtenue. Puis, nous allons étudier l’effet de la variation de cette condition sur les
performances de la solution obtenue par l’approche de base développée. À cet égard, nous
avons fait varier le nombre d’itérations sans amélioration dans l’intervalle [2, 5] avec un
pas unitaire. Comme la section précédente, notre étude sera jugée en fonction des solutions
générées par les approches proposées par Berkoune et al. (2011). Les tableaux 7 et 8
rapportent les résultats obtenus.
Dans le Tableau 7, nous avons ajouté deux autres colonnes à savoir la colonne ‘Itér_Amél’
et la colonne ‘Nb_Itér’, par rapport aux tableaux qui expriment la qualité de la solution. La
colonne ‘Itér_Amél’ illustre l’itération dans laquelle la meilleure solution a été enregistrée.
La colonne ‘Nb_Itér’ représente le nombre total d’itérations.
63
Tableau 7 : Effet de la variation du nombre d’itérations sans amélioration sur la qualité de la solution obtenue
Test Max_Itér Approche de base (C)
(C-A)/A (C-B)/B Nb_Rte Sol Gap Itér_Amél Nb_Itér
1
2
75 64,04 0% - 2 15,57% 0,00% 2 53 75,36 0% - 2 5,31% 0,00% 3 172 68,66 0% 1 3 3,72% -1,50% 4 837 72,71 0% 1 3 0,00% -4,89% 5 791 65,03 12% 1 3 0,42% -1,08% 6 139 36,36 0% - 2 0,32% 0,00% 7 166 48,88 0% 2 4 8,42% -4,49% 8 278 65,45 0% 4 6 6,71% -3,98% 9 195 75,03 0% 2 4 8,11% -0,17% 10 364 47,69 0% 2 4 0,32% 0,00% 1
3
75 64,04 0% - 3 15,57% 0,00% 2 53 75,36 0% - 3 5,31% 0,00% 3 172 68,66 0% 1 4 3,72% -1,50% 4 837 72,71 0% 1 4 0,00% -4,89% 5 791 65,03 0% 1 4 0,42% -1,08% 6 139 36,36 0% - 3 0,32% 0,00% 7 166 48,88 0,01% 2 5 8,42% -4,49% 8 306 65,45 0,01% 4 7 6,71% -3,98% 9 195 75,03 0,01% 2 5 8,11% -0,17% 10 590 47,61 0% 4 7 0,15% -0,17% 1
4
75 64,04 0% - 4 15,57% 0,00% 2 53 75,36 0% - 4 5,31% 0,00% 3 172 68,66 0% 1 5 3,72% -1,50% 4 837 72,71 0% 1 5 0,00% -4,89% 5 791 65,03 0% 1 5 0,42% -1,08% 6 139 36,36 0% - 4 0,32% 0,00% 7 166 48,88 0,01% 2 6 8,42% -4,49% 8 306 65,45 0,01% 4 8 6,71% -3,98% 9 195 75,03 0,01% 2 6 8,11% -0,17% 10 590 47,61 0% 4 8 0,15% -0,17% 1
5 75 64,04 0% - 5 15,57% 0,00%
2 53 75,36 0% - 5 5,31% 0,00% 3 172 68,66 0% 1 6 3,72% -1,50%
64
4 837 72,71 0% 1 6 0,00% -4,89% 5 791 65,03 0% 1 6 0,42% -1,08% 6 139 36,36 0% - 5 0,32% 0,00% 7 166 48,88 0,01% 2 7 8,42% -4,49% 8 306 65,45 0,01% 4 9 6,71% -3,98% 9 195 75,03 0,01% 2 7 8,11% -0,17% 10 590 47,61 0% 4 9 0,15% -0,17%
Les résultats du Tableau 7 montrent que la résolution du modèle mathématique (P) de
sélection des routes atteint l’optimalité indépendamment de la variation du nombre
d’itérations sans amélioration. En effet, l’écart d’optimalité relatif à la solution obtenue par
l’approche de base est le même pour toutes les valeurs du nombre d’itérations sans
amélioration. De même, nous constatons que l’écart de la solution générée par notre
approche par rapport aux celles obtenues par les approches proposées par Berkoune et al.
(2011) reste inchangé pour toutes les valeurs de la condition d’arrêt, sauf pour le test 10
nous remarquons une amélioration de 0,17% par rapport à la solution heuristique en passant
de 2 à 3 itérations. D’une autre côte, pour les tests 8 et 10 (ELDS : 20 et 25), nous
remarquons que le nombre de routes générées augmente lorsque le nombre d’itérations sans
amélioration passe de 2 à 3. Cette augmentation est expliquée par le fait que
l’accroissement de la valeur de la condition d’arrêt génère une augmentation du nombre
routes générées et par conséquent la possibilité d’améliorer la solution obtenue.
Tableau 8 : Effet de la variation du nombre d’itérations sans amélioration sur le temps de résolution
Test Nb_Itér Approche de base (C)
Étape 1 Étape 2 1+2 T_Sol 1
2
17,5 38,2 50,8 12,6 2 6,1 2,2 8,3 2,7 3 14,1 8,1 22,2 9,1 4 162,4 715,0 877,4 77,8 5 570,7 14042,7 14613,4 3395,8 6 10,0 5,7 15,6 6,2 7 20,0 669,0 689,0 290,7 8 316,9 789,4 1106,3 608,3 9 37,4 166,8 204,2 125,0 10 37,6 676,9 714,5 129,1
65
1
3
12,9 37,8 50,7 12,6 2 8,4 2,1 10,4 2,7 3 16,9 7,6 24,5 8,9 4 209,2 712,2 921,4 77,5 5 733,6 14032,3 14765,9 3384,0 6 12,9 5,9 18,7 6,2 7 23,2 670,1 693,4 291,4 8 352,3 1083,3 1435,6 605,8 9 43,0 167,2 210,2 125,2 10 90,8 1105,9 1196,7 1014,6 1
4
13,1 37,3 50,4 12,6 2 8,4 2,1 10,4 2,7 3 19,7 7,6 27,3 8,8 4 265,7 715,2 981,0 77,9 5 696,4 14032,6 14729,0 3384,1 6 15,9 5,8 21,6 6,2 7 26,5 669,8 696,3 292,2 8 398,8 1083,8 1482,6 606,4 9 48,6 166,8 215,5 125,2 10 99,0 1102,9 1202,0 1012,1 1
5
12,9 36,8 49,8 12,6 2 8,4 2,0 10,4 2,7 3 19,7 7,5 27,2 8,8 4 301,9 713,6 1015,5 77,4 5 758,7 14026,7 14785,4 3380,4 6 18,7 5,8 24,4 6,2 7 29,6 668,9 698,5 292,2 8 445,3 1082,4 1527,8 604,8 9 55,0 166,5 221,5 125,1 10 106,8 1102,6 1209,4 1010,9
Les résultats rapportés dans le Tableau 8 montrent que le temps de résolution dépend de la
variation de la valeur du nombre d’itérations sans amélioration. En effet, nous remarquons
que pour les tests 8 et 10 les temps de résolution augmentent lorsque la valeur du nombre
d’itérations sans amélioration passe de 2 à 3. Ces temps croissent, car le nombre de routes
générées a augmenté. Nous constatons aussi que pour le test 10, le temps de génération des
routes augmente légèrement et le temps de résolution du MIP reste inchangé lorsque la
valeur de la condition d’arrêt passe de 4 à 5. Ceci s’explique par le fait que l’augmentation
66
du nombre d’itérations sans amélioration, nous offre la possibilité de résoudre le problème
avec des itérations supplémentaires. Il convient de noter que les variations minimes des
différentes valeurs d’une instance donnée dépendent des performances de l’ordinateur
utilisé.
La Figure 8 illustre la variation de la moyenne du temps total de résolution en fonction du
nombre d’itération sans amélioration de la solution obtenue.
Figure 8 : Variation du temps total de résolution en fonction du nombre d'itérations sans
amélioration
D’après la Figure 8, on peut conclure que la moyenne du temps total de résolution avec
l’approche de base que nous avons développée dépend de la variation de la valeur du
nombre d’itérations sans amélioration. Outre, nous avons enregistré la plus importante
variation du temps total moyen lorsque la valeur de la condition d’arrêt passe de 2 à 3
itérations. Par conséquent, nous proposons de considère la valeur 3 comme nombre
d’itérations sans amélioration.
5.4.3. Comparaison des deux critères d’arrêt
Dans le but de comparer les deux conditions d’arrêt proposées dans cette section, nous
allons étudier la variation des temps de résolution dans le cas où on a le critère est le temps
de résolution maximal égal à 1800 secondes par rapport à ceux obtenus lorsque la condition
d’arrêt égale à 3 itérations sans amélioration de la solution générée. En effet, nous avons
choisi les temps de résolution comme critère d’évaluation, car avec les deux conditions
182018401860188019001920194019601980
2 3 4 5 6
Seco
ndes
Nombre d'itérations sans amélioration
Temps Total
67
proposées nous avons obtenu des solutions avec la même qualité pour toutes les instances.
Le Tableau 9 illustre la variation du temps de résolution en fonction des deux conditions
d’arrêt proposées.
Tableau 9 : Variation des temps de résolution en fonction du critère d’arrêt
Test Approche de base (1800 s) Approche de base (3 Itéra)
Étape 1 Étape 2 1+2 Étape 1 Étape 2 1+2 1 12,8 40,8 53,5 12,9 37,8 50,7 2 8,3 2,3 10,7 8,4 2,1 10,4 3 19,7 8,2 27,8 16,9 7,6 24,5 4 348,6 791,4 1140,1 209,2 712,2 921,4 5 216,4 3565,7 3782,1 733,6 14032,3 14765,9 6 24,5 5,9 30,4 12,9 5,9 18,7 7 42,2 668,3 710,5 23,2 670,1 693,4 8 679,9 1082,8 1762,7 352,3 1083,3 1435,6 9 74,4 166,6 241,0 43,0 167,2 210,2 10 145,7 1100,5 1246,2 90,8 1105,9 1196,7
Moyenne 900,5 Moyenne 1932,8
D’après le Tableau 9, nous remarquons que le temps total de résolution, lorsque la
condition d’arrêt est égale à 3 itérations sans amélioration de la solution obtenue, est plus
faible pour toutes les instances, sauf pour le test 5 où nous constatons le contraire. En effet,
le temps total obtenu avec un temps de résolution maximal égal à 1800 secondes est de
l’ordre 40% du temps requit pour résoudre le problème avec la deuxième condition d’arrêt.
Par conséquent, la moyenne du temps total obtenu avec un temps de résolution maximal
comme critère d’arrêt est beaucoup plus faible que celui requis avec le deuxième critère.
5.5. Étude comparative entre l’approche de base proposée et ses
variantes
Nous allons étudier, dans cette section, l’effet des changements apportées dans les trois
variantes proposées (chapitre 4) sur les performances de l’approche modifiée en termes de
la qualité de la solution obtenue et du temps de résolution. Pour le faire, nous allons
calculer l’écart en pourcentage entre la solution générée par l’approche de base que nous
avons proposée et celle obtenue par les trois autres versions modifiées.
68
La colonne (‘(D-C)/C’) exprime l’écart en pourcentage entre la solution obtenue par
l’approche de base (C) et celle générée avec la Variante 1 (D) améliorée de cette dernière.
La colonne (‘(E-C)/C’) exprime l’écart en pourcentage de la solution obtenue par la
Variante 2 (E) par rapport à celle générée avec l’approche de base (C).
La colonne (‘(F-C)/C’) représente l’écart en pourcentage entre la solution obtenue par
l’approche de base (C) et celle générée avec la Variante 3 (F). Les résultats obtenus sont
rapportés dans les tableaux 10 et 11.
69
Tableau 10 : Impact des changements effectués sur l’approche de base sur la qualité de la solution obtenue
Test Approche de base (C) Variante 1 (D) Variante 2 (E) Variante 3 (F)
(C-A)/A (D-C)/C (E-C)/C (F-C)/C Nb_Rte Sol Gap Nb_Rte Sol Gap Nb_Rte Sol Gap Nb_Rte Sol Gap
1 75 64,04 0,00% 190 55,59 0% 218 55,59 0% 117 60,58 0% 15,57% -13,19% -13,19% -5,40% 2 53 75,36 0,00% 53 75,36 0% 53 75,36 0% 53 75,36 0% 5,31% 0,00% 0,00% 0,00% 3 172 68,66 0,00% 297 68,66 0,01% 449 66,2 0,00% 297 68,66 0,01% 3,72% 0,00% -3,58% 0,00% 4 837 72,71 0,00% 1390 72,71 0 1830 72,71 0 1251 72,71 0% 0,00% 0,00% 0,00% 0,00% 5 592 65,03 0,01% 882 65,03 0,01% 882 65,03 0,01% 882 65,03 0% 0,43% 0,00% 0,00% 0,00% 6 139 36,36 0,00% 377 36,24 0% 385 36,24 0% 377 36,24 0% 0,33% -0,33% -0,33% -0,33% 7 166 48,88 0,01% 175 48,8 0,00% 175 48,8 0,00% 175 48,8 0% 8,43% -0,16% -0,16% -0,16% 8 306 65,45 0,01% 280 65,45 0,01% 280 65,45 0,00% 252 68,17 0% 6,70% 0,00% 0,00% 4,16% 9 195 75,03 0,01% 355 72,07 0,01% 355 72,07 0,01% 243 72,62 0% 8,11% -3,95% -3,95% -3,21%
10 590 47,61 0,00% 640 47,61 0,01% 1101 47,61 0,01% 576 47,61 0% 0,15% 0,00% 0,00% 0,00%
Tableau 11 : Impact des changements effectués sur l’approche de base sur le temps de résolution
Test Approche de base (C) Variante 1 (D) Variante 2 (E) Variante 3 (F)
Étape 1 Étape 2 1+2 Étape 1 Étape 2 1+2 Étape 1 Étape 2 1+2 Étape 1 Étape 2 1+2 1 12,8 40,8 53,5 23,1 272,5 295,6 35,6 345 380,7 47,6 68 115,5 2 8,3 2,3 10,7 4 2 5,9 4 2,2 6,1 3,9 2 6 3 19,7 8,2 27,8 21,3 8,8 30,1 29 5,8 34,7 21,3 8,9 30,3 4 348,6 791,4 1140,1 350,6 673,8 1024,4 462,3 2189,8 2652,1 350,8 473,6 824,4 5 216,4 3565,7 3782,1 434,8 4357,6 4792,4 434,8 4345,7 4780,4 434,8 4360,6 4795,3 6 24,5 5,9 30,4 23,4 10 33,4 34,6 11 45,6 23,4 10,1 33,5 7 42,2 668,3 710,5 22,7 381,8 404,5 22,9 242 264,8 22,7 382,7 405,4 8 679,9 1082,8 1762,7 686,3 702,2 1388,5 686,5 327,5 1013,9 686,3 404,8 1091,1 9 74,4 166,6 241 163,8 2212,3 2376,2 163,3 1942,8 2106,2 163,5 681,2 844,7 10 145,7 1100,5 1246,2 125,3 3311,5 3436,9 217,3 1579 1796,2 125,3 649,4 774,7
70
Les résultats obtenus, dans le Tableau 10, montrent que le modèle MIP est résolu à
l’optimalité avec toutes les approches que nous avons proposées pour toutes les instances
puisque l’écart d’optimalité est nul. Nous remarquons aussi que l’écart entre la solution
générée avec l’approche de base et celle obtenue par la Méthode exacte varie entre les
valeurs 0% et 15,57%.
Ainsi, nous constatons que la Variante 1 proposée dans le chapitre 4 apporte des
améliorations aux solutions obtenues par rapport à celles générées par l’approche de base
pour les tests 1, 6, 7 et 9. En effet, pour ces problèmes, l’écart avec l’approche exacte
diminue (i.e., ELDS = 1, on améliore la solution obtenue avec la Variante 1 de 13,19% par
rapport à celle générée par l’approche de base). Ceci est expliqué par le fait que la
génération de toutes les routes partant de tous les CDAH(s), capables de servir le client déjà
sélectionné, engendre l’augmentation de l’ensemble des tournées semi-réalisables ajoutées
à chaque itération.
Outre, nous remarquons aussi que l’écart en pourcentage entre la solution obtenue par la
Variante 2 et celle obtenue par l’approche de base atteint une valeur minimale de (-
13,19%). Par ailleurs, cette variante génère une solution optimale au problème 5, ce qui
représente une amélioration de l’ordre de 3,58% par rapport à la solution obtenue avec
l’approche de base. Ceci est dû au fait que la génération de toutes les routes partant de tous
les CDAH(s) et capables de servir le client (déjà sélectionné pour deux routes données),
augmente l’ensemble des tournées semi-réalisables ajoutées à chaque itération, ce qui
permet de s’approcher davantage de l’optimum global. Pour les instances restantes, nous
avons obtenu les mêmes solutions.
Nous constatons aussi que dans la plupart de cas, le nombre de routes générées avec la
Variante 2 est supérieur ou égal à celui crée par la Variante 1. Ceci vient du fait que nous
avons sélectionné deux routes ayant un écart nul entre le temps de distribution
correspondant et LMax, ce qui engendre une augmentation de l’ensemble de tournées semi-
réalisables générées. Par ailleurs, pour le test 8 le nombre de routes générées par la
Variante 1 modifiée est inférieur à celui obtenu avec la Variante 2. Ceci s’explique par le
fait que la génération de l’ensemble des tournées à partir de deux routes ayant un écart nul,
71
ne garantit pas nécessairement le maintien du même ensemble de routes définissant la
solution obtenue à chaque itération.
D’après les résultats du Tableau 10, nous constatons que la solution obtenue avec la
Variante 3 est moins bonne que celle générée avec la Variante 2 pour les tests 1, 3, 8 et 9.
Nous remarquons aussi que l’écart en pourcentage entre la solution obtenue avec
l’approche proposée dans cette section et celle obtenue par l’approche Variante 1 atteint
une valeur maximale de 8,98%. Ceci est dû au fait que la suppression d’un certain nombre
de routes peut détruire la solution obtenue dans des itérations prochaines, puisque
l’élimination de ces routes engendre le changement de l’ensemble de routes à injecter dans
le modèle (P) et par la suite l’obtention d’un mauvais optimum local.
D’après le Tableau 11, nous constatons que le temps caractérisant la solution obtenue par la
Variante 1 est supérieur à celui qui caractérise la solution générée par l’approche de base
que nous avons développée. Ceci est dû essentiellement à l’augmentation considérable du
temps requis pour résoudre le modèle (P), lorsque l’ensemble des tournées semi-réalisables
devient plus accentué. Par contre pour les tests 2, 4, 7 et 8, nous remarquons que le temps
total de résolution obtenu avec l’approche de base est supérieur à celui obtenu avec la
Variante 1. En effet, cette dernière variante permet la génération d’un nombre de routes
presque identique à celui obtenu avec l’approche de base, et ceci avec moins d’itérations.
Par conséquent le temps requis pour résoudre le problème, la génération des routes vides et
la résolution du MIP, deviens plus faible. Le temps moyen de résolution total obtenu avec
la Variante 1 (1378,8 s) est beaucoup plus important que celui obtenu avec l’approche de
base que nous avons proposée (900,5 s).
D’après le Tableau 11, nous constatons que pour les petites instances ((2, 15), (3, 15) et (4,
15)), les temps caractérisant la solution obtenue par la Variante 1 sont supérieurs à celui qui
caractérise la solution générée par la Variante 1. Ceci est expliqué par l’augmentation du
temps nécessaire pour résoudre le MIP, en passant d’une itération à une autre (i.e., pour le
Test 1, le temps de MIP est de 345 seconds presque 90% du temps total). Par contre pour le
reste des instances, nous remarquons que les temps obtenus par la Variante 2 modifiée de
l’approche de base développée sont inférieurs aux temps obtenus par la Variante 1. En
effet, l’accroissement du nombre des routes semi-réalisables à une ou plusieurs itérations,
72
en fonction de deux routes sélectionnées, engendre une diminution du nombre d’itérations
et par conséquent la réduction du temps nécessaire pour résoudre le MIP. En se basant sur
la moyenne du temps total de résolution, nous remarquons le temps total requit pour
résoudre le problème avec la Variante 2 (1308,07 s) est légèrement inférieur à celui
nécessaire avec la Variante 1 (1378,79 s).
Le Tableau 11 montre que les temps de résolution obtenus avec la Variante 3 sont plus
faibles que ceux obtenus avec la Variante 2. En effet, pour toutes les instances nous
remarquons (Tableau 10) que le nombre de routes générées avec la méthode (F) est
inférieur ou égal à celui obtenu avec la Variante 2. Par conséquent, le temps nécessaire
pour résoudre le modèle (P) devient plus faible.
La Figure 8 illustre la variation de l’écart en pourcentage entre la solution obtenue avec
l’approche de base que nous avons développée et celle générée avec les trois autres
versions développées.
Figure 9 : variation de l’écart en pourcentage par rapport au numéro du test
La Figure 9 montre que Variante 2 proposée domine les deux autres variantes développées
pour les 10 instances testées. En effet, la courbe ((E-C)/C) est toujours au-dessous de deux
autres versions quel que soit la valeur du test.
-14%
-12%
-10%
-08%
-06%
-04%
-02%
00%
02%
04%
0 2 4 6 8 10 12
Pour
cent
age
Test
(D-C)/C
(E-C)/C
(F-C)/C
73
5.6. Plan d’expérience comparatif
Dans cette section, nous chercherons à évaluer la qualité de la solution obtenue et le temps
de résolution associés aux approches que nous avons développées (soit l’approche de base
et la Variante 2) par rapport aux approches proposées par Berkoune et al. (2011). En effet,
nous allons étudier l’effet de la variation d’un ensemble de paramètres clés tels que le
nombre de CDAH(s) ouverts et le nombre total de clients à servir. Cette étude se présente
comme une comparaison qui sera effectuée entre l’approche de base et la Variante 2 (La
meilleure variante proposée) d’une part et les deux approches développées par Berkoune et
al. (2011) d’une autre part.
Dans la suite de ce travail, nous allons élaborer un plan d’expérience comparatif plus large
basé sur 54 problèmes tests. En effet, les 54 problèmes tests résultent des 27 problèmes
(Tableau 1) qui ont été résolus en limitant le nombre de visites par route à 3 puis à 4. Le
tableau 12 exprime les paramètres des 54 problèmes tests.
Tableau 12 : Paramètres des 54 problèmes tests
Test ELDS (|L|, |I|) |Kl| Max Visite
1 1
(2, 15)
5 3
2 4 3
2 5 3
4 4 5
3 5 3
6 4 7
4
(3, 15)
4 3
8 4 9
5 2 3
10 4 11
6 2 3
12 4 13
7
(3, 20)
3 3
14 4 15
8 3 3
16 4 17
9 3 3
18 4 19 10 (4, 15) 4 3
74
20 4 21
11 5 3
22 4 23
12 3 3
24 4 25
13
(4, 20)
5 3
26 4 27
14 5 3
28 4 29
15 2 3
30 4 31
16
(4, 25)
3 3
32 4 33
17 3 3
34 4 35
18 3 3
36 4 37
19
(5, 15)
2 3
38 4 39
20 2 3
40 4 41
21 2 3
42 4 43
22
(5, 20)
2 3
44 4 45
23 2 3
46 4 47
24 2 3
48 4 49
25
(5, 25)
4 3
50 4 51
26 4 3
52 4 53
27 3 3
54 4
5.6.1. Comparaison de la qualité de la solution
Pour mener à terme notre étude de la qualité de la solution obtenue, nous allons évaluer
l’effet de la variation du nombre de CDAH(s) et du nombre de clients à servir sur la qualité
de la solution obtenue. Pour le faire, nous allons comparer les résultats obtenus par les deux
75
approches proposées par Berkoune et al. (2011) : l’approche exacte (Méthode exacte (A)) et
l’approche heuristique (Méthode heuristique (B)) et les résultats obtenus par l’approche que
nous avons développée (Approche de base (C)) et la Variante 2 (E) améliorée. Afin
d’évaluer la qualité de la solution générée par les méthodes que nous avons proposées, nous
avons calculé l’écart en pourcentage par rapport à la solution obtenue avec la méthode
exacte.
Le Tableau 13 résume l’ensemble des résultats obtenus relatifs aux nombre de routes et
l’écart d’optimalité pour les 54 problèmes.
Tableau 13 : Nombre de routes et écart d’optimalité correspondants aux solutions obtenues
Test Méthode exacte (A) Méthode heuristique (B) Approche de base (C) Variante 2 (E) Nb_Rte Gap Nb_Rte Gap Nb_Rte Gap Nb_Rte Gap
1 261 0,01% 65 0,01% 75 0,00% 218 0,01% 2 351 0,01% 70 0,00% 80 0,00% 111 0,00% 3 183 0,00% 53 0,00% 60 0,00% 78 0,01% 4 243 0,00% 60 0,00% 66 0,00% 112 0,00% 5 130 0,01% 47 0,00% 53 0,00% 53 0,00% 6 149 0,00% 52 0,00% 58 0,00% 52 0,00% 7 416 0,00% 102 0,00% 166 0,00% 248 0,00% 8 524 0,00% 111 0,00% 175 0,00% 151 0,00% 9 1195 0,00% 119 0,00% 172 0,00% 449 0,00%
10 2636 0,01% 151 0,00% 158 0,00% 153 0,00% 11 1405 0,00% 128 0,00% 163 0,00% 172 0,00% 12 3922 4,89% 166 0,00% 837 0,00% 1830 0,00% 13 1121 9,90% 148 0,01% 237 0,01% 265 0,00% 14 1903 13,21% 172 0,01% 302 0,01% 355 0,01% 15 2318 96,33% 167 0,01% 228 0,00% 274 0,01% 16 6441 94,78% 215 0,01% 592 0,01% 882 11,24% 17 1591 47,61% 142 0,00% 546 0,01% 752 1,23% 18 3291 46,57% 175 0,01% 314 0,01% 266 7,90% 19 539 0,00% 136 0,00% 158 0,00% 219 0,00% 20 677 0,00% 147 0,00% 181 0,00% 151 0,00% 21 266 0,00% 102 0,00% 116 0,00% 107 0,00% 22 324 0,00% 111 0,00% 122 0,00% 236 0,00% 23 811 0,00% 129 0,00% 139 0,00% 385 0,00% 24 1326 0,00% 154 0,01% 163 0,00% 318 0,00%
76
25 447 0,01% 132 0,00% 151 0,00% 292 0,01% 26 563 0,01% 143 0,01% 163 0,00% 175 0,00% 27 721 0,00% 160 0,00% 239 0,00% 284 0,00% 28 1022 0,00% 185 0,00% 217 0,01% 190 0,00% 29 2383 9,76% 202 0,00% 361 0,00% 784 0,00% 30 5912 12,57% 250 0,00% 522 0,01% 675 0,00% 31 4940 88,03% 279 0,01% 465 0,01% 2024 0,01% 32 14499 99,20% 361 0,01% 1068 3,35% 3847 4,00% 33 3451 40,26% 249 0,00% 396 0,01% 829 0,01% 34 8154 76,98% 311 0,01% 403 8,15% 489 9,19% 35 6121 98,36% 278 3,03% 278 3,03% 278 3,05% 36 21333 99,79% 352 13,89% 352 13,89% 352 13,89% 37 359 0,00% 135 0,00% 166 0,01% 175 0,00% 38 407 0,00% 146 0,00% 179 0,00% 148 0,01% 39 699 0,01% 167 0,01% 231 0,00% 384 0,01% 40 945 0,00% 180 0,01% 306 0,01% 224 0,00% 41 383 0,01% 134 0,01% 137 0,01% 173 0,01% 42 443 2,42% 138 0,01% 142 0,01% 139 0,01% 43 848 7,01% 189 0,01% 195 0,01% 355 0,01% 44 1157 13,21% 207 0,01% 213 0,01% 207 0,01% 45 1085 24,18% 211 0,01% 248 0,01% 320 0,01% 46 1552 15,34% 236 0,01% 240 0,01% 311 0,01% 47 1594 21,53% 234 0,01% 263 0,01% 693 0,00% 48 2703 97,33% 272 0,01% 280 0,01% 554 5,59% 49 2451 0,00% 278 0,01% 590 0,00% 1101 0,00% 50 4529 0,00% 321 0,01% 700 0,01% 600 0,01% 51 1228 3,76% 207 0,00% 288 0,00% 558 3,93% 52 2158 4,61% 241 0,00% 292 0,00% 490 0,43% 53 1888 59,28% 223 4,73% 223 4,73% 223 4,70% 54 3476 59,27% 256 17,11% 256 17,11% 1806 51,54%
Les résultats du Tableau 13 montrent que le modèle mathématique (P) de sélection des
routes est résolu à l’optimalité avec l’approche de base presque pour toutes les instances
sauf les instances 32, 34, 35, 36, 53 et 54, soit 11,11% des instances. Cela est beaucoup
mieux que pour la Méthode exacte qui n’atteint pas l’optimalité dans 26 cas soit 48,15%
des instances et mieux aussi que la Variante 2 (22,22% de cas non résolu à l’optimalité). Il
convient de mentionner que même si le MIP de l’étape de chargement est résolu à
77
l’optimalité avec l’approche de base, la solution obtenue ne garantit pas l’optimalité pour le
problème. Dans les quatre approches, nous n’avons pas pu résoudre le modèle (P) de
sélection et de chargement à l’optimalité, car la limitation du temps pour la phase de
chargement (3600 secondes) exige l’arrêt de l’exécution du MIP. Pour les 26 instances non
résolues d’optimalité, l’écart d’optimalité obtenu avec l’approche exacte et tel que fourni
par CPLEX varie entre 2,42 % (pour l’instance 42) et 99,20% (pour l’instance 32) et il est
en moyenne égal à 42,45%. Alors que pour la Variante 2, l’écart d’optimalité
correspondant aux 12 instances varie entre 0,43% (pour l’instance 52) et 21,54 (pour
l’instance 54), la moyenne de l’écart est alors égale à 7,22%.
Les colonnes (‘(E-A)/A’) et (‘(E-B)/B’) expriment l’écart en pourcentage de la solution
obtenue par la Variante 2 (E) par rapport à celle générée avec l’approche exacte (A) et
l’approche heuristique (B) proposées par Berkoune et al. (2011).
Les colonnes (‘Sol-Approche (I)’) avec I = {A, B, C et E}, indiquent les solutions obtenues
avec les approches A, B, C et E.
Tableau 14 : Comparaison de la qualité de la solution obtenue par les quatre approches
Test Sol-Approche (A)
Sol-Approche (B)
Sol-Approche (C)
Sol-Approche (E) (C-A)/A (E-A)/A (E-B)/B
1 55,41 64,04 64,04 55,59 15,57% 0,32% -13,20% 2 55,41 64,04 64,04 60,58 15,57% 9,34% -5,40% 3 69,44 86,18 84,36 84,36 21,49% 21,49% -2,11% 4 69,44 86,18 84,36 80,16 21,49% 15,44% -6,99% 5 71,56 75,36 75,36 75,36 5,31% 5,31% 0,00% 6 71,56 75,36 75,36 75,36 5,31% 5,31% 0,00% 7 62,23 65,57 62,25 62,25 0,03% 0,03% -5,06% 8 62,23 65,57 62,25 62,25 0,03% 0,03% -5,06% 9 66,2 69,71 68,66 66,20 3,72% 0,00% -5,04%
10 65,91 66,2 66,2 66,20 0,44% 0,43% -0,01% 11 72,71 78,96 78,96 78,96 8,60% 8,59% -0,01% 12 72,71 76,44 72,71 72,71 0,00% 0,00% -4,88% 13 79,45 94,15 88,87 86,16 11,86% 8,45% -8,49% 14 79,62 87,75 86,33 85,80 8,43% 7,76% -2,22% 15 66,35 66,43 66,43 65,90 0,12% -0,68% -0,80% 16 64,75 65,74 65,03 65,03 0,43% 0,43% -1,08%
78
17 55,78 62,42 59,9 54,87 7,39% -1,63% -12,09% 18 54,69 60,94 60,72 60,48 11,03% 10,58% -0,76% 19 58,18 58,18 58,18 58,18 0,00% 0,00% 0,00% 20 58,18 58,18 58,18 58,18 0,00% 0,00% 0,00% 21 47,32 47,32 47,32 47,32 0,00% 0,00% 0,00% 22 47,32 47,32 47,32 47,32 0,00% 0,00% 0,00% 23 36,24 36,36 36,36 36,24 0,33% 0,00% -0,33% 24 36,24 36,36 36,36 36,24 0,33% 0,00% -0,33% 25 44,21 45,81 45,35 44,21 2,58% 0,00% -3,49% 26 44,21 45,81 45,35 45,35 2,58% 2,58% -1,00% 27 47,32 47,32 47,32 47,32 0,00% 0,00% 0,00% 28 47,32 47,32 47,32 47,32 0,00% 0,00% 0,00% 29 64,83 69,4 65,7 65,08 1,34% 0,39% -6,22% 30 63,94 69,4 65,08 65,08 1,78% 1,78% -6,22% 31 56,05 57,06 55,03 55,03 -1,82% -1,82% -3,56% 32 69,26 57,06 55,28 55,28 -20,18% -20,18% -3,12% 33 48,92 48,52 48,52 48,52 -0,82% -0,82% 0,00% 34 48,52 48,52 48,52 48,52 0,00% 0,00% 0,00% 35 57 56,44 56,44 56,44 -0,98% -0,98% 0,00% 36 67,65 56,72 56,72 56,72 -16,16% -16,16% -0,01% 37 45,08 51,17 48,88 48,79 8,43% 8,23% -4,65% 38 45,08 51,17 48,88 48,79 8,43% 8,23% -4,65% 39 61,34 68,17 65,45 65,41 6,70% 6,63% -4,05% 40 61,34 68,17 65,45 65,41 6,70% 6,63% -4,05% 41 62,43 67,82 67,82 62,97 8,63% 0,87% -7,15% 42 62,43 67,82 67,82 67,82 8,63% 8,63% 0,00% 43 69,4 75,16 75,03 72,07 8,11% 3,85% -4,11% 44 69,4 75,16 75,03 75,03 8,11% 8,11% -0,17% 45 70,88 76,43 75,96 75,96 7,17% 7,17% -0,61% 46 70,88 76,43 75,96 75,78 7,17% 6,92% -0,84% 47 73,87 78,81 74,92 68,14 1,42% -7,76% -13,54% 48 74,4 78,81 78,81 76,97 5,93% 3,46% -2,33% 49 47,54 47,69 47,54 47,54 0,00% 0,00% -0,31% 50 47,54 47,69 47,59 47,59 0,11% 0,11% -0,21% 51 40,96 43,23 43,23 41,90 5,54% 2,29% -3,08% 52 40,96 43,23 43,23 43,23 5,54% 5,55% 0,01% 53 41,13 43,38 43,38 43,38 5,47% 5,46% -0,01% 54 41,13 43,38 43,38 42,30 5,47% 2,84% -2,49%
79
D’après le Tableau 14, nous constatons que la Variante 2 génère des solutions de même
qualité que la Méthode exacte pour 21 instances sur 54 (38,9% des instances). Ceci est
expliqué par le fait que l’approche proposée ne prend pas en considération toutes les
combinaisons possibles des routes semi-réalisables. Par ailleurs, nous avons pu améliorer la
solution obtenue avec l’approche de base que nous avons développée 36 fois (soit 66,7%
des instances). Ceci est dû au fait que la génération de toutes les routes partant de tous les
CDAH(s) et capables de servir le client, augmente l’ensemble des tournées semi-réalisables
ajoutées à chaque itération, ce qui permet de s’approcher davantage de l’optimum global.
De plus, nous constatons que les solutions obtenues par la méthode améliorée (Variante 2)
sont meilleures dans 15 cas par rapport à la solution obtenue avec la Méthode exacte, et
pour les instances restantes nous avons obtenu une solution égale à celle générée par cette
dernière. Cela s’explique par une réduction du temps de calcul puisque le nombre de routes
générées dans la Variante 2 est plus faible par rapport à celui de l’approche exacte et qui
rend le modèle plus difficile à résoudre. L’écart en pourcentage entre les solutions obtenues
par la Variante 2 et celles obtenues par la Méthode exacte pour les 33 instances est en
moyenne égal à 3,39%. Cet écart reste inférieur à la moyenne pour 12 instances et dépasse
le 20% seulement pour les tests 3.
5.6.2. Effet de la variation du nombre de CDAH(s) sur la qualité de la
solution obtenue
Dans cette section, nous proposons d’étudier l’effet de la variation du nombre de CDAH(s)
sur la qualité de la solution obtenue. Pour ce faire, nous allons étudier l’effet de la variation
du nombre de CDAH(s), |L|, de 2 à 5. Ensuite, nous allons représenter graphiquement la
variation de la moyenne de l’écart d’optimalité (pour la résolution du modèle
mathématique) de chaque approche en fonction du nombre de CDAH(s). Ensuite, nous
allons schématiser l’effet de l’augmentation du paramètre |L| sur la moyenne des écarts en
pourcentage des solutions obtenues avec les deux approches que nous avons proposée par
rapport à celles générées avec les deux approches développées par Berkoune et al. (2011).
Dans cette section, nous avons considéré deux cas de figure différents :
• Premier cas : 15 clients à servir avec un nombre de clients maximal à visiter égal à 3;
80
• Deuxième cas : 15 clients à servir avec un nombre de clients maximal à visiter égal à
4.
Exemple du calcul : considérant le premier cas avec un nombre de CDAH(s) = 3, donc la
moyenne de l’écart d’optimalité est égal à la moyenne de la colonne représentant le ‘Gap’
des tests 7, 9 et 11 (voir Tableau 13).
Figure 10 : Variation de l’écart d’optimalité en fonction du nombre de CDAHs (Premier cas)
Figure 11 : Variation de l’écart d'optimalité en fonction du nombre de CDAHs (Deuxième cas)
D’après la Figure 10, nous constatons que dans le premier cas le modèle est résolu à
l’optimalité pour les quatre approches, puisque l’écart d’optimalité est pratiquement nul (au
maximum 0,01%). Par ailleurs, la Figure 11 montre que l’écart d’optimalité varie entre 0%
et 1,63% pour l’approche exacte (A). En effet, l’augmentation du nombre de CDAH(s)
engendre un nombre de combinaisons très important et par conséquent la résolution du
modèle (P) devient plus difficile (temps de résolution dépasse le temps limite de 3600
seconds).
000%
000%
000%
000%
000%
000%
000%
000%
2 3 4 5Nombre de CDAH
Gap (A) Gap (B) Gap (C) Gap (E)
000%000%000%001%001%001%001%001%002%002%
2 3 4 5Nombre de CDAH
Gap (A) Gap (B) Gap (C) Gap (E)
81
Figure 12 : Variation de l’écart en pourcentage en
fonction du nombre de CDAHs (Premier cas)
Figure 13 : Variation de l’écart en pourcentage en fonction du nombre de CDAHs (Deuxième cas)
La Figure 12 illustre le pourcentage d’amélioration de la solution obtenue par rapport à la
solution optimale. On constate que la solution obtenue avec la Variante 2 (E) est toujours
inférieure à celle obtenue avec l’approche heuristique proposée par Berkoune et al. (2011).
Cette amélioration en moyenne varie entre 0,11% et 4,13% (Premier cas) et elle
indépendante du nombre de CDAH(s). De plus, nous remarquons que l’écart en
pourcentage moyen de la solution obtenue avec la Variante 2 par rapport celle obtenue avec
l’approche exacte dépend du nombre de CDAH(s). En effet, dans le premier cas et pour un
nombre de CDAH(s) égal à 3 l’écart est supérieur à 0, par contre dans le deux cas et pour le
même nombre de CDAH(s) cet écart presque égal à 0. Tout cela est dû au fait qu’une
augmentation du nombre de CDAH(s), entraine une augmentation du nombre de
combinaisons possibles ce qui fournit plus de possibilités d’atteindre la solution optimale.
Par contre, le modèle MIP devient plus difficile à résoudre avec la méthode exacte où
toutes les routes sont énumérées d’une façon exhaustive. Par ailleurs, il est intéressant de
signaler que, l’amélioration de la solution générée avec notre approche par rapport à celle
obtenue avec la Méthode heuristique est fortement variée. En effet, cette amélioration
dépend du domaine de départ, l’ensemble initial des routes semi-réalisables et la mise à
jour des routes à chaque itération. Les deux figures 12 et 13 confirment notre constatation
concernant la dominance de la Variante 2 par rapport aux autres variantes proposées.
-010%
-005%
000%
005%
010%
015%
020%
2 3 4 5
Nombre de CDAH
(C-A)/A (E-A)/A (E-B)/B
-010%
-005%
000%
005%
010%
015%
020%
2 3 4 5
Nombre de CDAH
(C-A)/A (E-A)/A (E-B)/B
82
5.6.3. Effet de la variation du nombre de clients sur la qualité de la
solution obtenue
Dans le but d’examiner l’effet de la variation du nombre de clients sur la qualité de la
solution obtenue, nous étudierons la variation de la moyenne des écarts d’optimalité de
chaque solution obtenue par les quatre approches. Nous allons faire varier |I| entre les
valeurs suivantes 15, 20 et 25. La moyenne pour une valeur donnée de I est calculée en
fonction de toutes les instances correspondantes à cette valeur.
Figure 14 : Variation de l'écart d'optimalité en fonction du nombre de clients (3 Clients/route)
Figure 15 : Variation de l'écart d'optimalité en fonction du nombre de clients (4 clients/route)
D’après les Figures 14 et 15, nous constatons que l’écart d’optimalité lors de la résolution
du modèle mathématique est directement influencé par le nombre de clients, surtout pour la
méthode exacte. En effet, lorsque le nombre de clients à satisfaire dépasse 20 clients, l’écart
d’optimalité du modèle obtenu avec la Méthode exacte augmente considérablement contre
une petite augmentation pour les autres approches. Ceci est expliqué par le fait que la
résolution du modèle MIP devient plus difficile dans le cas où le nombre de clients à servir
croît.
0%
10%
20%
30%
40%
50%
60%
15 20 25Nombre de clients
Gap (A) Gap (B) Gap (C) Gap (E)
0%
10%
20%
30%
40%
50%
60%
15 20 25Nombre de clients
Gap (A) Gap (B) Gap (C) Gap (E)
83
Figure 16 : Variation de l’écart en pourcentage en fonction du nombre de clients (3 clients/route)
Figure 17 : Variation de l’écart en pourcentage en fonction du nombre de clients (4 clients/route)
Les Figures 16 et 17 présentent l’écart à la solution optimale pour l’approche de base (C) et
pour la Variante 2 (E). Nous remarquons que l’augmentation du nombre de clients à
satisfaire engendre une diminution du pourcentage d’écart moyen de la solution générée
avec l’approche de base par rapport à la solution exacte et celle obtenue avec la Variante 2.
Cela résulte de l’augmentation du nombre de clients à satisfaire, qui engendre à son tour
une augmentation du nombre de combinaisons possibles. Par conséquent la résolution du
MIP prend plus du temps pour atteindre l’optimalité, cette dernière devient impossible à
atteindre pour des instances de grande taille. Dans le cas où l’on accepte jusqu’à 4 clients
par route, l’approche de base procure même une amélioration par rapport à la méthode
exacte. On constate aussi que la Variante 2 est constamment meilleure que la méthode
heuristique.
5.6.4. Comparaison du temps de résolution
Dans cette section, nous allons mener une étude détaillée des temps de résolution des
méthodes analysées. Pour ce faire, nous avons regroupé tous les résultats correspondants
aux différents cas étudiés dans la section précédente dans un seul tableau. Le Tableau 15
résume les temps d’exécution machine obtenus pour chaque instance et pour chaque
approche de résolution.
-8%
-6%
-4%
-2%
0%
2%
4%
6%
8%
15 20 25
Nombre de clients
(C-A)/A (E-A)/A (E-B)/B
-6%
-4%
-2%
0%
2%
4%
6%
8%
15 20 25
Nombre de clients
(C-A)/A (E-A)/A (E-B)/B
84
Tableau 15 : Comparaison du temps de résolution de quatre approches
Test Méthode exacte (A) Méthode heuristique (B) Approche de base (C) Variante 2 (E)
Étape 1 Étape 2 1+2 Étape 1 Étape 2 1+2 Étape 1 Étape 2 1+2 Étape 1 Étape 2 1+2 1 36,3 34,2 70,5 2 10,6 12,6 12,8 40,8 53,5 35,9 341,6 377,5 2 452,6 34,9 487,5 6,4 11,6 18 170,8 34 204,8 194,6 94,4 289,0 3 25 4,9 29,9 2 0,9 2,8 13,5 4,3 17,8 5,6 4,8 10,4 4 268,2 10,3 278,5 5 2,1 7,1 119,4 7 126,4 170,8 43,5 214,3 5 18,4 9,7 28,1 1,8 1 2,7 8,3 2,3 10,7 3,9 2,0 6,0 6 186,6 24,7 211,3 4,8 0,9 5,7 82,2 2,1 84,3 30,6 1,7 32,2 7 67,6 290 357,6 3,8 3,7 7,5 30,8 27,8 58,6 41,1 28,9 70,0 8 888,3 107,9 996,2 10 4,4 14,4 376,2 20,5 396,7 434,2 15,0 449,2 9 59 18,1 77,1 3,2 1,4 4,5 19,7 8,2 27,8 29,1 5,5 34,6 10 861,8 1622 2483,9 8,6 4 12,6 289,1 5,7 294,9 162,6 13,5 176,1 11 50,5 109,2 159,7 3,3 1,7 5,1 21,9 10,2 32,1 9,6 19,1 28,7 12 758 3600 4358 9 6,4 15,4 348,6 791,4 1140,1 462,1 2185,1 2647,2 13 169,7 3600,4 3770,2 4,7 66,7 71,4 80 3136,4 3216,5 43,3 161,7 205,0 14 3122,4 3600,3 6722,7 14 151,2 165,2 1432,2 2259,5 3691,8 42,9 251,1 293,9 15 154,6 3600,4 3755,1 4,7 75,4 80,2 201,8 383,9 585,7 23,5 524,8 548,3 16 3058,3 3600,9 6659,2 13,8 839,4 853,2 216,4 3565,7 3782,1 434,8 4355,4 4790,2 17 138,7 3600,5 3739,2 4,5 30,4 34,8 35,6 3838,8 3874,4 67,9 4567,0 4634,9 18 2494,6 3600,2 6094,8 12,5 169,9 182,5 366,5 6550 6916,5 745,8 3767,1 4512,9 19 90,2 19 109,2 4,7 1,7 6,4 30,1 6,3 36,4 44,1 7,7 51,7 20 1185 9,4 1194,4 13,6 1,3 14,9 453,1 9,3 462,4 603,0 3,4 606,4 21 66,4 0,4 66,8 4 0,7 4,6 26,1 3,6 29,6 12,4 1,3 13,7 22 798,2 0,4 798,6 10,2 0,6 10,8 45,7 3,2 48,9 378,1 3,2 381,3 23 73 769,2 842,2 4,2 2 6,2 24,5 5,9 30,4 34,9 10,8 45,7 24 956 567,1 1523,1 12 2,2 14,2 309,8 5,4 315,2 462,7 17,0 479,7 25 102,9 14,9 117,8 5 1,3 6,2 31,1 7 38,1 73,2 13,8 87,0 26 1562,6 22,2 1584,8 14 2,6 16,6 396,8 9 405,9 448,3 4,7 453,0
85
27 175,3 109,5 284,9 5,6 1,6 7,2 66,7 37,6 104,3 70,0 22,5 92,5 28 2971,6 166,3 3137,9 15,2 2,7 17,9 860,8 73,9 934,7 674,6 5,5 680,0 29 207,9 3600,5 3808,5 6,2 7,4 13,6 57,6 50,5 108,1 72,0 324,2 396,2 30 3916,2 3600,9 7517,2 17,2 154,2 171,5 1493,1 1143,3 2636,4 1029,3 4191,7 5221,0 31 421,7 3601,1 4022,8 8,2 1270,9 1279 17,5 4613,2 4630,7 803,9 4741,0 5545,0 32 10314,2 3602,6 13916,9 23,9 1872 1895,9 336,1 5472 5808 2450,8 5467,6 7918,4 33 383,4 3600,7 3984,1 7,5 95,1 102,7 34,8 5924,1 5958,9 82,3 3694,9 3777,2 34 8776,9 3600,5 12377,4 22,1 3402,3 3424,5 261,5 7002,6 7264,1 1699,3 6976,0 8675,2 35 421,8 3600,6 4022,4 8,1 3600,2 3608,3 8,1 3600,2 3608,3 7,8 3600,2 3608,1 36 10645,6 3605,8 14251,4 21,7 3600,3 3622 21,7 3600,3 3622 61,7 3559,9 3621,6 37 78,1 300,4 378,5 5,3 81,6 86,8 42,2 668,3 710,5 22,8 245,2 268,0 38 942,3 243,7 1186 14,4 15,2 29,6 552,5 1178,5 1731 266,9 204,0 470,9 39 108 219,3 327,3 6 61,1 67 41,3 495,8 537,2 81,6 1326,6 1408,2 40 1403,3 12,7 1416 16,4 59,1 75,5 679,9 1082,8 1762,7 686,4 332,0 1018,4 41 93,5 2248,4 2341,9 5,4 79,1 84,4 23,3 307,3 330,6 42,0 523,3 565,3 42 1142,2 3599,9 4742,1 13,8 105,7 119,5 256,1 549,9 806,1 191,9 339,5 531,4 43 249,5 3600 3849,6 7,1 24,5 31,7 74,4 166,6 241 163,4 1970,7 2134,1 44 4292,3 3600,4 7892,6 19,4 75,9 95,3 1419,2 542,1 1961,3 934,9 151,1 1086,0 45 218,3 3600,4 3818,7 7,6 315,4 323 78,4 3470,5 3548,9 72,7 5012,7 5085,4 46 3736,7 3599,4 7336,2 21,4 2578,2 2599,6 164,6 4153,2 4317,8 971,4 3864,2 4835,5 47 244,4 3600,1 3844,5 7,7 286,2 293,9 72,2 2346,7 2419 116,7 5390,4 5507,1 48 4388 3600,4 7988,4 22,4 2060 2082,4 165 3958 4123 1227,5 5659,1 6886,6 49 474,9 1396,8 1871,7 9,3 119,8 129,1 145,7 1100,5 1246,2 216,9 1596,3 1813,2 50 10406,2 765,3 11171,4 26,8 30,5 57,3 2055 4139,2 6194,2 2338,5 59,0 2397,5 51 244,8 3600 3844,8 7,5 107,7 115,2 78,7 579,2 657,9 101,0 6507,3 6608,3 52 4703 3600,4 8303,4 19,6 1081,2 1100,8 328,6 3554,1 3882,7 1097,0 4680,4 5777,5 53 346,4 3600,5 3946,9 7,9 3599,9 3607,8 7,9 3599,9 3607,8 7,9 3600,4 3608,2 54 7365,2 3600,9 10966 21,1 3600 3621,1 21,1 3600 3621,1 27,0 3600,7 3627,8
86
Pour l’étape de chargement, tel que déduit du Tableau 13, le modèle (P) a été résolu à
l’optimalité pour 28 instances avec la Méthode exacte et pour 48 instances avec l’approche
de base. Le temps moyen de résolution du MIP est de 326,1 secondes pour l’approche
exacte (pour les 28 instances) et le temps moyen de résolution du MIP obtenu avec la
méthode développée est de 1268,2 secondes. Cet écart est dû aux MIP des 20 instances non
résolues à l’optimalité par la Méthode exacte et qui l’ont été par l’approche de base que
nous avons développée. En effet, si nous considérons les instances qui ont été résolues à
l’optimalité à l’étape 2 par les deux approches (il y en a 28 instances en tout), le temps de
résolution est de 326,1 secondes en moyenne pour l’approche exacte et 332,01 secondes en
moyenne pour la méthode que nous avons développée. Donc, ces temps restent
comparables.
Selon les résultats rapportés dans le Tableau 15, on constate que le temps total de résolution
obtenu avec l’approche de base et aussi la Variante 2, dans le cas des grandes instances, est
plus grand que le temps limite prédéfini par la condition d’arrêt. Ceci est dû au fait que la
condition d’arrêt n’est vérifiée que lorsque l’étape de chargement et de sélection est
terminée. Donc, si le temps de résolution total atteint une valeur plus petite que le temps
limite de résolution (même avec une différence de quelques secondes) à la fin d’une
itération donnée, on passe à la prochaine itération sans prendre en considération le temps
requis pour achever cette dernière.
Les Figures 18 et 19 résument la variation du temps total moyen de résolution des quatre
approches en fonctions des instances avec un nombre de clients maximal à visiter égal à 4
clients.
87
Figure 18 : Variation du temps total de résolution (4 CDAHs)
Figure 19 : Variation du temps total de résolution (5 CDAHs)
D’après les Figures 18 et 19, nous remarquons que les temps qui caractérisent les approches
que nous avons développées sont inférieurs aux temps de résolution obtenus avec
l’approche exacte. Ces temps sont relativement faibles pour les instances de petite taille,
ceci indépendamment du nombre de CDAH(s) et du nombre de clients à satisfaire. Par
contre, pour l’instance (5, 15) nous avons rapporté un temps total de résolution avec
l’approche de base supérieur à celui de l’approche exacte. En effet, nous avons signalé dans
le chapitre précédent qu’à chaque itération on met à jour l’ensemble des routes semi-
réalisables, ensuite on passe de nouveau à la résolution du MIP sans prendre en
considération la résolution faite à l’itération précédente. L’augmentation de l’ensemble des
routes vides induit un temps de résolution très important lorsque la taille de l’ensemble est
importante.
Les Figures 18 et 19 montrent aussi que les temps enregistrés (temps de génération et temps
de sélection et chargement), pour toutes les approches, augmentent considérablement
lorsque le nombre de clients à satisfaire est plus élevé. Pour l’approche exacte, nous
constatons que le temps de la première et de la deuxième étape ne dépasse pas la demi-
heure avec les instances de petite taille (15 clients). Ainsi pour les instances avec un
nombre de clients supérieur à 20, le temps de génération est supérieur à une heure (où un
nombre maximal de clients visités par une route égal à 4 clients) et le temps de la sélection
002 0004 0006 0008 000
10 00012 00014 00016 000
(4, 15) (4, 20) (4, 25)
Seco
nds
Instance
T_Temps (A) T_Temps (B)
T_Temps (C) T_Temps (E)
00
2 000
4 000
6 000
8 000
10 000
12 000
(5, 15) (5, 20) (5, 25)
Seco
nds
Instance
T_Temps (A) T_Temps (B)
T_Temps (C) T_Temps (E)
88
est toujours égal à 3600 secondes (temps limite de résolution de CPLEX). Ceci est expliqué
par le grand nombre de combinaisons possibles lorsque la taille de l’instance augmente.
Dans l’analyse des tableaux de la section précédente, nous avons mentionné que même si le
MIP de l’étape de chargement est résolu à l’optimalité avec les méthodes qui nous avons
développées, la solution obtenue ne garantit pas l’optimalité pour le VRP-RS (Problèmes
de tournées de véhicules en région sinistrée). En effet, l’ensemble des tournées semi-
réalisables considéré ne regroupe pas toutes les possibilités.
En conclusion, les tests expérimentaux menés sur le temps de résolution du problème
montrent que l’approche exacte proposée par Berkoune et al. (2011) permet de résoudre les
problèmes de petite taille à l’optimalité et avec des temps relativement courts. Par contre,
lorsque le nombre de clients dans un ensemble dépasse 20 clients, la résolution demande
encore plus de temps à cause du temps requis pour la génération des tournées semi-
réalisables ainsi que l’étape de sélection optimale des routes. De plus, nous avons remarqué
que pour les 12 instances avec 25 clients, deux seulement sont résolues à l’optimalité. Ceci
est dû entre autres au fait que lorsque le nombre de tournées semi-réalisables est grand, une
énumération complète de toutes les routes ne serait pas envisageable tant au niveau de la
première étape de génération que de la deuxième étape de résolution du MIP. Par contre, la
Variante 2 que nous avons proposée serait une alternative envisageable pour des problèmes
de grande taille. Les résultats obtenus montrent que pour la plupart des instances
considérées dans cette étude, les solutions obtenues par la Variante 2 s’écartent
relativement peu de l’optimum. De plus, le temps de résolution total de ces instances reste
relativement petit.
5.7. Conclusion
Dans ce chapitre nous avons présenté les différents résultats numériques obtenus à partir
des séries d’expérimentations basées sur des problèmes tests, afin d’étudier l’effet de la
variation de la condition d’arrêt sur les performances de la méthode développée. Ensuite,
nous avons proposé une nouvelle condition d’arrêt basée sur le nombre d’itérations sans
amélioration de la solution. De plus, nous avons étudié l’effet des modifications proposées
sur les performances de l’approche de base en termes de la qualité de la solution obtenue et
89
du temps de résolution. Ceci est dans le but de déterminer la meilleure variante développée.
Finalement, nous avons élaboré une analyse des performances des approches que nous
avons développées (l’approche de base et la Variante 2) par rapport aux approches
proposées par Berkoune et al. (2011). Cette étude a porté sur des paramètres clés à savoir le
nombre de CDAH(s) et le nombre de clients à servir, dans l’objectif de connaitre l’impact
de ces paramètres sur la qualité de la solution obtenue ainsi que le temps de résolution.
Les résultats obtenus, à partir des variantes modifiées de l’approche de base proposée, nous
ont permis de conclure que l’augmentation de la taille de l’ensemble des routes ajoutées à
chaque itération peut être une solution envisageable pour l’amélioration la qualité de la
solution obtenue spécialement lorsque la taille du problème devient grande. Par ailleurs, la
Variante 3 permet la réduction du temps de la résolution du modèle (P) et par conséquent le
temps total de résolution. Nous avons remarqué aussi que la Variante 2 domine les autres
versions proposées.
En outre, les expérimentations menées sur la qualité de la solution obtenue montrent que les
approches que nous avons développées permettent une résolution optimale du MIP presque
pour toutes les instances. Par contre, pour l’approche exacte nous n’avons atteint
l’optimalité que pour un nombre limité d’instances. Ceci découle de la limitation du temps
pour la phase de chargement qui exige en lui-même l’arrêt de l’exécution du MIP. De plus,
nous avons constaté que le modèle MIP est résolu à l’optimalité avec la Variante 2 et que
l’écart par rapport à la solution optimale du VRP-RS peut être relativement petit.
D’après les tests expérimentaux considérés sur le temps de résolution du problème, nous
pouvons conclure que l’approche exacte proposée par Berkoune et al. (2011) permet de
résoudre les problèmes de petite taille à l’optimalité et avec des temps relativement courts.
Par ailleurs, lorsque le nombre de clients dans un ensemble dépasse 20 clients, la Variante
2 que nous avons proposée serait une bonne alternative. En effet, les solutions obtenues par
l’approche proposée s’écartent relativement peu de l’optimum avec un temps de résolution
total qui reste relativement petit.
91
CHAPITRE 6
CONCLUSION
Le présent mémoire aborde une version complexe du problème de distribution à savoir le
problème de distribution de l’aide humanitaire en situation d’urgence. Malgré que la
résolution de ce problème montre beaucoup de similarité avec le problème de tournées
multi-dépôts, multi-produits et multi-véhicules avec livraison partagée, le contexte de
déploiement en situation d’urgence attribut au problème étudié des restrictions spécifiques,
telles que le temps d’accès maximum, le nombre de visites maximum par tournée, le
nombre de visites maximum par client, etc.
L’approche de base que nous avons proposée consiste en une méthode de résolution basée
sur un critère heuristique, capable d’améliorer la qualité de la solution obtenue avec
l’approche heuristique déjà proposée par Berkoune et al. (2011). L’approche développée
subdivise l’algorithme de résolution en deux phases. La première phase consiste à la
génération d’une solution initiale en se basant sur l’approche heuristique proposée par
92
Berkoune et al. (2011), qui est à son tour composée de deux étapes (énumération partielle
de routes semi-réalisables et chargement et sélection des meilleures routes via MIP). La
deuxième phase permet l’amélioration itérative de la dernière meilleure solution déjà
obtenue dont la condition d’arrêt est un temps limite prédéfini (en cohérence avec le
contexte d’urgence). En effet, la deuxième phase de l’algorithme proposé permet
l’augmentation du nombre de tournées semi-réalisables à travers une énumération
exhaustive et conditionnelle. Ensuite, nous avons proposé trois variantes modifiées de
l’approche de base développée. L’objectif principal de deux premières variantes consiste à
augmenter la taille de l’ensemble des tournées semi-réalisables générées à chaque itération.
Par contre, la Variante 3 a comme objectif l’élimination d’un sous-ensemble de routes non
sélectionnées avec le modèle (P) durant un certain nombre d’itérations.
Dans le but d’évaluer la condition d’arrêt puis choisir la meilleure, nous avons opté à
étudier l’impact de la variation du temps de résolution limite sur les performances de
l’approche de base que nous avons développée. Ensuite, nous avons proposé le nombre
d’itérations sans amélioration de la solution obtenue comme un critère d’arrêt. Les résultats
obtenus montrent que les performances de la méthode développée ne dépendent pas de la
variation de la valeur du temps de résolution maximal. Ce constat nous a amenés à garder la
valeur initiale du temps de résolution maximal. Par ailleurs, nous avons constaté que la
variation du nombre d’itérations sans amélioration de la solution générée influence les
performances de la solution obtenue en termes de qualité.
D’après les expérimentations menées sur les deux premières variantes modifiées de
l’approche proposée, nous avons constaté que la qualité de la solution obtenue peuvent être
améliorées lorsqu’on augmente la taille de l’ensemble des routes ajoutées à chaque
itération, cette constatation est vrai pour les problèmes de grande taille. Ceci nous a permis
de conclure que l’augmentation de la taille de l’ensemble des routes générées à chaque
itération peut être une solution envisageable pour améliorer les performances de l’approche
que nous avons proposée. Par ailleurs, la Variante 3 nous a permis de réduire le temps
d’exécution du MIP et par conséquent le temps total de résolution, mais elle reste toujours
dominée par la Variante 2 améliorée.
93
Dans la même optique que l’étude menée sur l’impact des modifications que nous avons
développées, nous avons effectué une analyse comparative plus large entre les résultats
obtenus par nos deux approches (l’approche de base et la Variante 2) et ceux générés par
les deux approches développées par Berkoune et al. (2011) en se basant sur des instances
aléatoires. Les expérimentations menées sur les performances des approches proposées
montrent que pour des problèmes de petite taille, l’approche exacte (Berkoune et al. 2011)
atteint l’optimalité dans un temps de calcul relativement petit. Par contre, pour des
problèmes de plus grande taille, la Variante 2 proposée génère des résultats plus
prometteurs en termes de performances de résolution à savoir la qualité de la solution
obtenue et le temps du calcul. En outre, l’écart entre la solution obtenue par l’approche
proposée et la solution optimale du VRP-RS peut être relativement grand et il varie en
fonction de la variation des paramètres clés. Ce résultat reste vrai dans le cas où la solution
obtenue par l’approche proposée est optimale.
Cependant, il serait intéressant d’envisager le développement d’autres méthodes permettant
d’améliorer l’approche développée. Proposer une approche qui consiste à charger les routes
pendant l’étape de génération de tournées semi-réalisables, afin de réduire le MIP tout en
supprimant les contraintes de capacité et du volume. Puisque notre approche consiste à
ajouter un ensemble de routes à chaque itération, nous pouvons utiliser les fonctionnalités
de CPLEX pour récupérer le branchement de l’itération précédente et ensuite le déployer
pendant l’itération en question. Finalement, l’utilisation de la programmation dynamique
pour résoudre le problème en question présente également un axe de recherche très
intéressant et qui mérite un intérêt de développement bien approfondit.
Dans le cadre de ce mémoire, notre intérêt principal s’est situé au niveau opérationnel de la
logistique en situation d’urgence. Ce volet consiste principalement à l’acheminement de
l’aide humanitaire pour satisfaire la demande des zones touchées dans les plus brefs délais.
Toutefois, et de manière à mieux adopter le problème abordé à un contexte plus fidèle à la
réalité du terrain, il est impératif de considérer les niveaux tactique et stratégique en
intégrant des activités supplémentaires exigées par la nature du problème traité. Ces
considérations supplémentaires peuvent porter sur la probabilité d’occurrence des
94
catastrophes naturelles, leurs ampleurs et leurs localisations géographiques ainsi que la
capacité des dépôts, la longueur des routes et l’aspect multi-objectif du problème.
96
BIBLIOGRAPHIES
Altay, N., Green III, W. G., OR/MS research in disaster operations management. European Journal of Operational Research, 175, 2006, 475-493.
Altinel I. K. & Öncan T., A new enhancement of the Clarke and Wright savings heuristic for the capacited vehicle routing problem. Journal of the Operational Research Society, 56, 2005, 954-961.
Applegate D., Bixby R.E., Chvátal V. & Cook W.J., The traveling salesman problem: A computational study. Princeton University Press, Princeton, 2006.
Applegate D., Cook W. & Rohe A., Chained Lin-Kernighan for large traveling salesman problems. INFORMS Journal on Computing, 15, 1, 2003, 82-92.
Babin G., Deneault S. & Laporte G., Improvements to the Or-opt heuristic for the symmetric traveling salesman problem. Journal of the Operational Research Society, 58, 2007, 402-407.
Balcik B., Beamon B. M. & Smilowitz K., Last mile distribution in humanitarian relief. Journal of Intelligent Transportation Systems, 12, 2008, 51-63.
Baldacci R., Christofides N. & Mingozzi A., An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming, 115, 2008, 351-385.
Baldacci R., Toth P. & Vigo D., Recent advances in vehicle routing exact algorithms. 4OR: A Quarterly Journal of Operations Research, 5, 2007, 269-298.
Berkoune D., Rekik M., Ruiz A. et Renaud J., Approches de résolution à deux étapes pour le problème de tournées de véhicules en région sinistrée. 9e Congrès International de génie industriel, St-Sauveur, Québec, 12-14 octobre 2011.
Chern C. C., Chen Y. L. & Kung L. C., A heuristic relief transportation planning algorithm for emergency supply chain management. International Journal of Computer Mathematics, 2009, 1-27.
Clarke G. & Wright J.W., Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 1964, 568-581.
Cornillier, F., Laporte, G., Boctor, F., Renaud, J., The petrol station replenishment problem with time windows. Computers and Operations Research, 36, 2009, 919-935.
97
Colorni A., Dorigo M. & Maniezzo V., Distributed Optimization by Ant Colonies. Proceedings of the First European Conference on Artificial Life, Paris, France, F.Varela & P.Bourgine (Eds.), Elsevier Publishing, 1991, 134-142.
Cordeau J.-F., Gendreau M., Hertz A., Laporte G. & Sormany J.-S. New heuristics for vehicle routing problem. In Logistics Systems: Design and Optimization (Eds A. Langevin & D. Riopel), Springer, Boston, 2005, 279-297.
Dantzig G.B., Fulkerson D.R. & Johnson S.M., Solution of a large-scale traveling salesman problem. Operations Research, 2, 1954, 393-410.
Fisher M.L. & Jaikumar R., A generalized assignment heuristic for vehicle routing problem. Networks, 11, 1981, 109-124.
Fukasawa R., Longo H., Lysgaard J., Poggi de Aragao M., Reis M., Uchoa E. & Werneck R.F., Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming, 106, 2006, 491-511.
Ghaziri H., Solving routing problems by a self-organizing map. Artificial Neural Networks, T. Konhonen, K. Makisara, O. Simula & J. Kangas (Eds), North-Holland, Amsterdam, 1991, 829-834.
Gillett B.E. & Miller L.R., A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22, 1974, 340-349.
Girard S., Renaud J. & Boctor F.F., A simple and efficient perturbation heuristic to solve the vehicle routing problem. Working paper, FSA, Université Laval, 2005.
Haddow, G. D., Bullock, J. A., Coppola, D. P., Introduction to Emergency Management. Butterworth-Heinemann homeland security series, Elsevier Inc, 2008.
Helsgaun K., An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126, 2000, 106-130.
Holland J.H., Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor, MI, 1975.
Jotshi, A., Gong, Q., Batta, R., Dispatching and routing of emergency vehicles in disaster mitigation using data fusion. Socio-Economic Planning Science 43, 1, 2009, 1-24.
Kara I., Laporte G. & Bektas T., A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem. European Journal of Operational Research, 158, 2004, 793-795.
98
Kinderwater G.A.P. & Savelsbergh M.W.P., Vehicle routing: Handling edge exchanges. In: Aarts E.H.L. & Lenstra J.K. (eds), Local Search in Combinatorial Optimization, Wiley, Chichester, 1997, 337-360.
Laporte G., The Traveling Salesman Problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59, 1992, 231-247.
Laporte, G., A concise guide to the Traveling Salesman Problem. Journal of the Operational Research Society 61, 2010, 35-40.
Laporte, G., What you should about the vehicle routing problem. Naval Research Logistics, 54, 2007, 811-819.
Laporte G. & Nobert Y., Exact algorithms for the vehicle routing problem. Annals of Discrete Mathematics, 31, 1987, 147-184.
Laporte G. & Osman I.H., Routing Problems: A Bibliography. Annals of Operations Research, 61, 1995, 227-262.
Laporte G. & Semet F., Classical heuristics for the capacitated VRP. In The Vehicle Routing Problem, P. Toth & D. Vigo (eds), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002, 109-128.
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.
Lin, S., Computer solutions of the traveling salesman problem. Bell System Computer Journal, 44, 1965, 2245-2269.
Or I., Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Ph D thesis, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, 1976.
Osman I.H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41, 1993, 421–451.
Prins C., A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31, 2004, 1985–2002.
Rego C. & Roucairol C., A parallel tabu search algorithm using ejection chains for the vehicle routing problem. In I.H. Osman & J.P. Kelly, editors, Meta-Heuristics: Theory and Applications, Kluwer, Boston, 1996, 661–675.
99
Reimann M., Doerner K. & Hartl R.F., D-Ants: Savings based ants divide and conquer the vehicle routing problem. Computers & Operations Research, 31, 2004, 563-591.
Renaud J., Boctor F.F. & Laporte G., A fast composite heuristic for the symmetric traveling salesman problem. INFORMS Journal on Computing, 8, 2, 1996a, 134-143.
Rochat Y. & Taillard É.D., Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1, 1995, 147–167.
Rosenkrantz D.J., Stearns R.E. & Lewis II P.M., An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6, 3, 1977, 563-581.
Ryan D.M., Hjorring C. & Glover F., Extensions of the Petal Method for Vehicle Routing. Journal of the Operational Research Society, 44, 1993, 289-296.
Schumann M. & Retzko R., Self-organizing maps for vehicle routing problems - minimizing an explicit cost function. Proceedings of the International Conference on Artificial Neural Networks, F. Fogelman-Soulie (Ed), Paris, 1995, 401-406.
Sheu, J.-B., Challenges of emergency logistics management. Transportation Research Part E 43, 2007, 655-659.
Sheu J.-B., Dynamic relief-demand management for emergency logistics operations under large-scale disasters. Transportation Research Part E, 46, 2010, 1-17.
Tarantilis C.D. & Kiranoudis C.T., BoneRoute: An adaptive memory-based method for effective fleet management. Annals of Operations Research, 32, 2005, 2309-2327.
Thompson P.M. & Psaraftis H.N., Cyclic transfer algorithms for multi-vehicle routing and scheduling problems. Operations Research, 41, 1993, 935-946.
Toth P. & Vigo D., The vehicle routing problem. SIAM monographs on discrete mathematics and applications, 2002.
Tufekci S., Wallace W.A., The emerging area of emergency management and engineering, IEEE Transactions on Engineering Management, 45, 2, 1998, 103-105.
Tzeng G.-H., Cheng H.-J. & Huang T. D., Multi-objective optimal planning for designing relief delivery systems. Transportation Research Part E, 43, 2007, 673-686.
Xu J. & Kelly J.P., A network flow-based tabu search heuristic for the vehicle routing problem. Transportation Science, 30, 1996, 379-393.
100
Wen, M., Cordeau, J.-F., Laporte, G., Larsen, J., The dynamic multiperiod vehicle routing problem. Computers and Operations Research, 37, 2010, 1615-1623.
Yi W. & Kumar A., Ant colony optimization for disaster relief operations. Transportation Research Part E, 43, 2007, 660-672.
Yi W. & Özdamar L., A dynamic logistics coordination model for evacuation and support in disaster response activities. European Journal of Operational Research, 179, 2007, 1177-1193.
