Keywords

1 Introduction

Combined location-routing problems (LRPs) are location problems where the service to customers is provided by a fleet of vehicles in less-than-truckload routes. That is, more than one customer can be served in one vehicle route from a facility. Therefore, the cost of servicing a customer in a solution of a location-routing problem does not only depend on the facility it is assigned to, but also on the route followed by the vehicle that services it. As happens with pure vehicle routing problems, a basic distinction needs to be made when referring to LRPs, depending on whether the customers are associated with nodes or links of the underlying network. In the first case, in order to provide service to a customer, a vehicle has to visit the corresponding node, whereas in the second case, the vehicle has to traverse the corresponding link. Most of the literature on LRPs is in fact devoted to node routing LRPs and only a few references are concerned with solving some variant with arc routing. For this reason, the name location-routing problem is commonly used to refer to problems where customers are located at the nodes, whereas the term location-arc routing problem (LARP) is used when customers are located on the links of the network. In both cases, the need to design vehicle routes to evaluate the cost of a set of facilities adds an extra level of difficulty to these problems which are, in general, \(\mathcal{N}\mathcal{P}\)-hard.

The first works addressing LRPs date back to the 1960s (e.g. Von Boventer 1961 and Maranzana 1964). However, it was not until the end of the 1980s, when a solid knowledge on both pure location and routing problems was achieved, that location-routing became a really active field of research. The most common approach in the first references addressing this type of problems was to make locational and routing decisions in two separate steps, although it is well-known that this is most likely to yield suboptimal solutions, as shown in Salhi and Rand (1989). For this reason, more recent references address both decisions simultaneously.

LRPs arise as a natural extension of both, location and vehicle routing problems. Moreover, there are several settings where LRPs appear naturally. For example, Schittekat and Sörensen (2009) study the optimization problem arising in some automotive companies that use third-party logistics partners for the distribution of spare parts and model it as a large scale LRP. Other examples of real applications where extensions of the LRP need to be solved are given in Ahn et al. (2012), where the authors present a LRP with profits faced by NASA while planning planetary surface exploration, or in Samanlioglu (2013) where hazardous waste management of a Turkish region is dealt with by solving a multiobjective LRP.

Although there exist papers dealing with planar LRPs (see, for instance, Manzour-al-Ajdad et al. 2012 or Salhi and Nagy 2009), most of the studies concerning LRPs deal with discrete location problems. As a consequence, this chapter will only consider this type of LRPs. Moreover, it does not pretend to be a complete survey of all works in the literature addressing discrete LRPs, and only presents the state of the art methods and the tools that have proven to be the most suitable ones to tackle LRPs. For a complete recent survey on works concerned with LRPs the reader is referred to Prodhon and Prins (2014). The reader can also find a taxonomy of location-routing models and the related literature in Borges Lopes et al. (2013). Earlier works are surveyed in Nagy and Salhi (2007). Given the little attention that LARPs have received, this chapter is also mostly concentrated on LRPs with node routing, and the most relevant issues concerning LARPs are gathered in a single section.

The remainder of this chapter is organized as follows. Section 15.2 provides a formal definition of the considered problems, together with the notation that will be used throughout the chapter. The next two sections describe the main scientific contributions on LRPs; Sect. 15.3 explores the different types of LRP formulations, together with the most relevant valid inequalities used in exact methods, whereas Sect. 15.4 is concerned with heuristic algorithms. The main findings regarding LARPs are outlined in Sect. 15.5, and 15.6 concludes the chapter.

2 Problem Definition and Notation

Let J be a set of customers and I a set of locations where facilities can be placed. For each candidate location i ∈ I, let f i be the cost of setting up a facility at i, and for each arc (i, j) with \(i,j \in I \cup J\), let ℓ ij be its length or cost. The basic variant of the LRP consists of choosing a set of locations from I and defining closed routes starting and ending at one of these facilities such that each customer is visited by exactly one of the routes, subject to side constraints. The goal is to minimize the total cost, which typically includes the sum of facility set-up costs plus a traveling cost. We also denote by G the underlying graph of an LRP instance formed by the set of vertices \(V = I \cup J\) and the set of links \(E = E_{\mathit{IJ}} \cup E_{I}\), where E IJ contains all links connecting one facility with one customer, and E J contains all links connecting two different customers. In what follows, both, directed and undirected formulations will be presented. For ease of notation, E will be used indistinctly to denote the set of (directed) arcs (i, j) or the set of (undirected) edges {i, j}. For any set of nodes S ⊆ V, E S will denote the set of links with both endpoints in S.

If a weight w j is associated with each customer j ∈ J, capacity constraints can be considered by imposing a maximum weight Q delivered by a vehicle or a maximum weight q i delivered from each facility i ∈ I. From now on, Q will be referred to as the vehicle capacity, and q j as the facility capacity and, for each set of customers S ⊆ J, w(S) will denote the total weight of customers in S: \(w(S) =\sum \nolimits _{j\in S}w_{j}\). LRPs considering either type of constraint, or both of them, are referred to as Capacitated LRPs (CLRPs). Additionally, many papers consider fixed vehicle utilization costs, g, and a limited size fleet indexed in set K. Figure 15.1 depicts an LRP solution.

Fig. 15.1
figure 1

Example of an LRP solution

Full size image

Further considerations and characteristics of the main elements of the problem (number of facilities to locate, types of customers, size and characteristics of the vehicle fleet, time horizon, etc.) give rise to a large variety of LRPs. A comprehensive recent classification, following the ideas already presented in Laporte (1988) can be found in Borges Lopes et al. (2013).

