Plus rapide chemin bicritère : un problème daménagement du territoire Y. Botquélen, P. Martineau, J-C. Billaut et H. Baptiste Laboratoire dInformatique

Plus rapide chemin bicritère : un problème

d’aménagement du territoire

Y. Botquélen, P. Martineau, J-C. Billaut et H. Baptiste

Laboratoire d’Informatique (EA 2101)Département Informatique - Polytech’Tours

Université de Tours - France

Plus rapide chemin bicritère

1/09/2004 MOSIM’04 2

Plan

1. Problématique2. Modélisation3. Algorithmes préliminaires4. Algorithme pour le graphe bicritère

temporisé5. Evaluations6. Conclusion


1/09/2004 MOSIM’04 3

Problématique

• Aider les conseils Régionaux à fixer les horaires des transports en commun pour :– Améliorer les déplacements des usagers au niveau

des régions– Développer les moyens de déplacement collectifs

(moins polluants, multimodales, …)– Offrir plusieurs possibilités d’aller/retour par jour

• Objectifs : temps de trajet, qualité de service (confort, nombre de changements), coût, sécurité


1/09/2004 MOSIM’04 4

Problématique

• Organisation des transports publics• Données:

– Réseau de transport– Grille horaire à respecter

• Objectifs:– Minimiser temps de trajet– Minimiser nombre de transbordements


1/09/2004 MOSIM’04 5

Problématique

• Certains modes sont à départ planifié d’autres à départ permanent

• Le réseau est non FIFO (un train peut en doubler un autre)

Toutes les solutions non dominées peuvent intéresser l’utilisateur


1/09/2004 MOSIM’04 6

Modélisation du problème

• Caractéristiques du problème de plus court chemin:– Problème all-to-all, pour toute date de départ– Contraintes horaires– Graphe non-FIFO

• Notations:– G(X,U), graphe orienté +(i), ensemble des successeurs du sommet i X– T, grille horaire des dates de départ disponibles

– c1u(t), c2u(t), longueurs associées à l’arc u, tT

– C, liste de candidats-solutions i,k(j), solution au sommet j pour un départ de i à à la date k


1/09/2004 MOSIM’04 7

Exemple


1/09/2004 MOSIM’04 8

Modélisation

• Modélisation par un graphe espace-temps = explosion du nombre des sommets et du nombre d’arcs

1. Recherche du plus court chemin dans un graphe temporisé

2. Recherche de solutions non dominées dans un graphe


1/09/2004 MOSIM’04 9

Algorithme Préliminaire

1. Plus rapide chemin dans un graphe temporisé• 1 seul coût sur un arc u : c1u(t)• Basé sur l’algorithme de Dijkstra

• A partir d’une ville, on constitue une liste ordonnée de chemins partiels

• Pour le premier chemin, on génère les successeurs donnant les plus petites dates d’arrivée

• Evolution• On constitue une liste de chemins en s’appuyant sur les

plus petites dates d’arrivée en chaque ville mais celles-ci doivent être recherchées

• On retire toujours le candidat de plus petite date d’arrivée pour constituer ses successeurs


1/09/2004 MOSIM’04 10

Principe de l’algorithme

• Initialisation des sommets à des valeurs infinies

• Création du 1er candidat• Tant qu’il existe un candidat non étudié et un

sommet non atteint:– Mise à jour du sommet atteint– Recherche des horaires arrivant le plus tôt– Création de nouveaux candidats à partir de celui

étudié et de la grille horaire


1/09/2004 MOSIM’04 11

Algorithmes de résolutions

• Problème monocritère– Étude du seul critère temps

• Problème multicritère– Nombre de transbordement– Coût de revient pour l’usager/ transporteur– Facteurs de congestion


1/09/2004 MOSIM’04 12

Algorithme monocritère

• Algorithme basé sur Dijkstra– Inspiré de l’algorithme de Chabini & al:

«Reoptmization algorithms for minimum time path problems in dynamic networks»

• Avantages– Résultats exacts– Complexité en O(n²)


1/09/2004 MOSIM’04 13


