Optimization algorithms for large-scale bus and train unit scheduling

GIRO公司销售用于计划公共汽车和火车客运的软件，用于制定公共汽车和火车单位时刻表(行程顺序)。公共交通机构中电动公交车的出现以及跨区域客运轨道交通中新客户的到来，对GIRO的优化算法提出了新的挑战，主要是为了解决大规模问题。该项目旨在开发有效的算法来解决这类规划问题，力求在尊重所需服务水平的同时将运营成本降至最低。主要的研究目标有四个：1)大规模公交调度问题的算法研究；2)公交调度问题，其中调度对沿线能量消耗的变化是稳健的；3)公交车辆段夜间出现的公交充电和停车集成问题；4)带维护约束的列车单元调度问题。对于目标1、2和4，将设想结合机器学习和统计分析技术的列生成算法。对于目标3，将设计一种基于混合整数规划模型的数学方法。这些工作将使Giro能够向电动车队的规划进行必要的过渡，并通过提供一套更好的优化算法来巩固其在公共交通领域的世界领先地位。魁北克也将从中受益，因为魁北克的大多数公共交通协会都使用GIRO优化软件来规划其运营。此外，这项研究将促进魁北克公共交通向电气化的过渡，使其更加绿色，并将培训7名研究生。

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.