1.3 Basic Models for the VRP

In this section we present the main mathematical programming formulations that can be used to model the basic VRPs presented in the previous section. In general, we give the models for the CVRP and discuss how they may be extended to incorporate additional constraints or different objective functions. Additional formulations can be found in Laporte and Nobert.

Three different basic modeling approaches have been proposed for the VRP in the literature. The models of the first type, known as vehicle flow formulations, use integer variables, associated with each arc or edge of the graph, which count the number of times the arc or edge is traversed by a vehicle. These are the more frequently used models for the basic versions of VRP. They are particularly suited for cases in which the cost of the solution can be expressed as the sum of the costs associated with the arcs, and when the most relevant constraints concern the direct transition between the customers within the route, so they can be effectively modeled through an appropriate definition of the arc set and of the arc costs. On the other hand, vehicle flow models cannot be used to handle many practical issues, e.g., when the cost of a solution depends on the overall vertex sequence or on the type of vehicle assigned to a route. Moreover, the linear programming relaxation of vehicle flow models can be very weak when the additional operational constraints are tight.

The second family of models is based on the so-called commodity flow formulation. In this type of model, additional integer variables are associated with the arcs or edges and represent the flow of the commodities along the paths traveled by the vehicles. Only recently have models of this type been used as a basis for the exact solution of CVRP.

The models of the last type have an exponential number of binary variables, each associated with a different feasible circuit. The VRP is then formulated as a Set-Partitioning Problem (SPP) calling for the determination of a collection of circuits with minimum cost, which serves each customer once and, possibly, satisfies additional constraints. A main advantage of this type of model is that it allows for extremely general route costs, e.g., depending on the whole sequence of the arcs and on the vehicle type. Moreover, the additional side constraints need not take into account restrictions concerning the feasibility of a single route. As a result, they often can be replaced with a compact set of inequalities. This produces a formulation whose linear programming relaxation is typically much tighter than that in the previous models. Note, however, that these models generally require dealing with a very large number of variables.

To simplify the notation, unless explicitly stated, in the following we assume that the graph G(V,A) (or G(V,E)) is complete.

1.3.1 Vehicle Flow Models

We start by describing an integer linear programming formulation for ACVRP, which is later adapted to SCVRP. The model is a two-index vehicle flow formulation that uses O(n2) binary variables ｘ to indicate if a vehicle traverse an arc in the optimal solution. In other words, variable xij takes value 1 if arc (i,j) ∈ A belongs to the optimal solution and takes value 0 otherwise.

(1.3)          

Subject to

(1.4)                                                     

(1.5)                                                     

(1.6)                                                                       

(1.7)                                                                      

(1.8)                                    

(1.9)                                                        

MACROBUTTON MTEditEquationSection2 Equation Section (Next) SEQ MTEqn \r \h \* MERGEFORMAT SEQ MTSec \h \* MERGEFORMAT MACROBUTTON MTEditEquationSection2 Equation Section (Next) SEQ MTEqn \r \h \* MERGEFORMAT SEQ MTSec \h \* MERGEFORMAT MACROBUTTON MTEditEquationSection2 Equation Chapter (Next) Section 1 SEQ MTEqn \r \h \* MERGEFORMAT SEQ MTSec \r 1 \h \* MERGEFORMAT SEQ MTChap \h \* MERGEFORMAT The indegree and outdegree constraints (1.4) and (1.5) impose that exactly one arc enters and leaves each vertex associated with a customer, respectively. Analogously, constraints (1.6) and (1.7) impose the degree requirements for the depot vertex. Note that one arbitrary constraint among the 2∣V∣ constraints (1.4)-(1.7) is actually implied by the remaining 2∣V∣-1 ones; hence it can be removed.

The so-called capacity-cut constraints (CCCs) of (1.8) impose both the connectivity of the solution and the vehicle capacity requirements. In fact, they stipulate that each cut defined by a customer set S is crossed by a number of arcs not smaller than (minimum number of vehicles needed to serve set S). The CCCs remain valid also if is replaced by trivial BPP lower bound (1.2); see, e.g.. cornuejols and Harche.

Observe that when or the CCCs (1.8) are weakened forms of the corresponding degree constraints (1.4)-(1.7), we have

(1.10)

In other words, each cutis crossed in both directions the same number of times. From (1.10) we may also restate (1.8) as

(1.11)

