Kallehauge, Brian4; Larsen, Jesper5; Madsen, Oli B.G.1
1 Department of Transport, Technical University of Denmark2 Operations Research, Department of Informatics and Mathematical Modeling, Technical University of Denmark3 Department of Informatics and Mathematical Modeling, Technical University of Denmark4 Management Science, Department of Management Engineering, Technical University of Denmark5 Department of Management Engineering, Technical University of Denmark
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.
non-differentiable optimization; proximal bundle methods; Vehicle Routing Problem with Time Windows; trust region methods; duality; cutting plane methods; Lagrangian relaxation