ACADÉMIE D'AIX MARSEILLE UNIVERSITÉ D'AVIGNON ET DES PAYS DE VAUCLUSE

De
Publié par

Niveau: Supérieur, Doctorat, Bac+8
ACADÉMIE D'AIX-MARSEILLE UNIVERSITÉ D'AVIGNON ET DES PAYS DE VAUCLUSE THÈSE de DOCTORAT Présentée pour obtenir le grade de Docteur en Sciences de l'Université d'Avignon et des Pays de Vaucluse Spécialité : Informatique, recherche opérationnelle et géomatique Étude et résolution exacte de problèmes de transport à la demande avec qualité de service par Garaix Thierry Soutenue publiquement le 13 décembre 2007 devant un jury composé de : M. Claramunt Christophe Professeur, IRENav, Brest Rapporteur M. Cordeau Jean-François Professeur, HEC Montréal Rapporteur M. Prins Christian Professeur, Univ. Technologies Troyes Rapporteur M. Artigues Christian Chargé de recherches (HDR), LAAS-CNRS, Univ. Toulouse Co-directeur M. Charre Joël Professeur, UMR ESPACE-CNRS 6012, UAPV Co-directeur M. Feillet Dominique Maître de conférences (HDR), LIA, UAPV Examinateur M. Josselin Didier Chargé de recherches, UMR ESPACE-CNRS 6012, UAPV Examinateur Laboratoire d'Informatique Université d'Avignon École Doctorale 379 Temps, Espacce , Pouvoir et Culture UMR ESPACE-CNRS 6012, LIA te l-0 05 34 89 4, v er sio n 1 - 1 0 No v 20 10

  • critères de qualité de service

  • bref aperçu des besoins et de la solution

  • chargé de recherche

  • tournée

  • noyau de calcul des tournées

  • manipulation des tournées de véhicules

  • méthode de génération de colonnes

  • résolution par programmation dynamique


Publié le : samedi 1 décembre 2007
Lecture(s) : 43
Source : univ-avignon.fr
Nombre de pages : 180
Voir plus Voir moins

