A Bi-directional Resource-bounded Dynamic Programming Approach for the Traveling Salesman Problem with Time Windows

Jing-Quan Li (jingquanpath.berkeley.edu)

Abstract: This paper presents a bi-directional resource-bounded label setting algorithm for the traveling salesman problem with time windows, in which the objective is to minimize travel times. Label extensions and dominance start simultaneously in both forward and backward directions: the forward direction from the starting depot and the backward direction from the terminating depot. The resultant label extension process scans much smaller the space than in single directional dynamic programming, substantially reducing the number of non-dominated labels. The labels for both the forward direction and backward direction are ultimately joined to form a complete route if all relevant feasibility conditions are satisfied. Our algorithm generates optimal solutions for a number of the instances with wide time windows for which no optimal solutions have been previously reported.

Keywords: Dynamic Programming, Time Windows, Bi-directional Search

Category 1: Network Optimization

Citation: Research report

Download: [PDF]

Entry Submitted: 03/27/2009
Entry Accepted: 03/30/2009
Entry Last Modified: 01/05/2011

Modify/Update this entry