@PHDTHESIS\{IMM1999-0140,
    author       = "J. Larsen",
    title        = "Parallelization of the Vehicle Routing Problem with Time Windows",
    year         = "1999",
    month        = "may",
    school       = "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/140-full.html",
    abstract     = "This dissertation presents a number of algorithms for solving the
Vehicle Routing Problem with Time Windows (VRPTW). The {VRPTW} is a
generalization of the well known capacity constrained Vehicle Routing
Problem (VRP). In the {VRP} a fleet of vehicles based at a central depot
must service a set of customers. In the {VRPTW} each customer has a
time window. Service of a customer must begin within the interval
given by the time window. The objective is to minimize some aspect of
operating costs (e.g. total distance traveled, number of vehicles
needed or a combination of parameters).

Since the late 80's and the beginning of the 90's optimal methods for
the {VRPTW} have appeared in the literature. Methods have basicly been
based on three approaches: dynamic programming, Lagrange relaxation
and column generation (Dantzig-Wolfe). The most successful approaches
rely on column generation. Good results have also been obtained using Lagrange relaxation.

This dissertation is divided into three parts. First the theoretical
framework is described. Thereafter a number of techniques to improve
the performance of the column-generation framework are proposed and
analyzed. Finally a parallel algorithm based on the sequential
algorithm developed in the previous part of the dissertation is
developed and analyzed."
}