Exact and Evolutionary Algorithms for Synchronization of Public Transportation Timetables Considering Extended Transfer Zones

Abstract

This article addresses timetable synchronization in public transportation, an important problem in modern smart cities, in order to guarantee a proper quality of service to citizens. Two variants of the bus timetabling synchronization problem considering extended transfer zones are studied: optimizing offsets and optimizing offsets and headways for each line. An exact mixed integer programming and an evolutionary algorithm are developed to solve both problem variants. The algorithms are evaluated on 45 instances of a real case study, the intelligent transportation system of Montevideo, Uruguay. Experimental results reported significant improvements over the current timetable implemented by the city administration. The number of successful synchronizations improved up to 66.6% and 179.9% for the first and second problem variant, respectively. The average waiting times for transfers improved, especially in tight problem instances (up to 57.8% and 158.3% for the first and second problem variant, respectively). The proposed planning methods are useful to help decision makers to configure public transportation systems.

Keywords

• timetable synchronization
• public transportation planning
• mixed integer programming
• evolutionary algorithms
• real case study
• smart cities