[PDF] Modélisation et Optimisation dun Système de Transport à la

View - Download Modélisation et Optimisation dun Système de Transport à la

Previous PDF

Next PDF

Numéro d"ordre : D.U.

EDSPIC :

Université Blaise Pascal - Clermont-Ferrand II

Ecole doctorale : Sciences Pour l"Ingénieur deClermont-Ferrand

Thèse

Présentée par

Samuel DELEPLANQUE

pour obtenir le grade de

Docteur d"Université

Spécialité : Informatique

Modélisation et résolution de problèmes difficiles de transport à la demande et deLot-Sizing Soutenue publiquement le 12 Septembre 2014 devant le jury composé de : Président :DominiqueFeillet- Prof. aux Mines, Saint-Etienne Rapporteur :AzizMoukrim- Prof. à l'UT, Compiègne Directeurs de thèse :AlainQuilliot- Prof. à l'UBP, Clermont-Ferrand II Jean-PierreDerutin- Prof. à l'UBP, Clermont-Ferrand II " La connaissance du chemin ne peut pas se substituer au fait de mettre un pied devant l"autre.»

Mary Caroline Richards

Remerciements

Je tiens à adresser mes plus sincères remerciements à Messieurs Alain Quilliot et Jean-Pierre Dérutin pour leurs judicieux conseils, leur apport critique et leur di- rection attentive au cours de ces années de recherche. Je remercie à nouveau M. Quilliot pour son accueil au sein du LIMOS (Informatique, Modélisation et Optimi- sation des Systèmes, UMR CNRS 6158) qu"il dirige : le dynamisme du laboratoire et la motivation de ses membres m"ont permis de travailler avec, j"espère, efficacité et dans un climat de confiance. Malgré la direction du laboratoire, M. Quilliot a su trouver le temps pour me soutenir. Je tiens également à exprimer ma profonde reconnaissance à tous les étudiants, techniciens, ingénieurs et chercheurs que j"ai côtoyés le long de ces trois années et en particulier à : - Madame Safia Kedad-Sidhoum avec laquelle il fut très agréable de travailler sur le Lot-Sizing. Elle m"accueillit plusieurs fois au LIP6, m"encouragea à ma première présentation en anglais à Oxford et m"aida à la rédaction d"un premier article; - Ana Luísa Marques et Luiza Bernardes Real que j"ai "tuteurées" lors de leur projet et de leur stage d"ingénieurs; mais aussi Benoit Bernay, ingénieur au LIMOS. Ils ont tous les trois travaillé avec un grand sérieux sur le problème de la minimisation du nombre d"arrêts; - Messieurs Philippe Vaslin et Marc Davis, le premier, maître de conférence au LIMOS et le second, son doctorant qui réalisa sa thèse en même temps que moi. Nous avons tous les trois travaillé dans une excellente ambiance au sein du même bureau à l"ISIMA; - Hélène Toussaint, ingénieur de recherche, dont j"ai pu apprécier la gentillesse, l"expérience et la compétence; - Khouloud Boukadi, aujourd"hui maître de conférence à Sfax - Tunisie -, qui m"a longtemps fait partagé son expérience de doctorante à l"école des mines de Saint- Etienne lors de son ATER au LIMOS. Ce sont nos échanges qui m"ont motivé pour faire de même; Je n"oublie pas non plus les autres membres du laboratoire qui rendent la vie quotidienne très agréable (Claude, Nicolas, Béa, M. Hou et bien d"autres); Enfin, je ne peux qu"avoir une pensée pour mes parents et mon frère : tous les trois ont su être présents, attentifs et m"épauler notamment pour la relecture de ce mémoire. 5

Table des matières

Remerciements 3

Introduction 14

1 Généralités sur l"algorithmique et la Recherche Opérationnelle 19

1.1 Algorithmique et notion de Complexité . . . . . . . . . . . . . . . . . 19

1.1.1 Généralités sur les algorithmes . . . . . . . . . . . . . . . . . . 19

1.1.2 Les problèmes et leur Complexité . . . . . . . . . . . . . . . . 21