The main difficulty when modeling LRPs through mathematical programming formulations is to ensure that each vehicle tour is connected to exactly one facility; that is, there are no closed tours visiting only customers, and there are no paths connecting two different facilities. Therefore, incorporating the design of vehicle routes within facility location problems entails a relevant additional level of difficulty. Furthermore, as some authors argue, facility location is most often a strategic decision, while vehicle routing is operational. These facts have discouraged many researchers from considering combined LRPs. However, although routing decisions can be readjusted relatively often once the facilities are established, the possible configurations of the routes are strongly conditioned by these locations. Therefore, if locations are chosen without taking into account the routing component of the final system, initial savings in the facilities set up costs may not compensate for large losses in distribution in the long run. Consider, for instance, the extreme situation depicted in Fig. 15.2.

Fig. 15.2
figure 2

Influence of facility location on the routing costs

Full size image

In this example, assume that the capacity of any of the two candidate facilities (black squares) is sufficient to serve all customers (white circles), and there is only one vehicle available at each location, also with a large enough capacity. If one single location is to be chosen and routing costs are ignored (i.e. if an uncapacitated facility location problem is considered in this setting) obviously, the facility will be located at 2. However, if a tour needs to be defined to serve all the customers once this facility is set, its cost will be \(2M + (11\pi M)/6 \simeq 7.76M\). On the other hand, if the facility is set at node 1, a better route, with cost \(2\pi M \simeq 6.28M\) can be defined. Since distribution is most often a repetitive activity, this extra routing cost for having chosen facility location 2 will be incurred regularly and, after some time, these accumulated extra costs can be larger than the initial possible savings in set up costs.

3 Formulations and Exact Algorithms

The available exact algorithms for solving LRPs rely on mathematical programming formulations of the problem. Most of these formulations have been developed around the existing formulations for discrete facility location problems and multi-depot vehicle routing problems. Since the early formulations of Golden et al. (1977) and of Perl and Daskin (1985), several LRP formulations have been studied. CLRPs have received particular attention, since they are amongst the most basic LRPs. This section will concentrate on these problems.

As mentioned above, the main difficulty when developing a formulation for an LRP model is to guarantee that each route will start and end at one facility and neither closed loops visiting only customers, nor paths connecting two different facilities will be formed. For this reason, to a large extent, the developments concerning formulations for LRP models are strongly related with the literature on capacitated vehicle routing problems, especially, on multi-depots problems. As happens in these problems, one can assume, without loss of generality, that an optimal solution exists in which no edge of E I is used more than twice and the only edges used twice, if any, belong to E IJ . This is actually the case of problem instances in which the edge lengths satisfy the triangle inequality. Any instance can in fact be easily transformed into an equivalent one satisfying this property, by replacing the actual length of each edge with the length of a shortest path connecting its endpoints.

Broadly speaking, the existing formulations for the LRP can be classified in either of two families. On the one hand, one can find the so-called flow formulations, where different sets of variables are used to determine the set of located facilities and to describe the vehicle routes. On the other hand, one can find set covering formulations, where one single variable is defined associated with each feasible vehicle route. To a large extent, the appropriate solution method depends on the formulation employed; while branch-and-cut approaches are the most suitable for flow formulations, set covering formulations are in general better suited for algorithms based on column generation. The most recently presented algorithms combine column generation and cut generation methods.

3.1 Flow Formulations

Within the flow formulations, different models can be distinguished according to two criteria: the number of indices of the variables used to define the vehicle routes (including or not a third index to identify which vehicle uses a given link), and the nature of these variables, known as commodity flow variables when they consider the quantity of goods traveling on every link and as vehicle flow variables when they only indicate whether it is used or not.

An early example of a three-index vehicle flow formulation is that of Perl and Daskin (1985). In fact, this reference defines a three-layer problem with suppliers, distribution centers and customers where, in addition to the characteristics of the basic LRP, the authors consider variable costs associated with the throughput at each distribution center, and extra constraints limiting the length of the routes. The proposed formulation, simplified by excluding these extra considerations, is described next. To this end, the following binary variables will be used:

  • For each i ∈ I, y i indicates whether a facility is established at i.

  • For each i ∈ I, j ∈ J, x ij indicates whether customer j is served from facility i

  • For each (i, j) ∈ E and k ∈ K, z ijk indicates whether vehicle k uses arc (i, j).

Using the above variables, a three index vehicle flow formulation for the LRP is detailed next:

