Projects per year
Abstract
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:14641487, 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 cuttingplane 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 cuttingplane algorithm in a branchandbound search and introduce strong valid inequalities at the master problem level by Lagrangian relaxation. The result is a Lagrangian branchandcut andprice (LBCP) algorithm for the VRPTW. Making use of this acceleration strategy at the master problem level gives a significant speedup 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 opensource framework for solving mixedinteger linearprograms 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 branchandcut algorithm on the Solomon test problems with wide time windows. Based on results on 25node 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 50node 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 6798, 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 branchandbound framework and address acceleration strategies used to increase the efficiency of branchandprice 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.
Original language  English 

Place of Publication  Kgs. Lyngby 

Publisher  Technical University of Denmark 
Number of pages  115 
Publication status  Published  May 2006 
Fingerprint Dive into the research topics of 'On the vehicle routing problem with time windows'. Together they form a unique fingerprint.
Projects
 1 Finished

Ikkedifferentiabel optimering i heltalsprogrammering
Kallehauge, B., Madsen, O. B. G., Larsen, J., Madsen, K., Nielsen, O. A., Lübbecke, M. & Pisinger, D.
01/08/2000 → 22/05/2006
Project: PhD