1.2 Programmes linéaires et graphes . . . . . . . . . . . . . . . . . . . . . 22

1.3 Principaux schémas algorithmiques . . . . . . . . . . . . . . . . . . . 25

1.3.1 Algorithmes gloutons et processus de Monte Carlo . . . . . . . 25

1.3.2 Algorithmes de "Transformations Locales" . . . . . . . . . . . 26

1.3.3 Exploration Arborescente . . . . . . . . . . . . . . . . . . . . 28

2 Les systèmes innovants de mobilité31

2.1 Les services innovants de transports . . . . . . . . . . . . . . . . . . . 31

2.1.1 Le transport à la demande . . . . . . . . . . . . . . . . . . . . 32

2.1.2 Les véhicules partagés . . . . . . . . . . . . . . . . . . . . . . 33

2.2 Les véhicules de nouvelles générations . . . . . . . . . . . . . . . . . . 35

2.2.1 Besoins et cibles d"un nouveau type de véhicule . . . . . . . . 35

2.2.2 Les systèmes et véhicules autonomes . . . . . . . . . . . . . . 37

2.2.3 L"intégration des véhicules autonomes . . . . . . . . . . . . . . 41

2.3 Modélisations des problèmes de tournées de véhicules . . . . . . . . . 42

2.4 Méthodes de résolution du DARP . . . . . . . . . . . . . . . . . . . . 47

2.5 Les problèmes couplant transport et production . . . . . . . . . . . . 55

3 Modélisation et résolution du DARP statique57

3.1 Le modèle DARP statique . . . . . . . . . . . . . . . . . . . . . . . . 58

3.1.1 Réseau réel et réseau réduit . . . . . . . . . . . . . . . . . . . 58

3.1.2 Validité d"une Tournée et Collection de Tournées datées . . . . 60

3.1.3 Evaluation d"une Tournée et d"une collection de Tournées . . . 61

3.1.4 Modèle DARP Standard . . . . . . . . . . . . . . . . . . . . . 62

3.1.5 Le modèle mathématique adapté de [Cordeau (2006)] . . . . . 64

3.2 Procédés de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . 65

3.2.1 Gestion des contraintes et évaluation des insertions . . . . . . 65

6 TABLE DES MATIÈRES

3.2.2 Processus d"horodatage . . . . . . . . . . . . . . . . . . . . . . 67

3.2.3 Algorithme d"insertions successives . . . . . . . . . . . . . . . 70

3.2.4 Renforcement du processus d"insertion . . . . . . . . . . . . . 74

3.3 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . 78

3.3.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

3.3.2 Environnement et performances . . . . . . . . . . . . . . . . . 78

3.3.3 La 1

èrebatterie de tests . . . . . . . . . . . . . . . . . . . . . . 79

3.3.4 La 2

èmebatterie de tests . . . . . . . . . . . . . . . . . . . . . 82

3.3.5 La 3

èmebatterie de tests . . . . . . . . . . . . . . . . . . . . . 85

4 Modélisation et résolution du DARP statique avec division de la

charge - DARPSL 89

4.1 Le modèle DARPSL statique . . . . . . . . . . . . . . . . . . . . . . . 90

4.1.1 Réseau réduit virtuel . . . . . . . . . . . . . . . . . . . . . . . 90

4.1.2 Tournées, tournées valides, système de tournées admissible . . 91

4.1.3 Evaluation d"une tournée . . . . . . . . . . . . . . . . . . . . . 91

4.1.4 Synthèse du modèle DARPSL . . . . . . . . . . . . . . . . . . 92

4.1.5 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

4.2 Procédés de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . 94

4.2.1 Principe général . . . . . . . . . . . . . . . . . . . . . . . . . . 95

4.2.2 Synthèse sur la résolution du DARPSL . . . . . . . . . . . . . 97

4.3 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . 100

4.3.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

4.3.2 Protocole expérimental . . . . . . . . . . . . . . . . . . . . . . 100

4.3.3 La 1

èrebatterie de tests . . . . . . . . . . . . . . . . . . . . . . 101

4.3.4 La 2

