Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

École Polytechnique de Montréal

$20,015.00

Exact and heuristic approaches for time-constrained vehicle routing

FY 2008-09

Summary
I am interested in various time-constrained vehicle routing problems which arise mostly in freight transportation. A generic definition for these problems is: given a set of tasks, a time window (interval) for each task, and a set of capacitated vehicles assigned to one or several depots whose locations may have to be determined, find a set of least-cost feasible routes for those vehicles such that each task is executed once within its time window, each route is feasible with respect to vehicle capacity, and side constraints are satisfied. My long-term objectives are: 1- to develop mathematical decomposition methods for solving to optimality such problems; and 2- to show that, for these problems, such methods can be integrated into metaheuristic frameworks to yield, in reasonable times, better solutions than those produced by the exsiting heuristics. In this proposal, I focus on the vehicle routing problem with time windows (VRPTW), the multi-depot VRPTW (MDVRPTW), and the location-routing problem with time windows (LRPTW). For the VRPTW, I will develop an exact branch-and-price-and-cut (BPC) algorithm and a large neighborhood search heuristic that relies on a BPC heuristic for neighborhood exploration. For the MDVRPTW, I will generalize the exact and heuristic algorithms proposed for the VRPTW. Finally, for the LRPTW, I will introduce two exact algorithms, one based on BPC and the other on Benders decomposition, and a two-level large neighborhood search algorithms that works at the top level on depot location and, at the bottom level, on vehicle routing. To explore the neighborhoods, mixed integer programming and BPC are used at the top and bottom levels, respectively. The research proposal will contribute to the development of efficient software systems for the transportation industry and produce methodological advances on three related problems. Its funding will support the training of 5 master's students, 2 PhD students, and 1 post-doc fellow.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
157935-2007
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
2008
Competition year année de concours
2007
Award amount
20015
Program id
RGPIN
Program nane 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
20
Committee name en
Industrial Engineering
Committee name fr
Génie industriel
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
2
Nb partie
5
Application title
Exact and heuristic approaches for time-constrained vehicle routing
Keyword
NA
Application summary
I am interested in various time-constrained vehicle routing problems which arise mostly in freight transportation. A generic definition for these problems is: given a set of tasks, a time window (interval) for each task, and a set of capacitated vehicles assigned to one or several depots whose locations may have to be determined, find a set of least-cost feasible routes for those vehicles such that each task is executed once within its time window, each route is feasible with respect to vehicle capacity, and side constraints are satisfied. My long-term objectives are: 1- to develop mathematical decomposition methods for solving to optimality such problems; and 2- to show that, for these problems, such methods can be integrated into metaheuristic frameworks to yield, in reasonable times, better solutions than those produced by the exsiting heuristics. In this proposal, I focus on the vehicle routing problem with time windows (VRPTW), the multi-depot VRPTW (MDVRPTW), and the location-routing problem with time windows (LRPTW). For the VRPTW, I will develop an exact branch-and-price-and-cut (BPC) algorithm and a large neighborhood search heuristic that relies on a BPC heuristic for neighborhood exploration. For the MDVRPTW, I will generalize the exact and heuristic algorithms proposed for the VRPTW. Finally, for the LRPTW, I will introduce two exact algorithms, one based on BPC and the other on Benders decomposition, and a two-level large neighborhood search algorithms that works at the top level on depot location and, at the bottom level, on vehicle routing. To explore the neighborhoods, mixed integer programming and BPC are used at the top and bottom levels, respectively. The research proposal will contribute to the development of efficient software systems for the transportation industry and produce methodological advances on three related problems. Its funding will support the training of 5 master's students, 2 PhD students, and 1 post-doc fellow.