Formulations and exact algorithms for the vehicle routing problem with time windows

https://doi.org/10.1016/j.cor.2006.11.006Get rights and content

Abstract

In this paper we review the exact algorithms proposed in the last three decades for the solution of the vehicle routing problem with time windows (VRPTW). The exact algorithms for the VRPTW are in many aspects inherited from work on the traveling salesman problem (TSP). In recognition of this fact this paper is structured relative to four seminal papers concerning the formulation and exact solution of the TSP, i.e. the arc formulation, the arc-node formulation, the spanning tree formulation, and the path formulation. We give a detailed analysis of the formulations of the VRPTW and a review of the literature related to the different formulations. There are two main lines of development in relation to the exact algorithms 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.

Introduction

In 1959, a paper by Dantzig and Ramser [1] appeared in the journal Management Science concerning the routing of a fleet of gasoline delivery trucks between a bulk terminal and a number of service stations supplied by the terminal. The distance between any two locations is given and a demand for a certain product is specified for the service stations. The problem is to assign service stations to trucks such that all station demands are satisfied and total mileage covered by the fleet is minimized. The authors imposed the additional conditions that each service station is visited by exactly one truck and that the total demand of the stations supplied by a certain truck does not exceed the capacity of the truck. The problem formulated in the paper by Dantzig and Ramser [1] was given the name ‘truck dispatching problem’. I do not know who coined the name ‘vehicle routing problem’ (VRP) for Dantzig and Ramser's problem but it caught on in the literature and is the title of the most recent book on the problem, and some of its main variants, edited by Toth and Vigo [2]. In this book, Toth and Vigo [3] considered branch and bound algorithms for the VRP, Naddef and Rinaldi [4] branch and cut algorithms for the VRP and polyhedral studies, Simchi-Levi [5] set covering based approaches for the VRP, Cordeau et al. [6] the VRP with time windows, Toth and Vigo [7] the VRP with backhauls, and Desaulniers et al. [8] the VRP with pickup and delivery. Furthermore, the book reviews heuristic approaches and issues arising in real-world applications. Now the basic variant of the VRP is often given the name ‘capacitated vehicle routing problem’ (CVRP) to distinguish it from other members of the family of VRPs. In this paper we consider the VRP with time windows (VRPTW), where each customer must be visited within a specified time interval, called a time window. We consider the case of hard time windows where a vehicle must wait if it arrives before the customer is ready for service and it is not allowed to arrive late. In the case of soft time windows a violation of the time window constraints is accepted but then a price must be paid.

Dantzig and Ramser [1] described how the VRP may be considered as a generalization of the traveling salesman problem (TSP). They described the generalization of the TSP with multiple salesmen and called this problem the ‘clover leaf problem’, a name that is the very picture of the problem. If there are m salesmen we will refer to the clover leaf problem as the m-TSP, a less lucid name. If in the m-TSP we impose the condition that specified deliveries be made at every location, excepting the start location, we get Dantzig and Ramser's problem. Obviously the VRP is identical with the m-TSP if the total demand of all locations is less than the capacity of a single vehicle. The standard reference book on the TSP was edited by Lawler et al. [9]. In this book Hoffman and Wolfe [10] describe how the importance of the TSP comes from the fact that it is typical of other problems of its genre: combinatorial optimization.

Dantzig had previously collaborated with Fulkerson and Johnson in developing an exact algorithm to the TSP. The appearance of their paper ‘Solution of a large-scale traveling-salesman problem’ [11] in the journal Operations Research was according to Hoffman and Wolfe [10] “one of the principal events in the history of combinatorial optimization”. In this paper the authors first associated with every tour a vector whose entries are indexed by the roads between the cities. An entry of this vector is 1 whenever the road between a pair of cities is traveled, otherwise it is 0. They also defined the linear equations that ensure all cities are visited exactly once in all representations of tours. These equations are called the degree constraints. Second, they defined a linear objective function that expressed the cost of a tour as the sum of road distances of successive pairs of cities in the tour. The problem is then to minimize the linear objective function such that the degree constraints are satisfied and the solution forms a tour. Third, the authors made a linear programming problem out of this integer programming problem by identifying just enough additional linear constraints on the vectors to assure that the minimum is assumed by some tour. This lead to the introduction of the subtour elimination constraints, which excludes solutions where cities are visited exactly once, but in a set of disconnected subtours. However, the authors pointed out that there are other types of constraints which sometimes must be added in addition to subtour elimination constraints in order to exclude solutions vectors involving fractional entries.