èmebatterie de tests . . . . . . . . . . . . . . . . . . . . . 104

5 Modélisation et résolution du DARP statique avec transferts -

DARPT 107

5.1 Le modèle DARPT statique . . . . . . . . . . . . . . . . . . . . . . . 108

5.1.1 Réseau réduit . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

5.1.2 Tournées, tournéesvalides, système de tournéesadmissible. . 111

5.1.3 Synthèse des INPUT et OUTPUT du DARPT . . . . . . . . 112

5.2 Procédés de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . 112

5.2.1 Principe général . . . . . . . . . . . . . . . . . . . . . . . . . 112

5.2.2 Gestion des paramètres de INSERTT . . . . . . . . . . . . . . 113

5.2.3 Synthèse du processus de test et d"évaluation d"une insertion . 120

5.2.4 Processus général de résolution . . . . . . . . . . . . . . . . . 120

5.3 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . 125

5.3.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

5.3.2 Environnement et performances . . . . . . . . . . . . . . . . . 125

5.3.3 Les instances . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

5.3.4 Résultats et analyse . . . . . . . . . . . . . . . . . . . . . . . 127

TABLE DES MATIÈRES 7

6 Introduction à la robustesse dans le DARP dynamique - DARPRob133

6.1 Anticipation dans le DARP statique - Notion d"Insérabilité. . . . . . 135

6.1.1 Mesure d"

Insérabilitéet optimisation de l"Insérabilité. . . . . 135

6.1.2 Adaptation des procédures du DARP à l"Insérabilité. . . . . 136

6.1.3 Prise en compte de rejets de demandes . . . . . . . . . . . . . 139

6.1.4 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . 142

6.2 Robustesse dans le DARP dynamique . . . . . . . . . . . . . . . . . 146

6.2.1 La demande virtuelleDV. . . . . . . . . . . . . . . . . . . . 147

6.2.2 Le modèle "DARP local" - MAIN-ROUTE . . . . . . . . . . . 149

6.2.3 Processus d"insertion . . . . . . . . . . . . . . . . . . . . . . . 149

6.2.4 Le problème des rendez-vous . . . . . . . . . . . . . . . . . . . 150

6.2.5 DARP dynamique : Synthèse . . . . . . . . . . . . . . . . . . 156

6.2.6 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

6.2.6.1 Etats du système . . . . . . . . . . . . . . . . . . . . 159

6.2.6.2 Transitions . . . . . . . . . . . . . . . . . . . . . . . 160

6.2.7 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . 164

7 DARP statique avec contraintes de fiabilité - DARPRel 169

7.1 Modèles mathématiques statiques . . . . . . . . . . . . . . . . . . . . 172

7.1.1 Modèles sur topologie Ligne . . . . . . . . . . . . . . . . . . . 172

7.1.2 Modèles sur topologie Circuit . . . . . . . . . . . . . . . . . . 176

7.2 Procédés de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . 180

7.2.1 Une méthode exacte sur topologie Ligne . . . . . . . . . . . . 180

7.2.2 Deux approches par insertions sur topologie Ligne . . . . . . . 185

7.2.3 Adaptation des procédures du DARP à la topologie Circuit . . 187

7.3 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . 190

8 Heuristique lagrangienne pour un problème deLot-Sizingavec ca-

pacités de transfert et stockage199

8.1 Définition du problème et formulation mathématique . . . . . . . . . 201

8.2 Reformulation du MLS-STPC en problème de multi-flots . . . . . . . 203

8.3 Résolution du MLS-STPC par relaxation lagrangienne . . . . . . . . 205

8.4 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . 209

8.4.1 Résolution exacte du problème de localisation - partie 1 . . . . 210

8.4.2 Expérimentations avec résolution heuristique FACLOC . . . . 210

8.4.3 Résolution exacte du problème de localisation - partie 2 . . . . 212

Conclusion Générale215

Acronymes217

Bibliographie228

9

Table des figures

1 Intégration du VIPA dans le transport intermodal . . . . . . . . . . . 16

1.1 Graphe de Petersen au nombre chromatique de 3 . . . . . . . . . . . 23

