Exact and Metaheuristic Approach for Bus Timetable Synchronization to Maximize Transfers

This article presents the application of mathematical programming and evolutionary algorithms to solve a variant of the Bus Timetabling Synchronization Problem. A new problem model is proposed to include extended synchronization points, accounting for every pair of bus stops in a city, the transfer demands for each pair of lines, and the offset for lines in the considered scenario. Mixed Integer Programming and evolutionary algorithm are proposed to efficiently solve the problem. A relevant real case study is solved, for the public transportation system of Montevideo, Uruguay. Several scenarios are solved and results are compared with the no-synchronization solution and the current planning of such transportation system too. Experimental results indicate that the proposed approaches are able to significantly improve the current plannings. The Mixed Integer Programming algorithm computed the optimum solution for all scenarios, accounting for an improvement of up to 95% in successful synchronizations when compared with the actual timetable in Montevideo. The evolutionary algorithm is efficient too, improving up to 68% the synchronizations with respect to the current planning and systematically outperforming the baseline solutions. Waiting times for users are significantly improved too, up to 33% in tight problem instances.