An alternative formulation may be obtained by transforming the CCCs (1.8), by means of the degree constraints (1.4)-(1.7), into the well-known generalized subtour elimination constraints (GSECS):

(1.12)

Which impose that at least arcs leave each customer set S.

Both families of constraints (1.8) and (1.12) have a cardinality growing exponentially with n. This means that it is practically impossible to solve directly the linear programming relaxation of problem (1.3)-(1.9).A possible way to partially overcome this drawback is to consider only a limited subset of these constraints and to add the remaining ones only if needed, by using appropriate separation procedures. The considered constraints can be relaxed in a Lagrangian fashion, as done by Fisher [18] and Miller [39] (see Chapter 2), or they can be explicitly included in the linear programming relaxation, as done in branch-and-cut approaches (see Chapter 3). Alternatively, a family of constraints equivalent to (1.8) and (1.12) and having a polynomial cardinality may be obtained by considering the subtour elimination constraints proposed for the TSP by Miller, Tucker, and Zemlin in [38] and extending them to ACVRP (see, e.g., Christofides, Mingozzi, and Toth [7] and Desrochers and Laporte [12]):

(1.13)

(1.14)

where,is an additional continuous variable representing the load of the vehicle after visiting customer i. It is easy to see that constraints (1.13)-(1.14) impose both the capacity and the connectivity requirements of ACVRP. Indeed, when xij=0, constraint (1.13) is not binding since ui≤Ｃand uｊ≥dｊ, whereas whenxij=1, they impose that ui≥ui+di. (Note that isolated subtours are eliminated as well.)

It is worth noting that the linear programming relaxation of formulation (1.3)-(1.7), (1.13), (1.14), and (1.9) generally is much weaker than that of formulation (1.3)-(1.9). Tightening constraints were proposed by Desrochers and Laporte [12].

Model VRP1 can be easily adapted to the symmetric problem. To this end it should be noted that in SCVRP the routes are not oriented (i.e., the customers along a route may be visited indifferently clockwise or counterclockwise). Therefore, it is not necessary to know in which direction edges are traversed by the vehicles, and for each undirected edge, only one of the two variables xij and xji must be used, for example, that with i<j. Note that when single-customer routes are not allowed, the edges incident to the depot can be traversed at most once. When, instead, a single-customer route is allowed for customerｊ, one may either include in the model both binary variables x0j and xj0 or use a single integer variable, which may take value {0,1,2}. In this latter case, ifx0j=2, then a route including the single customerｊis selected in the solution. In the following models, we assume that single-customer routes are allowed. The symmetric version of model VRP1 then reads

(1.15)

subject to

(1.16)

(1.17)

(1.18)

(1.19)

(1.20)

The degree constraints (1.16) and (1.17) impose that exactly two edges are incident into each vertex associated with a customer and that 2K edges are incident into the depot vertex, respectively. The CCCs (1.18) impose both the connectivity of the solution and the vehicle capacity requirements by forcing that a sufficient number of edges enter each subset of vertices. Constraints (1.10)-(1.12) may be adapted to SCVRP in a similar way.

The symmetric version of the two-index models is more frequently defined by using variables with a single index e associated with the undirected edges e ∈ E. If single-customer routes are not allowed, all used variables are binary; otherwise, if e∉ δ(0), then xe∈ {0,1}, whereas if xe∈δ(0), then xe∈ {0,1,2}.

(1.21)

subject to

(1.22)

(1.23)

(1.24)

(1.25)

(1.26)

Also in this case, due to (1.22), the CCCs (1.24) may be rewritten as the generalized subtour elimination constraints:

(1.27)

where r(S) may be replaced by the trivial BPP lower bound.

Two-index vehicle flow models have been extensively used to model the basic versions of SCVRP and ACVRP and some other variants, such as the VRPB, but they generally are inadequate for more complex versions of VRP. In fact, as mentioned, they can be used only when the cost of the solution can be expressed as the sum of the costs associated with the traversed arcs. In addition, it is not possible to directly know which vehicle traverse an arc used in the solution. Hence, these models are not suited for the cases where the cost (or the feasibility) of a circuit depends on the overall vertex sequence or on the type of vehicle allocated to the route.