1.3 Formulation d"un problème deLot-Sizingen un problème de flots . . 24

2.1 Taux d"utilisation des transports dans la ville de Coimbra . . . . . . . 31

2.2 Les PRT de Heathrow et Morgantown . . . . . . . . . . . . . . . . . 37

2.3 Deux Cycabs de l"Institut Pascal (ex LASMEA) . . . . . . . . . . . . 38

2.4 Le Yamaha AGV à Coimbra et les Serpentines à Lausanne . . . . . . 39

2.5 Le VIPA au salon de l"automobile de 2010 . . . . . . . . . . . . . . . 39

2.6 Mise en service duCybusà la Rochelle . . . . . . . . . . . . . . . . . 41

2.7 Une solution du TSP d"une instance à 4 villes . . . . . . . . . . . . . 42

2.8 Une solution du VRP d"une instance à 8 demandes . . . . . . . . . . 43

2.9 Une solution du PDP d"une instance à 4 demandes . . . . . . . . . . 44

2.10 Télébus de Berlin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.1 Exemple de segment d"une liste . . . . . . . . . . . . . . . . . . . . . 58

3.2 Exemple de graphe pour le DARP Standard . . . . . . . . . . . . . . 62

3.3 Solution de l"exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3.4 Solution de l"exemple 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3.5 Propagation de R1 et R2 sur deux noeuds successifs . . . . . . . . . . 66

3.6 Propagation de contraintes pour tester l"insertion d"un nouveau noeud

origineoi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.7GrapheNonCompatibledeux véhicules et deux demandes . . . . . . . 75

3.8 Coloration : état initial et état final de l"exemple . . . . . . . . . . . . 77

3.9 Moments entre deux noeuds d"une tournée . . . . . . . . . . . . . . . 83

4.1 Principe de la préemption de charge . . . . . . . . . . . . . . . . . . . 93

4.2 Respect des contraintes de temps avec une demande satisfaite par

deux tournées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

4.3 Partage d"une chargeQisur deux véhicules . . . . . . . . . . . . . . . 94

4.4 DARPSL - Série 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

5.1 Exemple de transbordement d"une demandeipar deux véhicules . . . 108

5.2 Transbordement sur un noeud relais dédoublé en émetteur et récepteur110

10 TABLE DES FIGURES

5.3 exemple de Fermeture . . . . . . . . . . . . . . . . . . . . . . . . . . 114

5.4 Transbordement d"une demande avec respect des contraintes de temps116

5.5 Trace de 7 itérationsXidu processusEvalTourTen situation d"in-

terblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

5.6 Schéma général de résolution du DARP avec transferts . . . . . . . . 122

5.7 Espaces Prioritaires et dépôts de 4 sous-flottes . . . . . . . . . . . . . 126

5.8 Minimisation indirecte des temps de connexion - Instance pr01 . . . . 127

5.9 Rendu du processus declustering. . . . . . . . . . . . . . . . . . . . 129

5.10 Intégration de la division de charge au schéma général de résolution . 131

5.11 Schéma général avec les 3 heuristiques de résolution . . . . . . . . . . 131

6.1 Contraction des fenêtres de temps . . . . . . . . . . . . . . . . . . . . 134

6.2 Relevé de la valeurINSERle long de la résolution de pr10 . . . . . . 143

6.3 Variation des valeursINSER. . . . . . . . . . . . . . . . . . . . . . . 145

6.4 Principaux processus autour des résolutions locales dans le DARP

dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

6.5 Flexibilité des tournées suite aux premiers rendez-vous . . . . . . . . 150

6.6 Enchaînement des processus DEC et ROUTE . . . . . . . . . . . . . 156

7.1 Aires d"échanges, voie principale et dépôt d"une flotte de VIPA . . . . 169

7.2 Profil de la vitesse d"un VIPA . . . . . . . . . . . . . . . . . . . . . . 170

7.3 Jeu de la minimisation du nombre d"arrêt . . . . . . . . . . . . . . . . 175

7.4 Exemple : fenêtres de temps associées à un même label . . . . . . . . 188