By now the approach of Dantzig et al. [11] is basic in combinatorial optimization. The approach is concerned with identifying linear inequalities or cutting planes describing the polytope defined by the convex hull of the points in the Euclidean space that represents the set of feasible solutions of the combinatorial optimization problem. No full description of the TSP polytope is known and because the TSP belongs to the class of NP-complete combinatorial optimization problems there is no hope for a polynomial-time cutting plane method for the TSP, unless NP=P. However, as Dantzig et al. [11] showed the cutting plane algorithm can still be applied to the TSP by including the TSP polytope in a larger polytope (a relaxation) over which we minimize a linear objective function. In this way the TSP is formulated as a linear program that gives a lower bound for the TSP which can be useful in a branch and bound algorithm. Padberg and Rinaldi [12] refined the integration of the enumeration approach of classical branch and bound algorithms with the polyhedral approach of cutting planes to create the solution technique called branch and cut. This method has been very successful in solving large-scale instances of the TSP and different authors have therefore applied the polyhedral approach to other hard combinatorial optimization problems. Laporte et al. [13] were the first to apply the polyhedral approach to the VRP. Finally, we note that the field of discrete mathematics where combinatorial optimization problems are formulated as linear programs is called polyhedral combinatorics and we refer to the recent work of Schrijver [14] for a detailed treatment of this subject. For a treatment of polyhedral theory we refer to Nemhauser and Wolsey [15].

Now we consider another basic method in combinatorial optimization which is concerned with the characterization of the objective function of the combinatorial optimization problem instead of its polytope. Using relaxation and duality we can determine the optimal objective function value, or at least a good lower bound on it (assuming minimization), without explicitly solving the integer problem. In particular, we are concerned with Lagrangian relaxation and duality. A related technique is Dantzig–Wolfe decomposition, which provides an equivalent bound to the Lagrangian dual bound. In Lagrangian relaxation a set of complicating constraints are dualized into the objective function by associating Lagrangian multipliers with them. This gives us an infinite family of relaxations with respect to the Lagrangian multipliers. For a given set of values of the Lagrangian multipliers the relaxed problem is called the Lagrangian subproblem. The problem of determining the largest lower bound for this family is called the Lagrangian dual problem. A fundamental result in mathematical programming is that the Dantzig–Wolfe (generalized) linear programming problem of finding a convex combination of solutions to the (Lagrangian) subproblem that also satisfy the complicating constraints is dual to the Lagrangian dual problem. The book by Shapiro [16] marked the first appearance of the term Lagrangian relaxation in a textbook. In this book the treatment of duality takes a constructive rather than existential approach to Lagrangian multipliers. Everett [17] was the first to take this constructive point of view of Lagrangian multipliers, which is different from the Karush–Kuhn–Tucker point of view of optimality involving dual variables. For a treatment of Lagrangian duality we refer to Hiriart-Urruty and Lemaréchal [18, Chapter XII]. There exist two classical algorithms for solving the Lagrangian dual problem. The simplest algorithm for the Lagrangian dual problem is the subgradient algorithm. The other classical algorithm is the cutting-plane algorithm (a row-generation algorithm), which in the primal version is the column-generation algorithm. These algorithms are convex minimization algorithms and belong to the field of non-smooth or non-differentiable optimization. For a treatment of non-smooth optimization we also refer to Hiriart-Urruty and Lemaréchal [18]. According to Thienel [19], the combination of branch and bound and column generation was by analogy to branch and cut called branch and price by Savelsbergh. Finally, when both variables and constraints are generated in the nodes of the search tree the procedure is called branch, cut, and price. In the last decade a number of frameworks for implementing branch, cut, and price has appeared, e.g. ABACUS [20], SYMPHONY [21], and BCP [22].

The use of Lagrangian relaxation in combinatorial optimization was in fact also inspired by the successful application of it to the TSP by Held and Karp [23], [24]. Lagrangian relaxation translates the problem of minimizing our objective function over a set of linear inequalities to finding the maximum of a concave piecewise affine function. There is a relationship between polyhedral combinatorics and Lagrangian relaxation. It is defined by the set of inequalities describing the convex hull of the incidence vectors of solutions to the (Lagrangian) subproblem. Held and Karp [23] proved using general linear programming theory that the maximization of the bound provided by the 1-tree Lagrangian relaxation of the TSP gives the same bound as the linear programming relaxation of the TSP proposed by Dantzig et al. [11] using the subtour inequalities. In this way the relationship between these two seminal contributions [1], [23], [24] is established, and thereby also an example of the relationship between polyhedral combinatorics and Lagrangian relaxation. If the complete set of inequalities of the subproblem was known it could be included in the integer programming problem and minimizing our objective function over the set of complicating constraints and the inequalities of the subproblem would give the Lagrangian dual value.

