The Delivery Man Problem with Time Windows

Géraldine Heilporn (Geraldine.Heilpornhec.ca)
Jean-François Cordeau (jean-francois.cordeauhec.ca)
Gilbert Laporte (gilbertcrt.umontreal.ca)

Abstract: In this paper, a variant of the Traveling Salesman Problem with Time Windows is considered, which consists in minimizing the sum of travel durations between a depot and several customer locations. Two mixed integer linear programming formulations are presented for this problem: a classical arc flow model and a sequential assignment model. Several polyhedral results are provided for the second formulation, in the special case arising when there is a closed time window only at the depot, while open time windows are considered at all other locations. Exact and heuristic algorithms are also proposed for the problem. Computational results show that medium size instances can be solved exactly with both models, while the heuristic provides good quality solutions for medium to large size instances.

Keywords: Delivery Man Problem, Traveling Salesman Problem, Time windows, Polyhedral analysis, Mixed integer linear programming.

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: To appear in Discrete Optimization.

Download:

Entry Submitted: 09/01/2009
Entry Accepted: 09/01/2009
Entry Last Modified: 07/12/2010

Modify/Update this entry