TY - RPRT
T1 - Lagrangean Duality Applied on Vehicle Routing with Time Windows - Experimental Results
AU - Kallehauge, Brian
AU - Larsen, Jesper
AU - Madsen, Oli B.G.
PY - 2001
Y1 - 2001
N2 - 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.
AB - 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.
KW - non-differentiable optimization
KW - proximal bundle methods
KW - Vehicle Routing Problem with Time Windows
KW - trust region methods
KW - duality
KW - cutting plane methods
KW - Lagrangian relaxation
M3 - Report
BT - Lagrangean Duality Applied on Vehicle Routing with Time Windows - Experimental Results
ER -