The methods for the VRP with time windows are in many aspects inherited from the work done for the TSP. In recognition of this fact this paper is structured relative to the four seminal papers on the TSP formulations, i.e. the arc formulation, the arc-node formulation, the spanning tree formulation, and the path formulation. We only give a detailed analysis of the formulations in this paper but we do give a full review of the literature related to the different formulations. There are two main lines of development in relation to the exact algorithms. One is concerned with the general decomposition approach and the solution to a certain dual problem associated with the primal VRPTW. Another direction is concerned with the analysis of the polyhedral structure of the VRPTW. The idea of convexity is central to both directions.

In what follows we give the complete list of references for the VRPTW relative to the four seminal papers on the TSP. We give the name of the authors of the papers concerning the TSP followed by a list of the papers on the VRPTW that consider a generalization of the approach for the TSP.

  • Arc formulation, Dantzig et al. [11], [25], [26].

  • Arc-node formulation, Miller et al. [27], [28].

  • Spanning tree formulation, Held and Karp [23], [24], [29].

  • Path formulation, Houck et al. [30], [29], [31], [32], [33], [34], [35], [36], [37], [38], [39], [40], [41], [42], [43], [44], [45], [46].

Cordeau et al. [6] and Kallehauge et al. [47] also give recent surveys in relation to the VRPTW. The survey of Kallehauge et al. [47] is given in the context of column generation in general and the focus is therefore the path formulation of the VRPTW which has been studied by several authors. These surveys also give a status on the computational success of the state of the art algorithms proposed in the literature.

The main contribution of this paper is that it provides a complete survey of all the formulations that has formed a basis for the exact solution of the VRPTW. The literature is approached from a different angle than the existing surveys and it includes new material on the polyhedral approach and a detailed treatment of the spanning tree formulation which is not available elsewhere. Finally, it contains a review of the recent developments related to the path formulation. The aim is also to provide an introduction to the field for people interested in the exact solution of the VRPTW and related resource constrained combinatorial optimization problems.

This paper is organized as follows. In Section 2 we define the VRPTW as a graph theoretic problem and introduce notation used throughout the paper. We also describe the complexity of the VRPTW and define its polytope. In Section 3 we consider the arc formulation of the VRPTW involving only binary variables associated with arcs of an underlying directed graph. In Section 4 we review the arc-node formulation of the VRPTW where we also associate variables with nodes of the directed graph. Section 5 considers a method to find lower bounds for the VRPTW, with the help of time and capacity constrained shortest spanning trees and Lagrangian relaxation. In Section 6 we consider a method to find lower bounds for the VRPTW, with the help of time and capacity constrained shortest paths and Lagrangian relaxation. Finally, in Section 7 we present some conclusions and discuss future directions of research.

Section snippets

Problem definition and notation

In this section we define the VRPTW as a graph theoretic problem and introduce notation used throughout the paper.

Given a set W, we associate the concept of a function c:WR with a vector c in RW. The components of the vector is denoted by cw. For any function c:WR and any FW, we denote c(F)=wFcw.If c is introduced as a “cost function” then cw is called the cost of w, and for any FW, c(F) is called the cost of F.

Definition 2.1

A time and capacity constrained digraph D=(V,A,c,t,a,b,d,q) is defined by a

Subtour and path inequalities

In this section we consider a formulation of the VRPTW involving only binary variables associated with the arcs in D.

The VRPTW polytope is the set of those xBA satisfying the degree equationsx(δ+(i))=1foriV*,x(δ-(i))=1foriV*,the subtour inequalitiesx(A(W))|W|-1forWV*with|W|2,and the path inequalitiesx(A(P))|A(P)|-1forPPD.

The formulation (8)–(11) of the VRPTW was proposed by Kallehauge et al. [25]. The subtour inequalities were proposed by Dantzig et al. [11] in their seminal paper on

Resource inequalities

Next we introduce a formulation of the VRPTW where we also associate variables with the nodes in D.

The integer solutions of (8)–(11) are exactly the incidence vectors of k-routes, so it gives an integer programming formulation of the VRPTW. The class of subtour inequalities (10) have a cardinality growing exponentially with n. An equivalent class of inequalities with polynomial cardinality was proposed by Tucker in 1960 [27]. He introduced node variables uZV* and proposed the inequalitiesui-uj+

Trees

In this section we consider a method to find lower bounds for the VRPTW, with the help of time and capacity constrained shortest spanning trees and Lagrangian relaxation or Dantzig–Wolfe decomposition.

Definition 5.1

A 0-arborescence in D is a subset B of A such that B forms a shortest spanning tree on V{n+1} rooted at node 0 and such that for each node vV* there is a feasible path from 0 to v.

Definition 5.2

A routed arborescence, or just arborescence, in D is a subset T of A such that Tδ-(n+1) is a 0-arborescence and

Paths

