On the vehicle routing problem with time windows

The vehicle routing problem with time windows is concerned with the optimal routing of a fleet of vehicles between a depot and a number of customers that must be visited within a specified time interval, called a time window. The purpose of this thesis is to develop new and efficient solution techniques for solving the vehicle routing problem with time windows (VRPTW). The thesis consists of a section of introductory remarks and four independent papers.

The first paper ‘Formulations and exact approaches for the vehicle routing problem with time windows’ (Kallehauge, 2005, unpublished) is a review of the exact algorithms proposed in the last three decades for the solution of the vehicle routing problem with time windows. A detailed analysis of the formulations of the VRPTW is presented together with a review of the literature related to the different formulations. We present the two main lines of development in relation to the exact approaches for the VRPTW. One is concerned with the general decomposition approach and the solution to certain dual problems associated with the VRPTW. Another more recent direction is concerned with the analysis of the polyhedral structure of the VRPTW. We conclude by examining possible future lines of research in the area of the VRPTW.

In the second paper ‘Lagrangian duality applied to the vehicle routing problem with time windows’ (Kallehauge, Larsen, and Madsen, Computers & Operations Research, 33:1464-1487, 2006) we consider the Lagrangian relaxation of the constraint set requiring that each customer must be served by exactly one vehicle yielding a constrained shortest path subproblem. We present a stabilized cutting-plane algorithm within the framework of linear programming for solving the associated Lagrangian dual problem. This algorithm creates easier constrained shortest path subproblems because less negative cycles are introduced and it leads to faster multiplier convergence due to a stabilization of the dual variables. We have embedded the stabilized cutting-plane algorithm in a branch-and-bound search and introduce strong valid inequalities at the master problem level by Lagrangian relaxation. The result is a Lagrangian branch-andcut- and-price (LBCP) algorithm for the VRPTW. Making use of this acceleration strategy at the master problem level gives a significant speed-up compared to algorithms in the literature based on traditional column generation. We have solved two test problems introduced in 2001 by Gehring and Homberger with 400 and 1000 customers respectively, which to date are the largest problems ever solved to optimality. We have implemented the LBCP algorithm using the ABACUS open-source framework for solving mixed-integer linear-programs by branch, cut, and price.

In the third paper ‘Path inequalities for the vehicle routing problem with time windows’ (Kallehauge, Boland, and Madsen, 2005, submitted) we introduce a new formulation of the VRPTW involving only binary variables associated with the arcs in the underlying digraph. The new formulation is based on a formulation of the asymmetric traveling salesman problem with time windows and has the advantage of avoiding additional variables and linking constraints. In the new formulation of the VRPTW time windows aremodeled using path inequalities. The path inequalities eliminate time and capacity infeasible paths. We present a new class of strengthened path inequalities based on polyhedral results obtained in the context of the asymmetric traveling salesman problem with replenishment arcs. We study the VRPTW polytope and determine the polytope dimension. We show that the lifted path inequalities are facet defining under certain assumptions. We also introduce precedence constraints in the context of the VRPTW. Computational experiments are performed with a branch-and-cut algorithm on the Solomon test problems with wide time windows. Based on results on 25-node problems the outcome is that the algorithmshows promising results compared to leading algorithms in the literature. In particularwe report a solution to a previously unsolved 50-node Solomon test problem R208. The conclusion is therefore that the path formulation of the VRPTW is no longer the unchallenged winning strategy for solving the VRPTW.

The fourth and final paper ‘Vehicle routing problem with time windows’ (Kallehauge, Larsen, Madsen, and Solomon. In Desaulniers, Desrosiers, and Solomon, editors, Column generation, pages 67-98, Springer, New York, 2005) is a contribution to a book on column generation edited by G. Desaulniers, J. Desrosiers, and M. M. Solomon. The focus of the paper is on the VRPTW as one of the important applications of column generation in integer programming. We discuss the VRPTW in terms of its mathematical modeling, its structure and decomposition alternatives. We then present the master problem and the subproblemfor the column generation approach, respectively. Next, we illustrate a branch-and-bound framework and address acceleration strategies used to increase the efficiency of branch-and-price methods. Then, we describe generalizations of the problem and report computational results for the classic Solomon test sets. Finally, we present our conclusions and discuss some open problems.