• Initialisation des sommets à des valeurs infinies

• Création du 1er candidat• Tant qu’il existe un candidat non étudié et un

sommet non atteint:– Mise à jour du sommet atteint– Recherche des horaires arrivant le plus tôt– Création de nouveaux candidats à partir de celui

étudié et de la grille horaire


1/09/2004 MOSIM’04 14

Exemple d’utilisation

01,0(j)

4321j

C = {(1,0)}C = {(2,2),(3,4)}C = {(3,3),(4,5)}

Candidat étudié: (1,0)Candidat étudié: (2,2)Candidat étudié: (3,3)

4

Candidat étudié: (4,4)


2 3

C = {(4,5)}C = {(4,4)}C = { }


1/09/2004 MOSIM’04 15

Algorithme multicritère

• Algorithme basé sur l’algorithme monocritère• Gestion du multicritère inspirée d’un

algorithme bicritère sur des graphes statiques

• Recherche des solutions non dominées• Complexité exponentielle en O(2n)• Temps de calcul raisonnables en pratique

pour 2 critères


1/09/2004 MOSIM’04 16


• Initialisation des sommets à des ensembles vides

• Création du 1er candidat• Tant qu’il existe un candidat non étudié:

– Mise à jour des solutions non dominées du sommet

– Étude de tous les horaires disponibles– Conservation des candidats non dominés


1/09/2004 MOSIM’04 17


C = {(1,0,0)}

j 1 2 3 4

1,0(j) {(0,0)}

Candidat étudié: (1,0,0)

C = { }C = {(2,2,2),(2,4,1)}C = {(2,2,2),(2,4,1),(3,4,1)}


C = {(2,4,1),(3,4,1)}

{(2,2)}

C = {(2,4,1),(3,4,1),(3,3,10),(4,5,3)}


C = {(2,4,1),(3,4,1),(4,5,3)}

{(2,2),(4,1)}


C = {(2,4,1),(3,4,1),(4,5,3),(4,4,16)}

{(3,10)}


C = {(3,4,1),(4,5,3),(4,4,16)}


1/09/2004 MOSIM’04 18

Complexité exponentielle

• Exemple d’un cas critique


1/09/2004 MOSIM’04 19

Résultats (1)

• Jeux de données réels et aléatoires• Comparaison avec résultats antérieurs• Comparaison du nombre de solutions

proposées• Application à la minimisation du nombre de

transbordements sur des données réelles


1/09/2004 MOSIM’04 20

Résultats (2)

• Résultats complets sur des données réelles

critères 1 2 3

temps (s)

5 45 900


1/09/2004 MOSIM’04 21

Résultats (3)

• Résultats one-to-all à date de départ fixée sur des données aléatoires pour deux critères

temps (s) nb solutions temps (s) solutions100 0.0 0.94 0.2 6.93200 0.0 0.94 0.5 6.70300 0.0 0.93 0.9 6.89400 0.0 0.94 1.5 6.90500 0.0 0.94 2.1 6.691000 0.0 0.94 12.3 6.662000 0.1 0.94 90.2 6.26

Algorithme monocritère Algorithme multicritèresommets


1/09/2004 MOSIM’04 22

Interface utilisateur

• Objectifs– Outil d’aide à la décision– Critères d’extraction– Économie de calculs– Convivialité

• Base de données MySQL• Interface PHP


1/09/2004 MOSIM’04 23

Les critères d’extraction (1)

• Formulaire de choix des critères:– Villes de départ et d’arrivée– Nombre maximum de transbordements– Durée totale du trajet– Durée totale des transbordements– Durées minimales/maximales des

transbordements– Heures de départ/d’arrivée au plus tôt/tard


1/09/2004 MOSIM’04 24

Extensions possibles

• Améliorer algorithme multicritère• Évaluation des critères supplémentaires• Développement d’outils d’aide à la décision

Documents

Plus rapide chemin bicritère : un problème daménagement du territoire Y. Botquélen, P. Martineau, J-C. Billaut et H. Baptiste Laboratoire dInformatique