$$\displaystyle{ \text{(LRP1)}\ \text{minimize }\sum \limits _{i\in I}f_{i}y_{i} +\sum \limits _{k\in K}\sum \limits _{(i,j)\in E}\ell_{\mathit{ij}}z_{\mathit{ijk}}\qquad }$$
(15.1)
$$\displaystyle{ \text{subject to}\sum \limits _{k\in K}\sum \limits _{i\in V }z_{\mathit{ijk}} = 1\qquad \qquad \quad j \in J }$$
(15.2)
$$\displaystyle{ \sum \limits _{j\in J}w_{j}\sum \limits _{i\in V }z_{\mathit{ijk}} \leq Q\qquad \qquad \quad k \in K }$$
(15.3)
$$\displaystyle{ \sum \limits _{j\in J}w_{j}x_{\mathit{ij}} - q_{i}y_{i} \leq 0\qquad \qquad \quad i \in I }$$
(15.4)
$$\displaystyle{ \sum \limits _{k\in K}\sum \limits _{i\in S}\sum \limits _{j\in V \setminus S}z_{\mathit{ijk}} \geq 1\qquad \qquad \quad I \subseteq S \subset V }$$
(15.5)
$$\displaystyle{ \sum \limits _{j\in V }z_{\mathit{ijk}} -\sum \limits _{j\in V }z_{\mathit{jik}} = 0\qquad \qquad \quad k \in K,i \in V }$$
(15.6)
$$\displaystyle{ \sum \limits _{i\in I}\sum \limits _{j\in J}x_{\mathit{ijk}} \leq 1\qquad \qquad \quad k \in K }$$
(15.7)
$$\displaystyle{ \sum \limits _{t\in J}z_{\mathit{itk}} +\sum \limits _{t\in V }z_{\mathit{jtk}} - x_{\mathit{ij}} \leq 1\qquad \quad i \in I,j \in J,k \in K }$$
(15.8)
$$\displaystyle{ y_{i} \in \{ 0,1\}\qquad \qquad \quad i \in I }$$
(15.9)
$$\displaystyle{ x_{\mathit{ij}} \in \{ 0,1\}\qquad \qquad \quad i \in I, j \in J }$$
(15.10)
$$\displaystyle{ z_{\mathit{ijk}} \in \{ 0,1\}\qquad \qquad \quad(i,j) \in E, k \in K. }$$
(15.11)

Constraints (15.2) mean that each customer is reached by one vehicle route, while constraints (15.3) and (15.4) are vehicle and plant capacity constraints, respectively. Additionally, constraints (15.4) guarantee that customers will be served from opened facilities. Connectivity constraints (15.5) ensure that each vehicle route includes a facility, while flow conservation constraints (15.6) ensure that z variables do indeed define routes, and constraints (15.7) mean that these routes visit one single facility. Finally, constraints (15.8) force the x and z variables to take consistent values.

Formulations of this type tend to be rather large, on the one hand, because they have an exponential number of connectivity constraints and, on the other hand, because they have O( | V | 3) variables. Connectivity constraints, as well as additional valid inequalities, have traditionally been dealt with by using cutting plane procedures, such as branch-and-cut. However, even after relaxing connectivity constraints, the size of the formulations remains too large for solving realistic size instances.

As an alternative, several authors have worked on formulations where vehicle flow variables z do not include the third index to identify which vehicle uses each arc. In fact, early works addressing the particular cases of the LRP with one single depot or one single route per depot, such as Laporte and Nobert (1981) or Laporte et al. (1983) already used this type of approach.

A very successful example of this type of formulations is presented in Belenguer et al. (2011). In this case, the authors propose an undirected formulation that uses the following variables:

  • For each i ∈ I, y i indicates whether a facility is established at i.

  • For each edge {i, j} ∈ E, \(z_{\mathit{ij}}^{1}\) indicates whether edge {i, j} is used exactly once in the solution.

  • For each edge {i, j} ∈ E IJ , z ij 2 indicates whether edge {i, j} is used twice in the solution.

Note that, as mentioned above, it can be assumed that the only edges that can be traversed twice in an optimal solution belong to E IJ and, therefore, variables z 2 are only defined for those edges.

Additionally to the above variables, the following notation is used. For each set of customers S ⊆ J, κ(S) is a lower bound on the minimum number of vehicles needed to serve the aggregate demand of all customers in set S. The most commonly used bound in this type of formulations is

$$\displaystyle{\kappa _{1}(S) = \left \lceil \frac{1} {Q}\sum \limits _{j\in S}w_{j}\right \rceil.}$$

However, instead of κ 1(S) some authors have used the optimal value of the bin packing problem defined by the weights of the customers in S, and bin size equal to the vehicle capacity, Q. In what follows, this second bound will be referred to as κ 2(S).

The formulation proposed in Belenguer et al. (2011) is

