Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

École Polytechnique de Montréal

$47,000.00

Exact and heuristic solution methods for time-constrained vehicle routing

EF 2012-13

Résumé
Time-constrained vehicle routing problems consist of determining least-cost vehicle routes to cover a set of tasks such that each task is executed within a predefined time window and vehicle capacity is respected for each route. Several problem variants exist, arising from different applications in freight transportation. In this proposal, we develop mathematical optimization models and methods to help the planners in determining the best possible vehicle routes. The optimization methods can be classified into two categories: an exact method seeks an optimal solution and can require substantial computational time; a heuristic method is much faster but provides a good-quality solution that may not be optimal. We explore three research directions for exact methods and one for heuristics. Furthermore, we develop optimization methods for two specific vehicle routing problems: the split delivery vehicle routing problem with time windows and synchronization constraints that allows multiple visits to each customer if they occur simultaneously; and the pickup and delivery vehicle routing problem with time windows and last-in, first-out constraints that consists of picking up merchandise at customers to deliver it at specific locations in the reverse order of the corresponding pickup operations. From a scientific point of view, the results of this research are rather methodological and will be applicable to a wide variety of vehicle routing problems in different mode of transportation and even to certain problems arising in other domains. From a commercial point of view, these results will help the freight companies to better manage the utilization of their vehicles and will therefore contribute to increase the productivity of Canadian companies. Finally, from an academic point of view, this research will provide financial support and training to three PhD students and two MSc students that will be in demand by the Canadian optimization software development companies after completing their studies.
Programme
Discovery Grants Program - Individual
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
157935-2012
Name nom
Desaulniers, Guy
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
2012
Competition year année de concours
2012
Award amount
47000
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 solution methods for time-constrained vehicle routing
Keyword
NSERC
Application summary
Time-constrained vehicle routing problems consist of determining least-cost vehicle routes to cover a set of tasks such that each task is executed within a predefined time window and vehicle capacity is respected for each route. Several problem variants exist, arising from different applications in freight transportation. In this proposal, we develop mathematical optimization models and methods to help the planners in determining the best possible vehicle routes. The optimization methods can be classified into two categories: an exact method seeks an optimal solution and can require substantial computational time; a heuristic method is much faster but provides a good-quality solution that may not be optimal. We explore three research directions for exact methods and one for heuristics. Furthermore, we develop optimization methods for two specific vehicle routing problems: the split delivery vehicle routing problem with time windows and synchronization constraints that allows multiple visits to each customer if they occur simultaneously; and the pickup and delivery vehicle routing problem with time windows and last-in, first-out constraints that consists of picking up merchandise at customers to deliver it at specific locations in the reverse order of the corresponding pickup operations. From a scientific point of view, the results of this research are rather methodological and will be applicable to a wide variety of vehicle routing problems in different mode of transportation and even to certain problems arising in other domains. From a commercial point of view, these results will help the freight companies to better manage the utilization of their vehicles and will therefore contribute to increase the productivity of Canadian companies. Finally, from an academic point of view, this research will provide financial support and training to three PhD students and two MSc students that will be in demand by the Canadian optimization software development companies after completing their studies.