Graphicage d'un réseau de bus par groupes de lignes

Valérie Guihaire, Jin-Kao Hao

► To cite this version:

Valérie Guihaire, Jin-Kao Hao. Graphicage d'un réseau de bus par groupes de lignes. 9e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, 2008, Clermont-Ferrand, France. pp.225-226. hal-03350662

HAL Id: hal-03350662

https://univ-angers.hal.science/hal-03350662

Submitted on 22 Sep 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Graphicage d'un réseau de bus par groupes de lignes *

Valérie Guihaire¹,² et Jin-Kao Hao²

¹ Perinfo SA, 41 avenue Jean Jaurès, 67100 Strasbourg, France
vguihaire@perinfo.com

² LERIA, Université d'Angers, 2 boulevard Lavoisier, 49045 Angers Cedex 01, France
jin-kao.hao@univ-angers.fr

# 1 Introduction

La planification d'un réseau de bus est un processus séquentiel, donnant aux premières étapes une influence capitale sur la qualité finale du planning. Le graphicage se situe au niveau tactique et regroupe deux étapes décisives : la conception des horaires (à vocation qualité de service) et la création des services véhicules (centrée sur l'aspect ressources).

Ces deux problèmes de forte complexité ont été largement étudiés dans la littérature [1]. Cependant peu de travaux ont été publiés sur la résolution simultanée des deux phases. Nous proposons une modélisation et une méthode de résolution heuristique qui intègrent réorganisation des horaires et affectation des véhicules en se basant sur des groupes de lignes. Nous présentons ici le cas de la réorganisation d'horaires de service existants.

# 2 Présentation du Problème

Les données de base du problème sont les itinéraires des lignes, les horaires actuels, les périodes horaires de fréquences homogènes, les temps de trajet à vide entre terminus, et l'ensemble des activités (lieux, horaires d'arrivée ou de départ) avec lesquelles on souhaite créer des correspondances intermodales. Une donnée supplémentaire spécifique à notre problème est la constitution des groupes de lignes.

Le problème consiste à planifier, pour une période et un type de jour donnés, l'ensemble des horaires de passage de toutes les lignes aux arrêts de bus d'un réseau. Il faut également déterminer, à l'intérieur de chaque groupe de lignes, le nombre de véhicules requis et les services de chacun, à savoir les successions de trajets en charge (dessertes) et de trajets à vide.

Notre problème, issu de l'industrie, présente deux caractéristiques particulières. D'une part, les lignes sont assemblées par petits groupes à l'intérieur desquels les véhicules peuvent pratiquer l'interligne (être affectés à plusieurs courses de lignes différentes). D'autre part, au moment du graphicage, les emplacements des dépôts sont encore indéterminés. Les trajets à vide de début et de fin de journée sont alors soumis à un forfait fixe.

La résolution intégrée rend le problème étudié fortement multi-objectifs.

Les critères de qualité de service que nous avons utilisés sont :

- la régularité des fréquences par période (minimisation des écarts)(1),

- les temps d'attente en correspondance pour les usagers (à rapprocher d'une valeur idéale)(2),

- le nombre de correspondances proposées (chacune générant un coût négatif)(3).

Au niveau des ressources, trois critères supplémentaires à minimiser entrent en jeu :

- le nombre de véhicules nécessaire(4),

- le kilométrage à vide(5),

- le temps de battement (attente aux terminus)(6).

# 3 Modélisation

Nous modélisons la phase graphicage comme un problème d'affectation. Les variables de décision représentent les heures de départ des dessertes de ligne et les valeurs appartiennent à une période de planification discrétisée en minutes.

<footnote>* Travail soutenu par l'ANRT au travers d'un contrat CIFRE (n°400/2005)</footnote>
Nous avons intégré les deux problèmes de la manière suivante : pour une solution donnée, les coûts liés aux critères de qualité de service sont évalués directement; pour calculer les coûts relatifs aux ressources en revanche, nous résolvons optimalement un sous-problème d'affectation linéaire des dessertes aux véhicules.

# 4 Approche de Résolution

Nous utilisons une méthode heuristique basée sur la recherche locale. Le planning des horaires de lignes actuels constitue la solution initiale.

La phase d'amélioration est basée sur un algorithme de descente simple, avec un voisinage de décalage des horaires de départs de desserte. La complexité et la particularité de notre méthode de résolution résident dans la fonction d'évaluation de chaque solution.

- Les coûts des objectifs 1 à 3 sont évalués par des fonctions non linéaires (quadratiques pour 1 et 2). De plus, à l'inverse de nombreuses études basées sur le modèle QSAP [2], nous considérons le cas plus réaliste d'usagers non-captifs en imposant un temps d'attente maximal par correspondance. Ceci rend nécessaire l'ajout de l'objectif 3 à notre modèle.

- Les deux spécificités de notre problème nous permettent d'avoir recours à une méthode exacte (un algorithme par enchères de résolution de problème d'affectation linéaire [3]) pour évaluer le coût des objectifs de ressources 4 à 6.

La fonction d'évaluation de la solution totale est la somme pondérée de chaque fonction de coût. Chacune est relativisée grâce aux coûts respectifs trouvés dans la solution initiale.

# 5 Résultats et Perspectives

Les tests effectués sur des jeux de données réels ont permis de trouver des résultats prometteurs, tant au niveau de la qualité de service que des ressources.

Nous présentons ici des résultats préliminaires obtenus sur un jeu de tests réel. Ce jeu comprend 3 lignes aller-retour (soit 6 lignes) pour un total de 46 dessertes sur un type de jour donné. 4 lignes de train sont en connexion avec le réseau.

<table><caption>TAB. 1. Résultats du graphicage</caption><thead><tr><td>Objectifs</td><td>Existant</td><td>Avec Graphicage</td></tr></thead><tbody><tr><td>Nombre de correspondances</td><td>7</td><td>25</td></tr><tr><td>Fréquences (%)</td><td>30</td><td>30</td></tr><tr><td>Nombre de véhicules</td><td>22</td><td>18</td></tr><tr><td>Kilomètres à vide (km)</td><td>402.97</td><td>556.15</td></tr><tr><td>Temps de battement (min)</td><td>8776</td><td>7337</td></tr></tbody></table>

Le tableau 1 présente les résultats obtenus par objectif sur les horaires existants et après graphicage. Les coûts liés au temps d'attente moyen en correspondance ne sont pas précisés car ils ne sont pas comparables pour des nombres de correspondances différents. Pour l'objectif(1), le taux d'intervalles de passage respectant une fréquence régulière est donné. Nous travaillons actuellement à l'amélioration des performances de l'algorithme à travers la mise en oeuvre d'un recuit simulé.

# Références

1. Desaulniers, G., Hickman, M. : Public Transit. Chapter 2 in G. Laporte and C. Barnhart (eds), Handbooks in Operations Research and Management Science : Transportation Science, North Holland, 69–127 (2007)

2. Daduna, J.R., Voss, S. : Practical experiences in schedule synchronization, Lecture Notes in Economics and Mathematical Systems, 430, 39-55. (1995)

3. Bertsekas, D. Auction Algorithm for Network Flow Problems : A Tutorial Introduction. Comput. Optim. Appl. 1, 7–66. (1992)