Paper Info
Title
Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows
Abstract
This paper presents a branch-and-price algorithm for the time-dependent vehicle routing problem with time windows TDVRPTW. We capture road congestion by considering time-dependent travel times, i.e., depending on the departure time to a customer, a different travel time is incurred. We consider the variant of the TDVRPTW where the objective is to minimize total route duration and denote this variant the duration minimizing TDVRPTW DM-TDVRPTW. Because of time dependency, vehicles' dispatch times at the depot are crucial as road congestion might be avoided. Because of its complexity, all known solution methods to the DM-TDVRPTW are based on meta-heuristics. The decomposition of an arc-based formulation leads to a set-partitioning problem as the master problem, and a time-dependent shortest path problem with resource constraints as the pricing problem. The master problem is solved by means of column generation, and a tailored labeling algorithm is used to solve the pricing problem. We introduce new dominance criteria that allow more label dominance. For our numerical results, we modified Solomon's data sets by adding time dependency. Our algorithm is able to solve about 63% of the instances with 25 customers, 38% of the instances with 50 customers, and 15% of the instances with 100 customers.
Year
DOI
Venue
2013
10.1287/trsc.1120.0445
Transportation Science
Keywords
Field
DocType
set-partitioning problem,master problem,time windows tdvrptw,pricing problem,time-dependent vehicle routing problem,time-dependent travel time,different travel time,departure time,time windows,time dependency,road congestion,time-dependent shortest path problem,branch and price,vehicle routing problem,column generation
Graph theory,Column generation,Data set,Mathematical optimization,Vehicle routing problem,Shortest path problem,Computer science,Branch and price,Linear programming,Traffic congestion,Operations management
Journal
Volume
Issue
ISSN
47
3
0041-1655
Citations 
PageRank 
References 
15
0.68
34
Authors
4
Name
Order
Citations
PageRank
Said Dabia1314.11
Stefan Ropke2134755.90
eu354939.51
Ton de Kok412612.45