Multi-objective re-synchronizing of bus timetable: Model, complexity and solution

This work is originally motivated by the re-planning of a bus network timetable. The existing timetable with even headways for the network is generated using line by line timetabling approach without considering the interactions between lines. Decision-makers (i.e., schedulers) intend to synchronize vehicle timetable of lines at transfer nodes to facilitate passenger transfers while being concerned with the impacts of re-designed timetable on the regularity of existing timetable and the accustomed trip plans of passengers. Regarding this situation, the authors investigate a multi-objective re-synchronizing of bus timetable (MSBT) problem, which is characterized by headway-sensitive passenger demand, uneven headways, service regularity, flexible synchronization and involvement of existing bus timetable. A multi-objective optimization model for the MSBT is proposed to make a trade-off between the total number of passengers benefited by smooth transfers and the maximal deviation from the departure times of the existing timetable. By clarifying the mathematical properties and solution space of the model, the authors prove that the MSBT problem is non-deterministic polynomial-time (NP)-hard, and its Pareto-optimal front is non-convex. Therefore, the authors design a non-dominated sorting genetic (NSGA-II) based algorithm to solve this problem. Numerical experiments show that the designed algorithm, compared with enumeration method, can generate high-quality Pareto solutions within reasonable times. The authors also find that the timetable allowing larger flexibility of headways can obtain more and better Pareto-optimal solutions, which can provide decision-makers more choice.


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01600214
  • Record Type: Publication
  • Files: TRIS
  • Created Date: May 16 2016 2:41PM