Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows

Said Dabia (), Stefan Ropke (), Tom van Woensel () and Ton De Kok ()
Additional contact information
Said Dabia: Eyefreight B.V., 3981 Bunnik, the Netherlands; and School of Industrial Engineering, Eindhoven University of Technology, 5600MB Eindhoven, the Netherlands
Stefan Ropke: Department of Transport, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark
Ton De Kok: School of Industrial Engineering, Eindhoven University of Technology, 5600MB Eindhoven, the Netherlands

Transportation Science, 2013, vol. 47, issue 3, 380-396

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.

Keywords: vehicle routing problem; column generation; time-dependent travel times; branch and price (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (44)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1120.0445 (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:47:y:2013:i:3:p:380-396

Access Statistics for this article

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