$$\displaystyle{ \text{(LRP2)}\ \text{minimize }\sum \limits _{i\in I}f_{i}y_{i} +\sum \limits _{\{i,j\}\in E}\ell_{\mathit{ij}}z_{\mathit{ij}}^{1} +\sum \limits _{\{ i,j\}\in E_{\mathit{IJ}}}2\ell_{\mathit{ij}}z_{\mathit{ij}}^{2}\quad }$$
(15.12)
$$\displaystyle{ \text{subject to}\sum \limits _{i\in I}2z_{\mathit{ij}}^{2} +\sum \limits _{ i\in V \setminus \{j\}}z_{\mathit{ij}}^{1} = 2\qquad \qquad \quad j \in J }$$
(15.13)
$$\displaystyle{ z_{\mathit{ij}}^{1} + z_{\mathit{ ij}}^{2} \leq y_{ i}\qquad \qquad \quad i \in I,j \in J }$$
(15.14)
$$\displaystyle{ \sum \limits _{i,j\in S}z_{\mathit{ij}}^{1} \leq \vert S\vert -\kappa (S)\qquad \qquad \quad S \subseteq J }$$
(15.15)
$$\displaystyle{ \sum \limits _{s\in S}\sum \limits _{j\in J\setminus S}z_{sj}^{1} +\sum \limits _{ t\in I\setminus \{i\}}\sum \limits _{s\in S}(z_{ts}^{1} + 2z_{ ts}^{2}) \geq 2\qquad \quad i \in I,S \subset J;w(S) > q_{ i} }$$
(15.16)
$$\displaystyle\begin{array}{rcl} & & z_{jt}^{1} +\sum \limits _{ s\in S}(z_{sj}^{1} + z_{\mathit{ st}}^{1}) +\sum \limits _{ s,u\in S}z_{su}^{1} \\ & & \qquad +\sum \limits _{i\in I^{{\prime}}}z_{\mathit{ij}}^{1} +\sum \limits _{ i\in I\setminus I^{{\prime}}}z_{\mathit{it}}^{1} \leq \vert S\vert + 2\qquad \qquad \quad S\,\subset \,J,I^{{\prime}}\,\subset \,I;j,t\,\in \,J\,\setminus \,S{}\end{array}$$
(15.17)
$$\displaystyle{ \sum \limits _{i\in I}(z_{\mathit{ij}}^{1} + z_{\mathit{ ij}}^{2}) \leq 1\qquad \qquad \quad j \in J }$$
(15.18)
$$\displaystyle{ y_{i} \in \{ 0,1\}\qquad \qquad \qquad \quad i \in I }$$
(15.19)
$$\displaystyle{ z_{\mathit{ij}}^{1} \in \{ 0,1\}\qquad \qquad \qquad \quad \{i,j\} \in E }$$
(15.20)
$$\displaystyle{ z_{\mathit{ij}}^{2} \in \{ 0,1\}\qquad \qquad \qquad \quad \{i,j\} \in E_{\mathit{ IJ}}. }$$
(15.21)

The original formulation includes an extra term in the objective function to account for fixed costs for the use of vehicles. Although this term has not been included here, these costs can be easily included in the above formulation by suitably modifying the lengths ℓ ij for each {i, j} ∈ E IJ .

In this formulation, constraints (15.13) are the degree constraints, which force each customer to be visited by some route. Constraints (15.14) are imposed in order to ensure that no route is rooted at a closed facility. Constraints (15.15) play two major roles. On the one hand, they forbid solutions with subtours which are not linked to any facility. On the other hand, they ensure that the vehicle capacities are not exceeded. Note that only z 1 variables are involved in these constraints since each z 2 variable is associated with one complete facility-customer-facility tour, which will not violate the vehicle capacity constraints in any feasible LRP instance. Facility capacities are imposed through constraints (15.16): if a set of customers S cannot be fully served from a given facility i because of its capacity, then at least one customer in S must be visited by a vehicle route rooted at a different facility and, therefore, at least two edges must be used that link set S with customers outside it, or to some facility different from i. Additionally, since individual routes are not identified using 2-index variables, it is necessary to explicitly forbid tours connecting two different facilities. This is done by means of the so-called path elimination constraints (15.17). Additional constraints (15.18) are needed to forbid paths connecting two facilities through one single customer. The path elimination constraints are similar to the chain-barring constraints introduced by Laporte et al. (1988).

Using this formulation enriched with some families of valid inequalities, Belenguer et al. (2011) were able to solve within less than 2 h instances of up to 50 customers and five potential facilities.

3.2 Set-Partitioning Formulations

Set partitioning formulations for the LRP were introduced much later than flow formulations. Indeed, papers addressing this type of formulations have appeared relatively recently, in parallel with similar formulations for vehicle routing problems. The first such formulation was presented in Berger et al. (2007); the slightly different formulation presented in Akca et al. (2009) was later used in Baldacci et al. (2011) and further strengthened by Contardo et al. (2014a).

In order to present this type of formulations, some extra notation is required. Variables now correspond to the possible vehicle routes that are feasible with respect to the vehicle capacity and serve more than one customer. These routes will be indexed in \(\varGamma = \cup _{i\in I}\varGamma _{i}\), where Γ i gathers the routes starting from facility i. The return trips from a facility to a single customer will be dealt with separately. For each route r ∈ Γ, we will denote by ℓ r the total length of the route, by w r its total demand and, for each edge {i, j} ∈ E, the coefficient a ijr will denote the number of times edge {i, j} is used in route r. Note that coefficients a ijr are binary if route r is elementary, but can take larger values if non-elementary routes are allowed.

The formulation exploited by Contardo et al. (2014a) uses the following binary variables:

  • For each i ∈ I, y i indicates whether a facility is established at i.

  • For each i ∈ I and j ∈ J, z ij 2 indicates whether a return trip from facility i to customer j is part of the solution.

  • For each route r ∈ Γ, λ r indicates whether route r is used.

$$\displaystyle{ \text{(LRP3)}\ \text{minimize }\sum \limits _{i\in I}f_{i}y_{i} +\sum \limits _{r\in \varGamma }\ell_{r}\lambda _{r} +\sum \limits _{\{i,j\}\in E_{\mathit{IJ}}}2\ell_{\mathit{ij}}z_{\mathit{ij}}^{2}\quad }$$
(15.22)
$$\displaystyle{ \text{subject to}\sum \limits _{r\in \varGamma }\sum \limits _{i\in V }a_{\mathit{ijr}}\lambda _{r} +\sum \limits _{i\in I}2z_{\mathit{ij}}^{2} = 2\qquad \qquad \quad j \in J }$$
(15.23)
$$\displaystyle{ \sum \limits _{r\in \varGamma _{i}}\sum \limits _{\{j,s\}\in E}(w_{j} + w_{s})a_{\mathit{jsr}}\lambda _{r} +\sum \limits _{j\in J}2w_{j}z_{\mathit{ij}}^{2} \leq 2q_{ i}y_{i}\qquad i \in I }$$
(15.24)
$$\displaystyle{ y_{i} \in \{ 0,1\}\qquad \qquad \quad i \in I }$$
(15.25)
$$\displaystyle{ z_{\mathit{ij}}^{2} \in \{ 0,1\}\qquad \qquad \quad \{i,j\} \in E }$$
(15.26)
$$\displaystyle{ \lambda _{r} \in \{ 0,1\}\qquad \qquad \quad r \in \varGamma. }$$
(15.27)

