Valid inequalities for the synchronization bus timetabling problem - Sorbonne Université
Article Dans Une Revue European Journal of Operational Research Année : 2016

Valid inequalities for the synchronization bus timetabling problem

Pierre Fouilhoux
Ibarra-Rojas Omar J.
  • Fonction : Auteur
Safia Kedad-Sidhoum
Yasmin Rios-Solis
  • Fonction : Auteur

Résumé

Bus transit network planning is a complex process that is divided into several phases such as: line planning, timetable generation, vehicle scheduling, and crew scheduling. In this work, we address the timetable generation which consists in scheduling the departure times for all trips of each bus line. We focus on the Synchronization Bus Timetabling Problem (SBTP) that favors passenger transfers and avoids congestion of buses at common stops. A Mixed Integer Program (MIP) was proposed in the literature for the SBTP but it fails to solve real bus network instances. We develop in this paper four classes of valid inequalities for this MIP using combinatorial properties of the SBTP on the number of synchronizations. Experimental results show that large instances are solved within few minutes with a relative deviation from the optimal solution that is usually less than 3 percent.
Fichier non déposé

Dates et versions

hal-01303053 , version 1 (15-04-2016)

Identifiants

Citer

Pierre Fouilhoux, Ibarra-Rojas Omar J., Safia Kedad-Sidhoum, Yasmin Rios-Solis. Valid inequalities for the synchronization bus timetabling problem. European Journal of Operational Research, 2016, 251 (2), pp.442-450. ⟨10.1016/j.ejor.2015.12.006⟩. ⟨hal-01303053⟩
272 Consultations
0 Téléchargements

Altmetric

Partager

More