Models and algorithms for transit network planning - Ibarra Rojas, Omar Jorge (2012)
The efficiency of urban transport system strongly relies on the transit network planning process that is commonly complex because of the number of related decisions. Usually this process is divided into several subproblems such as line planning, timetable generation, vehicle scheduling, and crew scheduling which are solved sequentially to obtain an entire solution. In this study we focus on timetabling problems based on the transit network of Monterrey, Mexico. The characteristics present in this network lead to the Synchronization Bus Timetabling Problem (SBT) with the objective of maximize the number of synchronization events between different lines to allow well timed passenger transfers and avoid bus bunching. We design a mixed integer linear programming formulation (MILP) for SBT considering constraints such as bounds of separation times between consecutive trips and departure time dispersion along the planning period. We prove that SBT is NP-hard. Nevertheless, the mathematical structure of SBT MILP allow to define a preprocessing stage based on constraint propagation leading to the elimination of a high percentage of decision variables and constraints