We next consider a method to find lower bounds for the VRPTW, with the help of time and capacity constrained shortest paths and Lagrangian relaxation or Dantzig–Wolfe decomposition.

Definition 6.1

We denote by D0,n+1 the time and capacity constrained digraph obtained from D by adding the arc (0,n+1) to the set of arcs A of D. For notational convenience we denote the extended set of arcs by A. The cost c0,n+1 and duration t0,n+1 on arc (0,n+1) are zero.

The elementary shortest path problem with time windows and

Conclusions

In this paper we have reviewed four different formulations of the VRPTW and the exact algorithms associated with them. We have identified and organized a total of 21 references on the VRPTW relative to four seminal papers on formulations of the TSP: arc formulation, arc-node formulation, spanning tree formulation, and path formulation. Out of these 21 references 17 references are related to the path formulation of the VRPTW. The polyhedral approach of the arc formulation is in our opinion

References (85)

  • J.F. Cordeau et al.

    VRP with time windows

  • P. Toth et al.

    VRP with backhauls

  • G. Desaulniers et al.

    VRP with pickup and delivery

  • Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB, editors. The traveling salesman problem—a guided tour of...
  • A.J. Hoffman et al.

    History

  • G. Dantzig et al.

    Solution of a large-scale traveling-salesman problems

    Operations Research

    (1954)
  • M. Padberg et al.

    A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems

    SIAM Review

    (1991)
  • G. Laporte et al.

    Optimal routing under capacity and distance restrictions

    Operations Research

    (1985)
  • A. Schrijver

    Combinatorial optimization, polyhedra and efficiency, algorithms and combinatorics 24

    (2003)
  • G.L. Nemhauser et al.

    Integer and combinatorial optimization

    (1988)
  • J.F. Shapiro

    Mathematical programming: structures and algorithms

    (1979)
  • H. Everett

    Generalized lagrange multiplier method for solving problems of optimum allocation of resources

    Operations Research

    (1963)
  • J.B. Hiriart-Urruty et al.

    Convex analysis and minimization algorithms I-II, grundlehren der matematischen wissenschaften 304-305

    (1993)
  • Thienel S, ABACUS a branch-and-cut system. PhD thesis, Mathematisch-Naturwissenschaftlichen Fakultät, Universität zu...
  • M. Jünger et al.

    The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization

    Software: Practice and Experience

    (2000)
  • Ralphs T, Guzelsoy M. The SYMPHONY callable library for mixed integer programming. Technical Report, Department of...
  • COIN/BCP User's manual....
  • M. Held et al.

    The traveling-salesman problem and minimum spanning trees

    Operations Research

    (1970)
  • M. Held et al.

    The traveling-salesman problem and minimum spanning trees: Part II

    Mathematical Programming

    (1971)
  • Kallehauge B, Boland N, Madsen OBG. Path inequalities for the vehicle routing problem with time windows. Networks...
  • Mak V, Ernst A. New cutting-planes for the time and/or precedence constrained asymmetric travelling salesman problem...
  • C.E. Miller et al.

    Integer programming formulation of traveling salesman problems

    Journal of the Association for Computing Machinery

    (1960)
  • J.F. Bard et al.

    A branch-and-cut procedure for the vehicle routing problem with time windows

    Transportation Science

    (2002)
  • M.L. Fisher et al.

    Vehicle routing with time windows: two optimization algorithms

    Operations Research

    (1997)
  • D.J. Houck et al.

    The travelling salesman problem as a constrained shortest path problem: theory and computational experience

    OPSEARCH

    (1980)
  • A.W.J. Kolen et al.

    Vehicle routing with time windows

    Operations Research

    (1987)
  • M. Desrochers et al.

    A new optimization algorithm for the vehicle routing problem with time windows

    Operations Research

    (1992)
  • Halse K, Modeling and solving complex vehicle routing problems. PhD thesis, Department of Mathematical Statistics and...
  • N. Kohl et al.

    An optimization algorithm for the vehicle routing problem with time windows based on Lagrangean relaxation

    Operations Research

    (1997)
  • N. Kohl et al.

    2-path cuts for the vehicle routing problem with time windows

    Transportation Science

    (1999)
  • Larsen J, Parallelization of the vehicle routing problem with time windows. PhD thesis, Department of Mathematical...
  • J. Larsen

    Refinements of the column generation process for the vehicle routing problem with time windows

    Journal of Systems Science and Systems Engineering

    (2004)
  • Cited by (133)

    • Upward scalable vehicle routing problem of automobile inbound logistics with pickup flexibility

      2023, Transportation Research Part E: Logistics and Transportation Review
    • The feeder-vehicle routing and high-speed-train assignment problem with time windows

      2021, Research in Transportation Business and Management
    View all citing articles on Scopus
    View full text