Recherche de chemins multiobjectifs pour la conception et la réalisation d'une centrale de mobilité destinées aux cyclistes, Multiobjective shortest paths computation for designing a bicycle route planner

Gaël Sauvanet

Description

Sous la direction de Emmanuel Neron, Hervé Baptiste
Thèse soutenue le 05 avril 2011: Tours
Les travaux présentés dans cette thèse visent à proposer des méthodes de calcul d’itinéraires adaptés aux cyclistes à l’échelle d’une agglomération. Plusieurs critères sont considérés, comme la distance, la sécurité et l’effort. La difficulté est de calculer des chemins de compromis sous une contrainte de temps de quelques secondes pour pouvoir intégrer ce calculateur à un site web. Deux approches ont été abordées pour résoudre ce problème. L’approche a posteriori dans laquelle l’ensemble des solutions de compromis est calculé et l’approche a priori dans laquelle les préférences de l’utilisateur sont prises en compte et permettent d’orienter la recherche pour privilégier les chemins les plus prometteurs. Enfin, nous proposons de modéliser le réseau routier sous la forme d’un graphe adjoint pour pouvoir prendre en compte de nouveaux critères nécessitant, par exemple, des coûts sur les enchaînements d’arcs. L’ensemble de ce travail a permis de développer le service Géovélo qui est un calculateur d’itinéraires multiobjectif adaptés au vélo. Le service est disponible sous la forme d’un site web et d’applications mobiles.
-Optimisation multiobjectif
-Problème du plus court chemin
The work presented in this thesis aims at proposing methods for computing bicycle paths across a metropolitan. Several criteria such as distance, safety and effort must be considered in the path computation. The difficulty is to compute paths under a time constraint of a few seconds, in order to integrate the computation in the respond-time of a web page.Two approaches were discussed to solve this problem. The first one is an a posteriori approach where all compromise solutions are computed and the second approach is an a priori method that takes user preferences into account to guide the search by the selection of the most promising sub-paths first. Finally, we propose to model the road network as a line graph to take into account new criteria,requiring costs on arc sequences for example. All this work was necessary to develop the service Géovélo, which is a multiobjective route planner adapted to bicycle. The service is available on a website and as mobile applications.
Source: http://www.theses.fr/2011TOUR4006/document

Sujets

• Optimisation multiobjectif

Informations

• Publié par: Thesee
• Nombre de lectures: 72
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

