TY - JOUR
T1 - The time window assignment vehicle routing problem with time-dependent travel times
AU - Spliet, R.
AU - Dabia, Said
AU - van Woensel, T.
PY - 2018/3
Y1 - 2018/3
N2 - 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 newvariant 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.
AB - 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 newvariant 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.
KW - Branch-price-And-cut
KW - Column generation
KW - Vehicle routing
UR - http://www.scopus.com/inward/record.url?scp=85045517296&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85045517296&partnerID=8YFLogxK
UR - http://www.mendeley.com/research/time-window-assignment-vehicle-routing-problem-timedependent-travel-times-1
U2 - 10.1287/trsc.2016.0705
DO - 10.1287/trsc.2016.0705
M3 - Article
AN - SCOPUS:85045517296
SN - 0041-1655
VL - 52
SP - 261
EP - 276
JO - Transportation Science
JF - Transportation Science
IS - 2
ER -