Here, constraints (15.23) ensure that each customer is either visited once by one of the selected routes, or in a round trip from a facility. Facility capacities are stated by constraints (15.24). For ease of notation, in these constraints, an artificial demand w i  = 0 is defined for each facility i.

Of course, in order to take advantage of this formulation it is essential to use a method based on column generation since the number of λ variables is exponential. Therefore, a crucial issue when developing exact solution methods based upon this formulation is the pricing problem. Here, the pricing problem consists of finding negative cost vehicle routes in Γ. It belongs to the family of resource constrained shortest path problems, which have been the focus of an abundant literature, mostly because they appear as pricing problems in many column generation algorithms where vehicle routes are involved (see, for instance, Desrochers et al. 1992; Feillet et al. 2007; Righini and Salani 2008).

In Contardo et al. (2014a), which has been the most successful work so far, the authors allow for solutions that contain cycles, as long as they contain at least three nodes. For this case, to guarantee that even if Γ contains non-elementary routes, these routes will not be part of a solution of LRP3, the authors replace the degree constraints (15.23) by their following stronger variant, the strengthened degree constraints:

$$\displaystyle{ \sum \limits _{r\in \varGamma }\sum \limits _{k:\{j,k\}\in E}a_{jkr}\lambda _{r} +\sum \limits _{i\in I}z_{\mathit{ij}}^{2} \geq 1\quad j \in J. }$$
(15.28)

On top of the efficiency of the algorithm used in the pricing problem, most set partitioning based exact algorithms for the LRP also rely on the addition of valid inequalities to tighten the bounds obtained during the branching process. In particular, Baldacci et al. (2011) proved that all valid inequalities developed for flow formulations can be transformed into valid inequalities for the set partitioning formulation presented above, since, thanks to the distinction between routes visiting one or more customers made in the variables definition, the following equalities hold:

$$\displaystyle{ z_{\mathit{ij}}^{1} =\sum \limits _{ r\in \varGamma }a_{\mathit{ijr}}\lambda _{r}\qquad \forall \{i,j\} \in E. }$$
(15.29)

Additionally to this equivalence, when adapting valid inequalities originally stated for flow formulations to set-partitioning formulations, some authors have used the following result, first established in Laporte et al. (1985) in the context of vehicle routing problems. Many of the valid inequalities derived for two-index formulations for vehicle routing problems are concerned with a combination of connectivity and capacity issues. In these cases, arguments of the type “at least κ vehicles are needed to satisfy the demand of all customers in S ⊂ J” result in constraints of the form “the border of S is crossed, at least, 2κ times”, that is, the sum of flows on edges with a single endpoint in S must be at least 2κ. In these constraints, the number of routes visiting S is overestimated using the flow in the cut-set of S, since there is no way to compute the exact number of routes that visit S using the flow variables. When equivalence (15.29) is used to derive valid inequalities for LRP3 from these valid inequalities, the coefficient of each λ r variable for a given set S is the number of times route r traverses the border of S. Bearing in mind the rationale behind the constraints, one can see that, actually, these coefficients can be changed to take value 2 if route r visits at least one customer in S, and 0 otherwise. In general, this results in stronger valid inequalities.

3.3 Valid Inequalities

It is impractical to list all the valid inequalities that have been more or less successfully used for LRPs. Actually, most of the valid inequalities that have been developed for vehicle routing problems have been adapted later for the case of LRPs and in many cases, families of inequalities have been gradually strengthened or extended. In what follows, we present a selection of the most recent families. For more detailed information on these cuts and their evolution, the reader is referred to Belenguer et al. (2011) and Contardo et al. (2013) for flow formulations, and to Baldacci et al. (2011) and Contardo et al. (2014a) for set partitioning formulations.

3.3.1 y-Strengthened Capacity Cuts (y-SCC)

For S ⊂ J, and a route r ∈ Γ, let the binary parameter ξ rS take value 1 if route r visits at least one customer in S, and 0 otherwise. Given S ′ ⊂ S such that \(\kappa _{1}(S^{{\prime}}) =\kappa _{1}(S)\), the following inequalities are valid:

$$\displaystyle{\sum \limits _{r\in \varGamma }\xi _{rS}\lambda _{r} +\sum \limits _{i\in I}\sum \limits _{j\in S\setminus S^{{\prime}}}z_{\mathit{ij}}^{2} \geq \kappa _{ 1}(S).}$$

This family of constraints is a strengthening proposed in Contardo et al. (2014a) of the previous y-Capacity Cuts derived in Belenguer et al. (2011).

3.3.2 Set Partitioning Effective Strengthened Facility Capacity Inequalities (SP-ESFCI)

As mentioned above, the main difficulty when modeling vehicle routes is to ensure the connectivity of the solutions, especially in capacitated problems. When locational decisions must also be made, ensuring connectivity and capacity satisfaction entails an extra degree of complexity. Most of the known valid inequalities focus on vehicle capacities and rarely take facility capacities into account. SP-ESFCI aim at putting facility capacity constraints in relation with the locational variables.

