Optimization algorithms for large-scale bus and train unit scheduling

Giro公司将规划公共汽车和火车乘客运输的软件商业化，用于制定公共汽车和火车的单元时间表（行程顺序）。公共交通机构电动公交车的出现以及跨区域客运轨道交通新客户的到来，对Giro的优化算法提出了新的挑战，主要是为了解决大规模问题。该项目旨在开发有效的算法，以解决此类规划问题，在尊重期望的服务水平的同时，尽量减少运营成本。主要有四个研究目标：开发算法来解决1)考虑到需要时公交车充电的大规模公交调度问题；2)公交调度问题，其中调度对沿线能源消耗的可变性具有鲁棒性；3)公交车站夜间公交综合充电停车问题；具有维护约束的列车单元调度问题。对于目标1、2和4，将考虑结合机器学习和统计分析技术的列生成算法。对于目标3，将设计一个基于混合整数规划模型的数学模型。这些工作将使Giro能够向电动车队的规划进行必要的过渡，并通过提供一套更好的优化算法，巩固其在公共交通领域的世界领先地位。quacimac也将从中受益，因为quacimac的大多数公共交通协会都是用Giro的优化软件来规划运营的。此外，这项研究将促进向公共交通电气化过渡，使其更加环保，并将培训七名研究生。

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.