[PDF] [PDF] Calcul ditinéraire multicritère en transport multimodal - Thesesfr

View - Download [PDF] Calcul ditinéraire multicritère en transport multimodal - Thesesfr

Previous PDF

Next PDF

opérée au sein de

Ecole Doctorale N° 488

Sciences, Ingénierie, Santé

Spécialité de doctorat :

Discipline : Informatique

Soutenue publiquement le 12/10/2017, par :

Alexandre Stéphane Gonzalo IGLESIAS

transport multimodal

Devant le jury composé de :

Artigues, Christian - Directeur de Recherches - LAAS-CNRS Président Huguet, Marie-José - Professeur INSA-Toulouse - LAAS-CNRS Rapporteur Neron, Emmanuel - Professeur - École Polytechnique Université de Tours Rapporteur Wolfler Calvo, Roberto - Professeur - Université de Paris Nord Examinateur Feillet, Dominique - Professeur - Mines Saint-Etienne Directeur Quadri, Dominique - Maître de conférences HDR - Université Paris Sud Co-directrice Lesens, Franck- Directeur Technique - Cityway Invité industriel

ABSINabilCRGénie industrielCMP

AUGUSTOVincentCRImage, Vision, SignalCIS

AVRILStéphanePR2Mécanique et ingénierieCIS BADELPierreMA(MDC)Mécanique et ingénierieCIS

BALBOFlavienPR2InformatiqueFAYOL

BASSEREAUJean-FrançoisPRSciences et génie des matériauxSMS BATTON-HUBERTMireillePR2Sciences et génie de l'environnementFAYOL

BEIGBEDERMichelMA(MDC)InformatiqueFAYOL

BOISSIEROlivierPR1InformatiqueFAYOL

BONNEFOYOlivierMA(MDC)Génie des ProcédésSPIN BORBELYAndrasMR(DR2)Sciences et génie des matériauxSMS

BOUCHERXavierPR2Génie IndustrielFAYOL

BRODHAGChristianDRSciences et génie de l'environnementFAYOL BRUCHONJulienMA(MDC)Mécanique et ingénierieSMS

CAMEIRAOAnaMA(MDC)Génie des ProcédésSPIN

CHRISTIENFrédéricPRScience et génie des matériauxSMS

DAUZERE-PERESStéphanePR1Génie IndustrielCMP

DEBAYLEJohanCRSciences des Images et des FormesSPIN DEGEORGEJean-MichelMA(MDC)Génie industrielFayol DELAFOSSEDavidPR0Sciences et génie des matériauxSMS

DELORMEXavierMA(MDC)Génie industrielFAYOL

DESRAYAUDChristophePR1Mécanique et ingénierieSMS DJENIZIANThierryPRScience et génie des matériauxCMP

DOUCESandrinePR2Sciences de gestionFAYOL

DRAPIERSylvainPR1Mécanique et ingénierieSMS

FAUCHEUJennyMA(MDC)Sciences et génie des matériauxSMS

FAVERGEONLoïcCRGénie des ProcédésSPIN

FEILLETDominiquePR1Génie IndustrielCMP

FORESTValérieMA(MDC)Génie des ProcédésCIS FRACZKIEWICZAnnaDRSciences et génie des matériauxSMS

GARCIADanielMR(DR2)Sciences de la TerreSPIN

GAVETYannMA(MDC)Sciences des Images et des FormesSPIN GERINGERJeanMA(MDC)Sciences et génie des matériauxCIS GOEURIOTDominiqueDRSciences et génie des matériauxSMS GONDRANNatachaMA(MDC)Sciences et génie de l'environnementFAYOL GONZALEZ FELIUJesusMA(MDC)Sciences économiquesFAYOL GRAILLOTDidierDRSciences et génie de l'environnementSPIN

GROSSEAUPhilippeDRGénie des ProcédésSPIN

GRUYFrédéricPR1Génie des ProcédésSPIN

GUYBernardDRSciences de la TerreSPIN

HANWoo-SuckMRMécanique et ingénierieSMS

