Formulations and exact algorithms for the vehicle routing problem with time windows
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 salesmen we will refer to the clover leaf problem as the -TSP, a less lucid name. If in the -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 -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 . 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 , we associate the concept of a function with a vector in . The components of the vector is denoted by . For any function and any , we denote If is introduced as a “cost function” then is called the cost of , and for any , is called the cost of . Definition 2.1 A time and capacity constrained digraph 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 .
The VRPTW polytope is the set of those satisfying the degree equationsthe subtour inequalitiesand the path inequalities
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 .
The integer solutions of (8)–(11) are exactly the incidence vectors of -routes, so it gives an integer programming formulation of the VRPTW. The class of subtour inequalities (10) have a cardinality growing exponentially with . An equivalent class of inequalities with polynomial cardinality was proposed by Tucker in 1960 [27]. He introduced node variables and proposed the inequalities
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 -arborescence in is a subset of such that forms a shortest spanning tree on rooted at node and such that for each node there is a feasible path from to . Definition 5.2 A routed arborescence, or just arborescence, in is a subset of such that is a -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 the time and capacity constrained digraph obtained from by adding the arc to the set of arcs of . For notational convenience we denote the extended set of arcs by . The cost and duration on arc 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)
Vehicle routing problem with elementary shortest path based column generation
Computers & Operations Research
(2006)- et al.
Lagrangian duality applied to the vehicle routing problem with time windows
Computers & Operations Research
(2006) - et al.
Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
Discrete Optimization
(2006) - et al.
Integer programming formulations of vehicle routing problems
European Journal of Operational Research
(1985) - et al.
Improvements and extensions to the Miller–Tucker–Zemlin subtour elimination constraints
Operations Research Letters
(1991) - et al.
The truck dispatching problem
Management Science
(1959) - Toth P, Vigo D, editors. The vehicle routing problem, SIAM monographs on discrete mathematics and applications....
- et al.
Branch-and-bound algorithms for the capacitated VRP
- et al.
Branch-and-cut algorithms for the capacitated VRP
- et al.
Set-covering-based algorithms for the capacitated VRP
VRP with time windows
VRP with backhauls
VRP with pickup and delivery
History
Solution of a large-scale traveling-salesman problems
Operations Research
A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems
SIAM Review
Optimal routing under capacity and distance restrictions
Operations Research
Combinatorial optimization, polyhedra and efficiency, algorithms and combinatorics 24
Integer and combinatorial optimization
Mathematical programming: structures and algorithms
Generalized lagrange multiplier method for solving problems of optimum allocation of resources
Operations Research
Convex analysis and minimization algorithms I-II, grundlehren der matematischen wissenschaften 304-305
The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization
Software: Practice and Experience
The traveling-salesman problem and minimum spanning trees
Operations Research
The traveling-salesman problem and minimum spanning trees: Part II
Mathematical Programming
Integer programming formulation of traveling salesman problems
Journal of the Association for Computing Machinery
A branch-and-cut procedure for the vehicle routing problem with time windows
Transportation Science
Vehicle routing with time windows: two optimization algorithms
Operations Research
The travelling salesman problem as a constrained shortest path problem: theory and computational experience
OPSEARCH
Vehicle routing with time windows
Operations Research
A new optimization algorithm for the vehicle routing problem with time windows
Operations Research
An optimization algorithm for the vehicle routing problem with time windows based on Lagrangean relaxation
Operations Research
2-path cuts for the vehicle routing problem with time windows
Transportation Science
Refinements of the column generation process for the vehicle routing problem with time windows
Journal of Systems Science and Systems Engineering
Cited by (133)
A neighborhood comprehensive learning particle swarm optimization for the vehicle routing problem with time windows
2024, Swarm and Evolutionary ComputationUpward scalable vehicle routing problem of automobile inbound logistics with pickup flexibility
2023, Transportation Research Part E: Logistics and Transportation ReviewA multi-tiered vehicle routing problem with global cross-docking
2022, Computers and Operations ResearchAn effective Progressive Hedging algorithm for the two-layers time window assignment vehicle routing problem in a stochastic environment
2021, Expert Systems with ApplicationsThe feeder-vehicle routing and high-speed-train assignment problem with time windows
2021, Research in Transportation Business and ManagementAccounting for cost heterogeneity on the demand in the context of a technician dispatching problem
2020, European Journal of Operational Research