To this end, we need to extend the definition of κ 1 to take into account a set of facilities. Given a set of customers S ⊂ J and a set of facilities H ⊂ I, we define \(\kappa _{1}(S,H) =\max \left \{0,\left \lceil \frac{w(S)-\sum \nolimits _{i\in H}q_{i}} {Q} \right \rceil \right \}\) as a lower bound on the number of vehicle routes rooted at facilities outside H, needed to serve all customers in S, even if all facilities in H provided their service to customers in S. Then, for S ′ ⊂ S ⊂ J, and i ∈ H ⊂ I with \(\kappa _{1}(S\setminus S^{{\prime}},H) =\kappa _{1}(S,H)\), the following inequality is valid:

$$\displaystyle{ \sum \limits _{i\in I\setminus H}\sum \limits _{r\in \varGamma _{i}}\xi _{rS}\lambda _{r} +\sum \limits _{i\in I\setminus H}\sum \limits _{j\in S\setminus S^{{\prime}}}z_{\mathit{ij}}^{2} \geq \kappa _{ 1}(S,H\!\setminus \!\{i\}) + y_{i}\Big(\kappa _{1}(S,H) -\kappa _{1}(S,H\!\setminus \!\{i\})\Big). }$$
(15.30)

The main idea behind these constraints is similar to that of the y-SCC inequalities, but now, the constraint takes two different shapes depending on whether facility i is opened or not.

3.3.3 Strengthened Framed Capacity Inequalities (SFrCI)

Moving back to vehicle capacities, we find the following valid inequalities, which have been successively improved since some early papers on vehicle routing.

Given a subset of customers S ⊂ J, partitioned into disjoint subsets \(\mathcal{S} =\{ S_{1},\ldots,S_{t}\}\) (\(S = \cup _{s=1}^{t}S_{s}\)), we denote by \(\kappa _{3}(S\vert \mathcal{S})\) the optimal value of the bin packing problem defined as follows. For each set S s in \(\mathcal{S}\), we define κ 1(S s ) items of size Q, except for the last one, which will have a size equal to \(w(S) - (\kappa _{1}(S) - 1)Q\), and we define bin capacities equal to Q. Then, the SFrCI corresponding to frame \((S,\mathcal{S})\) is:

$$\displaystyle{ \sum \limits _{r\in \varGamma }\xi _{rS}\lambda _{r} +\sum \limits _{ s=1}^{t}\sum \limits _{ r\in \varGamma }\xi _{rS_{s}}\lambda _{r} \geq \kappa _{3}(S\vert \mathcal{S}) +\sum \limits _{ s=1}^{t}\kappa _{ 1}(S_{s}). }$$
(15.31)

These inequalities generalize and reinforce the capacity inequalities, which force that the number of routes that visit a given set of customers S is at least κ 1(S). Note that when no location decisions have to be made, in the presence of degree constraints, capacity constraints are equivalent to subtour elimination constraints (15.15). Indeed, when for a given set S ⊂ J, \(\mathcal{S}\) only contains one set, the corresponding SFrCI constraint is a capacity constraint (in this case, \(\kappa _{3}(S\vert \mathcal{S}) =\kappa _{1}(S)\)). So, the two terms in the left-hand side of (15.31) are identical, the two terms in the right-hand side are also equal, and the inequality becomes:

$$\displaystyle{\sum \limits _{r\in \varGamma }\xi _{rS}\lambda _{r} \geq \kappa _{1}(S),}$$

which is the basic expression of the capacity constraint.

As is the case for other sets of inequalities, the framed capacity inequalities (FrCI) where originally developed for two-index flow formulations and later adapted to the set-partitioning formulation by using Eq. (15.29), and reinforced by modifying the coefficients of the λ r variables as explained in the last section. The FrCI for formulation LRP2 corresponding to \((S,\mathcal{S})\) is

$$\displaystyle\begin{array}{rcl} & & \sum \limits _{j\in S}\sum \limits _{k\in V \setminus S}z_{\mathit{jk}}^{1} + 2\sum \limits _{ i\in I}\sum \limits _{j\in S}z_{\mathit{ij}}^{2} +\sum \limits _{ s=1}^{t}\sum \limits _{ j\in S_{s}}\left (\sum \limits _{k\in V \setminus S_{s}}z_{\mathit{jk}}^{1} + 2\sum \limits _{ i\in I}z_{\mathit{ij}}^{2}\right ) \\ & & \qquad \geq 2\left (\kappa _{3}(S\vert \mathcal{S}) +\sum \limits _{ s=1}^{t}\kappa _{ 1}(S_{s})\right ). {}\end{array}$$
(15.32)

To illustrate that FrCI (and, therefore, SFrCI) is a broader set of inequalities that can be stronger than the combination of capacity constraints for the individual sets S s , Fig. 15.3 gives an example of a fractional solution with \(\mathcal{S} =\{ S_{1},\cdots \,,S_{4}\}\), where the capacity constraints for each of the S s sets are satisfied, but the overall FrCI constraint is violated. In this figure, customers are numbered from 1 to 7 and w i is given inside each customer.

Fig. 15.3
figure 3

Example of unsatisfied FrCI

Full size image