7.5 Minimisation des arrêts avec stations dynamiques et sens bidirectionnel198

8.1 Exemple du problème MLS-STPC avec 2 usines et 2 périodes . . . . 204

11

Liste des tableaux

2.1 Les principaux facteurs humains dans les accidents de la route en France 36

2.2 Contraintes des principaux problèmes de transport . . . . . . . . . . 46

3.1 Paramètres d"un exemple sur le DARP Standard . . . . . . . . . . . . 62

3.2 Pondération des deux exemples sur le DARP Standard . . . . . . . . 63

3.3 Populations de véhicules et de demandes pour les instances traitées . 80

3.4 Résultats d"

INSERTIONet de [Cordeau and Laporte (2003)] (suf-

fixe C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

3.5 Résultats obtenus par [Parragh et al. (2010)] . . . . . . . . . . . . . . 83

3.6 Résultats obtenus par INSERTION . . . . . . . . . . . . . . . . . . . 84

3.7 Comparaison des performances obtenues sur les trois approches . . . 84

3.8 Volumétrie des instances a et b . . . . . . . . . . . . . . . . . . . . . 85

3.9 Résultats sur le groupe d"instances a . . . . . . . . . . . . . . . . . . 86

3.10 Résultat sur le groupe d"instances b . . . . . . . . . . . . . . . . . . . 86

4.1 Exemple sur la préemption de charge : les paramètres . . . . . . . . . 93

4.2TInsertde INSERTION . . . . . . . . . . . . . . . . . . . . . . . . . . 102

4.3TInsertSLde INSERTIONDARPSL . . . . . . . . . . . . . . . . . . . . 102

4.4TPartde l"heuristique avec préemption de charge sur instances de [Cor-

deau and Laporte (2003)] avec multiplication du chargement de 1 à

7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4.5 Résultats Série 2 - Résolution du DARP . . . . . . . . . . . . . . . . 105

4.6 Résultats Série 2 - Résolution du DARPSL . . . . . . . . . . . . . . . 105

4.7 Résultats Série 2 - Comparaison DARP / DARPSL . . . . . . . . . . 105

5.1 Taux d"insertions sur 18 groupes d"instances . . . . . . . . . . . . . . 128

6.1 Taux de succès INSERTION / INSERTION avecInsérabilité. . . . . 143

6.2 Paramètres du processus de génération d"instances . . . . . . . . . . . 144

6.3 Gap entre les tauxINSER. . . . . . . . . . . . . . . . . . . . . . . . 145

6.4 Performances des tournées pour le DARP dynamique - 100 demandes

et 4 véhicules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

6.5 Performances des tournées pour le DARP dynamique - 200 demandes

et 5 véhicules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

12 LISTE DES TABLEAUX

6.6 Performances des tournées pour le DARP dynamique - 300 demandes

et 5 véhicules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

6.7TInsertselon les résolutions intégrant (I) ou pas (B) les procédés liés

à l"

Insérabilité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

7.1 Exemple : fenêtres de temps à amplitude constante . . . . . . . . . . 188

7.2 Paramètres des instances . . . . . . . . . . . . . . . . . . . . . . . . . 190

7.3 Paramètres des instances . . . . . . . . . . . . . . . . . . . . . . . . . 192

7.4 Résolution exacte du problème (Branch and Bound+ génération de

colonnes) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

7.5 Résolution approchée du problème (Insertions successives et courbes

de Profil) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

7.6fs/f. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

7.7 Résultats heuristiques sur différentes tailles de fenêtre de temps . . . 194

7.8 Résultats du DARPRel avec fenêtres de temps, temps de service et1195

7.9 Résultats du DARPRel avec fenêtres de temps, temps de service et2196

8.1 Analyse des gaps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210

8.2 Analyse de sensibilité : heuristique / méthode exacte pour FACLOC. 211

8.3 Analyse des gaps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

13

Liste des algorithmes

1 Glouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2 Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3 Transformation Locale . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4 Schéma de Transformation Locale :Descente. . . . . . . . . . . . . . 27

5 Propagation de contraintes . . . . . . . . . . . . . . . . . . . . . . . . 30

