Department of Mathematical Modelling

Technical University of Denmark Building 321/305 DK-2800 Lyngby Denmark

Telephone: +45 4588 1433 Telefax : +45 4588 2673 E-mail : imm@imm.dtu.dk

Exact methods for time constrained routing and related scheduling problems

Niklas Kohl

Summary

This dissertation presents a number of optimization methods for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is a generalization of the well known capacity constrained Vehicle Routing Problem (VRP), where a fleet of vehicles based at a central depot must service a set of customers. In the VRPTW customers must be serviced within a given time period - a so called time window. The objective can be to minimize operating costs (e.g. distance travelled), fixed costs (e.g. the number of vehicles needed) or a combination of these component costs.

During the last decade optimization methods, i.e. methods quaranteeing to find a proven optimal solution, have been studied by a number of researchers. The most successful approaches until now have been the Dantzig-Wolfe decomposition (column generation) method of Desrochers, Desrosiers and Solomon (1992) and the Variable Splitting approach of J”rnsten, Madsen and S›rensen (1986), which has been tested computationally by Halse (1992). Both methods decompose the problem into a series of time and capacity constrained shotest path problems. This yields a tight lower bound on the optimal objective, and the dual gap can often be closed by branch-and-bound methods. This work is closely related to these metods. The aim is to synthesize the research as well as develop the methods further with some original contributions.

The dissertation is divided in to three parts. First, the theoretic framework is developed, and a number of methods are proposed and analyzed. Second, some of the methods are tested computationally. In the third part, generalizations of the VRPTW are considered.

In the theoretic part of the dissertation, we outline the relationship between the methods based on constrained shortest path decompositions and show that the only real difference is how the coordinating master problem - a concave non-differentiable maximization problem - is solved. We show how the constrained shortest path problem can be solved efficiently, and present a number of different strategies for solving the master problem. The lower bound obtainable can be improved further by incorporation of valid inequalities . We show how this can be done computationally and we introduce a number of valid inequalities for the VRPTW. Finally we present a number of strategies, primarily branch-and-bound, to obtain integer solutions.

In the computational part of the dissertation, we test some of the proposed methods on the well known set of benchmark problems by Solomon (1987). On basis of these experiments an optimization algorithm is constructed and executed on the benchmark problems. Of the 87 problems 70 were solved to optimality. This is to be compared to Desrochers, Desrosiers and Solomon (1992) who were able to solve 50 of the problems, and Halse (1992) who solved 33. The main reason for the success of the algorithm is the exploitation of valid inequalities. The increase in speed of computers since 1992 play only a minor role.

In the last part of the dissertation a number of generalizations of the VRPTW are considered. We discuss complex routing problems with different constraints as well as important real world scheduling problems arising in transportation companies. We show how these problems can be modelled in the same framework as the VRPTW. This means, that the methods developed can be applied to a large number of important routing and scheduling problems.

The dissertation gives a state-of-the-art review of optimization methods for the VRPTW based on constrained shortest path decompositions. It also contains a number of new theoretic results, and is the first application of valid inequalities on the VRPTW. The algorithm developed represents a major step forward in terms of computational ability to solve the VRPTW. Solutions to a large number of previously unsolved problems are reported.

IMM Ph.D Thesis 16, 1995

Last modi fied April 18, 1997

For further information, please contact, Finn Kuno Christensen, IMM, Bldg. 321, DTU
Phone: (+45) 4588 1433. Fax: (+45) 4588 2673, E-mail: fkc@imm.dtu.dk

Go back