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.