6 PropagerFenetreTemps . . . . . . . . . . . . . . . . . . . . . . . . . . 67

7 EvalTour1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

8 EvalTour2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

9 TestUnNoeud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

10 TestDeuxNoeuds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

11 TestInsertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

12 INSERTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

13 INSERTIONAleatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

14 Coloration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

15 Principe des insertions partielles indépendantes . . . . . . . . . . . . 95

16 Principe de INSERTIONDARPSL . . . . . . . . . . . . . . . . . . . . 96

17 INSERTIONDARPSL . . . . . . . . . . . . . . . . . . . . . . . . . . 99

18 Echange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

19 PropageT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

20 EvalTourT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

21 INSERTIONDARPT . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

22 Mise à jour dei. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

23 DARPetDARPT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

24 Sélection des paramètres d"insertion par la mesure de l"

Insérabilité. . 137

25 Bi-Fenêtre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

26 Rendez-Vous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

27 MAIN-ROUTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

28 Schéma d"insertion gloutonne pour le couplage avec arrêts . . . . . . 187

29 TestInsertLoop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

30 LAG-LOT-SIZING . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

31 MLS-STPC-ALG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

15

Introduction Générale

Bien des personnes associent le mot transport à l"utilisation d"une voiture indivi- duelle. C"est le cas, d"ailleurs, dans 90% des déplacements, avec la plupart du temps une seule personne à bord. Aux problèmes de circulation que l"on imagine (ou plu- tôt que l"on vit au quotidien) s"ajoutent ceux des accidents - le risque s"accroît avec le nombre de véhicules -, de la pollution, bien sûr, de la prolifération des parkings (jamais en nombre suffisant pourtant) et de bien d"autres nuisances. De façon générale la gestion des flux dans les grandes villes est devenue très difficile. La situation déjà grave que nous connaissons devient critique, pour ne pas dire apocalyptique, dans certaines métropoles d"Asie par exemple, ou en cas d"événement exceptionnel. Aujourd"hui, de nouvelles organisations et mutualisations de véhicules sont nécessaires. Ces besoins apparaissent à la fois en zones rurales et urbaines, pour de multiples raisons : le vieillissement de la population entraînant des problèmes de dépendance, la désertification des campagnes et la diminution des

services assurés autrefois, l"augmentation des coûts énergétiques, les difficultés de la

circulation, etc... Le problème, on le voit, est important et délicat : il ne fera que s"intensifier. L"accroissement de la population urbaine et péri-urbaine et la mobilité de plus en plus grande des personnes, due au contexte technique, économique et social, ont rendu obligatoire, dans le cadre de différentes politiques d"aménagement du terri- toire, la remise en cause de la prééminence des transports individuels au profit de ceux qui mutualisent l"utilisation des véhicules. Ceci étant, la plupart des transports publics proposés aujourd"hui obéissent à des règles manquant de souplesse et n"in- cluent que rarement le caractère dynamique, en temps et en espace, de la demande, réduisant ainsi l"attractivité de ces services et les rendant même parfois difficile- ment supportables. De ce fait, la majorité des usagers utilisent encore leur propre véhicule. La littérature dans le domaine de l"urbanisation et de la géomatique nous indique que des transports à la demande performants remplaçant pour une grande part les véhicules privés pourraient être la clé d"une circulation urbaine harmonieuse et agréable. L"avancée technologique des véhicules sans conducteur et des moyens de communication devrait être un tremplin pour ces transports dynamiques. Le management de ces nouveaux flux tend à se faire à l"aide des TIC (géolocali- sation, communications mobiles, web services). Aussi, les modèles de la Recherche Opérationnelle (RO) peut contribuer à optimiser le rapport coût/qualité de ser- vice (QoS). Cette notion de compromis est essentielle dans la gestion des systèmes

16 Introduction Générale