HERRIJean MichelPR1Génie des ProcédésSPIN KERMOUCHEGuillaumePR2Mécanique et IngénierieSMS KLOCKERHelmutDRSciences et génie des matériauxSMS LAFORESTValérieMR(DR2)Sciences et génie de l'environnementFAYOL LERICHERodolpheCRMécanique et ingénierieFAYOL MOLIMARDJérômePR2Mécanique et ingénierieCIS

MOUTTEJacquesCRGénie des ProcédésSPIN

NEUBERTGillesFAYOL

NIKOLOVSKIJean-PierreIngénieur de rechercheMécanique et ingénierieCMP

NORTIERPatricePR1Génie des ProcédésSPIN

O CONNORRodney PhilipMA(MDC)MicroélectroniqueCMP

OWENSRosin MA(MDC)MicroélectroniqueCMP

PERESVéroniqueMRGénie des ProcédésSPIN

PICARDGauthierMA(MDC)InformatiqueFAYOL

PIJOLATChristophePR0Génie des ProcédésSPIN PINOLIJean CharlesPR0Sciences des Images et des FormesSPIN POURCHEZJérémyMRGénie des ProcédésCIS ROUSTANTOlivierMA(MDC)Mathématiques appliquéesFAYOL STOLARZJacquesCRSciences et génie des matériauxSMS TRIAAssiaIngénieur de rechercheMicroélectroniqueCMP VALDIVIESOFrançoisPR2Sciences et génie des matériauxSMS VIRICELLEJean PaulDRGénie des ProcédésSPIN WOLSKIKrzystofDRSciences et génie des matériauxSMS

XIEXiaolanPR1Génie industrielCIS

YUGMAGallianCRGénie industrielCMP

Spécialités doctoralesResponsables:

SCIENCES ET GENIE DES MATERIAUX K. Wolski Directeur de recherche

MECANIQUE ET INGENIERIE S. Drapier, professeur

GENIE DES PROCEDES F. Gruy, Maître de recherche SCIENCES DE LA TERRE B. Guy, Directeur de recherche

D. Graillot, Directeur de recherche

Spécialités doctoralesResponsables

MATHEMATIQUES APPLIQUEESO. Roustant, Maître-assistant

INFORMATIQUE O. Boissier, Professeur

SCIENCES DES IMAGES ET DES FORMES JC. Pinoli, Professeur

GENIE INDUSTRIEL X. Delorme, Maître assistant

MICROELECTRONIQUE Ph. Lalevée, Professeur

Mise à jour : 03/02/2017

A Capucine.

Remerciements

Cette these a ete realisee dans le cadre d'une convention industrielle entre Cityway et l'Ecole Nationale des Mines de Saint-Etienne. Je remercie donc l'ensemble des personnes de ces organismes qui ont rendu possible ces travaux. Je remercie en particulier mon directeur de these Dominique Feillet, directeur du la- boratoire SFL au Centre Georges Charpak de Gardanne, qui a su se rendre disponible malgre ses responsabilites administratives. Travailler avec lui fut un veritable plaisir, et il m'a oriente avec pertinence et beaucoup de competence tout au long de mes travaux de recherche. Mes remerciements vont egalement a Dominique Quadri, ma^tre de confe- rences HDR a Universite Paris Sud, co-directrice de ma these, pour sa gentillesse et sa patience lors des reunions au laboratoire ou a distance et pour ses precieuses relectures du manuscrit. Merci aussi aux rapporteurs de these et au jury de ma soutenance, Marie- Jose Huguet, Emmanuel Neron, Christian Artigues et Roberto Wolfer Calvo pour les remarques pertinentes et les critiques positives dont ils m'ont fait l'honneur, que ce soit dans leurs rapports ecrits ou pendant la soutenance. Je remercie egalement Franck Lesens et Laurent Briant, respectivement directeur technique et directeur general de Cityway, a l'initiative de ces longs travaux de recherche, et qui les ont accompagne lors des reunions de suivi, jusqu'a la soutenance. Je remercie chaleureusement Charlie Jacquelin, developpeur Cityway sur le calculateur d'itineraire, qui a repris une grande partie de mes t^aches lorsque le temps pour terminer la these s'est fait court, et avec qui les conversations autour de ce sujet furent enrichissantes. Merci encore a Pascal Lechalier, responsable de l'equipe Data a Cityway, pour sa bonne humeur constante et son ecoute attentive des problemes que je lui ai exposes. Je remercie evidemment les permanents et doctorants du laboratoire SFL pour leur accueil chaleureux, avec une mention speciale pour les organisateurs des seminaires annuels, toujours reussis. Je remercie Aurelia Lercari, ma ancee, pour son soutien indefectible et toutes ses attentions au quotidien qui m'ont donne le courage de continuer. Pour terminer, je remercie ma famille et mes amis de m'avoir soutenu et encourage dans cette voie, en particulier mes parents, sans lesquels je ne me serais pas lance dans cette aventure, mon pere pour m'avoir aide a formaliser un certain nombre de notions, et Nicolas Wodniack pour son devouement et sa disponibilite lors de la nalisation des trois premiers chapitres. 1

