La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Sujets
Informations
Publié par | profil-zyak-2012 |
Publié le | 01 décembre 2007 |
Nombre de lectures | 31 |
Langue | Français |
Poids de l'ouvrage | 2 Mo |
Extrait
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 .