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

Christophe Claramunt

Description

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

Sujets

• Artigues
• Claramunt
• Didier
• Académie d'Aix-Marseille
• Charre

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 décembre 2007
• Nombre de lectures: 45
• 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 .