Table des matieres

Introduction

6

I Probleme et modelisation

11

1 Concepts generaux

1 1

1.1 Cartographie

1 2

1.2 Transport

1 3

1.3 Trajets

1 7

1.4 Denition du probleme

1 8

2 Formalisation

18

2.1 Reseaux

1 8

2.2Etapes elementaires et trajets. . . . . . . . . . . . . . . . . . . . 2 0

2.3 Recherche d'itineraire

2 3

2.4 Variations du probleme

27

3 Modelisation des reseaux

2 8

3.1 Reseaux de transport individuel

2 8

3.2 Transport en commun

3 1

3.3 Combinaison des reseaux

38
II Etat de l'art sur les algorithmes de resolution4 2

1 Introduction

42

2 Algorithmes fondateurs

4 3

2.1 Bellman-Ford

43

2.2 Dijsktra

4 3

3 Optimisations du calcul du plus court chemin

4 5

3.1 Dijkstra bidirectionnel

45

3.2 Algorithme A*

4 6

3.3 Algorithme ALT

47

3.4Arc

ags. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 9

3.5Reachetshortcuts. . . . . . . . . . . . . . . . . . . . . . . . . .4 9

3.6Contraction Hierarchies. . . . . . . . . . . . . . . . . . . . . . .5 1

3.7Hub Labeling. . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 2

3.8Transit Node Routing. . . . . . . . . . . . . . . . . . . . . . . . .5 2

3.9 Combinaisons de methodes d'optimisation

53

4 Algorithmes de resolution TC

5 3

4.1 Dijkstra sur les modelestime-dependantettime-expanded. . . .5 3

4.2 Optimisations possibles sur les modelestime-dependantettime-

expanded. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 4

4.3 Dijkstra multilabel sur le modele par arr^et

55
2

4.4Contraction Hierarchiessur le modele par arr^et. . . . . . . . . . 5 6

4.5Transfer Pattern Routing. . . . . . . . . . . . . . . . . . . . . .5 7

4.6 RAPTOR (Round-Based Public Transit Routing). . . . . . . . . 5 8

4.7 Tri topologique etConnection Scan Algorithm. . . . . . . . . . .5 9

IIIRecherche d'itineraire chez Cityway

quotesdbs_dbs21.pdfusesText_27

[PDF] Itinéraire Itinéraire:

[PDF] Itinéraire Itinéraire: : :

[PDF] Itinéraire Keren Or 4-11 Mai 2014 - Anciens Et Réunions

[PDF] itinéraire mappy - Anciens Et Réunions

[PDF] Itinéraire Mauricie Patrimoine Religieux et incontournables 2 jours

[PDF] ITINÉRAIRE MONTAIGU – KOSZALIN (1800 km) - Anciens Et Réunions

[PDF] itinéraire motoneige GPS - Anciens Et Réunions

[PDF] Itinéraire NEW YORK

[PDF] Itinéraire New York - Blogues CSAffluents.qc.ca

[PDF] Itinéraire onctueux en pays d`Auge

[PDF] Itinéraire par excellence pour survoler les grandes villes de l`Est

[PDF] Itinéraire Passion Terre Mexique Oaxaca - 3 - Voyages Inter - Gestion De Projet

[PDF] Itinéraire PDF - France

[PDF] Itinéraire Pérou - Voyages Michel Barrette

[PDF] Itinéraire piéton depuis la Basilique de Fourvière