Grant: Alliance Grants
École Polytechnique de Montréal
$51,552.00
Optimization algorithms for large-scale bus and train unit scheduling
EF 2024-25
Résumé
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.
Programme
Alliance Grants
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
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
2024
Competition year année de concours
2021
Award amount
51552
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
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Optimization algorithms for large-scale bus and train unit scheduling
Keywords
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.