A Heuristic for the Time-Dependent Vehicle Routing Problem with Time Windows

Vincent Huart (), Sylvain Perron (), Gilles Caporossi () and Christophe Duhamel ()
Additional contact information
Vincent Huart: GERAD and HEC Montréal
Sylvain Perron: GERAD and HEC Montréal
Gilles Caporossi: GERAD and HEC Montréal
Christophe Duhamel: LIMOS, Université Blaise Pascal

A chapter in Computational Management Science, 2016, pp 73-78 from Springer

Abstract: Abstract We consider the Time-Dependent Vehicle Routing Problem (tdvrptw), a generalization of the Vehicle Routing Problem with Time Windows (vrptw) where the travel time between any pair of clients can vary over the time. Its purpose is to better handle the dynamic nature of the travel time, especially in urban areas where traffic congestion can have a significant impact on the transportation. We propose a heuristic based on column generation and on Variable Neighborhood Descent (vnd) for solving the tdvrptw. Several neighborhoods are used to identify improving columns at each iteration of the column generation process. Those columns are then stored in a shared pool. In the same time, the integer master problem is solved and its solution is then improved by the vnd. Both total distance and number of vehicle criteria are considered. Numerical results are then presented to show the interest of our approach.

Keywords: Local Search; Column Generation; Master Problem; Vehicle Route Problem; Speed Profile (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations: View citations in EconPapers (2)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnechp:978-3-319-20430-7_10

Ordering information: This item can be ordered from
http://www.springer.com/9783319204307

DOI: 10.1007/978-3-319-20430-7_10

Access Statistics for this chapter

More chapters in Lecture Notes in Economics and Mathematical Systems from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().