Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Université du Québec à Montréal

$22,000.00

Mathematical programming techniques for the solution of hard combinatorial optimization problems arising in transportation

FY 2014-15

Summary
This research plan is intended to study several classes of vehicle routing problems with synchronization constraints, to propose modeling approaches and efficient exact and heuristic algorithms. Notably, we consider vehicle routing problems with transfers and multiple-echelon vehicle routing problems. These classes of vehicle routing problems share a common characteristic: either because of synchronization at transfer points or consolidation points, the underlying timing issue plays a crucial role in determining the efficiency of a given solution. Indeed, if the timing issue is not properly handled, one may end with a possibly cheaper solution in terms of traveling time, but much more expensive in terms of total ride time (which includes the dead times due to improper synchronization).The methodological plan can be summarized as follows: First, we seek to develop appropriate mixed-integer models for these classes of vehicle routing problems. We are not interested in just any type of model, but the ones that will allow us to exploit the underlying structure of each problem, either in the context of an exact solver or a heuristic algorithm. For the exact solvers, we will consider known paradigms such as the branch-and-cut method, the column generation framework and Benders decomposition. On the other hand, we will develop heuristic algorithms based on neighborhood search coupled with integer programming methods, the latter being adaptations of the exact methods developed before.We will complement these theoretical and algorithmic developments with actual applications to real-life logistics problems. To that end, we will search for industrial partners that may be interested into applying some of the techniques applied during this research plan to their operational planning.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
435824-2013
Name nom
ContardoVera, Claudio
Department département
Management et technologie
Organization id
57
Institution établissement
Université du Québec à Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2013
Award amount
22000
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
2
Nb partie
5
Application title
Mathematical programming techniques for the solution of hard combinatorial optimization problems arising in transportation
Keyword
NSERC
Application summary
This research plan is intended to study several classes of vehicle routing problems with synchronization constraints, to propose modeling approaches and efficient exact and heuristic algorithms. Notably, we consider vehicle routing problems with transfers and multiple-echelon vehicle routing problems. These classes of vehicle routing problems share a common characteristic: either because of synchronization at transfer points or consolidation points, the underlying timing issue plays a crucial role in determining the efficiency of a given solution. Indeed, if the timing issue is not properly handled, one may end with a possibly cheaper solution in terms of traveling time, but much more expensive in terms of total ride time (which includes the dead times due to improper synchronization).The methodological plan can be summarized as follows: First, we seek to develop appropriate mixed-integer models for these classes of vehicle routing problems. We are not interested in just any type of model, but the ones that will allow us to exploit the underlying structure of each problem, either in the context of an exact solver or a heuristic algorithm. For the exact solvers, we will consider known paradigms such as the branch-and-cut method, the column generation framework and Benders decomposition. On the other hand, we will develop heuristic algorithms based on neighborhood search coupled with integer programming methods, the latter being adaptations of the exact methods developed before.We will complement these theoretical and algorithmic developments with actual applications to real-life logistics problems. To that end, we will search for industrial partners that may be interested into applying some of the techniques applied during this research plan to their operational planning.