Accueil

HORUS, projet ANR du programme COSINUS

Horaires Optimisés dans les Réseaux de transports Urbains et interurbains

La construction des horaires dans le domaine des transports publics urbains, périurbains et interurbains est un enjeu majeur pour les opérateurs publics et privés. La très grande complexité de cette tâche justifie généralement son découpage en étapes séquentielles : construction des horaires des bus, tramways ou trains, habillage de ces horaires par des matériels (graphicage) puis par des services conducteurs (habillage), et enfin, élaboration de plannings individuels nominatifs. Seuls de grands réseaux peuvent bénéficier d'une offre faisant appel à des modules d'optimisation. Depuis une dizaine d'années, EURODECISION a équipé la RATP et plus récemment le groupe VEOLIA Transport de son composant métier LP-EasyDriver permettant un habillage optimisé des horaires de bus par des services ou horaires de chauffeurs. Les méthodes d'optimisation de cette offre et des offres concurrentes sont basées sur des techniques de génération de colonnes. Dans le domaine ferroviaire, l’utilisation de méthodes d’optimisation des horaires est moins répandue en raison d’une complexité plus grande des problèmes.

L’objectif principal du projet HORUS est de préparer les offres de la nouvelle génération en relevant plusieurs défis :

  • extension au domaine ferroviaire (complexité combinatoire accrue et plus grande complexité métier),
  • conception d’une optimisation globale du graphicage et de l’habillage,
  • accès au calcul multi-coeur via la parallélisation des algorithmes,
  • mise à disposition des algorithmes d’optimisation via des logiciels libres et des web services de calcul mutualisés.

D'un point de vue académique, le PRiSM et le CReSTIC deux laboratoires universitaires reconnus pour leur expertise en optimisation combinatoire (méthodes avancées en génération de colonnes et métaheuristiques) et en calcul parallèle, proposent ainsi des contributions significatives dans les méthodes de résolution séquentielles et parallèles dédiées à ces problématiques: modélisation par arcs-états, génération de colonnes, métaheuristique innovante (Trust Branching Path) et hybridation entre métaheuristiques et méthodes exactes.

Bus, tramway and train scheduling and the corresponding workforce planning are major issues for public and private transportation companies. The complexity of this task usually justifies its decomposition in sequential steps : timetabling of the bus, tramways or trains, assignment of the vehicles to the transportation tasks, building shifts, and finally, individual rostering. Currently, only the major companies have access to optimisation modules. In the last decade, EURODECISION integrated its optimization component, LP-EasyDriver, to the activities of RATP and, more recently, VEOLIA. This offer, as well as similar ones from competitors, is based on column generation techniques. In the railway sector, the use of optimization modules is less expanded because of the higher complexity of the problems.

The main goal of HORUS project is to overcome the following challenges :

  • extension of the bus optimisation systems to the railway sector (higher combinatorial complexity and higher business complexity),
  • global optimization of the whole problem (time tabling and crew scheduling),
  • access to multi-core computing through algorithms parallelization,
  • access to the optimization algorithms through free software and shared web services.

From an academic point of view PRiSM and CReSTIC laboratories, which are well known for their specialization in combinatorial optimization and parallel computing, propose in this project significant contributions in the resolution methods dedicated to these kinds of problems: arcs-states modeling, column generation algorithms, innovative metaheuristic (Trust Branching Path) and hybridization techniques including metaheuristics and exact approaches.