Lagrangean Duality Applied on Vehicle Routing with Time Windows

Brian Kallehauge (bkctt.dtu.dk)
Jesper Larsen (jlaimm.dtu.dk)
Oli B.G. Madsen (ogmctt.dtu.dk)

Abstract: This paper presents the results of the application of a non-differentiable optimization method in connection with the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is an extension of the Vehicle Routing Problem. In the VRPTW the service at each customer must start within an associated time window. The Shortest Path decomposition of the VRPTW by Lagrangian relaxation require the finding of the optimal Lagrangian multipliers. This problem is a convex non-differentiable optimization problem. We propose a cutting-plane algorithm with a trust-region stabilizing device for finding the optimal multipliers. The cutting-plane algorithm with trust-region has been combined with a Dantzig-Wolfe algorithm for finding integer solutions in a branch-and-bound scheme. The root node of the branch-and-bound tree is solved by the cutting-plane algorithm and, if an integer solution is not obtained, shifting to a Dantzig-Wolfe algorithm in the tree nodes occurs. The combined cutting-plane and Dantzig-Wolfe algorithm has been tested on the well-known Solomon VRPTW benchmark problems and a range of extended Solomon problems created by Homberger. We have succeeded in solving 14 previously unsolved Solomon problems and a Homberger problem with 1000 customers, which is the largest problem ever solved to optimality. The computational times were reduced significantly by the cutting-plane algorithm in the root node compared to the Dantzig-Wolfe method due to easier subproblems. It therefore seems very efficient to stabilize the dual variables.

Keywords: Lagrangian relaxation, duality, non-differentiable optimization, cutting plane method, trust region method, Vehicle Routing Problem with Time Windows

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Technical Report IMM-TR-2001-9 Informatics and Mathematical Modelling, Technical University of Denmark, Kgs. Lyngby, Denmark August/2001

Download: [Compressed Postscript][PDF]

Entry Submitted: 11/06/2001
Entry Accepted: 11/06/2001
Entry Last Modified: 11/06/2001

Modify/Update this entry