Lagrangean Duality Applied on Vehicle Routing with Time Windows - Experimental Results

This report 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. The optimal multipliers are found using the non-differentiable method denoted the proximal bundle method.

The bundle-method has been coupled with a Dantzig-Wolfe algorithm in a branch-and-bound scheme. The root node of the branch-and-bound tree is solved by the bundle-method and, if an integer solution is not obtained, shifting to a Dantzig-Wolfe algorithm in the tree nodes. The combined bundle- and Dantzig-Wolfe algorithm has been tested on the well-known Solomon VRPTW benchmark problems and a range of extended Solomon problems.

Since we have succeded in solving 14 previously unsolved problems and an extended Solomon problem with 1000 customers, which is the largest problem ever solved to optimality, and since the computational times were reduced significantly by the bundle method in the root node compared to the Dantzig-Wolfe method it seems very efficient to combine the use of a bundle-method with a Dantzig-Wolfe algorithm, thereby combining the strengths of an Lagrangian relaxation approach with the strengths of an Dantzig-Wolfe decomposition approach for the VRPTW.