Note that, in this example, we have \(S = \cup _{s=1}^{4}S_{s}\), w(S) = 20 and Q = 7, so that κ 1(S) = 3. Thus, the capacity constraint for set S is satisfied, since the total flow in edges with one endpoint in S equals its lower bound, \(2 \cdot 3 = 6\). Also, for each set in the partition, w(S s ) < Q, so that κ 1(S s ) = 1 and the z-degree of S s is 2 or larger in all cases. In contrast, the evaluation of constraint (15.32) gives

$$\displaystyle{6 + (2 + 2 + 3 + 2) \geq 2(4 + 1 + 1 + 1 + 1),}$$

which is clearly not satisfied. Here, note that in the computation of \(\kappa _{3}(S\vert \mathcal{S})\), four items were defined, with sizes 6, 6, 2 and 6, respectively, and the bin capacity was set to 7.

The example of Fig. 15.3 also provides some insight in the way how the variable definition in set partitioning formulations such as LRP3 forbids some fractional solutions that are sometimes encountered when using flow formulations. Indeed, the solution of the figure can be obtained in a relaxation of formulation LRP2, but it is impossible to obtain it from formulation LRP3, since it cannot be decomposed as the (fractional) combination of vehicle routes which are feasible with respect to the vehicle capacity constraint.

4 Heuristic Algorithms

Many heuristics have been devised for different variants of LRPs. It is not the goal of this chapter to enumerate and explore all these contributions. Instead, we concentrate on the tools that have been most useful in those heuristics.

In the design of heuristics for LRPs it is very difficult to ignore the fact that the problem combines decisions of two completely different natures: the location of the facilities and the design of vehicle routes. Indeed, even solution methods based on the use of neighborhoods tend to distinguish between the neighborhoods that affect the set of facilities (add, drop or swap) and those that are typically used in vehicle routing problems. A clear example of this fact is the variable neighborhood search (VNS) heuristic recently proposed in Jarboui et al. (2013) for an LRP with capacitated facilities and uncapacitated vehicles or the granular tabu search heuristic presented in Willmer Escobar et al. (2013) for an LRP where both vehicles and depots are capacitated. Possible exceptions are some algorithms based on the construction of giant tours that encode both types of decisions, so that tour modifications can alter both, facility locations and vehicle routes. Examples of this type of algorithm are those of Yu et al. (2010) or Contardo et al. (2014b).

A commonly accepted classification for heuristic methods for LRPs, due to Nagy and Salhi (2007), includes four categories, depending on how the interaction between these decisions is taken into account in the design of heuristics.

  • Sequential methods split the problem into its subproblems. First they solve the location problem, using estimates of the routing costs that only take into account the distances between customers and facilities and, they then solve the routing problems defined at each opened facility with its assigned customers. Although Srivastava and Benton (1990) show that this type of methods, that are typically quite fast, can produce pretty good solutions for some types of instances, in general, they tend to have a rather poor behavior, and most authors moved fast to other types of heuristics.

  • Clustering-based methods partition the set of customers into clusters and then they either locate a depot for each cluster and solve a vehicle routing problem afterwards, or solve an auxiliary traveling salesman problem for each cluster before locating the depots. Barreto et al. (2007) present a method of this type and also analyze different clustering criteria in this context. A more recent example of this type of method is the constructive procedure considered in the two-phase method of Willmer Escobar et al. (2013) for the capacitated LRP. With their algorithm, the authors have provided the currently best known solutions for many of the existing benchmark instances (with up to 200 customers and 20 facilities) but at a high computational cost since some instances required more than 10 min of CPU time.

  • Iterative methods can be seen as an evolution of sequential methods, where several iterations of a sequential method are performed, and the information obtained at each iteration is used to guide the methods used for choosing the locations and designing the vehicle routes built at the next one. The algorithm proposed in Prins et al. (2007) falls in this category. Using their algorithm, the authors could find very good solutions (proven to be optimal in several cases) for instances with up to 200 customers and 20 facilities, and the CPU time exceeded 1 min in only a reduced subset of the considered instances.

  • In hierarchical methods the problem is considered in a more integrated way, without splitting its components. However, the two decisions are not considered to be equally important; facilities location is regarded as the main problem decision and vehicle routes design as a secondary one. Many contributions fit in this category (Albareda-Sambola et al. 2005; Ting and Chen 2013), especially the most recent ones, since they tend to yield better results. Indeed, the results obtained in Ting and Chen (2013) are comparable with those of Willmer Escobar et al. (2013), although solutions are slightly worse in general terms, this is compensated by somehow smaller CPU times.

Finally, one can also find in the literature one approximation algorithm for the LRP in Harks et al. (2013). The proposed algorithm builds a solution by combining the solutions to two auxiliary problems: and uncapacitated facility location problem, and a minimum spanning tree. For this algorithm, they prove an approximation factor of 4. 38.

5 Location Arc Routing

LARPs are typically defined on graphs G = (V, E) that can be either directed, undirected or, in the most general case, mixed. In G, a set I ⊂ V of selected nodes where facilities may be established is given, together with a selected subset of links R ⊆ E, known as required arcs or edges, which must be traversed to receive some service. Common applications of LARPs include garbage collection, road maintenance and postal delivery. For details on these applications, the reader is referred to Ghiani and Laporte (2001).

In contrast to the volume of the literature on LRPs with node routing, LARPs have been addressed only in a few references. This is due in part, to the difficulty of these problems, but also to the fact that several strategies have been devised to transform arc routing problems into node routing problems by suitably modifying the underlying graph (see, for instance Pearn et al. 1987; Baldacci and Maniezzo 2006; Longo et al. 2006). However, significant differences exist between the structures of the routes depending on whether service is provided at the nodes or on the links. These differences suggest that, as happens with pure routing problems, specific approaches for either type of problem may yield more efficient algorithms.

