Sawadogo Marie SMZ1137 PDF
Sawadogo Marie SMZ1137 PDF
Sawadogo Marie SMZ1137 PDF
Contact : ddoc-theses-contact@univ-lorraine.fr
LIENS
Spécialité : Automatique
Par
Marie SAWADOGO
À mes parents
À mes frères et sœurs
À toi mon chéri
À ma tante Habibou, tu es partie trop tôt…
2
Merci
Celui qui ne sait pas apprécier les petits actes de bienveillance ne mérite pas de recevoir de grands actes de
bienveillance (proverbe Bambara/ Maa min jona fèn fitinin na o makan ni fènba) fènba
Remerciements
La route a été longue, parfois semée d’embuches, mais nous y sommes arrivés. Je tiens à
remercier tous ceux qui ont participé de près où de loin à l’aboutissement de cette thèse.
J’aimerais avant tout témoigner toute ma gratitude à mon directeur de thèse, Monsieur Didier
ANCIAUX. Je tiens à le remercier de m’avoir soutenue à chaque instant de cette thèse. Merci
pour vos conseils précieux, votre confiance et vos encouragements sans cesse renouvelés.
Merci de n’avoir pas hésité à mettre la main à la pâte quand il le fallait pour m’aider à
avancer. Grâce à votre rigueur et votre disponibilité, j’ai pu avancer dans cette thèse et
travailler dans de bonnes conditions. Bien plus qu’un encadrement pédagogique, vous avez su
m’enseigner les rudiments du métier de chercheur et me conseiller pour ma carrière future. Je
suis très fière d'avoir travaillé à vos côtés.
Je remercie messieurs Teodor Gabriel CRAINIC et Jin-Kao HAO pour l’intérêt qu’ils ont
accordé à cette thèse en acceptant de la rapporter. Je remercie également messieurs Patrick
BURLAT, André THOMAS et Bernard GRABOT de m’avoir fait l’honneur de juger mon
travail.
Mes remerciements vont à tous ceux (amis, connaissances, oncles, tantes, belle-famille…) qui
de près ou de loin m’ont soutenu tout au long de mon cursus et pendant ma thèse.
Je ne saurais terminer sans remercier les personnes chères à mon cœur à savoir ma famille
(Clémentine et Zakarie SAWADOGO mes parents, mes frères et sœurs Félicité, Joséphine,
Flavien et Maxime) et mon fiancé Sayouba TIEMTORE qui ont été pour moi un appui et une
source de motivation tout au long de ces trois années. Merci pour votre patience et vos
encouragements.
Wend na rolé
3
Résumé
Résumé
Cette thèse est réalisée au sein du Laboratoire de Génie Industriel et Production de Metz
(LGIPM) et s'inscrit donc dans une dynamique à la fois européenne et mondiale qui est la
réduction des impacts environnementaux et sociétaux des systèmes de transport. Notre but est
de développer un système d'aide à la décision au choix d'un itinéraire de fret ayant le moins
d'impacts possible sur l'environnement et la société.
Pour se faire, nous avons défini des fonctions qui permettent de calculer pour chaque chemin
d'un réseau de transport intermodal, les critères économiques (coût, temps, dégâts dus aux
transbordements) et les critères écologiques (pollution, consommation d'énergie, nuisances
sonores et risque d'accident) à considérer. Par la suite, nous avons construit un modèle de plus
court chemin multiobjectif permettant d’optimiser les sept critères ainsi définis. Pour résoudre
ce modèle, un algorithme de colonies de fourmis multiobjectif a été mis en place afin de
prendre en compte le grand nombre de critères et l'intermodalité du réseau. Une
implémentation est ensuite réalisée sur un réseau de transport intermodal se basant sur des
données géographiques réelles et les performances de l’algorithme mis en place sont
analysées et prouvées.
Abstract
The topic of this thesis is about environmental and societal impacts abatement within the
green supply chain. This thesis is taking place in the Laboratory of Industrial Engineering and
Production of Metz (LGIPM). Our goal is to develop a decision support system in choosing a
path with the less environmental and societal impacts.
For building our decision support system, we defined a mathematical model which computes
for each part in our transportation network, the travel time, the transportation cost and the
damage due to transshipment, the amount of greenhouse gas emissions that are emitted, the
energy consumption, the noise emitted and the accident risk. From this graph, we built a
multiobjective shortest path problem. A multiobjective ant colony algorithm MOSPACO (Ant
colony optimization for multiobjective shortest path problem) is then proposed to solve the
proposed multiobjective shortest path problem; this new algorithm aims to take into account
the large number of criteria and intermodal network. The running of the algorithm gives a
Pareto front from which the decision maker can choose his desired itinerary.
4
Table des matières
5
Table des matières
6
Table des matières
8
Table des figures
Figures
Figure 1. Part des émissions de CO2 liés au transport (CEMT 2007) .................................................. 13
Figure 3. Modèle fonctionnel de l’organisation de la chaine logistique tenant compte des aspects
environnementaux (Sarkis, 2003). ......................................................................................................... 20
Figure 4. Actions majeures en chaîne logistique verte .......................................................................... 21
Figure 5. Objectifs du transport durable ............................................................................................... 22
Figure 6. Les diverses formes de transport intermodal (Toubol, 2007) ................................................ 23
Figure 7. Graphe multi-valué (Ziliaskopoulos et Wardell, 2000) ......................................................... 25
Figure 8. Modèle d’hypergraphe intermodal avec temps de transport et fréquence (Lozano et Storchi,
2002)...................................................................................................................................................... 25
Figure 9. Exemple de chemin intermodal avec un arc de transfert (Lozano et Storchi, 2001) ............. 26
Figure 10. Évolution prévisionnelle du fret par mode de transport (Transport White Paper, 2006) .... 29
Figure 11. Roue de l’impact (Sawadogo et Anciaux, 2011).................................................................. 31
Figure 12. Courbes d’estimation des émissions de CO2 (Mt) dans le monde de 2000 à 2050 (OECD
and the international transport forum, 2008) ......................................................................................... 31
Figure 13. Réduction des impacts du transport ..................................................................................... 34
Figure 14. Exemple de front de Pareto.................................................................................................. 36
Figure 15. Choix du plus court chemin par une colonie de fourmi ....................................................... 47
Figure 16. Modèle du processus décisionnel de choix de chemin intermodal ...................................... 59
Figure 17. Réseau de transport intermodal ........................................................................................... 60
Figure 18. Évolution de la pénalité de remplissage (surcoût) en € en fonction du poids de
marchandises acheminées (cas de l’unité non remplie) ........................................................................ 65
Figure 19. Courbe de praticité en fonction de la distance pour l’avion ............................................... 74
Figure 20. Courbe de praticité en fonction de la distance pour le camion ........................................... 74
Figure 21. Courbe de praticité massique pour l’avion.......................................................................... 75
Figure 22. Courbe de praticité massique pour le camion ..................................................................... 76
Figure 23. Une fourmi dans le graphe G............................................................................................... 83
Figure 24. Fronts de Pareto pour différentes valeurs de α et β ............................................................ 87
Figure 25. Front de Pareto pour les meilleures configurations de α et β (Pareto coût/Temps 42 ~ α =
4 ; β = 2)................................................................................................................................................ 88
Figure 26. Hiérarchie AHP utilisée ....................................................................................................... 89
Figure 27. Fronts de Pareto pour = 0.01 à 0.5 ................................................................................. 95
Figure 28. Fronts de Pareto pour = 0.1 à 1 ...................................................................................... 96
9
Table des figures
Figure 29. Courbes de convergence pour = 0,01 ; = 0,4 et = 1 pour Coût/Temps ................ 97
Figure 30. L’algorithme formel de MOSPACO..................................................................................... 97
Figure 31. Page d’accueil de l’outil MOSPACO ................................................................................ 104
Figure 32. Les onglets de l’outil .......................................................................................................... 105
Figure 33. Réseau routier des 100 villes étudiées ............................................................................... 106
Figure 34. Réseau ferroviaire des 100 villes étudiées ......................................................................... 106
Figure 35. Réseau maritime des 100 villes étudiées ............................................................................ 106
Figure 36. Saisie des paramètres de transport .................................................................................... 107
Figure 37. Saisie des paramètres de MOSPACO ................................................................................ 108
Figure 38. Choix des préférences ........................................................................................................ 108
Figure 39. Choix du taux de dégâts ..................................................................................................... 109
Figure 40. Résultat pour une préférence Pollution/Énergie................................................................ 111
Figure 41. Front de Pareto Pollution/Bruit......................................................................................... 112
Figure 42. Front de Pareto Pollution/Accident ................................................................................... 113
Figure 43. Front de Pareto Énergie/Bruit ........................................................................................... 114
Figure 44. Front de Pareto Accident/Bruit.......................................................................................... 115
Figure 45. Front de Pareto Énergie/Accident ..................................................................................... 115
Figure 46. Front de Pareto Pollution/Énergie/Bruit ........................................................................... 116
Figure 47. Exemple de chemin trouvé pour Pollution/Énergie/Bruit/Accident ................................... 117
Figure 48. Comparaison des fronts de Pareto Coût/Temps avec praticité (points bleus/étoiles) et sans
praticité (points rouges/triangles) ....................................................................................................... 118
Figure 49. Comparaison des fronts de Pareto Coût/Temps avec (points bleus/étoiles) et sans praticité
(points rouges/triangles) ..................................................................................................................... 119
Figure 50. Front de Pareto Coût/Dégâts............................................................................................. 119
Figure 51. Front de Pareto Temps/Dégâts .......................................................................................... 120
Figure 52. Chemin obtenu pour la stratégie gradient ......................................................................... 128
Figure 53. Évolution de l’entropie moyenne pour Énergie/Bruit ........................................................ 129
Figure 54. Évolution de l’entropie moyenne pour Coût/Temps........................................................... 130
Figure 55. Échelle de 1 à 9 de Saaty ................................................................................................... 152
Figure 56. Matrices de jugement ......................................................................................................... 152
Figure 57. Matrices de jugement pour les sous-critères de la pollution ............................................. 153
Figure 58 : Front de Pareto obtenus pour ρ=0,1 ; ρ=0,2 ; ρ=0,3 ...................................................... 153
Figure 59. Exemples de front de Pareto pour les meilleures configurations de ρ pour Énergie/Bruit 154
10
Table des Tableaux
Tableaux
Tableau 1. Coût moyen des impacts par mode de transport pour le transport de marchandise et le
transport de personnes en Europe INFRAS Zurich (Schreyer et al., 2005) ......................................... 30
Tableau 2. Facteur d’émission moyenne des polluants pour le fret (Knorr et Reuter, 2005) ............... 68
Tableau 3. Facteur de consommation moyenne d’énergie pour le fret (Knorr et Reuter, 2005) .......... 69
Tableau 4. Poids des critères pour le scénario industriel ..................................................................... 89
Tableau 5. Poids des critères pour le scénario écologique ................................................................... 89
Tableau 6. Préférences du décideur ...................................................................................................... 92
Tableau 7. Tableau comparatif des résultats pour Saint-Pétersbourg - Séville .................................. 127
Tableau 8. Écart-type et moyennes pour Énergie/bruit....................................................................... 131
Tableau 9. Ecart-type et moyennes pour Coût/Temps ......................................................................... 132
11
Introduction
Introduction
Introduction
Contexte et problématique
Par ailleurs, cette thèse est née d’un constat à la fois national et mondial ; c’est que le secteur
du transport et en particulier le transport de marchandises est l’un des secteurs économiques
émettant le plus de gaz à effets de serre (Figure 1).
La chaîne logistique est ainsi entrée dans une ère où les défis environnementaux et sociétaux
sont au cœur des préoccupations non seulement des décideurs, mais également des
populations touchées par ces activités. Comment transporter des marchandises jusqu’au client
final en impactant le moins possible la société et l’environnement, tout en garantissant un
13
Introduction
temps de transport raisonnable ainsi qu’un coût satisfaisant les parties prenantes ? Comment
trouver un compromis entre ces différents aspects ? Cette thèse essaie de proposer une
réponse à ces interrogations.
Les critères environnementaux, économiques et sociétaux pris en compte dans notre étude
sont le « coût de transport », le « temps de transport », les « dégâts dus aux
transbordements », la « pollution atmosphérique », la « consommation d’énergie », les
« nuisances sonores », et le « risque d’accident ». L’objectif de notre étude est de développer
un système d’aide à la décision au choix d’un chemin dans un système de transport intermodal
permettant de réduire ces impacts. Le coût et le temps de transport ne sont donc plus les seuls
critères de choix d’un chemin. Dans ce cas, l’aspect environnemental n’est plus intégré en tant
qu’une contrainte, mais en tant qu’un objectif à atteindre. Le système proposé devra, d’une
part, guider le décideur au choix d’un itinéraire intermodal (succession de modes et de
chemins) avec le meilleur compromis socio-environnemental et économique possible. D’autre
part, nous visons également à apporter des réponses à la gestion du trafic, notamment par la
prise en compte des problèmes de congestion dans notre système de décision.
• Étape 1 : La première étape consiste en une recherche bibliographique sur les thèmes
relatifs au sujet de la thèse. Celle-ci est résumée dans le chapitre 1. Dans un premier
temps, nous définissons la chaîne logistique dans sa globalité avant de passer à la
définition de la chaîne logistique verte et à un état de l’art sur les méthodes de gestion des
14
Introduction
chaînes logistiques vertes. Ce chapitre est également consacré à l’étude des systèmes de
transport intermodaux ainsi qu’à une revue de la littérature sur la modélisation et la
planification de tels systèmes. Nous étudierons également les problèmes d’optimisation
multiobjectif et plus particulièrement le problème de plus court chemin multiobjectif.
Pour finir, une revue de la littérature sur les algorithmes de colonies de fourmis et leurs
applications aux problèmes d’optimisation multiobjectif sera présentée.
• Étape 3 : Une fois le modèle théorique défini, nous présentons un algorithme permettant
de construire le système d’aide à la décision et ainsi d’optimiser l’ensemble des critères.
Cette étape correspond au chapitre 3 dans lequel nous proposons MOSPACO (Ant
Colony Optimization for MultiObjective Shortest Path), une nouvelle variante
d’algorithme de colonies de fourmis multiobjectif permettant d’optimiser plusieurs
objectifs appliqué au cas du transport intermodal au sein des chaînes logistiques vertes.
15
Chapitre 1. Généralités et état de l’art
16
Chapitre 1. Généralités et état de l’art
Introduction
Cette thèse est au croisement de plusieurs disciplines qui vont de la logistique, à la recherche
opérationnelle, en passant par les sciences de l’environnement. En effet, nos investigations
intègrent à la fois, les techniques de management environnemental (normes ISO 14000,
14001...) et l’évaluation des impacts environnementaux, la gestion du trafic intermodal, et
cela en utilisant des techniques de modélisation et de résolution issues de la recherche
opérationnelle. Le chapitre 1 est un chapitre introductif de cette thèse qui présente une revue
de la littérature concernant ce sujet de recherche et les domaines connexes que nous avons
été amenés à étudier.
L’étude bibliographique a donc porté à la fois sur des thèmes relatifs au sujet de la thèse,
notamment les études existantes en matière de réduction des impacts environnementaux du
transport et, en plus, sur des modèles mathématiques et des méthodes de résolution issue de
la recherche opérationnelle à même de nous aider à réaliser notre système de décision. Il
s’agissait ici de dégager, en tout premier lieu les différents impacts (détérioration de la
qualité de l’air, dégâts matériels, pollution des sols...) que peut avoir le transport intermodal
sur l’environnement et la société. Une recherche a ensuite été menée sur les travaux existants
sur la modélisation des réseaux de transport intermodaux. Dans cette section nous
introduirons également les définitions relatives à la gestion de la chaîne logistique, la chaîne
logistique verte et le transport intermodal ainsi que les méthodes de résolution telles que
l’optimisation multiobjectif et le problème de plus court chemin multiobjectif.
17
Chapitre 1. Généralités et état de l’art
nombreuses études sont de plus en plus menées dans ce sens ; et celles présentées dans la
littérature sont évoquées dans cette section.
Beamon (Beamon, 1998) quant à elle définit la chaîne logistique comme un processus intégré,
dans lequel un certain nombre d’acteurs différents (fournisseurs, fabricants, distributeurs et
détaillants) travaillent ensemble dans le but :
Historiquement, les études et les recherches de solutions sur les impacts des activités
industrielles ont toujours été au cœur des préoccupations à la fois du monde industriel, mais
aussi des défenseurs de la nature. En effet, l’idée de taxes (pollueur/payeur) pour réduire la
pollution émanant des activités industrielles a été émise depuis le début du 20e siècle (Pigou,
1920). Très souvent, la réduction des déchets et de la pollution industrielle est motivée par des
raisons économiques ou des règlementations (EURO 5, EURO 6) sans oublier les pressions
des instances politiques et l’image de marque auprès des clients (normes ISO 14000 et
18
Chapitre 1. Généralités et état de l’art
14001). De nos jours, les préoccupations environnementales sont plus que jamais au cœur des
débats politiques et scientifiques.
La gestion de la chaîne logistique verte trouve ses racines à la fois dans la gestion de
l’environnement et dans la gestion de la chaîne logistique. La définition et le champ
d’application de la chaîne logistique verte dans la littérature sont assez vastes et variés. Ils
vont des « achats verts ou achats responsables » (green purchasing), à la prise en compte des
impacts depuis le fournisseur jusqu’au client final en passant par la production jusqu’à la
logistique inverse qui tend à trouver de méthodes pour la gestion et le traitement des produits
en fin de vie. Srivastava (Srivastava, 2007) définit la gestion de la chaîne logistique verte
comme « l’intégration de la conscience environnementale dans la gestion de la chaîne
logistique, en incluant la phase de conception du produit, l’extraction et le choix des
matériaux et matières premières, le processus et les procédés de fabrication, la livraison du
produit fini au client ainsi que la gestion de la fin de vie du produit ». Selon Klassen (Klassen
et Johnson, 2002), il existe cinq méthodes de gestion de la chaine logistique verte ; la
certification environnementale, la prévention de la pollution, la logistique inverse, l’analyse
de cycle de vie et l’écoconception.
La chaîne logistique verte est aussi soucieuse de produire et de distribuer les marchandises de
façon durable en tenant compte des facteurs environnementaux et sociétaux. Ainsi, les
objectifs ne sont plus axés uniquement sur l'impact économique de la logistique, mais aussi
sur les effets sur la société et l'environnement. Les activités de la chaîne logistique verte
comprennent la mesure et l’analyse des impacts environnementaux des activités logistiques, la
réduction de la consommation d’énergie, la réduction, la gestion et le traitement des déchets
issus des activités logistiques, etc. La notion de logistique verte a ainsi fait naître une chaîne
logistique à deux sens ; la logistique directe et la logistique inverse gérant les flux retour,
formant ainsi une boucle fermée (Figure 2).
19
Chapitre 1. Généralités et état de l’art
Plusieurs études existent sur les différents aspects et méthodes concernant la chaîne logistique
verte. Une revue intéressante de la littérature est présentée par Zhang (Zhang et al., 1997) ;
elle met en évidence à la fois la prise en compte des impacts environnementaux dans la
conception des produits et l’analyse de cycle de vie des produits. Cette étude met également
l’accent sur la réduction des impacts pendant le processus de production et de gestion de la fin
de vie des produits (recyclage, réutilisation, re-manufacturing, gestion des déchets...). À cela,
il faut ajouter des études comme celles présentées par Min (Min et al., 1998) qui met en
évidence les problèmes de localisation et de routage dans la chaîne logistique verte.
Hormis ces études, d’autres méthodes peuvent être trouvées parmi lesquelles :
• Les méthodes de gestion des déchets (Hicks et al., 2004 ; Saadany et Jaber, 2010) ;
• La gestion des flux de la logistique inverse (El Korchi et Millet, 2011 ; Lee et al.,
2010) ;
20
Chapitre 1. Généralités et état de l’art
Sarkis soutient que l’organisation et la gestion de la chaîne logistique verte sont influencées
par un certain nombre de facteurs dont le cycle de vie du produit, la phase opérationnelle de la
chaîne logistique c’est-à-dire
dire les approvisionnements, la production, la distribution et la
logistique inverse en incluant les pratiques dictées par la prise en compte de l’aspect
environnemental, à savoir la gestion des déchets et les performances organisationnelles
préalables à la mise en place d’une chaîne logistique verte.
verte. Il définit un cadre de décision pour
la gestion et l’amélioration de la chaîne logistique verte (Sarkis,
( 2003).
On peut trouver dans la littérature d’autres aspects de la chaîne logistique verte ; des
références peuvent être trouvées dans les articles de synthèse publiés par Srivastava, Beamon
et par Sarkis (Srivastava,
Srivastava, 2007 ; Beamon, 2008 ; Sarkis et al., 2011).
•Transport
Transport combiné
•Modes
Modes de transport alternatifs
•logistique
logistique inverse gestion des flux retrour et transport des
Distribution flux retours
•Réduction
Réduction de la consommation d'énergie
•Utilisation
Utilisation de technologies propres
Fabrication •Diminution
Diminution des déchets de production
•Achats
Achats durables
Extraction de •Utilisation
Utilisation de matières premières non-polluantes
non
matières
premières
•Récyclage
Récyclage
Valorisation •Refabrication
Refabrication
du •Réutilisation
Réutilisation
produit
Le concept de mobilité durable a fait naître de nouveaux concepts de transport ainsi que des
de
technologies et méthodes managériales pour la réduction des impacts des systèmes de
transport. Ce concept de la mobilité durable a pour but de changer les habitudes en matière de
21
Chapitre 1. Généralités et état de l’art
transport afin de trouver un équilibre dans le triptyque « économie, écologie, société » (Figure
4), en d’autres termes ce concept a pour objectif de « mettre en œuvre des actions pour allier
développement économique et socio-écologique ».
Cette section sera consacrée à la présentation des impacts environnementaux et sociétaux des
systèmes de transport. Pour nous faire, nous allons dans un premier temps définir le transport
intermodal, puis nous présenterons les modèles de réseaux de transports intermodaux
existants ainsi que les études sur la planification d’itinéraires intermodaux, avant de détailler
les différents impacts et les méthodes existants pour réduire ou prévenir les conséquences
liées à ces impacts.
Le transport intermodal est défini par la Conférence Européenne des Ministres des Transports
(ECMT, 2001) comme étant le transport d’une charge utile (marchandises, hommes...) en
utilisant successivement deux ou plusieurs modes de transport (train, rail, bateau, route,
oléoduc...), d’un point « origine » à une « destination » donnée, sans avoir à dépoter les
marchandises d’un premier contenant pour les recharger dans un autre (Figure 5). Les
systèmes de transport intermodaux offrent donc un grand choix de mode de transport et
22
Chapitre 1. Généralités et état de l’art
Le transport intermodal combine les avantages de chaque mode de transport. Par exemple
pour le fret, il peut combiner les avantages de la route et du rail ; le rail pour les longues
distances et les grandes quantités et la route pour la distribution et/ou la collecte pour des
courtes et moyennes distances. Il vise à rééquilibrer l'utilisation du réseau et des modes de
transport exploités. Pour le cas du transport de personnes, il associe de façon complémentaire
la sécurité et l’efficacité d'un mode (par exemple, le train) à la souplesse d'un autre mode (par
exemple, le bus). Il présente également des avantages importants pour la collectivité en
constituant une bonne réponse aux problèmes de congestion, d’environnement et d’insécurité
routière. Cependant, le transport intermodal ne représente guère qu'environ 5 % du total des
transports terrestres (Conseil National des Transports CNT, 2005) en tonnes.kilomètres de
marchandises dans l'ensemble des pays européens.
Le transport intermodal est en pleine expansion ; les études menées sur de tels systèmes
portent le plus souvent sur les caractéristiques des réseaux intermodaux, la complexité des
algorithmes pour la modélisation des dits réseaux et l’optimisation des opérations en leur sein.
Les problématiques au sein des systèmes de transport intermodaux sont entre autres la
localisation et la modélisation des terminaux intermodaux, la planification d’itinéraires
intermodaux et la coordination des transbordements. Pour le fret intermodal, d’autres facteurs
doivent être pris en compte comme notamment la taille des lots à envoyer, le volume de
marchandises à transporter ainsi que les contenants utilisés.
La modélisation des réseaux de transport fait appel, dans la majorité des cas, à la théorie des
graphes. En effet, les problèmes de transport de marchandises peuvent être modélisés sous la
forme d’un problème d’optimisation de réseau de transport.
des nœuds représente les intersections entre ces chemins ; en d’autres termes, les nœuds
représentent des villes ou des points de dépôts et les arcs les chemins qui relient ces villes
entre elles ; ces chemins peuvent être des routes, des lignes de chemin de fer, des lignes
aériennes ou maritimes, etc.
La particularité des réseaux multimodaux et/ou intermodaux est la diversité des modes de
transport ; cela rend la modélisation du réseau plus complexe et le nombre de données à traiter
devient très important ; d’où la nécessité d’une modélisation cohérente des données de celui-
ci. La modélisation classique des réseaux de transport intermodaux consiste à considérer des
réseaux différents par mode de transport étudié et de mettre en place des points de transfert
entre ces réseaux. Crainic et Kim considèrent le transport intermodal de marchandises comme
étant une chaîne constituée de plusieurs modes de transport qui interagissent dans des
terminaux intermodaux afin d’assurer un service de transport de porte-à-porte ; dans ce cas, la
modélisation dans le réseau intermodal consiste à trouver la meilleure représentation possible
des modes de transport, des axes associés à ces modes et des infrastructures notamment les
installations et les terminaux intermodaux (Crainic et Kim, 2007). Parmi les méthodes de
modélisation de réseaux intermodaux existants, nous trouvons entre autres le modèle de
graphe multivalsé, les modèles utilisant des graphes de transfert et les modèles utilisant des
hypergraphes.
disponibles sur le réseau. Dans ce modèle, un temps de trajet ( ) est associé à chaque arc
des arcs, l’ensemble des fenêtres temporelles et l’ensemble des modes de transport
24
Chapitre 1. Généralités et état de l’art
de l’arc (!, ) avec le mode x pour aller vers l’arc ( , ) avec le mode y (Figure 6). Dans un tel
réseau, nous avons le choix entre plusieurs modes de transport à chaque nœud ; en d’autres
termes, à chaque nœud, pour accéder aux nœuds suivants, nous avons le choix entre continuer
avec le même mode transport ou le remplacer par un autre en effectuant des opérations de
transbordement (Ziliaskopoulos et Wardell, 2000).
k i’
( )
i
( )
Lozano (Lozano et Storchi, 2002) utilise le modèle d’hypergraphe présenté par Nguyen
hypergraphe multimodal (Figure 7). Un hypergraphe est une paire " = (#, $), où # est
(Nguyen et Pallottino, 1986) pour modéliser un réseau de transport intermodal appelé
l’ensemble des nœuds et E l’ensemble des hyper-arcs (h-arcs). L’hypergraphe multimodal est
défini par un triplet " = (#, $, ) où N est l’ensemble des nœuds, $ l’ensemble des h-arcs et
est l’ensemble des modes de transports associés aux h-arcs.
25
Chapitre 1. Généralités et état de l’art
Lozano utilise deux types d’arcs pour représenter les réseaux intermodaux : le premier arc
appelé « arc de transfert » est utilisé pour représenter les changements de modes dans le
réseau et le second appelé « arc de déplacement » représente un arc connectant deux nœuds
disponible sur le réseau, un seul mode de transport est associé à chaque arc ( , ) ∈ et les
par le même mode de transport (Figure 8). Si est l’ensemble des modes de transport
transferts de modes sont considérés comme des modes (Lozano et Storchi, 2001).
0 6
2 3
5
1
4
Arc de transfert
Voiture
Métro
Figure 8. Exemple de chemin intermodal avec un arc de transfert (Lozano et Storchi, 2001)
La majeure partie des études présentées dans la littérature sur la planification d’itinéraires
intermodaux portent sur la planification des itinéraires dans les réseaux de transport urbains et
notamment les transports en commun. Cette planification a pour objectif principal le choix
des moyens de transport adéquats et des chemins qui y sont associés en fonction d’un certain
nombre de critères de choix. À cet effet, Ahn par exemple étudie l’impact des décisions de
choix de chemins sur la consommation énergétique des véhicules et le coût des émissions
pour différents types de véhicules en utilisant des outils macroscopiques et microscopiques
d’estimations des émissions. Les résultats démontrent que le choix des autoroutes n’est pas la
meilleure des solutions du point de vue de la consommation énergétique et de l’impact
environnemental. Plus précisément, ces études révèlent que des améliorations significatives
peuvent être obtenues lorsque les automobilistes utilisent les routes à moyennes ou petites
vitesses plutôt que des voies rapides, même si cela augmente le temps de transport (Ahn et
Rakha, 2008).
26
Chapitre 1. Généralités et état de l’art
En effet, Hsua présente une analyse bi-critères appliquée à la gestion d’hubs multimodaux
dans le but de planifier les expéditions du transport maritime en optimisant simultanément le
coût de transport et le coût de stockage. Le modèle analytique proposé a permis de déterminer
un routage optimal ainsi que la taille de lots et les fréquences des expéditions en fonction des
coûts de stockage et de transport (Hsua et Hsieh, 2007).
Caramia propose une heuristique pour l’optimisation multiobjectif du fret intermodal longue
distance. Il optimise simultanément le temps de transport, le coût de transport et l’indice de
partage du moyen de transport (capacité du moyen de transport à générer des solutions
respectant une économie d’échelle). Cette étude est basée sur un cas réel d’étude en Italie, où
un opérateur logistique doit servir un certain nombre de demandes d'expédition de
marchandises de ses clients. Il s’impose donc la nécessité de définir des itinéraires avec le
mode de transport approprié et la composition moyenne des moyens de transport, pour mener
à bien les produits de leurs origines à leurs destinations données (Caramia et Guerriero, 2009).
L’algorithme de Martins (Martins, 1984), combiné à une heuristique de recherche locale a été
appliquée dans cette étude. L’algorithme privilégie trois types de chemins imposés par
l’opérateur logistique ; les chemins utilisant uniquement la route, les chemins ayant un
transbordement proche de l’origine et ceux ayant un transbordement proche de la destination.
Dans un premier temps, l’algorithme de Martins est appliqué pour trouver tous les chemins
non-dominés. Parmi les chemins ainsi trouvés, les chemins ne respectant pas les conditions
posées par l’opérateur logistique sont ensuite supprimés, les moyens de transport sont ensuite
affectés suivant deux procédures, l’une minimisant le coût de service du transport routier et
l’autre minimisant le coût et le temps de service des transports ferroviaires et maritimes.
Chang traite le problème de choix d’itinéraire intermodal sous forme d’un problème de flux
multi-produits multiobjectif multimodal (multiobjective multimodal multicommodity flow
problem (MMMFP)) en tenant compte de fenêtres temporelles et de coûts concaves. Ces coûts
sont définis pour chaque mode transport en tenant compte d’économies d’échelles dépendant
de la quantité de marchandises transportée ; ce qui donne une fonction coût de forme concave
c’est-à-dire que les coûts sont élevés pour de petites quantités de marchandises, moyens, voire
très bas, pour des quantités assez élevées et élevés encore pour de très grandes quantités de
marchandises. La méthode de résolution utilisée pour le problème est une heuristique basée
sur des techniques de relaxation et de décomposition ; le problème d’origine est subdivisé en
un ensemble de sous-problèmes, plus petits et plus faciles à résoudre. Les fonctions à
optimiser sont le temps de transport et le coût total des flux (Chang, 2008).
27
Chapitre 1. Généralités et état de l’art
Le transfert de matières premières et de biens d’un point à l'autre dans une chaîne logistique
se fait par divers modes de transport, à savoir terrestre, aérien ou maritime. Les niveaux et les
types de pollution dus au transport dépendent principalement de la combinaison de deux
facteurs : le type de mode de transport et de la distance parcourue. Les impacts du transport
sur la santé tels que les maladies respiratoires dues à la pollution de l’air, les intoxications sur
la faune et la flore dues aux marées noires, les risques de cancers dus aux hydrocarbures
aromatique polycyclique et les nitrates ne sont plus à démontrer. Les impacts du transport sur
l'environnement sont bien connus de nos jours ; ils comprennent le réchauffement climatique,
la détérioration de la couche d'ozone, la dispersion de substances organiques et inorganiques
toxiques notamment l'ozone troposphérique, la raréfaction du pétrole et d’autres ressources
naturelles, et la dégradation des paysages et des sols.
D’après un rapport de l’ADEME (ADEME, 2006) paru en mars 2006, la France est au
carrefour des principales routes européennes et supporte une grande partie du trafic intra-
européen. Entre 1990 et 2000, le trafic de marchandises intérieur a augmenté de 30%, alors
que le trafic de transit a crû de 70 %. En effet, l’Île-de-France, l'arc alpin et l'axe pyrénéen se
trouvent géographiquement à l’intersection des grands axes Nord-Sud et Est-Ouest de la
France. On y enregistre donc un trafic de transit très important à l’origine de fortes
concentrations de polluants atmosphériques (oxydes d’azotes particulièrement),
principalement du fait des poids lourds. Le transport routier assure à lui seul 80% des
échanges de marchandises régionaux et longues distances. Les distances parcourues ne
cessent d’augmenter, alors que le chargement des camions a plutôt diminué en poids, mais
augmenté en volume ; en conséquence, si les marchandises se sont globalement allégées, les «
tonnes.kilomètres » parcourues ne cessent de croître.
Dans son Livre blanc (Transport White Paper, 2006), la Commission Européenne évoque une
augmentation de 38% du marché de fret interne européen (tous modes confondus) dans les dix
prochaines années. Elle prédit une augmentation de 8% à 15% de la part de marché du fret
ferroviaire d’ici 2020. La Figure 9 présente l’augmentation prévisionnelle de l’utilisation de
chaque mode de transport de 2000 à 2020 ; suivant l’utilisation actuelle des ressources en
transport, la tendance est à l’augmentation exponentielle du taux d’utilisation. Cette
augmentation a pour conséquence l’augmentation de la consommation des ressources
naturelles et des émissions de polluants affectant à la fois l’environnement et la société, tant
au niveau des désagréments dus aux pollutions qu’au comportement.
28
Chapitre 1. Généralités et état de l’art
Figure 9. Évolution prévisionnelle du fret par mode de transport (Transport White Paper,
2006)
De plus, selon une étude menée par Piecyk, trois scénarios illustrent cette tendance pour le
fret routier. En effet, le premier scénario appelé Business-As-Usual (BAU) est un scénario
positif selon lequel on augmenterait l'efficacité énergétique du mode routier d’une part, et
d’autre part on réduirait de 10% les émissions de CO2 par rapport au niveau actuel ;
l'empreinte carbone du transport routier de marchandises serait donc de 17,4 millions de
tonnes de CO2 en 2020. Cela sera possible notamment par l'utilisation optimale des véhicules,
en optimisant le taux de charge des camions. Dans le deuxième scénario appelé scénario
optimiste, les émissions de CO2 du transport routier de marchandises seraient de 47% en
dessous du niveau actuel (10,3 millions de tonnes de CO2 en 2020), par exemple en déplaçant
des marchandises hors du transport routier vers des modes alternatifs et par une réduction de
la longueur moyenne du trajet de 15 km par rapport à la valeur actuelle. Enfin, dans un
scénario pessimiste, l'empreinte carbone du fret routier atteindra 30,0 millions de tonnes de
CO2 en 2020 (56% au-dessus du niveau actuel), si aucune action n'est mise en œuvre pour
limiter le phénomène (Piecyk et McKinnon, 2010). Des mesures efficaces doivent alors être
prise pour limiter voire supprimer tous ces impacts.
La pollution émanant des véhicules, tels que les camions, inclut les gaz polluants tels que le
monoxyde de carbone (CO), les oxydes d'azote (NOx), les particules polluantes et les
composés organiques volatils (COV). Certains hydrocarbures (y compris les COV) provenant
des émissions des moteurs sont cancérigènes. Les COV sont connus comme étant très
dangereux pour la santé humaine. Le NOx est un gaz toxique invisible qui peut former de
fines particules d'aérosols ou de sels pouvant contribuer aux pluies acides ou au smog. Les
carburants des moteurs sont souvent émis sous forme de particules polluantes. Ces particules
toxiques sont très souvent des substances chimiques cancérigènes causant d’énormes dégâts
dans les poumons. En outre, l'ozone et les particules sont responsables de maladies
respiratoires, de dommages environnementaux et de problèmes de visibilité, tels que le
brouillard (United States Environmental Protection Agency, 1999). De plus, environ 20% des
citoyens européens souffriraient de problèmes dus aux bruits des transports. Il apparaît que
même si nous avons une augmentation importante de l’utilisation des modes de transport, l’on
29
Chapitre 1. Généralités et état de l’art
peut obtenir une utilisation plus efficiente de ces modes sans augmenter les émissions de
polluants et la consommation des ressources naturelles.
Pour le transport aérien, les principaux impacts environnementaux directs sont les émissions
gazeuses et sonores des avions et, dans une moindre mesure, les rejets liquides, gazeux et
solides générés par les activités au sol. Au niveau local, l’impact majeur réside dans les
nuisances sonores (Air France, 2006-2007). La grande partie des émissions émanant du
transport aérien provient de la phase de décollage ou LTO-Landing and Taking-Off (roulage
et décollage). Des mesures sont prises par les compagnies aériennes et les aéroports pour
limiter ces conséquences notamment par la réduction du temps de roulage ainsi que par la
mise en place de méthodes permettant de réduire le nombre de moteurs en marche pendant la
phase LTO.
L'impact du transport sur l’environnement et la société peut également être évalué en termes
monétaires ; le coût de la santé, le coût des journées de travail perdues et le coût économique
des décès, etc. Au Royaume-Uni par exemple, les économistes de l'environnement ont estimé
le coût de la pollution atmosphérique due aux transports routiers à 19.7 milliards d'euros par
an (The Ashden Trust, 1994). Beaucoup d'autres chercheurs ont examiné les problèmes de
pollution dans les agglomérations (Flachsbart, 1999 ; Colvile et al., 2001). Le Tableau 1 ci-
dessous présente les coûts moyens des impacts pour plusieurs types de véhicules pour le mode
routier ainsi que les coûts engendrés par les autres modes de transport à la fois pour le
transport de marchandises et le transport de personnes.
Tableau 1. Coût moyen des impacts par mode de transport pour le transport de marchandises
et le transport de personnes en Europe INFRAS Zurich (Schreyer et al., 2005)
Les objectifs gouvernementaux sont de plus en plus axés sur une amélioration continue de la
qualité de vie et l’assurance d’un développement économique à travers une utilisation efficace
des ressources afin de promouvoir les potentiels d’innovation économiques et sociaux de
l’économie. Un autre impact du transport est la congestion du trafic et la superficie occupée
30
Chapitre 1. Généralités et état de l’art
par les systèmes de transport sur les surfaces habitables. La Figure 10 répertorie l’essentiel
des impacts économiques, sociétaux, sociaux et environnementaux des systèmes de transport.
Ces impacts sont ceux relevés pendant les phases d’utilisation du moyen de transport.
D’autres impacts tels que ceux intervenant lors de la maintenance des moyens de transport, du
dégivrage, les impacts lors des transbordements ou de la gestion des terminaux intermodaux
peuvent également être considérés. Des impacts sont également observés au niveau des
infrastructures de transport notamment sur la consommation de l’espace, la hausse de
l’urbanisation. La Figure 11 représente les émissions de CO2 par mode de transport entre 2000
et 2050 ; la tendance est à l’augmentation des émissions pour tous les modes de transport.
Figure 11. Courbes d’estimation des émissions de CO2 (Mt) dans le monde de 2000 à 2050
(OECD and the international transport forum, 2008)
31
Chapitre 1. Généralités et état de l’art
Plusieurs recherches ont été menées pour la réduction de ces impacts. Les solutions apportées
par ces recherches vont des techniques managériales aux méthodes d’optimisation issues de la
recherche opérationnelle. La majeure partie des études menées porte d’une part sur l’analyse
des impacts émanant des systèmes de transport, et d’autre part sur l’estimation des coûts
engendrés par les impacts environnementaux du transport (Piecyk et McKinnon, 2007 ;
Levinson et al., 1998 ; Forkenbrock, 1999). Des études sont également menées sur la mise en
place de politiques d’internalisation des coûts environnementaux du transport (Ricci et Black,
2005) ainsi que sur les méthodes et modèles de calcul des coûts engendrés par les impacts
(Janic, 2007).
Des méthodologies pour l'évaluation environnementale des politiques de transport, des plans
et des programmes de réductions des émissions ont été conçus tant au niveau des
gouvernements qu’au sein des entreprises. Ces politiques sont rendues possibles très souvent
grâce des logiciels de calcul des impacts et un ensemble de méthodes permettant d’estimer les
émissions des transports. Dans le secteur maritime par exemple, il a été démontré que la
réglementation MARPOL (MARPOL, 1973) sur la pollution par les navires a eu un effet
positif sur l'environnement marin. Cette règlementation a également permit l'échange de
bonnes pratiques entre les gestionnaires des ports sur la gestion environnementale, ainsi que
promotion de l'utilisation de données sur les sédiments pour améliorer le contrôle de la
pollution dans les opérations de dragage.
D’autres méthodes de réduction des impacts par l’introduction de nouvelles technologies, par
de nouveaux concepts de transport et par l’intégration des questions environnementales dans
la planification des systèmes de transport ont également été proposées. Ces concepts incluent
la mise en place de moteurs moins polluants, la mutualisation des moyens de transport,
l’utilisation de biocarburants et l’écoconduite entre autres. Un autre moyen pour réduire les
impacts est l’utilisation de moyens de transport non-motorisés comme la marche ou le vélo,
mais ceci n’est valable que pour les transports urbains. Pour le fret, la tendance est à
l’utilisation de modes moins polluants tels que le train ou le bateau ainsi qu’à l’optimisation
de la taille des lots transportés.
D'autres travaux ont porté sur les stratégies de réduction elles-mêmes, visant à partager la
connaissance des meilleures pratiques, des techniques managériales et d'évaluer leur
performance sur des cas réels. Les objectifs de ces travaux sont :
• L’identification des moyens pour améliorer la réduction des bruits (limitation des
horaires de livraison dans les secteurs urbains, véhicules à faibles nuisances sonores) ;
32
Chapitre 1. Généralités et état de l’art
• Le développement d'outils pour aider les autorités, les opérateurs et les décideurs à
évaluer et contrôler la situation environnementale dans les ports et les plateformes
logistiques ;
• La modélisation de la pollution ;
Une autre solution pour réduire les impacts est la réduction des distances parcourues qui en
elle-même est bénéfique pour l’environnement en ce sens où elle contribue à la réduction de
la consommation de carburant, et donc des polluants qui en résultent. À ce titre, de
nombreuses recherches s’intéressent aux problèmes de localisation d’unité de production ou
de centre de distribution dans les chaines logistiques vertes (Harris et al., 2011).
2.4 La congestion
Un autre volet de la réduction des impacts du transport concerne la réduction des congestions
sur les axes de circulation, notamment le trafic routier. Les chercheurs dans le monde des
transports ont longtemps cherché des moyens efficaces et satisfaisants pour décrire et analyser
la congestion du trafic ; ainsi, de nombreuses approches ont été développées pour modéliser et
réduire au mieux la congestion. La congestion dans les transports n’est bien sûr pas limitée au
seul cas de la route, mais concerne également les aéroports et les voies aériennes, les ports, les
chemins de fer et les usagers des réseaux de transport en commun comme le bus, le métro...
(Lindsey et Verhoef, 1999). L’étude de la congestion se fait sur plusieurs niveaux à savoir le
niveau microscopique, le niveau macroscopique et le niveau mésoscopique (Lindsey et
Verhoef, 1999). À cela, il faut également ajouter la gestion des files d’attente dues à la
congestion, qui est une forme d’analyse microscopique. La gestion des files d’attente
s’intéresse à la réduction du temps d’attente et à la diminution des files d’attente aux
différents points de congestions aux heures de pics ; des références peuvent être trouvées dans
(Yang et Meng, 1998 ;Otsubo et Rapoport, 2008 ; Newell.,1999).
2.5 Conclusion
Les impacts que peut avoir le transport sont multiples. Cependant, les méthodes d’aide au
déplacement intermodal au sein de la chaîne logistique verte ont très peu été étudiées dans la
littérature. Nous trouvons quelques tentatives de résolution dans (Rondinelli et Berry, 2000 ;
Qu et al., 2008). L’approche proposée par Rondinelli est une approche managériale intégrée
appelée « proactive environmental management systems » qui est un « Système Proactif pour
le Management Environnemental », ayant pour objectif de prévenir la pollution et de réduire
les sources de dégradation de l’environnement par le fret intermodal (Rondinelli et Berry,
2000). Qu propose une méthode d’aide à la décision multicritère hybride utilisant une
méthode AHP et une méthode à base de réseaux de neurones afin de proposer le choix de
33
Chapitre 1. Généralités et état de l’art
chemin intermodal dans un réseau de six nœuds ; cette approche prend en compte entre autres
les effets sociaux, la sécurité des moyens de transport et les effets de la congestion à travers
une évaluation qualitative (Qu et al., 2008). Cette dernière approche se révèle efficace pour
des problèmes de petite taille ayant un nombre de critères peu élevé.
Cependant, il y a très peu d’articles qui relient les modèles de planification d’itinéraire
intermodal et les problèmes de chaîne logistique verte énumérés précédemment. La Figure 12
présente un panorama des approches existantes pour la réduction des impacts du transport.
Optimisation du taux de
remplissage et réduction
du packaging
Introduction de Introduction de
techniques de véhicules éco-
management responsables
environnemental
Promotion de mode
Introduction des
de transport éco-
biocarburants
efficients
Mise en place de
collaboration entre
partenaires de la chaine
logistique verte
Les problèmes d’optimisation combinatoire multiobjectif (MOCO) font partie d’une famille
de méthodes dites d’optimisation multiobjectif. L’optimisation multiobjectif, aussi connue
sous le nom d’optimisation multicritère ou d’optimisation multi-attribut, est un processus qui
consiste à optimiser simultanément deux ou plusieurs objectifs, soumis à certaines
contraintes. La plupart des décisions prises dans la vie réelle sont basées sur plusieurs critères.
Les problèmes d’optimisation multiobjectifs sont donc dans divers domaines dont la
conception de produit/processus de fabrication, le domaine automobile, les finances, etc. La
solution obtenue représente un compromis entre deux ou plusieurs objectifs. Les objectifs
peuvent être très souvent contradictoires, par exemple les solutions offrant un temps de
transport optimal peuvent être celles qui émettent le plus de gaz à effet de serre, dans le cas où
l’objectif est d’optimiser simultanément le temps et les émissions de gaz à effet de serre.
Il existe plusieurs familles de méthodes d’aide à la décision multiobjectif à savoir les MCDM
(Multi Criteria Decision Making) ou méthodes de prise de décision multicritère, MCDA
34
Chapitre 1. Généralités et état de l’art
(Multi Criteria Decision Aid) ou méthode d’aide à la décision multicritères, MOO (Multi
Objective Optimization) ou méthodes d’optimisation multiobjectif.
forme '( ( ), ') (,), … , '+ (-). Ainsi, un problème d’optimisation mono-objectif peut être
défini comme suit :
Min '( )
∈.
Où ' est une fonction scalaire et . est un ensemble de contraintes définies comme suit :
. = / ∈ 0 1 : ℎ(= 0), 4( ) ≥ 06
∈.
∗
∈ . est dit Pareto-optimal pour un problème multiobjectif si tous les autres vecteurs ∈ .
difficilement applicable. La notion d’optimalité de Pareto est donc introduite. Un vecteur
ont soit des valeurs plus élevées pour au moins une des fonctions ' , avec = 1, . . . , 9 , soit la
même valeur pour tous les objectifs. Les solutions Pareto-optimales sont obtenues par des
tests de dominance. Ce test est défini comme suit pour deux vecteurs critères ( et ) :
alors ( est au moins aussi bon que ) sur tous les critères, et meilleur que lui sur au
moins un critère.
aperçu complet de l’état de l’art sur les MOCO et les méthodes de résolution existantes peut
être trouvé dans (Ehrgott et Gandibleux, 2000 ; Caramia et Dell’Olmo, 2008). Parmi les
méthodes présentées, nous pouvons citer entre autres :
F2
• •
D B
•
A F1
• •
C E
• Les techniques de scalarisation : Les objectifs sont combinés en une seule fonction
scalaire à optimiser. Cette approche est souvent appelée méthode des sommes
pondérées ou scalarisation. La fonction objectif ainsi obtenue est optimisée selon les
méthodes d’optimisation mono-objectif classiques. L’efficacité de cette méthode est
conditionnée par une définition adéquate des pondérations de chaque objectif. Les
insuffisances de cette méthode résident donc dans la définition des poids de chaque
objectif ainsi que dans la diversité des solutions obtenues.
donnée =. En d’autres termes, dans cette méthode il y a une fonction objectif plus
minimiser, le reste des objectifs est contraint à être inférieur ou égal à une valeur
importante que les autres, et un niveau maximal à respecter pour les autres fonctions tel
que :
Minimiser '( ( ), ∈ . et
'2 ( ) ≤ =2
> ⋮ B
'9 ( ) ≤ =9
Erghott propose des modifications de cette méthode en améliorant notamment les
difficultés de calculs générés par la méthode (Erghott et Ruzika, 2005).
• Goal Programming (programmation par but) : Cette méthode tente de trouver des
valeurs « but » spécifiques à chaque objectif. Des détails sur l’application de cette
méthode pour les problèmes multiobjectifs peuvent être trouvée dans (T’kindt et
Billaut, 2005).
36
Chapitre 1. Généralités et état de l’art
D’autres approches dites hybrides combinent ces méthodes les unes avec les autres, comblant
ainsi les insuffisances d’une des méthodes par les avantages d’une autre. Des applications de
l’optimisation multiobjectif telles que le problème de plus court chemin multiobjectif, le
problème de voyeur de commerce, des problèmes d’ordonnancement, des problèmes
localisation dans la chaîne logistique... peuvent être trouvées dans la littérature.
Lorsque plusieurs objectifs sont impliqués, de prime abord, les différents paramètres sont
ajustés afin de maximiser simultanément les profits (ou de minimiser les coûts) ou
d’optimiser le taux de service par exemple. Cette section présente quelques utilisations des
méthodes d’optimisation multiobjectif pour résoudre des problèmes au sein des chaînes
logistiques vertes.
Un système d’aide à la décision est proposé par Ülengin pour analyser les impacts des
politiques de transport sur le système social, l’environnement, et la consommation d’énergie ;
il a utilisé la méthode TOPSIS (Technique for Order Preference by Similarity to Ideal
Solution) pour analyser les interactions entre transport et environnement en vue d’aider les
décideurs à trouver des politiques appropriées pour atténuer et réduire les impacts
environnementaux liés au transport (Ülengin et al., 2009).
37
Chapitre 1. Généralités et état de l’art
Dans le même ordre d’idée, Kainumaa a proposé un système multi-attribut MAUT (Multi-
Attribute Utility Theory) pour l'évaluation d’une chaîne logistique en boucle fermée incluant
la réutilisation, le recyclage tout au long du cycle de vie des produits et des services. Ils
intègrent le « rendement de l'actif investi » ou « rentabilité économique » (return on asset-
ROA), la satisfaction du client, et l’analyse de cycle de vie (ACV) de la chaîne logistique
dans une fonction d'utilité multi-attribut (Kainumaa et Tawara, 2006).
Sawadogo et Anciaux mettent en œuvre une approche basée sur la méthode ELECTRE pour
trouver un chemin dans un réseau intermodal afin d'optimiser les critères économiques,
sociétaux et environnementaux ; le but étant de trouver les chemins ayant le meilleur
compromis entre ces critères ; sept critères sont pris en compte et les chemins les mieux
classés par la méthode ELECTRE sont présentés (Sawadogo et Anciaux, 2011). En se basant
sur le même modèle, une approche de résolution utilisant la méthode AHP (Analytic
Hierarchy Process a été mise en œuvre dans (Sawadogo et Anciaux, 2010), cette approche
hiérarchique d’analyse multicritère a permis de classer les chemins du plus intéressant au
moins intéressant suivant les critères socio-environnementaux et économiques.
L’avantage de méthodes d’aide à la décision multicritère telles que AHP, ELECTRE, MAUT,
TOPSIS est qu’elles permettent d’optimiser facilement les problèmes et d’obtenir de bons
résultats dans un temps raisonnable. Cependant, plus la complexité du problème augmente,
plus ces méthodes deviennent inefficaces ; de plus, elles nécessitent que l’on définisse toutes
les solutions possibles de l’espace de recherche, ce qui est impossible pour des problèmes de
grande taille où l’on a des milliers de solutions possibles.
Le choix d’un chemin pour acheminer des marchandises peut se faire en tenant compte du
temps de transport, du coût, des stationnements, etc. D’une façon générale, les outils utilisés
38
Chapitre 1. Généralités et état de l’art
Le problème de plus court chemin est l’un des problèmes d’optimisation de réseau les plus
étudiés depuis les années cinquante (Bellman, 1958 ; Dijkstra, 1959 ; Ford et Fulkerson,
1962). Toutes ces études sont basées sur la recherche d’un chemin dans un graphe en se
basant sur un seul objectif. En effet, le problème de plus court chemin traditionnel a pour
objectif la minimisation du temps et/ou du coût et de nombreux algorithmes de résolution sur
ce problème existent dans la littérature.
Le problème de plus court chemin multiobjectif est donc une extension du problème de plus
court chemin traditionnel et a pour objectif de trouver un ensemble de chemins dits efficaces
en prenant en considération deux ou plusieurs objectifs qui sont le plus souvent
contradictoires. La question ici n’est pas de trouver une solution optimale pour chaque
fonction objectif, mais de trouver une solution qui optimise simultanément tous les objectifs
(Pangilinan et al., 2007). Dans la plus part des cas, il n’existe pas de solution unique, mais un
ensemble de solutions efficaces ou non-dominées est déterminé ; cet ensemble de solutions est
appelé ensemble de solutions « Pareto optimal ».
Le problème de plus court chemin multiobjectif est connu comme étant NP-difficile et les
algorithmes rencontrés dans la littérature font face à des difficultés notamment pour la gestion
du grand nombre de données sur les chemins non-dominés ; il en résulte un temps de calcul
considérable. Il est à noter que le nombre de chemins non-dominés augmente de façon
exponentielle avec le nombre de nœuds du graphe (Hansen, 1979).
39
Chapitre 1. Généralités et état de l’art
Par exemple D ( (GH ) est le vecteur de performance du chemin GH par rapport au critère 1. Où
D O (GH ) = ∑(W,X)∈YZ[ DWX
O
est la somme des coûts sur chaque arc du chemin (GH ) par rapport à
chaque critère U ; avec U = 1 … 9 critères.
Soit :
1 si ( , ) appartient à un chemin B
=\
0 sinon
Ainsi, le problème de plus court chemin multiobjectif d’un point origine C à un point
destination , est définit comme suit :
min ' O ( ) = e DO ∀U = 1 … 9
( , )∈f
1 = C ; =0
s/c.
≥ 0, ∀ ( , ) ∈ (2)
nécessaire pour obtenir les arcs construisant un chemin de C à . La contrainte (2) est une
La contrainte (1) est la contrainte d’équilibre de conception à chaque nœud du réseau
contrainte de non-négativité.
qui procure simultanément la solution optimale pour l'ensemble des objectifs ' O ( ). Par
Les objectifs étant conflictuels, il est généralement impossible de trouver une solution unique
( )
Étant donné un chemin GHl (
∈ .H,l , le vecteur D(GHl
n’existe pas un autre vecteur D(GHl ) tel que D O (GHl
) )
< D O (GHl
( ),
U = 1, … , 9, sinon D(GHl
est « faiblement » non-dominé ssi ,il
) )
L’ensemble des solutions efficace ou Pareto-optimale est formé par l’ensemble des chemins
non-dominés. Divers algorithmes et méthodes ont été implémentés et étudiés pour résoudre ce
type de problème.
40
Chapitre 1. Généralités et état de l’art
Plusieurs chercheurs tels que (Climaco et Martins, 1981, 1982 ; Martins, 1984 ; Hansen,
1980 ; Martins et al., 1999) se sont intéressés à la résolution du problème de plus court
chemin multiobjectif. Les algorithmes et les méthodes qu’ils utilisent sont entre autres la
programmation dynamique, les algorithmes à correction d’étiquettes, les algorithmes à
sélection d’étiquettes, les méthodes interactives, et des algorithmes d’approximation
(Gandibleux et al., 2006). Les principales méthodes proposées dans la littérature pour
résoudre ce problème peuvent être classées en trois catégories : les méthodes génératrices, les
méthodes basées sur une fonction d’utilité et les méthodes interactives. Dans la suite, une
revue sur ces différentes approches et quelques résultats issus de la littérature sont présentés.
étiquette définitive [ ], on dira qu’elle est fixée ; une étiquette représente la valeur du
contiennent pas de circuits négatifs. À chaque itération, un sommet reçoit une
« Done » indique les sommets fixés. Hansen en 1980 (Hansen, 1980) propose le
premier algorithme à fixation d’étiquettes pour résoudre un problème de plus court
chemin bi-critère avec des critères positifs.
L’un des précurseurs des algorithmes à fixation d’étiquettes pour les problèmes de
plus court chemin multiobjectif est Ernesto Queiros Vieira Martins. En effet, Martins
définit un algorithme à fixation d’étiquettes attribuant plusieurs étiquettes à chaque
nœud. L’algorithme proposé dans (Martins, 1984) est une généralisation de
l’algorithme de Hansen et des conditions générales ont été établies de sorte à s’assurer
que l’étiquette temporaire la plus petite selon l’ordre lexicographique corresponde bien
à un chemin non-dominé. Cet algorithme est basé sur le principe d’optimalité de
existe deux types d’étiquettes: une étiquette temporaire et une étiquette permanente
(Caramia et Dell’Olmo, 2008). L’algorithme sélectionne l’étiquette la plus petite selon
41
Chapitre 1. Généralités et état de l’art
des successeurs) de pout tout ( , ) ∈ , puis il supprime toutes les étiquettes qui
toutes les étiquettes temporaires de ses successeurs directs (mise à jour des étiquettes
Une récente étude menée par Gandibleux présente une description concise du
problème de plus court chemin multiobjectif. Leur étude rappelle l’algorithme à
fixation d’étiquettes de Martins et tente de l’améliorer. Leur nouvel algorithme est une
extension de l’algorithme de Martins par l’introduction d’une procédure pour résoudre
les problèmes de plus court chemin multiobjectif avec plusieurs fonctions linéaires et
une fonction de type max-min. Leur algorithme est testé sur une variété d’exemples et
les résultats montrent que la densité et la taille du réseau augmentent le nombre de
solutions efficaces (Gandibleux et al, 2006).
D’autres algorithmes du même type pour les problèmes de plus court chemin
multiobjectif peuvent être trouvés dans (Skriver et al.,2000 ;Guerriero et al.,2001 ;
Ziliaskopoulos et Wardell, 2000).
42
Chapitre 1. Généralités et état de l’art
Ce type d’approches ne permet pas une analyse complète des compromis entre les critères.
Elle ne garantit pas que tous les chemins non-dominés seront trouvés.
Dans ces méthodes, les choix et préférences du décideur sont pris en compte progressivement
dans le calcul des solutions et dans le choix final des solutions. En effet, dans le cas de
l’optimisation multiobjectif, il n’est pas efficace de présenter l’ensemble des solutions non-
dominées au décideur, car les solutions non-dominées trouvées par les algorithmes sont
souvent multiples ; les procédures interactives ont pour but de remédier à ces lacunes
(Coutinho-Rodrigues et al., 1999).
À cet effet, Current propose une méthode permettant d’assister le décideur dans le choix des
solutions non-dominées trouvées ; cette méthode a pour objectif d’identifier un sous-ensemble
de solutions non-dominées (Current et al., 1990).
Gabrel propose une approche énumérative et interactive pour trouver des chemins non-
dominés dans un graphe ; la première phase de cette approche consiste à générer l’ensemble
des solutions non-dominées en utilisant un algorithme à fixation d’étiquette. La seconde phase
permet au décideur de choisir les critères qu’il privilégie en contraignant certains critères (par
la réduction des valeurs de certains critères), cela a pour but d’agir sur la structure des
solutions obtenues (Gabrel et Vanderpooten, 2002).
43
Chapitre 1. Généralités et état de l’art
Dans cette section, nous présentons les métaheuristiques utilisées dans la littérature pour
résoudre le problème de plus court chemin multiobjectif. Les métaheuristiques sont
représentées essentiellement par les méthodes de voisinage comme le recuit simulé et la
recherche tabou, et les algorithmes évolutionnaires comme les algorithmes génétiques et les
stratégies d'évolution. Les algorithmes évolutionnaires sont des heuristiques de recherche
basées sur les idées évolutionnaires sur la sélection naturelle des espèces. À ce titre, ils
représentent une exploitation intelligente d’une recherche aléatoire utilisée pour résoudre les
problèmes d’optimisation. Les algorithmes évolutionnaires ont été longtemps utilisés pour
résoudre des problèmes mono-objectifs, mais très peu de chercheurs les ont appliqués au
problème de plus court chemin multiobjectif (Pangilinan et al., 2007). Ils possèdent plusieurs
caractéristiques qui leur permettent d’être aptes à résoudre les problèmes multiobjectifs.
De ce fait, diverses approches évolutionnistes ont été proposées depuis 1985 capables de
résoudre les problèmes d’optimisation multiobjectif en un temps d’exécution raisonnable. Les
principaux algorithmes évolutionnaires utilisés pour le problème de plus court chemin
multiobjectif sont les algorithmes génétiques. De plus, des algorithmes à base de populations
tels que les algorithmes de colonies de fourmis ont également été utilisés pour résoudre ce
type de problème.
Bien que plusieurs approches aient été proposées pour résoudre les problèmes de plus court
chemin multiobjectif, très peu se sont porté sur l’application des algorithmes évolutionnaires
ou les métaheuristiques. La plupart des méthodes les plus récentes se sont concentrées surtout
sur l’analyse des performances des différents algorithmes existants en termes de vitesse
d’exécution, de complexité d’exécution ; la diversité et l’optimalité des solutions non-
dominées sont presque toujours omises.
Une présentation détaillée des algorithmes génétiques peut être trouvée dans (Mitchell, 1999),
elle résume également les approches actuelles en matière d’optimisation multiobjectif par les
algorithmes évolutionnaires et soulignent l’importance des nouvelles approches dans
l’exploitation des algorithmes évolutionnaires pour des problèmes multiobjectifs. Un nombre
important d’algorithmes génétiques pour les problèmes multiobjectif existent, mais
l’algorithme SPEA-II (Strength Pareto Evolutionnary Algorithm) est considéré comme étant
l’un des meilleurs algorithmes évolutionnaires multiobjectif élitistes.
Pangilinan propose une résolution, du problème de plus court chemin multiobjectif, basée sur
les algorithmes génétiques et analyse les résultats obtenus en termes de diversité des
solutions, de complexité de calcul et d’optimalité des solutions. L’algorithme SPEA-II est
appliqué à un réseau généré aléatoirement avec neuf configurations possibles. Les résultats de
cette étude montrent que le nombre de chemins efficaces augmente quand le nombre de
générations augmente. Les solutions obtenues tendent vers le font de Pareto et donnent un bon
compromis de solutions non-dominées à chaque génération. Considérant la complexité de
44
Chapitre 1. Généralités et état de l’art
calcul, ils démontrent que l’algorithme est exécuté en un temps polynomial en rapport avec le
nombre de nœuds et d’arcs du réseau (Pangilinan et al., 2007).
Si les algorithmes de colonies de fourmis sont de plus en plus utilisés pour la résolution de
problèmes multiobjectifs, très peu d’études sur leur application au problème de plus court
chemin multiobjectif existent. Dans l’article présenté par Cardoso, un algorithme de colonies
de fourmis est utilisé pour résoudre un problème de plus court chemin multiobjectif. Ici, le
processus d’optimisation utilise une seule colonie avec des traces de phéromones multi-
niveaux et une heuristique qui favorise l’introduction d’une formule d’heuristique aléatoire
plus court chemin de la source C à la destination . Pour cela, chaque fourmi est placée sur le
pour construire les chemins optimisés. Toutes les fourmis artificielles essaient de trouver le
nœud source C et construit son chemin en ordonnant les nœuds et en considérant la proximité
avec le nœud ainsi que les traces de phéromones entre le nœud courant et ses successeurs.
La première phase de cet algorithme consiste à construire les chemins optimaux en fonction
de « probabilité de transition » de l’ACO (Ant Colony Optimization) ; la seconde phase
concerne la mise à jour des traces de phéromones dans le réseau en fonction de l’intensité des
traces de phéromones laissées par les fourmis sur les chemins du graphe (Cardoso et al.,
2003).
Les études utilisant les algorithmes évolutionnaires ont montré l’efficacité de ces méthodes en
termes de temps d’exécution. Les algorithmes évolutionnaires constituent donc une alternative
quand les autres méthodes rencontrent des problèmes de traçabilité ou de rapidité d’exécution.
Les études les plus récentes sur la résolution du problème de plus court chemin multiobjectif
se focalisent plus sur la comparaison des vitesses d’exécution de différents algorithmes de
plus court chemin multiobjectif existant, délaissant par exemple l’analyse de la complexité
45
Chapitre 1. Généralités et état de l’art
des algorithmes ainsi que la diversité et l’optimalité des solutions non-dominées. De plus, une
des limites de ces méthodes est qu’elles nécessitent toutes de connaître auparavant l’ensemble
du réseau à étudier et tous les chemins possibles à emprunter. Aussi, les études présentées
dans la littérature se limitent le plus souvent l’étude deux critères et peu d’études existent sur
les problèmes de plus court chemin multiobjectif pour le transport intermodal. Plusieurs
méthodes sont basées sur des heuristiques, des métaheuristiques et d’autres méthodes conçues
pour offrir des solutions réalisables en un temps de calcul raisonnable sans pour autant
garantir une optimalité.
En plus de ces méthodes, il faut ajouter que de plus en plus la tendance est à l’utilisation des
métaheuristiques et des algorithmes évolutionnaires pour résoudre ce problème. Des
approches basées sur la programmation dynamique ont aussi été proposées dans Henig
(Henig, 1986) et Kostreva (Kostreva et Wiecek, 1993).
Les algorithmes de colonies de fourmis (ACO : Ant Clony Optimization) sont des algorithmes
inspirés du comportement des fourmis et qui forment une famille de métaheuristiques
d'optimisation. Parmi les algorithmes évolutionnaires, l’un des plus récent est l’optimisation
par colonies de fourmis, introduit par Marco Dorigo (Dorigo et al., 1991), pour la recherche
de chemins optimaux dans un graphe (Dorigo et Gambardella, 1996). Le premier algorithme
s'inspire du comportement des fourmis recherchant un chemin entre leur colonie et une source
de nourriture (Figure 14). L'idée originale s'est depuis diversifiée pour résoudre une classe
plus large de problèmes et plusieurs algorithmes ont vu le jour, s'inspirant de divers aspects du
comportement des fourmis. Les ACO sont des approches récemment proposées pour résoudre
des problèmes d’optimisation avec une combinatoire énorme et complexe. La source
d’inspiration des ACO est la trace des phéromones et le comportement des fourmis réelles qui
utilisent les phéromones comme moyen de communication. Par analogie à la biologie, les
ACO sont basés sur la communication indirecte d’une colonie de simples agents appelés
fourmis artificielles en utilisant des traces de phéromones artificielles. Les fourmis
artificielles dans un ACO mettent en œuvre une heuristique de construction aléatoire qui
construit des décisions probabilistes en fonction des traces de phéromones artificielles et les
données d’entrées du problème pour le résoudre. La Figure 14 représente la faculté d’une
colonie de fourmis à retrouver le plus court chemin entre leur nid et une source de nourriture.
Des détails sur le principe de fonctionnement et les applications des ACO peuvent être
trouvés dans (Dorigo et Blum, 2005 ; Dréo et al., 2003 ; Dorigo et Krzysztof, 2006).
46
Chapitre 1. Généralités et état de l’art
Figure 14. Choix du plus court chemin par une colonie de fourmis
La première étape de l’application d’un ACO est la définition d’un modèle adéquat : le
modèle de phéromones.. En général,
général tout algorithme de colonies de fourmis doit contenir les
éléments suivants : traces de phéromones,
phéromones information heuristique (visibilité),
(visibilité) règle de mise à
jour des traces de phéromones,
phéromones construction de solutions, probabilité de sélection et condition
d’arrêt.
Cette information indique l’attrait de tout arc ( , et est calculée en utilisant une approche
heuristique. Il existe diverses méthodes pour évaluer l'attrait de chaque arc. L'information
heuristique est calculée pour tous les déplacements des fourmis; il peut réduire
considérablement l'efficacité de l'algorithme
l'algo s’il est mal défini.. Elle peut être définie « à priori
» c’est-à-dire
dire au début et demeure inchangée durant toute l’exécution
l’exécution de l’algorithme, ou « à
posteriori » c’est-à-dire
dire qu’elle est dynamique et dépend de l’état actuel de la fourmi. Dans le
cas de l’optimisation mono-objectif,
bjectif, elle est souvent définie comme étant l’inverse du critère
1
à optimiser. Pour l’optimisation de la distance q par exemple, la visibilité t u v.
q
Les fourmis ont la particularité d'employer pour communiquer des substances volatiles
appelées phéromones. Elles sont attirées par ces substances, qu'elles perçoivent grâce à des
récepteurs situés dans leurs antennes. Dans le cas des fourmis artificielles, les traces de
phéromones sont représentées
présentées en fonction de la valeur de la fonction objectif pour l’arc
considéré. La définition de la quantité de phéromone est spécifique à chaque problème étudié
et dépend de la variante d’ACO utilisée. Pour l’algorithme de base « ant system » utilisé pour
le problème du voyageur de commerce, la quantité de phéromones ∆ déposée par une
fourmi est donnée par :
o
∆ = >>p si la fourmi k est passée par l'arc i,j B
0 sinon
Où o est une constante et p la longueur du chemin parcouru par la fourmi k ou w valeur de
la solution obtenue par la fourmi k (la meilleure solution).
47
Chapitre 1. Généralités et état de l’art
Chaque fourmi ! est placée sur un nœud source et recherche un chemin en sélectionnant les
nœuds à ajouter à sa mémoire Lxyz . À chaque fois qu’une fourmi se trouve sur un nœud i,
elle choisit le nœud suivant selon une règle probabiliste donnée dans le cas du « Ant
System » par :
}
.t ~
si j∈ Lxyz B
{ = |∑•∉•‚ƒ„… O } . t O ~
0 sinon
†
Algorithme général
1. Initialisation des traces de phéromones
2. Tant que le critère d’arrêt n’est pas atteint, faire
Pour toutes les fourmis, faire
• Construire une nouvelle solution en utilisant les traces
de phéromones et la visibilité (règles de transition)
• Évaluer les solutions construites
Fin pour
3. Mise à jour des traces de phéromones
4. Fin tant que
Une fois que les solutions ont été évaluées, elles peuvent influencer la matrice de phéromones
à travers un processus de mise à jour des traces de phéromones. La mise à jour des traces de
phéromones est effectuée à la fois localement et globalement. Le but de la mise à jour des
phéromones est d’augmenter les valeurs de phéromones associées aux solutions « bonnes » ou
prometteuses et de diminuer la valeur de phéromones associées aux mauvaises solutions.
Cette mise à jour est donc opérée par :
← (1 − ) + e ∆
‹(
48
Chapitre 1. Généralités et état de l’art
La quantité de phéromones présente sur un élément donné représente les expériences passées
de la colonie sur cet élément. Dans le cas de problèmes mono-objectifs, cette expérience est
définie en fonction de l’objectif considéré. Cependant, lorsque nous avons plusieurs objectifs,
nous pouvons considérer deux stratégies :
49
Chapitre 1. Généralités et état de l’art
Pour mettre à jour les traces de phéromones, on doit décider parmi les solutions construites
celles qui portent le plus de phéromones.
• La mise à jour individuelle : dans ce cas, une des matrices de phéromones est
sélectionnée pour la mise à jour. (Doerner et al., 2003 ; Iredi et al., 2001 ; Cardoso et
al., 2003).
• La mise à jour globale : dans ce cas, plusieurs matrices de phéromones sont mises à
jour. (Doener et al., 2004 ; López-Ibáñez et al., 2004)
4.2.3 La visibilité
La visibilité intervient pour beaucoup dans l’efficacité de l’algorithme, il est donc nécessaire
d’en définir correctement les paramètres. Dans le cas de l’optimisation mono-objectif, la
visibilité est définie comme l’inverse du critère à optimiser. Pour l’optimisation multiobjectif,
deux stratégies peuvent être considérées :
• Une première stratégie consiste à agréger les différents objectifs en une seule
information heuristique (Doerner et al., 2004 ; Bauer et al., 1999 ; Gravel et al., 2002) ;
les méthodes d’agrégation utilisées diffèrent d’une variante à l’autre. Doener par
exemple propose une matrice définie comme étant l’inverse de la somme des critères
pris en compte (Doerner et al., 2004).
• Une seconde stratégie est de considérer chaque objectif séparément ; dans ce cas, une
matrice de visibilité est associée à chaque objectif (Baran et al., 2003 ; Doener et al.,
2003 ; Gambardella et al., 1999 ; Iredi et al., 2001 ; Mariano et Morales, 1999).
La clé de la construction des solutions dans le cas multiobjectif se trouve dans la combinaison
de la visibilité et des valeurs des phéromones. Ces combinaisons sont de plusieurs sortes :
50
Chapitre 1. Généralités et état de l’art
L’évaluation et le classement des solutions ont été abordés de diverses manières dont les deux
principales sont les méthodes d’évaluations basées sur la construction de fronts de Pareto et
les méthodes non-Pareto.
• Pareto : Les solutions sont évaluées pour tous les objectifs et se voient attribués un
« score » qui reflète la façon dont la solution satisfait tous les objectifs dans le sens de
Pareto en se référant classement selon la dominance (Guntsch et Middendorf, 2003 ;
Iredi et al., 2001).
Parmi les études utilisant ces approches nous pouvons citer Gagné qui utilise les algorithmes
de colonies de fourmis pour un problème d’optimisation tri-objectif. Le contexte industriel
étudié correspond à l'ordonnancement d'un ensemble de commandes sur une machine unique.
Elle est basée sur la construction d’une heuristique dans laquelle une fourmi choisit la
prochaine commande à ordonnancer suite à la commande précédente en fonction d’un
premier facteur appelé « intensité de la trace ». L’intensité de la trace procure
l’information sur l’importance du trafic qui a été emprunté par la suite de commande (i,j)
précédente, et plus cette trace est importante, plus la probabilité de l’emprunter de nouveau
est grande. Au début de l’algorithme, l’intensité de la trace se voit accordée une valeur
faible et positive Œ . Le choix de la prochaine commande pour une fourmi est également
fonction d’un deuxième facteur que l’on appelle la visibilité t . La résolution de ce problème
est effectuée en trois étapes ; la première concerne la recherche du point idéal en optimisant
séparément les trois objectifs, la deuxième étape consiste à rechercher les solutions de
compromis par l’algorithme de colonies de fourmis pour enfin présenter les solutions
efficaces en tenant compte des choix du décideur (Gagné et al, 2004).
Une autre application des ACO est présentée par Baran pour la résolution d’un problème de
tournées de véhicules avec fenêtres temporelles. Dans cette étude, on utilise deux colonies de
fourmis différentes pour minimiser deux fonctions objectifs. Les deux colonies utilisent des
traces de phéromones indépendantes et collaborent en partageant « la meilleure solution
globale », qui sera utilisée pour la mise à jour des phéromones (Barán et Schaerer, 2003).
Guntsch utilise d’une approche « Population-based Ant Colony Optimization (PACO) » dans
laquelle les critères d’optimisation sont pondérés par ordre d’importance. La population de
solutions est choisie parmi les solutions non-dominées. Le but est de trouver un ensemble de
solutions différentes couvrant le front de Pareto. L’avantage de l’algorithme proposé est qu’il
51
Chapitre 1. Généralités et état de l’art
peut être appliqué à un problème avec plus de deux critères et ne biaise pas des solutions qui
sont les meilleures pour un critère. Cette approche est appliquée à un problème
d’ordonnancement avec minimisation des retards et des coûts de changement de gamme de
fabrication. L’algorithme emploie une matrice de phéromones pour chaque type de critère.
Les phéromones sont localisées dans une matrice (job x job) et une pondération est appliquée
pour définir l’importance relative de chaque critère dans la décision des fourmis (Guntsch et
Middendorf, 2003).
Mariano propose une approche multi-colonies où pour chaque objectif, il existe une colonie
de fourmis. Il étudie un problème où chaque objectif est influencé uniquement par une partie
de solutions ; ainsi, une fourmi de la colonie i reçoit une solution (partielle) venant d’une
fourmi de la colonie i-1 et ensuite tente d’améliorer cette solution ou de l’étendre en tenant
compte du critère i. Une solution finale qui est passée à travers toutes les colonies est
autorisée à mettre à jour les traces de phéromones (Mariano et Morales, 1999).
Gambardella et Donati ont mis en place un algorithme pour résoudre un problème de VRP
(Vehicule Routing Problem) bi-critère où ils ont également utilisé une colonie de fourmis
pour chaque critère. (Critère 1 : le nombre de véhicules considéré plus important que le critère
2 : temps total de trajet par tour). Les deux colonies donnent une meilleure solution globale
commune qui sera utilisée pour la mise à jour des phéromones dans ces colonies. La colonie 1
tente de trouver une solution avec un véhicule de moins que la meilleure solution globale,
pendant que la colonie 2 essaie d’améliorer la meilleure solution globale par rapport au critère
2 sous la restriction que la solution n’est pas pire que la meilleure solution globale en
respectant le critère 1. Chaque fois que la colonie 1 trouve une nouvelle meilleure solution
globale, les deux colonies commencent à nouveau une nouvelle itération avec la meilleure
solution trouvée (Gambardella et al., 1999 ; Donati et al., 2008).
Gagné a testé une approche multicritère pour résoudre des problèmes de retard d’une seule
machine avec des coûts de changement de gamme de production et deux autres critères. Dans
son approche, le coût de basculement est considéré comme étant plus important. Des valeurs
heuristiques pour les décisions des fourmis ont été utilisées afin de prendre en compte tous les
critères. Cependant, la quantité de phéromones qu’une fourmi ajoute à la matrice de
phéromones dépend uniquement du coût de changement de gamme de production dans la
solution (Gagné et al., 2001). Une approche similaire est utilisée par Gravel pour résoudre un
problème d’ordonnancement industriel (Gravel et al, 2002).
Un algorithme est proposé par Doener pour résoudre un problème de transport où l’objectif
est de minimiser le coût total en cherchant des solutions qui minimisent deux autres critères
différents. L’approche générale est d’utiliser deux colonies de fourmis où chaque colonie se
concentre sur un critère différent en utilisant différentes méthodes heuristiques (Doener et al
20011, 20012). Dans la première approche (Doener et al., 20011), un critère est considéré
comme étant le critère principal. À chaque itération k, la population principale qui minimise le
critère principal met à jour ses traces de phéromones selon les bonnes solutions obtenues par
les populations dites « esclaves », qui minimisent le critère secondaire. Cependant, aucune
information ne circule de l’esclave vers la colonie principale. Dans la seconde approche
52
Chapitre 1. Généralités et état de l’art
(Doener et al., 20012), tous les critères sont considérés comme ayant une égale importance. La
taille des deux populations a été adaptée de sorte que la colonie ayant trouvé la meilleure
solution pour le coût devienne plus « grande ». L’échange d’informations entre les colonies
est rendu possible par des « fourmis-espionnes » dont les décisions sont fondées à partir des
matrices de phéromones dans les deux colonies.
Jusqu’ici, les seuls algorithmes ACO qui sont capables de couvrir un front de Pareto d’un
problème d’optimisation multiobjectif ont été proposés par Doerner (Doerner et al., 2004) et
Iredi (Iredi et al., 2001).
Doerner étudie un problème d’optimisation de portefeuille avec plus de deux critères. Pour
chaque critère, une matrice de phéromones est utilisée. Au lieu d’une colonie de fourmis pour
chaque critère, chaque fourmi associe des poids aux informations sur les phéromones pour
tous les critères selon un vecteur de poids aléatoire pendant la construction de la solution. Les
phéromones sont mises à jour par les fourmis ayant trouvé la meilleure solution ou la
« seconde » meilleure solution pour un critère. Le problème avec cette approche est que les
fourmis du front non-dominé faisant partie des meilleures solutions obtenues pour un objectif
ne mettent pas à jour les traces de phéromones (Doerner et al., 2004).
Iredi étudie une approche pour résoudre un problème d’optimisation bi-critère avec des
colonies multiples. Les colonies sont spécialisées dans la recherche de « bonnes » solutions
sur les différentes parties du front non-dominé. La coopération entre les colonies est établie en
permettant uniquement aux fourmis ayant des solutions dans le front des solutions non-
dominées de mettre à jour les traces de phéromones. Dans cette approche, deux méthodes ont
été proposées pour la mise à jour des phéromones. Dans la première méthode, une fourmi
effectue des mises à jour uniquement dans sa colonie. Dans la seconde méthode, la séquence
de solutions le long de la frontière de Pareto divisé en p parties de dimensions égales. Les
i ; ∈ 71, {8. Cette méthode de mise à jour est appelée « mise à jour par région » dans le front
fourmis ayant trouvé des solutions dans la ième partie effectue des mises à jour dans la colonie
non-dominé. Il a été montré que la coopération entre les colonies permet les bonnes solutions
tout au long du front de Pareto. Des colonies hétérogènes sont utilisées lorsque les fourmis ont
des préférences différentes entre les critères lors de la construction des solutions (Iredi et al.,
2001).
quatre variantes de l’algorithme ont été présentées. Dans la première variante, • matrices de
nombre de colonies de fourmis et le nombre de traces de phéromones. Dans cette approche,
Dans la dernière variante, une colonie est utilisée avec • matrices de phéromones et une
troisième variante, une seule colonie de fourmis est utilisée avec une matrice de phéromones.
matrice de visibilité définit comme étant la somme des visibilités associées à chaque objectif ;
53
Chapitre 1. Généralités et état de l’art
à chaque itération, les fourmis choisissent aléatoirement l’objectif à optimiser (Alaya et al.,
2007).
Conclusion
• Par rapport au deuxième point, les études sur la modélisation des critères
environnementaux se concentrent essentiellement sur la réduction de l’empreinte
carbone et sur l’évaluation des coûts engendrés par les impacts d’une part, et d’autre
part sur la réduction des impacts émanant du mode routier.
• Enfin, le problème de plus court chemin multiobjectif a été largement étudié dans la
littérature ; un très grand nombre de méthodes de résolution de ce problème existent en
recherche opérationnelle et en intelligence artificielle. La majeure partie de ces
méthodes (algorithmes génétiques, algorithme utilisant des étiquettes) nécessite que
l’on calcule toutes les étiquettes de tous les chemins ou que l’on liste tous les chemins
pour la modélisation chromosomique pour les algorithmes génétiques par exemple. De
plus, la majeure partie des algorithmes présents dans la littérature prennent en compte
au plus deux critères. Les approches de planification d’itinéraire intermodal prenant en
compte plusieurs critères tendent à combiner les critères à optimiser ou de dissocier les
phases d’allocation des moyens de transport et les phases de choix de chemins ; aussi
ces approches ne prennent pas en compte le coût réel du transport de marchandises et
tendent à optimiser des critères comme le coût, le temps, le taux de service... occultant
les impacts environnementaux et sociétaux.
54
Chapitre 1. Généralités et état de l’art
Il conviendrait donc de mettre en place des techniques d’optimisation prenant en compte tous
les critères indispensables dans le contexte économique et social actuel, en y associant les
caractéristiques du transport intermodal et la structure géographique des systèmes de transport
de marchandises. À cet effet, le chapitre suivant a pour objectif de présenter notre apport en
termes de modélisation de réseaux intermodaux et de la mise en place d’un problème de plus
court chemin multiobjectif à travers la modélisation des critères de décision intégrant les
aspects environnementaux et sociétaux.
55
Chapitre 2. Modélisation du système de décision
Chapitre 2 Modélisation du
système de décision
56
Chapitre 2. Modélisation du système de décision
Introduction
Le précédent chapitre a mis en évidence les besoins en termes de modélisation des impacts du
transport intermodal. Le présent chapitre a pour objectif d’y répondre.
Notre contribution pour réduire les impacts du transport intermodal passe par la proposition et
la conception d’un système d’aide à la décision pour le choix d’un chemin minimisant ces
impacts. Cependant, ce choix ne doit pas seulement privilégier la réduction des impacts au
détriment des objectifs économiques que sont le gain de temps et la minimisation de coûts de
transport. Il est démontré que ces critères sont fortement contradictoires (Sawadogo et
Anciaux, 2011). La prise de décision dans un système intermodal devient ainsi multicritère.
Cela nous conduit au fait que le choix d’un chemin dans le réseau intermodal se fait suivant
plusieurs objectifs ; à la fois, sur des objectifs économiques, mais aussi sur des objectifs
écologiques et sociétaux.
Le problème défini, ici, concerne un transporteur qui doit livrer une quantité o de
marchandises d’un point d’origine C à une destination . Nous considérons dans notre étude
le transport d’un seul type de marchandises ; les marchandises ne sont pas dépotées de leurs
déplacements entre deux nœuds et séparés d’une distance q 1 pour chaque mode transport
• utilisé. A chaque nœud de ce réseau, nous avons des fenêtres temporelles d’arrivées et de
départ qui imposées soit par le client à la destination finale, soit par la configuration du réseau
au niveau des plateformes multimodales.
Nous avons dans le graphe plusieurs choix de chemins et de modes de transport possibles : il
existe donc plusieurs arcs reliant les villes du réseau. L’objectif ici est de déterminer le
57
Chapitre 2. Modélisation du système de décision
chemin « le plus efficace » de s à afin de minimiser les coûts engendrés par le transport, le
temps de transport et les différents impacts sur l’environnement et la société.
Les critères retenus pour le choix du chemin sont alors multiples et sont divisés sept groupes
de critères :
• Le coût de transport ;
• Le temps de transport ;
• La pollution atmosphérique ;
• La consommation d’énergie ;
Dans bon nombre d’études présentées dans la littérature, les objectifs sont souvent pondérés
ou réduits à un seul critère à optimiser. Cette pondération des critères nécessite de définir au
mieux l’importance que l’on souhaite accorder à chaque critère et ne permet pas de trouver un
compromis entre les critères à optimiser. Lorsqu’une importance égale est donnée à
l’ensemble des critères et surtout lorsque les critères à optimiser sont contradictoires, il est
nécessaire de les considérer individuellement pour en déterminer un compromis, donc une
solution qui améliore un objectif sans en détériorer un autre.
La particularité du choix des moyens de transport est que le moyen de transport le moins cher
peut s’avérer être le plus lent ou vice-versa. De même, le moyen de transport le plus rapide
donc intéressant en terme de temps de transport est souvent le plus polluant et/ou le plus
consommateur d’énergie (kérosène). En effet, pour le cas d’un transport entre Amsterdam et
Barcelone (transport de 50 tonnes de marchandises), le temps de transport moyen en avion est
de 254 minutes avec des émissions en gaz à effet de serre de 2.09 tonnes. Par contre, l’usage
du bateau par exemple nous garantit des émissions moins importantes de l’ordre de 357 kg,
mais le temps de transport est considérable de 5853 minutes.
58
Chapitre 2. Modélisation du système de décision
Le challenge ici consiste donc à trouver la meilleure représentation possible des critères ainsi
qu’une méthode d’optimisation efficace permettant de garantir le meilleur compromis
possible.
Le système de décision que nous avons été amenés à définir comprend plusieurs modules qui
permettent de prendre en compte à la fois la base de données sur le graphe et les critères à
optimiser (Figure 15). En fonction des préférences du décideur et des paramètres qu’il aura
choisis, il lui sera proposé un ensemble de chemins potentiellement intéressants du point de
vue de ses objectifs.
du réseau. Les arcs représentent un seul mode de transport ; le choix du mode à utiliser pour
59
Chapitre 2. Modélisation du système de décision
Soit
avec le même mode de transport ou le remplacer par un autre. Tout mode de transport •
transbordements; en effet, chaque nœud est un lieu où nous avons le choix entre continuer
utilisé sur un arc ( , ) est un élément de = /’L U, •L’ •N, 'UzM LU, Lé’ N9, ’yz N’6.
Dans le graphe , un seul et unique mode transport • ∈ est utilisé sur chaque
arc ( , ) ∈ .
est décrit par un triplet – = /” − , / 6, ” P 6 et chaque arc (i,j) est défini par un quadruplet
Ceci nous permet de décrire des étiquettes pour les nœuds et les arcs du réseau. Chaque nœud
Ω = ( , !, • , D O
Étiquette d’arc (j,k)
i
k j
– = /Γ − , / 6, Γ P 6
Étiquette du sommet i
t
s
On définit un horizon de temps total 70, 8 ; horizon de temps pendant lequel le trajet est
effectué sur un arc ( , ) donné. L’horizon de temps est choisi de telle sorte qu’il couvre la
totalité du temps nécessaire pour acheminer les marchandises d’un nœud à un autre. Le temps
60
Chapitre 2. Modélisation du système de décision
total de transport comprend les durées de transbordement, les retards dus aux engorgements,
ainsi que les temps de circulation « fluide ».
Dans notre étude, la prise en compte de la congestion se fait en termes de réduction des
retards éventuels causés par les congestions sur les arcs du réseau et de choix des heures de
départ et d’arrivées afin d’éviter les pics de congestion. Les heures de pics de congestion et
leurs positions sur les axes sont supposées connues à l’avance. Nous définissons des fenêtres
de temps correspondant aux pics de congestion et des vecteurs « positions » indiquant la
par trois variables : une densité de trafic š (nombre de véhicules par kilomètre), un flux φ
position du moyen de transport au niveau des pics de congestion. Le flot du trafic est décrit
(nombre de véhicules par heure) et une vitesse de circulation v (en kilomètre par heure).
Soit ι le nombre de fenêtres de temps pour chaque période de pic de congestion sur un arc
( , ) et ž Ÿ[
(
,…, ¡
Ÿ[ ¢ l’ensemble des fenêtres temporelles correspondant aux heures
d’engorgement sur l’arc ( , ) où :
¡
Ÿ[ =£ Ÿ[ , Ÿ[
¡• ¡P
¤ et ¡
correspond à l’heure du pic de congestion.
¡•
Ÿ[ : L’heure de début des engorgements
¡P
Ÿ[ : L’heure de fin des engorgements
On définit une variable position du moyen de transport aux heures de pic (’ ( , … , ’ ¡ ). Sur
chaque arc, nous observons des périodes de pics de congestion avec des goulets
0 ¡1
= yz © M (°)q° − ¨( ̌ 1 − ¡•
)
¨ ( 'Uz : 9y•x’N qN Méℎ DzUNC {L’ ℎNz’N) ¬-®¯
Ÿ[
[
Le transbordement est l’ensemble des opérations permettant de faire passer des marchandises
d’un mode de transport à un autre, avec éventuellement une mise à quai intermédiaire, sans
passer par le stock.
Soit Ž 1,1 le temps total de transbordement au nœud ∈ ; c’est le temps requis pour faire
•
avec :
61
Chapitre 2. Modélisation du système de décision
Ž 11 = o. ∆ . ℎ
•
À chaque nœud, nous pouvons avoir des heures de départ ou d’arrivées précises compte
tenues des opérations de transbordement à effectuer, des horaires d’ouverture et de fermeture
des quais, des heures de fermeture des entrepôts du client, etc. Nous en déduisons des
contraintes horaires appelées fenêtres de temps associant une date au plus tôt et une date au
plus tard pour chaque moyen de transport sur chaque nœud. Ces fenêtres de temps peuvent
être rigides (aucun retard n’est permis) ou souples (les retards sont autorisés sous certaines
conditions). Ces contraintes induisent des coûts supplémentaires que nous définirons plus
loin.
L’heure de départ, ̌ 1 du nœud avec le mode •, est déterminée suivant deux cas :
i. L’heure de départ n’est pas connue à l’avance et dans ce cas, il faudra le calculer en
fonction des données du problème :
̌ 1 = L1 + Ž 11
•
U 1 = ̌ 1 − Ž 11
•
Aussi, si le nœud considéré est le nœud final (la destination finale) c’est-à-dire =
alors ̌ 1 = 0 et si = C c’est-à-dire le nœud source, alors L1 = 0.
,
Soit 1
le temps total de transport sur l’arc( , ). En présence de congestion, le temps total de
¥1
transport est défini comme ayant deux composantes : le temps « libre » de trajet qui est
une composante fixe et connue du temps de trajet calculée en fonction des fenêtres
62
Chapitre 2. Modélisation du système de décision
la congestion 0 ¡1 ; d’où
temporelles et de la vitesse moyenne, et une composante variable qui représente le retard dû à
= + 0 ¡1
1 ¥1
Avec :
= p1 − ̌ 1
¥1
Afin de caractériser le coût global (externe et interne) d’un transport de marchandises, il est
nécessaire de modéliser le plus fidèlement possible le coût réel demandé par le transporteur
pour acheminer la marchandise d’un fournisseur. Ainsi, la construction du modèle ci-dessous
a pour but de répondre au mieux à ces exigences. Le coût de transport inclut les coûts de
débrayage et les frais de voyage. C’est l’ensemble des coûts fixes et variables engendrés par
mobilisés par l’utilisation d’un moyen de transport • pour répondre à la demande d’un
l’utilisation du moyen de transport, c’est-à-dire l’ensemble des coûts du transporteur
fournisseur. Le coût de transport ³(1 sur l’arc ( , ) utilisant le mode de transport • est
donné par :
³(1 = ´ED(1 + 1
. D)1 + q 1 . D 1 F. µ¶ 1 + 1
+ (1 − 1 ).
·Eo/ − ¶ 1 . ¹)/¹ Bº»
Avec,
0≤ 1
≤1 (i)
¶1 = i B
¶(1
(ii)
Sinon
Avec,
63
Chapitre 2. Modélisation du système de décision
1 Si >
¾ Á
¿¾ « ¿Á «
=i B (iv)
sinon
¾
Á
³o si ¿¾ > ¿Á
¾ Á
¹=| B (v)
³ sinon
Où
¶1 : Nombre (d’unité -1) de moyens de transport du mode • nécessaires pour l’arc ( , )
D(1 : Coût fixe dû à l’utilisation du moyen de transport • (coût de prise en charge) exprimé
D)1 : Coût d’utilisation du moyen de transport • par unité de temps (en fonction du temps
en devise.
DÂ1
de transport).
: Coût de déplacement en devise par unité de déplacement pour moyen de transport.
1
: Temps de trajet sur l’arc (i, j)
1
o
: Coefficient de prise en charge du moyen de transport •.
: Masse de produits transportés en unité de poids
³o
: Volume de produits transportés en unité de volume
1
³
: Capacité massique du moyen de transport •.
1
: Capacité volumique du moyen de transport •.
Dans ce modèle, D(1 caractérise les coûts fixes rencontrés par le transporteur pour l’utilisation
du moyen de transport • ; ce paramètre inclut la venue éventuelle du moyen de transport sur
dossier…). D)1 permet de prendre en compte les coûts horaires engendrés par l’utilisation du
le site du fournisseur quelque soit la charge à transporter et les kilomètres à réaliser (frais de
64
Chapitre 2. Modélisation du système de décision
L’acheminement de marchandises par une unité non remplie engendre des frais qui peuvent
être de natures différentes ; en effet :
• L’unité de transport voyage seulement avec la marchandise du client : l’unité n’est pas
remplie donc le surcoût unitaire de masse transporté est plus élevé pour le transporteur
que s’il voyageait rempli.
• L’unité de transport voyage remplie, car le transporteur a rempli son unité de transport
incomplète grâce à d’autres clients : le transporteur a des coûts supplémentaires de
cogestion.
³Ä1 = à 1 = ED(1 + 1
. D)1 + q 1 . DÂ1 F. (¶ 1 + 1
+ (1 − 1 ).
·Eo/ − ¶ 1 . ¹)/¹ )B
− Eo/ − ¶ 1 . ¹)/¹F
C’est le coût du stock en transit dans les points de transbordement, plateformes logistiques ou
hubs intermodaux. Ce coût est considéré comme étant la somme des coûts de stockage en
transit et du coût du stock de sécurité. Le coût du stock de sécurité est généralement
négligeable par rapport à celui du stock en transit ; de ce fait, il est souvent ignoré lors des
comme étant proportionnel au temps de transit. Le coût total ³)1 du stock en transit est donné
prises de décisions. Nous tenons compte uniquement du coût du stock en transit, considéré
par :
³)1 = Å. DÆ1 . š’
65
Chapitre 2. Modélisation du système de décision
Avec
Pour aller d’un nœud à un nœud successeur ∈ ” P , les containers sont transbordés (ou
non) d’un mode de transport • vers le même mode de transport (transfert intra-modal) ou un
autre mode •’ (transfert intermodal). Le coût de ce transbordement est obtenu à partir de la
fonction suivante :
³Â1 = ³ 11 . ℎ . µ(¶ 1² +
•
1²
+ (1 − 1² B
. ·Eo/ − ¶ 1² . ¹ /¹ º
Avec :
3.2.5 La remise
³Æ1 = È 1 = 4(¶ 1
Avec les fenêtres temporelles, le coût total de transport inclut non seulement les coûts définis
plus haut, mais également les coûts engendrés par le fait qu’un moyen de transport arrive très
tôt ou en retard à destination. Nous définissons deux coûts de pénalité : le coût de pénalité de
66
Chapitre 2. Modélisation du système de décision
D’où :
Í =. EN 1 − L1 F C L1 ≤ N 1 {é9LU é q² LML9DN
Ë
³É1 = D = 0 C L ∈ ÎN , U Ï B
1 1 1
W
Ì
Ë . EL − U F C L ≥ U 1 {é9LU é qN ’N L’q
1 1 1
Ê
Avec :
Le coût de transport total D ( est donné par la somme des coûts définis plus haut :
É
D ( = e ³Ð1 = ´ED(1 + 1
. D)1 + q 1 . DÂ1 F. µ¶ 1 + 1
+ (1 − 1 ). B
·Eo/ − ¶ 1 . ¹)/¹ º»
Ñ‹(
+ ED(1 + 1
. D)1 + q 1 . DÂ1 F. ( 1
+ (1 − 1 ).
·Eo/ − ¶ 1 . ¹)/¹ )B
+ ³ 11 . ℎ . µ(¶ 1² +
•
1²
+ (1 − 1² ). B + È 1 + D W
·Eo/ − ¶ 1² . ¹)/¹º
Pendant les opérations de transbordement, des dégâts peuvent survenir pendant le transport et
la manipulation des produits. Par exemple, lors du transbordement de marchandises fragiles
comme des fleurs ou du verre, nous avons des risques d’abimer ou de casser la marchandise.
nœud du réseau est donnée par un calcul réalisé en utilisant le théorème central limite.
.Å ÔZÖ − ÅÔZÖ ×Û
Ò 11′ = o. ℎ .
ÈÜÅÔZÖ
Avec :
Pour estimer la quantité des émissions de gaz à effet de serre émise par le transport de
marchandises, il est nécessaire de considérer les émissions directes et indirectes des différents
moyens de transport. Le modèle d’estimation ici présenté permet de quantifier les émissions
de CO2, COV et NOX, principaux gaz émis par les moyens de transport. La fonction
d’estimation dépend de la masse de marchandises acheminée, du type de moyen de transport
ainsi que de la distance parcourue. Les performances environnementales des transports
dépendent également du coefficient de charge et de la capacité des moyens de transport
utilisés.
La quantité de gaz polluant émis ß d’un gaz á par le mode de transport • sur un arc ( , )
1à
DÄ = ß = N 1à (o, ). Eq 1 + 0âl F. µ¶ 1 + + (1 − 1 ).
·Eo/ − ¶ 1 . ¹)/¹ Bº
1à 1 1
Avec:
N 1à : Quantité de polluant á émise par le moyen de transport • en unité de poids, par unité
de poids de marchandises transportées et par unité de déplacement, les différentes valeurs
correspondant à ce paramètre sont présentées dans le Tableau 2.
Tableau 2. Facteur d’émission moyenne des polluants pour le fret (Knorr et Reuter, 2005)
68
Chapitre 2. Modélisation du système de décision
0âl
1
représente la distance parcourue pendant la période de roulage pour un avion en unité de
distance ; en effet une grande partie des émissions de gaz à effet de serre émanant des avions
est observée lors de la phase de roulage. Il est donc indispensable de tenir compte de la
d’énergie consommée par un moyen de transport • est calculée ici en fonction de la distance
dans les pays les plus dépendants du nucléaire pour leur production d’électricité. La quantité
D É = $ 1 = o. q 1 . = 1
Le diagnostic et la gestion des nuisances sonores dues au transport de marchandises sont une
entreprise difficile, car elle demande une grande transversalité des acteurs et des compétences.
Elle rassemble plusieurs domaines aux préoccupations parfois antagonistes, comme
l’environnement, l’économie, les transports ou encore la santé. De plus, au problème
scientifique qu’est la description quantitative du bruit s’ajoute le problème
psychosociologique qui est celui de la description de la gêne sonore.
Le transport est la principale source de pollution sonore. La pollution sonore peut être définie
comme un son indésirable ou nuisible. Le bruit généré par les systèmes de transport affecte
69
Chapitre 2. Modélisation du système de décision
les personnes dans les zones d’habitation ; ces nuisances sont d’autant plus importantes que le
trafic est dense. Les perturbations sonores émises par le trafic dépendent du volume du trafic
(la densité), de la vitesse et de la composition du trafic (type de véhicules) ; elles dépendent
également de la distance entre la route et les premières habitations ou les zones d’impacts. Un
camion entendu à 50 mètres produit par exemple un bruit d’environ 90 dBA (David J.
Forkenbrock 1999). En effet, le bruit tend à s’affaiblir si la distance séparant l’autoroute des
zones d’impact est supérieure à environ 305 m selon des études menées par (Hokanson et al.
,1981). Même si le bruit émis est faible, le bruit intermittent ou discontinu peut être très
gênant plus particulièrement pour des gens qui sont dans des lieux nécessitant une certaine
concentration, de la tranquillité ou même un repos, à savoir les écoles, les lieux de cultes, les
hôpitaux... En plus de cela, il faut ajouter les effets psychologiques du bruit qui est difficile à
estimer financièrement ; par exemple, les nuisances sonores tendent à diminuer la valeur
financière des habitations situées dans des zones sujettes à ces nuisances. En outre, d’autres
éléments comme la topographie du chemin, les arbres, les buildings... peuvent avoir une
influence sur le niveau de bruit émis. Dans notre cas, nous modélisons le bruit en fonction de
l’éloignement moyen des zones d’impacts et du nombre moyen de personnes impactées.
¹ = ¨ x 1 ÒWåW[ æ 1
survienne sur un tronçon de route ( , ) et la conséquence engendrée par l’incident, qui peut
Traditionnellement, le risque est défini comme le produit entre la probabilité qu’un incident
70
Chapitre 2. Modélisation du système de décision
Lowrance (Lowrance, 1976) définit le risque d’accident comme une mesure de la probabilité
qu’un accident survienne et de la gravité des dommages engendrés par cet accident.
probabilité qu’un moyen de transport • transportant une quantité o de marchandises sur une
Pour les besoins de notre étude, nous définissons le risque d’accident comme étant la
distance q soit impliqué dans un accident sur un arc ( , ) du réseau. Cette probabilité suit
une loi de Poisson de paramètre ç1 . En effet, la loi de probabilité a priori la mieux adaptée,
Poisson (probabilité d’être impliqué dans ! accidents). Sa fonction de répartition est définie
concernant le nombre d’accidents sur une période donnée sur un axe de transport, est la loi de
Eç1 F
{ (× = !) = N
è •é«
.
!!
[
ç1 : Nombre réel strictement positif représentant le nombre moyen d’accidents engendré par
le moyen de transport m sur l’arc ( , ) en fonction de la densité du trafic : nombre
d’accidents par unité de flux : ç1 =
f:+å1ëìâ 1å â+ í• èîî íâ+lH HÑì O²èìî
ï:¥OÑ íÑ lìè¥ î HÑì O²èìî
!
N
: Nombre réel strictement positif
: La base de l’exponentielle
Dans notre modèle, le risque d’accident est associé au mode routier ; les risques d’accident
émanant des autres modes de transport (aériens, maritimes, fluvial, ferroviaire) étant très
faibles, ils sont considérés comme négligeables.
Le modèle proposé ici contrairement à ceux proposés dans la littérature permet de prendre en
compte à la fois les caractéristiques du transport intermodal et l’ensemble des critères
intervenant dans la prise de décision au sein de la chaîne logistique verte. Nous construisons
une fonction objectif pour chacun des critères pris en compte. Les contraintes du problème
sont également modélisées et prises en compte dans le système de décision.
Considérons le graphe ( , , ) défini plus haut. Soit n le nombre de critères étudiés, avec
9 ≥ 2. À chaque arc ( , ) ∈ , nous associons une fonction vectorielle c de dimension 9, qui
attribue à chaque arc un « coût » D O , (U = 1, … , 9) représentant l’ensemble des coûts sur l’arc
( , ) l’ensemble des critères U. D’où :
71
Chapitre 2. Modélisation du système de décision
D: ⟶ ℝ+
( , ) ⟼ D O ( , ) = D O = ED ( , … , D + F
D O = D( , … , D +
i j
Les valeurs des composants du vecteur coût D O dépendent du mode de transport utilisé sur
l’arc ( , ) ∈ .
et , 1 , où
, 1 la variable d’utilisation des modes de transport avec :
Soit deux variables binaires représente la variable de conception du réseau et
• Les fonctions
Pour chaque critère D O étudié, une fonction objectif ' O ( ) est définie.
i j i j
Soit ' O ( ) le vecteur « fonction objectif » de dimension U ; le problème de plus court chemin
multiobjectif dans un réseau intermodal est formulé comme suit :
• 9 'O ( ) = e DO . ∀U = 1, … , 9
( , )∈f
Dans ce modèle, nous supposons que toutes les fonctions objectifs sont aussi importantes les
unes que les autres. Les critères étudiés étant indépendants les uns des autres, nous sommes
dans un cas d’optimisation multiobjectif avec fonctions indépendantes.
On distingue deux types de contraintes dans notre problème : des contraintes globales,
définies sur l’ensemble du réseau, et des contraintes locales définies sur les arcs ou les nœuds
72
Chapitre 2. Modélisation du système de décision
du réseau. Ces contraintes peuvent porter sur le graphe et sa construction ou directement sur
les critères.
D O ≥ 0 , ∀ ( , ) ∈ (1)
= ∈ ℕ⁄ ∈ 70,18; ∀ ( , ) ∈ (2)
, 1 = , 1 ∈ ℕ ∕ , 1 ∈ 70,18B; ∀ ( , ) ∈ B N • ∈ 6 (3)
entrants en ( =1) doit être égal au nombre total d’arcs utilisés sortants de ( = 1) ; en
La contrainte d’équilibre de conception est définie comme suit : le nombre total d’arcs utilisés
d’autres termes,
e = e
/ :( , )∈f)6 / :( , )∈f)6
D’où la contrainte,
1 = C ; =0
∑/ :( , )∈f)6 − ∑/ :( , )∈f)6 = i 0 ∀ ∈ \/C, Ö6 B
−1 = Ö ; =0
(4)
= ,1 ∀ ( , ) ∈ et • ∈ (5)
Les contraintes (1), (2) et (3) sont des contraintes de non-négativité. La contrainte (4) est la
arcs construisant un chemin de C à . La contrainte (5) signifie que l’utilisation d’un arc ( , )
contrainte d’équilibre de conception à chaque nœud du réseau (nécessaire pour obtenir les
4.1.2.2 La praticité
La praticité ö1 d’un moyen de transport • correspond à son aptitude à être pratique pour
acheminer o (tonnes) ou (m3) de marchandises sur une distance q 1 . Ce caractère pratique
d’un moyen de transport • est fonction des trois variables énoncées ci-dessus et donné par :
ö1 = ÷(o, , q 1 )
Une pénalité de praticité ö1 ∈ 71,28 est affectée au coût de transport pour le moyen de
transport • utilisé sur l’arc ( , ) donnant ainsi ö1 × D O1 . Nous considérons que le train et le
Par contre, pour ce qui concerne l’avion et le camion nous avons défini plusieurs fonctions de
praticité en fonction de la distance et de la quantité de marchandises transportées.
73
Chapitre 2. Modélisation du système de décision
ö(í) èù å+ = + 1. Cette fonction est une asymptote horizontale à 1 (Figure 18); en effet,
Æ(
La fonction de praticité en fonction de la distance pour l’avion est donnée par la fonction
íPÆŒ
pour de courtes distances il parait inutile d’utiliser un avion, par contre plus la distance
parcourue augmente, plus il devient intéressant d’utiliser l’avion la pénalité affectée au coût
tend alors vers 1.
ö(í) èù å+
Distance d
ö(í) îè1 å+ = (Œú q ) + 1. Plus la distance est grande plus le camion devient moins pratique à
(
Pour le camion cette fonction de praticité en fonction de la distance est donnée par :
ö(í) îè1 å+
Distance d
74
Chapitre 2. Modélisation du système de décision
(Æ ÆŒŒ ÉŒ
o < 120 et pour o > 120 une praticité allant jusqu’à 2 est infligée pour l’usage de l’avion. Il
de sommet (120, 1). La capacité moyenne des avions-cargos étant d’environ 120 tonnes, pour
serait plus intéressant pour de très grandes quantités d’utiliser le train et pour de très petites
quantités le camion par exemple.
ö(¾) èù å+
Quantité Q
La fonction de praticité massique associée au camion est donnée par la fonction ö(¾) îè1 å+ =
o ) + 1. Pour une quantité supérieure à environ 30 tonnes, le camion devient moins
(
() ÄŒŒ
intéressant à utiliser, en effet vu que la capacité massique des camions est en général de 30-40
tonnes, il faudrait utiliser plus d’un camion ou privilégier plutôt l’usage de l’avion ou du train
(Figure 21).
75
Chapitre 2. Modélisation du système de décision
ö(¾) îè1 å+
Quantité Q
Soit l’heure idéale d’arrivée au nœud tel que ∗ ∈ ÎN 1 , U 1 Ï. L’heure de départ du nœud
∗
̌1 = ∗
− 0 ¡1
∗
≤ U1
Cette contrainte a pour but d’induire le choix de l’heure de départ du nœud source de façon à
temps imposée par le client au nœud destination. Soit Ÿ• = 7Nl1 , Ul1 8 la fenêtre de temps au
respecter les différentes fenêtres temporelles dans chaque ville et d’arriver dans la fenêtre de
nœud destination, Nl1 et Ul1 représentent respectivement l’heure d’arrivée au plus tôt et heure
d’arrivée au plus tard au nœud destination. Et soit ŸZ = 7 ̌H1• , ̌H1P 8 la fenêtre de temps au
nœud source, ̌H1• et , ̌H1P représentent respectivement l’heure de départ au plus tôt et heure
de départ au plus tard au nœud source.
Le choix de l’heure de départ du nœud source est contraint par l’équation suivante :
Ul1 − ̌H1• ≤ e
( , )∈YZ•
76
Chapitre 2. Modélisation du système de décision
Å ÔZ• = e ℎ ≤ ü
‹(
l’ensemble des chemins optimaux dans le graphe pour aller de C à . La recherche d’un
, le problème de plus court chemin multiobjectif dans un graphe a pour but de trouver
Le temps de transport : D ( = + 0 ¡1
¥1
•
• Le coût de transport : D ) = ∑ÉÑ‹( ³Ð1
ÞÅ Ô •ÅÔZÖ Û
• Les dégâts dus aux transbordements : D Â = o. ℎ . ZÖ
·ÅÔZÖ
(1 − 1 ).
·Eo/ − ¶ 1 . ¹)/¹ vB
• La consommation d'énergie : D Ä = o. q 1 . = 1
• La pollution sonore : D É = ¨ x 1 ÒWåW[ æ 1
žé«
[ ¢
• Le risque d'accident : D = N •é«
[ . !
Les fonctions objectifs associées à ces critères permettent de poser le problème suivant :
77
Chapitre 2. Modélisation du système de décision
Í' ( )=e D( . . ,1
(
Ë
( , )∈f
Ë' ) ( )=e D) . . ,1
Ë ( , )∈f
Ë Â
Ë' ( )=e DÂ . . ,1
Ë
( , )∈f
9 ' (
Æ )=e DÆ . . ,1B
Ì ( , )∈f
Ë' Ä ( )=e DÄ . . ,1
Ë ( , )∈f
Ë
Ë' É ( )=e DÉ . . ,1
Ë ( , )∈f
Ë' ( )=e D . . ,1
Ê ( , )∈f
D O ≥ 0 , ∀ ( , ) ∈ (1)
= ∈ ℕ⁄ ∈ 70,18; ∀ ( , ) ∈ (2)
, 1 = , 1 ∈ ℕ ∕ , 1 ∈ 70,18B; ∀ ( , ) ∈ B N • ∈ 6 (3)
1 = C ; =0
∑/ :( , )∈f)6 − ∑/ :( , )∈f)6 = i 0 ∀ ∈ \/C, Ö6 B
−1 = Ö ; =0
(4)
= ,1 ∀ ( , ) ∈ et • ∈ (5)
ö1 = ÷Eo, , 1
, q1 F (6)
Å ÔZ• = ∑Ú•(
‹( ℎ ≤ ü (8)
somme des valeurs associées au critère U sur le chemin GHl c’est-à-dire la somme des valeurs
associées aux arcs qui le composent.
D’où :
D O ( GHl ) = e D O
( , )∈ YZ•
D O ( GHl ) , représente la somme des valeurs associées au critère U sur chaque arc du chemin GHl
∀U = 1, … , 9. En d’autres termes, le vecteur D O ( GHl ) du chemin GHl est une somme
78
Chapitre 2. Modélisation du système de décision
vectorielle des vecteurs correspondant aux arcs. Résoudre le problème de plus court chemin
objectif D O ( GHl ).
revient donc à trouver l’ensemble des chemins ayant une valeur minimale pour le vecteur
Conclusion
Dans ce chapitre nous avons intégré les impacts environnementaux et sociétaux dans la prise
de décision au sein d’un réseau de transport intermodal. Pour aider les décideurs à planifier
leurs itinéraires dans un contexte de développement durable, un modèle mathématique a été
mis en place pour modéliser leurs critères de choix. Ce modèle a pour objectif de modéliser le
plus fidèlement possible tous les critères devant être pris en compte dans la prise de décision
pour un transport intermodal au sein de la chaîne logistique verte. Et contrairement à ce qui se
fait dans la littérature, il se veut, être plus complet parce que prenant en compte, tous les
aspects du système étudié. Nous avons ainsi présenté un modèle de plus court chemin
multiobjectif qui caractérise des réseaux intermodaux et qui permet à la fois d’optimiser les
coûts de transport, le temps de transport et les impacts socio-environnementaux, dans de but
d’apporter une réponse efficace à la résolution de problèmes environnementaux liés au
transport.
79
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
Chapitre 3 MOSPACO : Un
algorithme de colonie de fourmis
pour le problème de plus court
chemin multiobjectif au sein des
chaînes logistiques vertes
80
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
Introduction
Bien que de plus en plus utilisés pour résoudre des problèmes complexes, les algorithmes de
colonies de fourmis sont très peu utilisés pour résoudre des problèmes de plus court chemin
multiobjectif. En effet, l’usage des algorithmes de colonies de fourmis est moins important
par rapport à celui des algorithmes génétiques par exemple, à cause notamment du très
grand nombre de paramètres à régler et surtout de la sensibilité de l’algorithme aux
changements de paramètres. Il faut une adaptabilité et un réglage adéquat des paramètres de
l’algorithme afin de favoriser la convergence.
Ce chapitre présente l’algorithme de colonies de fourmis que nous avons mis en place pour
optimiser les critères définis au chapitre 2 en tenant compte du modèle de plus court chemin
multiobjectif proposé et des différentes contraintes. Partant du modèle développé au chapitre
2, l’algorithme de recherche de chemin devrait prendre en compte les critères choisis par le
décideur ainsi que les caractéristiques du réseau de transport intermodal (changement de
mode, existence de transbordements...). La plupart des algorithmes utilisés pour résoudre les
problèmes de plus court chemin multiobjectif (algorithmes à correction d’étiquettes,
algorithmes à sélection d’étiquettes, algorithmes génétiques) nécessitent que l’ensemble des
étiquettes associées aux chemins soit calculé ou que l’on connaisse toutes les alternatives
possibles de chemins dans le réseau. Dans un réseau prenant en compte un très grand
nombre de critères (sept dans notre cas) et ayant un nombre de transbordements élevé, il est
impossible de lister toutes les alternatives et de calculer les différentes étiquettes.
La recherche de chemin dans notre cas se veut purement exploratoire, nous avions donc
besoin d’une méthode constructive dans laquelle les chemins sont construits nœud après
nœud en fonction des données disponibles à chaque étape de la construction ainsi que des
chemins déjà construits et des nœuds déjà sélectionnés ; les algorithmes de colonies de
fourmis étaient donc plus adaptés pour atteindre cet objectif.
De plus, pour les besoins de notre étude nous avons été amenés à modifier l’algorithme « Ant
Colony System » et les différents éléments de l’ACO afin de mettre en place un algorithme de
colonie de fourmis « MOSPACO » (Ant Colony Optimization for Multi-Objectif Shortest
Path) à même de prendre en compte les sept critères étudiés ici et le caractère intermodal de
notre réseau de transport. L’algorithme proposé utilise des formules présentées dans
(Garcia-Martinez et al., 2007) pour certains calculs, notamment pour le calcul de la
probabilité de sélection, définit comme étant la combinaison de la visibilité et des traces de
phéromones.
Dans MOSPACO, nous avons proposé une nouvelle définition des matrices de visibilité et des
traces de phéromones, des règles de transition, de la procédure de mise à jour des traces et
d’évaluation des solutions. Dans cette approche, les fourmis représentent des agents fictifs
construisant des chemins dans le graphe ; chaque fourmi porte en elle des informations sur le
chemin construit.
Dans ce chapitre, nous présenterons dans un premier temps une description de MOSPACO,
puis nous détaillerons les paramètres de l’algorithme en mettant en évidence nos apports,
81
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
1. Description de MOSPACO
En général, tout algorithme de colonie de fourmis doit contenir les éléments suivants : une
information heuristique (visibilité), une stratégie des traces de phéromones, des règles mises à
jour des traces de phéromones, un processus de construction des solutions, une règle de
transition, et une condition d’arrêt ; les différents algorithmes de colonies de fourmis sont le
résultat d’implémentations spécifiques de ces éléments. La présente section décrit ces
éléments pour MOSPACO qui est une variante multiobjectif de l’algorithme original « ACS »
(Ant Colony System). Dans MOSPACO, nous avons modifié certains paramètres de l'ACO
classique. Les principales caractéristiques de cette approche sont les suivantes :
• Chaque fourmi de la colonie porte comme information la liste des nœuds visités, les
moyens de transport utilisés entre ces nœuds, le vecteur objectif du chemin trouvé, le
temps mis par la fourmi pour trouver un chemin ainsi que le nombre de
transbordements réalisés par la fourmi.
• Nous utilisons plusieurs matrices de phéromones, une par objectif et par mode de
transport. Les mises à jour des traces de phéromones sont opérées par les meilleures
fourmis des itérations en cours.
• Contrairement à ce qui se fait dans la littérature (une ou deux règles de transition), nous
avons défini trois règles de transition pseudoaléatoires en fonction des caractéristiques
de notre problème.
En d’autres termes, nous utilisons des traces de phéromones et des matrices de visibilité
multiobjectifs et multimodales ; les fourmis dans cet algorithme utilisent ces différents
82
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
paramètres pour le choix des modes de transport et des transbordements qui en découlent.
Chaque fourmi incrémente le nombre de transbordements qu’elle réalise à chaque fois que le
mémoire p C N¥ qui stocke les informations concernant les chemins sélectionnés par la
mode de transport choisi est différent du précédent. Chaque fourmi de la colonie possède une
fourmi, la succession de moyens de transport utilisée, ainsi que le vecteur objectif de chaque
chemin contenant les valeurs de chaque objectif pour ledit chemin. Ces vecteurs sont ensuite
évalués et comparés les uns par rapport aux autres pour déterminer les solutions non-
dominées. Comme présenté dans la Figure 22, à chaque nœud du réseau la fourmi doit trouver
son chemin en optimisant les sept critères pris en compte et les moyens de transport
disponibles. Les contributions principales de MOSPACO résident dans la définition des
matrices de visibilités et des traces de phéromones, dans la stratégie de construction et
d’évaluation des solutions ainsi que dans la définition des règles de transition.
?
t
s
Cette information indique l’attrait de tout arc ( , ) en utilisant le moyen de transport • ; cette
visibilité dépend donc fortement du moyen de transport utilisé. L'information heuristique est
calculée pour tous les arcs accessibles à partir de nœud courant, l’arc ayant la visibilité la
plus intéressante sera sélectionné. Cette heuristique pouvant être définie « à priori » ou « a
posteriori », notre approche tend à combiner ces deux aspects. En effet, la visibilité est définie
au début de l’algorithme et mise à jour dynamiquement au fur et mesure que l’on avance dans
la recherche de solutions. Sept matrices de visibilité tO1 ont été définies, une par critère U.
83
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
Chaque matrice est définie comme étant l’inverse de la valeur associée au critère U pour le
moyen de transport • sur l’arc ( , ) tel que :
1
tO1 = µ º
= + DO
Dans cette expression, = représente un nombre positif ajouté pour éviter la division par 0. Par
ayant un temps de transport minimal. En d’autres termes, si la valeur associée au critère U sur
exemple, la matrice associée au temps de transport permet aux fourmis de privilégier les arcs
l’arc ( , ) est minimale, ce dernier sera préféré aux autres. La visibilité totale sur un arc est
obtenue en multipliant les valeurs des visibilités de chaque critère.
utilisé, sept matrices O1 ont été définies, une pour chaque critère U et chaque mode de
l’empreinte laissée par chaque fourmi pour chacun des critères et chaque moyen de transport
o
∆ O1
=
D O E GHl (¥) F
Cette valeur est définie pour chaque moyen de transport • utilisé. Nous définissons donc une
matrice de phéromone multimodale à trois dimensions : 7y’ 4 9N, qNC 9L y9 , •yqN 8
associée à chaque critère.
Dans cette équation o est une constante relative à la quantité de phéromones laissée par la
fourmi '. La matrice de visibilité totale sur un arc pour chaque moyen de transport • est
obtenue en multipliant les valeurs de traces associées à chaque critère.
84
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
3. Fonctionnement de l’algorithme
Cette partie décrit le processus utilisé par les fourmis pour la construction des chemins. Dans
les approches utilisées dans la littérature, notamment pour le problème du voyageur de
commence, le sens de parcours du graphe n’est pas imposé, les fourmis sont donc le plus
souvent réparties de façon aléatoire sur les nœuds du réseau. Dans notre cas, les contraintes
liées aux fenêtres temporelles et la configuration du réseau (partir d’une source vers une
destination donnée) exigent que les fourmis soient positionnées de façon à pouvoir construire
un chemin cohérent entre la source et la destination.
Ainsi, nous avons choisi de faire fonctionner l’algorithme de deux manières différentes
( → C) ; ces deux sens de parcours sont imposés surtout par la prise en compte des fenêtres
l’algorithme, toutes les fourmis sont placées sur le nœud source s et leur mémoire p C N¥
temporelles (plus de détails dans la section 3.1.5). Dans le premier cas, au début de
prend comme valeur initiale le nœud C. Dans le second cas, toutes les fourmis sont placées sur
le nœud destination et leur mémoire p C N¥ prend comme valeur initiale le nœud .
fourmis de la colonie. Une fois que la fourmi ' atteint le nœud destination , elle arrête la
directs (vecteur coût, mode de transport utilisé). Ce processus est répété pour chacune des
‡ et ˆ sont les paramètres d’ajustement propre aux ACO. ‡ est l’importance relative des
traces de phéromones par rapport à la visibilité et ˆ contrôle l’importance relative de la
fortement le fonctionnement des ACO. Les paramètres ‡ et ˆ peuvent réduire fortement les
visibilité par rapport aux traces de phéromones ; le choix de ces deux paramètres influence
85
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
Concernant ces paramètres, il est impossible de les régler précisément ; il faut donc trouver un
compromis permettant de maintenir un bon niveau de performance de l’algorithme. Dans la
construction des solutions, deux processus sont opérés simultanément à savoir un processus
dit de diversification et un processus dit d’intensification. Le processus de diversification a
pour objectif de diversifier l’espace de recherche afin de permettre aux fourmis de découvrir
de nouvelles, voire de meilleures solutions. Le processus d’intensification a pour but
d’intensifier la recherche autour des zones de l’espace de recherche contenant les meilleures
solutions. L’équilibre entre ces deux processus garantit l’efficacité de l’algorithme utilisé.
En général dans les ACO, il existe plusieurs manières de gérer ces deux processus. Les deux
méthodes les plus utilisées pour régler ces deux processus consistent d’une part à régler les
paramètres α et β, et d’autres parts à régler les paramètres α et ρ (facteur d’évaporation des
traces de phéromones). Le but ici étant de ne pas avoir une convergence trop rapide de
l’algorithme (intensification plus forte), mais aussi d’éviter une convergence trop lente
(diversification, donc recherche aléatoire de solutions.) : il faut donc trouver un compromis.
Pour régler ces deux paramètres, nous avons exécuté l’algorithme pour plusieurs
combinaisons des paramètres, nous avons utilisé un réseau de transport de 100 villes avec 100
fourmis et 50 itérations par fourmi. Les fronts de Pareto obtenus par les différentes
configurations sont ensuite comparés les unes aux autres. Par la suite, la combinaison de
paramètres donnant de meilleurs résultats sera conservée pour l’exécution de l’algorithme.
Les valeurs de paramètres qui permettent de respecter les propriétés d’intensification et de
diversification de l’algorithme seront jugées acceptables pour l’algorithme. La Figure 23 et la
Figure 24 représentent les solutions non-dominées obtenues pour différentes valeurs des
paramètres en optimisant simultanément les critères coût et temps.
86
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
Les fronts de Pareto obtenus par les meilleures valeurs des paramètres sont ensuite comparés
entre eux (Figure 24).
87
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
Synthèse a, b, c a
b c
configuration ‡ = 5, ˆ = 1.
88
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
les interactions entre ceux-ci. Ils permettent également au décideur de donner la priorité à
certains critères et cela selon ses préférences. La cohérence des jugements doit être respectée,
en effet un ratio de consistance est calculé pour chaque matrice de jugement et le jugement est
dit cohérent lorsque le ratio de consistance CR est inférieur à 10%.
Pour ce scénario, les critères « coûts de transport », « temps de transport », « dégâts dus aux
transbordements » sont les plus importants ; par conséquent, leur poids est plus élevé que
celui des autres critères. La visibilité et les traces de qui leur est associé sont aussi plus
importantes. La comparaison par paires des critères permet d’obtenir les poids représentés
dans le Tableau 4 pour le scénario industriel. Le ratio de consistance des matrices de jugement
(Annexe 1) utilisées est de 1.9%, ce qui traduit une consistance du jugement. Parmi les
critères dits industriels, le coût et le temps ont une importance plus élevée que les dégâts.
Dans ce cas, la priorité est donnée aux critères « pollution », « consommation d’énergie »,
« pollution sonore » et « risque d’accident ». Le Tableau 5 donne les valeurs obtenues pour
ces critères. L’importance donnée aux critères pollution et énergie est plus importante que
celle des autres critères. Les matrices de jugement utilisées pour obtenir ces poids donnent un
ratio de consistance acceptable de 8.6%.
89
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
On définit le paramètre §Œ tel que §Œ ∈ 70,18 correspondant à la probabilité pour une fourmi
' de faire un bon choix et le paramètre ’L9q qui est une variable aléatoire générée
automatiquement par le système. Suivant les valeurs de §Œ et ’L9q, le prochain nœud à
visiter par la fourmi est choisi selon les trois règles de transition ; les deux premières règles
découlent d’un compromis entre la visibilité et les traces de phéromones, la troisième règle est
aléatoire. La troisième règle a été rajoutée pour deux raisons ; la première est que certains de
nos critères notamment le risque d’accident et les nuisances sonores peuvent prendre des
valeurs nulles sur certains arcs donnant des probabilités de sélection nulles, la seconde est que
dans certains cas, les probabilités de sélection sont identiques pour tous les arcs partant de
nœud courant .
+ } + ~
= arg L ( E O1
F . EtO F ), , ! ∈ ” P
• •
O‹( O‹(
Cette première règle permet de choisir le nœud suivant formant un arc avec les meilleures
combinaisons possible de la visibilité et des traces. Cette combinaison est calculée pour
disponibles. Dans cette expression, les traces de phéromones associées à chaque critère U
tous les arcs accessibles à partir de nœud courant et pour tous les modes de transport
} ~
Í Î∏+O‹(E O1
F Ï . Î∏+O‹(EtO F Ï
• •
C , ! ∈ ” P B
{ =
¥1 } ~
Ì∑ ∈ [ Î∏O‹(E F Ï . Î∏+O‹(EtO F Ï
+ O1 • •
Ê 0 C 9y9
La règle de transition ici est la probabilité d’aller de vers en utilisant le moyen de
transport •, cette probabilité est donc calculée pour tous les modes de transport disponible
sélectionné et ajouté à U C N¥ .
et pour tous les arcs. Parmi les nœuds candidats, celui ayant la plus grande probabilité sera
90
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
} ~
Règle 3 : Si Î∏+O‹(E F Ï . Î∏+O‹(EtO F Ï = 0 ou { =0
O1 • • ¥1
•
Cette dernière règle est la nouvelle règle ; elle indique que tous les arcs ont la même
probabilité d’être sélectionnés. Cela est dû au fait que les valeurs associées aux critères
L’utilisation de l’une ou l’autre de ces règles dépend des valeurs de §Œ et ’L9q, et des
contraintes de transbordement. L’algorithme est répété pour toutes les fourmis n’ayant pas
Comme évoquées précédemment, les contraintes de fenêtres temporelles induisent deux sens
de parcours du graphe :
Sens de parcours ( → ) : Dans ce cas, les fenêtres temporelles sont prises en compte
et l’heure d’arrivée au nœud destination Ul1 est fixée à l’avance. La fourmi doit donc
•
̌H1P de sorte à arriver avant l’heure d’arrivée au plus tard au nœud destination Ul1 . La
parcourir le réseau en sens inverse afin de déterminer l’heure de départ du nœud source
fourmi réalise un compte à rebours en soustrayant les temps de transport et les durées
de transbordements à chaque fois qu’elle sélectionne un nœud. Ce rebours part du
nœud destination et s’effectue à chaque étape de la construction jusqu’à atteindre le
nœud source. Le chemin trouvé est ensuite reconstruit en prenant les nœuds de la
source vers la destination ; les heures de départ trouvées à chaque nœud dans le
parcours → deviennent les heures d’arrivée et inversement pour les heures
d’arrivée.
91
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
À chaque itération, les vecteurs objectifs sont calculés pour les chemins trouvés par les
fourmis. Ces chemins sont évalués suivant deux stratégies : une stratégie dite « Pareto » et
une stratégie dite du « Gradient ».
Les solutions sont évaluées les unes par rapport aux autres en utilisant des tests de
dominance ; ces tests de dominance sont réalisés en comparant les vecteurs objectifs des
chemins. Ayant sept critères, les solutions sont évaluées en prenant les critères soit par paires,
par triplets... ou en évaluant tous les sept critères simultanément. Pour ce faire, nous nous
basons sur les « préférences » du décideur. En fonction du scénario choisi, le tableau ci-
dessous (Tableau 6) donne les préférences possibles :
Quelle que soit la préférence du décideur, nous optimisons simultanément les sept
critères. Le fait de prendre les critères par deux ou trois... permet au décideur de donner
la priorité à certains par rapport à d’autres, ce qui va permettre d’intensifier les traces
de phéromones sur les chemins ayant les meilleures solutions pour ces critères. De plus,
les sept critères interviennent simultanément dans la règle de transition et donc dans la
construction des solutions.
Soit #_ l’ensemble des solutions non-dominées, .H,l l’ensemble des solutions obtenues par
les fourmis de l’itération courante et . l’ensemble des solutions dominées. Chacune des
solutions obtenues est comparée avec celles appartenant au front de Pareto #_ , les solutions
dominées sont extraites du front de Pareto et les solutions non-dominées sont ajoutées au front
de Pareto, mettant ainsi à jour la frontière entre les solutions dominées et non-dominées.
l’archive Pareto #_ ; les solutions dominées par au moins une des nouvelles solutions sont
Chaque nouvelle solution obtenue est comparée avec toutes les solutions contenues dans
extraites du front de Pareto, les solutions de .H,l qui dominent au moins une des solutions du
front sont ajoutées au front de Pareto.
92
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
Dans cette stratégie, les sept critères sont évalués simultanément suivant les deux scénarios
¹NC Hå_¥èì de toutes les itérations. Une agrégation est effectuée en pondérant chaque critère
évoqués précédemment. Cette stratégie a pour objectif de maintenir la meilleure solution
sur chacun des arcs des chemins trouvés, nous obtenons une évaluation D¥ ( GHl ) du chemin
GHl étudié.
+
D¥ ( GHl ) = e =O D O (GHl )
O‹Œ
D¥ ( GHl ) est le « coût » du chemin trouvé par la fourmi ' et =O est le poids du critère U défini de
solution de l’itération courante est comparée à ¹NC Hå_¥èì ; elle remplace ¹NC Hå_¥èì si elle
la même manière que pour les règles de transition avec la méthode AHP. La meilleure
Pour f=0 à #¥
Pour chaque itération
Calculer D¥ ( GHl )
Si (D¥ ( GHl ) < ¹NC Hå_¥èì )
¹NC Hå_¥èì ← D¥ ( GHl )
La mise à jour des traces de phéromones comporte deux parties essentielles : l’évaporation et
l’amplification qui sont appliquées simultanément. Pendant la phase d’évaporation, les traces
de phéromones sont réduites suivant un pourcentage ou une probabilité donnée. La phase
d’amplification consiste à renforcer les traces de phéromones sur les meilleures solutions de la
même manière que dans la nature. L’évaporation a pour but d’éviter une convergence trop
rapide de l’algorithme et de favoriser la diversification dans la recherche des solutions ; ainsi
donc, les phéromones s’évaporent et les fourmis entretiennent la concentration des meilleures
traces en empruntant le même chemin un grand nombre de fois. Les mises à jour s’effectuent
à la fois localement et globalement.
Les mises à jour locales sont effectuées pendant la phase de construction des solutions. À
chaque fois qu’une fourmi sélectionne un arc, les traces de phéromones sur celui-ci sont mises
à jour. Cette mise à jour a pour objectif de renforcer ainsi les traces de phéromones sur ledit
arc afin de permettre aux fourmis d’emprunter les arcs les plus prometteurs. Elle est définie
comme suit :
93
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
← (1 − ¦) + ¦. Œ
Œ est la valeur initiale des traces de phéromones, ¦ est le taux d’évaporation locale des traces
et est la quantité de phéromones précédemment présente sur l’arc ( , ).
La mise à jour globale est effectuée à la fin de chaque itération ; la difficulté ici réside dans le
choix de la fourmi qui opèrera cette mise à jour. Dans le cas de MOSPACO, la matrice des
gradient, la meilleure fourmi ¹NC Hå_¥èì est utilisée pour la mise à jour. Dans une stratégie
traces est mise à jour par la meilleure fourmi de l’itération. Dans le cas d’une stratégie du
Pareto, nous considérons que toutes les fourmis appartenant au front de Pareto sont habilitées
à effectuer des mises à jour globales ; la fourmi effectuant la mise à jour est donc choisie
aléatoirement parmi celles qui appartiennent au front de Pareto. La mise à jour globale
renforce les traces de phéromone du meilleur chemin de l’itération. Ce meilleur chemin
indique généralement le « plus court » chemin, dans notre cas le chemin avec un moindre
impact environnemental pour le scénario écologique ou le chemin à moindre coût et temps
pour le scénario industriel. Selon les préférences du décideur, les traces de phéromones
correspondant aux critères choisis par le décideur seront renforcées. La mise à jour est donc
spécifique en fonction des critères à optimiser, pour l’optimisation coût/temps par exemple,
les matrices de phéromones correspondant à ces deux critères seront renforcées.
Le mécanisme de mise à jour globale est mis en place en rajoutant au chemin une quantité de
phéromones proportionnelle à la valeur du meilleur chemin obtenu (procédure élitiste). Cette
mise à jour est effectuée par l'équation suivante :
O1
← O1
+ ∆ O1
, U = 1. . . 9
∆ O1
est la quantité de phéromone déposée telle que :
∆ =
O1 ¾
î •E P YZÖ ( ) F
.
Dans cette formule, est le taux d’évaporation globale tel que ∈ 70,18. Si = 1, cela
signifie qu’il n’y a pas d’évaporation des traces et si = 0, les fourmis prennent en compte
uniquement la quantité de phéromones déposée lors du dernier cycle. Les valeurs que prend le
paramètre influencent le comportement des fourmis par rapport à cette dualité entre
diminuant la valeur du poids du facteur ‡ (de sorte que les fourmis deviennent moins
l’intensification et la diversification. La diversification peut aussi être augmentée soit en
sensibles aux traces de phéromones), soit en diminuant le taux d’évaporation de sorte que la
phéromone s’évapore plus doucement et les écarts d’une trace à l’autre évoluent plus
doucement.
Pour tester l’évolution du paramètre , nous fixons la valeur de ‡ et ensuite nous faisons
évoluer celle de pour tester l’influence de l’évolution du paramètre sur la dualité
intensification / diversification. Ces tests sont appliqués pour une valeur de allant de 0 à 0.1
94
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
avec un pas de 0.01 puis de 0.1 à 1 avec un pas de 0.1. Les fronts de Pareto obtenus pour
chacune de ces valeurs sont comparés les uns aux autres, de même une analyse de
convergence est réalisée pour chacune de ces configurations.
Pour des valeurs trop faible de , l’évaporation des traces est très importante, de ce fait nous
avons trop de diversification et l’intensification des bonnes solutions est faible ; le nombre de
solutions du front de Pareto est important, mais un grand pourcentage de solutions est dominé
par des solutions trouvées pour des valeurs de élevées. En effet, lorsque nous avons des
valeurs de proches de 1, l’évaporation des traces n’est pas importante et par conséquent le
phénomène d’intensification est très élevé ; au fur et à mesure que la valeur de tend vers 1,
le front de Pareto se renforce autour des mêmes solutions.
et la Figure 27. Nous constatons que pour = 0.5 (points de couleur moutarde) les solutions
Les fronts de Pareto pour des valeurs de allant de 0.01 à 0.5 sont présentés dans la Figure 26
dominent les solutions ayant un coefficient d’évaporation moins élevé ; par contre, les fronts
de Pareto correspondant à ces valeurs sont très diversifiés comme le montre la Figure 26.
valeur seuil = 0.4 ; c’est la valeur pour laquelle nous avons un équilibre acceptable entre la
intensification autour des solutions appartenant à ce front. Dans ce cas nous prendrons comme
95
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
Lorsque les traces de phéromones ne sont pas du tout utilisées, c’est-à-dire quand α=0 et ρ=0,
l’algorithme fonctionne comme un algorithme glouton, les solutions trouvées sont moins
bonnes que lorsque les traces de phéromones sont utilisées.
Ainsi, l’ensemble des paramètres doit être choisi de sorte que les fourmis se diversifient
autour des bonnes solutions. Lorsque nous augmentons ainsi la capacité exploratoire des
fourmis, nous trouvons généralement de meilleures solutions, mais en contrepartie ces
solutions sont plus longues à trouver et donc la convergence est plus lente. Dans la Figure 28,
nous étudions le seuil de convergence pour plusieurs configurations possibles de pour une
préférence coût/temps. Pour une valeur très faible (ρ=0,01), pour une valeur maximale (ρ=1)
et pour la valeur que nous avons choisi pour à l’issue de l’étude des fronts de Pareto
(ρ=0,4). Pour une valeur de très faible (ρ=0,01), nous avons une convergence très lente de
est très rapide (à partir de 20 itérations, ce qui traduit une trop grande intensification autour
une diversification apparait être celle utilisant = 0,4, ce qui vérifie les résultats obtenus par
des solutions optimales. La configuration qui donne une convergence moyenne et qui assure
96
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
Si C →
Placer toutes les fourmis au noeud C
U C N¥ ← C
Si → C
Sinon
U C N¥ ← C
Placer toutes les fourmis au nœud
Fin pour
Construction
U C N¥ ←
Choisir le nœud suivant une règle de transition
GHl ← U C N¥
Si toutes les fourmis arrivent au nœud destination
++
Itération ++.
97
Chapitre 3. MOSPACO-Un algorithme de colonie de fourmis pour le problème de plus court chemin
multiobjectif au sein des chaînes logistiques vertes
Conclusion
Nous avons construit deux sens de parcours du graphe de sorte à pouvoir tenir compte des
fenêtres temporelles. Nous avons également défini trois règles de transition en tenant compte
du nombre de moyens de transport que nous avons, de la particularité des critères et du
nombre de transbordements dans le graphe. Pour garantir un algorithme de colonie de fourmis
robuste et performant, permettant à la fois d’optimiser les meilleures solutions et de trouver
des solutions diverses dans l’espace de recherche nous avons mené des tests sur les différents
paramètres à utiliser.
Pour l’évaluation des solutions, nous avons opté pour une méthode d’agrégation (méthode du
gradient) et pour une méthode construisant les fronts de Pareto. Dans le chapitre suivant, nous
implémenterons l’algorithme développé ici afin d’analyser l’optimalité des solutions
obtenues.
98
Chapitre 4. Implémentation et résultats
Chapitre 4 Implémentation et
résultats
99
Chapitre 4. Implémentation et résultats
Introduction
Comme mentionné plus haut, notre objectif est de construire un système d’aide à la décision
pour le choix d’un itinéraire intermodal permettant d’optimiser simultanément un ensemble
de sept critères en donnant la préférence à ceux choisis par le décideur.
Nous avons construit une base de données constituée de fichiers textes permettant de stocker
toutes les informations dont nous avons besoin à la fois pour les critères, le graphe et
l’algorithme.
Carte Europe
100
Chapitre 4. Implémentation et résultats
Villes
Lien
101
Chapitre 4. Implémentation et résultats
• Dégâts
• Fenêtres temporelles
• Nuisances sonores
102
Chapitre 4. Implémentation et résultats
• Polluants
• Stockage :
• Transbordements :
103
Chapitre 4. Implémentation et résultats
L’outil développé comprend une interface principale composée de quatre onglets principaux :
« Fichier », « Édition », « Optimisation », « Affichage » (Figure 30).
L’onglet « Fichier » permet de charger le fichier contenant le réseau de transport sur lequel
l’on veut travailler. Dans cet onglet, nous choisissons également la base de données afin de
permettre une acquisition des données et une introduction des données dans le système.
L’onglet « Édition » permet d’ajouter automatiquement des villes dans la base de données en
indiquant le code du pays auquel elles appartiennent afin que l’application les associe à leur
zone géographique. Dans l’onglet « Optimisation », la partie « paramètres » permet à
l’utilisateur de saisir un certain nombre de paramètres indispensable à l’exécution de
l’algorithme ; la partie « ANT » quant à elle permet de déclencher l’exécution de l’algorithme
avec une possibilité d’arrêter l’exécution. L’onglet « Affichage » permet d’afficher la liste des
villes du réseau étudié en affichant pour chaque ville ses successeurs directs et la liste des
moyens de transport disponibles. La partie cartographie de cet onglet permet l’affichage du
réseau de transport étudié avec toutes les liaisons existantes (Figure 31), ainsi que les chemins
trouvés en exécutant l’algorithme et les valeurs des différents critères pour ces chemins. La
partie « Arbre de Données » est une hiérarchie de toutes les données utilisées dans
l’application (graphe, coordonnées géographiques…). La partie « Graphiques » de cet onglet
104
Chapitre 4. Implémentation et résultats
permet d’afficher les courbes correspondant aux solutions obtenues ; elle affiche les fronts de
Pareto pour toute préférence du décideur.
1.3 La cartographie
La première étape est la construction de réseau de transport. Pour cela nous avons construit un
réseau de transport intermodal en utilisant la carte de l’Europe. Les villes sont localisées en
utilisant des données géographiques réelles notamment la longitude et la latitude ; chaque
ville appartient à une zone géographique. En effet, les paramètres utilisés dans l’application
dépendent de la zone géographique dans laquelle se déroule le transport ; la consommation
d’énergie et les émissions de gaz à effet de serre dépendent du type de combustible utilisé
pour le transport ; par exemple, plus la part du nucléaire est élevée dans la production
d’électricité motrice pour les trains, moins les émissions globales de CO2 produites par le
transport combiné sont importantes. Ainsi, une unité d’électricité pour les chemins de fer
tchèques (produite principalement par des centrales alimentées par du combustible fossile)
produit des émissions de CO2 plus de 12 fois supérieures à celles de la même unité utilisée par
les chemins de fer français (plus de 80% de l’électricité française étant produite par des
centrales nucléaires) (IFEU, 2002).
Par la suite, les moyens de transport reliant les villes les unes aux autres sont construits en
utilisant Google Maps, les cartes routières et ferroviaires européennes, les données de la
SNCF ainsi que les données sur les voies aériennes et maritimes en Europe. Ces données ont
permis de construire le réseau routier présenté sur la Figure 32.
105
Chapitre 4. Implémentation et résultats
La Figure 33 ci-dessous représente le réseau ferroviaire reliant l’ensemble de nos 100 villes.
En analysant le réseau, nous nous rendons compte que toutes les villes possédant un accès par
le train possèdent également une route facilitant ainsi le ferroutage et le transport combiné
rail-route à la différence que les distances de parcours ne sont pas identiques.
106
Chapitre 4. Implémentation et résultats
Le réseau maritime est présenté dans la Figure 34 ; toute ville possédant un port est accessible
à partir de toute autre ville portuaire ; du moment où elle a un port, elle peut recevoir des
bateaux venant de partout. Le réseau aérien est également construit en se basant sur le même
principe ; il n’est pas présenté ici du fait de sa densité.
2. L’interface utilisateur
Une interface a été mise en place de sorte que le système d’aide à la décision prenne en
compte les besoins de l’utilisateur. L’utilisateur (décideur ou autre) doit fixer un certain
nombre de paramètres intrinsèque au modèle ; ces paramètres sont ceux définis pour
l’algorithme de colonies de fourmis, mais également ceux relatifs aux critères. Le module
dédié à cet objectif est appelé « paramètres » et comprend quatre parties à savoir :
• Les données globales du problème : Cette fenêtre (Figure 35) permet de saisir les
données propres au problème de transport tel que la quantité de marchandises
transportée, le volume, le nombre d’unités à transporter (nombre de container, de
cartons, ou de produits vrac...) et le nombre de transbordements autorisés. Elle permet
également de spécifier la ville de départ et la ville destination qui sont à choisir dans
une liste déroulante contenant toutes les villes du réseau stockées dans la base de
données. Dans cette partie le décideur spécifie également l’heure d’arrivée au nœud
destination (si nous sommes dans le sens t→s) ou l’heure de départ souhaitée au nœud
source (si nous sommes dans un sens de parcours s→t).
107
Chapitre 4. Implémentation et résultats
• Choix des critères à optimiser : En fonction du scénario choisi par l’utilisateur, il peut
dans cette partie entrer ses préférences. Le décideur choisit entre la stratégie gradient
ou la stratégie Pareto (Figure 37). Si la stratégie Pareto est sélectionnée, il pourra
ensuite choisir la combinaison de critères qu’il souhaite privilégier. La case
« Praticité » permet de choisir si l’on prend en compte la contrainte de praticité ou non.
3. Implémentation et résultats
Afin de valider le modèle théorique, une implémentation est réalisée en utilisant Visual C# sur
un ordinateur ayant les configurations suivantes : Windows 7-64 bits, Pentium (R) Dual-Core
CPU T4300, 2.10 GHz, RAM 4 Go. Pour exécuter l’algorithme, nous avons choisi les
données d’entrée suivantes en fonction des tests qui ont été réalisés sur les différents
paramètres de l’algorithme :
• Paramètres MOSPACO : χ=0.1, #¥ =100, et 9lì =10, q0=0.4, α=2, β=1. Compte
tenu des tests réalisés sur le paramètre , sa valeur est fixée en fonction des critères de
préférence du décideur.
À la fin de chaque essai, les vecteurs objectifs des chemins trouvés par les fourmis non-
perdues sont calculés. Les valeurs obtenues pour chacun des critères sont fonction des valeurs
associées aux différents paramètres de ces critères dans notre base de données. Les solutions
109
Chapitre 4. Implémentation et résultats
obtenues sont comparées les unes aux autres afin de construire les fronts de Pareto, dans le cas
d’une stratégie Pareto. Dans ce cas, les solutions non-dominées seront analysées en comparant
les solutions les unes aux autres en se basant sur les préférences du décideur. Pour toutes les
préférences, les tests sont réalisés en présence de la contrainte de praticité ; pour mieux
visualiser l’effet de la contrainte de praticité, nous effectuerons des tests avec et sans praticité
sur le coût de transport. Pour une stratégie gradient, la meilleure solution obtenue est
analysée.
Pour ce scénario, nous étudierons l’habilité de l’algorithme à trouver des chemins éco-
efficients. Nous évaluerons les quantités de gaz à effet de serre des chemins obtenus et les
gains en termes de consommation d’énergie, lorsque l’on compare les solutions les unes aux
autres. L’impact environnemental et sociétal des chemins obtenus sera également évalué.
• Pollution-Énergie = 0,1 :
est obtenu pour une valeur de = 0,1. En utilisant cette valeur pour l’exécution de
Pour une préférence axée sur ces deux critères, le compromis diversification/intensification
l’algorithme, nous obtenons comme solution non dominée le point présenté sur la Figure 39.
Sur cette figure le front de Pareto comporte un seul point ; cela est dû au fait que l’espace des
solutions a une forme d’entonnoir. Ceci s’explique d’une part par le fait que pour de courtes
distances (solutions proches du front de Pareto), nous avons un rapport de proportionnalité
entre les émissions de gaz à effet de serre et la consommation d’énergie. Par ailleurs, notons
que les émissions de CO2 (prépondérantes parmi les gaz étudiés) sont proportionnelles à la
consommation d’énergie primaire parce que les émissions de ces gaz sont liées au type de
combustible fossile utilisé, et donc au type d’énergie et cela en général quelque soit le mode
de transport utilisé. Cette proportionnalité n’est pas vérifiée pour l’énergie électrique.
Cependant, nous considérons la somme d’un ensemble de gaz à effet de serre, moins
importants que le CO2 tels que les NOx et les SOx qui ne sont pas uniquement liés au type de
combustible utilisé, mais également au mode de combustion et à la qualité de la combustion ;
ils influencent donc ce rapport de proportionnalité lorsqu’on utilise des modes transport ou
qu’on empreinte des itinéraires donnant un fort taux d’émission de ces gaz.
Amsterdam→train→Louvain→train→Bruxelles→train→Luxembourg→train→
Metz→train→Nancy→train→Lyon→train→Aix-en-Provence→train→
Marseille→bateau→Barcelone
Le vecteur objectif de ce chemin donne : bruit moyen 111 dBA, pollution 103 kg, risque
d’accident 0, consommation d’énergie 2, 3 GJ, coût de transport 283528 €, dégâts 1 kg, temps
de transport 1183,5 minutes.
110
Chapitre 4. Implémentation et résultats
Dans notre étude, nous considérons que les trains utilisés sont électriques en Europe de
l’Ouest ; les villes présentes dans cet itinéraire étant en Europe de l’Ouest, le moyen de
transport privilégié en termes d’émission de gaz à effet de serre et de consommation d’énergie
minimale sera donc le train. Concernant la liaison (Marseille-Barcelone), à partir de Marseille
les modes de transport en direction de Barcelone étaient le train via Montpellier (pollution
36,29 kg et énergie 0,504 GJ), l’avion (pollution 825 kg et énergie 8,61 GJ), le bateau
(pollution 31,57 kg et énergie 0,686 GJ). Dans le cas où les solutions sont incomparables sur
les deux critères, l’algorithme va privilégier celle ayant un taux de pollution minimal à cause
du poids plus élevé accordé à ce critère pour la règle de transition. De plus, la différence en
termes de consommation d’énergie entre les alternatives utilisant le train via Montpellier et le
bateau est très faible. Le meilleur compromis possible est donc le bateau pour cet itinéraire.
• Pollution-Bruit = 0,3 :
Dans ce cas, la valeur retenue est = 0,3. Pour un décideur qui choisit de retenir les solutions
Pareto-optimales basées sur ces deux critères, l’ensemble des solutions non-dominées
trouvées est présenté sur la Figure 40.
Ces solutions peuvent être subdivisées en deux cas. Le premier correspond aux chemins qui
d’une part ont des émissions de gaz à effet de serre très faibles, mais des nuisances sonores
assez élevées ; dans ce cas la priorité est donnée aux solutions ayant une pollution très basse,
mais qui ne dégradent pas énormément la fonction bruit, donc dans notre cas c’est le train. En
effet, cela s’explique par le fait que le poids du critère pollution obtenu par la méthode AHP
plus élevé que celui des nuisances sonores, ces poids intervenants dans les règles de
transition, les fourmis choisiront dans une moindre mesure les solutions ayant une pollution
minimale, mais ne dégradant pas énormément le critère nuisances sonores. Un des chemins
correspondant à ce cas est :
Amsterdam→bateau→Rotterdam→bateau→Le Havre→train→Paris→train→
Montpellier→train→Marseille→ bateau →Barcelone
avec comme vecteur objectif : bruit 19 dBA, consommation d'énergie 3,3 GJ, quantité de
polluants 144 kg, risque d'accident 0, coût 177169 €, dégâts 2,5 kg, temps 2095,2 minutes.
111
Chapitre 4. Implémentation et résultats
Le second cas est celui des solutions ayant un taux de bruit égal à zéro, ces dernières font
partie du front de Pareto et représentent des chemins utilisant soit le bateau ; ce dernier a un
impact sonore quasi nul. Les solutions étant incomparables sur le critère nuisances sonore, le
décideur choisira donc celles qui dégradent le moins la fonction pollution. Un des chemins
ayant une quantité de gaz à effet de serre minimal consiste à aller d’Amsterdam à Barcelone
en utilisant le bateau :
Amsterdam→bateau→Barcelone
avec les performances suivantes : Bruit 0 dBA, consommation d'énergie 7.87 GJ, quantité de
polluants 358 kg, risque d'accident 0, coût 43283 €, dégâts 0, temps 5943 minutes. En
comparant cette solution à la précédente, nous constatons qu’en matière de nuisance sonore
elle est meilleure, cependant le taux de pollution est supérieur au chemin alliant train et
bateau, à cause notamment du temps de transport qui est plus long (quasiment le double) en
utilisant uniquement le bateau. Dans ce cas les autres critères (temps de transport, coût,
dégâts) peuvent également servir de base au choix final du décideur.
• Pollution-Accident = 0,5
L’objectif ici est de trouver l’ensemble des chemins les moins accidentogènes possible tout en
garantissant des émissions de gaz à effet de serre minimales. Dans la Figure 41, le front de
Pareto obtenu est une droite, en effet les solutions ayant un risque moyen d’accident égal à
zéro sont retenues ; ces solutions sont celles qui utilisent un mode transport autre que la
route ; le taux d’accidentologie associé aux autres modes de transport est très négligeable. Les
solutions étant incomparables du point de vue du risque d’accident, nous allons privilégier
pour la décision finale les solutions ayant une quantité de pollution la plus minimale possible.
Le chemin ayant un risque d’accident égal à zéro et la quantité de polluants la moins élevée
est :
112
Chapitre 4. Implémentation et résultats
Avec les performances suivantes : Bruit 0 dBA, consommation d'énergie 7.87 GJ, quantité de
polluants 358 kg, risque d'accident 0, coût 43283 €, dégâts 0, temps 5943 minutes. Une autre
alternative est :
Amsterdam→train→Rotterdam→bateau→Nice→train→Aix-en-Provence→
train→Marseille→bateau→Barcelone
et les valeurs des critères pour ce chemin sont : bruit 219 dBA, consommation d’énergie 9.87
GJ, gaz à effet de serre 451 kg, risque d’accident 0, coût 169041 €, dégâts 2,5 kg, temps de
transport 7341 minutes. Comme dans le cas (pollution/bruit) la décision finale du décideur
pourra se faire en tenant compte des valeurs des critères autres que la pollution et le risque
d’accident.
• Énergie-Bruit = 0,2
Le front de Pareto obtenu est présenté dans la Figure 42. Le nombre de solutions évaluées
s’élève à 17000, avec un taux de fourmis perdues de 0%. Les solutions appartenant au front
de Pareto sont celles ayant une quantité de bruit très faible ou égale à zéro. Les chemins ayant
une quantité de bruit élevée sont ceux qui utilisent soit le train ou le camion, ou une
combinaison des deux. L’un de ces chemins est :
Amsterdam→bateau→Lisbonne→train→Séville→
camion→Getafe→camion→Madrid→train→Barcelone
avec bruit 6,2 dBA, consommation d'énergie 7 GJ, quantité de polluants 382 kg, risque
d'accident 0,4 ; coût 137426 €, dégâts 4 kg, temps 4196,4 minutes. Le train est utilisé sur une
partie du tronçon (Madrid-Barcelone) et le camion entre Séville et Madrid ; ce qui permet
d’avoir une solution donnant un bruit non nul, mais en garantissant une consommation
d’énergie de 7 GJ. Pour cette alternative, le risque d’accident est différent de zéro à cause de
l’utilisation du camion de Séville à Madrid ; les dégâts dus aux transbordements sont non-nuls
à cause du nombre de transbordements (3 transbordements).
113
Chapitre 4. Implémentation et résultats
Les alternatives ayant des nuisances sonores égales à zéro correspondent aux combinaisons
n’utilisant ni le train, ni le camion. Une des alternatives correspondant à ce cas est :
Amsterdam→bateau→Marseille→bateau→Barcelone
avec bruit 0 dBA, consommation d'énergie 9,3 GJ et quantité de polluants 430 kg, risque
d'accident 0, coût 71779 €, dégâts 0 kg, temps 7048,5 minutes. Nous constatons donc que
l’ensemble des solutions trouvé représente un compromis acceptable pour ces deux critères.
• Accident-Bruit = 0,3
Pour une préférence accident bruit, le meilleur compromis possible c’est d’avoir un risque
d’accident et un bruit égal à zéro (Figure 43), donc l’usage du bateau. L’itinéraire trouvé par
les fourmis correspondant à ce compromis est :
avec les performances suivantes : Bruit 0 dBA, consommation d'énergie 7.87 GJ, quantité de
polluants 358 kg, risque d'accident 0, coût 43283 €, dégâts 0, temps 5943 minutes. Les autres
solutions du front de front de Pareto sont celles ayant un risque d’accident égal à zéro ; le
choix final du décideur sera donc basé sur la quantité moyenne de bruit émis.
114
Chapitre 4. Implémentation et résultats
• Énergie-Accident : = 0,1
Le front de Pareto est une droite avec un risque d’accident égal à zéro et une consommation
d’énergie variable (Figure 44). Le choix final du décideur se basé sur la consommation
d’énergie correspondant aux itinéraires proposés.
• Pollution-Énergie-Bruit : = 0,4
Amsterdam→train→Rotterdam→bateau→Barcelone
Avec bruit 4 dBA, consommation d'énergie 7.94 GJ, quantité de polluants 365 kg, risque
d'accident 0, coût 74926 €, dégâts 1 kg, temps 5966,1 minutes. Les solutions non-dominées
sont meilleures que les autres sur au moins deux critères.
115
Chapitre 4. Implémentation et résultats
Amsterdam→train→Rotterdam→train→Eindhoven→train→Liège→train→
Bruxelles→train→Lille→avion→Turin→train→Nice→train→
Aix-en-Provence→train→Marseille→bateau→Barcelone
avec les performances : bruit 160 dBA, consommation d'énergie 19.4 GJ, quantité de
polluants 1.57 tonne, risque d'accident 0, coût 333888 €, dégâts 1 kg, temps 1030,5 minutes. Il
est évident que ce chemin est moins avantageux que le précédent en termes de pollution, de
nuisances sonores et de consommation d’énergie. Cependant en termes de temps de transport
il parait intéressant, à cause de l’utilisation du bateau sur le premier chemin.
• Pollution-Énergie-Bruit-Accident = 0,3 :
Amsterdam→train→Rotterdam→train→Eindhoven→train→
Liège→train→Luxembourg→train→Sarrebruck→train→
Metz→train→Nancy→train→Lyon→train→
Aix-en-Provence→train→Marseille→bateau→Barcelone
Nous avons : bruit 128 dBA, consommation d'énergie 2,3 GJ, quantité de polluants 108 kg,
risque d'accident 0, cout 342757 €, dégâts 4, temps 1214,1 minutes.
116
Chapitre 4. Implémentation et résultats
• Coût-Temps = 0,4
Pour une préférence sur ces deux critères, nous analyserons les solutions en termes de
compromis entre le coût et le temps. De plus, nous analyserons l’effet de la contrainte de
praticité sur le coût de transport.
Amsterdam→avion→Barcelone
Les performances associées à ce chemin sont : bruit 60 dBA, consommation d'énergie 32 GJ,
quantité de gaz à effet de serre 2,8 tonnes, risque d'accident 0, coût 115989 €, dégâts 0, temps
110,4 minutes ; pour ce chemin les quantités de gaz effet de serre sont très élevées, par contre
en terme de temps de transport cette alternative est plus avantageuse que le bateau ou le train.
Une autre alternative est la combinaison route-avion, cette alternative permet d’associer le
faible coût dû à l’utilisation du camion sur de courtes distances et le gain de temps par l’usage
de l’avion :
Amsterdam→avion→Montpellier→camion→Barcelone
117
Chapitre 4. Implémentation et résultats
Nous effectuons donc un autre test avec et sans praticité, mais en utilisant 200 tonnes de
marchandises. Les fronts de Pareto obtenus sont présentés sur la Figure 47, les points en rouge
sont ceux obtenus sans contrainte de praticité et les points en bleu sont ceux utilisant la
praticité. Le premier constat est que le coût maximal en utilisant la praticité est nettement
supérieur à celui sans la praticité. La quantité de marchandise étant très grande, les modes de
transport à petite et moyenne capacité tels que l’avion ou le camion seront frottement
pénalisés tandis que le bateau et le train seront privilégiés. Pour le cas de l’avion, la pénalité
est appliquée pour une quantité de marchandise dépassant 120 tonnes, il apparait donc que
pour 200 tonnes de marchandises ce mode de transport ne sera pas très pénalisé et donc
restera une alternative viable. En effet un des chemins obtenus en appliquant la contrainte de
praticité pour ce cas est :
Amsterdam→avion→Montpellier→train→Barcelone
avec bruit 6 dBA, consommation d'Énergie 25,301 GJ, quantité de polluants 2,1 tonnes, risque
d'accident 0, cout 97122 €, dégâts 1,5 kg et temps 252,94 minutes.
L’ensemble des chemins obtenus pour les deux cas est présenté dans l’annexe 3 ; le mode
routier est écarté de l’ensemble des solutions ; de plus en comparant les mêmes itinéraires
avec et sans praticité, nous remarquons que l’alternative soumise à la contrainte de praticité
est pénalisée et donc coûte plus cher.
Figure 47. Comparaison des fronts de Pareto Coût/Temps avec praticité (points
bleus/étoiles) et sans praticité (points rouges/triangles)
118
Chapitre 4. Implémentation et résultats
Figure 48. Comparaison des fronts de Pareto Coût/Temps avec (points bleus/étoiles) et sans
praticité (points rouges/triangles)
• Coût-Dégâts = 0,2
Dans ce cas, les solutions privilégiées seront celles ayant une quantité de dégâts très faibles
(peu de transbordements) ou nuls (aucun transbordement). Le front de Pareto obtenu pour la
préférence Coût/Dégâts montre une droite avec des dégâts nuls (Figure 49), ce qui indique
que les chemins choisis sont ceux n’utilisant aucun transbordement, par exemple :
Amsterdam→bateau→Rotterdam→bateau→Barcelone
• Temps-Dégâts = 0,3
Comme dans le cas précédent, les solutions privilégiées seront celles ayant une quantité de
dégâts très faibles (peu de transbordements) ou nuls (aucun transbordement). Le front de
Pareto (Figure 50) indique qu’il y a eu au moins un transbordement. La quantité de dégâts
occasionnée varie selon la nature et le nombre de transbordements réalisés. Ici la quantité de
dégâts enregistrée est de 1,5 kg ce qui correspond au chemin suivant :
119
Chapitre 4. Implémentation et résultats
Amsterdam→avion→Montpellier→train→Barcelone.
Une série de tests est réalisée pour le cas d’un transport de 50 tonnes de marchandises entre
Saint-Pétersbourg et Séville. Le Tableau 7 synthétise les résultats obtenus pour différentes
préférences du décideur ; les chemins les plus intéressants du point de vue de l’itinéraire
trouvé et des valeurs trouvées pour les différents critères seront présentés.
En analysant ces résultats, nous constatons que les chemins utilisant le train (arcs verts) sur
une grande distance ont une quantité de bruit élevée tandis que ceux utilisant le bateau ont des
nuisances sonores quasi nulles. Par ailleurs, fort est de constater que les solutions utilisant
l’avion (arcs noirs) sont intéressantes uniquement sur le plan du temps de transport, les
quantités de gaz à effet de serre et la consommation d’énergie étant très élevées pour ces
solutions, cela conduit à la conclusion qu’en l’absence de contraintes temporelles, il est
préférable d’éviter ce mode de transport (si les solutions alternatives respectent les contraintes
de praticité). Les itinéraires utilisant le bateau (arc bleu) ont un temps de transport
considérable, cependant elles restent intéressantes du point de vue écologique et sociétal. Les
solutions utilisant le camion (arc rouge) sont celles optimisant le coût de transport.
Pour les préférences où l’on a une multitude de solutions, représentant souvent celles ayant
des ordonnées nulles (front de Pareto sous forme de droites), on ne considèrera que les 10
premières solutions c’est-à-dire celles qui donnent un meilleur résultat pour les critères non
nul (les abscisses) ; par exemple pour une préférence pollution/accident, on ne considèrera
que les 10 meilleures solutions pour la pollution. Le tableau permet de se rendre compte des
variations de solutions d’une préférence à l’autre.
120
Chapitre 4. Implémentation et résultats
121
Chapitre 4. Implémentation et résultats
122
Chapitre 4. Implémentation et résultats
123
Chapitre 4. Implémentation et résultats
124
Chapitre 4. Implémentation et résultats
125
Chapitre 4. Implémentation et résultats
126
Chapitre 4. Implémentation et résultats
127
Chapitre 4. Implémentation et résultats
Le résultat obtenu pour les deux scénarios est présenté dans la Figure 51. La meilleure
alternative trouvée pour un meilleur compromis entre les sept critères à la fois pour le
scénario industriel et le scénario écologique est d’aller directement d’Amsterdam à Barcelone
en utilisant le bateau. L’itinéraire trouvé est
Avec bruit 0 dBA, consommation d’énergie 7.9 GJ, pollution 358 kg, risque d’accident 0,
coût 43283 €, dégâts 0 kg, temps 5943 minutes.
Cette alternative présente clairement des avantages en termes d'émissions de gaz à effet de
serre, de risques d'accident et d'émission de bruit. Pour cette stratégie, le meilleur compromis
est le bateau. Ceci peut être expliqué par le fait que le bateau a moins d'impacts sur
l'environnement et la société. Par ailleurs, la capacité du bateau est très importante, permettant
ainsi de réduire les pénalités et donc le coût total du transport. Néanmoins, le temps de
transport lié au bateau à reste toujours élevé.
L’analyse des performances d’un algorithme multiobjectif n’est pas une tâche facile. Dans le
cas de l’optimisation mono-objectif, la qualité de l’algorithme peut être facilement évaluée
selon la valeur optimale obtenue selon qu’il s’agisse d’un optimum local ou d’un optimum
global. Dans le cas où un front de Pareto est construit, il est difficile d’en évaluer l’optimalité,
dans le sens où les solutions obtenues sont multiples et toutes potentiellement intéressantes.
Quelques approches de mesures des performances d’un front de Pareto ont été proposées dans
128
Chapitre 4. Implémentation et résultats
Pour ce faire, nous utiliserons l’entropie de Shannon (Shannon, 1948) pour mesurer la
distribution de la règle de transition aux différents nœuds. L’entropie de Shannon est une
mesure de l’incertitude liée à un système aléatoire. Plus l’entropie est faible, plus l’incertitude
l’est aussi. Au début de l’algorithme, les traces de phéromones sont égales sur tous les arcs, le
Figure 53). Nous définissons une entropie de sélection du nœud $ 1 définie pour chaque nœud
choix des fourmis est donc aléatoire ; ce qui s’explique par une entropie élevée (Figure 52 et
$1 = − e {
¥1 ¥1
ln {
∈![
Par la suite, nous calculons l’entropie moyenne $Û pour toutes les valeurs de la probabilité de
transition. Les résultats obtenus au bout des 100 itérations pour les préférences Énergie/Bruit
et Coût/Temps sont présentés respectivement sur les figures 53 et 54 ; ces figures montrent
l’évolution de l’entropie moyenne au fil des itérations
129
Chapitre 4. Implémentation et résultats
La valeur de $Û tend vers 0.5x10-4 environ pour les deux préférences. Nous constatons que plus
le nombre d’itération augmente plus la fonction d’entropie se stabilise. Dans le cas
Énergie/Bruit la stabilisation est constatée au bout de 45 itérations et au bout de 30 itérations
pour Coût/Temps.
Cela signifie que l’évolution de l’algorithme devient mature ; le chemin non-dominé ayant la
plus grande probabilité de sélection se démarque et les probabilités de sélection deviennent
stables. L’algorithme MOSPACO converge donc vers une solution correspondant dans
chaque cas au chemin dominant, sur lequel les traces de phéromones sont renforcées. Le
renforcement des traces de phéromones sur les chemins non-dominés est ainsi prouvé. Au
début de l’exécution (itérations 1-20), l’entropie moyenne est variable, ce qui traduit un choix
pseudo-aléatoire, voire aléatoire effectué par les fourmis. Au fur et à mesure que le nombre
d’itérations augmente, les chemins choisis par les fourmis sont de plus en plus les mêmes, et
les probabilités de sélection des dits-chemins augmentent. La séquence d’entropie est
convergente, ce qui prouve que la probabilité de choisir les chemins non-dominées augmente
au fil des itérations. Cette étude permet ainsi de démontrer que les fourmis de la colonie
convergent vers les mêmes solutions et suivent les pistes de phéromones.
La convergence obtenue pour chaque préférence a été réalisée en utilisant une valeur de ρ
garantissant une convergence optimale de l’algorithme pour chaque cas.
En statistiques, la robustesse est définie comme étant la capacité d’un estimateur à ne pas être
modifié par une petite modification dans les données ou dans les paramètres du modèle choisi
pour l'estimation. En ingénierie, la robustesse d'un système se définit comme la « stabilité de
sa performance » tandis qu’en optimisation robuste, la robustesse concerne des situations où
différents scénarios sur les données sont considérés et où l’objectif est de déterminer une
solution qui reste “bonne” quel que soit le scénario considéré.
130
Chapitre 4. Implémentation et résultats
Dans notre cas, la robustesse est similaire à la définition en ingénierie ; c’est la capacité de
l’algorithme à avoir une performance stable et donc de trouver les meilleures solutions
possible (le meilleur front de Pareto), en l’exécutant plusieurs fois sous les mêmes contraintes
et la même configuration. Afin de mesurer la robustesse de MOSPACO, nous lançons une
série de 20 essais, puis nous calculerons les écarts-types et les moyennes des valeurs obtenues
à chaque lancement de l’algorithme. L’écart-type est un indicateur de dispersion de
l’algorithme.
Des analyses statistiques sur les données recueillies sont ensuite effectuées pour déterminer
l’écart-type et la moyenne des valeurs obtenues pour chaque série de tests. Dans les tableaux
8 et 9, nous présentons les résultats issus d’une série de tests réalisés pour les préférences
Coût/Temps et Énergie/Bruit.
• Énergie / Bruit
Les moyennes et les écart-type observés sont variables d’un lancement à l’autre. Nous
n’observons aucune tendance centrale. En effet pour chaque critère nous avons les valeurs
suivantes :
de ± 1.9488e + 004 .
131
Chapitre 4. Implémentation et résultats
Les écarts-types et les différences entre les moyennes sont très grands. Ces résultats
démontrent que pour ces deux critères, l’algorithme est fortement perturbé et les résultats
trouvés ne présentent aucune tendance ; ce qui signifie que la robustesse de l’algorithme pour
ces deux critères est très faible. Nous observons un manque de précision dans le
fonctionnement de l’algorithme. Cela est dû au fait que pour les critères bruit, accident et
dégâts les valeurs sont très souvent nulles, ce qui induit l’utilisation de la troisième règle de
transition qui est aléatoire. Une des conséquences de l’utilisation de cette règle est
l’augmentation du temps de convergence donc le temps de calcul. Pour atténuer le caractère
aléatoire de cette règle, nous pouvons par exemple hybrider l’algorithme avec une méthode de
voisinage qui choisira les solutions autour du front de Pareto.
• Coût/Temps
L’analyse de la robustesse de l’algorithme pour cette préférence est présentée dans le Tableau
9, les résultats donnent :
de ± 0.0855e + 004 .
Les résultats obtenus pour ces deux critères montrent en revanche un écart-type bien plus
faible. À chaque lancement, nous obtenons sensiblement les mêmes résultats, ce qui traduit
132
Chapitre 4. Implémentation et résultats
une robustesse et une précision de l’algorithme sur ces deux critères. Les moyennes obtenues
pour chaque critère ont le même ordre de grandeur ; ce qui traduit une bonne dispersion des
solutions sur le front de Pareto.
5. Conclusion
Les résultats trouvés par l’algorithme donnent les solutions représentant un compromis entre
les critères étudiés. Nos résultats démontrent qu’en fonction des préférences du décideur,
MOSPACO est capable de trouver un bon compromis de chemins possible.
La nature des fronts de Pareto obtenus dépend fortement des critères à optimiser. Les
solutions appartenant au front de Pareto sont compatibles avec les objectifs. En effet,
l'optimisation des critères écologiques privilégie les chemins avec des moyens de mode de
transport éco-efficients tels que le rail et le bateau, tandis que l’optimisation des critères
économiques privilégie les itinéraires utilisant des moyens de transport plutôt rapide (avion)
ou économique (train, camion), ou toute autre combinaison de mode de transport permettant
d’optimiser ces critères. Toutefois, les alternatives retenues dépendent fortement des données
de transports tels que la quantité de marchandises transportée et la distance entre le nœud
source et le nœud destination.
En comparant les solutions obtenues pour le scénario écologique et pour le scénario industriel
nous obtenons un gain en émission de gaz à effet de serre pouvant atteindre 2 tonnes d’une
alternative à l’autre, et une réduction de la consommation d’énergie de 23 GJ.
Cependant, pour certains critères, le nombre de solutions non-dominées est très élevé, rendant
difficile le choix final du décideur ; ceci est l’une des limites de l’approche Pareto. Pour
pallier à cette limite, dans notre approche le décideur peut visualiser pour chaque solution les
valeurs de tous les critères qui y sont associés.
Les résultats de la méthode du gradient représentent un compromis entre les sept critères
étudiés. Cependant, la stratégie du gradient empêche la diversification et ne laisse pas le choix
au décideur de privilégier un critère par rapport à un autre. Les solutions obtenues tendent
vers un optimum local.
133
Chapitre 4. Implémentation et résultats
Le temps total d’exécution de l’algorithme varie d’une préférence à l’autre ; cela est dû à la
différence de convergence d’une préférence à l’autre. Le temps d’exécution moyen pour 100
itérations en 10 essais est de 1 heure. Selon les préférences, nous avons par exemple 2,41 h
pour une préférence Bruit/Accident, 57 minutes pour Coût/Temps, 23 minutes pour la
méthode du gradient. Le temps mis par les meilleures fourmis pour trouver un chemin non-
dominé est de 53 secondes maximum.
134
Conclusion et perspectives
Conclusion et perspectives
135
Conclusion et perspectives
Cette dernière partie représente une synthèse du travail réalisé. Après avoir résumé les
différents apports scientifiques, nous aborderons aussi leurs limites, puis nous terminerons
par des perspectives de recherches qui s’ouvrent à l’issue de ces travaux.
Conclusion
La conjoncture économique actuelle et les prises de conscience environnementales obligent
les entreprises à reconsidérer l'organisation de leur chaîne logistique, dans le but de favoriser
les modes de transport respectueux de l'environnement et d’assurer une meilleure
coordination des flux afin de réduire les impacts environnementaux et sociétaux.
C’est dans cette optique que nous avons mis en place un modèle du plus court chemin
multiobjectif ayant pour objectif d’aider au choix d’un « plus court chemin » dans un réseau
intermodal. Dans notre cas, « plus court chemin » signifie un chemin avec moins d'impacts
environnementaux et sociétaux et garantissant des critères économiques (coût, temps, dégâts)
satisfaisants. Nous avons ainsi fourni un système d’aide à la décision pour les décideurs
politiques ou les opérateurs logistiques qui souhaitent réduire leurs impacts sur
l'environnement lors du choix d’itinéraire et pour la planification de leurs expéditions. Le
système permet de se baser sur un certain nombre de données d’entrée (quantités de
marchandises, réseau de transport…) pour fournir un itinéraire répondant aux exigences du
décideur.
L’application présentée peut être utilisée pour évaluer et calculer les impacts
environnementaux et sociétaux des systèmes de transport. Elle permet ainsi donc d’assurer la
mise en œuvre de bonnes pratiques au sein des chaînes logistiques durables. Pour les
décideurs politiques, cet outil permet de planifier les déplacements au sein des territoires tout
en favorisant l’utilisation de modes de transport respectueux de l’environnement et du cadre
de vie, en favorisant par la même occasion la décongestion des axes de circulation.
136
Conclusion et perspectives
compte en plus de l’empreinte carbone, des critères permettant de limiter les impacts
sociétaux que sont les risques d’accident, les nuisances sonores et la consommation
d’énergie entre autres, en mettant l’accent sur les types de combustibles utilisés dans
les différentes zones étudiées. Cela permet de réduire l’impact global du système de
transport en se basant sur la particularité de chaque mode de transport et sur la
complémentarité de ceux-ci. Notre approche contribue à rendre la chaîne logistique
« plus verte », en ce sens où les solutions obtenues permettent une réduction des
impacts de gaz à effet de serre pouvant aller jusqu’à 2 tonnes et un gain en
consommation d’énergie pouvant atteindre 24.04 GJ en comparant les solutions
obtenues pour le scénario industriel et celles obtenues pour le scénario écologique.
Cependant, l’approche proposée dans le cadre de ces travaux présente des limites et des
insuffisances sur certains points. En effet, la modélisation du système de transport n’intègre
pas la localisation des plateformes multimodales ainsi que la gestion des marchandises dans
celles-ci ; le cas de transport de marchandises de différents types et le cas où les marchandises
ont des destinations différentes ne sont pas traités.
De plus, concernant l’algorithme et son fonctionnement, les résultats obtenus pour certaines
préférences sont en très grand nombre (plus de 100 solutions) ; l’avantage dans ce cas est que
toutes les solutions Pareto-optimales de l’espace de recherche sont proposées au décideur.
137
Conclusion et perspectives
Cependant, le risque dans ce cas est que le décideur se sente « perdu » du fait du trop grand
nombre de données à gérer et du grand nombre de paramètres à fixer ; si le décideur n’est pas
un expert, le choix final peut se révéler très cornélien. D’autre part, dans le cas où on a plus de
trois critères, la représentation du front de Pareto devient difficile et les tests de dominances
sont moins précis, ce qui conduit à des solutions qui, bien que conformes aux critères fixés
sont non-viables ou paraissent aberrantes.
Pour finir, les résultats obtenus pour certains critères tels que le risque d’accident manquent
de précision (plusieurs solutions ayant un risque d’accident nul) ; cela est dû au manque de
données sur certains arcs du réseau. Le manque de données précises sur la congestion n’a pas
permis de vérifier la pertinence de la modélisation du dit problème.
Perspectives de recherche
Les limites relevées à l’issue de cette étude ouvrent des perspectives de recherche tant au
niveau de la modélisation théorique des critères qu’au niveau du fonctionnement de
l’algorithme proposé.
Le modèle : Une des perspectives d’amélioration serait de pouvoir modéliser et intégrer plus
de critères dans le modèle, notamment les autres critères de la roue de l’impact (Figure 10)
tels que les critères sociaux (satisfaction des parties prenantes, contribution au développement
humain, les conditions de travail…) et la part d’occupation des eaux de surface et du sol. La
modélisation des impacts sociaux nécessite des études réalisées avec des sociologues afin de
déterminer des données statistiques qui serviront de base au modèle. Ces impacts pourraient
être optimisés en utilisant des mesures qualitatives impliquant la logique floue (règles floues,
pondération des critères avec AHP flou…). Une autre perspective est la prise en compte de la
disponibilité des moyens de transport lors des transbordements et l’intégration d’un système
utilisant des marchandises de différents types et ayant des destinations différentes.
Concernant le problème de transport, des données sont nécessaires pour tester la prise en
compte de la congestion dans le modèle. Le modèle défini ici étant statique, nous pourrions
intégrer dans le modèle la gestion en temps réel du problème à l’aide des données réelles du
trafic pour avoir un système beaucoup plus dynamique. Cela permettrait par exemple de
basculer d’un mode de transport vers un autre en cas d’aléas (embouteillages, accidents,
catastrophes naturelles…) et d’envisager le ferroutage dans certains cas.
L’algorithme : Des perspectives pour améliorer l’algorithme proposé ici et les algorithmes de
colonies de fourmis multiobjectifs de façon générale sont à prévoir.
Pour notre cas, nous constatons que lorsque l’on choisit certaines préférences, on obtient un
trop grand nombre de solutions, rendant la tâche difficile au décideur pour choisir le résultat
final. Une des alternatives proposées pour réduire ce nombre de solutions et de mettre en
place un système expert afin de ne garder que les solutions les plus pertinentes. Une autre
solution est la mise en place d’un système interactif permettant d’agir sur l’algorithme lui-
même afin de privilégier certaines solutions par rapport à d’autres. Ce système aura pour
objectif de permettre au décideur d’agir à priori ou à postériori sur l’algorithme et notamment
138
Conclusion et perspectives
sur les tests de dominance. Le décideur choisirait parmi les solutions appartenant au front de
Pareto, les objectifs qu’il souhaite améliorer d’une part et d’autre part, il pourrait modifier les
paramètres pour voir à chaque fois si les solutions obtenues sont meilleures ou non.
Afin de mieux filtrer les solutions, il serait intéressant de mettre en place une procédure de
recherche locale afin d’améliorer le fonctionnement de l’algorithme, par exemple par la
réduction de l’espace des solutions en fonction des solutions appartenant au front de Pareto ;
dans ce cas, on fixerait une borne inférieure et une borne supérieure dans l’espace de
recherche en fonction des meilleures solutions obtenues pour la préférence choisie.
Pour finir, l’algorithme présenté ici pourrait être comparé aux algorithmes existants afin d’en
évaluer les performances. Cependant, la comparaison avec des algorithmes existants est
difficile du fait de la particularité du problème et de l’inexistence de benchmarks pour des
applications des algorithmes de colonies de fourmis aux problèmes de plus court chemin
multiobjectif pour le transport intermodal ; nous avons ainsi défini une nouvelle classe de
modèle, le modèle de plus court chemin multiobjectif multimodal utilisant les algorithmes de
colonies de fourmis. Par ailleurs, des algorithmes à correction d’étiquettes tels que ceux
proposés par Ziliaskopoulos (Ziliaskopoulos et Wardell, 2000) permettent d’optimiser deux
objectifs dans un contexte de transport intermodal. Nous pourrions appliquer cet algorithme à
notre modèle et comparer les résultats obtenus ainsi que leurs performances respectives.
Toutefois, cela nécessiterait de réadapter notre modèle, la difficulté qui se pose est que pour
ce type de modèles, il faut définir tous les chemins possibles dans notre graphe.
139
Bibliographie
Bibliographie
A
ADEME, (2006), « Les transports de marchandises : Quels impacts ? Quelles actions ? »
Ahn K., Rakha H., (2008), “The effects of route choice decisions on vehicle energy
consumption and emissions”, Transportation Research Part D, Vol.13, pp. 151–167.
Alaya I., Solnon C., Ghedira K., (2007). “Ant Colony Optimization for Multi-Objective
Optimization Problems”, Proceedings of the 19th IEEE International Conference on Tools
with Artificial Intelligence, pp. 450-457.
Andersson H., Hoff A., Christiansen M., Hasle G., Løkketangen A., (2010). “Industrial
aspects and literature survey: Combined inventory management and routing”, Computers
&OperationsResearch, Vol.37, pp. 1515–1536.
Androutsopoulos K. N., Zografos K. G., (2008). “Solving the k-shortest path problem with
time windows in a time varying network”, Operations Research Letters, Vol.36, pp.692-695.
Angus D., Woodward C., (2009). “Multiple objective ant colony optimization”, Swarm
Intelligence, Vol. 3, N° 1, pp. 69-85.
B
Barán B., Schaerer M., (2003). “A multiobjective ant colony system for vehicle routing
problem with time windows”, In Proceedings of the 21st IASTED international conference on
applied informatics, pp. 97–102. Calgary: ACTA Press.
Bauer A., Bullnheimer B., Hartl R.F., Strauß C., (1999). “An Ant Colony Optimization
Approach for the Single Machine Total Tardiness Problem”, In CEC99: Proceedings of the
Congress on Evolutionary Computation.
Beamon B. M., (1998). “Supply Chain Design and Analysis: Models and Methods”,
International Journal of Production Economics, Vol. 55, No. 3, pp. 281-294.
Beamon B. M., (1999). “Designing the Green Supply Chain”, Logistics Information
Management, Vol.12, N°4, pp. 332-342.
140
Bibliographie
Beamon B. M., (2008). “Sustainability and the Future of Supply Chain Management”,
Operations and supply chain management, Vol. 1, N° 1, pp. 4-18.
Bellman R.E., (1958). “On a routing problem”, Quarterly of Applied Mathematics, Vol. 16,
pp. 87–90.
Bunse K., Vodicka M., Schönsleben P., Brülhart M., Ernst F. O., (2011). “Integrating energy
efficiency performance in production management e gap analysis between industrial needs
and scientific literature”, Journal of Cleaner Production, Vol. 19, pp. 667-679.
C
Caramia M., Guerriero F., (2009). “A Heuristic approach to long-haul freight transportation
with multiple objective functions”, Omega, Vol. 37, N°3, pp.600-614.
Cardoso P., Jesus M., Marquez A., (2003). MONACO – « Multi-Objective Network
Optimisation Based on an ACO », Proc. X Encuentros de Geometria Computacional, Seville,
Spain, June 16-17.
Carter C. R., Kale R., Grimm C. M., (2000). “Environmental purchasing and firm
performance: an empirical investigation”, Transportation Research Part E, Vol. 36, pp. 219-
228.
Chang T., (2008). “Best routes selection in international intermodal networks”, Computers &
Operations Research, Vol. 35, pp. 2877–2891.
Chen C., (2005). “Incorporating green purchasing into the frame of ISO 14000”, Journal of
Cleaner Production, Vol.13, pp.927-933.
Climaco J.C.N., Martins E.Q.V., (1981). “On the determination of the nondominated paths in
a multiobjective network problem”, Proceedings of V Symposium uber Operations Research,
Koln, (1980), in Methods in Operations Research , Anton Hain, Konigstein, Vol. 40, pp. 255-
258.
Climaco J.C.N., Martins E.Q.V., (1982). “A bicriterion shortest path algorithm”, European
Journal of Operational Research, Vol. 11, pp. 399–404.
Colvile R. N., Hutchinson E. J., Mindell J. S., Warren R. F., (2001). “The transport sector as a
source of air pollution”, Atmospheric Environment, Vol. 35, N° 9, pp. 1537-1565.
141
Bibliographie
Coutinho-Rodrigues J.M., Clìmaco J.C.N., Current J.R., (1999). “An interactive bi objective
shortest path approach: searching for unsupported non-dominated solutions”, Computers &
Operations Research, Vol. 26, pp.789-798.
Crainic T. G., Kim K. H., (2007). “Chapter 8. Intermodal Transportation Review Article”,
Handbooks in Operations Research and Management Science, Vol. 14, pp. 467-537.
Croom S., Romano P., Giannakis M., (2000). “Supply chain management: an analytical
framework for critical literature review”, European Journal of Purchasing & Supply
Management, Vol.6, N°1, pp. 67-83.
Cruz J., Matsypura D., (2009). Supply chain networks with corporate social responsibility
through integrated environmental decision-making. International Journal of Production
Research, Vol. 47, N° 3, pp. 621– 648
Current J. R., Revelle C. S., Cohon J. L., (1990). “An interactive approach to identify the best
compromise solution for two objective shortest path problems”, Computers & Operations
Research, Vol. 17, N°2, pp. 197-198.
D
Daganzo C. F., (2005). “Logistics Systems Analysis”, 4th ed., Springer-Verlag, ISBN-
10: 0387540695.
Dijkstra E.W., (1959). “A note on two problems in connection with graphs”, Numerische
Mathematik, Vol. 1, pp. 269–271.
Doerner K., Gutjahr W.J., Hartl R.F., Strauss C., Stummer C., (20011). “Ant Colony
Optimization in Multiobjective Portfolio Selection”, Proceedings of the 4th Metaheuristics
International Conference, Porto, pp.243-248.
Doerner K., Hartl R.F., Reimann M., (20012). “Cooperative Ant Colonies for optimizing
resource allocation in transportation”, In E.J.W. Boers, J. Gottlieb, P.L. Lanzi, R.E. Smith, S.
Cagnoni, E. Hart, G.R. Raidl, H. Tijink (eds.), Applications of Evolutionary Computing:
EvoWorkshops, Berlin, pp. 70-79.
Doerner K., Hartl R.F., Teimann M., (2003). “Are COMPETants more competent for problem
solving?-The case of full truckload transportation”, Central European Journal of Operations
Research, Vol. 2, pp. 115–141.
Doerner K., Gutjahr W. J., Hartl R. F., Strauss C., Stummer C., (2004). “Pareto Ant Colony
Optimization: A metaheuristic approach to multiobjective portfolio selection”, Kluwer
Academic Publishers, Annals of Operations Research, Vol. 131, pp. 79–99.
142
Bibliographie
Donati A.V., Montemanni R., Casagrande N., Rizzoli A. E., Gambardella L. M., (2008).
“Time dependent vehicle routing problem with a multi ant colony system”, European Journal
of Operational Research, Vol.185, pp. 1174–1191.
Dorigo M., Maniezzo V., Colorni A., (1991) “The Ant System: An Autocatalytic Optimizing
Process”, Technical Report No. 91-016 Revised, Politecnico di Milano, Italy.
Dorigo M., Gambardella L., (1996). “A Study of some properties of Ant-Q” .In Proceedings
of PPSN IV– Fourth International Conference on Parallel Problem Solving from Nature, pp.
656–665.
Dorigo M., Maniezzo V., Colorni A., (1996). “The Ant System: Optimization by a colony of
cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics–Part B, Vol.26,
No.1, pp.1-13.
Dorigo M., Gambardella L., (1997) Ant colony system: A cooperative learning approach to
the travelling salesman problem, IEEE Transactions on Evolutionary Computation, Vol.1,
N°1, pp.53–66.
Dorigo M., Blum C., (2005). “Ant colony optimization theory: A survey”, Theoretical
Computer Science, Vol. 344, pp. 243 – 278.
Dorigo M., Krzysztof S., (2006). “An Introduction to Ant Colony Optimization”, IRIDIA
Technical Report Series.
Dréo J., Pétrowski A., Siarry P., Taillard E., (2003). “Métaheuristiques pour l'optimisation
difficile”. Editeur : Eyrolles.
Dullaert W., Maes B., Cernimmen B., Witlox F., (2005). “An evolutionary algorithm for
order splitting with multiple transport alternatives”, Expert Systems with Applications, Vol.
28, pp.201-208.
E
Ehrgott M., Gandibleux X., (2000). “A survey and annotated bibliography of multiobjective
combinatorial optimization”, Operation Research Spektrum, Vol. 22, pp. 425–460.
Ehrgott M., Ruzika S., (2005). “Improved ε-Constraint Method for Multiobjective
Programming”, Journal of optimization theory and applications, Vol. 138, N°3, pp. 375-396.
143
Bibliographie
El korchi A., Millet D., (2011). “Designing a sustainable reverse logistics channel: the 18
generic structures framework”, Journal of Cleaner Production, Vol. 19, pp. 588–597.
F
Fija1 T., (2007). “An environmental assessment method for cleaner production technologies”,
Journal of Cleaner Production, Vol. 15, pp. 914-919.
Flachsbart P. G., (1999). “Human exposure to carbon monoxide from mobile sources”,
Chemosphere - Global Change Science, Vol. 1, N° 1-3, pp. 301-329.
Ford L.R, Fulkerson D.R, (1962). “Flows in networks”, Princeton, New Jersey, USA.
G
Gabrel V., Vanderpooten D., (2002). “Enumeration and interactive selection of efficient paths
in a multiple criteria graph for scheduling an earth observing satellite”, European Journal of
Operational Research, Vol.139, pp. 533–542.
Gagné C., Gravel M., Price W., (2001). “Scheduling a single machine with sequence
dependent setup time using ant colony optimization”, Faculté des sciences de l’administration,
Université Laval Québec (Québec) Canada, ISBN – 2-89524-123-6.
Gagné C., Gravel M., Price WL., (2004). “Optimisation multi-objectifs à l'aide d'un
algorithme de colonie de fourmis”, Information Systems and Operational Research (INFOR),
Vol. 42, N° 1, pp. 23-42.
Gambardella L. M., Dorigo M., (1995). “Ant-Q: A Reinforcement Learning approach to the
traveling salesman problem”, Université Libre De Bruxelles.
Gambardella L., Taillard E., Agazzi G., (1999). “MACS-VRPTW: A multiple ant colony
system for vehicle routing problems with time windows”, in: D. Corne, M. Dorigo, F. Glover
(Eds.), New Ideas in Optimization, McGraw-Hill, pp.73–76.
Gandibleux X., Beugnies F., Randriamasy S., (2006). “Martins’ algorithm revisited for multi-
objective shortest path problems with a MaxMin cost function”, A Quarterly Journal of
Operations Research, Vol. 4, No 1, pp. 47-59.
García-Martínez C., Cordón O., Herrera F., (2007). “A taxonomy and an empirical analysis of
multiple objective ant colony optimization algorithms for the bi-criteria TSP”, European
Journal of Operational Research, Vol. 180, pp. 116–148
144
Bibliographie
Giannakis M., Louis M., (2011). “A multi-agent based framework for supply chain risk
management”, Journal of Purchasing & SupplyManagement, Vol. 17, pp. 23–31.
Gravel M., Price W. L., Gagné C., (2002). “Scheduling continuous casting of aluminum using
a multiple objective ant colony optimization metaheuristic”, European Journal of Operational
Research, Vol. 1, pp. 218–229.
Guerriero F., Musmanno R., (2001). “Label Correcting Methods to Solve Multicriteria
Shortest Path Problems”, Journal of Optimization Theory and Applications: Vol.111, N°. 3,
pp.589-613.
Guntsch M.G., Middendorf M., (2003). “Solving multi-criteria optimization problems with
population-based ACO”, Lecture Notes in Computer Science, Vol. 2632/2003, pp. 464-478.
H
Hansen, P., (1980). “Bicriterion Path Problems, Multiple-Criteria Decision Making: Theory
and Applications”, Edited by G. Fandel and T. Gal, Springer Verlag, Heidelberg, Germany,
pp. 109–127.
Harris I., Naim M. and Mumford C., (2007). “A review of infrastructure modelling for Green
Logistics”, Proceedings of the Logistics Research Network Annual Conference, 5th - 7th
September 2007, pp 694-699.
Harris I., Naim M., Palmer A., Potter A., Mumford C., (2011). “Assessing the impact of cost
optimization based on infrastructure modelling on CO2 emissions”, Int. J. Production
Economics, Vol. 131, pp. 313–321. doi:10.1016/j.ijpe.2010.03.005.
He F., Qi H., Fan Q., (2007). “An Evolutionary Algorithm for the Multi-objective Shortest
Path Problem”, Advances in Intelligent Systems Research, International Conference on
Intelligent Systems and Knowledge Engineering (ISKE 2007).
Heikkilä J, (2002). “From supply to demand chain management: efficiency and customer
satisfaction”, Journal of Operations Management, Vol.20, pp. 747–767.
Henig M., (1986). “The shortest path problem with two objective functions”, European
Journal of Operational Research, Vol. 25, pp. 281–291.
Hicks C., Heidrich O., McGovern T., Donnelly T., (2004). “A functional model of supply
chains and waste”, Int. J. Production Economics, Vol. 89, pp. 165–174.
Ho W., Xu X., Dey P. K., (2010). “Multi-criteria decision making approaches for supplier
evaluation and selection: A literature review”, European Journal of Operational Research,
Vol. 202, pp.16–24.
145
Bibliographie
Hsua C., Hsieha Y., (2007). “Routing, ship size, and sailing frequency decision-making for a
maritime hub-and-spoke container network”, Mathematical and Computer Modelling, Vol.
45, pp. 899–916.
Hugo A., Pistikopoulos E., (2005). “Environmentally conscious long-range planning and
design of supply chain networks”, Journal of Cleaner Production, Vol. 13, N° 15, pp. 1428-
1448.
I-J
IFEU, (2002). Etude scientifique- Analyse comparative de la consommation d’énergie et des
émissions de CO entre le transport routier et le transport combiné rail/route.
Iredi S., Merkle D., Middendorf M., (2001). “Bi-criterion optimization with multi colony ant
algorithms”, Lecture Notes in Computer Science (LNCS), Vol. 1993/2001, pp. 359–372.
Janic M., (2007). “Modelling the full costs of an intermodal and road freight transport
network”, Transportation Research Part D, Vol. 12, pp. 33-44.
K
Kainumaa Y., Tawara N., (2006). “A multiple attribute utility theory approach to lean and
green supply chain management”, International Journal of Production Economics, Vol.101,
pp.99–108.
Kara B.Y., Verter V., (2004). “Designing a road network for hazardous materials
transportation”, Transportation Science, Vol.38, N°2, pp. 188–196.
Karlsson R., Luttropp C., (2006). “EcoDesign: what’s happening? An overview of the subject
area of EcoDesign and of the papers in this special issue”, Journal of Cleaner Production,
Vol. 14, pp. 1291 – 1298.
Khoo H. H., Bainbridge I., Spedding T.A., Taplin D.M., (2001). “Creating a green supply
chain”, Greener Management International, Vol. 35, pp. 71-88.
Klassen R., Johnson P.F., (2004). “The green supply chain”. In Westbrook, R. & New, S.
(Eds.). Understanding Supply Chains - Concepts, Critiques and Futures, pp. 229 -251.
Knörr W., Reuter C., (2005). “EcoTransIT: Ecological Transport Information Tool-
Environmental Methodology and Data”, Heidelberg, July 2005.
Kostreva M.M., Wiecek M.M., (1993). “Time dependency in multiple objective dynamic
programming”, Journal of Mathematical Analysis and Applications, Vol. 173, N° 1, pp. 289–
307.
146
Bibliographie
L
Lacomme P., Prins C., Sevaux M., (2003). “Algorithmes de graphes”, 2e édition, Eyrolles
ISBN : 2-212-11385-4.
Lacomme P., Prins C., Tanguy A., (2003). “Optimisation par colonies de fourmis pour les
tournées sur arcs”, 4e Conférence Francophone de MOdélisation et SIMulation, MOSIM’03 –
du 23 au 25 avril 2003 - Toulouse (France).
Lee H. B., Cho N. W., Hong Y. S., (2010). “A hierarchical end-of-life decision model for
determining the economic levels of remanufacturing and disassembly under environmental
regulations”, Journal of Cleaner Production, Vol. 18, pp.1276-1283.
Levinson D.M., Gillen D., Kanafani D., (1998). “The social cost of intercity transportation: a
review and comparison of air and highway”, Transport Reviews, Vol. 18, pp. 15-24.
Li S., Lin B., (2006). “Accessing information sharing and information quality in supply chain
management”, Decision Support Systems, Vol. 42, pp.1641–1656.
Lindsey R., Verhoef E. T., (1999). “Congestion Modelling”, Handbook in transport Vol.1,
Chapter 21.
López-Ibáñez M., (2004). Multi-objective ant colony optimization, Master’s thesis, Darmstadt
University of Technology.
Lozano A., Storchi G., (2001). “Shortest viable path algorithm in multimodal networks”,
Transportation Research Part A, Vol.35, pp.225-241.
Lozano A., Storchi G., (2002). “Shortest viable hyperpath in multimodal networks”,
Transportation Research Part B, Vol. 36, pp. 853–874.
Luttropp C., Lagerstedt J., (2006) “EcoDesign and The Ten Golden Rules: generic advice for
merging environmental aspects into product development”, Journal of Cleaner Production,
Vol. 14, pp.1396 – 1408.
M
Mariano C.E., Morales E., (1999). “MOAQ: An Ant-Q algorithm for multiple objective
optimization problems”, in: W. Banzhaf, J. Daida, A.E. Eiben, M.H. Garzon, V. Hnavar, M.
Jakiela, R.E. Smith (Eds.), Proc. of the Genetic and Evolutionary Computing Conference
(GECCO 99), San Francisco, California, USA, July, pp. 894–901.
MARPOL 73/78, Convention internationale de 1973 pour la prévention de la pollution par les
navires.
147
Bibliographie
Martins E.Q.V., (1984). “On a multicriteria shortest path algorithm”, European Journal of
Research, Vol.16, N° 2, pp.236-245.
Martins E.Q.V., Pascoal M.M.B., Dos Santos J.L.E., “The K Shortest path Problem”, June
1998.
Martins E.Q.V., Pascoal M.M.B., Dos Santos J.L.E., “Labelling algorithms for ranking
shortest path”, October 1999.
Martins E., Santos J., (1999). “The labeling algorithm for the multiobjective shortest path
problem”, Departamento de Matematica, Universidade de Coimbra, Portugal, Tech. Rep. TR-
99/005.
McMullen P.R., (2001). “An ant colony optimization approach to addressing a JIT sequencing
problem with multiple objectives”, Artificial Intelligence in Engineering, Vol. 15, N° 3, pp.
309-317.
Melo M.T., Nickel S., Saldanha-da-Gama F., (2009). “Facility location and supply chain
management – A review”, European Journal of Operational Research, Vol.196, pp. 401–412.
Min H., Jayaraman V., Srivastava R., (1998). “Combined location-routing problems: a
synthesis and future research directions”, European Journal of Operational Research,
Vol.108, pp. 1–15.
Mitchell M., (1998) “An Introduction to Genetic Algorithms”, First MIT Press paperback
edition, Massachusetts Institute of Technology, ISBN 0−262−13316−4 (HB), 0−262−63185−7
(PB).
Modesti P., Sciomachen A., (1998). “A utility measure for finding multiobjective shortest
paths in urban multimodal transportation networks”, European Journal of Operational
Research, Vol.111, pp.495-508.
Morais S., Mata T. M., Martins A. A., Pinto G. A., Costa C. A.V., (2010). “Simulation and
life cycle assessment of process design alternatives for biodiesel production from waste
vegetable oils”, Journal of Cleaner Production, Vol. 18, pp. 1251-1259.
N-O
Newell G.F., (1999). “Delays caused by a queue at a freeway exit ramp”, Transportation
Research Part B, Vol. 33, pp.337-350.
Nguyen S., Pallottino S., (1986). “Hyperpaths and shortest hyperpaths”. In: Simeone, B. (Ed.),
Combinatorial Optimization. Lecture Notes in Mathematics. Springer, Berlin, pp. 258–271.
OECD and the international transport forum, Transport outlook 2008 focusing on CO2
emissions from road vehicles, discussion paper N°2008-13, May 2008.
148
Bibliographie
Otsubo H., Rapoport A., “Vickrey’s model of traffic congestion discretized”, Transportation
Research Part B, Vol.42, pp.873–889, 2008.
P
Pangilinan J.M. A., Janssens G. K., “Evolutionary Algorithms for the Multiobjective Shortest
Path Problem”, International Journal of Computer and Information Science and Engineering,
Vol.1, N°1, 2007.
Perotto E., Canziani R., Marchesi R., Butelli P., (2008). “Environmental performance,
indicators and measurement uncertainty in EMS context: a case study”, Journal of Cleaner
Production, Vol.16, pp. 517-530.
Piecyk M., McKinnon A., (2007). “Internalising the External Costs of Road Freight Transport
in the UK”,. Logistics Research Centre, School of Management and Languages. Heriot-Watt
University, Edinburgh, UK, Obtained through the Internet: http://www.greenlogistics.org.
Piecyk M.I., McKinnon A.C., (2010). “Forecasting the carbon footprint of road freight
transport in 2020”, International Journal of Production Economics, Vol.128, N° 1, pp. 31-42.
Q-R
Qu L., Chen Y.F., (2008). “A Hybrid MCDM Method for Route Selection of Multimodal
Transportation Network”. In: Sun, F., Zhang, J., Tan, Y., Cao, J., Yu, W. (eds.): Advances in
Neural Networks. Lecture Notes in Computer Science, Vol. 5263. Springer, Berlin /
Heidelberg, pp.374-383.
Ricci A., Black I., (2005). “Measuring the Marginal Social Cost of Transport”, Research in
Transportation Economics, Vol.14, pp. 245–285.
Rondinelli D., Berry M., (2000). “Multimodal Transportation, Logistics, and the
Environment: Managing Interactions in a Global Economy”, European Management Journal,
Vol. 18, pp.398–410.
S
El Saadany A.M.A., Jaber M.Y., (2010); “A production/remanufacture model with returns’
subassemblies managed differently”, International Journal of Production Economics,
doi:10.1016/j.ijpe.2010.08.014.
Sarkis J., 2003. “A strategic decision framework for green supply chain management”,
Journal of Cleaner Production, Vol.11, pp. 397–409.
149
Bibliographie
Sarkis J., Zhu Q., Lai K., (2011). “An organizational theoretic review of green supply chain
management literature”, International Journal of Production Economics,
doi:10.1016/j.ijpe.2010.11.010.
Sawadogo M., Anciaux D., (2010). “Reducing the environmental impacts of intermodal
transportation: amulti-criteria analysis based on ELECTRE and AHP methods”, Proceedings
of the 3rd International Conference on Information Systems, Logistics and Supply Chain
Creating value through green supply chains ILS 2010 –Casablanca (Morocco), April 14-16.
Sawadogo M., Anciaux D., (2011). “Intermodal transportation within the green supply chain:
an approach based on ELECTRE method”, International Journal of Business Performance
and Supply Chain Modeling, Vol. 3, No. 1, pp.43–65.
Schreyer C., Schneider C., Maibach M., RothengatterW., Doll C., (2005). “External Cost of
Transport”, INFRAS.
Shiftan Y., Kaplan S., Hakkert S., (2003). “Scenario building as a tool for planning a
sustainable transportation system”, Transportation Research Part D, Vol. 8, pp. 323–342.
Skriver A.J.V., Andersen, K.A., (2000). “A label correcting approach for solving bicriterion
shortest-path problems”, Computers & Operations Research,Vol. 27, pp. 507-524.
Spangenberg J. H., Fuad-Luke A., Blincoe K., (2010). “Design for Sustainability (DfS): the
interface of sustainable production and consumption”, Journal of Cleaner Production, Vol.
18, pp. 1485-1493.
Stützle T., Hoos H. H., (2000). “MAX – MIN Ant system”, Future Generation Computer
Systems, Vol.16, N° 8, pp. 889–914.
T
T’Kindt V., Billaut J.C., (2005). “Multicriteria scheduling, theory, models and algorithms”,
Springer- Verlag, Berlin, Heidelberg.
The Ashden Trust, How Vehicle Pollution Affects Our Health, (1994).
150
Bibliographie
Transport White Paper, (2006). Final Communication from the commission to the council and
the European parliament: Keep Europe moving - Sustainable mobility for our continent. Mid-
term review of the European Commission’s 2001. June, 22th 2006, Brussels.
U-V-W
Ülengin F., Özgür K., Şule Ö., Ülengin B., Aktaş E., (2010). “A problem-structuring model
for analyzing transportation–environment relationships”, European Journal of Operational
Research 200, pp. 844–859.
United States Environmental Protection Agency, Air and Radiation- Emission Facts,
EPA420-F-99-040, November 1999.
Wang F., Lai X., Shi N., (2011). “A multi-objective optimization for green supply chain
network design”, Decision Support Systems, Vol. 51, pp. 262–269.
Y-Z
Yang H., Meng Q., (1998). “Departure time, route choice and congestion toll in a queuing
network with elastic demand”, Transportation Research Part B, Vol. 32, N°. 4, pp. 247-260.
Zhang H.C., Kuo T.C., Lu H., Huang S.H., (1997). “Environmentally conscious design and
manufacturing: a state-of-the-art survey”, Journal of Manufacturing Systems, Vol. 16, pp.
352-371.
Ziliaskopoulos A., Wardell W., (2000). “An intermodal optimum path algorithm for
multimodal networks with dynamic arc travel times and switching delays”, European Journal
of Operational Research, Vol. 125, pp.486-502.
151
Annexes
Annexes
Annexe 1 : Les matrices de jugement- Poids des critères à l’aide de la méthode
AHP
Les matrices de jugements sont obtenues en effectuant une comparaison par paire des
différents critères pour chaque niveau de la hiérarchie, en utilisant l’échelle de 1 à 9 de Saaty.
Pour le scénario industriel, les critères coût et temps sont plus important que les autres
critères, tandis que pour le scénario écologique la priorité est donnée à la pollution et à la
consommation d’énergie.
SCENARIO INDUSTRIEL SCENARIO ECOLOGIQUE
Coût Temps Environ Transb Accide Vecteur Coût Temps Environ Transb Accide Vecteur
Coût 1,00 1,00 9,00 5,00 9,00 0,4217 Coût 1,00 1,00 0,11 5,00 2,00 0,1229
Temps 1,00 1,00 9,00 3,00 9,00 0,3715 Temps 1,00 1,00 0,11 3,00 2,00 0,1033
Environ 0,11 0,11 1,00 0,20 1,00 0,0379 Environ 9,00 9,00 1,00 9,00 9,00 0,6723
Transb 0,20 0,33 5,00 1,00 3,00 0,1277 Transb 0,20 0,33 0,11 1,00 2,00 0,0527
Accide 0,11 0,11 1,00 0,33 1,00 0,0413 Accide 0,50 0,50 0,11 0,50 1,00 0,0488
λm ax= 5,09 CI= 0,02 CR= 1,9% λm ax= 5,39 CI= 0,10 CR= 8,6%
Pollut 1,00 0,33 5,00 0,2654 Pollut 1,00 3,00 7,00 0,6491
Energie 3,00 1,00 9,00 0,6716 Energie 0,33 1,00 5,00 0,2790
Bruit 0,20 0,11 1,00 0,0629 Bruit 0,14 0,20 1,00 0,0719
λm ax= 3,03 CI= 0,01 CR= 2,5% λm ax= 3,06 CI= 0,03 CR= 5,6%
Transbordement Transbordement
λm ax= 2,00 CI= 0,00 CR= 0% λm ax= 2,00 CI= 0,00 CR= 0%
152
Annexes
Pour les différents polluants, les émissions de CO2 ont un poids plus important que ceux des
autres critères.
La Figure 57 représente les fronts de Pareto obtenus pour des valeurs de ρ=0,1 ; ρ=0,2 ;
ρ=0,3. L’analyse des résultats obtenus pour cette préférence montre que l’on a un équilibre
intensification/diversification à partir de ρ=0,2 (Figure 58) et les fronts de Pareto obtenus pour
des valeurs supérieures de ρ sont identiques à celui obtenu pour ρ=0,2. Pour notre étude, nous
avons retenu la valeur de ρ=0,2.
153
Annexes
Figure 58. Exemples de front de Pareto pour les meilleures configurations de ρ pour
Énergie/Bruit
Les résultats présentés ici permettent également de voir le format de sortie des données du
problème ; ainsi pour chaque itinéraire, on a les valeurs obtenues pour les différents critères,
le temps mis par la fourmi pour trouver le chemin et l’itinéraire trouvé. Concernant le dernier
point, l’heure d’arrivée souhaitée étant le 14/07/2010 08:45:00, l’heure de départ est
déterminée en fonction de la succession de moyens de transport utilisée et des temps de
transbordements. Ainsi le chemin de la solution 2 signifie :
154
Annexes
Bruit 0 Bruit 0
Consommation d'Énergie 7796,6 Consommation d'Énergie 7796,6
Quantité de polluants 358 Quantité de polluants 358
Risque d'accident 0 Risque d'accident 0
Cout 42838 Cout 42838
Dégâts 0 Dégât 0
Temps 5943 Temps 5943
Temps mis par la fourmi 0,0130008 Temps mis par la fourmi 0,034002
Solution 2 Solution 2
Bruit 74 Bruit 46
Consommation d'Energie 29320,71 Consommation d'Énergie 32251,08
Quantite de polluants 2350 Quantité de polluants 2760
Risque d'accident 0 Risque d'accident 0
Cout 97725 Cout 103237
Dégât 8 Dégât 0
Temps 164,65715 Temps 108,428566666667
Temps mis par la fourmi 0,0770044 Temps mis par la fourmi 0,1100063
Solution 3 Solution 3
Bruit 48 Bruit 74
Consommation d'Énergie 25301,07 Consommation d'Énergie 29320,71
Quantité de polluants 2059 Quantité de polluants 2350
Risque d'accident 0 Risque d'accident 0
Cout 97122 Cout 85522
Dégât 6 Dégât 8
Temps 252,94285 Temps 164,65715
Temps mis par la fourmi 0,0630036 Temps mis par la fourmi 0,0660038
Solution 4
Bruit 97
Consommation d'Énergie 32123,6
Quantité de polluants 2751
Risque d'accident 0
Cout 125924
Dégât 0
Temps 108
156
Annexes
Revues
Sawadogo, M. and Anciaux, D. (2011) ‘Intermodal transportation within the green supply
chain: an approach based on ELECTRE method’, Int. J. Business Performance and Supply
Chain Modelling, Vol. 3, No. 1, pp.43–65.
Sawadogo, M. and Anciaux, D. (2009). “Intermodal transportation within the green supply
chain: An approach based on the ELECTRE method”, Computers & Industrial Engineering
(CIE). International Conference on Industrial Engineering, 6-9 July 2009, p.839 – 844.
Sawadogo, M. and Anciaux, D. “Modèle de plus court chemin multiobjectif pour le transport
intermodal au sein de la chaine logistique verte”, Proceedings of the 8th ENIM IFAC
International Conference of Modeling and Simulation - MOSIM’10 - 10 au 12 mai 2010 -
Hammamet – Tunisie, Lavoisier ISBN : 978-2-7430-1330-1, pp. 392-401.
Sawadogo, M. and Anciaux, D. « Aide au choix d’un chemin intermodal au sein de la chaîne
logistique verte par la méthode AHP», 12e congrès annuel de la ROADEF - Saint-Etienne - 2
au 4 Mars 2011 Volume II - Page 717.
157
Annexes
Sawadogo, M, Anciaux, D., Roy D. Sustainable Intermodal Freight by route choice with
practicality constraints, Association for European Transport and contributors 2011, European
Transport Conference, 10 -12 October 2011, Glasgow, Scotland, UK.
158