1
UNIVERSITÉ
FRANÇOIS RABELAIS
DE TOURS
École Doctorale SST
Laboratoire d’Informatique : EA2101
Équipe Ordonnancement et Conduite
THÈSE présentée par :
Gaël SAUVANET
soutenue le : 5 avril 2011
pour obtenir le grade de : Docteur de l’université François Rabelais - Tours
Discipline / Spécialité : Informatique
Recherche de chemins multiobjectifs pour la conception et la
réalisation d’une centrale de mobilité destinée aux cyclistes
THÈSE dirigée par :
BAPTISTE Hervé Maître de Conférences, Université François Rabelais Tours
NÉRON Emmanuel Professeur des Universités, Université François Rabelais Tours
RAPPORTEURS :
ARTIGUES Christian Chargé de recherche HDR, LAAS CNRS
WOLFLER CALVO Roberto Professeur des Universités, Université Paris 13
JURY :
ARTIGUES Christian Chargé de recherche HDR, LAAS CNRS
BAPTISTE Hervé Maître de Conférences, Université François Rabelais Tours
CARLIER Jacques ProfesseurdesUniversités,UniversitédeTechnologiedeCompiègne
GALAND Lucie Maître de Université Paris Dauphine
LIBERTI Leo Professeur des Universités, École Polytechnique
NÉRON Emmanuel des Univ Université François Rabelais Tours
WOLFLER CALVO Roberto Professeur des Universités, Université Paris 13
MEMBRE INVITÉ :
GRUNBERG Benoit Directeur, La Compagnie des Mobilités, ToursRemerciements
Le travail présenté dans cette thèse a été réalisé dans le cadre d’une convention CIFRE
au sein de l’association Autour du Train, puis de l’entreprise la Compagnie des Mobilités,
et de l’équipe Ordonnancement et Conduite du Laboratoire d’Informatique de l’Université
François Rabelais Tours situé à Polytech’Tours. Je tiens donc à remercier l’ensemble des
personnes travaillant à la Compagnie des Mobilités et à Polytech’Tours pour leur accueil
durant ces trois années de thèse.
Je tiens à remercier Benoît Grunberg qui a permis de débuter ce travail de thèse.
Pouvoir partager avec lui le développement de Géovélo et la création de la Compagnie des
Mobilités a été très enrichissant. Je le remercie également pour m’avoir fait partager sa
passion du vélo et pour m’avoir laisser suffisamment de temps pour la recherche lorsque
c’était nécessaire. Merci également à l’ensemble des personnes qui ont travaillé sur ce
projet et en particulier à Jocelyn de Sinety pour son travail de terrain sur Paris et à Jiehao
Yuan pour le développement de l’application sur téléphones mobiles. Enfin, je remercie
Emmanuel Dewaele, nouveau doctorant et employé de la Compagnie des Mobilités, pour
m’avoir permis d’aborder avec lui les problèmes de plus court chemin multimodaux.
Je remercie plus particulièrement Emmanuel Néron pour son encadrement dans la
bonne humeur durant ces trois années. Il a su se rendre disponible malgré ses lourdes
charges administratives. Merci également à Hervé Baptiste pour m’avoir fait découvrir le
domaine de l’aménagement à travers plusieurs co-encadrements de projets de fin d’études.
Je remercie aussi Jean Charles Billaut pour son accueil au sein du Laboratoire d’Informa-
tique. Enfin, je voulais remercier l’ensemble des stagiaires et étudiants qui ont été amenés
à travailler sur le projet et en particulier : Zhu Yu, Zhang Juan et Shang Ke.
Merci également à l’ensemble des membres du jury et plus particulièrement aux deux
rapporteurs Christian Artigues et Roberto Wolfler Calvo.
Merci à tous les doctorants du bureau 202 et aux autres pour la bonne humeur et les
discussions scientifiques ou non que nous avons pu partagées.
Enfin, merci à ma famille et à ma compagne qui m’ont encouragé à faire une thèse et
qui ont toujours essayé de comprendre mon travail durant ces trois années.
3REMERCIEMENTS
4Résumé
Les travaux présentés dans cette thèse visent à proposer des méthodes permettant de
calculer des itinéraires adaptés aux cyclistes à l’échelle d’une agglomération. Contraire-
ment au problème du plus court chemin classique, le contexte est ici multiobjectif puisque
plusieurs critères, comme la distance, l’insécurité et l’effort, doivent être pris en compte
dans le calcul des itinéraires. Dans un problème multiobjectif, il n’existe pas qu’une seule
solution mais un ensemble de solutions de compromis. La difficulté est alors de calculer
des chemins sous une contrainte de temps de quelques secondes pour pouvoir intégrer ce
calculateur à un site web par exemple.
Deux approches ont été abordées pour résoudre ce problème. L’approche a posteriori
consiste à calculer l’ensemble des solutions de compromis. Une méthode classique de la
littérature est présentée et améliorée en utilisant des prétraitements. Les améliorations
proposées reposent sur des recherches de plus court chemin mono-objectif qui permettent
de calculer sur chacun des nœuds du graphe, des bornes inférieures et supérieures sur les
coûts des chemins de ce nœud vers le nœud destination.
La deuxième approche a priori prend en compte les préférences de l’utilisateur pour
se concentrer sur le calcul d’une solution de meilleur compromis. La méthode utilisée per-
met d’orienter la recherche des chemins, de façon à privilégier les sous-chemins les plus
prometteurs du point de vue des préférences de l’utilisateur.
Enfin, nous proposons de modéliser le réseau routier sous la forme d’un graphe adjoint
pour pouvoir prendre en compte de nouveaux critères comme le temps de parcours ou la
linéarité de l’itinéraire et de nouvelles contraintes comme des manœuvres interdites. Ces
critères et contraintes nécessitent de pouvoir résoudre le problème du plus court chemin
multiobjectif dans lequel des coûts peuvent être associés sur les arcs mais également sur
les nœuds ou sur des enchaînements d’arcs.
L’ensembledecetravailapermisdedévelopperleserviceGéovéloquiestuncalculateur
d’itinéraires adaptés au vélo et entièrement multiobjectif. Le service est disponible sous la
forme d’un site web et d’applications mobiles.
Mots-clés : problème de plus court chemin, graphe, optimisation multiobjectif.
5RÉSUMÉ
6Abstract
Theworkpresentedinthisthesisaimsatproposingmethodsforcomputingbicyclepaths
across a metropolitan. Unlike the problem of the classical shortest path, here the context is
multiobjectivebecauseseveralcriteriasuchasdistance,safetyandeffortmustbeconsidered
in the path computation. In a multiobjective problem, there is no single solution, but a set
of compromise solutions. Then, the difficulty is to compute paths under a time constraint
of a few seconds, in order to integrate the computation in the respond-time of a web page
for example.
Two approaches were discussed to solve this problem. The first one is an a posteriori
approachwhereallcompromisesolutionsarecomputed.Aclassicalmethodoftheliterature
is presented here and improved by using preprocessing. The proposed improvements are
based on single objective shortest path searches in order to compute lower and upper
bounds on the costs of paths from all nodes to the target node.
The second approach is an a priori method that takes user preferences into account to
focus on the computation of the best compromise solution. The method allows to guide
the search by the selection of the most promising sub-paths first, according to the user
preferences.
Finally, we propose to model the road network as a line graph to take into account new
criteria such as travel time or the linearity of the path and new constraints as prohibited
turns. To take into account these new criteria and constraints, it’s necessary to define costs
on the nodes, on the arcs and on arc sequences.
All this work was necessary to develop the service Géovélo, which is a multiobjective
route planner adapted to bicycle. The service is available on a website and as mobile
applications.
Keywords : shortest path problem, graph, multiobjective optimization.
7ABSTRACT
8Table des matières
1 Introduction 19
2 L’usage du vélo et les services associés 25
2.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.1 Le vélo en France . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.2 L’association «Autour du train» . . . . . . . . . . . . . . . . . . . . 29
2.1.3 Un outil de calcul d’itinéraires adapté aux besoins des cyclistes . . . 29
2.2 Critères pour élaborer un itinéraire adapté aux cyclistes . . . . . . . . . . . 30
2.2.1 Recherche du chemin le plus direct . . . . . . . . . . . . . . . . . . . 31
2.2.2 Recherche du chemin le plus sé