A possible way to partially overcome some of the drawbacks associated with the two-index models is to explicitly indicate the vehicle that traverses an arc, so that more involved constraints may be imposed on the routes. In this way one obtains the so-called three-index vehicle flow formulation of SCVRP and ACVRP, which uses O() binary variables x: variable xijk counts the number of times arc (ｉ，ｊ) is traversed by vehicle k (k=1,…,K) in the optimal solution. In addition, there are O(nK) binary variables y: variable yik(i∈V;k=1,…,K) takes value 1 if customer i is served by vehicle k in the optimal solution and takes value 0 otherwise. The three-index model for ACVRP is given in the following.

(1.28) (VRP4)

subject to

(1.29)

(1.30)

(1.31)

(1.32)

(1.33)

(1.34)

(1.35)

Constraints (1.29)-(1.31) impose that each customer is visited exactly once, that K vehicles leave the depot, and that the same vehicle enters and leaves a given customer, respectively. Constraints (1.32) are the capacity restriction for each vehicle k, whereas constraints (1.33) impose the connectivity of the route performed by k. These latter constraints may be replaced by subtour elimination constraints (SECs) (see Fisher and Jaikumar [20]):

(1.36)

which impose that for each vehicle k at least 1 arc leaves each vertex set S visited by k and not containing the depot. Alternatively, the three-index version of the generalized Miller-Tucker-Zemlin subtour elimination constraints (1.13) can be used.

(1.37)

(1.38)

Note that these constraints replace also the capacity requirements (1.32).

The undirected version of the above model can be obtained easily by using binary variables, e∈E and k=1,…,K.

(1.39)

subject to

(1.40)

(1.41)

(1.42)

(1.43)

(1.44)

(1.45)

(1.46)

(1.47)

Three-index vehicle flow models have been extensively used to model more constrained versions of the VRP, such as the VRPTW, due to their greater flexibility in incorporating additional features (see the next section). The main drawback of these models is represented by the increased number of variables. On the other hand, they generalize the two-index models, which may be obtained by simply definingfor all or for all e∈E, thus allowing both the direct use of all the inequalities proposed for two-index models and the development of additional and stronger formulations.

1.3.2 Extensions of Vehicle Flow Models

Vehicle flow formulations, particularly the more flexible three-index ones, may be adapted to model some variants of the basic versions of SCVRP and ACVRP. In the following we discuss some of them by describing only the modifications required by the asymmetric models VRP1 and VRP4. Models VRP2, VRP3, and VRP5 can be adapted in a similar way. The adaptations required to model VRPB, VRPTW, and VRPPD are described in Chapters 7, 8, and 9, respectively.

First, we consider the case in which the graph is not complete, arising when some of the arcs are missing. This may be immediately incorporated into the considered models by defining the cost of the missing arcs as a suitably large positive value (practically equivalent to ＋∞). When the number of missing arcs is large, i.e., when |A|=m≪ , the models may be modified to take advantages of the graph sparsity by explicitly using the forward and backward stars of the vertices. As an example, model VRP1 becomes

(1.48)

subject to

(1.49)

(1.50)

(1.51)

(1.52)

(1.53)

(1.54)

A frequent modification of the models we consider is obtained by replacing the single depot vertex with K vertices, one for each available vehicle. For the asymmetric case, this is obtained by defining an extended complete degraph G’=(V’,A’), where V’:=V∪{n+1,…,n+K-1} contains K-1 additional copies of vertex 0, and the cost of each arc in A’ is defined as follows:

(1.55)

where W:={0}∪{n+1,…,n+K-1} is the set of the K vertices of G’ associated with the depot, and λ is a proper value. After this transformation, constraint (1.6) may be replaced by K constraints of type (1.4), one for each copy of the depot. Analogously, constraint (1.7) may be replaced by K constraints of type (1.5). This extension was originally proposed by Lenstra and Rinnooy Kan [35] to transform into an ordinary TSP the m-TSP, which calls for the determination of a collection of ｍ circuits visiting ｍ times a distinguished vertex (i.e., the depot) and one time each for the remaining vertices. Observe that, by appropriately defining λ,we may obtain different effects. In particular, when λ﹦Ｍ, where Ｍ is a very large positive number, the model requires use of all the Ｋ available vehicles, i.e., leads to the min-cost solution performing exactly Ｋroutes. Defining λ﹦０ leads to the min-cost solution using at most Ｋ routes, whereas definingλ﹦－Ｍ leads to the min-cost solution using routes. Different values of λ can take into account possible fixed costs associated with the use of the vehicles.

An alternative way to model the case in which some vehicles may be left unused may be obtained by replacing constraints (1.6) and (1.7) in model VRP1 with