ACADÉMIED’AIX MARSEILLE
UNIVERSITÉD’AVIGNONETDESPAYSDEVAUCLUSE
THÈSEdeDOCTORAT
PrésentéepourobtenirlegradedeDocteurenSciences
del’Universitéd’AvignonetdesPaysdeVaucluse
Spécialité: Informatique,rechercheopérationnelleetgéomatique
Étudeetrésolutionexactedeproblèmesdetransport
àlademandeavecqualitédeservice
par
GaraixThierry
Soutenuepubliquementle13décembre2007devantunjurycomposéde:
M. ClaramuntChristophe Professeur,IRENav,Brest Rapporteur
M. CordeauJean François Pr,HECMontréal
M. PrinsChristian Professeur,Univ.TechnologiesTroyes
M. ArtiguesChristian Chargéderecherches(HDR),LAAS CNRS,Univ.Toulouse Co directeur
M. CharreJoël Professeur,UMRESPACE CNRS6012,UAPV
M. FeilletDominique Maîtredeconférences(HDR),LIA,UAPV Examinateur
M. JosselinDidier Chargéderecherches,UMRESPACE CNRS6012,UAPV
Laboratoire d'Informatique
Université d'Avignon ÉcoleDoctorale379Temps,Espacce,PouvoiretCulture
UMRESPACE CNRS6012,LIA
tel-00534894, version 1 - 10 Nov 20102
tel-00534894, version 1 - 10 Nov 2010Résumésdeschapitresdelathèse
1. Dans ce chapitre introductif, nous présentons les systèmes de transport à la de
mande(TAD)dansleurfonctionnementainsiquelaplacequ’ilsoccupentdansle
mondedutransportdepersonnes.LesTADsontabordésavecunevisionélargie,
en insistant sur les enjeux sociaux liés à l’évolution de la mobilité et les enjeux
technologiques ou pratiques liés à la mise en place et la pérennisation de tels
système. Nous évoquons également les thèmes de recherche liés aux TAD qui
peuvent susciter l’intérêt des communautés de la géographie et de la recherche
opérationnelle.
2. Nous présentons un état de l’art sur les problèmes de calcul de tournées de vé
hicules principalement axé sur les problèmes de type ramassages et livraisons,
et plus particulièrement liés au transport de personnes. Un intérêt particulier est
porté aux méthodes de résolution exactes. Une introduction à une de ces mé
thodes est l’objet des sections 2.2 et 2.3. Il s’agit de fournir les bases pour appré
hender la méthode de génération de colonnes qui décompose le problème en un
problème maître, un programme linéaire généralement résolu à l’aide d’un sol
veur, et un problème esclave qui dans notre cas particulier prend la forme d’un
Problème de Plus Court Chemin avec Contraintes de Ressources. Un algorithme
de programmation dynamique générique résolvant le problème esclave est pré
senté.Ilestutilisé,différemmentadapté,toutaulongdelathèse.
3. Aprèsavoirdéfiniformellementleproblèmeétudiédanslasection3.1,nouspro
posons dans la section 3.2 une liste de critères de qualité de service, organisée
suivant le niveau à partir duquel ils sont mesurables : à partir d’une longue pé
riode de fonctionnement, d’une solution complète, d’une tournée, de la course
d’unpassageroud’unsimpletronçonderoute.Nousdonnonsunemodélisation
formelledecescritèreslorsquecelanoussemblepouvoirrentrerdanslecadrede
notreétudeplusconcentréesurlescritèresmesurablesàunepetiteéchelle.
Nous considérons dans la section 3.3 l’optimisation des critères mesurables au
moins sur une tournée, dans le cas où un véhicule connaît exactement les lieux
qu’ildoitvisiterainsiquel’ordredanslequelilsdoiventêtrevisités.Leproblème
se restreint alors à un problème d’horodatage de la tournée, et/ou de choix des
itinérairesàemprunterentrechaqueslieuxconsécutifs.
4. Danslasection4.1,nousproposonsuneméthodedegénérationdecolonnespour
le problème de maximisation de la qualité de service présenté dans la section
3.1.Nousprésentonslesdétailsd’implémentationdelarésolutiondesproblèmes
3
tel-00534894, version 1 - 10 Nov 2010maîtreetesclave,ainsiquelesrésultatsobtenussurdesinstancesdePDPTWdela
littérature.Danslasection4.2,nousintégronsàceschématroiscritèresdequalité
deservicesélectionnéspourleurintérêtapplicatifetdiscutonsdesmodificationsà
apporteràlaméthodegénéralepourlesprendreencompte.Cestroiscritèressont
ladistancetotaleparcourue,letempsperduentransportetletauxderemplissage
desvéhicules.L’optimisationsuivantcestroiscritèreestévaluéesurdesinstances
dérivéesdecelledePDPTWdelalittérature.Hormisl’intégrationdescritèresde
qualitédeservice,undesobjectifsdecechapitreestdecalculeretdecomparerles
solutionsobtenuesenoptimisantsuivantdifférentscritères.Afinquelesrésultats
obtenus, en terme de qualité des tournées soient comparables et ne soient pas
imputablesàlaméthodederésolution,unerésolutionexactes’impose.
5. L’application produite pour le TAD du Doubs Central est le sujet de ce chapite.
Après un bref aperçu des besoins et de la solution proposée (section 5.1), nous
présentons la partie d’optimisation interne à l’application, dans la section 5.2. Le
noyaudecalculdestournéesestuneheuristiqued’insertion.Nouscomparonsses
performances avec une adaptation de la méthode de génération de colonnes du
chapitre4.
6. Aprèsavoirmisenplacedesoutilspermettantlavisualisationetlamanipulation
destournéesdevéhiculesdansleurenvironnementgéographique,nousgénérons
desinstancesréalistescorrespondantàdifférentsscénariosdedemandesdetrans
port.Nouscomparonsensuitelessolutionsobtenuesàpartirdestroiscritèresde
qualitédeservicequesontladistancetotaleparcourue,letempsperduetletaux
de remplissage. Pour finir dans la section 6.2, nous étudions comment évaluer la
sinuosité des tournées, vue comme un critère de qualité de service lié à la forme
destournées.
4
tel-00534894, version 1 - 10 Nov 2010Tabledesmatières
I Transportàlademande 7
1 Enjeux,problématiques,méthodes 9
1.1 ÉvolutiondesbesoinsdemobilitéetTAD . . . . . . . . . . . . . . . . . . 9
1.2 Miseenplaced’unTADetliensaveclaRechercheOpérationnelle . . . . 16
2 Optimisationducalculdestournéesdevéhicules:«Dial A RideProblem» 21
2.1 Étatdel’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1 Problèmesdecalculdetournéesdevéhicules . . . . . . . . . . . . 21
2.1.2 DARP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 Méthodedegénérationdecolonnes . . . . . . . . . . . . . . . . . . . . . 31
2.2.1 Principesdelaméthode . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2.2 Contexted’utilisation–Calculdebornesinférieurespourdespro
grammeslinéairesennombresentiers . . . . . . . . . . . . . . . . 34
2.2.3 Paramétrages–Efficacité . . . . . . . . . . . . . . . . . . . . . . . 35
2.3 Pluscourtcheminaveccontraintesderessources(SPPRC) . . . . . . . . 36
2.3.1 Modélisationd’unESPPRC . . . . . . . . . . . . . . . . . . . . . . 38
2.3.2 Résolutionparprogrammationdynamique . . . . . . . . . . . . . 39
II Qualitédeservicepourletransportàlademande 43
3 Critèresdequalitédeservice 45
3.1 Définitionduproblèmeétudié. . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Critèresdequalitédeservice . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2.1 Évaluationsuruntronçonouunarrêt . . . . . . . . . . . . . . . . 49
3.2.2surunecourse . . . . . . . . . . . . . . . . . . . . . . . 52
3.2.3 Évaluationsurunetournée . . . . . . . . . . . . . . . . . . . . . . 54
3.2.4surunesolution . . . . . . . . . . . . . . . . . . . . . . 55
3.2.5 Évaluationàlongterme . . . . . . . . . . . . . . . . . . . . . . . . 60
3.3 Maximisationdelaqualitédeservicepouruneséquencefixéed’arrêtsà
visiter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.3.1 Définitionetmodélisation . . . . . . . . . . . . . . . . . . . . . . . 61
3.3.2 Casdu1 graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.3.3 Casdu p graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5
tel-00534894, version 1 - 10 Nov 20104 Maximisationdelaqualitédeservice 71
4.1 Méthodederésolutionpargénérationdecolonnes . . . . . . . . . . . . . 71
4.1.1 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.1.2 Adaptationdelaméthodegénéraledegénérationdecolonnes . . 75
4.1.3delarésolutionduproblèmeesclave . . . . . . . . . 78
4.1.4 Résultatssurdesproblèmesstandarddelalittérature . . . . . . . 89
4.2 Intégrationdescritèresdequalitédeservice . . . . . . . . . . . . . . . . 99
4.2.1 Ladistancetotaleparcourue . . . . . . . . . . . . . . . . . . . . . 99
4.2.2 Letempsperdu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.2.3 Letauxderemplissage . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.2.4 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
III Étudedecas:LeTADduPaysduDoubsCentral 125
5 L’applicationdéveloppée 127
5.1 TADàmettreenplace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.1.1 DescriptiongénéraleduTADàréaliser . . . . . . . . . . . . . . . 127
5.1.2 Définitionduproblèmedecalculdetournées. . . . . . . . . . . . 129
5.1.3 L’applicationTADOU . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.2 Heuristiqued’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5.2.1 Résolutionparunalgorithmed’insertion . . . . . . . . . . . . . . 134
5.2.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6 Visualisationdestournées 143
6.1 Plate formedetravailcoupléeàunSIG . . . . . . . . . . . . . . . . . . . 143
6.1.1 StructuredelaplateformeOpensource . . . . . . . . . . . . . . . 144
6.1.2 Constructiond’instancestypées . . . . . . . . . . . . . . . . . . . 144
6.1.3 Critèresdequalitédeserviceetmodèlesdeflux . . . . . . . . . . 148
6.2 Étudedelasinuosité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.2.1 Définitiondequatrecritèresd’évaluation . . . . . . . . . . . . . . 151
6.2.2 Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
Conclusion 165
Listedesillustrations 165
Listedestableaux 167
Bibliographie 169
6
tel-00534894, version 1 - 10 Nov 2010Premièrepartie
Transportàlademande
7
tel-00534894, version 1 - 10 Nov 2010tel-00534894, version 1 - 10 Nov 2010Chapitre1
Enjeux,problématiques,méthodes
RÉSUMÉ :Danscechapitreintroductif,nousprésentonslessystèmesdetransportàlademande
(TAD) dans leur fonctionnement ainsi que la place qu’ils occupent dans le monde du transport
depersonnes.LesTADsontabordésavecunevisionélargie,eninsistantsurlesenjeuxsociaux
liésàl’évolutiondelamobilitéetlesenjeuxtechnologiquesoupratiquesliésàlamiseenplaceet
lapérennisationdetelssystème.NousévoquonségalementlesthèmesderechercheliésauxTAD
quipeuventsusciterl’intérêtdescommunautésdelagéographieetdelarechercheopérationnelle.
1.1 ÉvolutiondesbesoinsdemobilitéetTAD
Les transports évoluent pour permettre d’aller plus loin, plus vite à un plus grand
nombred’individus.Laquantité,ladiversitéetlalongueurdesfluxdepassagersaug
mentent.Cesdernièresdécennies,lestransportsontprisdeplusenplusdeplacedans
notrequotidien.Lebudgettempsdechaqueindividuconsacréautransport,longtemps
constantà12%,estpasséà20%(constatfaitentre1994et2000enSuisse);cequiàpre
mièrevuecontreditlaloideZahavi(ZahavietRyan,1980;ZahavietTalvitie,1980)sur
le budget temps (et argent) constant. La journée «moyenne» a subi une désynchroni
sation temporelle avec par exemple une forte atténuation des pics de trafic, due entre
autresàunesouplessedel’organisationdutempsdetravailaccrue(BaillyetHeurgon,
2001). Qu’en est il de notre mobilité? et des enjeux économiques, politiques, sociaux,
écologiquesliésàlagestiondecesflux?
Denombreusesdiscipliness’intéressentàcessujets.Unepartiedesgéographesétu
die l’interaction entre les réseaux de communication (transport ou autre) et les terri
toires, pour savoir dans quelle mesure les territoires forment les réseaux ou à quel ni
veau les réseaux (dé)structurent les territoires. Les sociologues s’interrogent sur l’im
pact d’une plus grande offre de mobilité dans notre société et sa fluidité. Est ce que
cette offre de quasi ubiquité est égalitaire et génère un gain de liberté? Ou bien, la so
ciétésevoit elleimposerdenouvellescontraintesdansunsystèmeélitisteséparantdes
9
tel-00534894, version 1 - 10 Nov 2010Chapitre1. Enjeux,problématiques,méthodes
autresceuxquiontunaccèsfacilitéàlamobilité?Ilss’interrogentaussisurlessources
d’un tel besoin de mobilité; s’il répond à un désir naturel de mouvement ou à des
contraintessociétales,commeparl’exemplelaprésencedeshabitatslesmoinsonéreux
loindescentresd’activités.Lesindustrielscherchentàproposerdesproduitsbaséssur
de nouvelles technologies (GPS, Bluetooth, WI FI...) satisfaisant ou anticipant les be
soinsenmobilité.Lestransporteursrationalisentleuroffredetransportetleurgestion
des flux via des outils d’optimisation et d’aide à la décision généralement basés sur
des développements informatiques. En effet, lorsqu’un système de transport ne peut
plusêtregérémanuellement,notammentlorsquelaquantitédedemandesdemobilité
autorise potentiellement le regroupement des passagers dans les véhicules, l’utilisa
tion de systèmes automatisés pour la recherche de solutions optimisées s’impose. Ces
systèmes permettent de gérer des services au fonctionnement complexe soumis à de
nombreuses contraintes. La recherche opérationnelle apporte ainsi une vision complé
mentaireàcelledel’expertdeterrain,grâceàl’introductiondethéoriesetdeconcepts
éprouvés tels que la recherche du plus court chemin basée sur la théorie des graphes,
les méthodes d’ordonnancement ou de programmation linéaire sous contraintes. Ces
approchespeuventintervenirpouraiderauchoixdesservices(simulationpréalablede
fonctionnement du système), pour gérer le TAD (optimisation des tournées effectives)
ou pour suivre son fonctionnement (audit et retour sur expérience). Le traité IGAT ré
digé sous de la direction de G. Finke (Finke, 2002) fournit un aperçu de ces différents
aspects.
Dans cette thèse, nous nous intéressons au transport collectif individualisé corres
pondantaux exigences modernes et plus particulièrementaucalcul età l’optimisation
desitinérairesviadifférentscritèresdequalitédeservice,àl’aidedeméthodesadaptées
provenantdelarechercheopérationnelle.
Lesindividusrecherchentdesservicesdetransporttoujoursplussouples,pluspro
ches de leurs besoins. Malgré de récents efforts, les transports publics ne répondent
quepartiellementàcesattentes.Siceux cirestentcompétitifssurcertainssegments(en
milieu urbain dense sur sites propres), dans la majorité des cas la voiture personnelle
restelaplusàmêmederépondreauxbesoinsdedéplacementsindividuels(Wiel,2002;
Dupuy, 1999). Toutefois, sur ces segments où les véhicules privés sont les plus com
pétitifs (zones péri urbaines, rurales...), de par leur disponibilité et leur efficacité, des
solutionsalternativesexistent(CastexetJosselin,2007).
Relativement mal connus du grand public et plutôt négligés par les transporteurs,
les transports à la demande (TAD), datant des années 1970, font leur réapparition de
puislafindesannées1990,àlafaveurdel’avènementdestechnologiesdel’information
etdelacommunication(AmbrosinoetNelson,2004)etdevolontéspolitiques.LesTAD
peuvent se définir comme : des «transports terrestres collectifs individualisés de per-
sonnes, activés seulement à la demande». On les trouve actuellement essentiellement
danslespaysriches(États Unis,Europe,Japon).Lesfigures 1.1et1.2illustrentleprin
cipedefonctionnementd’unTAD.
La figure 1.1 représente les requêtes (flèches), les temps de trajet (pondération des
flèches)estimésdel’origine(cerclesurmontédepersonnages)versladestination.L’heure
10
tel-00534894, version 1 - 10 Nov 2010

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.