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.

Den første artikel ‘Formulations and exact approaches for the vehicle routing problem with time windows’ (Kallehauge 2005, ikke publiceret) er en gennemgang af eksakte metoder udviklet gennem de seneste tre årtier til løsning af ruteplanlægningsproblemet med tidsvinduer. Der præsenteres en detaljeret analyse af formuleringerne af VRPTW, samt en gennemgang af den relevante litteratur for de forskellige formuleringer. De to hovedretninger i forskningen inden for eksakte metoder til VRPTW beskrives. En af retningerne omhandler generel dekomposition og løsning af visse duale problemer forbundet med VRPTW. En anden og nyere retning omhandler analyse af den polyhedrale struktur forbundet med VRPTW. Artiklen afsluttes med en diskussion af mulige fremtidige forskningsområder inden for VRPTW.

I den anden artikel ‘Lagrangian duality applied to the vehicle routing problem with time windows’ (Kallehauge, Larsen, and Madsen, Computers & Operations Research, 33:1464-1487, 2006) betragter vi en Lagrange relaksering af VRPTW. De restriktioner der kræver at hver kunde besøges af netop en lastbil relakseres, hvilket resulterer i et korteste vej subproblem med bibetingelser. Der præsenteres en stabiliseret snitplansalgoritme inden for rammerne af lineær programmering. Algoritmen anvendes til løsning af det Lagrange duale problem. Denne algoritme resulterer i nemmere korteste vej subproblemer, fordi færre negative kredse introduceres, og den resulterer i bedre konvergens af løsningen, fordi de duale variable stabiliseres. Vi har inkluderet den stabiliserede snitplansalgoritme i en branch-and-bound søgning og introducerer stærke gyldige uligheder i master problemet ved hjælp af Lagrange relaksering. Resultatet er en Lagrangian branch-and-cut-and-price (LBCP) algoritme til løsning af VRPTW. Benyttelsen af denne algoritme giver en signifikant forbedring af løsningstiden sammenlignet med algoritmer i litteraturen baseret på sædvanlig søjlegenerering. Vi har løst to test problemer introduceret i 2001 af Gehring og Homberger med henholdsvist 400 og 1000 kunder. Disse problemer er de til dato største problemer løst til optimalitet. Algoritmen er implementeret ved hjælp af open-source rammesystemet ABACUS, der er beregnet til løsning af heltalsproblemer ved hjælp af branch-and-cut-and-price.

I den tredje artikel ‘Path inequalities for the vehicle routing problem with time windows’ (Kallehauge, Boland, and Madsen, 2005, indsendt til publicering) præsenterer vi en ny formulering af VRPTW der kun involverer binære variable tilknyttet kanterne i en underliggende orienteret graf. Denne nye formulering er baseret på en formulering af traveling salesman problemet (TSP) med tidsvinduer og har den fordel at man undgår ekstra variable og koblende begrænsninger. I den nye formulering af VRPTW modelleres tidsvinduer ved hjælp af uligheder, der eliminerer ugyldige veje i netværket. En ugyldig vej kan skyldes overskridelse af kapacitet eller tidsbegrænsninger. Vi præsenterer en ny klasse af uligheder baseret på polyhedrale resultater opnået inden for TSP med replenishment begrænsninger. Vi bestemmer dimensionen af VRPTW polytopen. Vi beviser under visse antagelser at de nye uligheder er facetter for VRPTW polytopen. Vi introducerer også precedence begrænsinger for VRPTW. Beregningsmæssige eksperimenter udføres med en branch-and-cut algoritme. Vi betragter Solomons test problemer med brede tidsvinduer. Baseret på resultater for problemer med 25 kunder er konklusionen at algoritmen er lovende sammenlignet med førende algoritmer i litteraturen. Vi præsenterer også en løsning til et hidtil uløst problem med 50 kunder, nemlig R208. Konklusionen er derfor at korteste vej dekompositionen af VRPTW ikke længere er den absolutte vinderstrategi til løsning af VRPTW.

Den fjerde og sidste artikel ‘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) er et bidrag til en bog om søjlegenerering redigeret af G. Desaulniers, J. Desrosiers ogM.M. Solomon. Fokus for denne artikel er VRPTW som et vigtigt eksempel på anvendelse af søjlegenerering i heltalsprogrammering. Vi diskuterer VRPTW i henhold til modelleringsmæssige aspekter, problemstrukturen og dekompositionsalternativer. Derefter præsenterer vi master problemet og subproblemet ved søjlegenereringsalgoritmen. Efterfølgende beskriver vi branch-and-bound strukturen og forskellige strategier til accelerering af branch-and-price metoder. Vi beskriver generaliseringer af problemet og rapporterer beregningsmæssige resultater for de klassiske Solomon test problemer. Afslutningsvist præsenterer vi vore konklusioner og diskuterer åbne problemstillinger.