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

This paper presents a branch-and-price algorithm for the time-dependent vehicle routing problem with time windows (TDVRPTW). The authors 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. They 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. The authors introduce new dominance criteria that allow more label dominance. For their numerical results, the authors modified Solomon's data sets by adding time dependency. Their 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.

• Record URL:
  https://doi.org/10.1287/trsc.1120.0445
• Record URL:
  http://transci.journal.informs.org/content/47/3/380.abstract
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Supplemental Notes:
  • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
• Authors:
  • Dabia, Said
  • Ropke, Stefan
  • van Woensel, Tom
  • De Kok, Ton
• Publication Date: 2013-8

Language

• English

Media Info

• Media Type: Print
• Features: Appendices; Figures; References; Tables;
• Pagination: pp 380-396
• Serial:
  • Transportation Science
  • Volume: 47
  • Issue Number: 3
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Branch and bound algorithms; Dispatching; Time dependence; Time windows; Traffic congestion
• Uncontrolled Terms: Column generation (Mathematics); Vehicle routing problem
• Subject Areas: Highways; Planning and Forecasting; I71: Traffic Theory;

Filing Info

• Accession Number: 01493712
• Record Type: Publication
• Files: TRIS
• Created Date: Sep 17 2013 11:18AM