@TECHREPORT\{IMM2001-0145,
    author       = "B. Kallehauge and J. Larsen and O. B. G. Madsen",
    title        = "Lagrangean Duality Applied on Vehicle Routing with Time Windows - Experimental Results",
    year         = "2001",
    keywords     = "Lagrangian relaxation, duality, non-differentiable  optimization, cutting plane methods, trust region methods, proximal  bundle methods, Vehicle Routing Problem with Time Windows",
    number       = "",
    series       = "IMM-Technical Report-2001-9",
    institution  = "Informatics and Mathematical Modelling, Technical University of Denmark, {DTU}",
    address      = "Richard Petersens Plads, Building 321, {DK-}2800 Kgs. Lyngby",
    type         = "",
    url          = "http://www2.compute.dtu.dk/pubdb/pubs/145-full.html",
    abstract     = "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}."
}