Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$82,000.00
Optimization algorithms for rich vehicle routing problems
EF 2024-25
Résumé
Vehicle routing problems (VRPs) consist of determining a set of least-cost vehicle routes to accomplish a set of tasks while respecting operational constraints such as vehicle capacity and delivery time windows at customers. Many problem variants arise from different applications in freight transportation, parcel delivery, humanitarian logistics, etc. With evolving technologies (e.g., electric vehicles or drones), several of them are new and complex to solve. In this research proposal for the next five years and beyond, we develop mathematical optimization models and algorithms, called branch-price-and-cut (BPC) algorithms, to help planners solve these problems and determine the best possible vehicle routes. We explore four main directions of research. In two of them, we aim at integrating machine learning (artificial intelligence) tools into BPC algorithms to make them more efficient. In the third, we focus on complex vehicle routing problems involving time synchronization constraints (for example, when two vehicles must meet to transfer a load) that are difficult to handle in the BPC algorithms. Finally, in the fourth direction, we devise new algorithms for two specific vehicle routing problems arising in city logistics and in humanitarian logistics. Different contemporary vehicle routing problems will serve as case studies, namely, some involving electric commercial vehicles (trucks), drones for parcel delivery, and electric mini-vans for disabled transportation.
This research will make contributions at various levels. From a scientific point of view, the expected results are methodological and, most of them, will be applicable to a wide variety of vehicle routing problems in different transportation modes and even to certain problems arising in other domains. From a commercial point of view, these results will help transportation companies and humanitarian logistics providers to better manage their vehicle fleet utilization and will therefore contribute to increase the productivity of Canadian companies. From a societal point of view, our research will help to reduce greenhouse gas emissions (by better managing fleet of electric vehicles and drones) and to improve the transportation of disabled persons (by better planning the routes of the vehicles transporting disabled persons). Finally, from an academic point of view, funding this research will provide financial support and training to four PhD students, two MSc students, and two undergraduate students that will be in demand after completing their studies in Canadian optimization software companies and potentially for academic positions.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2023-03791
Name nom
Desaulniers, Guy
Department département
Mathematics and industrial engineering
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
2023
Award amount
82000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
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 rich vehicle routing problems
Keywords
operations research; transportation; vehicle routing; branch-price-and-cut; matheuristics; machine learning; timing constraints
Application summary
Vehicle routing problems (VRPs) consist of determining a set of least-cost vehicle routes to accomplish a set of tasks while respecting operational constraints such as vehicle capacity and delivery time windows at customers. Many problem variants arise from different applications in freight transportation, parcel delivery, humanitarian logistics, etc. With evolving technologies (e.g., electric vehicles or drones), several of them are new and complex to solve. In this research proposal for the next five years and beyond, we develop mathematical optimization models and algorithms, called branch-price-and-cut (BPC) algorithms, to help planners solve these problems and determine the best possible vehicle routes. We explore four main directions of research. In two of them, we aim at integrating machine learning (artificial intelligence) tools into BPC algorithms to make them more efficient. In the third, we focus on complex vehicle routing problems involving time synchronization constraints (for example, when two vehicles must meet to transfer a load) that are difficult to handle in the BPC algorithms. Finally, in the fourth direction, we devise new algorithms for two specific vehicle routing problems arising in city logistics and in humanitarian logistics. Different contemporary vehicle routing problems will serve as case studies, namely, some involving electric commercial vehicles (trucks), drones for parcel delivery, and electric mini-vans for disabled transportation.
This research will make contributions at various levels. From a scientific point of view, the expected results are methodological and, most of them, will be applicable to a wide variety of vehicle routing problems in different transportation modes and even to certain problems arising in other domains. From a commercial point of view, these results will help transportation companies and humanitarian logistics providers to better manage their vehicle fleet utilization and will therefore contribute to increase the productivity of Canadian companies. From a societal point of view, our research will help to reduce greenhouse gas emissions (by better managing fleet of electric vehicles and drones) and to improve the transportation of disabled persons (by better planning the routes of the vehicles transporting disabled persons). Finally, from an academic point of view, funding this research will provide financial support and training to four PhD students, two MSc students, and two undergraduate students that will be in demand after completing their studies in Canadian optimization software companies and potentially for academic positions.