Optimization Online


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

Gonzalo Lera Romero(gleraromero***at***dc.uba.ar)
Juan José Miranda Bront(jmiranda***at***utdt.edu)
Francisco Soulignac(francisco.soulignac***at***unq.edu.ar)

Abstract: In this paper we implement a branch and price (BP) algorithm for a time dependent vehicle routing problem with time windows (TDVRPTW) in which the goal is to minimize the total route duration (DM-TDVRPTW). The travel time between two customers depends on the departure time and, thus, it need not remain fixed along the planning horizon. We propose several improvements to the exact labeling algorithm by Dabia et al. (Branch and price for the time-dependent vehicle routing problem with time windows, Transportation Science 47(3):380–396, 2013) for solving the pricing problem, while we provide a tailored implementation for the dominance tests that relies on efficient data structures for storing the enumerated labels. Computational results show that the proposed techniques are effective for accelerating the column generation step. The obtained BP algorithm is able to solve benchmark instances with up to 100 customers, being able to solve all the instances with 25 customers. Furthermore, heuristic adaptations are able to find good quality solutions in reasonable computing times, showing its potential to be applied in practice.

Keywords: vehicle routing problem; time windows; time dependent travel times; branch and price; dynamic programming

Category 1: Applications -- OR and Management Sciences

Category 2: Combinatorial Optimization (Other )


Download: [PDF]

Entry Submitted: 06/24/2018
Entry Accepted: 06/24/2018
Entry Last Modified: 06/24/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society