T. Multimodal
T. Multimodal
Spécialité : Informatique
M. Ahmed El Hilali Alaoui Professeur des Universités / FST de Fès Co-directeur de thèse
Thèse codirigée par Jaouad Boukachour et Ahmed El Hilali Alaoui, et encadrée par Dalila Boudebous.
Laboratoire de Mathématiques Appliquées du Havre (LMAH - EA 3821)
4
THESE
pour l’obtention du grade de
DOCTEUR de l’UNIVERSITE
DU HAVRE NORMANDIE
En partenariat international avec la FST
de Fès
Spécialité : Informatique
Naoufal Rouky
le 29 Octobre 2018
JURY
M. Christian Prins PROFESSEUR DES UNIVERSITES Rapporteur
M. Ali Boutoulout PROFFESSEUR DES UNIVERSITES Rapporteur
M. Abdelmajid Hilali PROFESSEUR DES UNIVERSITES Examinateur
Mme Ghizlane Bencheikh MAITRE DE CONFERENCS - HDR Examinatrice
M. Djamal Benslimane PROFESSEUR DES UNIVERSITES Président
M. Jaouad Boukachour MAITRE DE CONFERENCS - HDR Directeur de thèse
Mme. Dalila Boudebous MAITRE DE CONFERENCS Encadrante de thèse
M. Ahmed El Hilali Alaoui PROFESSEUR DES UNIVERSITES Directeur de thèse
Je remercie les membres du jury pour l’intérêt, le temps et l’effort qu’ils ont consacrés à
la relecture de ce manuscrit et de m’avoir fait l’honneur de faire partie de ma soutenance de
thèse.
J’adresse un immense et très sincère merci à mes parents, mes sœurs et à ma famille, pour
leur soutien inconditionnel, la joie, la confiance et la fierté qu’ils me portent chaque jour.
Je remercie enfin toutes les personnes qui ont contribué, de près ou de loin, à la réalisation
de ce travail et que ma réussite leur tient à cœur.
Table des Matières
5. Conclusion ......................................................................................................................... 38
Chapitre III. Optimisation Sous Incertitudes .................................................................... 41
1. Introduction ....................................................................................................................... 43
2. Techniques d’Optimisation sous Incertitudes ..................................................................... 44
2.1. Optimisation Stochastique .............................................................................................................. 45
2.2. Optimisation par Ensembles Flous .................................................................................................. 47
2.4. Analyse de Sensibilité ...................................................................................................................... 49
2.5. Fonctions de Croyance .................................................................................................................... 50
5. Conclusion ......................................................................................................................... 68
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires................................... 71
2. Introduction ....................................................................................................................... 73
3. Travaux Antérieurs sur le Transfert de Conteneurs au Port du Havre .................................. 74
4. Problème de Tournées de Véhicules Robuste ..................................................................... 75
5. Problème de Tournées de Navettes Ferroviaires ................................................................ 79
5.1. Description et Modélisation Déterministe ...................................................................................... 79
5.2. Résultats Initiaux ............................................................................................................................. 80
5.3. Modélisation Robuste ..................................................................................................................... 82
8. Conclusion ......................................................................................................................... 98
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai .....101
1. Introduction ..................................................................................................................... 103
2. Etat de l’Art...................................................................................................................... 104
3. Description du Problème .................................................................................................. 107
4. Résolution par Simulation-Optimisation .......................................................................... 109
4.1. Structure Générale du Couplage ................................................................................................... 109
4.2. Procédure d’Optimisation par Colonies de Fourmis ..................................................................... 110
4.3. Recherche Locale : Descente à Voisinages Variables .................................................................... 114
4.4. Procédure de Simulation ............................................................................................................... 115
4.5. Mise à jour Globale de Phéromone .............................................................................................. 118
Chapitre II
Figure II.1 Exemple d'une chaîne logistique multimodale ................................................................... 10
Figure II.2 Illustration d'une chaîne de transport intermodal .............................................................. 11
Figure II.3 Transport combiné : (a) fleuve-route et (b) rail-route ....................................................... 11
Figure II.4 Exemple de chaîne de transport comodal avec utilisation isolée des modes de
transport ............................................................................................................................................. 12
Figure II.5 Exemple d’une chaîne de transport synchromodal ........................................................... 12
Figure II.6 Différentes configurations de réseaux de transport multimodal ..................................... 14
Figure II.7 Structure d’une gare de triage ferroviaire ............................................................................ 15
Figure II.8 Structure d’un terminal Rail-Route ...................................................................................... 15
Figure II.9 Structure d’un terminal Rail-Rail .......................................................................................... 16
Figure II.10 (a) Structure d’un terminal Trimodal et (b) Terminal Trimodal de Basel Nord (Suisse)
.............................................................................................................................................................. 17
Figure II.11 Structure d’un terminal maritime à conteneurs ................................................................ 17
Figure II.12 Classification des différents problèmes dans la chaîne de transport multimodal selon
leur niveau de décision et leur occurrence temporelle. ................................................................ 21
Figure II.13 (a) Plan du Port du Havre (b) Vue sur Port 2000 ............................................................ 33
Figure II.14 Vue sur le terminal multimodal du Havre ........................................................................ 34
Figure II.15 Schéma logistique actuelle au port du Havre ................................................................... 35
Figure II.16 Architecture du terminal multimodal ................................................................................ 35
Figure II.17 Problèmes d’optimisation dans le terminal multimodal du Havre ................................ 38
Chapitre III
Figure III.1 Illustration de l’influence des incertitudes sur la qualité des solutions.......................... 44
Figure III.2 Illustration des ensembles d’incertitudes les plus utilisés ................................................ 57
Figure III.3 Structures hiérarchiques de couplage Simulation-Optimisation .................................... 64
Figure III.4 Nombre d’articles traitant de la Simulation-Optimisation pour la gestion des
terminaux à conteneurs par année (1998-2016) ............................................................................ 67
Chapitre IV
Figure IV.1 Une navette ferroviaire au port du Havre ......................................................................... 73
Figure IV.2 Illustration d’une solution déterministe du RSRP ............................................................ 82
Figure IV.3 Les coûts supplémentaires et les degrés de protection obtenus par l'algorithme
RACO sur chaque niveau d'incertitudes ........................................................................................ 95
Chapitre V
Figure V.1 Structure d’un navire porte-conteneurs (a) et (b) Une vue en coupe d’une baie ........103
Figure V. 2 (a) Illustration d’une instance du QCSP incertain et (b) Représentation des relations
de précédence entre les tâches.......................................................................................................108
Figure V. 3 Structure générale de l’approche de couplage Simulation-Optimisation ....................110
Figure V. 4 Graphe de déplacement des fourmis ................................................................................111
Figure V. 5 Organigramme de la simulation à événements discrets .................................................117
Figure V. 6 Résultats de la comparaison de la performance des algorithmes considérés ..............120
Figure V. 7 (a) Pourcentage de déviation entre les valeurs maximales et (b) Pourcentage de
déviation entre les espérances........................................................................................................125
Figure V. 8 Pourcentages d'amélioration que les solutions S-O offrent par rapport aux solutions
déterministes ....................................................................................................................................125
Liste des Tableaux
Chapitre II
Tableau II.1 Caractéristiques des terminaux intermodaux ................................................................... 18
Tableau II.2 Classement des plus grands ports européens en 2015 ................................................... 19
Tableau II.3 Principaux terminaux intermodaux en Europe ............................................................... 20
Tableau II.4 Principaux travaux sur le problème de conception de réseau. ...................................... 23
Tableau II.5 Principaux travaux sur le problème de localisation des hubs. ....................................... 25
Tableau II.6 Quelques travaux sur la conception des terminaux intermodaux. ................................ 27
Tableau II.7 Aperçu de quelques travaux sur le problème de conception des services ................... 28
Tableau II.8 Un aperçu d’état de l’art sur le problème de gestion de ressources. ............................ 30
Tableau II.9 Quelques travaux sur le problème de replanification des itinéraires. ........................... 31
Tableau II.10 Répartition modale en 2013 en % dans les principaux ports nord européens ......... 34
Chapitre III
Tableau III.1 Aperçu sur l’utilisation de l’optimisation stochastique dans les problèmes de
transport multimodal ................................................................................................................................. 47
Tableau III.2 Quelques applications de l’optimisation par ensembles flous dans les problèmes de
transport multimodal ................................................................................................................................. 48
Tableau III.3 Aperçu sur les applications de l’analyse de sensibilité dans les problèmes de
transport multimodal ................................................................................................................................. 49
Tableau III.4 Évaluation des solutions sur les quatre scénarios .......................................................... 54
Tableau III.5 Résultats de la famille des critères de pire des cas ......................................................... 54
Tableau III.6 Résultats de l’𝛂-robustesse ............................................................................................... 55
Tableau III.7 Aperçu sur les principales applications des approches Simulation-Optimisation dans
la gestion des terminaux à conteneurs maritimes .................................................................................. 68
Chapitre IV
Tableau IV.1 Résumé de la littérature sur le problème de tournées de véhicules robuste
(RVRP)… .................................................................................................................................................... 78
Tableau IV.2 Exemple d’une instance de RSRP composée de dix rames, deux locomotives et trois
terminaux à conteneurs (inst10-2-3) ........................................................................................................ 81
Tableau IV.3 Comparaison des résultats de la modélisation mathématique et ceux de l’approche
en NORIA ................................................................................................................................................... 81
Tableau IV.4 Notations utilisées dans l'algorithme RACO ................................................................. 85
Tableau IV.5 Les meilleurs paramètres de l’algorithme RACO obtenus en utilisant l’outil irace .. 91
Tableau IV.6 Niveaux d’incertitudes ....................................................................................................... 91
Tableau IV.7 Résultats de l'algorithme RACO ...................................................................................... 92
Tableau IV.8 Temps de calcule de l'algorithme RACO........................................................................ 93
Tableau IV.9 Résultats correspondants aux instances : inst25-3-3 et inst25-4-3 .............................. 94
Tableau IV.10 Pool de solutions associé à l’instance inst25-3-3 ......................................................... 96
Tableau IV.11 Résultats du test de Friedman ........................................................................................ 97
Tableau IV.12 Écarts entre les sommes des rangs des différents niveaux d’incertitudes ................ 98
Chapitre V
Tableau V.1 Exemple de données d'entrée pour le QCSP incertain ................................................108
Tableau V.2 Meilleure combinaison de paramètres pour l’ACO. .....................................................118
Tableau V.3 Résultats des algorithmes : B&B, GRASP, TS, UDS, GA, HGA, HGP, HACO-EST
et HACO-LWL. ........................................................................................................................................121
Tableau V.4 Valeurs de Mflops des différents algorithmes étudiés ..................................................122
Tableau V.5 Temps de calcul des algorithmes (en minutes) ..............................................................122
Tableau V.6 Résultats de la simulation..................................................................................................124
1
Chapitre I. Introduction Générale
Chapitre I
Introduction Générale
“ Pour renforcer leur attractivité...les ports français...ont vocation à se positionner comme
des acteurs coordonnateurs démontrant une forte valeur ajoutée dans la mise en place de chaînes
logistiques intégrées, économiquement compétitives et pérennes, favorisant les moyens massifiés... ”
Ministère de l’Écologie, du Développement durable et de l’Énergie : Stratégie nationale de
relance portuaire, Mai 2013
Sommaire
1. Contexte ......................................................................................................................... 1
2. Objectifs et Contributions .............................................................................................3
3. Structure de la Thèse .....................................................................................................5
Les travaux présentés dans cette thèse ont été réalisés dans le cadre d’un projet de
recherche international regroupant quatre partenaires : la région de Normandie, le port du
Havre, l’Université du Havre-Normandie et l’Université Sidi Mohamed Ben Abdellah-Maroc.
Cette thèse a fait l’objet d’une allocation CODAH, et une partie de nos travaux ont été effectués
dans le cadre du projet CLASSE 2 financé par le Fond Européen de DEveloppement Régional
(FEDER), et par le conseil régional de Normandie. La thèse s’est déroulée au sein du Pôle
Ingénieur et Logistique (PIL) et les locaux de l'Institut Universitaire de Technologie (IUT) du
Havre.
1. Contexte
Le transport maritime, par ses possibilités de massifications, joue un rôle primordial dans
le développement commercial et la prospérité économique des pays. En effet, le volume de
marchandises transportées par voie maritime a vertigineusement évolué durant les dernières
années ; aujourd'hui il représente plus de 90% du trafic international. Par ailleurs, au-delà de sa
tâche principale qui consiste à assurer la circulation des biens, le transport maritime a également
un impact considérable sur la vie de nombreuses personnes en contribuant à la création de
milliers d'emplois et à l'amélioration des infrastructures autour des zones portuaires. L'évolution
du transport maritime est rendue possible grâce à la standardisation des conteneurs et
l'accroissement de la taille de la flotte mondiale des porte-conteneurs, passée de 3000 unités
(porte-conteneurs) en 2004 à près de 5100 unités en 2014, pour une capacité totale qui dépasse
les 17.5 millions EVP 1 ; ces chiffres placent le marché du transport maritime à la seconde
position mondiale, juste après le marché agroalimentaire, avec un chiffre d'affaires de plus de
1.5 trillion d'euros (UNCTAD, 2014).
1
EVP (Equivalent Vingt Pieds) : Unité de mesure définissant une longueur normalisée de 20 pieds pour les conteneurs
1
Chapitre I. Introduction Générale
Bien que les retombées économiques de l’évolution du transport maritime soient certes
significatives, elles s’accompagnent d’importants problèmes organisationnels et
environnementaux dont les plus visibles sont la congestion des ports maritimes et des réseaux
de systèmes de transport reliant les ports à leurs hinterlands, les accidents causés par les
camions, la pollution de l’air, le bruit et diverses autres nuisances. La situation est
particulièrement délicate en France ; la congestion au niveau du port du Havre, qui est le
premier port national pour les conteneurs, a atteint plus de 89%, le flux de marchandises
conteneurisées est responsable de plus de 40 % des émissions des gaz à effet de serre du secteur
de transport et plus de 10 % des émissions de tous les secteurs confondus (Aslog, 2016). Ceci
s’explique par une domination du transport routier qui représentait en 2014 plus de 87% du
volume de marchandises échangées au niveau national contre 11% pour le transport ferroviaire
et 2% pour le transport fluvial. À cause de ces problèmes, les ports français peinent à rivaliser
avec leurs concurrents européens ; en effet, ils occupent une place marginale en Europe avec à
peine 5 millions de conteneurs manutentionnés en 2015, loin derrière des pays comme
l'Allemagne, l'Espagne, les Pays-Bas, la Belgique et le Royaume-Uni. Au point qu’"un
conteneur sur deux à destination de la France ne passe pas par un des ports français" comme
annonce l’ancien président de la République, François Hollande, durant les "Assises de
l'économie de la mer" de 2015.
Pour faire face à cette situation et améliorer la compétitivité des ports français, l’état a
lancé depuis 2013 la stratégie nationale de relance portuaire (SNRP, 2013), dont l’objectif est
de donner à la France une place de premier rang au niveau du commerce international, comme
un point d’entrée ou hub de l’Europe, et de contribuer au développement industriel et
économique du pays. Cette stratégie repose sur trois principaux piliers :
2
Chapitre I. Introduction Générale
L’un des fruits de la stratégie de relance portuaire est le lancement du projet "Terminal
Multimodal" au Port du Havre. Ce dernier est l’un des projets majeurs au niveau du Grand Port
Maritime du Havre (GPMH), il vise à réduire le niveau de congestion dans les terminaux
maritimes, développer la part du transport massifié des conteneurs et réduire les émissions des
gaz à effet de serre en utilisant des modes alternatifs à la route pour le transfert des conteneurs.
Néanmoins, la réussite de ce projet dépend essentiellement de la bonne planification des
différentes opérations dans les composantes du nouveau terminal multimodal. La gestion de ces
opérations est laborieuse. Cela s’explique par plusieurs facteurs, entre autres, la nature
dynamique et distribuée de ces systèmes, la diversité des opérations, et l’incertitude et le
manque d’informations nécessaires au contrôle du flux. En effet, les opérateurs portuaires
havrais se retrouvent face à plusieurs problèmes de décision complexes, tels que : les problèmes
de tournées et les problèmes d'ordonnancement qui feront l’objet de cette thèse.
2. Objectifs et Contributions
Cette thèse s’inscrit dans la continuité des travaux initiés dans le cadre des projets de
recherche : ESSIMAS (Evaluation par Simulation de Solutions Innovantes pour le
développement du transport Massifié sur l'Axe Seine par coupons ferroviaires électriques)
(Benghalia , 2014) et DCAS (Direct Cargo Axe Seine) (Oudani, 2015). La finalité de cette thèse
est de développer des approches capables de répondre aux besoins des opérateurs portuaires au
niveau opérationnel, avec prise en compte des différentes sources d’incertitudes dans les
problèmes d’optimisation rencontrés dans le terminal multimodal du port du Havre (Figure I.1).
Deux problèmes d'optimisation sont principalement considérés dans cette thèse, à savoir :
l'optimisation de tournées de navettes ferroviaires (Rail Shuttle Routing Problem (RSRP)) et
l'ordonnancement de grues de quai (Quay Crane Scheduling Problem (QCSP)). Quant à
l’ordonnancement des opérations de manutention des trains, il a déjà été étudié sous incertitudes
dans la thèse de Abourraja (2017).
Figure I.1 Les trois problèmes majeurs d’optimisation rencontrés dans le terminal multimodal (les
problèmes encadrés en rouge sont ceux étudiés dans cette thèse)
Le problème de tournées de navettes ferroviaires vise à améliorer le système de transport
de conteneurs dans le port du Havre, et plus précisément entre le nouveau terminal multimodal
et les terminaux maritimes, en considérant les incertitudes sur les données (les incertitudes sur
3
Chapitre I. Introduction Générale
les temps de déplacement à vide des locomotives et les incertitudes sur les temps de transfert
des rames). L'objectif est de construire des tournées qui permettent de minimiser le taux des
déplacements improductifs des locomotives tout en respectant les contraintes de fenêtres de
temps définies sur les disponibilités des rames. Nous avons modélisé le problème dans le cas
déterministe comme un problème de tournées de véhicules, en considérant que les rames
représentent des nœuds à visiter, les temps de transfert représentent des temps de service et les
temps de déplacement à vide représentent les temps de déplacement entre les nœuds. Ensuite,
nous avons testé et validé notre modélisation sur quelques instances en utilisant le solveur
CPLEX, et nous avons comparé nos résultats à ceux de l’approche utilisée actuellement au port
du Havre. Nous avons introduit les incertitudes dans notre modélisation en utilisant des
techniques d'optimisation robuste et proposé un algorithme d'optimisation par colonie de
fourmis pour résoudre le problème sous incertitudes. Enfin, nous avons évalué les résultats de
notre approche en utilisant deux mesures de robustesse, à savoir, le degré de protection contre
les retards de transfert, et le coût supplémentaire payé par les décideurs en choisissant
d'appliquer une solution robuste au lieu d'une solution déterministe.
4
Chapitre I. Introduction Générale
3. Structure de la Thèse
Le Chapitre III « Optimisation sous Incertitudes », fournit un aperçu général sur les
différents paradigmes et approches d’optimisation utilisés dans la littérature pour étayer la prise
de décision face aux incertitudes. En particulier, le chapitre vise à présenter un état de l’art sur
les applications des approches d’optimisation sous incertitudes dans la résolution des problèmes
de transport multimodal.
Enfin, dans le Chapitre VI, une synthèse générale sur les travaux effectués au cours de
cette thèse ainsi que des perspectives de recherche sont présentés pour clôturer ce document.
5
Chapitre I. Introduction Générale
6
Chapitre II. Transport Multimodal
Chapitre II
Transport Multimodal
Sommaire
1. Introduction ...................................................................................................................9
2. Généralités sur le Transport Multimodal .................................................................... 10
2.1. Terminologie du Transport Multimodal .......................................................................... 10
2.1.1. Transport Multimodal ................................................................................................................. 10
2.1.2. Transport Intermodal.................................................................................................................. 10
2.1.3. Transport Combiné ..................................................................................................................... 11
2.1.4. Transport Comodal ..................................................................................................................... 11
2.1.5. Transport Synchromodal ............................................................................................................ 12
7
Chapitre II. Transport Multimodal
8
Chapitre II. Transport Multimodal
1. Introduction
Ce présent chapitre a pour but de dresser une vue d'ensemble sur le concept de transport
multimodal et sur la littérature relative aux problèmes de décision liés à la planification et la
gestion des différentes composantes de la chaîne logistique multimodale, ainsi qu’aux
problèmes qui seront traités dans cette thèse. Dans la section suivante, nous présenterons les
terminologies utilisées dans le transport multimodal, les différentes configurations de réseaux
de transport possibles et les principaux types de terminaux intermodaux utilisés dans la
conception d’une chaîne de transport. Dans la section 3, nous nous pencherons sur les
problèmes de gestion de la chaîne multimodale, nous présenterons une classification de ces
problèmes selon les trois niveaux de décisions : stratégique, tactique et opérationnel, et nous
exposerons les principaux travaux de recherches menés dans chaque niveau. Ensuite, dans la
section 4, nous décrirons notre cas d’étude « le port du havre » et nous abordons les travaux se
rattachant à la gestion de son nouveau terminal multimodal. Finalement, dans la section 5, nous
résumerons ce chapitre et nous mettrons en relief l’importance de la prise d’incertitude dans la
gestion du terminal multimodal et la rareté des travaux menés à ce titre.
9
Chapitre II. Transport Multimodal
La terminologie sur le transport multimodal n'est pas unifiée et différents termes circulent
dans la littérature et dans la pratique. En effet, à côté du terme "transport multimodal" les
intervenants dans la chaîne multimodale utilisent d'autres termes tels que : le transport
intermodal, le transport comodal, le transport synchromodal et le transport combiné (Economie
Commission, 2001). Même si toutes ces formes de transport impliquent, en fait, l'utilisation
d'au moins deux modes de transport, il existe quand même quelques différences entre eux que
nous soulignerons dans cette section.
10
Chapitre II. Transport Multimodal
manutention (empotage ou dépotage) de marchandise elle-même lors de changement entre les
modes (Figure II.2). L'intermodalité offre ainsi la flexibilité et les économies d'échelle
nécessaires pour une combinaison efficace entre plusieurs modes de transport (Lowe, 2006).
Le Transport combiné est l’une des formes de transport multimodal, qui implique
l’utilisation de deux modes de transport en combinaison, tels que le transport routier et
ferroviaire ou routier et fluvial (Figure II.3). Dans cette forme de transport, les parcours
principaux s’effectuent par les modes massifiés (i.e. rail, fleuve ou mer), et les parcours initiaux
et/ou terminaux (i.e. premier ou dernier kilomètre) par route (Economie Commission, 2001).
C’est le nombre de modes impliqués dans une opération multimodale et la faible distance qui
doit être parcourue par route qui distingue le transport combiné du transport intermodal. Ainsi,
le transport combiné est un type de transport intermodal, mais le transport intermodal n’est pas
forcément un transport combiné. Pour qu’il le devienne, il faudrait que les parcours par route
soient les plus courts possible et que le nombre de modes utilisés soit exactement égal à deux.
La comodalité est définie par la commission des communautés européennes (CCE, 2006)
comme le recours intelligent à différents modes de transport en combinaison ou isolément
(Figure II.4), débouchant sur une utilisation maximale des avantages de tous les modes, en
termes de durabilité globale (Feki, 2010). À la différence de l’intermodalité et le transport
combiné, qui ont tendance à favoriser les modes massifiés par rapport au mode routier, la
11
Chapitre II. Transport Multimodal
comodalité cherche plutôt une complémentarité entre les modes pour améliorer l’utilisation des
ressources et répondre à la demande logistique (Engström, 2013).
Comodalité
Figure II.4 Exemple de chaîne de transport comodal avec utilisation isolée des modes de transport
Synchromodalité
L’opérateur a le choix entre
les trois modes fluvial,
routier et ferroviaire dans
tous les centres de
transbordement (A, B et C
en cas de retour de
marchandise).
La terminologie sur le transport multimodal semble être bien diversifiée en fonction des
aspects du processus de transport mis en avantage. En effet, l’intermodalité se concentre plus
sur l’utilisation d’une même unité de transport, tandis que le transport combiné s’intéresse à la
faible distance parcourue par route, la comodalité met l’accent sur l’optimisation des ressources,
et la synchromodalité cherche une flexibilité dans le choix des modes. Néanmoins, la définition
de base du transport multimodal (section 2.1.1) englobe toutes les autres définitions, du fait
qu’elles se caractérisent toutes par l’utilisation de deux modes de transport ou plus. Dans le
reste de cette thèse, nous utiliserons régulièrement le terme transport multimodal pour faire
référence à toutes ses formes.
12
Chapitre II. Transport Multimodal
Le transport multimodal est un concept qui cherche une coordination efficace entre les
différentes composantes de la chaîne de transport, tout en assurant le mouvement continu de
marchandises le long des meilleurs itinéraires, et en utilisant les moyens les plus efficaces et les
plus rentables. Ce concept est caractérisé par la présence des terminaux intermédiaires (hubs)
où les marchandises sont regroupées et déplacées d'un mode de transport à un autre. De telles
opérations de massification de marchandises sont au cœur du transport multimodal et le
distinguent du tout routier. Dans la littérature, plusieurs configurations de réseaux de transport
multimodal (appelés aussi réseaux de massification) sont possibles :
Point à point : cette structure de réseau représente un système de transport dans lequel
la marchandise est transférée directement depuis son origine vers sa destination, plutôt que de
passer par un hub central. Cette configuration est courante lorsque des commandes spécialisées
ou ponctuelles doivent être satisfaites, ce qui crée souvent des problèmes de charge partielle ou
de retour à vide. Les exigences logistiques d'une telle structure sont minimes, mais au détriment
de l'efficacité.
Corridor : ce type de réseaux est généralement utilisé pour assurer des fortes liaisons
terrestres ou fluviales entre les régions à forte densité et un nœud de collecte où les
marchandises regroupées sont transportées par des moyens de transport plus grands. Tout au
long des corridors, la marchandise peut être chargée ou déchargée dans des centres de
distribution locaux ou régionaux. En France, le corridor de la vallée de Seine (CCI Normandie,
2014) est utilisé pour relier par fleuve la capitale Paris à la façade maritime du port du Havre.
Réseau de routage : cette structure de réseau utilise des circuits où la marchandise peut
être transbordée d'un itinéraire à l'autre dans des hubs spécifiques. On distingue deux types de
réseaux de routage : les réseaux avec routes fixes où les itinéraires sont déterminés à l’avance
et ne changent pas au cours de l’acheminement de marchandises, comme c’est le cas dans le
transport maritime de conteneurs. Et les réseaux avec routes dynamiques qui sont une structure
de réseau complexe qui nécessite un haut niveau d'intégration logistique, car les itinéraires et
les hubs évoluent en fonction des variations anticipées de la demande. Le routage dynamique
est principalement utilisé dans les services de colis du dernier kilomètre, où l'acheminement des
camions de livraison dépend de l'évolution de la demande.
13
Chapitre II. Transport Multimodal
Figure II.6 Différentes configurations de réseaux de transport multimodal (adaptée de Woxenius (2002))
14
Chapitre II. Transport Multimodal
Pour mener à bien ces services, différents types de centres de transbordement ont été
développés au fil des années, qui, en fonction de la nature des échanges modaux, peuvent
généralement être classifiés en cinq types de terminaux.
Dans une gare de triage ferroviaire (Figure II.7), les trains arrivent à un ensemble de voies
de réception, où les wagons sont découplés et poussés sur une bosse. Les wagons sont ensuite
triés dans une zone de classification avant d’être redirigés, via un système de commutateurs de
voies, vers la zone de départ où des trains de grandes distances sont formés. Les gares de triage
ont une longue histoire remontant aux débuts du transport ferroviaire, mais dans ces dernières
années beaucoup ont été mises hors service, en raison des opérations de manœuvre très longues
et de la croissance du transport conteneurisé qui demande des terminaux avec des grandes
capacités de stockage (Boysen et al., 2013).
Figure II.7 Structure d’une gare de triage ferroviaire (source Boysen et al. (2013))
2.3.2. Terminal Rail-Route
Figure II.8 Structure d’un terminal Rail-Route (adapté de Ballis et al. (2002))
15
Chapitre II. Transport Multimodal
pour l'empilage intermédiaire des conteneurs et des voies de camions adjacentes pour un
transbordement immédiat des trains aux camions et vice versa. Les terminaux rail-route sont
devenus l'une des pierres angulaires du fret intermodal pour servir d'interface entre les deux
modes de transport routier et ferroviaire.
Les terminaux de type Rail-Rail sont dédiés à un échange rapide de la marchandise entre
les trains. La structure de ces terminaux (Figure II.9) est très similaire à celle des terminaux
Rail-Route. Lorsque les trains se trouvent en même temps dans le terminal, les opérations de
transbordement sont effectuées directement d’un train vers un autre. Dans le cas où les trains
ne sont pas en même temps dans le terminal, mais qu'ils ont une corrélation d'échange, les
conteneurs sont séquentiellement échangés via les zones de stockages, où des opérations de tris
sont effectuées par des navettes automatiques pour accélérer le chargement final sur les trains
de destination (Macharis and Bontekoning, 2004).
Figure II.9 Structure d’un terminal Rail-Rail (adapté de Cichenski et al. (2017))
Un terminal Trimodal (Figure II.10) présente une interface intermodale intérieure qui
relie les trois modes routier, ferroviaire et fluvial. Les différences principales par rapport à un
terminal Rail-Route sont les suivantes :
16
Chapitre II. Transport Multimodal
Figure II.10 (a) Structure d’un terminal Trimodal et (b) terminal Trimodal de Basel Nord (Suisse)
(Source : [Link])
Les terminaux à conteneurs maritimes (Figure II.11) sont considérés comme les
installations intermodales les plus complexes. C’est le type de terminaux qui implique la gestion
des plus grands flux de conteneurs, et les consommations d'espace et de capital les plus
17
Chapitre II. Transport Multimodal
importantes (Reis et al., 2013). En effet, les terminaux à conteneurs sont les points de
convergence de plusieurs systèmes de transport et constituent une interface entre le mode de
transport maritime et les modes intérieurs. Un terminal à conteneur maritime se compose de
différentes zones desservant chacune un objectif fonctionnel spécifique, en général, on peut
diviser ce type de terminal en quatre zones principales (Meisel, 2009) :
18
Chapitre II. Transport Multimodal
Tableau II.2 Classement des plus grands ports européens en 2015 (source Abourraja (2018))
19
Chapitre II. Transport Multimodal
Tableau II.3 Principaux terminaux intermodaux en Europe
8 voies
Antwerpen Mainhub
Rail-Route 20000 m2 ------------- 3 RMG
(Belgique)
4 Chariots Cavalier
6 voies
Duisburg
Trimodal ------------ 12500 EVP 3 portiques
Meiderich (Allemagne)
2 Reach Stackers
14 voies ferrées
Le Terminal Mutimodal du
Trimodal 650000 m2 30000 EVP 2 RMG
Havre (France)
2 portiques fluviaux
14 voies ferrées
Praque Uhrineves
Rail-Route 420000 m2 17500 EVP 5 RMG
(Tchèque)
7 Reach Stackers
6 voies ferrées
Ceske Trebova (Tchèque) Rail-Route 138000 m2 6000 EVP 3 RMG
4 Reach Stackers
8 voies ferrées
Rail hub terminal Budapest
Rail-Route 140000 m2 20000 EVP 2 RMG
(Hongrie)
4 Reach Stackers
9 voies ferrées
Dunajska Streda
Rail-Route 280000 m2 25000 EVP 3 RMG
(Slovaquie)
10 Reach Stackers
7 voies
5 portiques de grande
Basel Nord
------------ ------------- -------------- taille
(Suisse)
(fluvial+ferroviaire)
3 Reach Stackers
Terminal de Krems An Der 4 voies
Donau Trimodal 35000 m2 10000 EVP 1 portique fluvial
(Autriche) 4 Reach stackers
ICY Intermodal 16 voies
Container Yard Rail-Route 250000 m2 20000EVP 5 RMG
Tczew (Pologne) 5 Reach Stackers
20
Chapitre II. Transport Multimodal
seront pas traités dans cette section, nous référons le lecteur intéressé par ces problèmes aux
états l’art de Vis et al. (2003) et Steenken et al. (2004).
Niveau
stratégique Conception de Localisation
réseau des Hubs
Niveau
tactique Conception des Conception des
terminaux services
intermodaux
Replanification
Niveau des itinéraires
Figure II.12 Classification des différents problèmes dans la chaîne de transport multimodal selon leur niveau de
décision et leur occurrence temporelle.
Dans un réseau de transport multimodal, les biens doivent être acheminés entre les
différents points d'origine et de destination sur un réseau de nœuds et d'arcs ayant une capacité
éventuellement limitée. De plus, à part le coût d'acheminement proportionnel au nombre
d'unités de chaque bien transporté sur une liaison du réseau, un coût fixe doit être payé la
première fois qu’un lien (arc) est utilisé, représentant ses coûts de construction (ouverture) ou
d'amélioration. Le problème général de conception de réseau consiste à trouver une conception
de coût minimal, c'est-à-dire un choix d'arcs dans le réseau qui permettra d’assurer
21
Chapitre II. Transport Multimodal
l’acheminement des flux de marchandises tout en minimisant la somme des coûts fixes
d'inclusion des arcs et des coûts variables de routage (Jaržemskienė, 2007). Ceci passe par deux
étapes, premièrement, il doit être décidé quel type de massification de flux est à utiliser parmi
les structures de réseaux : point-à-point, corridor, hub-and-spoke ou réseau de routage,
présentées dans la section 2.2. Deuxièmement, l'opérateur de réseau doit décider quels sont les
arcs qui seront utilisés pour l’acheminement de marchandises à travers le réseau et quels seront
les nœuds à servir. Il existe deux catégories majeures de problèmes de conception de réseau :
Le Tableau II.4 présente un aperçu des principaux travaux sur le problème de conception
de réseau. Des états d’arts plus détaillés sur le problème sont disponibles dans (Magnanti and
Wong, 1984 ; Minoux, 1989 ; Costa, 2005).
22
Chapitre II. Transport Multimodal
Tableau II.4 Principaux travaux sur le problème de conception de réseau.
contraintes de
contraintes latérales
capacité Approche de
Référence Objectif
Avec Sans résolution
Assignement Budget
Capacité Capacité
Minimiser le coût total de
Holmberg and Relaxation
conception du réseau ✔
Yuan, (1998) lagrangienne
Minimiser le coût de
transport de marchandises Méthode de
Crainic et al.
(2000)
et le coût de création des ✔ simplexe et
arcs Recherche Tabou
Minimiser le coût de
transport de marchandises
Crainic et al. Relaxation
et le coût de création des ✔
(2001) lagrangienne
arcs
Minimiser le coût de
transport et assurer une
Viswanath and
couverture maximale des ✔ ✔ Branch and Bound
Peeta (2003).
demandes
Minimiser le coût de
transport de marchandises
Ghamlouche et
et le coût de création des ✔ Path-Relinking
al. (2004)
arcs
Minimiser le coût de
transport de marchandises
Frangioni and
Gendron (2009)
et le coût de création des ✔ ✔ Branch and Bound
arcs
Minimiser le temps de
Luathep et al. transfert de marchandises Optimisation
✔ ✔
(2011) dans le réseau globale
Une fois que la décision sur le type de réseau a été prise et que les connexions entre les
différents nœuds du réseau ont été déterminées, l’opérateur en charge de la conception du réseau
doit choisir les nœuds qui vont servir comme des centres de massifications de flux « hubs ».
Les hubs sont des installations dans lesquelles les flux de marchandises entrant en petits
volumes sont regroupés, triés et redistribués (repartitionnés) en volumes plus importants aux
destinations finales ou à d’autres hubs dans le réseau. La principale motivation pour déployer
de telles structures de réseau consiste à exploiter des économies d'échelle (en termes de temps
et/ou de coût) en transportant des volumes plus élevés sur des liaisons beaucoup plus efficaces
(hubs de connexion) caractérisées par des faibles coûts de transport (Campbell and O’Kelly,
2012). Dans la littérature, les structures de réseaux de massification sont pour la plupart
configurées en tant que réseaux en étoile « hub-and-spoke». Dans ce cas, le problème de
23
Chapitre II. Transport Multimodal
localisation des hubs comporte deux décisions : (i) le choix et l’ouverture des hubs et (ii) la
quantité de marchandise à transférer sur les connexions nœud-hub et hub-hub pour répondre à
la demande au moindre coût possible.
Une classification des différentes variantes du problème de localisation des hubs dans la
littérature peut être effectuée en se basant sur les caractéristiques suivantes :
Domaine de la solution :
Réseau : la liste des nœuds candidats pour servir comme hubs, est composée de
tous les nœuds du réseau.
Discret : la liste des nœuds candidats pour servir comme hubs, est composée d’un
sous-ensemble de nœuds du réseau.
Continu : les hubs peuvent être localisés aléatoirement dans un plan ou une
sphère.
Fonction objectif :
Min-somme : le coût d’ouverture des hubs plus le coût de transfert est minimisé.
Exogène : le nombre de hubs à localiser est connu à l’avance, il est donné comme
un paramètre du problème.
Nombre de hubs :
Plusieurs hubs : le réseau est composé de p-hubs. L’entier p peut être fixé par un
format exogène ou par un format endogène.
24
Chapitre II. Transport Multimodal
Coût fixe : le coût d'ouverture d'un hub est défini comme un paramètre du
problème.
Allocation unique : chaque nœud peut être affecté seulement à un seul hub.
Le Tableau II.5 présente les principaux travaux sur la localisation des hubs en fonction
de l’objectif considéré, le schéma d’allocation des nœuds aux hubs, le nombre de hubs à
localiser et l’approche de résolution utilisée. Des états d’arts qui couvrent un nombre plus large
de travaux et traitent d’autres aspects du problème sont disponibles dans (Campbell and
O’Kelly, 2012 ; Farhani et al., 2013).
Min-
Nagy and Salhi, Avec
Somme Allocation unique P-hub MIP modélisation
(1998) capacité
Kara and Tansel Min-
Allocation unique Sans capacité P-hub MIP modélisation
(2000) Somme
Ebery (2001) Min-Max Allocation unique Sans capacité P-hub MIP modélisation
Min- Avec
Marin (2005) Allocation multiple P-hub MIP modélisation
Somme capacité
25
Chapitre II. Transport Multimodal
niveau, on distingue principalement deux problèmes : le problème de conception des terminaux
intermodaux et le problème de conception des services.
26
Chapitre II. Transport Multimodal
des conditions d'exploitation spécifiques. Ces équipements peuvent être classés
en des technologies conventionnelles et innovantes. Parmi les engins de
manutention conventionnels, on trouve des équipements classiques utilisés aussi
dans les terminaux à conteneurs, tels que les Reach Stackers, les portiques
ferroviaires et les portiques fluviaux. Dans les dernières années, quelques
technologies innovantes ont été introduites dans certains terminaux pour assurer
une manutention rapide et un degré avancé d'automatisation, à l’image de
Metrocargo Système Italien de manutention (Anghinolfi et al., 2014).
Le Tableau II.6 présente un aperçu sur quelques travaux qui s’intéressent à la conception
des terminaux intermodaux.
27
Chapitre II. Transport Multimodal
Une plateforme de simulation
basée sur les réseaux de Petri a
Développer un outil pour l’évaluation
été développée, cette plateforme
quantitative des différents schémas
Chen et al. (2016) Rail-Route peut être utilisée comme un outil
possibles dans les terminaux Rail-
prédictif pour la conception et la
Route.
gestion des terminaux Rail-
Route.
Les structures de réseaux hub-and-spoke sont les plus étudiés dans la littérature sur le
transport multimodal. Dans ce type de réseaux, la marchandise est transportée par un seul
service, ou une séquence de services avec des échanges entre eux au niveau des terminaux
intermodaux. Un service est caractérisé par son origine, sa destination, les nœuds
intermédiaires, son mode de transport, son itinéraire et sa capacité. De même, un mode est
caractérisé par sa capacité, sa vitesse et son prix. Le problème de conception de réseau de
service comprend toutes les décisions relatives au choix des services de transport et des modes
de déplacement, qui impliquent la détermination de la fréquence du service, l'allocation des
capacités, la planification des équipements et le routage des flux de marchandises. Deux
variantes du problème sont généralement étudiées :
Le Tableau II.7 résume les principaux travaux de littérature sur le problème. Un état de
l’art sur le problème est présenté dans (Crainic, 2000).
Tableau II.7 Aperçu de quelques travaux sur le problème de conception des services
28
Chapitre II. Transport Multimodal
29
Chapitre II. Transport Multimodal
consiste à minimiser les transports à vide, les coûts de stockage et, dans certains
cas, la substitution.
Le Tableau II.8 passe en revue quelques travaux relatifs aux problèmes de gestion de
ressources.
Ce problème vise une réponse optimale à l'évolution du système en temps réel, afin de
maximiser la qualité du service et le profit marginal. Ici, la notion de solution planifiée n'a pas
de sens et toutes les opérations doivent être replanifiées en temps réel (Crainic, 2003). De plus,
un seul modèle ou une seule approche de résolution n'est pas capable de gérer ce problème
complexe. À ce titre, il est nécessaire d'utiliser des combinaisons d'approches, non seulement
30
Chapitre II. Transport Multimodal
d’optimisation, mais en provenance d’autres sciences d’aide à la décision et de l’informatique.
Les systèmes de transport intelligents (Crainic et al., 2009) sont largement utilisés pour la
résolution de ce type de problème, en effet de tels systèmes fournissent des informations
précises en quelques secondes aux opérateurs multimodaux, ce qui réduit considérablement les
degrés d’incertitudes (Harris et al., 2015). Dans (Bock,2010), une approche de contrôle en
temps réel a été introduite pour une consolidation efficace et une gestion dynamique des
perturbations telles que les pannes de véhicule et les accidents. L'externalisation partielle ou
totale des services de transport est également autorisée et les temps de repos pour les
conducteurs de camions ont été pris en considération. Goel (2010) étudie la valeur de
l'utilisation de la technologie RFID et de la visibilité sur les expéditions à travers un réseau de
transport multimodal de routes et de trains à horaires fixes, avec des temps de transit variables.
Dans ce réseau, il y a deux décideurs : un gestionnaire de transport responsable de la
planification des expéditions, et un opérateur de terminal chargé de gérer les écarts imprévus.
Référence Description
Développement d’un système de suivi et de traçabilité intermodal pour faciliter
l’échange des informations et des données utilisées, pour les présenter de manière
uniforme. Plus précisément, l'objectif du travail est de proposer une solution de
Davies et al. (2007)
suivi et de traçabilité des marchandises peu coûteuse, conviviale et applicable aux
niveaux national et international.
Proposition d’un concept de visibilité élargie basé sur une perspective de capacité
de processus et l’approche Six Sigma pour évaluer et améliorer la gestion de la
Lee and Rim (2016)
chaîne de transport.
31
Chapitre II. Transport Multimodal
Le port du Havre a été fondé en 1517 sur l’ordre du roi François 1er pour servir comme
port militaire afin de renforcer les moyens de défense de la région de l'estuaire de la Seine et
protéger les navires français contre les attaques de l’armement anglais. Mais, il s’est vite
transformé après, en un des plus grands ports de commerce européens. Aujourd’hui, le port du
Havre est le leader français en termes de trafic conteneurisé avec plus de 2.6 millions d’EVP
par an. Il bénéficie d’une position géographique très stratégique, située sur la façade occidentale
de l’Europe à l’entrée du range nord-ouest, lui permettant d’être le premier port touché par les
navires océaniques en provenance de l’Asie et le dernier lorsque ces derniers quittent l’Europe.
Il s’étend sur plus de 27 km avec une surface totale de 10 300 hectares (Benghalia, 2015) et
bénéficie de très bonnes conditions d'accès nautique qui le libèrent des contraintes de tirant
d’eau et de marées et lui permettent d’avoir l’avantage d’être accessible 24h/24h 365 jours par
an, et lui offrent la possibilité de recevoir les plus grands porte-conteneurs du monde. Le port
du Havre possède un arrière-pays très riche et diversifié, qui couvre une large portion du
territoire français et contient un des plus grands hubs de commerce mondial qui est la métropole
parisienne. L’arrière-pays du port est desservi par un réseau routier à connexion directe avec le
sud-ouest de la France, la région parisienne ainsi qu'avec l'Espagne et le Portugal ; il est
également relié au port par une voie fluviale (la Seine) et des réseaux ferroviaires électrifiés
nationaux et internationaux. Le trafic conteneurisé est le plus dominant au port du Havre, il
représente plus de 40% du trafic global et affiche le plus grand potentiel de croissance (Hausse
de 14% en 2017 par rapport au trafic de 2016) et apporte le plus de bénéfices. Cette évolution
du trafic conteneurisé est rendue possible grâce à la présence d’infrastructures de très bons
niveaux (Figure II.13), notamment au niveau de ces nombreux terminaux à conteneurs qui sont :
Par ailleurs, au-delà de son activité principale de transport conteneurisé, le port du Havre
rayonne aussi dans d’autres activités commerciales, il est le premier port exportateur de céréales
en Europe de l’Ouest avec plus de 10 millions de tonnes échangées par an et il est considéré
comme le premier bassin pétrochimique de France. Début 2012, Un Groupement d’Intérêt
Économique (GIE) qui réunit, le grand port maritime du Havre, le port de Rouen et le port de
32
Chapitre II. Transport Multimodal
Figure II.13 (a) Plan du Port du Havre (b) Vue sur Port 2000
Paris (HAROPA) a été créé dans le but de répondre au mieux aux besoins de réactivité, de
souplesse, de coordination qu’exige un système de service et de transport efficace de bout en
bout. Cette nouvelle structure accueille aussi diverses parties prenantes telles que : les
collectivités territoriales, la tutelle d’état, les opérateurs de réseaux fluviaux et ferroviaires
(VNF et RFF), les entreprises, les syndicats de salariés et les associations environnementales.
Bien que le port du Havre possède des possibilités de connexion très diversifiées (route,
fleuve, rail) avec son arrière-pays, son attractivité au niveau de l’interaction port-hinterland
reste très faible comparée à ses concurrents Nord européens. En effet, l’activité de transport de
conteneurs depuis/et vers le port est caractérisée par une dominance de la part du mode routier
qui représentait en 2013 plus de 87% du volume de marchandises transportées. Contre
seulement, 8 % pour le fluvial et 5% pour le ferroviaire (Tableau II.10). Ceci générait des coûts
33
Chapitre II. Transport Multimodal
de transport très élevés et des émissions de gaz à effet de serre très importantes. Ces facteurs
diminuaient la performance du port et lui faisaient perdre des grandes parts de marché.
Tableau II.10 Répartition modale en 2013 en % dans les principaux ports Nord européens
Hambourg 69 29 2
Rotterdam 60 9 31
Bremerhaver 40 56 4
Anvers 60 8 32
Le Havre 87 5 8
Pour résoudre ces problèmes et améliorer la compétitivité du port du Havre par rapport à
ses concurrents européens, un terminal multimodal (Figure II.14) a été créé en 2014 à quelques
kilomètres des terminaux maritimes du port du Havre.
Le terminal multimodal est la plus grande plateforme intermodale en France avec une
surface de plus de 65 ha et une capacité de stockage destiné à accueillir plus de 300 000 EVP
par an. Ce terminal joue le rôle d’un grand méga hub qui permet de favoriser l’utilisation des
modes massifiés de transport (ferroviaire et fluvial) et vise à réduire la congestion au niveau
des terminaux maritimes. Dans le nouveau schéma logistique du port du Havre (Figure II.15),
le transfert des conteneurs entre le terminal multimodal et les terminaux maritimes est assuré
par des navettes ferroviaires d'une part. D'autre part, la livraison des conteneurs vers leurs
destinations finales est effectuée par des trains de grandes lignes (TGL), par des barges, ou par
des camions.
34
Chapitre II. Transport Multimodal
Le terminal multimodal est composé de cinq zones (Figure II.16) : une cour fluviale, une
zone de transport interne, une cour ferroviaire, un faisceau de réception et une zone de transport
multi-terminaux.
35
Chapitre II. Transport Multimodal
Zone de transport interne : dans cette zone plusieurs reach stackers sont utilisés
pour exécuter le transfert de conteneurs entre les buffers de la cour ferroviaire et
ceux de la cour fluviale.
Les objectifs visés par la création du terminal multimodal sont très ambitieux, la feuille
de route tracée par le Grand Port Maritime du Havre (GPMH) prévoit une amélioration
considérable de la part des transports massifiés d'ici 2020. Le défi est d'atteindre 14% de rapport
modal pour le mode fluvial (contre 8% en 2014) et 11% pour le mode ferroviaire (contre 5%
en 2014). À terme, 320 000 conteneurs devraient transiter chaque année par le terminal
multimodal, pour un gain environnemental de 500 000 tonnes d'émissions de CO2 par an, par
rapport au mode routier (Garnier, 2015). Néanmoins, atteindre de tels objectifs passe tout
d’abord par une gestion efficace des différentes zones du terminal multimodal. La gestion du
nouveau système logistique au port du havre est laborieuse et implique la résolution de plusieurs
problèmes opérationnels de routage et d'ordonnancement que nous détaillerons dans la section
suivante.
36
Chapitre II. Transport Multimodal
Certains de ces problèmes sont des problèmes classiques au niveau de la littérature sur les
terminaux à conteneurs, et de nombreux travaux ont été consacrés à leurs études. Parmi ces
problèmes, nous mentionnons le problème d'élaboration du plan de chargement/déchargement
de barges (Monaco et al., 2014 ; Ding and Chou, 2015), qui vise à trouver une affectation
préétablie des conteneurs à des emplacements dans les barges tout en tenant compte des poids
de conteneurs et de leurs ports de destination, ce qui permet d'assurer leur stabilité et de
minimiser les mouvements improductifs de portiques lors des opérations de déchargement.
Le problème d'ordonnancement des grues de quai introduit par Dagonzo (1989), et traité
récemment dans (Al-Dhaheri and Diabet, 2015 ; Meisel and Bierwirth, 2011), consiste à
déterminer l'ordre de chargement et de déchargement des conteneurs par les grues de quai dans
le but de minimiser le temps total passé dans le terminal. Généralement, au niveau du terminal
multimodal, les conteneurs sont transbordés directement des barges et des trains de grandes
lignes vers les navettes ferroviaires et inversement. Cependant, parfois, pour accélérer la
manutention des barges ou pour soulager les zones de stockage des terminaux maritimes, les
conteneurs sont stockés d'abord dans le terminal multimodal. Une bonne planification des
opérations de transport des conteneurs entre les parcs de stockage et les autres zones du terminal
multimodal contribue à l'amélioration de la performance du terminal multimodal, la
problématique sous-jacente est l'optimisation des opérations de transport interne dans un
terminal à conteneurs (Bose et al., 2000 ; Ivarez, 2006).
La Figure II.17 classifie les principaux problèmes rencontrés dans la gestion du terminal
multimodal selon les zones concernées. Dans cette thèse, deux de ces problèmes seront traités
à savoir : le problème de tournées des navettes ferroviaires (Chapitre IV) et le problème
d’ordonnancement de grues de quai dans la cour fluviale (Chapitre V).
37
Chapitre II. Transport Multimodal
transport interne
Tournées des navettes ferroviaires
Zone de transport interne
5. Conclusion
Dans un premier temps, nous avons établi le contexte général de cette thèse, en présentant
une vue d’ensemble sur les différentes composantes et possibles formes d’organisations d’une
chaîne de transport multimodal, en attachant une attention particulaire aux problèmes de
planification et de gestion rencontrés. Un état de l’art détaillé, d’un point de vue de
l'optimisation, sur ces problèmes a été présenté et une classification en trois niveaux stratégique,
tactique et opérationnel de ces problèmes a été proposée. Ensuite, nous avons décrit le terminal
multimodal du port du havre, qui représente le cas d’étude de ce travail. Une description
détaillée des différentes parties de ce terminal et des opérations de transfert et de manutentions
de conteneurs a été établie, tout en portant une attention particulaire aux différents problèmes
d’optimisation qui doivent être résolus pour améliorer la performance du terminal.
38
Chapitre II. Transport Multimodal
En résumé, la gestion des opérations de transfert et de manutention de conteneurs dans le
terminal multimodal du port du havre est laborieuse et cela s’explique par plusieurs facteurs,
entre autres, la nature dynamique et distribuée de cette plateforme, la diversité de ses opérations,
et l’incertitude et le manque d’information. En effet, souvent dans le nouveau schéma logistique
du port du Havre, des données comme les temps de déplacement entre les terminaux à
conteneurs, les temps de manutention et/ou les positions initiales de conteneurs sont objets
d’incertitudes causées par un mauvais temps, des pannes, un mauvais chargement des
conteneurs, ou des changements de dernières minutes. Ces incertitudes qui portent sur les
données ont une influence sur la qualité des solutions trouvées dans le cas déterministe, et
généralement une bonne solution trouvée sans considérer ces perturbations devient très
mauvaise ou même infaisable en leur présence. Bien qu'une attention considérable ait été
accordée dans la littérature aux différents problèmes de planifications et de gestion dans la
chaîne de transport multimodal, à notre connaissance, très peu de travaux ont étudié ces
problèmes avec prise en compte des incertitudes. Fort de tout ce qui précède, nous avons
proposé, dans ce qui suit, des approches capables de gérer les différentes sources d’incertitudes
au niveau du terminal multimodal. Mais avant d’aborder les solutions proposées, il est
primordial d’étudier les différents paradigmes et approches d’optimisation utilisés dans la
littérature pour étayer la prise de décision face aux incertitudes. Le chapitre suivant fournit un
état de l’art sur ces approches.
39
Chapitre II. Transport Multimodal
40
Chapitre III. Optimisation sous Incertitudes
Chapitre III
Optimisation Sous Incertitudes
Sommaire
1. Introduction ................................................................................................................. 41
2. Techniques d’Optimisation sous Incertitudes ............................................................ 44
2.1. Optimisation Stochastique ............................................................................................. 45
2.2. Optimisation par Ensembles Flous .................................................................................. 47
2.4. Analyse de Sensibilité ..................................................................................................... 49
2.5. Fonctions de Croyance ................................................................................................... 50
3. Optimisation Robuste : Généralités et Applications au Transport Multimodal ......... 51
3.1. Critères de Robustesse ................................................................................................... 52
3.1.1. Robustesse Absolue .................................................................................................................... 52
3.1.2. Regret Maximal ........................................................................................................................... 52
3.1.3. Regret Relatif .............................................................................................................................. 53
3.1.4. α-Robustesse .............................................................................................................................. 53
3.1.5. 𝑏𝑤-Robustesse ........................................................................................................................... 53
3.1.6. Exemple Numérique ................................................................................................................... 54
41
Chapitre III. Optimisation sous Incertitudes
42
Chapitre III. Optimisation Sous Incertitudes
1. Introduction
À cet égard, le présent chapitre fournit un aperçu général sur les différents paradigmes et
approches d’optimisation utilisés dans la littérature pour étayer la prise de décision face aux
incertitudes. En particulier, le présent chapitre vise à présenter un état de l’art sur les
applications des approches d’optimisation sous incertitudes dans le transport multimodal, plus
particulièrement, la résolution des problèmes de gestion des terminaux à conteneurs.
Le reste de ce chapitre est organisé comme suit. La prochaine section expose les
principales approches d’optimisation sous incertitudes qui existent dans la littérature, à savoir :
l’optimisation stochastique, l’optimisation par ensembles flous, l’optimisation robuste,
l’analyse de sensibilité, les fonctions de croyance et les approches de couplage entre la
simulation et l’optimisation. Ensuite, nous mettrons l’accent sur les approches qui seront
utilisées dans cette thèse. Ainsi, dans la section 3 nous donnerons une description détaillée de
l’optimisation robuste, où nous présenterons les principaux critères de robustesse appliqués
dans la littérature et nous décrirons les différents ensembles et modèles d’incertitudes existants.
Nous introduirons à la fin de cette section le principe de la Pareto robustesse et nous
présenterons un état de l’art sur les applications de l’optimisation robuste pour la résolution des
problèmes de transport multimodal. Nous consacrerons la section 4, à l’étude des approches de
couplage entre la simulation et l’optimisation. Nous commencerons par une présentation des
différents paradigmes de couplage possibles ; ensuite, nous donnerons dans cette section une
brève description des différentes méthodes d’optimisation et de simulation qui peuvent être
utilisées. Nous terminerons la section par un état d’art sur les applications des approches de
couplages dans le transport multimodal et dans la gestion des terminaux à conteneurs. Enfin, la
section 5 conclut ce chapitre.
43
Chapitre III. Optimisation Sous Incertitudes
Figure III.1 Illustration de l’influence des incertitudes sur la qualité des solutions
Dans la littérature, les approches traitant de l'optimisation sous incertitudes ont suivi au
fil des années une variété de philosophies de modélisation, qui peuvent être classifiées selon les
trois catégories suivantes (Roy, 2010) :
44
Chapitre III. Optimisation Sous Incertitudes
Les approches a posteriori : dans ces approches, des solutions pour le problème
d’optimisation initial (déterministe) sont d’abord calculées, en utilisant des
méthodes classiques d’optimisation déterministe. Une fois les solutions calculées,
l’influence des perturbations des paramètres d’entrée sur la qualité de ces
solutions est étudiée. Un exemple d’approche a posteriori le plus connu est
l’analyse de sensibilité.
Les approches a priori : dans ces approches, les incertitudes sur les données
d’entrée sont intégrées dans la formulation initiale du problème. Le but de ces
approches est de trouver la meilleure solution qui protège au mieux contre les
perturbations. Les incertitudes sont prises en considération au cours du processus
d’optimisation et la solution trouvée par ces approches est une solution optimale
(ou approchée) du problème d’optimisation sous incertitudes.
En pratique, les approches en ligne sont rarement utilisées puisque la prise de décision
doit être établie en avance, pour permettre la mise en œuvre des solutions, bien avant le moment
où les données seront connues. Ainsi, il est préférable d’utiliser les approches a priori et a
posteriori pour gérer les perturbations sur les données d’entrées des systèmes étudiés, afin
d’obtenir des solutions préalables qui seront efficaces pour faire face aux futurs perturbations
possibles. Dans ce contexte, plusieurs types de ces approches ont été développés dans la
littérature pour guider le décideur lors de la prise de décisions sous incertitudes telles que :
l’optimisation stochastique, l’optimisation robuste, l’analyse de sensibilité, l’optimisation par
ensembles flous, les fonctions de croyance et la simulation-optimisation.
45
Chapitre III. Optimisation Sous Incertitudes
l’espérance. En conséquence, dans la théorie d’optimisation sous incertitude, la
programmation stochastique est souvent considérée comme une approche basée
sur des scénarios et les formulations des problèmes sont effectuées en plusieurs
niveaux de décision, selon l'ordre dans lequel les incertitudes se manifestent.
Chaque niveau implique une représentation temporelle discrète du problème et
établit les informations sur les paramètres incertains disponibles au moment de
son occurrence. La formulation la plus simple ne tient compte que des décisions
qui sont prises avant que l'incertitude ne se révèle. Ce type de formulation est
appelé programmation stochastique avec un seul niveau de décision ou
programmation stochastique sans recours (Grossmann et al., 2016).
Une description plus détaillée des différents paradigmes d’optimisation stochastique est
disponible dans le tutoriel proposé par (Shapiro and Philpott, 2007) et dans les travaux de (Birge
and Louveaux, 1997) et (Sahinidis, 2004). Le Tableau III.1 présente quelques travaux qui
utilisent l’optimisation stochastique pour la résolution des problèmes de transport multimodal
sous incertitudes.
46
Chapitre III. Optimisation Sous Incertitudes
Tableau III.1 Aperçu sur l’utilisation de l’optimisation stochastique dans les problèmes de transport multimodal
CCP : Programmation stochastique avec contraintes probabilistes (Chance Constrained Programing (CCP)), TSP : Programmation stochastique avec recours
(Stochastic programming with recourse or Two Stage Programming (TSP)).
47
Chapitre III. Optimisation Sous Incertitudes
nombres flous et les contraintes sont traitées comme des ensembles flous (Buckley and Eslami,
2002). Certaines violations de contraintes sont autorisées et le degré de satisfaction d'une
contrainte est défini comme la fonction d'appartenance de la contrainte. Deux types de
programmation par ensembles flous peuvent être distingués : la programmation flexible
consacrée à l’étude des incertitudes sur le second membre des contraintes et la programmation
possibiliste qui traite les incertitudes dans les coefficients de la fonction objectif ainsi que dans
les coefficients des contraintes. Dans les deux types de programmation floue, la fonction
objectif est traitée comme une contrainte du problème, et les bornes inférieures et supérieures
de cette contrainte définissent les attentes des décideurs. Les fonctions d'appartenance sont
utilisées pour représenter le degré de satisfaction des contraintes et les niveaux d’attentes des
décideurs vis-à-vis de la fonction objectif.
Le lecteur intéressé par plus de détails sur l’optimisation par ensembles flous peut se
référer à (Luhandjula and Gupta, 1996), (Ross, 2009) et (Lodwick and Untiedt, 2010). Le
Tableau III.2 présente quelques applications de l’optimisation par ensembles flous dans les
problèmes de transport multimodal.
Tableau III.2 Quelques applications de l’optimisation par ensembles flous dans les problèmes de transport
multimodal
Référence Description
Proposition d’un modèle multi-objectif pour résoudre le problème de sélection des
fournisseurs et détermination des quantités de commandes optimales à attribuer à
Yücel and Güneri (2011)
chaque fournisseur.
48
Chapitre III. Optimisation Sous Incertitudes
L’analyse de sensibilité est l’une des approches a posteriori pour l’optimisation sous
incertitudes. Elle consiste à étudier l’impact des perturbations des données d’entrée d’un
problème sur la qualité des solutions obtenues par des méthodes classiques d’optimisation.
L’analyse de sensibilité ne vise pas à résoudre le problème sous incertitudes, mais à analyser le
comportement des solutions déjà obtenues face aux perturbations des données, en mettant en
évidence les liens entre les entrées et les sorties du système étudié. En effet, il s’agit d’une
analyse a posteriori de la stabilité des solutions déterministes pour déterminer les données
d’entrées dont les incertitudes sur leurs valeurs génèrent la plus grande dégradation au niveau
de la valeur de la fonction objectif. En optimisation combinatoire, on peut distinguer deux types
d’approches principales :
Le Tableau III.3 présente un aperçu sur les applications de l’analyse de sensibilité dans
les problèmes de transport multimodal de conteneurs.
Tableau III.3 Aperçu sur les applications de l’analyse de sensibilité dans les problèmes de transport multimodal
Référence Description
Comparaison de la performance des chariots cavaliers et des portiques automatisés
dans la manutention de conteneurs, en considérant les incertitudes sur les temps de
Vis (2006)
déplacement des engins de manutention et sur les dates d’arrivée des conteneurs.
Proposition d’un modèle linéaire pour trouver les conditions économiques optimales
pour une coopération efficace entre les ports du Bangladesh et de l'Inde, au niveau
du trafic intermodal. Une analyse de sensibilité prenant en compte les incertitudes
Munim and Haralambides (2018)
sur les capacités et les demandes des différents ports considérés est également
utilisée afin d'établir la robustesse des décisions stratégiques qui pourraient être
prises.
49
Chapitre III. Optimisation Sous Incertitudes
La théorie des fonctions de croyance, également appelée théorie des preuves ou théorie
de Dempster-Shafer (DST), est un cadre général pour raisonner sous incertitudes, avec des liens
compréhensibles avec d'autres domaines comme la probabilité, la théorie de possibilité et la
théorie de probabilité imprécise. D'abord introduite par Arthur Pentland Dempster (Dempster,
1967) dans le contexte de l'inférence statistique, la théorie a été ensuite utilisée par Glenn Shafer
(Shafer, 1976) pour la modélisation de l'incertitude. La théorie des fonctions de croyance est un
cadre riche et flexible généralisant l’inférence bayésienne au traitement de l’incertain, elle
permet de représenter explicitement les incertitudes sur les données en exprimant parfaitement
ce qui est déjà connu et en prenant en compte ce qui reste à connaître. Le modèle le plus utilisé
dans la théorie des fonctions de croyance est le Modèle des Croyances Transférables (MCT ou
en anglais TBM pour Transferable Belief Model) (Smets and Kennes, 1994), dans ce modèle il
s’agit de surveiller, enregistrer et transmettre des nouvelles connaissances à partir
d’informations observées. Le Modèle des Croyances Transférables différencie deux niveaux de
raisonnement :
Le niveau crédal : du latin “credo” voulant dire “je crois”, qui est constitué de
deux parties : une partie statique pour la représentation des informations et une
partie dynamique permettant d’observer et de combiner les connaissances.
La théorie de fonctions de croyance a été appliquée dans plusieurs travaux traitant des
divers domaines, tels que : la reconnaissance des formes (Appriou, 1991) et la diagnostique
(Smets, 1998). Mais peu de travaux de la littérature ont été consacrés à ses applications aux
problèmes de transport multimodal.
Bien que les quatre premières approches présentées dans ce chapitre aient été largement
utilisées dans la littérature pour la gestion des incertitudes et notamment pour la résolution de
plusieurs problèmes de transport multimodal, leur application en pratique est souvent très
difficile, surtout si l'on ne peut pas déterminer avec précision les lois de probabilité ou les degrés
d’appartenance associés aux données incertaines. Ceci est particulièrement important dans des
nouvelles applications réelles, comme dans notre cas d’étude, où il n'y a pas assez d’historiques
sur les données qui peuvent permettre de faire ces estimations. Comme alternatives à ces
approches, les techniques d’optimisation robuste et de couplage simulation optimisation sont
de plus en plus utilisées pour faire face aux incertitudes lorsqu’il s’agit des problèmes réels.
Dans ce qui suit, nous présenterons ces deux approches de façon approfondie.
50
Chapitre III. Optimisation Sous Incertitudes
L'optimisation robuste est une approche qui vise à trouver une solution dite "Robuste" à
des problèmes d'optimisation dans lesquels les données sont incertaines sans avoir recours à
une analyse probabiliste. Introduite dès 1955 par Dantzig (Dantzig, 1955), l'idée de robustesse
a connu un regain d’intérêt durant les dernières décennies avec de nombreuses applications à la
fois de la part des praticiens et des théoriciens (Remili et al., 2012). Contrairement aux
approches stochastiques, l’optimisation robuste modélise les données incertaines en utilisant
des ensembles continus ou discrets de valeurs possibles, sans probabilité attachée. Dans le cas
continu, les ensembles d’incertitudes sont souvent représentés par des intervalles et des
ensembles convexes (i.e. polyèdre, box ou ellipsoïde), en se basant sur les déviations minimales
et maximales des paramètres incertains par rapport à leurs valeurs nominales. Dans le cas
discret, on parle de modèles à base de scénarios, où les valeurs possibles des paramètres
incertains sont modélisées par un ensemble fini discret de scénarios avec une même probabilité
d'occurrence. Dans les deux cas, c’est le produit cartésien des ensembles d’incertitudes
considérées qui définit les instances possibles du problème étudié. Plusieurs définitions d’une
“solution robuste” circulent dans la littérature ; dans cette thèse, nous adopterons celle
proposée par Gabrel and Murat (2010). Selon ces auteurs, une solution est qualifiée de robuste
si elle est “acceptable” dans tous les scénarios possibles et si sa performance n’est jamais “trop
mauvaise”. Une approche d’optimisation robuste consiste alors à définir la meilleure stratégie
qui permet de se protéger contre les différentes réalisations possibles des incertitudes, tout en
minimisant la valeur du pire cas sur toutes les solutions possibles. De ce fait, il est important,
lorsqu'on recourt à une approche robuste, de bien identifier le contexte dans lequel l'étude est
faite. Selon Kouvelis and Yu (1997), l’implémentation d’une approche d’optimisation robuste
comprend trois étapes principales :
ii. Sélection d’un critère de robustesse approprié (i.e. robustesse absolue, regret
maximal, regret relatif, α-robustesse, 𝑝-robustesse, etc.)
Dans le reste de cette section, nous présenterons les principaux critères de robustesse
appliqués dans la littérature. Nous décrirons ensuite les différents ensembles utilisés en
optimisation robuste pour modéliser les incertitudes sur les données et nous expliquerons le
principe de Pareto robustesse. Enfin, quelques applications de l'optimisation robuste à la
résolution des problèmes de transport multimodal seront exposées.
51
Chapitre III. Optimisation Sous Incertitudes
Plusieurs critères de robustesse ont été élaborés dans la littérature pour mesurer la qualité
des solutions robustes. Ces critères peuvent être divisés selon (Aloulou et al., 2005) en deux
grandes familles :
Nous présentons, ci-après, une brève description de quelques critères représentatifs de ces
deux familles.
Une solution robuste, selon ce critère, est la meilleure solution au pire des cas sur tous les
scénarios possibles. Considérons un problème de minimisation d’une fonction objectif 𝑓, avec
𝑋 l’ensemble de solutions possibles de ce problème, et 𝑆 l'ensemble de tous les scénarios. Le
critère de robustesse absolue est défini par la relation suivante :
Ce critère est souvent lié à la notion de risque où les décideurs cherchent à se protéger
contre les pertes générées par un grand changement des données. Nombreux sont les travaux
qui utilisent ce critère comme mesure de robustesse, nous mentionnons les travaux sur le plus
court chemin robuste traité dans (Yu and Yang, 1998) et dans (Gabrel and Murat, 2010) et
l'application au problème de sac à dos robuste (Kouvelis and Yu, 1997).
Le regret est le sentiment de perte ressenti par un décideur quand il apprend l’existence
d’une solution plus préférable sur un scénario donné que celle qui était réellement appliquée.
Une solution robuste, selon le critère de regret maximal, est celle qui présente le plus petit pire
écart aux solutions optimales sur tous les scénarios possibles. En effet, le regret est défini en
optimisation robuste comme étant la différence entre la valeur d'une solution et la valeur de la
solution optimale sur le même scénario, et le regret maximal est le regret le plus élevé d'une
solution sur tous les scénarios. Une solution robuste est alors la solution dont le regret maximal
est le plus petit. Ce critère est défini par la relation suivante :
52
Chapitre III. Optimisation Sous Incertitudes
Où x ∗ ∈ X est la solution optimale sur le scénario s ∈ S et f(x ∗ , s) est sa valeur sur le même
scénario.
Le principe du regret relatif est presque semblable à celui du regret maximal, la seule
différence réside dans le fait qu’on remplace, dans la définition du regret, la minimisation des
écarts absolus entre les solutions et les valeurs optimales par la minimisation des pourcentages
de déviation. La relation utilisée pour représenter le regret relatif est la suivante :
f(x, 𝑠) − f(x ∗ , s)
min max
x∈X s∈S f(x ∗ , s)
La famille des approches à base d’optimisation du critère de pire des cas, présentée ci-
dessus, est généralement considérée dans la littérature comme une famille de critères très
conservatrice. En effet, étudier la notion de robustesse en se basant sur ce critère conduit
souvent à privilégier un seul aspect qui est la protection contre les pires scénarios, même s’il
est très improbable, en pratique, que tous les paramètres incertains atteignent leurs valeurs les
plus élevées simultanément. D’autre part, une solution qui protège contre les réalisations au
pire des cas est robuste, mais elle est très mauvaise lorsqu’elle est appliquée dans d'autres
scénarios.
3.1.4. 𝛂-Robustesse
Cette approche a été présentée pour la première fois par Aloulou et al. (2005), comme
une alternative moins conservatrice aux approches d’optimisation à base du critère de pire des
cas, pour des problèmes où les données incertaines sont modélisées à l'aide de scénarios
discrets. Dans ce critère, un paramètre 𝛼 définit un seuil de tolérance pour limiter le degré de
conservatisme d'une solution. Au début de cette approche, les valeurs de chaque solution x ∈ 𝑋
sur l’ensemble des scénarios S sont classées par ordre décroissant, et le vecteur obtenu est
appelé “vecteur de désutilité” de la solution x. Ensuite, un vecteur de désutilité fictif pour une
solution x′ appelée “solution idéale”, dont les coordonnées représentent les coûts minimaux
sur chaque ligne de la matrice des vecteurs de désutilités, est calculé. Une solution robuste selon
cette approche est toute solution dont l’écart entre son vecteur de désutilité et le vecteur de
désutilité fictif ne dépasse pas le seuil de tolérance α.
3.1.5. 𝒃𝒘-Robustesse
Pour Roy (2010) la robustesse est définie comme une aptitude à résister à des “à peu
près” ou à des “zones d’ignorance” afin de se protéger d’impacts jugés regrettables sur tous
les scénarios possibles. Selon l’auteur, les approches min-max classiques ne permettent pas de
répondre totalement à cette question, puisqu'elles se concentrent uniquement sur la
minimisation du pire des cas. Pour pallier cet inconvénient, Roy a proposé un nouveau critère
de robustesse qu’il a appelé la bw-robustesse. Dans cette approche deux paramètres sont utilisés
: une constante w qui définit la valeur que le décideur ne veut pas dépasser dans tous les
53
Chapitre III. Optimisation Sous Incertitudes
scénarios (le respect de cette valeur doit être garantie et représente une contrainte ferme du
problème), et une valeur 𝑏, avec 𝑏 ≤ w (pour un problème de minimisation), que le décideur
veut atteindre sous le plus grand nombre (ou proportion) de scénarios. En d’autres termes, si
f(x, 𝑠) est la valeur d’une solution x sur le scénario 𝑠, alors la solution robuste selon le critère
de 𝑏𝑤-robustesse est la solution x qui maximise le nombre de scénarios pour lesquels f(x, 𝑠) ≤
𝑏, tout en assurant que f(x, 𝑠) ≤ 𝑤 ∀𝑠 ∈ 𝑆. À l'instar des critères de la famille min-max, la 𝑏𝑤-
robustesse peut être présentée aussi sous la forme de robustesse absolue, de regret ou de regret
relatif.
D’autres critères de robustesse ont été aussi utilisés dans la littérature pour déterminer la
qualité d’une solution robuste, tels que : la p-robustesse, le min-max lexicographique, la pw-
robustesse, etc. Un état de l’art sur ces critères est présenté dans (Coco et al., 2014).
Scénarios
Solutions
s1 s2 s3 s4
x5 90 90 220 210
Critères
Solutions
Robustesse Absolue Regret maximal Regret relatif
(min-max absolue) (min-max regret) (min-max regret relatif)
x1 180 90 100%
x2 180 50 55.55%
x3 190 90 100%
x5 220 50 29.41%
Les résultats des critères de pire des cas (Tableau III.5) montrent que les solutions x1 et
x2 sont les meilleures solutions pour le critère de la robustesse absolue puisqu’elles offrent les
54
Chapitre III. Optimisation Sous Incertitudes
coûts maximums les moins élevés. Tandis que, la solution x2 et x5 sont les meilleures solutions
pour le critères de regret maximal, et la solution x5 est la meilleure solution pour le critère de
regret relatif, puisqu’elle génère les déviations les plus faibles par rapport aux valeurs optimales
sur chaque scénario.
Pour la 𝑏𝑤-robustesse qui, rappelons-le, définit les solutions robustes comme l’ensemble
des solutions qui maximisent le nombre de scénarios avec une valeur de fonction objectif
inférieure ou égale à une valeur 𝑏, tout en garantissant que sur tous les scénarios la valeur ne
dépasse pas un seuil 𝑤. On obtient les résultats suivants :
Pour un grand seuil 𝑤 ≥ 220 et une valeur souhaitée 𝑏 = 150 : toutes les
solutions respectent le seuil définit, et les solutions robustes sont x2 et x5 dont le
nombre de scénarios, où la valeur de la fonction objectif est inférieure à 150, est
égal à 2. Par contre, si 𝑏 = 130, la seule solution robuste est x5 .
Enfin, le Tableau III.6 rapporte les résultats du critère de l’α-robustesse qui se base dans
le calcul des solutions robustes sur l’écart entre les vecteurs de désutilité 𝐶̂ (x) des solutions et
le vecteur de désutilité fictif 𝐶̂ (x′) :
Pour un seuil 90 ≤ 𝛼 < 110 : toutes les solutions restent robustes sauf la solution
x4 .
55
Chapitre III. Optimisation Sous Incertitudes
min 𝑐x
𝑠𝑐 𝐴x ≤ 𝑏
x∈X
Sans perte de généralité nous supposons, dans ce qui suit, que seuls les coefficients de la
matrice A sont objet d’incertitudes, et que leurs valeurs appartiennent à un ensemble 𝒰 appelé
ensemble d’incertitudes. Dans la littérature, quatre principales formes d'ensembles
d'incertitudes peuvent être distinguées :
Ellipsoïdal : pour réduire le degré de conservatisme dans les ensembles par Box,
Ben-Tal et Nemirovski (1998) ont proposé un ensemble alternatif appelé
l'ensemble d'incertitudes ellipsoïdale. Cet ensemble introduit un paramètre Ω qui
permet de réduire l'espace d'incertitude en supprimant les extrémités des
intervalles et éviter ainsi le pire des cas. Cet ensemble est donné par la relation
suivante :
2
𝒰𝐸 ={𝑎̃𝑖𝑗 | 𝑎̃𝑖𝑗 = 𝑎𝑖𝑗 + 𝜀𝑖𝑗 𝑎̂𝑖𝑗 , ∑𝑗 𝜀𝑖𝑗 ≤ Ω2𝑖 ∀i}
56
Chapitre III. Optimisation Sous Incertitudes
Polyédrique : introduit par Bertisimas and Sim (2004), ce type d’ensembles vise
à assurer un compromis entre la robustesse et la performance des solutions en
proposant une modélisation paramétrable des données incertaines. Cet ensemble
utilise un paramètre Γ appelé budget de robustesse pour contrôler le nombre de
données qui seront objet d’incertitudes :
La Figure III.2 représente la différence entre les ensembles d’incertitudes par box,
ellipsoïdal et polyédrique pour un problème avec deux paramètres incertains. En se basant sur
ces différents ensembles, plusieurs approches de modélisation robuste ont été proposées dans
la littérature, à savoir : l’approche de Soyster, l’approche de Ben-Tal et Nemirovski et
l’approche de Bertsimas et Sim.
Figure III.2 Illustration des ensembles d’incertitudes les plus utilisés (adaptée de Jalilvand-Nejad et al.(2016))
Soyster (1973) a proposé un modèle d'optimisation linéaire pour construire une solution
réalisable pour toutes les réalisations d’incertitudes appartenant à l’ensemble par box 𝒰𝐵 . Le
modèle robuste de Soyster a été formulé comme suit :
min 𝑐x
𝑛
𝑠𝑐 ∑ 𝑎̃𝑖𝑗 𝑥𝑗 ≤ 𝑏 ∀ 𝑎̃𝑖𝑗 ∈ 𝒰𝐵 , 𝑖 = 1, … , 𝑚
𝑗=1
x∈X
Cette formulation est également connue sous le nom de formulation d'incertitude relative
aux colonnes. Cette approche, à l’image des critères min-max, vise à se protéger contre le pire
des cas. En outre, Soyster montre que pour des problèmes où les variables 𝑥𝑗 ne sont pas
négatives le modèle précédent est équivalent à :
57
Chapitre III. Optimisation Sous Incertitudes
min 𝑐x
𝑛
L’approche de Soyster est une garantie absolue contre toutes les réalisations possibles
d’incertitudes, elle ramène la résolution du problème sous incertitudes à la résolution d’un
problème déterministe dont tous les paramètres incertains prennent leurs valeurs au pire des
cas. Cependant, malgré la garantie de faisabilité qu’offre cette approche pour toutes les
réalisations d'incertitudes, elle est souvent jugée très conservative dans la littérature. En effet,
Ben Tal and Nemnirovski (1999) soulignent qu'en raison de la protection contre le pire des cas,
il y a une énorme perte d'optimalité sur les autres scénarios.
Pour pallier les inconvénients de l’approche de Soyster, Ben-Tal and Nemirovski (1999)
ont proposé une nouvelle approche basée sur l’utilisation de l’ensemble d’incertitudes
ellipsoïdal 𝒰𝐸 . Cette approche diminue le degré conservatisme en autorisant une faible
violation des valeurs au pires des cas sur les contraintes. En effet, sur chaque contrainte i du
problème, les paramètres aléatoires 𝜀𝑖𝑗 qui définissent les valeurs de déviations maximales sont
2
supposés appartenir à un ensemble 𝐸(Ω𝑖 ) = {𝜀𝑖𝑗 | ∑𝑗 𝜀𝑖𝑗 ≤ Ω2𝑖 , 𝜀𝑖𝑗 ∈ [−1,1]} et la modélisation
robuste correspondante est donnée par :
min cx
n
Ce modèle d’incertitudes est aussi connu dans la littérature par le nom “modèle en ligne”,
du fait qu’un paramètre Ω𝑖 est défini pour contrôler le degré de conservatisme sur chaque
contrainte i du problème étudié.
Bertsimas and Sim (2004) ont proposé une approche similaire à l’approche de Ben-Tal et
Nemirovski dans le but de trouver un compromis entre la performance des solutions et leur
robustesse. La différence entre les deux approches réside uniquement dans l’ensemble
d’incertitudes considéré. En effet, l’approche de Bertismas et Sim est basée sur l’ensemble
d’incertitudes polyédrique en supposant que les paramètres aléatoires 𝜀𝑖𝑗 sont définis sur un
ensemble de la forme 𝜙𝑖 (Γ𝑖 ) = {𝜀𝑖𝑗 | ∑𝑛𝑗=1|𝜀𝑖𝑗 | ≤ Γ𝑖 , 𝜀𝑖𝑗 ∈ [−1,1]} . Le modèle robuste
correspondant à cette approche est donné par :
58
Chapitre III. Optimisation Sous Incertitudes
min cx
n
Cette approche est également connue sous le nom “approche avec budget de robustesse”
puisqu’elle a recours à un paramètre Γ qui contrôle le nombre de données qui seront objet
d’incertitudes. Ainsi, une solution robuste selon l’approche de Bertsimas and Sim est définie
comme une solution qui protège contre toutes les situations dans lesquelles au plus les valeurs
de Γ𝑖 coefficients sur chaque contrainte i du problème étudié sont perturbés.
Ordóñez and Zhao (2007) ont étudié le problème de conception de réseaux de transport
avec des incertitudes sur les temps de déplacements et sur les demandes. Les auteurs proposent
59
Chapitre III. Optimisation Sous Incertitudes
une formulation robuste du problème basée sur l’utilisation de l’ensemble d’incertitudes
polyédriques. Mudchanatongsuk et al. (2008) ont considéré un problème similaire avec des
coûts de transport et des demandes incertains. Deux formulations robustes, à base d’ensembles
polyédrique et ellipsoïdal, ont été développées et une approche de génération de colonnes a été
proposée pour résoudre la relaxation lagrangienne sur les grandes instances. Dans (Pishavee et
al., 2011), les auteurs ont traité un problème de conception de réseau en boucle avec des
incertitudes sur les coûts et les demandes. Un modèle déterministe a été d’abord développé pour
concevoir le réseau, ensuite, la contrepartie robuste du modèle a été proposée en utilisant
l’approche de Ben-Tal et Nemirovski. Les qualités des solutions obtenues par le modèle
déterministe et celles obtenues par le modèle robuste ont été comparées sur plusieurs scénarios
et avec différents jeux de données.
Les problèmes de localisation des hubs sous incertitudes ont été également largement
étudiés dans la littérature, un état de l’art complet sur ces problèmes est disponible dans (Correia
and da Gama, 2015). Récemment, Merakh et Yaman (2016) ont étudié le problème de P-hub
avec allocation multiple et demandes incertaines. Les auteurs utilisent un modèle d'incertitude
de tuyau et un modèle hybride pour caractériser les incertitudes sur la demande. Le premier
considère que la seule information disponible est une limite supérieure du débit total adjacent
à chaque nœud, tandis que le dernier incorpore des limites inférieure et supérieure sur chaque
flux Origine/Destination. Les auteurs présentent des formulations robustes et un algorithme de
décomposition de Benders pour résoudre les deux problèmes pour des instances allant jusqu'à
150 nœuds. Ghaderi and Rahmaniani (2016) ont traité le problème de P-hub avec allocation
unique et incertitudes sur les demandes et les temps de manutention. Le problème robuste est
modélisé avec l’objectif de minimisation du critère de regret maximal et des métaheuristiques
hybrides sont proposées pour le résoudre. Zetina et al. (2017) ont présenté des contreparties
robustes au problème de localisation des hubs sans capacité en se basant sur l’approche de
Bertsimas et Sim. Trois cas de réalisation des incertitudes ont été considérés : (1) les incertitudes
sur les demandes, (2) les incertitudes sur les coûts de transport et (3) les deux sources
d’incertitudes en même temps. Pour chaque cas, une formulation robuste a été présentée et
résolue en utilisant un algorithme de Branch-and-Cut.
Au niveau des terminaux intermodaux, Bruns et al. (2014) ont étudié le problème de
détermination des plans de chargement des trains en considérant différents types d'incertitudes.
Deux approches ont été présentées pour inclure les incertitudes : des plans de chargement
robustes stricts, dans lesquels il est supposé que la solution ne peut pas être changée une fois
implémentée, et des plans de charge robustes et ajustables qui permettent au planificateur de
réagir une fois que les paramètres incertains deviennent connus. Les formulations robustes
associées aux deux approches permettent une résolution efficace du problème. Fotuhi and
Huynh (2017) ont proposé un nouveau modèle robuste basé sur le critère de regret maximal
pour l'extension d'un réseau intermodal. L’objectif du modèle est d'identifier les liaisons
ferroviaires critiques à moderniser, les emplacements pour établir des nouveaux terminaux
intermodaux, et les terminaux existants à développer, tout en prenant en compte les incertitudes
60
Chapitre III. Optimisation Sous Incertitudes
sur les demandes. Un algorithme génétique hybride qui utilise la génération de colonnes pour
déterminer les flux de fret a été développé pour résoudre le modèle proposé.
Shang et al. (2016) ont proposé une application intéressante de l’optimisation robuste
pour la résolution conjointe des problèmes d’allocation de poste à quai et d’ordonnancement de
grues de quai dans un terminal maritime. Les auteurs ont considéré les incertitudes sur les dates
d’arrivée des navires et sur les temps de manutentions de conteneurs. Le problème a été
modélisé suivant l’approche de Bertsimas et Sim, et un algorithme génétique a été proposé pour
la résolution des grandes instances.
61
Chapitre III. Optimisation Sous Incertitudes
nombreuses classifications de ses approches ont été proposées en se basant sur plusieurs
critères :
Carson and Maria (1997) ont classifié les approches de couplage entre la
simulation et l’optimisation selon les techniques d’optimisation employées (i.e.
les approches de gradient, les heuristiques ou des techniques statistiques).
Quelques logiciels de simulation et des applications réelles du couplage ont été
également présentés dans cet état de l’art.
Figuera and Almada-Lodo (2014) ont proposé un état de l’art sur les approches
de couplage Simulation-Optimisation qui couvre plusieurs critères négligés dans
la littérature. La classification proposée par les auteurs se base sur quatre
dimensions : i) l’objectif de la simulation, (ii) la structure hiérarchique du
couplage, (iii) les approches d’optimisation et de simulation utilisées et (iv) le
schéma de recherche employé. Les deux premières dimensions sont liées à
l'interaction entre la simulation et l'optimisation. Alors que les deux autres
concernent la conception de l'algorithme de recherche.
Les différents objectifs visés par la composante simulation distinguent les principales
formes d’usages des approches de couplage Simulation-Optimisation dans la littérature. En
effet, en se basant sur ce critère, on peut distinguer trois objectifs du couplage :
62
Chapitre III. Optimisation Sous Incertitudes
Optimisation avec des itérations basées sur la simulation : dans tous (ou une
partie) des itérations du processus d'optimisation, une ou plusieurs exécutions de
la simulation sont effectuées.
Simulation avec des itérations basées sur l'optimisation : dans tous (ou une
partie) des itérations du processus de simulation, une ou plusieurs exécutions d’un
algorithme d'optimisation sont effectuées.
63
Chapitre III. Optimisation Sous Incertitudes
La Figure III.3 représente les différences entre ces quatre structures de couplage.
64
Chapitre III. Optimisation Sous Incertitudes
Méthodes exactes : ce sont des méthodes qui permettent une résolution complète
du problème ciblé en arrivant à une solution optimale (par exemple : l’algorithme
de Branch-and-Bound, l’algorithme Branch-and-Cut, la méthode de génération de
colonnes, etc.).
65
Chapitre III. Optimisation Sous Incertitudes
Pendant plusieurs décennies, la simulation a été utilisée comme un outil descriptif par la
communauté de recherche opérationnelle pour la modélisation et la description d'une grande
variété de systèmes réels complexes. Mais avec les progrès récents de la technologie
informatique, les approches de couplage Simulation-Optimisation ont reçu une grande attention
dans la littérature, et ont été utilisées comme des outils d'aide à la décision permettant la
résolution de ces systèmes. Dans cette section, nous présentons un aperçu des applications de
la Simulation-Optimisation dans la résolution des problèmes de transport multimodal, en
mettant surtout l’accent sur leur utilisation dans la gestion des terminaux à conteneurs.
Truang and Azadivar (2003) ont proposé une approche Simulation-Optimisation pour la
configuration d’une chaîne logistique. Ce problème consiste à prendre des décisions
stratégiques sur l'emplacement des centres de production, l'emplacement des centres de
stockage, la politique de production, la capacité de production, la politique de distribution et les
modes de transport à utiliser. Un modèle linéaire en nombres entiers et un algorithme génétique
ont été développés pour déterminer les variables qualitatives du problème et la politique de
production et de distribution à suivre. Quant à la simulation, elle évalue la performance des
solutions de l’optimisation sous des hypothèses plus réalistes. Ding et al. (2005) ont développé
une nouvelle méthodologie de couplage Simulation-Optimisation pour faciliter l'évaluation et
la sélection des fournisseurs dans une chaîne de production. L’approche proposée comprend
trois modules de base : une simulation à événements discrets, un algorithme génétique et un
cadre de modélisation de la chaîne d'approvisionnement. Les configurations possibles des
fournisseurs ont été sélectionnées puis validées sur la base des indicateurs de performance. Ko
et al., (2006) ont présenté une approche Simulation-Optimisation pour concevoir un réseau de
distribution pour les services logistiques tiers, en tenant compte de la performance des
entrepôts. Le modèle d'optimisation utilise un algorithme génétique pour déterminer les
66
Chapitre III. Optimisation Sous Incertitudes
structures de réseau de distribution dynamique. Par la suite, le modèle de simulation est
appliqué pour capturer les incertitudes au niveau des demandes des clients, les temps de
préparation des commandes et les temps de déplacement. Une approche basée sur le couplage
Simulation-Optimisation a été développée dans (Vidović et al., 2011) pour la résolution d’un
problème de localisation des terminaux intermodaux en Serbie. Le modèle d'optimisation est
basé sur une formulation mathématique du problème de p-hub, et la simulation a été utilisée
pour estimer les volumes de transport intermodal, en raison du manque de fiabilité et de
l'indisponibilité de données statistiques, et comme méthode d'analyse quantitative des effets
économiques, temporels et environnementaux de différents scénarios possibles. Gambardella
et al., (2001) ont présenté une approche de couplage Simulation-Optimisation pour les
problèmes d'allocation des ressources et d'ordonnancement de la manutention de conteneurs
dans un terminal intermodal. Les deux problèmes ont été formulés mathématiquement et résolus
hiérarchiquement, et la faisabilité des solutions a été vérifiée par un modèle de simulation à
base d'événements discrets. Dong and Song (2009) ont considéré le problème conjoint de
dimensionnement de la flotte de conteneurs et de repositionnement des conteneurs vides dans
les systèmes d'expédition multi-navires/multi-ports avec des demandes de clients dynamiques,
incertaines et déséquilibrées. Un outil basé sur le couplage Simulation-Optimisation est
développé pour optimiser la taille du parc de conteneurs et la politique de repositionnement des
conteneurs vides. Dans le processus d'optimisation, un algorithme génétique et une stratégie
évolutive associés à un mécanisme d'ajustement ont été utilisés. Un autre algorithme génétique
basé sur l’évaluation par simulation a été proposé dans (Dong et al., 2012) pour résoudre le
problème de positionnement des conteneurs vides dans une zone portuaire avec plusieurs
dépôts, et des demandes de clients et des dates de retour des conteneurs aux dépôts qui sont
objets d’incertitudes.
8 7 7
6
6 5
4 4
4 3
2
2 1 1 1 1
0 0 0
0
-2 1998199920002001200220032004200520062007200820092010201120122013201420152016
Année
Figure III.7 Nombre d’articles traitant de la Simulation-Optimisation pour la gestion des terminaux à conteneurs
par année (1998-2016)
67
Chapitre III. Optimisation Sous Incertitudes
Tableau III.4 Aperçu sur les principales applications des approches Simulation-Optimisation dans la gestion de
terminaux à conteneurs maritimes
Optimisation avec
Simulation à
Lagana et des itérations Différentes
Allocation des postes et événements
al., (2006) basées sur la Recuit Simulé réalisations pour
des grues de quai discrets
simulation chaque solution
Simulation à
Chang et Simulation- Modèle linéaire + Une réalisation
Allocation des postes à événements
al., 2008 Optimisation plusieurs pour chaque
quai discrets
Séquentielle heuristiques solution
Zeng and Simulation- Simulation à
Ordonnancement des Modèle linéaire + Différentes
Yang Optimisation événements
opérations de chargement Algorithme réalisations pour
(2009) discrets
de conteneurs Alternée Génétique chaque solution
Optimisation avec
des itérations Simulation à Différentes
Legato et Ordonnancement des
basées sur la Recuit Simulé événements réalisations pour
al. (2010) grues de quai
simulation discrets chaque solution
Simulation avec
Gestion des ressources des itérations Simulation à Réalisations
Bruzzano Algorithme
dans un terminal à basées sur événements communes pour
et al., 2012 Génétique
conteneurs l'optimisation discrets chaque solution
Optimisation avec
He et al., Partage de camions des itérations Simulation à Réalisations
Algorithme
2013 internes entre plusieurs basées sur la événements communes pour
Génétique
terminaux à conteneurs simulation discrets chaque solution
Optimisation avec
Algorithme de
des itérations Différentes
Legato et Allocation des postes à recherche en Simulation de
basées sur la réalisations pour
al., 2014 quai faisceau + Recuit Monte-Carlo
simulation chaque solution
Simulé
Optimisation avec
des itérations Simulation à Réalisations
Zhou et al., Conception de la zone de
basées sur la Modèle linéaire événements communes pour
2016 stockage de conteneurs
simulation discrets chaque solution
Simulation avec
des itérations Différentes
Abourraja Ordonnancement des Optimisation par Simulation
basées sur réalisations pour
et al. 2017 grues ferroviaires colonies de fourmis multi-agents
l'optimisation chaque solution
5. Conclusion
68
Chapitre III. Optimisation Sous Incertitudes
Ces deux approches seront utilisées dans la suite de cette thèse pour faire face aux
différentes sources d’incertitudes sur les données, au niveau des problèmes d’optimisation dans
le terminal multimodal du Havre. Le chapitre suivant est dédié à la résolution du problème de
tournées de navettes ferroviaires sous incertitudes au niveau du port du Havre.
69
Chapitre III. Optimisation Sous Incertitudes
70
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
Chapitre IV
Optimisation des Tournées de Navettes
Ferroviaires
Sommaire
1. Introduction ................................................................................................................. 73
2. Travaux Antérieurs sur le Transfert de Conteneurs au Port du Havre ....................... 74
3. Problème de Tournées de Véhicules Robuste............................................................. 75
4. Problème de Tournées de Navettes Ferroviaires ........................................................ 79
4.1. Description et Modélisation Déterministe ...................................................................... 79
4.2. Résultats Initiaux............................................................................................................ 80
4.3. Modélisation Robuste .................................................................................................... 82
5. Résolution par l’Algorithme d’Optimisation par Colonies de Fourmis ...................... 84
5.1. Schéma Général ............................................................................................................. 85
5.2. Génération des Réalisations ........................................................................................... 86
5.3. Recherche d’une Solution ............................................................................................... 86
5.4. Vérification de la Robustesse ......................................................................................... 88
5.5. Évaluation au Pire des Cas .............................................................................................. 89
6. Expériences Numériques ............................................................................................ 90
6.1. Génération des Jeux de Données .................................................................................... 90
6.2. Réglage des Paramètres de l’Algorithme ........................................................................ 91
6.3. Résultats ........................................................................................................................ 91
6.4. Mesures de la Robustesse .............................................................................................. 94
6.5. Choix du Niveau d'Incertitudes le Plus Pertinent ............................................................ 95
7. Conclusion ................................................................................................................... 98
71
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
72
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
2. Introduction
Le transport maritime occupe une place importante dans les mouvements internationaux
de conteneurs. En effet, aujourd'hui, plus de 90% de marchandises sont transportées par voie
maritime. Cette part importante est rendue possible grâce à la standardisation des conteneurs et
l'accroissement de la taille de la flotte mondiale des porte-conteneurs passée de 3000 unités
(porte-conteneurs) en 2004 à près de 5100 unités en 2014, pour une capacité totale qui dépasse
les 17.5 millions EVP (UNCTAD, 2014). Cette évolution s’est accompagnée d’une accélération
du transfert de marchandises et d’une réduction des coûts de transport, mais a également
soulevé des défis pour les manutentionnaires qui voient leurs zones de stockage de plus en plus
congestionnées. Pour répondre à ces défis, le port du Havre a construit un terminal multimodal
à quelques kilomètres de ses terminaux maritimes pour leur servir de hub ; avec l'objectif de
libérer les zones de stockage de ces terminaux et réduire les émissions des gaz à effet de serre
liées à l’utilisation du transport routier (voir Section 4.2 du Chapitre II pour plus de détails sur
le terminal multimodal). Actuellement, au port du Havre, le transfert de conteneurs entre le
terminal multimodal et les terminaux maritimes est effectué par des navettes ferroviaires
suivant un principe de mouvement en NORIA. En effet, chaque navette ferroviaire se compose
d'une locomotive et d'une rame (un ensemble de wagons) (Figure IV.1). Selon le principe de
mouvement en NORIA, le transfert de conteneurs entre le terminal multimodal et chaque
terminal maritime est géré indépendamment. En d'autres termes, les déplacements des
locomotives entre les terminaux maritimes ne sont pas autorisés, et à chaque moment, une
locomotive qui transfère une rame depuis le terminal multimodal vers un terminal maritime,
soit récupère une rame à destination du terminal multimodal au terminal maritime d'arrivée, si
une rame est disponible, soit attend au terminal maritime jusqu'à la disponibilité d'une rame ou
bien retourne au terminal multimodal.
73
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
Dans ce chapitre, nous étudions le transfert de conteneurs par navettes ferroviaires entre
le terminal multimodal et les terminaux maritimes du port du Havre, que nous désignons par le
problème de tournées des navettes ferroviaires (ou en anglais : The Rail Shuttle Routing
Problem (RSRP)). L'objectif de ce travail est de proposer une approche d'optimisation
définissant des nouvelles règles de transfert de conteneurs entre le terminal multimodal et tous
les terminaux maritimes, et qui permet de faire face aux différentes sources d’incertitudes sur
les données d’entrée.
Le reste de ce chapitre est structuré comme suit. Dans la section suivante, nous
présenterons les travaux antérieurs relatifs à la gestion du transfert de conteneurs dans le port
du Havre suivi, dans la section 3, par un état de l’art sur le problème de tournées de véhicules
robuste où nous positionnerons notre travail par rapport à la littérature existante et nous
montrerons sa contribution. Dans la section 4, nous donnerons une description détaillée du
problème de tournées des navettes ferroviaires et nous expliquerons ses similitudes avec le
problème de tournées de véhicules. Ensuite, nous proposerons une modélisation déterministe
du problème et nous comparerons les résultats de cette modélisation et les résultats du principe
de mouvement en NORIA. Nous présenterons une modélisation robuste du problème dans la
section 5 et nous proposerons une nouvelle approche d’optimisation par colonies de fourmis
pour sa résolution dans la section 6. Dans la section 7, nous évaluerons la robustesse de
l’approche proposée sur plusieurs niveaux d’incertitudes. Enfin, dans la section 8 nous
concluons ce chapitre.
74
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
Les travaux antérieurs sur le problème de transfert de conteneurs se sont limités à l'étude
du transfert de conteneurs entre deux terminaux sans tenir compte des incertitudes, et leurs
résultats étaient caractérisés par des taux de déplacements à vide de locomotives très importants.
Par conséquent, l'objectif principal du travail que nous présentons dans ce chapitre est d’étendre
les études précédentes pour inclure tous les terminaux à conteneurs, ainsi que de minimiser les
taux de déplacements improductifs, en proposant des règles alternatives au principe de
mouvement en NORIA. Pour répondre à ces objectifs, nous avons modélisé dans le cas
déterministe, le problème de tournées des navettes ferroviaires (Rail Shuttle Routing Problem
(RSRP)) comme un problème de tournées de véhicules (Vehicle Routing Problem (VRP)) (Prins,
2004) en considérant que les rames représentent des nœuds à visiter, les temps de transfert
représentent des temps de service et les temps de déplacement à vide représentent les temps de
déplacement entre les nœuds. Nous appliquerons des fenêtres de temps sur les dates de
disponibilité des rames pour permettre uniquement le transfert des rames totalement remplies
et pour respecter les délais de livraison. Cela nous permettra de bénéficier des avantages des
deux modes : massifié et planifié, en termes de minimisation des émissions de CO2 et de
protection contre les retards. Notre deuxième objectif, consiste à garantir un haut niveau de
protection contre les incertitudes sur les temps de transfert des rames et sur les temps de
déplacement à vide des locomotives. Ces incertitudes sont introduites dans la modélisation en
utilisant l'approche de Bertsimas et Sim (2004). Notre approche de résolution du RSRP sous
incertitudes combine une métaheuristique d'optimisation par colonies de fourmis et des
techniques statistiques. En effet, bien qu'il soit très fréquent dans le port du Havre d'avoir des
incertitudes qui diminuent la qualité des solutions trouvées dans le cas déterministe, à notre
connaissance, aucune formulation similaire de ce problème n'a été étudiée auparavant.
Cependant, comme le problème déterministe peut être vu comme un problème de VRP et que
la contrepartie incertaine du RSRP est formulée en utilisant une technique d’optimisation
robuste, les références les plus proches dont nous disposons sont celles sur le problème de
tournées de véhicules robuste (Robust Vehicle Routing Problem (RVRP)) (Sungur et al., 2008 ;
Salano-Charris et al., 2016).
75
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
section, une revue de littérature sur le problème de tournées de véhicules robuste et nous
positionnons notre contribution par rapport aux travaux existants.
76
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
demandes incertaines. Le problème a été d'abord modélisé dans le cas déterministe en utilisant
une formulation de type Miller-Tucker-Zemlin. Ensuite, le modèle proposé a été adapté au cas
incertain en utilisant les approches robustes de Ben-Tal et al. (1999), Bertsimas and Sim (2004)
et une approche stochastique. Les trois modèles obtenus ont été résolus en utilisant la méthode
de Branch-and-Cut et leurs résultats ont été comparés. Le VRP avec capacité et des coûts de
déplacement incertains a été étudié par Toklu et al. (2013). Les incertitudes ont été modélisées
en se basant sur l'approche robuste de Bertsimas et Sim (2004) et un algorithme d’optimisation
par colonies de fourmis a été proposé pour résoudre le problème. Cette approche a été adaptée
dans (Toklu et al., 2014) pour résoudre le VRP avec fenêtres de temps et des temps de
déplacement incertains. Salano-Charris et al. (2015) ont proposé quatre metaheuristiques pour
la résolution du problème de VRP avec capacité et des coûts de déplacements incertains. Les
incertitudes ont été modélisées sous la forme d'un ensemble de scénarios, où chaque scénario
correspond à l’affectation d'un coût de déplacement possible à chaque arc. Un critère de
robustesse min-max lexicographique a été utilisé pour déterminer la meilleure solution qui
protège contre le pire des cas possibles, mais aussi qui reste meilleure sur les autres cas. La
performance des solutions trouvées par les quatre approches proposées a été comparée en
utilisant des instances de 10 à 100 clients.
Certains travaux ont été consacrés au problème de VRP avec des temps de déplacements
incertains. Lee at al. (2012) se sont intéressés à l'étude du VRP avec date au plus tard, temps de
déplacement incertains et demandes incertaines. Un modèle robuste basé sur l’approche de
Bertsimas and Sim (2004) a été proposé, et une méthode de Branch-and-Price a été développée
pour sa résolution. Les incertitudes ont été encapsulées dans le sous-problème de génération de
colonnes qui a été résolu en adaptant une version de l'algorithme d'étiquetage proposé dans
(Irnich et al., 2005). La robustesse de cette approche a été testée sur plusieurs scénarios générés
par l'outil de simulation Monte-Carlo. Agra et al. (2013) ont proposé deux formulations
robustes pour le problème de VRP avec fenêtres de temps et des temps de déplacement
incertains. La première étend la formulation des inégalités de ressources et la deuxième
généralise la formulation des inégalités de chemins. Certaines techniques permettant de réduire
le nombre de points extrêmes ont été développées et la performance des modèles proposés a été
testée sur un cas réel en transport maritime. Han et al. (2013) ont traité le problème de VRP
avec date limite et des temps de déplacement incertains. La violation de la limite de temps a été
pénalisée et une approche basée sur des scénarios robustes a été proposée ; cette approche
consiste à considérer pour chaque arc une série d'intervalles de temps de déplacement possible
et des probabilités de choisir chacun d'eux, un scénario est défini quand un intervalle est
sélectionné pour chaque arc. Une solution robuste est donnée en minimisant le coût au pire des
cas sur tous les scénarios considérés. Un algorithme de Branch-and-Cut a été proposé pour
résoudre le problème et les tests ont été réalisés sur deux types d'instances : sur une version
adaptée des instances de Salomon (1987) et sur des instances générées aléatoirement.
77
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
Tableau IV.1 Résumé de la littérature sur le problème de tournées de véhicules robuste (RVRP)
Localisation des
Ensemble d’incertitudes Paramètre incertain Approche d’optimisation
incertitudes
Variante de Temps
Références Bertsimas Ensemble Coût de
VRP Ben-tal et de Temps de
and Sim de Objectif Contraintes Demande déplace Exacte Heuristique
al. (1999) déplace- service
(2003) scénarios -ment
ment
Sungur et al. (2008) CVRP
* - - - * * - - - B&C -
Ce travail VRPTW
- * - * * - * - * - ACO
CVRP : Problème de tournées de véhicules avec capacité ; VRPD : Problème de tournées de véhicules avec dates au plus tard ; HVRP : Problème de tournées de véhicules avec flotte hétérogène ;
VRPTW : Problème de tournées de véhicules avec fenêtres de temps ; VRPTL : Problème de tournées de véhicules avec limite de temps ;
B&C : Branch and Cut ; PSO : Optimisation par essaim de particules ; LS : Recherche locale ; ACO : Optimisation par colonies de fourmis ; ILS : Recherches locales itérées ; MS-ILS : Multi Starts-ILS ;
78
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
Le Tableau IV.1 résume l’état de l’art présenté dans cette section et montre que même si
plusieurs travaux ont été consacrés à l'étude des variantes du problème de RVRP, la plupart des
études ont uniquement pris en compte les incertitudes relatives à un seul paramètre. Ce travail
est, à notre connaissance, le premier qui traite un problème de RVRP avec fenêtres de temps,
en considérant que les temps de déplacement et les temps de service sont tous les deux
incertains.
𝑙
𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 ∑ ∑ 𝑡𝑖𝑗 𝑥𝑖𝑗 (𝐼𝑉. 1)
𝑙∈𝐿 𝑗∈𝑅′
79
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
Sous les contraintes :
𝑙
∑ ∑ 𝑥𝑖𝑗 = 1 ∀𝑖 ∈ 𝑅 (𝐼𝑉. 2)
𝑙∈𝐿 𝑗∈𝑅′
∑ 𝑥𝑟𝑙0 𝑗 = 1 ∀𝑙 ∈ 𝐿 (𝐼𝑉. 3)
𝑗∈𝑅
𝑙
∑ 𝑥𝑖𝑗 − ∑ 𝑥𝑗𝑖𝑙 = 1 ∀𝑖 ∈ 𝑅, ∀𝑙 ∈ 𝐿 (𝐼𝑉. 4)
𝑗∈𝑅′ 𝑗∈𝑅′
𝑙
∑ 𝑥𝑖𝑟0
=1 ∀𝑙 ∈ 𝐿 (𝐼𝑉. 5)
𝑖∈𝑅
𝑎𝑖 ≤ 𝑠𝑖𝑙 ≤ 𝑏𝑖 ∀𝑖 ∈ 𝑅, ∀𝑙 ∈ 𝐿 (𝐼𝑉. 7)
𝑙
𝑥𝑖𝑗 ∈ {0,1} , 𝑠𝑖𝑙 ≥ 0 ∀𝑖, 𝑗 ∈ 𝑅′ , ∀𝑙 ∈ 𝐿 (𝐼𝑉. 8)
Les tournées des locomotives ainsi que l'ordre de transfert des rames sont définis par la
𝑙
variable binaire 𝑥𝑖𝑗 , qui prend la valeur 1 si et seulement si le transfert de la rame 𝑗 suit le
transfert de la rame 𝑖 sur la locomotive 𝑙. Les dates de début de transfert des rames par les
locomotives sont déterminées par les variables 𝑠𝑖𝑙 . La fonction objectif est exprimée par
l'expression (IV.1), qui consiste à minimiser le temps total des déplacements à vide effectués
par les locomotives. Les contraintes (IV.2) assurent que chaque rame est transférée par une
seule locomotive. Les contraintes (IV.3), (IV.4), et (IV.5) représentent les contraintes de
conservation de flux. Les contraintes (IV.6) garantissent la cohérence temporelle des tournées.
Le respect des fenêtres de temps est exprimé par les contraintes (IV.7). En fin, les contraintes
(IV.8) désignent les domaines des variables de décision.
Dans cette section, les résultats du modèle proposé, qui définit un nouveau schéma de
transfert des conteneurs dans le port du Havre en autorisant les déplacements directs des
locomotives entre les terminaux maritimes (i.e. sans retour au terminal multimodal), sont
comparés aux résultats du principe de mouvement en NORIA actuellement utilisé dans le port
du Havre, où seuls les mouvements de locomotives entre le terminal multimodal et chaque
terminal maritime sont autorisés. Les tests sont réalisés à l'aide du solveur CPLEX 12.6 sur sept
instances générées à partir des temps de parcours réels entre les terminaux à conteneurs du port
du Havre ; il s'agit notamment des temps de parcours entre le Terminal Multimodal, le Terminal
Atlantique, le Terminal de France et le Terminal Porte Océan. Pour simuler le principe du
mouvement en NORIA, nous avons supposé que les temps de parcours entre les terminaux
maritimes sont très importants afin d’interdire les déplacements des locomotives entre ces
80
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
terminaux. La notation instX-Y-Z est utilisée pour caractériser les instances : X représente le
nombre de rames à transférer, Y définit le nombre de locomotives disponibles et Z indique le
nombre de terminaux à conteneurs considérés. Le Tableau IV.2 présente un exemple d’instance
du RSRP composé de dix rames, deux locomotives et trois terminaux à conteneurs.
Tableau IV.2 Exemple d’une instance de RSRP composée de dix rames, deux locomotives et trois terminaux à
conteneurs (inst10-2-3)
Numéro de la rame 1 2 3 4 5 6 7 8 9 10
Terminal de départ (Di) 2 0 0 2 2 1 0 1 0 1
Terminal d’arrivée (Ai) 0 2 2 0 0 0 2 0 1 0
Date au plus tôt (ai) 310 910 10 400 700 350 70 401 920 256
Date au plus tard (bi) 500 1440 165 650 900 900 300 656 1440 400
Temps de Terminal
0 87 86
déplacement entre Multimodal
les terminaux Terminal
87 0 81
Maritime1
Terminal
86 81 0
Maritime2
Les résultats présentés dans le Tableau IV.3 montrent que la nouvelle modélisation, qui
autorise les déplacements entre les terminaux maritimes, permet de réduire considérablement
le temps total de déplacement à vide des locomotives. L'amélioration obtenue sur toutes les
instances est supérieure à 34.35% et l'amélioration moyenne est de 88.04%. En outre, pour les
instances inst10-2-3 et inst20-4-3, le modèle proposé a trouvé des solutions réalisables (i.e.
solutions sans violation des contraintes de fenêtres de temps) même quand un petit nombre de
ressources (i.e. locomotives) a été utilisé, contrairement au principe de mouvement en NORIA
qui nécessite l'utilisation de plus de ressources pour respecter les fenêtres de temps.
Tableau IV.3 Comparaison des résultats de la modélisation mathématique et ceux de l’approche en NORIA
Amélioration = [Résultats du principe en NORIA – Résultats de la modélisation mathématique] ×100/ Résultats de la modélisation mathématique
81
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
Il est fréquent au port du Havre que les temps de déplacement entre les terminaux à
conteneurs augmentent en raison d’un mauvais temps, des pannes ou d’un chargement instable
des conteneurs sur les rames ; ces incertitudes influencent la qualité des solutions trouvées dans
le cas déterministe et en général, les bonnes solutions calculées sans tenir compte de ces
perturbations deviennent très mauvaises, voire infaisables, en leur présence (Mirjalili and
Lewis, 2016). À titre d'exemple, dans la solution optimale de l’instance inst10-2-3 trouvée par
CPLEX (Figure IV.2), les dates de début de transfert de la rame 6 et de la rame 9 coïncident
avec leurs dates de transfert au plus tard, ainsi même une petite perturbation sur les temps de
transfert des rames ou sur les temps de déplacement à vide des locomotives peut rendre la
solution fournie par le solveur infaisable.
Dans cette solution, les rames : rame3, rame10, rame1, rame8 et rame6, sont transférées
par la locomotive 1 dont les dates : 10, 256, 429, 602 et 775, respectivement. Et les rames :
rame7, rame4, rame5, rame2 et rame9, sont transférées par la locomotive 2 dans les dates : 70,
400, 700, 1268 et 1440. Les flèches présentent les itinéraires des locomotives et indiquent
l'ordre dans lequel le transfert des rames est effectué ; les flèches pleines sont utilisées pour
représenter les tâches de transfert des rames tandis que les flèches pointillées indiquent les
déplacements à vide des locomotives.
82
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
Comme mentionné dans le chapitre précédent, l’optimisation robuste offre un bon moyen
pour faire face aux incertitudes sur les données, sans avoir recours aux distributions de
probabilité. Ceci est très adapté à la résolution de notre problème où nous ne possédons pas un
historique suffisant qui nous permet de faire appel à une approche stochastique. De ce fait, nous
modélisons le problème en utilisant l’approche robuste de Bertsimas and Sim (2004), cette
approche contrôle la quantité de données incertaines en introduisant un paramètre appelé le
degré de robustesse (ou budget de robustesse) pour trouver des bonnes solutions pour tous les
scénarios possibles avec une garantie élevée de faisabilité. En nous basant sur cette approche,
nous supposons que les temps de transfert et les temps de déplacement à vide sont incertains,
et qu'ils prennent leurs valeurs respectivement dans les intervalles [𝑃𝑖 , 𝑃𝑖 + 𝛿𝑖 ] et [𝑡𝑖𝑗 , 𝑡𝑖𝑗 +
𝛥𝑖𝑗 ] , où 𝑃𝑖 et 𝑡𝑖𝑗 représentent les valeurs nominales, 𝛿𝑖 et 𝛥𝑖𝑗 représentent les déviations
maximales. Nous définissons également les ensembles d'incertitudes associées à ces temps par
:
𝑙 𝑙
𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 ∑ ∑ 𝑡𝑖𝑗 𝑥𝑖𝑗 + max ∑ ∑ 𝛥𝑖𝑗 𝑥𝑖𝑗 (𝐼𝑉. 1′)
{Ψ / Ψ⊂𝐸,|Ψ|=Γ}
𝑙∈𝐿 𝑖,𝑗∈𝑅′ 𝑙∈𝐿 (𝑖,𝑗)∈Ψ
∀𝑖 ∈ 𝑅′ , ∀𝑗 ∈ 𝑅, ∀𝑙 ∈ 𝐿, ∀𝜃 ⊂ 𝑅, |𝜃| = Λ, ∀Ψ ⊂ 𝐸, |Ψ| = Γ
minimiser (𝐼𝑉. 1′ )
𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶ (𝐼𝑉. 2)(𝐼𝑉. 3)(𝐼𝑉. 4)(𝐼𝑉. 5)(𝐼𝑉. 6′ )(𝐼𝑉. 7) 𝑎𝑛𝑑 (𝐼𝑉. 8)
où 𝜃 et Ψ représentent respectivement l'ensemble des noeuds et des arcs qui seront objet
d’incertitudes. 𝜈𝑖𝜃 et 𝜇𝑖𝑗
Ψ
sont deux fonctions indicatrices, 𝜈𝑖𝜃 prend une valeur égale à 1 quand
Ψ
𝑖 ∈ 𝜃 et 𝜇𝑖𝑗 prend la valeur 1 si (𝑖, 𝑗) ∈ Ψ. La fonction objectif (IV.1') vise à minimiser les
83
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
temps de déplacement improductifs des locomotives parmi tous les cas où les temps de parcours
à vide de Γ arcs sont autorisés à changer et un écart supplémentaire Δ𝑖𝑗 est ajouté à leurs valeurs
nominales 𝑡 𝑖𝑗 . Les contraintes (IV.6') assurent que la cohérence temporelle des tournées est
respectée quels que soient les Γ arcs et les Λ nœuds objet d’incertitudes.
La contrepartie robuste du RSRP est plus difficile à résoudre que la version déterministe,
même pour des problèmes de taille moyenne, car le nombre de réalisations possibles pour un
degré de robustesse (Λ, Γ) donné, peut être très grand. Par exemple, une solution pour un
problème avec 20 rames (nœuds) et 2 locomotives (véhicules) va être composée de 20 + 2 = 22
arcs. Ainsi, pour un degré de robustesse où Λ = ⌊20/10⌋ et Γ = ⌊22/2⌋, le nombre de nœuds
et d'arcs objet d’incertitudes est respectivement égale à 2 et 11, et la contrepartie robuste du
RSRP cherche la meilleure solution qui protégera contre ces augmentations (incertitudes) quels
que soient les 2 nœuds et les 11 arcs qui seront objet d'incertitudes (i.e. ∀θ⊂R, | θ | = 2 and
∀Ψ⊂E, | Ψ | = 11). Ce qui revient à vérifier (20
2
) = 190 possibilités sur les nœuds et (22
11
)=
705432 possibilités sur les arcs, et donne un total de 190 × 705432 = 134032080 scénarios. En
comparant les modèles déterministes et robustes, nous voyons que le nombre de contraintes de
type (IV.6) est égal à |R| × |R′ | × |L| = 840 contre |R| × |R′ | × |L| × (|R|
Λ
) × (|R|×|L|
Γ
)=
112586947200 de type (IV.6') dans la version robuste, ce qui montre que la complexité du
problème augmente en passant de la modélisation déterministe à sa contrepartie robuste.
De plus, la contrepartie robuste n'est pas linéaire, par conséquent, elle ne peut pas être
résolue directement avec les solveurs standards. C'est pourquoi nous avons choisi de résoudre
le problème en utilisant une métaheuristique d’optimisation par colonies de fourmis.
L’optimisation par colonies de fourmis (Ant Colony Optimization (ACO)) a été initiée par
Dorigo (1999). Cette métaheuristique est inspirée du comportement des fourmis dans la vie
réelle. Dans leur procédure de recherche de nourriture, les fourmis commencent par explorer la
zone entourant leur nid aléatoirement ; puis, en revenant au nid, elles déposent une substance
appelée phéromone. Les phéromones guident les autres fourmis vers le point cible, et les trajets
empruntés par plusieurs fourmis seront plus intéressants pour les fourmis suivantes. Cependant,
les quantités de phéromones s'évaporent avec le temps si elles ne sont pas renforcées, et
puisqu'il faut plus de temps pour voyager sur les chemins longs, l'intensité des phéromones dans
les chemins les plus courts devient plus élevée, ce qui favorise leurs choix lors des prochaines
itérations.
L'ACO est souvent utile pour résoudre les problèmes combinatoires grâce à ses capacités
d'exploration dynamiques et d'apprentissage (El Khoukhi et al., 2016). Cela est particulièrement
vrai lorsqu'elle est appliquée à des problèmes dynamiques et incertains, où seule une partie de
l’information sur les données est disponible (Dorigo and Stutzle, 2002). L'ACO a été appliquée
avec succès à la résolution de plusieurs variantes de VRP caractérisées par le manque
d’information, telles que le VRP dynamique (Montemanni et al., 2005, Messaoud et al., 2013),
84
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
le VRP stochastique (Kenyon et al. 2013, Bianchi et al., 2006) et le VRP robuste (Toklu et al.,
2013).
Dans cette section, nous proposons une approche robuste d’optimisation par colonies de
fourmis (RACO) pour résoudre le RSRP. Nous supposons que les temps de déplacement à vide
et les temps de transfert sont tous les deux, objet d’incertitudes. L'objectif est de fournir, pour
chaque niveau d'incertitudes, représenté par un couple (Λ, Γ) de degrés de robustesse, une
solution qui protège contre la violation des fenêtres de temps ou, si nécessaire, une solution qui
minimise les retards. Le Tableau IV.4 présente les principales notations qui seront utilisées dans
notre approche.
Notation Description
𝒘𝜦,𝜞
𝑵 Une réalisation possible
𝑩𝒆𝒔𝒕𝑺𝒐𝒍 La meilleure solution de l’algorithme RACO
La meilleure solution trouvée à la Ième itération
𝑺𝒐𝒍𝑰𝒕𝒆𝒓𝒂𝒕𝒊𝒐𝒏𝑰
de l’algorithme / 𝐼 ∈ {1, … , 𝐼𝑚𝑎𝑥}
La meilleure solution trouvée à la Néme
𝑺𝒐𝒍𝑹𝒆𝒂𝒍𝒊𝒔𝒂𝒕𝒊𝒐𝒏𝑵
réalisation / 𝑁 ∈ {1, … , 𝑁𝑚𝑎𝑥}
La solution trouvée par la kème fourmi à la Nème
𝑺𝒐𝒍𝒌𝑵
réalisation / 𝑁 ∈ {1, … , 𝑁𝑚𝑎𝑥}, 𝑘 ∈ {1, … , 𝑚}
𝑪𝒐𝒔𝒕(. ) La valeur de la fonction objectif d’une solution
La tournée de la locomotive 𝑙 trouvée par la
𝑻𝒌𝒍 = (𝒊𝟏 = 𝒓𝟎 , 𝒊𝟐 , . . . , 𝒊𝒏 = 𝒓𝟎 )
fourmi 𝑘
𝒑𝒉 = (𝒊𝟏 , 𝒊𝟐 , . . . , 𝒊𝒉 ) Un sous chemin de la tournée 𝑇𝑙𝑘
L'ensemble des nœuds qui constituent le chemin
𝝃(𝒑𝒉 ) = {𝒊𝟏 , 𝒊𝟐 , . . . , 𝒊𝒉 }
𝑝ℎ
𝑨𝒓𝒄(𝒑𝒉 ) = {(𝒊𝟏 , 𝒊𝟐 ), (𝒊𝟐 , 𝒊𝟑 ), . . . , (𝒊𝒉−𝟏 , 𝒊𝒉 )} L'ensemble des arcs qui constituent le chemin 𝑝ℎ
La date maximale d’arrivée prévue de la
𝒔̅𝒍𝒉
locomotive 𝑙 au nœud 𝑖ℎ
L'ensemble des nœuds qui ont les Λ plus
𝒘𝜹𝜦,𝒉 grandes déviations de temps de transfert sur le
chemin 𝑝ℎ
L'ensemble des arcs qui ont les Γ plus grandes
𝒘𝜟𝜞,𝒉 déviations de temps de déplacement à vide sur le
chemin 𝑝ℎ
𝑾𝒆𝒗𝒂𝒍𝜞 (. ) La valeur de l’évaluation au pire des cas
Pour chaque couple de degrés de robustesse (Λ,Γ), une itération de l'algorithme RACO
commence par générer un ensemble de réalisations possibles {𝑤1𝛬,𝛤 , 𝑤2𝛬,𝛤 , … , 𝑤𝑁𝑚𝑎𝑥
𝛬,𝛤
}, chaque
réalisation est définie par l'affectation de Γ temps de déplacement à vide (resp. Λ temps de
transfert) à leurs valeurs maximales, et les |E|- Γ (resp. |R|- Λ) qui restent à leurs valeurs
nominales. Sur chaque réalisation 𝑤𝑁𝛬,𝛤 , nous utilisons une colonie composée de 𝑚 fourmis
𝑘
{𝑓 1 , 𝑓 2 , . . , 𝑓 𝑚 }, où chaque fourmi 𝑓 𝑘 est chargée de trouver une solution réalisable 𝑆𝑜𝑙𝑁 pour
la réalisation 𝑤𝑁𝛬,𝛤 . Ensuite, une procédure de vérification de la robustesse des solutions
𝑘
trouvées est exécutée. L’objectif, est de vérifier si la solution 𝑆𝑜𝑙𝑁 respecte les contraintes de
𝑘
fenêtres de temps dans toutes les autres réalisations possibles. Si 𝑆𝑜𝑙𝑁 est robuste, nous
85
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
calculons sa pire évaluation. Sinon, nous calculons le retard qu'elle provoque. Ensuite, si au
moins une solution robustement faisable a été trouvée, nous choisissons la solution avec la pire
évaluation minimale. Sinon, nous choisissons la solution qui offre le retard total minimal. Enfin,
à la fin de chaque itération, nous renforçons les quantités de phéromones associées aux arcs de
la meilleure solution trouvée, en appliquant une mise à jour globale de phéromone.
L'Algorithme IV.1 présente la structure générale de l'algorithme RACO. Les différentes étapes
seront complètement détaillées dans les prochaines sections.
Sur chaque réalisation wNΛ,Γ , nous utilisons une colonie composée de 𝑚 fourmis
{𝑓 1 , 𝑓 2 , . . , 𝑓 𝑚 }, chaque fourmi 𝑓 𝑘 se charge de trouver une solution réalisable SolkN sur la
86
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
réalisation wNΛ,Γ en construisant les routes de toutes les locomotives. Ces routes sont construites
d’une façon itérative comme décrite dans l’Algorithme IV.2. Chaque fourmi commence par
construire l'itinéraire de la première locomotive à partir du terminal multimodal (i.e. à partir de
la position initiale 𝑟0 ), et définit ensuite un ensemble 𝐽𝑖𝑙 de rames (nœuds) candidates qui
peuvent être atteintes par la locomotive 𝑙, à partir du nœud actuel i (actuellement 𝑟0 ), avant la
fin de leurs fenêtres de temps. La fourmi sélectionne à partir de 𝐽𝑖𝑙 la rame suivante j à ajouter
à la route de la locomotive 𝑙 selon la règle de transition définie dans l'équation (IV.9). Cette
procédure est répétée jusqu'à ce que l'ensemble des rames candidates soit vide (i.e. aucune rame
ne peut être ajoutée à la route de la locomotive actuelle sans violation des fenêtres de temps).
Ensuite, la locomotive actuelle revient à la position initiale 𝑟0 , et la fourmi commence à
construire l'itinéraire de la locomotive suivante.
∝ 𝛽
𝑎𝑟𝑔 𝑚𝑎𝑥𝑙 [ 𝜏𝑖𝜋 𝜂𝑖𝜋 ] 𝑆𝑖 𝑞 ≤ 𝑞0
𝑗={ 𝜋∈𝐽𝑖 (𝐼𝑉. 9)
𝑗0 𝑆𝑖𝑛𝑜𝑛
La règle de transition proposée est définie en fonction de deux mesures : la première est
l'information heuristique 𝜂𝑖𝑗 présentée dans l'équation (IV.10). Cette mesure favorise le choix
des rames urgentes, une rame urgente est définie comme la rame 𝑗 avec la date de transfert au
plus tard 𝑏𝑗 la plus proche de la date de fin de transfert 𝐶𝑖 = 𝑠𝑖𝑙 + 𝑃̃ 𝑖 de la dernière rame 𝑖
transférée par la locomotive 𝑙.
1
𝜂𝑖𝑗 = (𝐼𝑉. 10)
𝑚𝑎𝑥 (1, ((max(𝐶𝑖 + 𝑡̃𝑖𝑗 , 𝑎𝑗 ) − 𝐶𝑖 ) × (𝑏 𝑗 − 𝐶𝑖 )))
La deuxième mesure est la trace de phéromone 𝜏𝑖𝑗 , qui indique l'historique de la colonie
et favorise le choix des arcs (𝑖, 𝑗) qui ont été empruntés par un grand nombre de fourmis. Au
début de l'algorithme, 𝜏𝑖𝑗 est initialisée par une petite valeur 𝜏0 et elle est mise à jour à la fin de
chaque itération de l'algorithme selon le mécanisme décrit dans la section 5.4.
∝ 𝛽
𝜏𝑖𝑗 𝜂
0 𝑖𝑗0
𝑃𝑖𝑗𝑙 0 = (𝐼𝑉. 11)
∝ 𝛽
∑𝜋∈𝐽𝑖𝑟 𝜏𝑖𝜋 𝜂𝑖𝜋
87
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
Algorithme IV.2 : Recherche d’une solution
1: Entrées : fourmi f k, réalisation wNΛ,Γ
2: pour l ← 1 à |L| faire
3: Tlk ← {r0 }, i ← r0 , Ci ← 0 et candidate ← Vrai
6: Répéter
7: Insérer dans 𝐽𝑖𝑙 tous les nœuds 𝜋 qui ne sont pas encore sélectionnés et qui vérifient 𝑏𝜋 ≥ 𝑚𝑎𝑥(𝐶𝑖 + 𝑡̃𝑖𝜋 , 𝑎𝜋 )
8: si 𝐽𝑖𝑙 n’est pas vide alors
8: pour chaque noeud 𝜋 ∈ 𝐽𝑖𝑙 faire
1
10: 𝜂𝑖𝜋 ←
𝑚𝑎𝑥(1,(max(𝐶𝑖 +𝑡̃𝑖𝜋 ,𝑎𝜋 )−𝐶𝑖 )×(𝑏 𝜋 −𝐶𝑖 ))
11: fin pour
12: Assigner au paramètre q une valeur aléatoire dans l’intervalle [0,1]
13: si 𝑞 ≤ 𝑞0 alors
β
14: j ← arg maxl ταiπ ηiπ // stratégie d'exploitation
π∈Ji
15: sinon
β
τα
ij0 ηij
16: selectionner 𝑗0 ∈ 𝐽𝑖𝑙 avec une probabilité 0
// stratégie d'exploration
∑ l τiπ ηβ
α
iπ
π∈Ji
17: j ← j0
18: fin si
19: Ci ← max(Ci + t̃ ij , 𝑎𝑗 ) + 𝑃̃𝑗
20: Tlk ← {j} and i ← j
21: sinon
22: Tlk ← {r0 } et candidate ← Faux
23: fin si
24: Jusqu’à (candidate = Faux)
25: fin pour
k
26: SolkN ← {T1k , … , T|L| }
De plus, nous notons que lorsque le degré de robustesse Λ (resp. Γ) est inférieur au
nombre de nœuds (resp. arcs) qui composent le chemin 𝑝ℎ , l'ensemble 𝑤δΛ,h (respectivement
𝑤ΔΓ,h ) est composé de tous les nœuds du chemin 𝑝ℎ (resp. tous les arcs du chemin 𝑝ℎ ). La
88
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
𝑘
solution 𝑆𝑜𝑙𝑁 est robustement faisable si, dans tous les chemins 𝑝ℎ de ses routes, les dates
𝑙
maximales de transfert 𝑠ℎ appartiennent à la fenêtre de temps [𝑎ℎ , 𝑏ℎ ].
Dans cette étape nous évaluons la solution 𝑆𝑜𝑙𝑘𝑁 sur le pire des cas possibles, qui
correspond à la réalisation où les temps de déplacement à vide associés aux Γ arcs ayant les
pires déviations, atteignent simultanément leurs valeurs maximales. D'abord, nous trions par
ordre décroissant tous les arcs de la solution suivant leurs déviations maximales. Ensuite, nous
attribuons aux premiers Γ arcs leurs temps de déplacement à vide maximaux et aux arcs qui
restent leurs de temps de déplacement à vide nominaux. Enfin, nous effectuons une sommation
des temps obtenus pour déterminer l'évaluation au pire des cas. Cette étape est résumée dans
l’Algorithme IV.4.
Si la solution n'est pas robustement faisable, alors nous calculons aussi le retard total
qu'elle génère, ceci est effectué en calculant la somme de différences entre les dates de départ
de transfert maximales prévues (calculées dans l’Algorithme IV.3) et les dates au plus tard de
89
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
transfert des rames où les contraintes des fenêtres de temps ne sont pas respectées. À la fin de
chaque réalisation, la colonie retourne une solution robuste, si elle existe, notée
𝑆𝑜𝑙𝑅𝑒𝑎𝑙𝑖𝑠𝑎𝑡𝑖𝑜𝑛𝑁 dont le coût correspond à l’évaluation au pire des cas minimale, ou le cas
échéant la colonie retourne une solution qui minimise le retard total. Les coûts de l'ensemble
des solutions trouvées sur toutes les réalisations considérées sont comparés à la fin de chaque
itération pour obtenir une solution avec un coût minimal ou une solution avec un retard
minimal, notée 𝑆𝑜𝑙𝐼𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛𝐼 . Les quantités de phéromone sur les arcs de cette solution sont
renforcées en utilisant une mise à jour globale, définie par la relation (IV. 12).
7. Expériences Numériques
Dans cette section, nous présentons les différents tests numériques effectués pour évaluer
l'efficacité de l'algorithme RACO proposé dans ce chapitre. L'algorithme est codé en C ++ et
tous les tests ont été exécutés sur une machine Intel (R) Core (TM) i5-3337U, 1,80 GHz avec
6 Go de RAM. Dans chaque cas de test, 10 exécutions indépendantes sont effectuées. Le
nombre d'itérations dans chaque exécution a été fixé à 1000 itérations.
Les tests ont été effectués sur 17 instances, les noms de ces instances ont la même forme
InstX-Y-Z définie dans la section 4.2 ; cette notation différencie les instances et permet de
déterminer facilement leurs caractéristiques, à savoir le nombre de rames, le nombre de
locomotives et le nombre de terminaux à conteneurs pris en considération. Les instances ont
été générées en se basant sur les temps de déplacement réels entre les terminaux à conteneurs
du port du Havre, compris entre 70 et 90 minutes. Les terminaux de départ et d'arrivée des
rames ont été définis de manière aléatoire, l'horizon de planification a été fixé à une journée de
travail et les dates au plus tôt de disponibilité des rames ont été générées en simulant les flux
réels en import et en export de conteneurs. En effet, selon des observations sur le terrain, 30%
des rames sont généralement disponibles dans les cinq premières heures de travail, 50% sont
disponibles dans les dix heures qui suivent et 20% sont disponibles vers la fin de l'horizon de
travail. Ce qui correspond à un flux import très élevé et un flux export moins élevé au début de
la journée, ensuite un flux import et un flux export très important au milieu de la journée et des
flux moins élevés dans les deux sens en fin de journée. Les dates au plus tard de transfert des
rames ont été déterminées en laissant une marge de temps supérieure ou égale à 150 minutes
après les dates de disponibilité ; cette valeur correspond au temps de séjour moyen d'une rame
dans son terminal de départ. Enfin, nous avons considéré qu'en présence des incertitudes, les
temps de transfert et de déplacement s'écartent au maximum de 15% de leurs valeurs nominales.
90
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
Tableau IV.5 Les meilleurs paramètres de l’algorithme RACO obtenus en utilisant l’outil irace
7.3. Résultats
Dans cette section nous présentons les résultats obtenus par l’algorithme RACO sur les
16 niveaux d’incertitudes présentés dans le Tableau IV.6. Chaque niveau d’incertitudes
correspond à un couple de degrés de robustesse (Λ,Γ), quatre valeurs ont été considérées pour
|𝑅| |𝑅|
chaque degré d'incertitudes, nous avons utilisé les valeurs : 0, ⌊ ⌋, ⌊ ⌋et |𝑅| pour le degré de
10 2
|𝑅|+|𝐿| |𝑅|+|𝐿|
robustesse Λ, et les valeurs : 0, ⌊ ⌋, ⌊ ⌋ et |𝑅| + |𝐿|, pour le degré de robustesse Γ.
10 2
Niveau1 Niveau2 Niveau3 Niveau4 Niveau5 Niveau6 Niveau7 Niveau8 Niveau9 Niveau10 Niveau11 Niveau12 Niveau13 Niveau14 Niveau15 Niveau16
|R| + |L| |R| + |L| |R| + |L| |R| + |L| |R| + |L| |R| + |L| |R| + |L| |R| + |L|
Γ 0 ⌊ ⌋ | | |R| + |L| 0 ⌊ ⌋ | | |R| + |L| 0 ⌊ ⌋ | | |R| + |L| 0 ⌊ ⌋ | | |R| + |L|
10 2 10 2 10 2 10 2
91
Chapitre IV. Optimisation des Tournées de Navettes Ferroviaires
92
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Les résultats de l’algorithme RACO sur toutes les instances générées sont présentés dans
le Tableau IV.7. Les résultats pour chaque instance et chaque couple de degrés de robustesse
sont donnés en fonction du temps total de déplacement à vide des locomotives (en première
ligne) et des retards (en deuxième ligne). 'NF' indique qu'une solution réalisable n'a pas pu être
trouvée pour toutes les réalisations générées de l'algorithme (c'est-à-dire qu'aucune solution
réalisable n'a été trouvée dans l'étape de recherche d'une solution). En effet, dans ces cas, pour
se protéger contre les grands degrés d’incertitudes, plus de locomotives doivent être utilisées
pour effectuer le transfert des rames. Dans 89.7% des tests, le RACO a été capable de trouver
une solution qui respecte les contraintes de fenêtres de temps.
Le Tableau IV.8 fournit les temps de calcul pour l’algorithme RACO. La colonne intitulée
Avg. donne les moyennes des temps de calcul sur tous les niveaux d'incertitudes, et la colonne
intitulée Max. donne les valeurs de temps maximales. Nous pouvons remarquer que
l’algorithme proposé est très efficace pour résoudre le RSRP sous incertitudes, puisque toutes
les instances ont été résolues rapidement sur tous les niveaux d'incertitudes et les temps de
calcul sont inférieurs à 4 secondes. De plus, les écarts-types, indiqués dans la troisième colonne
du tableau, sont très faibles (proches de zéro dans tous les cas), ce qui signifie que le nombre
de scénarios possibles pour chaque niveau d'incertitudes n’influence pas sur les temps de calcul
requis par l'algorithme RACO.
Le Tableau IV.9 montre les résultats correspondants aux instances : inst25-3-3 et inst25-
4-3. L'algorithme a été capable de trouver des solutions robustes pour la plupart des niveaux
d'incertitudes sauf pour les niveaux 11, 12, 15 et 16 de l’instance inst25-3-3. Notons que
l'augmentation du nombre de locomotives, de 3 en inst25-3-3, à 4 en inst25-4-3, a eu un impact
93
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
positif sur les résultats obtenus, car cela a permis de réduire le temps total de déplacement à
vide et de se protéger complètement contre les retards.
Cette mesure permet de calculer le supplément de coût ajouté par les décideurs en
choisissant d'utiliser une solution robuste au lieu d'appliquer la solution déterministe, sur un
niveau d'incertitudes (Λ ,Γ). Nous rappelons que nous désignons par le mot coût, le temps total
des déplacements à vide donné par une solution, et par une solution déterministe la solution
calculée sans considérer les incertitudes. La deuxième mesure détermine le degré de protection
contre les retards qu'offre la solution robuste par rapport à la solution déterministe, et elle est
calculée en utilisant la relation suivante :
94
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Notons qu’une solution est dite de bonne qualité, lorsque son coût supplémentaire est
minimal et son degré de protection contre les retards est très élevé.
Les tests basés sur les deux mesures de performance proposées (Figure IV.3) montrent
que l'algorithme RACO offre, dans la plupart des cas, une protection élevée contre les retards
(degré de protection moyen égal à 96.74%) avec une légère augmentation au niveau des temps
de déplacement à vide (coût supplémentaire moyen égal à 7.37%).
Figure IV.3 Les coûts supplémentaires et les degrés de protection obtenus par l'algorithme RACO sur
chaque niveau d'incertitudes
Dans la section précédente, nous avons démontré la capacité de notre approche à produire
des bons résultats comparés à ceux d’une approche déterministe aurait offert si elles étaient
appliquées sur le même niveau d'incertitudes. Cependant, le choix du niveau d'incertitudes à
considérer est lui-même une décision très importante, qui est souvent laissée au décideur, et est
rarement discutée dans la littérature. Toklu et al. (2014) ont introduit la notion de « pool de
solutions », qui consiste à réanalyser le comportement d'une solution trouvée sur tous les
niveaux, et sélectionner ensuite la solution qui est la moins influencée par les changements de
niveaux. Dans cette section, nous adoptons cette approche et nous la renforçons avec des
nouveaux tests statistiques afin de faciliter le choix du niveau d'incertitudes le plus pertinent.
Considérons l’instance inst25-3-3, le pool de solutions associé à cette instance est obtenu
par une réévaluation de chacune de ses solutions trouvées par un niveau d’incertitudes 𝑖 sur
tous les autres niveau𝑥 𝑗 tels que 𝑖 ≠ 𝑗. Le Tableau IV.10 présente le pool de solutions associé
à cette instance. Chaque colonne du tableau indique le niveau d’incertitudes initial qui a été
utilisé pour trouver la solution et les lignes du tableau rapportent la somme des temps de
déplacement à vide et des retards obtenus lors de la réévaluation sur les autres niveaux.
95
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Tableau IV.10 Pool de solutions associé à l’instance inst25-3-3
Niveau1 Niveau2 Niveau3 Niveau4 Niveau5 Niveau6 Niveau7 Niveau8 Niveau9 Niveau10 Niveau11 Niveau12 Niveau13 Niveau14 Niveau15 Niveau16
Niveau1 783.00 783.00 783.00 869.00 783.00 869.00 783.00 783.00 869.00 955.00 955.00 1047.00 961.00 1047.00 961.00 961.00
Niveau2 809.70 809.70 809.70 895.70 809.70 809.70 809.70 809.70 895.70 981.70 809.70 1087.19 987.70 1073.69 987.70 987.70
Niveau3 999.35 999.35 900.45 900.45 900.45 999.35 900.45 900.45 999.35 1100.40 900.45 1225.70 900.45 1204.05 1105.15 1105.15
Niveau4 999.35 999.35 900.45 900.45 900.45 999.35 900.45 900.45 999.35 1100.40 900.45 1225.70 900.45 1204.05 1105.15 1105.15
Niveau5 790.25 790.25 790.25 783.00 783.00 783.00 783.00 783.00 869.00 955.00 783.00 1073.39 783.00 1047.00 961.00 961.00
Niveau6 1073.69 1073.69 981.70 981.70 895.70 895.70 895.70 895.70 895.70 981.70 981.70 1201.69 987.70 1073.69 987.70 1073.69
Niveau7 1100.50 999.35 915.45 927.01 915.45 999.35 900.45 915.45 999.35 927.01 906.41 1105.15 1105.15 1105.15 999.35 1105.15
Niveau8 1204.05 1105.15 927.01 900.45 999.35 999.35 906.41 900.45 915.45 915.45 927.01 1105.15 999.35 927.01 927.01 1105.15
Niveau9 1258.50 1039.21 1040.80 1014.79 1039.21 1040.80 1039.21 935.59 869.00 869.00 1014.21 1039.21 1014.79 1014.79 961.00 1040.80
Niveau10 1258.50 1192.79 1105.15 1073.69 1114.79 1114.79 1100.41 1073.69 1073.69 1073.69 1073.69 1152.90 1100.41 1100.41 1073.69 1152.90
Niveau11 1296.45 1284.71 1152.90 1100.51 1152.90 1114.79 1114.79 1073.69 1048.44 1048.44 1045.15 1087.19 1048.44 1048.44 1048.44 1087.19
Niveau12 1296.45 1296.45 1284.70 1100.50 1296.45 1284.70 1152.90 1100.50 1087.20 1087.20 1048.44 1045.15 1087.20 1048.44 1087.20 1087.19
Niveau13 1258.50 1105.15 1073.69 1040.80 1105.15 1105.15 1040.80 1040.80 1039.20 1039.20 998.00 1014.79 869.00 961.00 961.00 1014.79
Niveau14 1289.85 1271.45 1181.04 1175.34 1271.45 1271.45 1181.04 1175.34 1106.80 1073.69 1073.69 1100.50 1073.69 1073.69 1100.50 1106.80
Niveau15 1330.80 1296.45 1284.70 1278.99 1330.85 1296.45 1284.70 1278.99 1189.85 1181.05 1159.50 1175.35 1159.50 1159.50 1159.50 1175.34
Niveau16 1330.85 1330.85 1284.70 1278.99 1330.85 1296.45 1284.70 1284.70 1211.60 1211.60 1159.50 1159.50 1159.50 1159.50 1181.04 1159.50
Ensuite, nous utilisons des tests statistiques pour comparer le comportement des solutions
obtenues sur les différents niveaux d’incertitudes. Soit Cij le résultat de la réévaluation de la
solution obtenue par le niveau d'incertitudes 𝑖 sur un autre niveau 𝑗. Nous assignons un rang 𝑟𝑖𝑗
égal à 1 à la meilleure réévaluation 𝐶𝑖𝑗 , un rang égal à 2 à la deuxième meilleure et ainsi de
suite. En cas d'égalité, un rang moyen est attribué. Ensuite nous utilisons le test de Friedman
(Friedman, 1940) ; sous l'hypothèse nulle, le test indique que tous les niveaux d'incertitudes
présentent des performances équivalentes. Cette hypothèse peut être rejetée avec un niveau de
confiance spécifique lorsque la statistique de Friedman donnée dans l'équation (IV. 15) est
supérieure au quantile de la distribution de Fisher avec (k-1) et (k-1)×(b-1) degrés de liberté.
96
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Tableau IV.11 Résultats du test de Friedman
Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Somme
205 185 139 111 145 162 110 89.5 109.5 115.5 68 176.5 105.5 142 128 171.5
des rangs
Somme
des rangs 2898.5 2347 1430.5 898 1719.5 1854.5 998.5 655.75 871.75 1016.3 383 2377.8 982.75 1731 1300.5 2071.25
au carré
Les résultats du test de Friedman montrent que les solutions fournies par les différents
niveaux d’incertitudes n’ont pas de performances équivalentes. De ce fait, nous procédons
ensuite à une « comparaison par paires » pour déterminer le niveau d’incertitudes qui fournit
la solution la plus robuste au changement des degrés d’incertitudes. Nous considérons que la
performance de deux niveaux est significativement différente si la différence entre leurs
sommes des rangs dépasse la valeur critique CV définie dans l'équation (IV. 16), où t1−α
2
α
désigne le quantile 1 − de la distribution de Student avec (k-1) × (b-1) degré de liberté.
2
2𝑏(𝐴 − 𝐵)
𝐶𝑉 = 𝑡1−𝛼 √ (𝐼𝑉. 16)
2 (𝑏 − 1)(𝑘 − 1)
Dans notre cas, CV = 39.08. Le Tableau IV.12 rapporte les résultats des écarts entre les
sommes des rangs des différents niveaux d’incertitudes. Les différences significatives qui
dépassent la valeur CV sont représentées en gras. D’après ces résultats, nous pouvons conclure
que le niveau d'incertitudes le plus performant (i.e. le moins influencé par les changements) est
le niveau 11, car il montre la plus petite somme des rangs qui est significativement différente
de la plupart des autres. Nous pouvons également remarquer à partir de ce tableau que les
niveaux les plus affectés par les changements sont les niveaux 1 et 2, suivis du niveau 16. Cela
montre qu’une analyse basée seulement sur le cas déterministe ou seulement sur le pire des cas
aboutit généralement à des résultats de mauvaise qualité.
97
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Tableau IV.12 Écarts entre les sommes des rangs des différents niveaux d’incertitudes
Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau Niveau
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Niveau
20 66 94 60 43 95 115.5 95.5 89.5 137 28.5 99.5 63 77 33.5
1
Niveau
46 74 40 23 75 95.5 75.5 69.5 117 8.5 79.5 43 57 13.5
2
Niveau
28 6 23 29 49.5 29.5 23.5 71 37.5 33.5 3 11 32.5
3
Niveau
34 51 1 21.5 1.5 4.5 43 65.5 5.5 31 17 60.5
l4
Niveau
17 35 55.5 35.5 29.5 77 31.5 39.5 3 17 26.5
5
Niveau
52 72.5 52.5 46.5 94 14.5 56.5 20 34 9.5
6
Niveau
20.5 0.5 5.5 42 66.5 4.5 32 18 61.5
7
Niveau
20 26 21.5 87 16 52.5 38.5 82
8
Niveau
6 41.5 67 4 32.5 18.5 62
9
Niveau
47.5 61 10 26.5 12.5 56
10
Niveau
108.5 37.5 74 60 103.5
11
Niveau
71 34.5 48.5 5
12
Niveau
36.5 22.5 66
13
Niveau
14 29.5
14
Niveau
43.5
15
8. Conclusion
Dans ce chapitre, nous avons étudié le problème de tournées des navettes ferroviaires
(RSRP) dans le port du Havre avec le but d’améliorer la performance du système de transfert
de conteneurs entre le terminal multimodal et les terminaux maritimes. L’objectif est de
minimiser les temps de déplacement à vide des locomotives et de se protéger contre les retards
de livraison, qui sont les deux principaux indicateurs définis par Benghalia et al. (2013) pour
mesurer la performance du système de transport dans le port. Tout d'abord, un modèle
déterministe basé sur la formulation du problème de tournées de véhicules a été développé pour
définir un nouveau schéma de transfert de conteneurs. L'efficacité de ce modèle a été comparée
à celle du principe du mouvement en NORIA actuellement utilisé dans le port du Havre. Les
résultats ont montré que la modélisation proposée permet de réduire significativement les temps
de déplacement à vide des locomotives et que cette formulation nécessite, dans certains cas,
98
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
moins de ressources que le principe de mouvement en NORIA pour effectuer les transferts de
rames. Ensuite, un algorithme robuste d’optimisation par colonies de fourmis (RACO) a été
proposé pour résoudre le RSRP sous des incertitudes sur les temps de déplacement et les temps
de transfert. Plusieurs niveaux d'incertitudes ont été considérés. Chacun d'entre eux a été
représenté par un couple de degrés de robustesse (Λ, Γ), où Λ est le nombre de temps de transfert
incertains et Γ est le nombre de temps de déplacement à vide supposés incertains. L'efficacité
de l'algorithme proposé a été testée sur plusieurs jeux de données et les résultats ont montré que
l'algorithme offre, pour tous les niveaux d'incertitudes, un degré de protection très élevée contre
les retards avec une légère augmentation des temps de déplacement à vide des locomotives par
rapport à ce qui aurait été trouvé par les solutions déterministes. L'algorithme développé offre
aux opérateurs portuaires un outil d'aide à la décision qui leur permet de choisir, selon leur
budget et leur cahier de charge, le niveau de protection ainsi que la solution à appliquer.
99
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
100
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Chapitre V
Ordonnancement des Opérations de
Manutention dans la Zone à Quai
Sommaire
101
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
102
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
1. Introduction
QCSP avec baies : une tâche correspond à toutes les opérations de chargement et
de déchargement dans une baie.
QCSP avec zone de baies : une tâche représente toutes les opérations de
chargement ou de déchargement dans une zone connectée de baies.
Figure V.1 Structure d’un navire porte-conteneurs (a) et une vue en coupe d’une baie (b) (adaptée de
(Bierwirth and Meisel, 2010))
103
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Le QCSP a fait l’objet de plusieurs travaux de recherche. Cependant, la plupart d’entre
eux n'ont traité que la version déterministe du problème, bien qu’il soit très rare en pratique
d’avoir des paramètres qui sont connus avec certitude, puisqu’ils dépendent de plusieurs
facteurs tels que la durée des tâches et le temps de déplacement des grues ; ces perturbations
réduisent la qualité des solutions déterministes et ont un impact significatif sur le temps de
manutention du navire. De ce fait, notre contribution dans ce chapitre porte sur l’étude du QCSP
stochastique, dans lequel les temps de déchargement/chargement de conteneurs et les temps de
déplacement des grues entre les baies sont supposés être incertains.
Le problème est résolu avec une approche Simulation-Optimisation dont l’objectif est de
profiter simultanément des grandes possibilités offertes par la simulation pour modéliser les
détails du problème étudié et de la capacité de l’optimisation à trouver des solutions de bonne
qualité. Une métaheuristique d’optimisation par colonies de fourmis (Ant Colony Optimization
(ACO)) hybridée avec un algorithme de descente à voisinages variables (Variable
Neighborhood Descent (VND)) est proposée pour déterminer les affectations des tâches aux
grues de quai et les séquences d’exécution de ces tâches sur chaque grue. La simulation est
utilisée à l’intérieur de l’algorithme d’optimisation pour générer des scénarios en concordance
avec les probabilités de distributions des paramètres incertains, ce qui permet d’effectuer des
évaluations stochastiques des solutions trouvées par chaque fourmi.
Le reste de ce chapitre est structuré comme suit. Dans la section suivante, nous
présenterons un aperçu de littérature sur le problème de QCSP. Ensuite, nous donnerons une
description du problème étudié dans la section 3. Nous proposerons, dans la section 4, une
approche de couplage Simulation-Optimisation pour résoudre le QCSP sous incertitudes. Suivie
par des expériences numériques dans la section 5. Enfin, la section 6 résume ce chapitre.
2. Etat de l’Art
La gestion des opérations dans les terminaux à conteneurs est considérée comme l’un des
sujets les plus difficiles dans le domaine de la recherche opérationnelle, en raison de la
complexité des systèmes étudiés. En particulier, le problème de QCSP a reçu une grande
attention au cours des dernières décennies. Des états de l’art récents sur ce problème sont
présentés dans Bierwirth and Meisel (2010, 2015), Carlo et al. (2015) et Boysen et al. (2017).
Le QCSP avec baies a été étudié pour la première fois par Daganzo (1989), avec l’objectif
de minimiser le coût global de retard d’un navire par rapport à sa date de départ prévue. Les
navires ont été supposés partitionnés en plusieurs baies et une tâche a été définie comme
l’ensemble des opérations de manutention de tous les conteneurs dans une baie. Les contraintes
d’interférence entre les grues de quai n'ont pas été prises en considération et les tâches étaient
supposées préemptives. Les versions statique et dynamique du problème ont été étudiées et
résolues par une approche exacte et une heuristique. Dans un travail connexe, un algorithme de
Branch and Bound a été proposé par Peterkofsky and Daganzo (1990) pour résoudre le
problème. Lim et al. (2004) ont étudié une version plus réaliste du QCSP avec des baies en
considérant les contraintes d'interférence et les contraintes de non-simultanéité entre les tâches.
104
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Un algorithme de programmation dynamique a été développé pour la résolution des petites
instances du problème, tandis qu’une recherche tabou et une heuristique de type « Squeaky
Wheel Optimization » ont été utilisées pour résoudre les grandes instances. Zhu and Lim (2006)
ont étudié le QCSP avec baies dans l’objectif de minimiser la date de fin de la dernière tâche et
ont considéré que les tâches sont non préemptives. Les auteurs ont démontré que le problème
est NP-complet et ont proposé un algorithme de Branch and Bound et un algorithme de recuit
simulé pour sa résolution. Lim et al. (2007) ont proposé une nouvelle formulation pour le QCSP
avec baies et ont montré qu'il y a toujours une solution optimale parmi tous les
ordonnancements unidirectionnels possibles. Une heuristique d'approximation simple et une
méthode de recuit simulé ont été conçues pour résoudre le problème. Un algorithme génétique
a été proposé dans (Lee et al., 2008) pour résoudre le QCSP avec baies. La performance de cet
algorithme a été testée sur un grand nombre d'instances. Les résultats ont montré que
l'algorithme génétique est très efficace puisque les déviations par rapport aux bornes inférieures
ne dépassent pas 0.9% dans toutes les instances.
Peu d'articles dans la littérature ont été consacrés à l'étude du QCSP avec zone de baies.
Steenken et al. (2001) ont traité le problème dans le but d’équilibrer les charges de travail des
grues. Les auteurs ont montré que, pour les instances de taille pratique, le problème peut être
réduit à un problème de partitionnement qui peut être facilement résolu par une énumération
simple. Lu et al. (2012) ont proposé une heuristique efficace basée sur le principe de
mouvement unidirectionnel des grues pour résoudre le problème. Les résultats ont montré que
l'heuristique proposée offre un bon compromis entre la qualité des solutions et le temps de
calcul.
105
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
problème de tournées, et une technique de recherche locale a été utilisée pour résoudre le
problème d'ordonnancement. Les résultats ont révélé que l’algorithme proposé surpasse la
méthode de Brunch and Cut (Moccia et al., 2006) en termes de temps de calcul, mais conduit à
une légère baisse au niveau de la qualité des solutions dans les grandes instances. Bierwirth and
Meisel (2009) ont également amélioré le modèle proposé dans (Kim and Park, 2004) et ont
présenté une heuristique basée sur le principe de mouvement unidirectionnel des grues
(Unidirectional Scheduling (UDS)) pour résoudre le problème. Les tests ont révélé que la
performance de cette heuristique surpasse tous les algorithmes proposés précédemment en
termes de qualité des solutions et de temps de calcul. Un algorithme génétique a été proposé
par (Chung and Choy, 2012) pour traiter le QCSP avec groupes de conteneurs. Les expériences
ont été réalisées sur les jeux de données proposés par Kim and Park (2004), et les résultats ont
montré que l'algorithme génétique est compétitif par rapport aux algorithmes existants. Monaco
and Sammarra (2011) ont étudié le QCSP avec un groupe de conteneurs en supposant que les
grues de quai ne peuvent effectuer que des déplacements unidirectionnels et que les
disponibilités des grues sont données par des fenêtres de temps. Une recherche tabou a été
développée pour résoudre le problème, et son efficacité a été testée sur une version modifiée
des jeux de données de Kim and Park (2004) et sur une application réelle dans le terminal italien
de Gioia Tauro. Dans (Wang and Kim, 2011), le QCSP a été combiné avec le problème de
gestion des zones de stockage dans le but de minimiser le temps passé par les navires dans le
port et un GRASP algorithme a été proposé pour la résolution du problème. Dans les travaux
de Nguyen et al. (2013), deux approches évolutionnaires basées sur la programmation génétique
et l'algorithme génétique ont été proposées pour résoudre le QCSP. Les résultats numériques
ont montré que les méthodes proposées offrent des meilleures solutions que les algorithmes
existants dans littérature sur plusieurs instances.
Meisel et Bierwirth (2011) ont proposé des nouveaux jeux de données pour les QCSP,
qui se composent de 400 instances allant de 10 à 100 tâches et de 2 à 6 grues. Ces jeux de
données ont été largement utilisés dans certains travaux récents comme (Kaveshgar et al.,
2012), (Unsal et Oguz, 2011), (Chen et al., 2014) et (Rouky et al., 2015).
Bien qu'une attention considérable ait été accordée dans la littérature aux différentes
variantes du QCSP, à notre connaissance, très peu de travaux ont étudié le QCSP avec des
incertitudes. Legato et al. (2010) ont été les premiers à aborder le QCSP tout en prenant en
compte les incertitudes. Ils ont pris en considération les incertitudes sur les temps de
manutention et ont proposé un algorithme de recuit simulé pour résoudre le QCSP et une
simulation à événements discrets pour évaluer les solutions. Dans un travail récent, AL-Dhaheri
et al. (2016) ont étudié le problème conjoint d’ordonnancement de grues (QCSP) avec baies et
de tournées des chariots cavaliers (Straddle Carriers Routing Problem (SCRP)) dans le but
d’améliorer la compétitivité d’un terminal à conteneurs. Le caractère aléatoire et dynamique du
processus de déchargement de conteneurs a été considéré et un algorithme génétique basé sur
la simulation a été proposé pour la résolution. Les tests numériques ont démontré l'importance
de l'utilisation de la simulation pour obtenir des solutions plus réalistes.
106
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Notre contribution dans ce chapitre est différente des travaux antérieurs de Legato et al.
(2010) et AL-Dhaheri et al. (2016) ; puisque, d’une part, notre procédure de simulation est
utilisée à l’intérieure de l’approche d’optimisation pour évaluer toutes les solutions possibles
obtenues par l’algorithme d’optimisation plutôt que d’évaluer uniquement la meilleure solution
trouvée, comme c’est le cas dans (Legato et al., 2010). D'autre part, ce travail est consacré à
l'étude du QCSP avec un groupe de conteneurs, qui est connu pour être plus complexe que le
QCSP avec baies étudiées dans (AL-Dhaheri et al., 2016). De plus, à notre connaissance, c'est
la première fois dans la littérature que l'intégration d’un algorithme d’optimisation par colonies
de fourmis (ACO) avec une procédure de simulation est considérée pour résoudre un problème
de QCSP sous incertitudes.
3. Description du Problème
Comme il a été expliqué dans la première section, le QCSP consiste à planifier les
opérations de déchargement et de chargement des conteneurs par un ensemble de grues de quai
affectées à un navire. Par extension, le QCSP incertain peut être défini comme une variante du
QCSP dans laquelle les temps de manutention des tâches et les temps de déplacement des grues
entre les positions de ces tâches (i.e. entre les baies) sont supposés être incertains et leurs valeurs
sont données par des probabilités de distribution. Formellement, dans le problème de QCSP
incertain, un navire est repartitionné en un ensemble de zones de stockages 𝐵 = {1, . . , |𝐵|}
appelées baies. Ces baies sont destinées au stockage d’un ensemble de tâches T = {𝑇1 , . . , 𝑇𝑁 },
qui représentent des opérations de chargement et de déchargement de conteneurs qui doivent
être exécutées par un ensemble de grues de quai Q = {𝑄1 , . . , 𝑄𝐶 } affectées au navire. Chaque
tâche 𝑇𝑖 est caractérisée par sa position 𝑙𝑖 , qui représente le numéro de la baie où elle est (ou
sera) contenue. Les grues de quai et les baies sont toutes les deux supposées indexées par ordre
croissant de gauche à droite. Le temps de manutention des tâches et le temps de déplacement
des grues de quai entre les baies sont supposés être des variables aléatoires indépendantes avec
des probabilités de distribution connues ; le temps de manutention incertain 𝑃̃𝑖 associé à la tâche
𝑇𝑖 suit une loi 32-Erlang avec une moyenne 𝑃𝑖 , et le temps de déplacement incertain 𝑡̃ entre
deux baies adjacentes suit une loi triangulaire avec une borne inférieure égale à une minute, un
mode de 1.5 minute et une borne supérieure de 2.5 minutes. Des contraintes de précédence sont
définies entre les tâches pour respecter le plan de chargement initial des conteneurs sur le navire.
En effet, dans le QCSP avec groupe de conteneurs, plusieurs tâches peuvent être contenues dans
une même baie. Ainsi, les tâches de déchargement doivent précéder les tâches de chargement,
les opérations de déchargement depuis le pont du navire doivent précéder le déchargement
depuis la cale et les opérations de chargement sur la cale du navire doivent être effectuées avant
les opérations de chargement sur le pont. On note par 𝜙 l’ensemble de tous les couples de tâches
liées par des relations de précédences, et par 𝑒𝑖 l'ensemble de toutes les tâches qui doivent être
exécutées avant la tâche 𝑇𝑖 . Les grues de quai sont montées sur un ensemble commun de voies
et par conséquent elles ne sont pas autorisées à se croiser (contraintes d’interférence). De plus,
pour éviter les collisions entre les grues, certaines tâches situées dans des baies adjacentes ne
peuvent pas être traitées simultanément. On note par 𝜓 l'ensemble de couples de tâches qui sont
107
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
liées par des relations de non-simultanéité et par 𝐸𝑖 l'ensemble des tâches qui ne peuvent pas
être effectuées simultanément avec la tâche 𝑇𝑖 . Enfin, pour chaque grue de quai 𝑄𝐶 , une position
initiale 𝑙𝑐0 et une date de disponibilité 𝑟𝑐0 sont données.
Le Tableau V.I présente un exemple d’instance du QCSP avec incertitudes. Cette instance
est composée de 2 grues de quai destinées à la manutention de 10 tâches dans un navire divisé
en 10 baies. Les lignes de 2 à 5 représentent les attributs de chaque tâche à savoir : sa position
dans le navire (donnée par le numéro de baie), la nature de l’opération qu’elle représente (i.e.
chargement (Loading (L)) ou déchargement (Unloading (U))), si la tâche est placée sur le pont
du navire (Deck (D)) ou dans sa cale (Hold (H)) et enfin la valeur initiale de son temps de
manutention prévu 𝑃𝑖 . Les relations de présidence et de non-simultanéité sont rapportées dans
les lignes 6 et 7. Les deux grues de quai sont supposées être disponibles dès le début de l'horizon
de planification et sont initialement situées dans la baie 1 et la baie 6, respectivement. La Figure
V.2.(a) donne une illustration de cette instance, et la Figure V.2.(b) fournit une représentation
simple des relations de précédence.
Figure V. 2 (a) Illustration d’une instance du QCSP incertain et (b) Représentation des relations de
précédence entre les tâches
108
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Dans cette instance, trois tâches sont situées dans la baie 2 ; une opération de
déchargement T4 et deux opérations de chargement T6 et T1. Ainsi, T4 doit être exécutée avant
les tâches T6 et T1, et la tâche T1 doit précéder T6, car le chargement sur la cale précède le
chargement sur le pont.
Dans cette section, nous proposons une nouvelle approche de couplage Simulation-
Optimisation (S-O) basée sur un algorithme d’optimisation par colonies de fourmis pour
résoudre le QCSP sous incertitudes. L’objectif est de minimiser la date de fin de la dernière
tâche exécutée (connue sous le nom de makespan). La section 4.1 présente la structure générale
de l'approche de couplage proposée, tandis que les étapes des différentes méthodes
d’optimisation et de simulation implémentées sont entièrement décrites dans les sections de 4.2
à 4.5.
Comme le montre la Figure V.3, l'approche S-O commence par charger les données
d'entrée depuis le fichier d'instance. Les données d'entrée représentent le nombre de tâches, le
nombre de grues de quai affectées au navire, les positions des tâches (i.e. les numéros de baies),
le type des tâches et leur emplacement dans le pont ou dans la cale du navire. Une itération 𝐼
de l’approche S-O commence par attribuer à la position 𝑙𝑐 de chaque grue de quai et à sa date
de disponibilité 𝑟𝑐 leurs valeurs initiales. Une procédure d’optimisation par colonies de fourmis
est ensuite exécutée pour déterminer un ensemble d’ordonnancements réalisables pour le
QCSP. Dans cette procédure, nous utilisons une colonie composée de 𝑚 fourmis
{𝑓 1 , 𝑓 2 , . . , 𝑓 𝑚 }, chaque fourmi 𝑓 k est responsable de trouver un ordonnancement réalisable
𝑋0 (𝐼, 𝑓 k ) qui détermine une affectation initiale des tâches aux grues de quai et la séquence
d’exécution des tâches par les grues de quai, tout en respectant les contraintes de précédence,
d’interférence et de non-simultanéité. L’ordonnancement initial est calculé en n’utilisant que
109
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
les valeurs nominales sur les temps de manutention des tâches et sur les temps de déplacement
des grues entre les baies. Ensuite, un algorithme de descente à voisinages variables (VND),
utilisé comme une recherche locale, est exécuté pour améliorer l’ordonnancement initial
𝑋0 (𝐼, 𝑓 k ) trouvé par la procédure d’optimisation par colonies de fourmis. L’ordonnancement
obtenu après l’application de la recherche locale est noté 𝑋1 (𝐼, 𝑓 k ). La simulation est utilisée
pour évaluer chaque ordonnancement sur des scénarios réalistes générés en concordance avec
les probabilités de distribution des temps de déplacement et des temps de manutention. À la fin
de la simulation, la valeur en espérance de la fonction objectif (i.e. espérance du makespan sur
tous les scénarios) de chaque ordonnancement est calculée et comparée, et une mise à jour
globale est exécutée pour renforcer la trace de phéromone sur les arcs de la meilleure solution
trouvée à l'itération 𝐼. L'approche s'arrête lorsqu'un nombre maximal d'itérations est atteint et
la meilleure solution 𝑋𝑏𝑒𝑠𝑡 sur toutes les itérations est retournée.
L’algorithme d’optimisation par colonies de fourmis (ACO) est considéré comme l’un
des meilleurs choix pour résoudre les problèmes d’ordonnancement, car la littérature sur ces
problèmes a démontré son efficacité pour donner de bonnes solutions (Rajendran et al., 2004 ;
Hirsch et al., 2012 ; Thiruvady et al., 2016 ; Bencheikh et al., 2016 ; El Khoukhi et al. 2017).
110
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Dans chaque itération 𝐼 de l’approche du couplage S-O une structure ACO qui se
compose de 𝑚 fourmis {𝑓 1 , 𝑓 2 , . . , 𝑓 𝑚 } est utilisée. Chaque fourmi 𝑓 𝑘 construit un
ordonnancement initial 𝑋0 (𝐼, 𝑓 k ) tout en considérant les attributs des tâches et des grues de
quai, et en utilisant que les valeurs nominales sur les temps de manutention des tâches et sur les
temps de déplacement des grues de quai. Les fourmis se déplacent durant les étapes de
recherche de solutions suivant un graphe biparti (Figure V.4). Les sommets du premier niveau
de ce graphe représentent les grues de quai tandis que les sommets du deuxième niveau
représentent les tâches. Deux sommets fictifs S et F sont ajoutés à ce graph pour représenter le
début et la fin de déplacement d'une fourmi.
Grues de quai Tâches
S
F
argmin 𝑟𝑐 𝑠𝑖 𝑞 < 𝑞0
𝑘
𝑃𝑆𝑐 = { 𝑐=1..𝐶 (𝑉. 1)
𝑄0 𝑠𝑖𝑛𝑜𝑛
Une fois qu'une grue de quai 𝑄𝑐 est sélectionnée, la fourmi définit un ensemble de tâches
candidates pouvant être exécutées par la grue actuelle. L'ensemble des tâches candidates d'une
fourmi est noté 𝐽𝑘 et contient toutes les tâches 𝑇𝑖 qui ne sont pas encore affectées à une grue
111
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
de quai (i.e. les tâches qui ne sont pas dans l'ensemble des tâches déjà sélectionnées 𝑂𝑘 par la
fourmi 𝑓 𝑘 ) et que leur liste de prédécesseurs 𝑒𝑖 est vide.
𝑒𝑖 = ∅
𝑇𝑖 ∈ 𝐽𝑘 𝑠𝑖 { (𝑉. 2)
𝑇𝑖 ∉ 𝑂𝑘
Ensuite, la fourmi choisit parmi les tâches candidates de l’ensemble 𝐽𝑘 , la tâche suivante
𝑇𝑖 à affecter à la grue actuelle 𝑄𝑐 conformément à la seconde règle de transition définie dans
l'équation (V.3).
(𝜏𝑐𝑖 )𝛼 (𝜂𝑐𝑖 )𝛽
𝑠𝑖 𝑖 ∈ 𝐽𝑘
𝑃𝑐𝑖𝑘 = {∑ 𝑘 (𝜏𝑐𝑗 )𝛼 (𝜂𝑐𝑗 )𝛽 (𝑉. 3)
𝑗∈𝐽
0 𝑠𝑖𝑛𝑜𝑛
Où, τci représente la quantité de phéromone sur l'arc (𝑐, 𝑖). La trace de phéromone
représente la mémoire de l'ACO et elle est utilisée pour favoriser les déplacements sur les arcs
sélectionnés par un grand nombre de fourmis. Cette trace est initialisée au début de l'approche
S-O par une petite valeur τ0 et mise à jour localement dans l'ACO à chaque fois qu'une tâche
est sélectionnée (voir section 4.2.6). Une mise à jour globale de la trace de phéromone est
également effectuée à la fin de chaque itération de l’approche S-O selon le mécanisme décrit
dans la section 4.5. 𝜂𝑐𝑖 représente l’information heuristique associée à l'affectation de la tâche
Ti à la grue actuelle Q c , 𝜂𝑐𝑖 fournit des informations utiles sur le problème et guide les fourmis
dans la procédure de recherche de solutions. Deux stratégies différentes sont proposées dans la
section suivante pour l’information heuristique. Les paramètres α et β sont introduits pour
contrôler la direction de recherche en déterminant l'intensité relative à la trace de phéromone et
à l'information heuristique.
Afin de converger vers des solutions de bonne qualité dans la procédure ACO, nous
proposons deux différentes stratégies pour l’information heuristique :
Stratégie de la date de début au plus tôt (Earliest Start Time strategy (EST)) :
Cette stratégie est basée sur les dates de début d’exécution possibles des tâches
candidates. La date de début au plus tôt d’une tâche Ti ∈ 𝐽𝑘 est définie dans
l’équation (V.4) comme la première date dans laquelle la grue de quai courante
Q c peut commencer l’exécution de la tâche Ti , sans violations des contraintes de
non-simultanéité et d’interférence.
112
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
L’information heuristique associée à la stratégie EST est définie par l'équation (V.5)
comme suit :
1
𝜂𝑐𝑖 = (V. 5)
1 + 𝐸𝑆𝑇𝑖
L’information heuristique associée à la stratégie LWL est définie par l'équation (V.7)
comme suit :
Pi + t̂|lc − li |
ηci = (V. 7)
1 + LWLi
Une fois qu’une tâche 𝑇𝑖 est affectée à la grue Q c , la fourmi 𝑓 k se déplace vers le sommet
F et met à jour l’ensemble de ses informations. En effet, la fourmi ajoute la tâche sélectionnée
à l’ensemble 𝑂𝑘 des tâches déjà sélectionnées et supprime cette tâche des ensembles de tâches
prédécesseurs 𝑒𝑗 de toutes les autres tâches 𝑇𝑗 telles que 𝑇𝑗 ≠ 𝑇𝑖 . Ensuite, nous attribuons une
date de fin de manutention 𝐶𝑖 à la tâche 𝑇i selon la relation (V.8) et nous mettons la date de
disponibilité 𝑟𝑐 de la grue de quai courante 𝑄𝑐 à 𝐶𝑖 .
𝐶𝑖 = 𝑚𝑎𝑥(𝑟𝑐 , 𝑚𝑎𝑥
𝑘
𝐶𝑗 , 𝑚𝑎𝑥
𝑠<𝑐
𝑟𝑠 , 𝑚𝑎𝑥
𝑠>𝑐
𝑟𝑠 ) + 𝑡̂|𝑙𝑐 − 𝑙𝑖 | + 𝑃𝑖 (V. 8)
𝑗∈𝑂 ∩𝐸𝑖
𝑙𝑠 >𝑙𝑖 𝑙𝑠 <𝑙𝑖
Enfin, nous effectuons une mise à jour locale de phéromone sur l’arc (𝑐, 𝑖) suivant la
relation (V.9) :
Les étapes de 4.2.2 à 4.2.6 sont répétées jusqu'à ce que toutes les tâches soient
sélectionnées par la fourmi courante 𝑓 𝑘 . Ensuite la fourmi suivante 𝑓 𝑘+1 commence la
113
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
construction de son ordonnancement 𝑋0 (𝐼, 𝑓 𝑘+1 ) . La procédure ACO est résumée dans
l’algorithme V.1.
26: Ajouter Ti à Ok et la supprimer de toutes les listes de prédécesseurs ej des tâches 𝑇𝑗 telles que 𝑇𝑖 ≠ 𝑇𝑗
114
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
itérativement de l'améliorer en employant un ensemble de structures de voisinage. L'ordre
d'exploration des structures de voisinage est généré de manière aléatoire à chaque appel de
l'algorithme. VND exécute la première structure de voisinage tant qu'une amélioration est
obtenue, et passe à la suivante lorsque la précédente ne parvient plus à améliorer la solution
courante. VND s'arrête lorsque toutes les structures de voisinage sont appliquées. Les étapes de
l'algorithme VND sont présentées dans l’Algorithme V.2 et les différentes structures de
voisinage utilisées sont décrites ci-dessous.
Swap1 : Sélectionner au hasard une grue de quai et examiner tous les échanges
possibles entre chaque paire de tâches affectées à cette grue, seuls les échanges
possibles sont considérés.
115
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
simulation. Chaque réplication définit un scénario possible généré en concordance avec les
probabilités de distribution des paramètres incertains. Les temps de déplacement des grues de
quai entre les baies sont générés selon une distribution triangulaire avec une borne inférieure
égale à 1 minute, un mode de 1.5 minute et une borne supérieure de 2.5 minutes. Les temps de
manutention des tâches suivent une distribution 32-Erlang avec une moyenne 𝑃𝑖 . Une
simulation à événements discrets (Discrete Event Simulation (DES)) est ensuite utilisée pour
évaluer les ordonnancements obtenus lors de la procédure d'optimisation et pour corriger les
dates de début et de fin des tâches en fonction de chaque scénario. La simulation commence
par lire les séquences d’exécution des tâches sur les grues de quai à partir de la solution
𝑋1 (𝐼, 𝑓 𝑘 ) fournie par le processus d’optimisation et les valeurs des paramètres incertains à partir
de la réplication 𝑤 𝑛 . Nous utilisons le statut de chaque grue de quai, i.e. "inactive" "occupée"
ou "ne peut pas être sélectionnée" et le nombre de tâches en attente d'exécution par chaque grue
de quai comme deux variables pour décrire l'état du système simulé. Les grues de quai sont
marquées comme "occupées" jusqu'à ce que leurs dates de disponibilité soient atteintes.
Ensuite, la première grue de quai qui est disponible est sélectionnée, et se déplace à la
position de la première tâche dans sa séquence et les opérations de manipulation des conteneurs
associées à cette tâche démarrent. Juste après, la grue de quai sélectionnée change son statut de
"inactive" à "occupée" et une autre grue disponible est sélectionnée. Dans le cas où plusieurs
grues de quai afficheraient des dates de disponibilité similaires, la priorité est donnée à la grue
avec l'indice le plus bas. Avant d'effectuer un mouvement d’une grue de quai, nous vérifions
tout d’abord si ce déplacement provoque des interférences, si c'est le cas, nous changeons le
statut de la grue de quai à "ne peut pas être sélectionnée maintenant" et nous sélectionnons une
autre grue libre.
Le statut d’une grue de quai change également à "ne peut pas être sélectionnée
maintenant" si la première tâche dans sa séquence ne peut pas être exécutée simultanément avec
l'une des tâches en cours d'exécution par d'autres grues de quai. Lorsque les opérations de
manutention d'une tâche se terminent, la grue de quai qui exécutait cette tâche change son statut
en "inactive" et le nombre de tâches en attente d'exécution par cette grue diminue par 1. Le
processus de simulation se termine lorsque le nombre de tâches en attente dans toutes les grues
de quai est égal à 0. À la fin de la simulation, la date de fin de la dernière tâche exécutée est
retournée.
Cette expérience est réalisée pour tous les ordonnancements 𝑋1 (𝐼, 𝑓 1 ), . . . , 𝑋1 (𝐼, 𝑓 𝑚 )
obtenus à la fin du processus d'optimisation, et la valeur en espérance du makespan de chaque
ordonnancement est calculée par:
N
𝑘 ),
1
𝐸(𝐶𝑚𝑎𝑥 (𝑋1 (𝐼, 𝑓 𝑤)) = ∑ 𝐶𝑚𝑎𝑥 (𝑋1 (𝐼, 𝑓 𝑘 ), 𝑤 𝑛 ) (V. 10)
N
n=1
116
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Oui Non
Non
Non
117
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
5. Expériences Numériques
Dans cette section, plusieurs expériences numériques sont exécutées pour évaluer la
performance de l’approche de couplage S-O proposée. Tout d'abord, le choix des meilleurs
paramètres pour l'algorithme ACO et la procédure de simulation est étudié. Ensuite, dans le cas
déterministe la performance de la procédure d’optimisation par colonies de fourmis hybrides
(HACO) (i.e. l’ACO et l’algorithme VND) est testée sur les jeux de données présentés dans
(Kim and Park, 2004). Dans le cas stochastique, deux mesures sont proposées pour comparer
la performance de l'approche S-O en utilisant les stratégies EST et LWL. Toutes les expériences
sont réalisées sur une machine Intel(R) Core i5-3337U, 1,80 GHz avec 6,00 Go de RAM.
118
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
|𝐶𝑚𝑎𝑥−𝐸(𝐶𝑚𝑎𝑥)|
𝛾= est un paramètre de l’algorithme qui représente l’erreur d’estimation
𝐶𝑚𝑎𝑥
𝛼
relative qui peut être tolérée dans la simulation, t 𝑁−1,1− 𝛼 est le quantile 1 − de la distribution
2 2
Dans cette section, les résultats de l’algorithme d’optimisation par colonies de fourmis
hybride (HACO) sont comparés à ceux des algorithmes : GRASP de Kim and Park (2004), la
recherche tabu (TS) de Sammarra et al. (2007), l’heuristique de mouvement unidirectionnel
(UDS) de Bierwirth and Meisel (2009), l’algorithme génétique (GA) de Chung and Choy
(2012), l’algorithme génétique hybride (HGA) et la programmation génétique hybride (HGP)
de Nguyen et al. (2013). L’équation (V.12) est utilisée pour calculer les déviations des résultats
de chaque algorithme par rapport aux bornes inférieures rapportées dans (Bierwirth and Meisel
119
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
, 2009). Pour chaque algorithme le pourcentage de déviation relative (Relative Percent
Deviation (RPD)) en une instance 𝑖 est donné par :
𝐵𝑒𝑠𝑡𝑖 (𝐻) est la valeur de la fonction objectif (i.e. 3×la valeur makespan, voir la
modélisation proposée par Bierwirth and Meisel (2009)) obtenue par l’algorithme 𝐻 sur
l’instance 𝑖 et 𝐿𝐵𝑖 la valeur de la borne inférieure sur la même instance.
Le Tableau V.3 présente les résultats des pourcentages de déviation relative obtenus par
les différents algorithmes et la Figure V.6 résume ces résultats et rapporte la moyenne des
déviations sur chaque groupe d'instances. Les résultats démontrent que les deux stratégies
proposées pour la définition de l’information heuristique dans l’algorithme HACO sont très
compétitives et efficaces pour résoudre le QCSP. Les résultats révèlent que l’HACO avec la
stratégie LWL est le seul algorithme de la littérature capable d’atteindre un pourcentage de
déviation de 0% dans les instances de petite et moyenne taille, tout en restant performant sur
les grandes instances. D'autre part, l'HACO avec la stratégie EST donne également de bons
résultats lorsqu'il est appliqué aux petites et moyennes instances du groupe 1 et 2, puisque le
RPD moyen est inférieur à 0.06% dans les instances de groupe 1 et il est égal à 0.04% dans
ceux du groupe 2. De plus, le HACO avec la stratégie EST surpasse tous les autres algorithmes
sur les grandes instances du groupe 3 avec un RPD moyen égal à 0.39%, et présente des
performances assez similaires aux meilleurs algorithmes dans la littérature (i.e. UDS et HGP)
sur les grandes instances du groupe 4.
120
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Tableau V.3 Résultats des algorithmes : B&B, GRASP, TS, UDS, GA, HGA, HGP, HACO-EST et HACO-
LWL.
Bierwirth Chung
Sammarra
Kim and Park and and Nguyen et al.
et al. Nos algorithmes
(2004) Meisel Choy (2013)
Groupe Instance (2007)
(2009) (2012)
Il est généralement très difficile de comparer les temps de calcul des algorithmes,
puisqu’ils sont souvent implémentés sur des machines avec des configurations différentes. De
ce fait, nous adoptons dans cette section une approche basée sur le calcul de nombre
d'opérations arithmétiques flottantes par seconde dont l'unité est le Mflops (Million Floating
Point Calculation Per Second (Mflops)) (Dongarra, 2014). Cette approche nous permettra de
réaliser une comparaison équitable entre les temps de calcul des algorithmes. Le Tableau V.4
montre les valeurs de Mflops relatives aux algorithmes considérés dans l’étude. La ligne 2 du
121
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
tableau présente les configurations des machines sur lesquelles chaque algorithme est
implémenté. La ligne 3 rapporte les configurations équivalentes à certaines machines qui ne
sont pas répertoriées dans le rapport de Dongarra (2014). Les Mflops correspondant à chaque
machine sont ensuite donnés dans la ligne 4. Enfin la ligne 5 rapporte le facteur de conversion
𝑟 qui permettra de mettre les temps de calcul des algorithmes sur la même échelle, ce facteur
est défini comme le rapport de la valeur de Mflops de la machine sur laquelle un algorithme a
été implémenté et celle de Mflops de la machine sur laquelle nous avons exécuté nos
algorithmes.
Facteur de
conversion 0.09289 1.12796 1.24834 1.24834 1.49099 1
𝑟
Initial 0.44 0.35 1.52 1.12×10-5 0.52 0.01 0.01 0.02×10-3 0.3×10-3
Groupe 1 :
Instances de
petite taille Après
0.41 0.33 1.71 1.39×10-5 0.65 0.01 0.01 0.02×10-3 0.3×10-3
conversion
Groupe 2 : Initial 17.53 1.46 5.86 3.86×10-5 0.75 0.04 0.03 0.01 0.01
Instance de
taille Après
moyenne 1.63 0.13 6.61 4.81×10-5 0.93 0.06 0.04 0.01 0.01
conversion
Initial 564.47 3.16 21.75 6.26×10-4 1.18 0.18 0.20 0.04 0.03
Groupe 3 :
Instance de
grande taille Après
52.43 0.29 24.53 7.81×10-4 1.47 0.27 0.29 0.04 0.03
conversion
Initial 809.73 7.56 48.68 3.43×10-3 1.58 0.57 0.39 0.07 0.09
Groupe 4 :
Instance de
grande taille Après
75.21 0.70 54.91 4.28×10-3 1.97 0.85 0.58 0.07 0.09
conversion
122
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Le Tableau V.5 présente les résultats de comparaison des temps de calcul. Le temps de
calcul après conversion correspond au temps de calcul initial de chaque algorithme multiplié
par le taux de conversation 𝑟. Ce temps indique le temps de calcul qui aurait été affiché par les
différents algorithmes de la littérature s'ils étaient exécutés sur notre machine.
Les résultats de ce tableau montrent clairement que l’algorithme HACO avec les deux
stratégies EST et LWL est très efficace pour résoudre le QCSP, puisque toutes les instances ont
été résolues en moins de 0.1 minute. L'UDS est le seul algorithme dans la littérature qui est plus
rapide que notre algorithme.
Les résultats déterministes ont montré que l'algorithme HACO, avec les deux stratégies
EST et LWL définies dans l’information heuristique pour la sélection d’une tâche, est très
efficace pour résoudre le QCSP. Cette performance de l’algorithme d’optimisation est très
recommandée au niveau du couplage Simulation-Optimisation (S-O), car le choix d'un
algorithme d'optimisation à utiliser dans le couplage dépend de son efficacité (Kelly, 2002).
Dans cette section, nous comparons les résultats des deux stratégies EST et LWL lorsqu'elles
sont appliquées dans l'approche S-O pour gérer les incertitudes. Ensuite, nous démontrons
l’importance de l’utilisation de l’approche S-O pour obtenir des solutions plus réalistes dans un
environnement incertain.
Le Tableau V.6 présente les résultats des tests de simulation effectués en utilisant les deux
stratégies EST et LWL. Pour comparer ces stratégies et sélectionner la plus appropriée pour
l’approche S-O, nous proposons deux mesures :
𝑀𝑎𝑥𝑉𝑎𝑙𝑢𝑒[𝐶𝑚𝑎𝑥(𝐿𝑊𝐿,𝑤)]−𝑀𝑎𝑥𝑉𝑎𝑙𝑢𝑒[𝐶𝑚𝑎𝑥(𝐸𝑆𝑇,𝑤)]
𝐺𝑎𝑝1 = × 100 : la déviation entre
𝑀𝑎𝑥𝑉𝑎𝑙𝑢𝑒[𝐶𝑚𝑎𝑥(𝐸𝑆𝑇,𝑤)]
la valeur maximale de la fonction objectif (i.e. makespan maximal) obtenue par la
stratégie LWL et la valeur maximale de la fonction objectif obtenue par la
stratégie EST, parmi toutes les réplications de l'approche S-O (i.e. parmi les
scénarios de l’échantillon w).
𝐸[𝐶𝑚𝑎𝑥(𝐿𝑊𝐿,𝑤)]−𝐸[𝐶𝑚𝑎𝑥(𝐸𝑆𝑇,𝑤)]
𝐺𝑎𝑝2 = × 100 : la déviation entre la valeur de
𝐸[𝐶𝑚𝑎𝑥(𝐸𝑆𝑇,𝑤)]
l’espérance de la fonction objectif (i.e. espérance du makespan) obtenue par la
stratégie LWL et la valeur de l’espérance de la fonction objectif obtenue par la
stratégie EST, sur toutes les réplications de l'approche S-O (i.e. sur tous les
scénarios de l’échantillon w).
123
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
Tableau V.6 Résultats de la simulation
La Figure V.7.(a) résume les valeurs de Gap1 et montre que la stratégie EST surpasse la
stratégie LWL sur les scénarios les plus défavorables (i.e. le pire scénario possible), puisque la
valeur maximale du makespan observée sur LWL et plus grande que celle observée sur la
stratégie EST (i.e. Gap1 positif), sauf dans les instances k15 et k19 où des écarts négatifs de -
3.12% et -0.86% sont respectivement observés.
124
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
De plus, en regard de la minimisation de l’espérance du makespan, les résultats de Gap2
(Figure V.7.(b)) montrent clairement que l'utilisation de la stratégie EST dans la procédure
d'optimisation donne les meilleurs résultats pour l'approche S-O sur toutes les instances puisque
le seul écart négatif a été observé dans l’instance k25 avec une faible valeur de -1,19%.
Figure V. 7 (a) Pourcentage de déviation entre les valeurs maximales et (b) Pourcentage de déviation entre
les espérances
Par conséquent, il est évident, d'après les résultats présentés dans la Figure V.7, que
l'utilisation de la stratégie EST est plus efficace que l’utilisation de la stratégie LWL pour faire
face aux incertitudes, même si les deux stratégies avaient montré des performances presque
similaires dans le cas déterministe.
Pour démontrer l'importance de l'utilisation de l'approche S-O pour gérer les incertitudes,
nous comparons ces résultats avec ceux des solutions déterministes lorsqu'elles sont mises en
œuvre sur des scénarios identiques. Pour les solutions S-O, nous utilisons celles obtenues en
appliquant la stratégie EST, et pour les solutions déterministes, nous considérons sur chaque
instance la meilleure solution obtenue entre les stratégies EST et LWL. Chaque solution est
ensuite simulée sur 1000 scénarios avec des temps de déplacement de grues et des temps de
manutention des tâches stochastiques. Les pourcentages d'amélioration que les solutions S-O
offrent par rapport aux solutions déterministes sont illustrés dans la Figure V.8.
Figure V. 8 Pourcentages d'amélioration que les solutions S-O offrent par rapport aux solutions déterministes
125
Chapitre V. Ordonnancement des Opérations de Manutention dans la Zone à Quai
La valeur de l’amélioration moyenne est égale à 7.43% et l’amélioration maximale est de
15.6%. Par conséquent, nous pouvons conclure que l'utilisation de l’approche SO est très utile
pour obtenir des solutions plus robustes contre les incertitudes.
6. Conclusion
126
Conclusion Générale et Perspectives
Dans le Chapitre II, nous avons présenté un tour d’horizon sur le concept de transport
multimodal et sur la littérature relative aux problèmes de décision liés à la planification et la
gestion des différentes composantes de la chaîne logistique multimodale, en mettant en exergue
les différentes configurations de réseaux de transport possibles, les principaux types de
terminaux intermodaux utilisés dans la conception de ces réseaux et les principaux problèmes
de décision auxquels sont confrontés les opérateurs multimodaux. Ces éléments introductifs
nous ont permis d’établir le concept général de cette thèse et de positionner les problèmes traités
dans les chapitres suivants par rapport à la littérature existante.
Ensuite, dans le Chapitre III, nous avons fourni un état de l’art sur les différents
paradigmes et approches d’optimisation utilisés dans la littérature pour étayer la prise de
décision face aux incertitudes.
Le travail présenté dans ce chapitre fait partie des rares travaux consacrés à
l’application des approches d’optimisation robuste pour la résolution des
problèmes réels. Ce type de contribution a été fortement recommandé dans l’état
de l’art sur l’optimisation robuste présenté par Roy (2010).
En regard de la littérature sur le VRP robuste, cette étude est, à notre connaissance,
la première qui traite un problème de VRP robuste avec fenêtres de temps, en
127
Conclusion Générale et Perspectives
considérant que les temps de déplacement et les temps de service sont tous les
deux incertains.
Les travaux que nous avons accomplis sont encourageants, mais il nous reste quand même
un travail important à mener. En effet, cette thèse ouvre plusieurs perspectives que nous allons
nous efforcer de présenter dans ce qui suit :
128
Conclusion Générale et Perspectives
129
Listes des Publications
130
Listes des Publications
2. Simulation optimization based ant colony algorithm for the uncertain quay
crane scheduling problem, Naoufal Rouky, Mohamed Nezar ABOURRAJA,
Jaouad Boukachour, Dalila Boudebous, Ahmed El Hilali Alaoui & El Khoukhi
Fatima. International Journal of Industrial Engineering Computations, Vol.10,
no (1), pp. 111-132. DOI: 10.5267/[Link].2018.2.002
3. Optimization and Simulation for the Quay Crane Scheduling Problem under
Uncertainty, Naoufal Rouky, Mohamed Nezar ABOURRAJA, Jaouad
Boukachour, Dalila Boudebous, Ahmed El Hilali Alaoui & El Khoukhi Fatima.
in The 4th International IEEE conference on Logistics Operations Management
(GOL'18), April 10-12, 2018, Le Havre, France.
131
Listes des Publications
132
Références
Bibliographie
Abourraja, M. N. (2018). Gestion multi-agents d'un terminal à conteneurs (Doctoral
dissertation, Normandie).
Abourraja, M. N., Oudani, M., Samiri, M. Y., Boudebous, D., El Fazziki, A., Najib, M., ... &
Rouky, N. (2017). A multi-agent based simulation model for rail–rail transshipment: An
engineering approach for gantry crane scheduling. IEEE Access, 5, 13142-13156.
Agra, A., Christiansen, M., Figueiredo, R., Hvattum, L. M., Poss, M., & Requejo, C. (2013).
The robust vehicle routing problem with time windows. Computers & Operations
Research, 40(3), 856-866.
Al-Dhaheri, N., & Diabat, A. (2015). The quay crane scheduling problem. Journal of
Manufacturing Systems, 36, 87-94.
Al-Dhaheri, N., Jebali, A., & Diabat, A. (2016). A simulation-based Genetic Algorithm
approach for the quay crane scheduling under uncertainty. Simulation Modelling Practice and
Theory, 66, 122-138.
Aloulou, M. A., Kalaï, R., & Vanderpooten, D. (2005). Une nouvelle approche de robustesse:
α-robustesse lexicographique. Bulletin du Groupe de Travail Européen Aide Multicritère à la
Décision.
Andersen, J., & Christiansen, M. (2009). Designing new European rail freight services. Journal
of the Operational Research Society, 60(3), 348-360.
Anghinolfi, D., Caballini, C., & Sacone, S. (2014). Optimizing train loading operations in
innovative and automated container terminals. IFAC Proceedings Volumes, 47(3), 9581-9586.
Ayar, B., & Yaman, H. (2012). An intermodal multicommodity routing problem with scheduled
services. Computational optimization and applications, 53(1), 131-153.
Ballis, A., & Golias, J. (2002). Comparative evaluation of existing and innovative rail–road
freight transport terminals. Transportation Research Part A: Policy and Practice, 36(7), 593-
611.
Bandeira, D. L., Becker, J. L., & Borenstein, D. (2009). A DSS for integrated distribution of
empty and full containers. Decision Support Systems, 47(4), 383-397.
133
Références
Bencheikh, G., Boukachour, J., & Alaoui, A. E. H. (2016). A memetic algorithm to solve the
dynamic multiple runway aircraft landing problem. Journal of King Saud University-
Computer and Information Sciences, 28(1), 98-109.
Benghalia, A., Boukachour, J., & Boudebous, D. (2013). Évaluation de la performance du trafic
des conteneurs maritimes. In 9th International Conference on Integrated Design and
Production, CPI (pp. 21-23).
Benghalia, A., Oudani, M., Boukachour, J., Boudebous, D., & Alaoui, A. E. H. (2014).
Optimization-simulation for maritime containers transfer. International Journal of Applied
Logistics (IJAL), 5(2), 50-61.
Benna, T., & Gronalt, M. (2008, December). Generic simulation for rail-road container
terminals. In Proceedings of the 40th Conference on Winter Simulation, Winter Simulation
Conference, 2656-2660.
Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations research, 52(1), 35-53.
Better, M., Glover, F., Kochenberger, G., & Wang, H. (2008). Simulation optimization:
Applications in risk management. International Journal of Information Technology &
Decision Making, 7(04), 571-587.
Bianchi, L., Birattari, M., Chiarandini, M., Manfrin, M., Mastrolilli, M., Paquete, L., ... &
Schiavinotto, T. (2006). Hybrid metaheuristics for the vehicle routing problem with stochastic
demands. Journal of Mathematical Modelling and Algorithms, 5(1), 91-110.
Bierwirth, C., & Meisel, F. (2009). A fast heuristic for quay crane scheduling with interference
constraints. Journal of Scheduling, 12(4), 345-360.
Bierwirth, C., & Meisel, F. (2010). A survey of berth allocation and quay crane scheduling
problems in container terminals. European Journal of Operational Research, 202(3), 615-
627.
Bierwirth, C., & Meisel, F. (2015). A follow-up survey of berth allocation and quay crane
scheduling problems in container terminals. European Journal of Operational
Research, 244(3), 675-689.
Birattari, M., Yuan, Z., Balaprakash, P., & Stützle, T. (2010). F-Race and iterated F-Race: An
overview. In Experimental methods for the analysis of optimization algorithms. Springer,
Berlin, Heidelberg, 311-336.
Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming. Springer Science
& Business Media.
134
Références
Bose, J., Reiners, T., Steenken, D., & Voß, S. (2000, January). Vehicle dispatching at seaport
container terminals using evolutionary algorithms. In System Sciences, 2000. Proceedings of
the 33rd Annual Hawaii International Conference on (pp. 10-pp). IEEE.
Boysen, N., Briskorn, D., & Meisel, F. (2017). A generalized classification scheme for crane
scheduling with interference. European Journal of Operational Research, 258(1), 343-357.
Boysen, N., Fliedner, M., Jaehn, F., & Pesch, E. (2013). A survey on container processing in
railway yards. Transportation Science, 47(3), 312-329.
Bray, S., Caggiani, L., & Ottomanelli, M. (2015). Measuring transport systems efficiency under
uncertainty by fuzzy sets theory based Data Envelopment Analysis: theoretical and practical
comparison with traditional DEA model. Transportation Research Procedia, 5, 186-200.
Bruns, F., Goerigk, M., Knust, S., & Schöbel, A. (2014). Robust load planning of trains in
intermodal transportation. OR spectrum, 36(3), 631-668.
Bruzzone, A., Longo, F., Nicoletti, E., & Montanari, R. (2012). Simulation, analysis and
optimization of container terminals processes. International Journal of Modeling, Simulation,
and Scientific Computing, 3(04), 1240006.
Buckley, J. J., & Eslami, E. (2002). An introduction to fuzzy logic and fuzzy sets (Vol. 13).
Springer Science & Business Media.
Caris, A., & Janssens, G. K. (2010). A deterministic annealing algorithm for the pre-and end-
haulage of intermodal container terminals. International Journal of Computer Aided
Engineering and Technology, 2(4), 340-355.
Carlo, H. J., Vis, I. F., & Roodbergen, K. J. (2015). Seaside operations in container terminals:
literature overview, trends, and research directions. Flexible Services and Manufacturing
Journal, 27(2-3), 224-262.
Carson, Y., & Maria, A. (1997, December). Simulation optimization: methods and applications.
In Proceedings of the 29th conference on Winter simulation. IEEE Computer Society, 118-
126.
135
Références
CEC (2006). Keep europe moving – Sustainable mobility for our continent. ISBN: 92-79-
02312-8.
CER (2013). Rail Freight Status Report 2013; rail freight after a decade of EU rail policy.
Chang, D., Yan, W., Chen, C. H., & Jiang, Z. (2008). A berth allocation strategy using heuristics
algorithm and simulation optimisation. International Journal of Computer Applications in
Technology, 32(4), 272-281.
Chang, H., Jula, H., Chassiakos, A., & Ioannou, P. (2008). A heuristic solution for the empty
container substitution problem. Transportation Research Part E: Logistics and
Transportation Review, 44(2), 203-216.
Chen, J. H., Lee, D. H., & Goh, M. (2014). An effective mathematical formulation for the
unidirectional cluster-based quay crane scheduling problem. European Journal of
Operational Research, 232(1), 198-208.
Chen, X., He, S., Li, T., & Li, Y. (2018). A Simulation Platform for Combined Rail/Road
Transport in Multiyards Intermodal Terminals. Journal of Advanced Transportation, 2018.
Chen, X., Zhu, Z., He, X., & Zhang, L. (2015). Surrogate-based optimization for solving a
mixed integer network design problem. Transportation Research Record: Journal of the
Transportation Research Board, (2497), 124-134.
Cheung, R. K., & Chen, C. Y. (1998). A two-stage stochastic network model and solution
methods for the dynamic empty container allocation problem. Transportation science, 32(2),
142-162.
Chung, S. H., & Choy, K. L. (2012). A modified genetic algorithm for quay crane scheduling
operations. Expert Systems with Applications, 39(4), 4213-4221.
Cichenski, M., Jaehn, F., Pawlak, G., Pesch, E., Singh, G., & Blazewicz, J. (2017). An
integrated model for the transshipment yard scheduling problem. Journal of
Scheduling, 20(1), 57-65.
Coco, A. A., Solano-Charris, E. L., Santos, A. C., Prins, C., & de Noronha, T. F. (2014). Robust
optimization criteria: state-of-the-art and new issues. Technical Report UTT-LOSI-14001,
ISSN: 2266-5064.
Correia, I., & da Gama, F. S. (2015). Facility location under uncertainty. In Location science.
Springer, Cham. pp. 177-203.
136
Références
Crainic, T. G., Frangioni, A., & Gendron, B. (2001). Bundle-based relaxation methods for
multicommodity capacitated fixed charge network design. Discrete Applied
Mathematics, 112(1-3), 73-99.
Crainic, T. G., Gendreau, M., & Farvolden, J. M. (2000). A simplex-based tabu search method
for capacitated network design. INFORMS journal on Computing, 12(3), 223-236.
Crainic, T. G., Gendreau, M., & Potvin, J. Y. (2009). Intelligent freight-transportation systems:
Assessment and the contribution of operations research. Transportation Research Part C:
Emerging Technologies, 17(6), 541-557.
Crainic, T. G., Hewitt, M., Toulouse, M., & Vu, D. M. (2016). Scheduled service network
design with resource acquisition and management. EURO Journal on Transportation and
Logistics, 1-33.
Crainic, T. G., Li, Y., & Toulouse, M. (2006). A first multilevel cooperative algorithm for
capacitated multicommodity network design. Computers & Operations Research, 33(9),
2602-2622.
Dang, Q. V., Yun, W. Y., & Kopfer, H. (2012). Positioning empty containers under dependent
demand process. Computers & Industrial Engineering, 62(3), 708-715.
De Camargo, R. S., de Miranda, G., & Løkketangen, A. (2013). A new formulation and an exact
approach for the many-to-many hub location-routing problem. Applied Mathematical
Modelling, 37(12-13), 7465-7480.
Dempster J A.P. (1967). Upper and lower probabilities induced by a multivalued mapping.
Annals of Mathematical Statistics, 38, 325–339.
Di Francesco, M., Lai, M., & Zuddas, P. (2013). Maritime repositioning of empty containers
under uncertain port disruptions. Computers & Industrial Engineering, 64(3), 827-837.
Ding, D., & Chou, M. C. (2015). Stowage planning for container ships: a heuristic algorithm to
reduce the number of shifts. European Journal of Operational Research, 246(1), 242-249.
Ding, H., Benyoucef, L., & Xie, X. (2005). A simulation optimization methodology for supplier
selection problem. International Journal of Computer Integrated Manufacturing, 18(2-3),
210-224.
Ding, J. F., & Chou, C. C. (2013). An evaluation model of quantitative and qualitative fuzzy
multi-criteria decision-making approach for location selection of transshipment
ports. Mathematical Problems in Engineering, 2013.
137
Références
Dong, J. X., & Song, D. P. (2009). Container fleet sizing and empty repositioning in liner
shipping systems. Transportation Research Part E: Logistics and Transportation
Review, 45(6), 860-877.
Dorigo M, Di Caro G (1999) Ant colony optimization: a new meta-heuristic. In: Evolutionary
Computation. CEC 99. Proceedings of the 1999 Congress, IEEE, Vol. 2,1470–1477.
Dorigo, M., & Stützle, T. (2003). The ant colony optimization metaheuristic: Algorithms,
applications, and advances. In Handbook of metaheuristics. Springer, Boston, MA, pp. 250-
285.
Dürr, E., & Giannopoulos, G. A. (2003). SITS: a system for uniform intermodal freight
transport information exchange. International Journal of Transport Management, 1(3), 175-
186.
Ebery, J. (2001). Solving large single allocation p-hub problems with two or three
hubs. European Journal of Operational Research, 128(2), 447-458.
Eksioglu, B., Vural, A. V., & Reisman, A. (2009). The vehicle routing problem: A taxonomic
review. Computers & Industrial Engineering, 57(4), 1472-1483.
El Khoukhi, F., Boukachour, J., & Alaoui, A. E. H. (2017). The “Dual-Ants Colony”: A novel
hybrid approach for the flexible job shop scheduling problem with preventive
maintenance. Computers & Industrial Engineering, 106, 236-255.
Elhedhli, S., & Merrick, R. (2012). Green supply chain network design to reduce carbon
emissions. Transportation Research Part D: Transport and Environment, 17(5), 370-379.
Erera, A. L., Morales, J. C., & Savelsbergh, M. (2005). Global intermodal tank container
management for the chemical industry. Transportation Research Part E: Logistics and
Transportation Review, 41(6), 551-566.
Erera, A. L., Morales, J. C., & Savelsbergh, M. (2009). Robust optimization for empty
repositioning problems. Operations Research, 57(2), 468-483.
138
Références
Expósito-Izquiero, C., Lalla-Ruiz, E., Lamata, T., Melián-Batista, B., & Moreno-Vega, J. M.
(2016). Fuzzy optimization models for seaside port logistics: berthing and quay crane
scheduling. In Computational Intelligence Springer, Cham, 323-343.
Farahani, R. Z., Hekmatfar, M., Arabani, A. B., & Nikbakhsh, E. (2013). Hub location
problems: A review of models, classification, solution techniques, and
applications. Computers & Industrial Engineering, 64(4), 1096-1109.
Ferrucci, F., Bock, S., & Gendreau, M. (2013). A pro-active real-time control approach for
dynamic vehicle routing problems dealing with the delivery of urgent goods. European
Journal of Operational Research, 225(1), 130-141.
Fotuhi, F., & Huynh, N. (2017). Reliable intermodal freight network expansion with demand
uncertainties and network disruptions. Networks and Spatial Economics, 17(2), 405-433.
Frangioni, A., & Gendron, B. (2009). 0–1 reformulations of the multicommodity capacitated
network design problem. Discrete Applied Mathematics, 157(6), 1229-1241.
Fu, M. C. (2002). Optimization for simulation: Theory vs. practice. INFORMS Journal on
Computing, 14(3), 192-215.
Gabrel, V., & Murat, C. (2010). Robustness and duality in linear programming. Journal of the
Operational Research Society, 61(8), 1288-1296.
Gambardella, L. M., Mastrolilli, M., Rizzoli, A. E., & Zaffalon, M. (2001). An optimization
methodology for intermodal terminal management. Journal of Intelligent
Manufacturing, 12(5-6), 521-534.
Ghaderi, A., & Rahmaniani, R. (2016). Meta-heuristic solution approaches for robust single
allocation p-hub median problem with stochastic demands and travel times. The International
Journal of Advanced Manufacturing Technology, 82(9-12), 1627-1647.
Ghaffarinasab, N., Motallebzadeh, A., Jabarzadeh, Y., & Kara, B. Y. (2018). Efficient
simulated annealing based solution approaches to the competitive single and multiple
allocation hub location problems. Computers & Operations Research, 90, 173-192.
Ghamlouche, I., Crainic, T. G., & Gendreau, M. (2004). Path relinking, cycle-based
neighbourhoods and capacitated multicommodity network design. Annals of Operations
research, 131(1-4), 109-133.
139
Références
Goel, A. (2010). The value of in-transit visibility for supply chains with multiple modes of
transport. International Journal of logistics: research and Applications, 13(6), 475-492.
Gounaris, C. E., Repoussis, P. P., Tarantilis, C. D., & Floudas, C. A. (2011). A hybrid branch-
and-cut approach for the capacitated vehicle routing problem. In Computer Aided Chemical
Engineering, 29, 507-511.
Gounaris, C. E., Repoussis, P. P., Tarantilis, C. D., Wiesemann, W., & Floudas, C. A. (2014).
An adaptive memory programming framework for the robust capacitated vehicle routing
problem. Transportation Science, 50(4), 1239-1260.
Gounaris, C. E., Wiesemann, W., & Floudas, C. A. (2013). The robust capacitated vehicle
routing problem under demand uncertainty. Operations Research, 61(3), 677-693.
Grossmann, I. E., Apap, R. M., Calfa, B. A., García-Herreros, P., & Zhang, Q. (2016). Recent
advances in mathematical programming techniques for the optimization of process systems
under uncertainty. Computers & Chemical Engineering, 91, 3-14.
Han, J., Lee, C., & Park, S. (2013). A robust scenario approach for the vehicle routing problem
with uncertain travel times. Transportation science, 48(3), 373-390.
Hansen, P., Mladenović, N., & Pérez, J. A. M. (2010). Variable neighbourhood search: methods
and applications. Annals of Operations Research, 175(1), 367-407.
Harris, I., Wang, Y., & Wang, H. (2015). ICT in multimodal transport and technological trends:
Unleashing potential for the future. International Journal of Production Economics, 159, 88-
103.
He, J., Zhang, W., Huang, Y., & Yan, W. (2013). A simulation optimization method for internal
trucks sharing assignment among multiple container terminals. Advanced Engineering
Informatics, 27(4), 598-614.
Heggen, H., Braekers, K., & Caris, A. (2017). An efficient heuristic for multi-objective train
load planning: a parameter sensitivity analysis.
Herazo-Padilla, N., Montoya-Torres, J. R., Nieto Isaza, S., & Alvarado-Valencia, J. (2015).
Simulation-optimization approach for the stochastic location-routing problem. Journal of
Simulation, 9(4), 296-311.
Hirsch, P., Palfi, A., & Gronalt, M. (2012). Solving a time constrained two-crane routing
problem for material handling with an ant colony optimisation approach: an application in the
roof-tile industry. International Journal of Production Research, 50(20), 6005-6021.
Hoff, A., Lium, A. G., Løkketangen, A., & Crainic, T. G. (2010). A metaheuristic for stochastic
service network design. Journal of Heuristics, 16(5), 653-679.
Iancu, D. A., & Trichakis, N. (2013). Pareto efficiency in robust optimization. Management
Science, 60(1), 130-147.
140
Références
Ilvarez Serrano, J. F. (2006). A heuristic for vessel planning in a reach stacker terminal. Journal
of Maritime Research, 3(1), 3-16.
Irnich, S., & Desaulniers, G. (2005). Shortest path problems with resource constraints.
In Column generation Springer, Boston, MA., pp. 33-65.
Jalilvand-Nejad, A., Shafaei, R., & Shahriari, H. (2016). Robust optimization under correlated
polyhedral uncertainty set. Computers & Industrial Engineering, 92, 82-94.
Jaržemskiene, I. (2007). The evolution of intermodal transport research and its development
issues. Transport, 22(4), 296-306.
Jin, J. G., Lee, D. H., & Hu, H. (2015). Tactical berth and yard template design at container
transshipment terminals: A column generation based approach. Transportation Research Part
E: Logistics and Transportation Review, 73, 168-184.
Jung, J. Y., Blau, G., Pekny, J. F., Reklaitis, G. V., & Eversdyk, D. (2004). A simulation based
optimization approach to supply chain management under demand uncertainty. Computers &
chemical engineering, 28(10), 2087-2106.
Kara, B. Y., & Tansel, B. C. (2000). On the single-assignment p-hub center problem. European
Journal of Operational Research, 125(3), 648-655.
Kaveshgar, N., Huynh, N., & Rahimian, S. K. (2012). An efficient genetic algorithm for solving
the quay crane scheduling problem. Expert Systems with Applications, 39(18), 13108-13117.
Kenyon, A. S., & Morton, D. P. (2003). Stochastic vehicle routing with random travel
times. Transportation Science, 37(1), 69-82.
Kim, K. H., & Park, Y. M. (2004). A crane scheduling method for port container
terminals. European Journal of operational research, 156(3), 752-768.
Ko, H. J., Ko, C. S., & Kim, T. (2006). A hybrid optimization/simulation approach for a
distribution network design of 3PLS. Computers & Industrial Engineering, 50(4), 440-449.
Kouvelis, P., & Yu, G. (2013). Robust discrete optimization and its applications (Vol. 14).
Springer Science & Business Media.
Kreutzberger, E., & Konings, R. (2016). The challenge of appropriate hub terminal and hub-
and-spoke network development for seaports and intermodal rail transport in
Europe. Research in Transportation Business & Management, 19, 83-96.
Laganá, D., Legato, P., Pisacane, O., & Vocaturo, F. (2006). Solving simulation optimization
problems on grid computing systems. Parallel Computing, 32(9), 688-700.
Lam, S. W., Lee, L. H., & Tang, L. C. (2007). An approximate dynamic programming approach
for the empty container allocation problem. Transportation Research Part C: Emerging
Technologies, 15(4), 265-277.
141
Références
Lee, B. K., Jung, B. J., Kim, K. H., Park, S. O., & Seo, J. H. (2006, December). A simulation
study for designing a rail terminal in a container port. In Simulation Conference, 2006. WSC
06. Proceedings of the Winter . IEEE, 1388-1397.
Lee, C., Lee, K., & Park, S. (2012). Robust vehicle routing problem with deadlines and travel
time/demand uncertainty. Journal of the Operational Research Society, 63(9), 1294-1306.
Lee, D. H., Wang, H. Q., & Miao, L. (2008). Quay crane scheduling with non-interference
constraints in port container terminals. Transportation Research Part E: Logistics and
Transportation Review, 44(1), 124-135.
Lee, Y., & Rim, S. C. (2016). Quantitative Model for Supply Chain Visibility: Process
Capability Perspective. Mathematical Problems in Engineering, 2016.
Legato, P., Mazza, R. M., & Gullì, D. (2014). Integrating tactical and operational berth
allocation decisions via simulation–optimization. Computers & Industrial Engineering, 78,
84-94.
Legato, P., Mazza, R. M., & Trunfio, R. (2010). Simulation-based optimization for
discharge/loading operations at a maritime container terminal. OR spectrum, 32(3), 543-567.
Leriche, D., Oudani, M., Cabani, A., Hoblos, G., Mouzna, J., Boukachour, J., & Alaoui, A. E.
H. (2015). Simulating new logistics system of Le Havre Port. IFAC-PapersOnLine, 48(3),
418-423.
Li, L., Negenborn, R. R., & De Schutter, B. (2017). Distributed model predictive control for
cooperative synchromodal freight transport. Transportation Research Part E: Logistics and
Transportation Review, 105, 240-260.
Lim, A., Rodrigues, B., & Xu, Z. (2007). A m‐parallel crane scheduling problem with a non‐
crossing constraint. Naval Research Logistics (NRL), 54(2), 115-127.
Lim, A., Rodrigues, B., Xiao, F., & Zhu, Y. (2004). Crane scheduling with spatial
constraints. Naval Research Logistics (NRL), 51(3), 386-406.
Lim, S. J., Jeong, S. J., Kim, K. S., & Park, M. W. (2006). A simulation approach for
production-distribution planning with consideration given to replenishment policies. The
International Journal of Advanced Manufacturing Technology, 27(5-6), 593-603.
Lin, C. C., & Chen, S. H. (2008). An integral constrained generalized hub-and-spoke network
design problem. Transportation Research Part E: Logistics and Transportation
Review, 44(6), 986-1003.
Liu, C. I., Jula, H., Vukadinovic, K., & Ioannou, P. (2004). Automated guided vehicle system
for two container yard layouts. Transportation Research Part C: Emerging
Technologies, 12(5), 349-368.
Lodwick, W. A., & Untiedt, E. (2010). Introduction to fuzzy and possibilistic optimization.
In Fuzzy Optimization Springer, Berlin, Heidelberg, pp. 33-62.
142
Références
López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., & Stützle, T. (2016). The
irace package: Iterated racing for automatic algorithm configuration. Operations Research
Perspectives, 3, 43-58.
Lu, B., & Park, N. K. (2013). Sensitivity analysis for identifying the critical productivity factors
of container terminals. Journal of Mechanical Engineering, 59(9), 536-546.
Lu, Z., Han, X., Xi, L., & Erera, A. L. (2012). A heuristic for the quay crane scheduling problem
based on contiguous bay crane operations. Computers & Operations Research, 39(12), 2915-
2928.
Luathep, P., Sumalee, A., Lam, W. H., Li, Z. C., & Lo, H. K. (2011). Global optimization
method for mixed transportation network design problem: a mixed-integer linear
programming approach. Transportation Research Part B: Methodological, 45(5), 808-827.
Luhandjula, M. K., & Gupta, M. M. (1996). On fuzzy stochastic optimization. Fuzzy Sets and
Systems, 81(1), 47-55.
Magnanti, T. L., & Wong, R. T. (1984). Network design and transportation planning: Models
and algorithms. Transportation science, 18(1), 1-55.
Marín, A. (2005). Formulating and solving splittable capacitated multiple allocation hub
location problems. Computers & operations research, 32(12), 3093-3109.
Meisel, F., & Bierwirth, C. (2011). A unified approach for the evaluation of quay crane
scheduling models and algorithms. Computers & Operations Research, 38(3), 683-693.
Meng, Q., & Wang, T. (2010). A chance constrained programming model for short-term liner
ship fleet planning problems. Marit. Pol. Mgmt., 37(4), 329-346.
Meng, Q., Wang, T., & Wang, S. (2012). Short-term liner ship fleet planning with container
transshipment and uncertain container shipment demand. European Journal of Operational
Research, 223(1), 96-105.
Meraklı, M., & Yaman, H. (2016). Robust intermodal hub location under polyhedral demand
uncertainty. Transportation Research Part B: Methodological, 86, 66-85.
143
Références
Michael, P. (1995). Scheduling, theory, algorithms, and systems. Englewood Cli s, New Jersey.
Minoux, M. (1989). Networks synthesis and optimum network design problems: Models,
solution methods and applications. Networks, 19(3), 313-360.
Mirjalili, S., & Lewis, A. (2016). Obstacles and difficulties for robust benchmark problems: A
novel penalty-based robust optimisation method. Information Sciences, 328, 485-509.
Moccia, L., Cordeau, J. F., Gaudioso, M., & Laporte, G. (2006). A branch‐and‐cut algorithm
for the quay crane scheduling problem in a container terminal. Naval Research Logistics
(NRL), 53(1), 45-59.
Moccia, L., Cordeau, J. F., Laporte, G., Ropke, S., & Valentini, M. P. (2011). Modeling and
solving a multimodal transportation problem with flexible‐time and scheduled
services. Networks, 57(1), 53-68.
Moghadam, B., & Seyedhosseini, S. (2010). A particle swarm approach to solve vehicle routing
problem with uncertain demand: A drug distribution case study. International Journal of
Industrial Engineering Computations, 1(1), 55-64.
Moghaddam, B. F., Ruiz, R., & Sadjadi, S. J. (2012). Vehicle routing problem with uncertain
demands: An advanced particle swarm algorithm. Computers & Industrial
Engineering, 62(1), 306-317.
Monaco, M. F., & Sammarra, M. (2011). Quay crane scheduling with time windows, one-way
and spatial constraints. International Journal of Shipping and Transport Logistics, 3(4), 454-
474.
Monaco, M. F., Sammarra, M., & Sorrentino, G. (2014). The terminal-oriented ship stowage
planning problem. European Journal of Operational Research, 239(1), 256-265.
Montemanni, R., Gambardella, L. M., Rizzoli, A. E., & Donati, A. V. (2005). Ant colony
system for a dynamic vehicle routing problem. Journal of Combinatorial Optimization, 10(4),
327-343.
Mudchanatongsuk, S., Ordóñez, F., & Liu, J. (2008). Robust solutions for network design under
transportation cost and demand uncertainty. Journal of the Operational Research
Society, 59(5), 652-662.
Munim, Z. H., & Haralambides, H. (2018). Competition and cooperation for intermodal
container transhipment: A network optimization approach. Research in Transportation
Business & Management, 26, 87-99.
Nagy, G., & Salhi, S. (1998). The many-to-many location-routing problem. Top, 6(2), 261-275.
144
Références
Nguyen, S., Zhang, M., Johnston, M., & Tan, K. C. (2013). Hybrid evolutionary computation
methods for quay crane scheduling problems. Computers & Operations Research, 40(8),
2083-2093.
Noorizadegan, M., Galli, L., & Chen, B. (2012). On the heterogeneous vehicle routing problem
under demand uncertainty.
Noteboom, T. (2009, July). Les Ports Maritimes et leur arrière-pays intermodal: Relations dans
le cadre des chaînes d’approvisionnement internationales-Les défis pour l’Europe,”. In Forum
International des Transports, Table Ronde: Concurrence entre les ports et liaisons terrestres
avec l’arrière-pays, 27-81.
Ordóñez, F., & Zhao, J. (2007). Robust capacity expansion of network flows. Networks: An
International Journal, 50(2), 136-145.
Oudani, M., Leriche, D., Boukachour, J., Cabani, A., Hoblos, G., & Alaoui, A. E. H. (2015).
Optimisation et simulation d’un problème d’affectation des trains aux voies dans le Terminal
Multimodal du Havre. In 16ème conférence ROADEF de la Société Française de Recherche
Opérationnelle et Aide à la Décision, Marseille, France.
Pazour, J. A., Meller, R. D., & Pohl, L. M. (2010). A model to design a national high-speed rail
network for freight distribution. Transportation Research Part A: Policy and Practice, 44(3),
119-135.
Pearce, R. H., & Forbes, M. (2018). Disaggregated Benders decomposition and branch-and-cut
for solving the budget-constrained dynamic uncapacitated facility location and network design
problem. European Journal of Operational Research.
Peterkofsky, R. I., & Daganzo, C. F. (1990). A branch and bound solution method for the crane
scheduling problem. Transportation Research Part B: Methodological, 24(3), 159-172.
Pishvaee, M. S., Rabbani, M., & Torabi, S. A. (2011). A robust optimization approach to closed-
loop supply chain network design under uncertainty. Applied Mathematical Modelling, 35(2),
637-649.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing
problem. Computers & Operations Research, 31(12), 1985-2002.
Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop
scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational
Research, 155(2), 426-438.
Reis, V., Meier, J. F., Pace, G., & Palacin, R. (2013). Rail and multi-modal transport. Research
in Transportation Economics, 41(1), 17-30.
145
Références
Ries, J., González-Ramírez, R. G., & Miranda, P. (2014, September). A fuzzy logic model for
the container stacking problem at container terminals. In International Conference on
Computational Logistics. Springer, Cham, 93-111.
Rizzoli, A. E., Fornara, N., & Gambardella, L. M. (2002). A simulation tool for combined
rail/road transport in intermodal terminals. Mathematics and Computers in Simulation, 59(1-
3), 57-71.
Rondinelli, D., & Berry, M. (2000). Multimodal transportation, logistics, and the environment:
managing interactions in a global economy. European Management Journal, 18(4), 398-410.
Ross, T. J. (2009). Fuzzy logic with engineering applications. John Wiley & Sons.
Rouky, N., Abourraja, M., Boukachour, J., Boudebous, D., Alaoui, A., & Khoukhi, F. (2019).
Simulation optimization based ant colony algorithm for the uncertain quay crane scheduling
problem. International Journal of Industrial Engineering Computations, 10(1), 111-132.
Rouky, N., Boukachour, J., Alaoui, A.E.H, El Khoukhi, F., & Boudebous D. (2015). Un
algorithme d’optimisation par colonie de fourmis pour l’ordonnancement des grues de quai.
JD-JN- MACS, Bourges, France.
Rouky, N., Boukachour, J., Boudebous, D., & Alaoui, A. E. H. (2018). A Robust Metaheuristic
for the Rail Shuttle Routing Problem with Uncertainty: A Real Case Study in the Le Havre
Port. The Asian Journal of Shipping and Logistics, 34(2), 171-187.
Rouky, N., Boukachour, J., Boudebous, D., & Alaoui, A. E. H. (2016). Optimisation des
tournées des navettes ferroviaires sous incertitudes dans le port du Havre. 17ème congrès de
la Société Française de la Recherche Opérationnelle et d’Aide à la Décision. ROADEF.
Rouky, N., Couzin, P., Boukachour, J., Boudebous, D., Alaoui, A., & Alaoui, A. E. H. (2018).
Optimization of Containers Transfer in Le Havre Port: a New Algorithm for the Railway
Transportation System. IFAC-PapersOnLine, 51(11), 1676-1681.
Sammarra, M., Cordeau, J. F., Laporte, G., & Monaco, M. F. (2007). A tabu search heuristic
for the quay crane scheduling problem. Journal of Scheduling, 10(4-5), 327-336.
Segura, F. G., Segura, E. L., Moreno, E. V., & Uceda, R. A. (2017, September). A fully fuzzy
linear programming model to the berth allocation problem. In Computer Science and
Information Systems (FedCSIS), 2017 Federated Conference on (pp. 453-458). IEEE.
146
Références
Shang, X. T., Cao, J. X., & Ren, J. (2016). A robust optimization approach to the integrated
berth allocation and quay crane assignment problem. Transportation Research Part E:
Logistics and Transportation Review, 94, 44-65.
Shapiro, A., Dentcheva, D., & Ruszczyński, A. (2009). Lectures on stochastic programming:
modeling and theory. Society for Industrial and Applied Mathematics.
Smets, P., & Kennes, R. (1994). The transferable belief model. Artificial intelligence, 66(2),
191-234.
Solano-Charris, E., Prins, C., & Santos, A. C. (2015). Local search based metaheuristics for the
robust vehicle routing problem with discrete scenarios. Applied Soft Computing, 32, 518-531.
Solano-Charris, E. L., Prins, C., & Santos, A. C. (2016). Solving the bi-objective Robust
Vehicle Routing Problem with uncertain costs and demands. RAIRO-Operations
Research, 50(4-5), 689-714.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time
window constraints. Operations research, 35(2), 254-265.
Song, D. P., & Dong, J. X. (2012). Cargo routing and empty container repositioning in multiple
shipping service routes. Transportation Research Part B: Methodological, 46(10), 1556-
1575.
Steenken, D., Voß, S., & Stahlbock, R. (2004). Container terminal operation and operations
research-a classification and literature review. OR spectrum, 26(1), 3-49.
Steenken, D., Winter, T., & Zimmermann, U. T. (2001). Stowage and transport optimization in
ship planning. In Online optimization of large scale systems (pp. 731-745). Springer, Berlin,
Heidelberg.
Sungur, I., Ordónez, F., & Dessouky, M. (2008). A robust optimization approach for the
capacitated vehicle routing problem with demand uncertainty. IIE Transactions, 40(5), 509-
523.
Tang, J., Wang, D. W., Fung, R. Y., & Yung, K. L. (2004). Understanding of fuzzy
optimization: theories and methods. Journal of Systems Science and Complexity, 17(1), 117-
136.
Thiruvady, D., Ernst, A. T., & Singh, G. (2016). Parallel ant colony optimization for resource
constrained job scheduling. Annals of Operations Research, 242(2), 355-372.
147
Références
Toklu, N. E., Gambardella, L. M., & Montemanni, R. (2014). A multiple ant colony system for
a vehicle routing problem with time windows and uncertain travel times. Journal of Traffic
and Logistics Engineering, 2(1).
Toklu, N. E., Montemanni, R., & Gambardella, L. M. (2013, April). An ant colony system for
the capacitated vehicle routing problem with uncertain travel costs. In Swarm Intelligence
(SIS), 2013 IEEE Symposium on (pp. 32-39). IEEE.
Tongzon, J., & Heng, W. (2005). Port privatization, efficiency and competitiveness: Some
empirical evidence from container ports (terminals). Transportation Research Part A: Policy
and Practice, 39(5), 405-424.
Topaloglu, H. (2006). A parallelizable dynamic fleet management model with random travel
times. European Journal of Operational Research, 175(2), 782-805.
Topaloglu, H., & Powell, W. B. (2005). A distributed decision-making structure for dynamic
resource allocation using nonlinear functional approximations. Operations Research, 53(2),
281-297.
Topaloglu, H., & Powell, W. B. (2007). Sensitivity analysis of a dynamic fleet management
model using approximate dynamic programming. Operations research, 55(2), 319-331.
Tréfond, S., Billionnet, A., Elloumi, S., Djellab, H., & Guyon, O. (2017). Optimization and
simulation for robust railway rolling-stock planning. Journal of Rail Transport Planning &
Management, 7(1-2), 33-49.
Tsang, H. T., & Mak, H. Y. (2015). Robust Optimization Approach to Empty Container
Repositioning in Liner Shipping. In Handbook of Ocean Container Transport Logistics (pp.
209-229). Springer, Cham.
Unsal, O., & Oguz, C. (2013). Constraint programming approach to quay crane scheduling
problem. Transportation Research Part E: Logistics and Transportation Review, 59, 108-
122.
Van Hui, Y., Gao, J., Leung, L., & Wallace, S. (2014). Airfreight forwarder’s shipment
planning under uncertainty: A two-stage stochastic programming approach. Transportation
Research Part E: Logistics and Transportation Review, 66, 83-102.
Verdonck, L., Caris, A., Ramaekers, K., & Janssens, G. K. (2014). Analysis of the operations
of an intermodal barge terminal. International Journal of Simulation and Process
Modelling, 9(1-2), 3-15.
148
Références
Verweij, K. (2011). Synchronic modalities – Critical success factors. In P. J. van der Sterre
(Ed.), Logistics yearbook edition 2011. Rotterdam (pp. 75–88). ISBN: 978-90-79470-00-6.
Vidović, M., Zečević, S., Kilibarda, M., Vlajić, J., Bjelić, N., & Tadić, S. (2011). The p-hub
model with hub-catchment areas, existing hubs, and simulation: A case study of Serbian
intermodal terminals. Networks and Spatial Economics, 11(2), 295-314.
Viswanath, K., & Peeta, S. (2003). Multicommodity maximal covering network design problem
for planning critical routes for earthquake response. Transportation Research Record:
Journal of the Transportation Research Board, (1857), 1-10.
Wang, B., & Yang, T. (2012). Stochastic optimization of empty container repositioning of sea
carriage. In Advanced Materials Research (Vol. 340, pp. 324-330). Trans Tech Publications.
Wang, R., Yang, K., Yang, L., & Gao, Z. (2018). Modeling and optimization of a road–rail
intermodal transport system under uncertain information. Engineering Applications of
Artificial Intelligence, 72, 423-436.
Wang, Y., & Kim, K. H. (2011). A quay crane scheduling algorithm considering the workload
of yard cranes in a container yard. Journal of intelligent manufacturing, 22(3), 459-470.
Wiegmans, B. W., Stekelenburg, D. T., Versteegt, C., & Bontekoning, Y. M. (2007). Modeling
rail-rail exchange operations: An analysis of conventional and new-generation
terminals. Transportation Journal, 5-20.
WU, Z., SONG, T., & ZHAO, K. (2006). Selection of Container Shipping Routes [J]. Journal
of Southwest Jiaotong University, 3.
Yu, G., & Yang, J. (1998). On the robust shortest path problem. Computers & Operations
Research, 25(6), 457-468.
Yücel, A., & Güneri, A. F. (2011). A weighted additive fuzzy programming approach for multi-
criteria supplier selection. Expert Systems with Applications, 38(5), 6281-6286.
Zeng, Q., & Yang, Z. (2009). Integrating simulation and optimization to schedule loading
operations in container terminals. Computers & Operations Research, 36(6), 1935-1944.
Zetina, C. A., Contreras, I., Cordeau, J. F., & Nikbakhsh, E. (2017). Robust uncapacitated hub
location. Transportation Research Part B: Methodological, 106, 393-410.
149
Références
Zhou, Y., Wang, W., Song, X., & Guo, Z. (2016). Simulation-based optimization for yard
design at mega container terminal under uncertainty. Mathematical Problems in
Engineering, 2016.
Zhu, E., Crainic, T. G., & Gendreau, M. (2014). Scheduled service network design for freight
rail transportation. Operations research, 62(2), 383-400.
Zhu, Y., & Lim, A. (2006). Crane scheduling with non-crossing constraint. Journal of the
Operational Research Society, 57(12), 1464-1471.
150
Références
Webbliographie :
“ASLOG” Guide Pratique du Transport Multimodal. [Link]
[Link]
AIPCR (2013), Les terminaux intermodaux de marchandises : défis et bonnes pratiques. Comité
technique B.4 de l’AIPCR – Transport de marchandises et intermodalité. [Link]
Garnier C. (2015). La bataille du port du Havre se joue sur terre. Usine Nouvelle [online].
[Link]/article/la-bataille-du-port-du-havre-se-joue-sur-terre.N359024
Multimethod Simulation Software and Solutions, accessed on, Nov. 22, 2015. [Online].
Available: [Link]
UNCTAD (2014) Review of Maritime Transport 2014. United Nations Conference on Trade
and Development (UNCTAD), New York and Geneva.
[Link]
151
152
Optimisation et Simulation de la Massification du Transport Multimodal de
Conteneurs
Résumé : Les ports maritimes se confrontent aujourd'hui à des exigences rigoureuses imposées
par l'évolution de la taille de la flotte mondiale des porte-conteneurs, l’accroissement de la
concurrence et des zones de stockage qui arrivent à des niveaux de saturation très élevés. Pour
répondre à ces défis, plusieurs ports ont décidé de créer des terminaux multimodaux qui jouent
le rôle de méga-hubs pour les terminaux maritimes, en vue de libérer les zones de stockage de
ces terminaux, de développer la part du transport massifié de conteneurs et de réduire les
émissions des gaz à effet de serre en utilisant des modes alternatifs à la route. Néanmoins, la
gestion de ces nouveaux schémas logistiques est laborieuse. Cela s’explique par plusieurs
facteurs, entre autres, la nature dynamique et distribuée de ces systèmes, la diversité des
opérations, et l’incertitude et le manque des informations nécessaires au contrôle de flux. En
effet, les opérateurs portuaires se trouvent face à plusieurs problèmes de décision complexes,
tels que : les problèmes de tournées et les problèmes d'ordonnancement. La finalité de cette
thèse est de développer des approches capables de répondre aux besoins des opérateurs
portuaires dans un terminal multimodal, avec prise en compte des différentes sources
d’incertitudes. Deux problèmes d'optimisation sont principalement considérés dans cette thèse,
à savoir : l'optimisation de tournées de navettes ferroviaires (en anglais : the Rail Shuttle
Routing Problem (RSRP)) et l'ordonnancement de grues de quai (en anglais : the Quay Crane
Scheduling Problem (QCSP)). En vue d'aborder la complexité et l’aspect incertain de ces
problèmes, nous proposerons des modélisations mathématiques, ainsi que des approches de
résolution basées sur l’optimisation par colonies de fourmis, l’optimisation robuste et le
couplage Simulation-Optimisation. Les différents tests numériques effectués dans ce travail ont
prouvé l’efficacité des algorithmes proposés et leur robustesse face aux différentes sources
d’incertitudes.
Mots clés : Logistique portuaire ; Transport multimodal ; Simulation-Optimisation ;
Optimisation robuste.
153