émergents. Alors qu"auparavant seuls les coûts étaient pris en compte (coûts de pro- duction, coûts de fonctionnement d"une flotte de véhicules), la performance d"une solution à un tel problème se mesure aujourd"hui également à la qualité du ser- vice rendu (temps d"acheminement des usagers d"un service de transport), à son empreinte écologique, etc... Le principal objet de cet thèse réside dans la modélisation et l"optimisation de services de transport à la demande aussi différents soient-ils (ou seront-ils). Les techniques de supervision doivent alors pouvoir supporter différents objectifs et dif- férentes contraintes pour s"adapter aux services actuels et futurs. Ainsi, ce rapport de thèse développe différentes variantes du DARP - ang.Dial-a-Ride Problem-, le problème de RO modélisant et optimisant un service classique de transport à la demande. Le DARP standard a été étendu de façon à prendre en compte des hy- pothèses de fonctionnement prometteuses, comme le fait de séparer les composants d"une même requête pour les dispatcher sur des véhicules différents ou encore la

présence de mécanismes d"intermodalité (cf. figure 1).Figure1 - Intégration du VIPA dans le transport intermodal

Le passage d"un service à l"autre se fait par un transfert (transbordement). Les contextes statiques (toutes requêtes connues en amont de la résolution) et dyna- miques (les demandes sont intégrées en cours de tournée) doivent également être examinés. De ce fait, nous adoptons ici le point de vue dominant des algorithmes dits d"insertion, permettant d"articuler statique et dynamique. La littérature scien- tifique sur le DARP dynamique souffre d"une réelle lacune dès lors que l"on étudie un contexte qui peut-être qualifié dedynamique pureoù les tournées courantes de- viennent de moins en moins flexibles au fil du temps. Aussi, cette thèse permet-elle d"inscrire les véhicules autonomes tels que les VIPA dans de nouvelles problématiques de la Recherche Opérationnelle tout en restant dans le domaine du transport à la demande. La modélisation puis l"optimisation de ces systèmes permet de créer les plannings de ces nouveaux véhicules. A long terme, l"évolution technologique devrait permettre de ne plus se soucier du fait qu"ils sont automatiques. Ces travaux tentent de fournir un cadre suffisamment générique permettant à la fois de fournir une solution exploitable aujourd"hui et qui soit adaptable demain. Les travaux présentés dans ce mémoire se classent en trois catégories. La pre- mière, recouvrant 2 chapitres, étudie les problèmes de transport à la demande selon deux modes de fonctionnement bien spécifiques : les transferts et la division du char- gement. La seconde, sur 3 chapitres, concerne les différents critères de qualité recher-

Introduction Générale 17

chés : rapport Coût/QoS, Fiabilité (véhicules sans conducteur) et enfin Robustesse (DARP dynamique). La thèse se conclut sur une question de production incluant un problème de transport, plus précisément un cas particulier du problème deLot-

Sizing

. Ce problème est multi-produits, multi-sites, multi-périodes, multi-capacités, et intègre des coûts fixes de production. Avant ces 5 chapitres sont présentés le contexte général dans lequel ces travaux de recherche interviennent, puis l"état de l"art sur la modélisation et l"optimisation des différents problèmes de transports

étudiés dans ce mémoire.

La première étude sur les transports à la demande débute donc au chapitre 3, elle met au point une résolution heuristique par insertions particulièrement rapide du problème deDial-a-Ride(DARP) qui pourra être aisément déployé sur un système multi-processeurs et adapté à une exploitation concrète dynamique. Elle se concentre sur les contraintes temporelles en réduisant l"espace solution par la contraction des fenêtres de temps selon l"enchaînement des noeuds de chaque tournée. De nombreusesquotesdbs_dbs35.pdfusesText_40

[PDF] probleme de transport optimisation

[PDF] probleme de transport exercices corrigés pdf

[PDF] problème de transport stepping stone

[PDF] exercice corrige résolution du problème de transport en recherche opérationnelle

[PDF] transport et probléme d affectations

[PDF] exos corrigés problème d'affectation recherche opérationnelle

[PDF] développement limité fonction plusieurs variables

[PDF] recherche opérationnelle exercices corrigés gratuit

[PDF] programmation linéaire exercices corrigés simplex

[PDF] examen recherche opérationnelle corrigé

[PDF] exercice corrigé methode simplexe pdf

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice