The Time Window Assignment Vehicle Routing Problem with Time-Dependent Travel Times

Remy Spliet (), Said Dabia () and Tom Van Woensel ()
Additional contact information
Remy Spliet: Econometric Institute, Erasmus University, 3062 PA Rotterdam, Netherlands
Said Dabia: Department of Information, Logistics and Innovation, Vrije University, 1081 HV Amsterdam, Netherlands
Tom Van Woensel: Department of Industrial Engineering and Innovation Sciences, Eindhoven University of Technology, 5600 MB Eindhoven, Netherlands

Transportation Science, 2018, vol. 52, issue 2, 261-276

Abstract: In this paper, we introduce the time window assignment vehicle routing problem (TWAVRP) with time-dependent travel times. It is the problem of assigning time windows to customers before their demand is known and creating vehicle routes adhering to these time windows after demand becomes known. The goal is to assign the time windows in such a way that the expected transportation costs are minimized. We develop a branch-price-and-cut algorithm to solve this problem to optimality. The pricing problem that has to be solved is a new variant of the shortest path problem, which includes a capacity constraint, time-dependent travel times, time window constraints on both the nodes and on the arcs, and linear node costs. For solving the pricing problem, we develop an exact labeling algorithm and a tabu search heuristic. Furthermore, we present new valid inequalities, which are specifically designed for the TWAVRP with time-dependent travel times. Finally, we present results of numerical experiments to illustrate the performance of the algorithm.

Keywords: vehicle routing; column generation; branch-price-and-cut (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
https://doi.org/10.1287/trsc.2016.0705 (application/pdf)

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:inm:ortrsc:v:52:y:2018:i:2:p:261-276

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().