Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Alliance Grants

École Polytechnique de Montréal

$52,757.00

Optimization algorithms for large-scale bus and train unit scheduling

FY 2023-24

Summary
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. La compagnie Giro commercialise des logiciels de planification du transport de passagers en autobus et en train pour déterminer les horaires (suites de voyages) des autobus et des rames de train. L'avènement des autobus électriques dans les sociétés de transport public et la venue de nouveaux clients en transport ferroviaire de passagers inter-régional posent de nouveaux défis aux algorithmes d'optimisation de Giro, surtout pour résoudre des problèmes de grande taille. Ce projet vise donc à développer des algorithmes efficaces pour résoudre de tels problèmes de planification qui cherchent à minimiser les coûts d'opération tout en respectant le niveau de service attendu. Quatre objectifs de recherche principaux sont poursuivis: Développer des algorithmes pour résoudre 1) des problèmes d'horaires d'autobus de très grande taille prenant en compte la recharge des autobus au besoin; 2) des problèmes d'horaires d'autobus robustes vis-à-vis de la variabilité de la décharge des batteries; 3) des problèmes intégrés de recharge et stationnement d'autobus la nuit; et 4) des problèmes d'horaires de rames de train avec contraintes de maintenance. Pour les objectifs 1, 2 et 4, des algorithmes de génération de colonnes combinés à des techniques d'apprentissage machine et d'analyse statistique seront conçus. Pour l'objectif 3, une matheuristique basée sur un modèle de programmation en nombres entiers sera mise en oeuvre. Ces travaux permettront à Giro d'effectuer la transition nécessaire vers la planification de flottes électriques et de consolider sa position de leader mondial en transport public en offrant une meilleure gamme d'algorithmes d'optimisation. Le Québec en bénéficiera aussi puisque la plupart des grandes sociétés de transport public québécoises planifient leurs opérations avec les logiciels d'optimisation de Giro. De plus, cette recherche facilitera la transition vers l'électrification des transports publics au Québec, les rendant plus verts, et formera sept étudiants aux études supérieures.
Program
Alliance Grants
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
567169-2021
Name nom
Desaulniers, Guy G
Department département
Mathématiques et génie industriel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2021
Award amount
52757
Program id
ALLRP
Program name en
Alliance Grants
Program name fr
Subventions Alliance
Group en
RESEARCH PARTNERSHIPS
Group fr
PARTENARIATS DE RECHERCHE
Committee code
96
Committee name en
RPP Internal Decision Cttee
Committee name fr
Cté de décision interne - PPR
Area of application code
700
Area of application group en
Transportation systems and services
Area of application group fr
Services et systèmes de transport
Area of application en
Transportation systems and services
Area of application fr
Services et systèmes de transport
Research subject code
2715
Research subject group en
Information technology
Research subject group fr
Optimization
Research subject en
Technologie de l'information
Research subject fr
Optimisation
Application title
Optimization algorithms for large-scale bus and train unit scheduling
Keyword
bus parking; bus scheduling; column generation; degeneracy; electric bus recharging; large-scale problems; machine learning; operations research; passenger transportation; train unit scheduling
Application summary
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. La compagnie Giro commercialise des logiciels de planification du transport de passagers en autobus et en train pour déterminer les horaires (suites de voyages) des autobus et des rames de train. L'avènement des autobus électriques dans les sociétés de transport public et la venue de nouveaux clients en transport ferroviaire de passagers inter-régional posent de nouveaux défis aux algorithmes d'optimisation de Giro, surtout pour résoudre des problèmes de grande taille. Ce projet vise donc à développer des algorithmes efficaces pour résoudre de tels problèmes de planification qui cherchent à minimiser les coûts d'opération tout en respectant le niveau de service attendu. Quatre objectifs de recherche principaux sont poursuivis: Développer des algorithmes pour résoudre 1) des problèmes d'horaires d'autobus de très grande taille prenant en compte la recharge des autobus au besoin; 2) des problèmes d'horaires d'autobus robustes vis-à-vis de la variabilité de la décharge des batteries; 3) des problèmes intégrés de recharge et stationnement d'autobus la nuit; et 4) des problèmes d'horaires de rames de train avec contraintes de maintenance. Pour les objectifs 1, 2 et 4, des algorithmes de génération de colonnes combinés à des techniques d'apprentissage machine et d'analyse statistique seront conçus. Pour l'objectif 3, une matheuristique basée sur un modèle de programmation en nombres entiers sera mise en oeuvre. Ces travaux permettront à Giro d'effectuer la transition nécessaire vers la planification de flottes électriques et de consolider sa position de leader mondial en transport public en offrant une meilleure gamme d'algorithmes d'optimisation. Le Québec en bénéficiera aussi puisque la plupart des grandes sociétés de transport public québécoises planifient leurs opérations avec les logiciels d'optimisation de Giro. De plus, cette recherche facilitera la transition vers l'électrification des transports publics au Québec, les rendant plus verts, et formera sept étudiants aux études supérieures.
École Polytechnique de Montréal - $52,757 Grant (2023… | Canada Spends