Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

École Polytechnique de Montréal

$51,000.00

Exact and heuristic algorithms for vehicle routing

FY 2017-18

Summary
Vehicle routing problems consist of determining least-cost vehicle routes to perform a set oftasks while respecting operational constraints, such as vehicle capacity and service time windows at the customers.Several problem variants exist, arising from different applications in, e.g., freight transportation and humanitarian logistics. In thisproposal, we develop mathematical optimization models and methods, called branch-price-and-cut methods, to help the planners determine thebest possible vehicle routes. The optimization methods can be classified into two categories: an exact methodseeks an optimal solution and can require substantial computational time; a heuristic method is much faster butprovides a good-quality solution that may not be optimal. We explore four research directions for exactmethods and one for heuristics. In particular, we aim at integrating machine learning algorithms developed in artificial intelligence into branch-price-and-cut algorithms that are widely used for vehicle routing. Furthermore, we develop optimization methods for two specific vehicle routingproblems: 1) the simultaneouspickup and deliveryproblem with time windows and a load fragility constraint that forbids stacking heavy items over light ones and 2) the vehicle routing problem with a moving depot that arises in humanitarian logistics when drones are dispatched from a moving helicopter to assess the extent of damage in different zones of a devastated area.From ascientific point of view, the results of this research are methodological and will be applicable to a widevariety of vehicle routing problems in different modes of transportation and even to certain problems arising inother domains. From a commercial point of view, these results will help the freight companies and the humanitarian logistic providers to better managethe utilization of their vehicles and will therefore contribute to increase the productivity of Canadiancompanies and reduce greenhouse gas emissions. Finally, from an academic point of view, this research will provide financial support and training tothree PhD, two MSc and one undergraduate students that will be in demand by the Canadian optimization softwaredevelopment companies after completing their studies.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2017-05683
Name nom
Desaulniers, Guy
Department département
Mathématiques et génie industriel - 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
2017
Competition year année de concours
2017
Award amount
51000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à 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
Partie
1
Nb partie
5
Application title
Exact and heuristic algorithms for vehicle routing
Keyword
NSERC
Application summary
Vehicle routing problems consist of determining least-cost vehicle routes to perform a set oftasks while respecting operational constraints, such as vehicle capacity and service time windows at the customers.Several problem variants exist, arising from different applications in, e.g., freight transportation and humanitarian logistics. In thisproposal, we develop mathematical optimization models and methods, called branch-price-and-cut methods, to help the planners determine thebest possible vehicle routes. The optimization methods can be classified into two categories: an exact methodseeks an optimal solution and can require substantial computational time; a heuristic method is much faster butprovides a good-quality solution that may not be optimal. We explore four research directions for exactmethods and one for heuristics. In particular, we aim at integrating machine learning algorithms developed in artificial intelligence into branch-price-and-cut algorithms that are widely used for vehicle routing. Furthermore, we develop optimization methods for two specific vehicle routingproblems: 1) the simultaneouspickup and deliveryproblem with time windows and a load fragility constraint that forbids stacking heavy items over light ones and 2) the vehicle routing problem with a moving depot that arises in humanitarian logistics when drones are dispatched from a moving helicopter to assess the extent of damage in different zones of a devastated area.From ascientific point of view, the results of this research are methodological and will be applicable to a widevariety of vehicle routing problems in different modes of transportation and even to certain problems arising inother domains. From a commercial point of view, these results will help the freight companies and the humanitarian logistic providers to better managethe utilization of their vehicles and will therefore contribute to increase the productivity of Canadiancompanies and reduce greenhouse gas emissions. Finally, from an academic point of view, this research will provide financial support and training tothree PhD, two MSc and one undergraduate students that will be in demand by the Canadian optimization softwaredevelopment companies after completing their studies.