(1.56)

(1.57)

Whereas in model VRP4 constraint (1.30) may be replaced with

(1.58)

Generally, the possibility of leaving some vehicles unused is associated with the presence of fixed costs for their use and, possibly, the additional objective requiring the minimization of the number of vehicles used, and then of the total routing costs associated with the use of vehicles. There are different ways to take this requirement into account. When considering models that impose the use of all the Ｋ available vehicles, one may first compute, by solving the BPP associated with ACVRP or SCVRP, and then define Ｋ﹦. Otherwise, the instance may be extended, as described above, by adding multiple copies of the depot and the parameter λ is set to －Ｍ.

When the model allows for the determination of solutions using a number of vehicles smaller than Ｋ, this objective may be easily included by adding a large constant value to the cost of the arcs leaving the depot. Thus, the optimal solution first minimizes the number of arcs leaving the depot (hence the number of circuits) then minimizes the cost of the other used arcs. In three-index models, where the use of each vehicle may be individually determined, the fixed costs may be different, and they can be directly included into an extended objective function rather than being added to the cost of the arcs leaving the depot.

Three-index vehicle flow models may easily take into account the case of a nonhomogeneous fleet, where each vehicle may have a different capacity Ｃk, k=1,….,K. This is obtained by replacingＣ with Ｃk in the capacity constraints (1.32).

Finally, in some cases, as in Fisher [18], routes serving a single customer are not allowed. In the models for the ACVRP, this can be imposed by adding the following additional constraints:

(1.59)

In the models for SCVRP, the infeasibility of the single customer routes can be easily imposed, as discussed in the previous section, by imposing that each variable associated with an edge incident into the depot-vertex does not take value 2. In this case, constraints (1.19) and (1.20) may be replaced by

(1.60)

It should be noted that in many practical cases the above assumption is not constraining. Indeed, customerｊcan be served alone in a route if and only if on the remaining Ｋ－１vehicles there is enough space to load the demand of the other customers, i.e., if r(V\{ｊ})≤Ｋ－１.By replacing the r(·) with the trivial BPP lower bound we may restate the above condition as

(1.61)

If，given an SCVRP (or ACVRP) instance, condition (1.61) is satisfied by no customer ｊ, then in any feasible solution no customer may be served alone in a route (hence the constraints preventing single-customer routes are superfluous).

1.3.3 Commodity Flow Models

Commodity flow models were first introduced by Garvin et al. [21] for an oil delivery problem and later extended by Gavish and Graves [23,24] to variants of TSP and VRP. These formulations, in addition to the variables used by the two-index vehicle flow formulations of section 1.3.1, require a new set of (continuous) variables, associated with the arcs, which represent the amounts of demand that flow along them. The reader is referred to Laporte and Nobert [32] for a presentation and a discussion of early commodity flow models. However, no such model was used to develop exact approaches to VRP.

Baldacci, Mingozzi, and Hadjiconstantinou [2] presented an exact approach to SCVRP, based on the extension to SCVRP of the two-commodity flow formulation for the TSP introduced by Finke, Claus, and Gunn [16]. (see also Langevin et al.[29] for an extension of the model for the TSP with Time Windows.) Since commodity flow formulations require arc orientation, we define the model on a directed graph equivalent to the undirected one.

The formulation requires the extended graph G’=(V’,A’) obtained from G by adding vertex n+1, which is a copy of the depot node, as explained in section 1.3.2. Routes are now paths from vertex 0 to vertex n+1. Two nonnegative flow variables, and are associated with each arc (ｉ,ｊ)∈Ａ’.

If a vehicle travels fromｉtoｊ,then and give the vehicle load and the vehicle residual capacity, respectively, along the arc, i.e.,﹦Ｃ－. The roles are reversed if the vehicle travels fromｊtoｉ. Therefore, the equation＋﹦Ｃ holds for each arc(ｉ,ｊ)∈Ａ＇.

For any route of a feasible solution, the flow variables define two directed paths, one from vertex 0 to n+1, whose variables represent the vehicle load, and another from vertex n+1 to vertex 0, whose variables represent the residual capacity on the vehicle. In other words, think of this as one vehicle going from 0 to n+1, leaving vertex 0 with just enough product, delivering at every customer an amount equal to its demand, and arriving empty at vertex n+1; and think of another vehicle leaving vertex n+1 empty and picking up at every customer an amount equal to its demand.