The most relevant difference between routes in node and arc routing is that in node routing problems one can assume, without loss of generality, that no node will be visited more than once, and the only links that may be traversed twice are those connecting one facility with one customer, allowing thus for routes visiting one single customer. In contrast, in arc routing problems, even required links may be traversed more than once in optimal solutions. Also, the set of required arcs induces a family of connected components of G which, as happens in pure arc routing problems, play an important role in determining which links are susceptible of being used more than once.

The first paper addressing a LARP is probably that of Levy and Bodin (1989) in which a problem with uncapacitated vehicles arising in the USA postal services was solved. To this end, the authors split the problem into its components and solve them sequentially, following the scheme (1) location of facilities, (2) allocation of required edges to facilities, and (3) route design.

Uncapacitated LARPs were also studied in Ghiani and Laporte (1998). One of the first consequences of having uncapacitated vehicles is that, when the triangle inequality holds, only one route needs to be built for each open facility. Moreover, the authors show that, in this case, optimal solutions exist where all the required edges belonging to the same connected component are served in the same route, which allows to transform this particular LARP into different arc routing problems, depending on whether the number of depots to locate is bounded or not. Applying a branch-and-cut algorithm to these problems, the authors solve uncapacitated LARP instances on graphs with up to 200 nodes. Since then, no exact algorithm for any LARP variant has been proposed, and only heuristic algorithms for different variants can be found in the literature. Actually, two mixed integer programming formulations for capacitated LARPs were proposed by Doulabi and Seifi (2013): one for the general case, and a second one for the particular case where one single depot has to be located. Another formulation is also presented in Borges Lopes et al. (2014). However, these papers do not explore the possibility of solving these formulations exactly, possibly because they all use flow variables, with up to four indices in some cases, and therefore, they are rather large.

Bearing in mind the evolution of the formulations for the capacitated arc routing problem (CARP), one might expect set partitioning formulations to allow for more efficient solution methods. Indeed, the most successful algorithms for the CARP so far, proposed by Bode and Irnich (2012) and Bartolini et al. (2013), both rely on set partitioning formulations for this problem. In any case, further research is still needed before reaching efficient exact methods for solving general LARPs. Although it is true that research on the CARP has been very fruitful in the past years, the subproblem obtained from a LARP when the set of facilities to open is fixed is a CARP with multiple depots, which has hardly been studied, and for which only heuristic algorithms exist (see, for instance, Amberg et al. 2000).

In the case of heuristic methods, the original approaches relying on the sequential solution of the different subproblems of a LARP have evolved with a recent focus on the use of metaheuristics. Doulabi and Seifi (2013) propose a simulated annealing heuristic which, at each iteration, proceeds following an allocation-routing-location scheme: it first builds a routing solution then tries to improve the depot locations. More recently, Borges Lopes et al. (2014) have proposed and compared several heuristics combining tabu search, variable neighborhood search, and GRASP for which they also test different constructive heuristics. According to their computational experiments, the combination of tabu search and GRASP provides the best results. With this combination, they find optimal or near optimal solutions in less than a minute, for instances with up to 140 nodes and 190 required edges. They also propose a set of benchmark instances for future comparisons.

In contrast to the scarce literature available on the LARP, a relatively large variety of related problems have been studied. This is the case, for instance, of the capacitated arc routing problem with intermediate facilities presented in Ghiani et al. (2001). In this case, no location decisions need to be made, and a single depot is considered, like in the CARP, but several facilities are available in the network where a vehicle can unload the demand collected at the required edges before the loaded demand exceeds the vehicle capacity.

Other examples are the capacitated arc routing problem with refill points or the synchronized arc and node routing problem, presented in Amaya et al. (2007) and Salazar-Aguilar et al. (2013), respectively. In these cases, an additional fleet of vehicles is available to refill the main fleet, and the locations where these vehicles meet each other need to be determined when designing their respective routes. These problems differ in the types of routes performed by the vehicles used to replenish the service vehicles.

A recent paper on the directed profitable location rural postman problem (Arbib et al. 2014) also deserves a mention. This is an uncapacitated LARP where required arcs have associated profits and the decision maker can choose whether or not to serve any of them, taking into account the differences between the profit generated and the cost of reaching the arcs. Using a branch-and-cut algorithm, the authors can solve to optimality instances involving up to 140 nodes and 190 required arcs.

6 Conclusions

This chapter has summarised some the most relevant research contributions on LRPs and LARPs. As it has been shown, the different research directions followed in the study of formulations and exact algorithms for LRPs have finally converged to one single proposal, which has been able to incorporate most of the relevant contributions in the field so far. In the case of heuristic algorithms, the research activity has recently been reactivated, giving raise to several competitive algorithms in the last years. The most successful approaches involve one or several metaheuristics, and the current activity in this area gives the impression that relevant further improvements can be expected in the near future.

In contrast, research on LARPs is still in its early stages. Exact algorithms have only been proposed for very particular cases, and even in the case of heuristics the literature is rather scarce. Keeping in mind the evolution followed by the research on LRPs, especially in what concerns exact algorithms, further research is still required on arc routing problems with multiple depots before it is possible to devise efficient algorithms for solving LARPs.