Optimization algorithms for large-scale bus and train unit scheduling

点击翻译按钮获取中文摘要

The Giro company commercializes softwares for planning passenger transportation by bus and by train for establishing bus and train unit schedules (sequences of trips). The advent of electric buses in public transit agencies and the arrival of new customers in inter-regional passenger rail transport pose new challenges for Giro's optimization algorithms, mostly for solving large-scale problems. This project aims at developing efficient algorithms for solving such planning problems that seek to minimize the operational costs while respecting the desired level of service. Four main research objectives will be targeted: Developing algorithms for solving 1) large-scale bus scheduling problems taking into account bus recharging if needed; 2) bus scheduling problems where the schedules are robust to the variability of the energy consumed along the routes; 3) integrated bus recharging and parking problems arising in the bus depots overnight; 4) train unit scheduling problems with maintenance constraints. For objectives 1, 2 and 4, column generation algorithms combined with machine learning and statistical analysis techniques will be conceived. For objective 3, a matheuristic based on a mixed-integer programming model will be devised. These works will allow Giro to make the necessary transition towards the planning of electric fleets and to consolidate its world-leadership in public transport by offering a better suite of optimization algorithms. Québec will also benefit from them since most public transit societies in Québec plan their operations with the optimization softwares of Giro. Furthermore, this research will facilitate the transition towards the electrification of public transportation in Québec, making it greener, and will train seven graduate students.