Multi-depot rural postman problems

Abstract

This paper studies multi-depot rural postman problems on an undirected graph. These problems extend the well-known undirected rural postman problem to the case where there are several depots instead of just one. Linear integer programming formulations that only use binary variables are proposed for the problem that minimizes the overall routing costs and for the model that minimizes the length of the longest route. An exact branch-and-cut algorithm is presented for each considered model, where violated constraints of both types are separated in polynomial time. Despite the difficulty of the problems, the numerical results from a series of computational experiments with various types of instances illustrate a quite good behavior of the algorithms. When the overall routing costs are minimized, over 43 % of the instances were optimally solved at the root node, and 95 % were solved at termination, most of them with a small additional computational effort. When the length of the longest route is minimized, over 25 % of the instances were optimally solved at the root node, and 99 % were solved at termination.

1 Introduction

In this paper, we present multi-depot rural postman problems (MDRPPs) on undirected graphs. Similar to other arc routing problems, in MDRPPs, service demand is placed at a subset of edges, denoted demand or required edges. The distinguished feature of MDRPPs is that there are several depots instead of just one. In MDRPPs, feasible solutions are given by sets of routes, each of them starting and ending at one of the depots, where each demand edge is traversed at least once by some route. MDRPPs involve two types of decisions: the allocation of the demand edges to the depots and the construction of the set of routes. We consider two different MDRPP models, which differ from each other in the objective function. The first model uses a min-cost objective where the goal is to determine a set of routes of minimum total cost and will be referred to as MC-MDRPP. The MC-MDRPP extends to several depots the well-known undirected Rural Postman Problem (RPP) introduced by Orloff (1974), which considers one single depot.

The second model that we study uses a min–max objective where the goal is to minimize the length of the longest route, and will be referred to as MM-MDRPP. In contrast to the MC-MDRPP, which minimizes the overall routing costs, but may produce routes which are unbalanced in terms of their length, the MM-MDRPP can be suitable when balanced routes are sought. The MM-MDRPP is related to the min-max K-Rural Postman Problem (MM-K-RPP) that has been studied by several authors for different types of graphs (Willemse and Joubert 2012; Benavent et al. 2013, 2009, 2011, 2010, 2014). The MM-K-RPP is an uncapacitated arc routing problem, with one single depot and a fixed number of vehicles, K. Each vehicle must perform a tour starting and ending at the depot. The objective is to minimize the length of the longest among the K routes. It clear that the undirected MM-K-RPP is a particular case of the MM-MDRPP, by considering K depots co-located at the same vertex.

The motivation for studying MDRPPs comes not only from their theoretical interest, but also from their potential applications. Similar to other arc routing problems, such applications appear in a wide variety of practical cases. Mail delivery, garbage collection, road maintenance or pipelines inspection are typical examples of real-life applications. When considering large application areas for the above examples, there is usually more than one depot from which service demand can be satisfied. Such depots may be vehicle stations, dump sites, replenishment points or relay boxes. For instance, in urban waste collection companies usually operate from multiple depots. A possibility for handling such problems is to decompose them in as many independent problems as depots, first allocating to the different depots demand sectors within smaller operating areas, and then finding optimal routes within each sector. Such solution strategy is indeed suboptimal, as it can be possible to obtain better solutions if a global approach is applied in which the allocation and routing decisions are jointly addressed.

The literature on multi-depot arc routing problems (MDARP) is scarce. To the best of our knowledge, this is the first work where an exact algorithm based on a mixed integer linear programming (MILP) formulation is proposed to solve the MDRPP on an undirected graph. A directed MDARP has been considered in the recent work (Fernández et al. 2016), where an exact branch-and-cut algorithm is proposed for a collaboration arc routing problem. Other than this, all previous work on MDARPs we are aware of focus on capacitated arc routing problems with multiple depots (MDCARPs). Some theoretical aspects of MDCARPs are considered by Wøhlk (2004). The asymmetric multi-depot capacitated arc routing problem is studied by Krushinsky and Woensel (2015) where a new formulation and exact solution algorithm are presented. Heuristic methods have been proposed for both undirected and directed MDCARPs. Sequential heuristics for the undirected MDCARP are proposed by Amberg et al. (2000), Muyldermans et al. (2002, 2003): a cluster-first-route-second strategy, where the assignment of arcs to depots is established before designing the routes, is applied in the study by Amberg et al. (2000), and a route-first-cluster-second strategy is used by Muyldermans et al. (2002, 2003), where a single route is created first, which is later divided into smaller routes. Population-based heuristics have also been used for solving MDCARPs. For the undirected case, two different ant colony strategies are presented by Kansou and Yassine (2009), and a hybrid genetic algorithm with perturbation that incorporates a local search, a replacement method, and a perturbation mechanism is proposed by Hu et al. (2013). The directed case is addressed by Xing et al. (2010), where an evolutionary approach is presented, which takes advantage of the extensions of the classical heuristics for the capacitated arc routing problem (Golden and Wong 1981).

Multi-depot routing problems are indeed related to districting, where a set of clusters or districts that suitably partition the demand set is sought. The design of good districts at an strategic level, where demand points or edges are allocated to depots, allows finding efficient routes at each district at an operational in a later phase. There exists a rich districting literature, in relation to arc routing. In fact, some of the above-referenced works stem from this relation. As an example, the heuristics of Muyldermans et al. (2002, 2003) are devised as a second phase in districting design problems. Two recent works on districting for arc routing are Butsch et al. (2014) and García Ayala et al. (2015). The interested reader is addressed to the studies by Muyldermans (2003) and Muyldermans and Pang (2014) for further reading on this topic.

In this work, we exploit properties and optimality conditions of MDRPPs, when stated on undirected graphs. These properties allow us to obtain MILP formulations where all variables are binary. In its turn, using binary variables only makes it possible to model parity constraints with an adaptation of the co-circuit inequalities (Barahona and Grötschel 1986). The resulting formulations have two families of constraints of exponential size on the number of vertices of the input graph: one set for the parity of vertices and the usual set of connectivity constraints. As we will see, the constraints in each family can be separated exactly in polynomial time with adaptations of well-known algorithms. We propose an exact branch-and-cut algorithm where the linear programming (LP) relaxation of the formulation is reinforced with several families of valid inequalities. To analyze the behavior of the proposed algorithm, we have run a series of computational experiments for both the MC-MDRPP and the MM-MDRPP, with a set of benchmark instances adapted from well-known data sets used for other arc routing problems in the literature. The results of these experiments are presented and analyzed.

The reminder of this work is structured as follows. In Sect. 2, we define MDRPPs whereas in Sect. 3 we state some properties that will be exploited in the proposed formulations. The formulations for the MC-MDRPP and the MM-MDRPP are presented in Sect. 4, as well as some families of valid inequalities that we use to reinforce their LP relaxations. Section 5 describes the solution algorithm and discusses the procedures used to separate violated connectivity and parity inequalities. The computational experiments and the obtained results are described in Sect. 6. Section 7 concludes the work with some comments and directions for future research.

2 Multi-depot rural postman problems

MDRPPs are defined on an undirected connected graph $G=(V, E)$ with vertex set V,  $|V|=n$, edge set E, $|E|=m$, set of depots $D\subset V$, and set of demand (required) edges $R\subset E$. Non-demand edges are denoted by $F=E{\setminus } R$. The connected components induced by demand edges are denoted by $C_k=(V_k, R_k)$, $k\in K$ so $R=\bigcup \nolimits _{k\in K}R_k$. Let $V_{R}=\bigcup \nolimits _{k\in K}V_k$. We assume that E contains no edge connecting two depots, and no component has more than one depot, although it is possible that a component contains no depot, i.e., $|V_k\cap D|\le 1$ for all $k\in K$. Let c denote a non-negative real cost function defined on the edges of G.

Throughout we use the term route to denote a closed path, not necessarily simple, that starts and ends at the same depot $d\in D$. When the depot of the route needs to be explicit, we say that the route is rooted at depot d. We say that a demand edge $e\in R$ is served by a route, if the route traverses e at least once. As usual, the cost of a route is the sum of the costs of the edges in the route, where the cost of each edge is counted as many times as it is traversed in the route.

We will use the following notation. For any non-empty vertex subset $S\subset V$, $\delta (S)=\{e \in E | e =(u,v), u \in S, v \in V{\setminus } S\}=\delta (V{\setminus } S)$ is the set edges in the cut between S and $V\backslash S$ and $\gamma (S)=\{e \in E | e =(u,v), u, v \in S \text { or vice versa}\}$ the set of edges with both vertices in S. For a singleton $S=\{v\}$, with $v\in V$, we do not use the brackets and just write $\delta (v) \equiv \delta (\{v\})$. For $H\subset E$, we use $\delta _{H}(S)= \delta (S) \bigcap H$ and $\gamma _{H}(S)= \gamma (S) \bigcap H$. Furthermore, we will say that a vertex $v\in V$ is H-odd if $|\delta _{H}(v)|$ is odd; otherwise we will say that v is H-even. Finally, we use the standard compact notation $f(A)\equiv \sum \nolimits _{e \in A}{f_{e}}$ where $A \subseteq E$, and f is a vector or a function defined on E. If f is only defined on subset $B \subset E$, we use $f(A) \equiv f(A \cap B) \equiv \sum \nolimits _{e \in A \cap B}{f_{e}}$.

In the reminder of this paper, we make the following modeling assumption:

• (H1) Demand edges in the same component can be served from different depots. The effect of this assumption is illustrated in Fig. 1. Figure 1a shows the input graph, which has two demand components and one depot in each of them ($v_1$ and $v_2$, respectively). Demand edges are represented by black lines while non-demand edges are drawn in light gray. The numbers next to the edges indicate their costs. Figure 1b shows the optimal solution when we impose that all demand edges in the same component are served from the same depot, whose total cost is 23 units. The route of depot $v_1$ (represented with straight lines), which serves the demand edges of $C_1$, consists of edges ($v_1$, A), (A, B), and (B, $v_1$). The route of depot $v_2$ (represented with doted lines), which serves the demand edges of $C_2$, consists of edges ($v_2$, E), (E, C), (C, D), (D, E), (E, F), and (F, $v_1$). Figure 1c shows that a better solution, of value 19 units, can be obtained if we allow to serve demand edges in the same component from different depots. Now all demand edges of $C_1$ and some demand edges of $C_2$ are served in the route from depot $v_1$ defined by edges ($v_1$, A), (A, C), (C, E), (E, D), (D, B), and (B, $v_1$). The remaining demand edges of this component are served in the route from depot $v_2$, which consists of edges ($v_2$, E), (E, F), and (F, $v_2$).

  The routes not necessarily have to be vertex disjoint.

Fig. 1

Example that allowing to split the demand components among routes may produce better solutions

In the following, we assume that G has been simplified so that V is the set of vertices incident with edges in R, and E contains the edges in R plus additional non-demand edges, connecting every pair of vertices not connected with an edge of R, representing shortest paths in the original graph. For this, according to Christofides et al. (1981), first we add to $G_R=(V_R, R)$ an edge between every pair of vertices of $V_R$ having a cost equal to the shortest path length on G. Then we remove all non-demand edges $(i,j)\in F$ for which $c_{ij} = c_{ik} + c_{kj}$ for some $k\in V$ and one of two edges in parallel whenever they both have the same cost. Hence, the costs satisfy the triangle inequality.

Definition 2.1

• The MC-MDRPP is to find a set of routes that serve all the demand edges of minimum total travel cost.

• The MM-MDRPP is to find a set of routes that serve all the demand edges that minimizes the length of the longest route.

3 Complexity and optimality conditions

The RPP is a particular case of the MC-MDRPP with $|D|=1$. Since the RPP is NP-hard Orloff (1976), we also have:

Proposition 3.1

The MC-MDRPP is NP-hard.

The RPP is also a particular case of the MM-MDRPP with $|D|=1$. Thus, we also have:

Proposition 3.2

The MM-MDRPP is NP-hard.

As it is usual in other uncapacitated arc routing problems on undirected graphs the feasibility of MDRPP solutions is basically established via connectivity and parity conditions, in addition to the requirement that all demand edges are served. Thus, it is not surprising that, similar to other such problems with min-cost objectives, when non-negative costs satisfy the triangle inequality, optimality conditions hold for the MC-MDRPP that allow to derive formulations using binary variables (see, for instance, Ghiani and Laporte 2000; Fernández et al. 2003). These properties extend or can be adapted to the MM-MDRPP as well as explained below:

• (O1) MC-MDRPP and MM-MDRPP There is an optimal MDRPP solution in which each demand edge is served by exactly one route.

• (O2) MC-MDRPP and MM-MDRPP There is an optimal solution in which no edge is traversed more than twice. Otherwise, two copies of the same edge can be removed without affecting neither the requirement that all demand edges are served, nor the parity of the vertices or the connectivity with the depot.

• (O3) MC-MDRPP and MM-MDRPP There is an optimal solution where no non-demand edge with the two end-nodes in the same component ($e\in \gamma _{F}(V_k)$) is traversed more than once. Otherwise, two copies of such an edge can be removed without affecting the feasibility of the solution. Furthermore, because of the triangle inequality, the only edges of $\gamma _{F}(V_k)$, that are used, are those connecting two R-odd vertices.

• (O4) There is an optimal solution in which the only non-demand edges that are traversed twice are of one of the following types:

  • (a) MC-MDRPP (see Ghiani and Laporte (2000) for a similar result for the RPP) Edges of the Minimum Spanning Tree (MST) of the multigraph graph $G_C=(V_C, E_C)$ induced by the connected components. $V_C$ contains a node representing each connected component $C_k$, $k\in K$. For each pair of distinct components $C_k$ and $C_{k'}$, $E_C$ contains an edge $(k_e, k'_e)$ associated with each original edge e linking $C_k$ and $C_{k'}$, i.e., each edge $e\in \delta _F(V_k)\cap \delta _F(V_{k'})$, which inherits its cost from G.

    It is clear that any MST of $G_C$ will use only least cost edges between pairs of components. Let $T^*$ be an MST of $G_C$, and suppose an edge $e^*\in E$ connecting components $C_k$ and $C_{k'}$ is traversed twice in an optimal MC-MDRPP solution $s^*$, but $(k_{e^*}, k'_{e^*})$ is not a least cost edge connecting components $C_k$ and $C_{k'}$. Then, adding edge $e^*$ to $T^*$ produces a cycle in $G_C$, in which $c_{\widehat{e}}<c_{e^*}$, where $\widehat{e}$ denotes a least cost edge in such cycle. Then, replacing in $s^*$ the two copies of edge $e^*$ by two copies of $\widehat{e}$ produces feasible solution: the parity of the vertices of the original graph G does not change and the connectivity of the new solution is guaranteed by the two copies of $\widehat{e}$. It is possible that in the new solution some edges are served from a different depot than in the original solution $s^*$, but this does not affect to its feasibility either. The fact that the cost of the new solution is smaller than that of the original one, contradicts the optimality of the original solution.

    As shown in the example of Fig. 2, this optimality condition does not apply to the MM-MDRPP, where an optimal solution may have two copies of a non-demand edge connecting two different components, which does not belong to any MST of $G_C$. Thus, the adaptation of this condition to the MM-MDRPP must take into account all least cost edges connecting any pair of components.

  • (b) MM-MDRPP Least cost edges connecting pairs of vertices of the multigraph graph $G_C=(V_C, E_C)$.

Fig. 2

Optimal MM-MDRP solution using twice an edge not in the MST of $G_C$. a Input graph. b MST of $G_C$. c Optimal solution

4 Formulations

Below we present an MILP formulation for the MC-MDRPP that exploits the optimality conditions of the previous section. Condition (O2) implies that we only need two sets of binary variables, for the first and second traversals of edges, respectively. We denote by $E^y\subset E$ the set of edges that can be traversed twice in an optimal MC-MDRPP solution, which consists of all demand edges plus the edges of the MST of $G_C$ [see conditions O4(a)]. In each set, variables are also associated with the depot of the route that traverses the edges. For each $e\in E$, $d\in D$, let $x_{e}^{d}$ be a binary variable indicating whether or not edge e is traversed by the route of depot d. For each $e\in E^y$, $d\in D$, let $y_{e}^{d}$ be a binary variable that takes the value one if and only if edge e is traversed twice in the route of depot d. Then, the MILP for the MC-MDRPP is as follows:

$$\begin{aligned} \min&\sum \limits _{d\in D}\left( \sum \limits _{e\in E} c_ex^d_e+\sum \limits _{e\in E^y}y^d_e\right) \quad \quad \quad \quad \qquad \qquad \qquad \qquad \qquad \quad \end{aligned}$$

(1)

$$\begin{aligned}&\left( x^d+y^d\right) (\delta (d))\ge 2, \ \quad \quad \quad \qquad \qquad \qquad \qquad \qquad \qquad \quad d\in D \end{aligned}$$

(2)

$$\begin{aligned}&\left( x^d+y^d\right) (\delta (S))\ge 2 x_e^d, \quad \quad \qquad \qquad \qquad \qquad \qquad \qquad \quad d\in D, S\subseteq V{\setminus } \{d\}, \end{aligned}$$

(3)

$$\begin{aligned}&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \qquad e\in \gamma (S) \nonumber \\&\left( x^d-y^d\right) (\delta (S){\setminus } H) + y^d(H)\ge x^d(H) - |H|+ 1, \quad S\subset V,\ H\subseteq \delta (S), \end{aligned}$$

(4)

$$\begin{aligned}&\quad |H| \text{ odd }, d\in D \nonumber \\&\sum \limits _{d\in D}x^d_e = 1,\quad e\in R \end{aligned}$$

(5)

$$\begin{aligned}&y^d_e \le x^d_e,\quad e\in E^y, d\in D \end{aligned}$$

(6)

$$\begin{aligned}&x^d_e\in \{0,1\},\quad e\in E; \quad y^d_e \in \{0,1\}, \quad e\in E^y d\in D \end{aligned}$$

(7)

Inequalities (2) and (3) ensure that all depots are used and the connectivity of each route with its depot, respectively. This latter condition is imposed by stating that if an edge is traversed by the route associated with depot $d\in D$, then at least two edges must cross the cut-set of any vertex set containing its two end-nodes, if it does not contain the depot d. Inequalities (4) ensure the parity (even degree) of every subset of vertices and, in particular, at every vertex. Broadly speaking, they impose that if a solution uses an odd number of edges, H, incident to a set of vertices S, then the solution uses at least one additional traversal of some edge in the cut-set $\delta (S)$. In our case, we further exploit the precedence relationship of the x variables with respect to y variables imposed by constraints (6). Thus, the additional edge will be either a second traversal of some edge of H or a first traversal of some edge of $\delta (S)\backslash H$. Inequalities (4) are an adaptation to the MDRPP of those proposed in Aráoz et al. (2006, 2009a, b), which were later reinforced by Corberán et al. (2013) for the Maximum Benefit Chinese Postman Problem. Inequalities (2)–(4) jointly guarantee that any solution defines |D| Eulerian circuits. Taking into account optimality condition (O1), equalities (5) ensure that each demand edge is served by one route. As mentioned, inequalities (6) impose that a route cannot traverse an edge for the second time unless it also traverses the edge for the first time. Binary conditions of the variables x and y derived from their definition are reflected in constraints (7).

The above formulation has $|E| \times |D|$ x variables and $|E^{y}| \times |D|$ y variables. There are |D| inequalities of type (2), |R| inequalities (5) and $|E^y| \times |D|$ inequalities of type (6). The size of the families inequalities (3) and (4) is exponential on |V|.

For the formulation for the MM-MDRPP, we use the same sets of decision variables x and y, taking into account that the index set $E^y$ for the variables associated with edges that can be traversed twice in an optimal MM-MDRPP solution must be defined according to conditions O4(b). The formulation inherits all constraints (2)–(7). In addition, we define a new integer variable z representing the length of the longest route, so the objective becomes the minimization of z. A new family of constraints is needed to relate the new variable z to the lengths of the routes. These inequalities also ensure that z represents the longest route:

$$\begin{aligned} z \ge \sum \limits _{e\in E} c_ex^d_e+ \sum \limits _{e\in E^y} c_ey^d_e \qquad v\in D. \end{aligned}$$

(8)

4.1 Valid inequalities

Below we present some families of simple valid inequalities that we will use to reinforce the LP relaxations of the above formulations for the MC-MDRPP and the MM-MDRPP:

• 1. Aggregated connectivity constraints

  By adding up over all depots the connectivity constraints (3) associated with subsets of nodes containing no depots, and taking into account that all vertices, except possibly the depots, are incident with some demand edge, and thus must be visited, we obtain:

  $$\begin{aligned} \sum \limits _{d\in D}\left( x^d+y^d\right) (\delta (S))\ge 2, \quad S\subset V, S\cap D=\emptyset . \end{aligned}$$

  (9)

  Even if the family (9) is implied by the general family (3) and is also of exponential size, some small sub-families associated with particular subsets S can be very useful to reinforce the initial LP relaxation when the general family (3) is relaxed:

  • Singletons $S=\{v\}$, with $v\in V{\setminus } D$:

    $$\begin{aligned} \sum \limits _{d\in D}\left( x^d+y^d\right) (\delta (v))\ge 2, \quad v\in V{\setminus } D. \end{aligned}$$

    (10)

    For the depots $d\in D$, the inequalities (10) are also valid, although they are dominated by the stronger constraints (2).

  • End-nodes of demand edges. $S^e=\{u, v\}$, with $e=(u, v)\in R$, $S^e\cap D=\emptyset$:

    $$\begin{aligned} \sum \limits _{d\in D}\left( x^d+y^d\right) (\delta (S^e))\ge 2, \quad e\in R, S^e\cap D=\emptyset . \end{aligned}$$

    (11)

  • Vertex sets of components without depot. $S=V_k$, $k\in K$, $V_k\cap D=\emptyset$:

    $$\begin{aligned} \sum \limits _{d\in D}\left( x^d+y^d\right) (\delta (V_k))\ge 2, \quad k\in K, V_k\cap D=\emptyset . \end{aligned}$$

    (12)

• 2. Aggregated parity constraints

  Aggregate versions of the parity constraints (4) are indeed valid for the MC-MDRPP and the MM-MDRPP. Similar inequalities (but combining binary and general integer variables) have been used for other ARPs with multiple vehicles, namely the MM-K-RPP (Benavent et al. 2009, 2014). For the MC-MDRPP and the MM-MDRPP, for $S\subset V$, $H\subseteq \delta (S)$, |H| odd. The inequality that we obtain is the following:

  $$\begin{aligned} \sum \limits _{d\in D}\left( x^d-y^d\right) (\delta (S){\setminus } H) + \sum \limits _{d\in D}y^d(H)\ge \sum \limits _{d\in D}x^d(H) - |H|+ 1. \end{aligned}$$

  (13)

  In particular, when S is R-odd, i.e., $|\delta _R(S)|$ odd, and $H=\delta _R(S)$, the inequality (13) becomes

  $$\begin{aligned} \sum \limits _{d\in D}\left( x^d-y^d\right) (\delta _F(S)) + \sum \limits _{d\in D}y^d(\delta _R(S))\ge 1. \end{aligned}$$

  (14)

5 Solution algorithm

In this section, we present the solution algorithm that we use to solve the MDRPPs, based on the formulations proposed in Sect. 4. It is a branch-and-cut algorithm where an iterative Liner Programming (LP)-based cutting plane algorithm is applied to the nodes of the enumeration tree. For this, the families of constraints of exponential size are relaxed and, at each iteration, inequalities violated by the current LP solution are separated. Such inequalities are iteratively incorporated into the current formulation and the reinforced formulation is resolved. In our case, the two families of constrains of exponential size are the connectivity and the parity constraints, (3) and (4), respectively. In the following subsections, the different elements of our algorithm are described: the initial formulation that is considered and the separation procedures for inequalities (3) and (4).

5.1 Initial relaxation

The algorithm starts with the integrality conditions relaxed and only a subset of constraints. Initially, we include all constraints (2), (5) and (6), plus a small subset of connectivity and parity constraints. In particular, for each $d\in D$, we consider the inequalities (3) associated with the vertex subsets defined by the end-nodes of the edges not incident with any depot, i.e., $S^e=\{u,v\}$, with $e=(u,v)\in E$, such that $u,v\notin D$. This relaxation is reinforced with the aggregated connectivity inequalities (10), (11) and (12), plus the aggregated parity constraints (14), associated with R-odd singletons, i.e., $S=\{v\}$ with $v \in V$ and $|\delta _R(v)|$ odd.

5.2 Separation of inequalities

At any iteration of the algorithm, the step that solves exactly the separation problem for the connectivity and parity inequalities consists of two parts. First, we look for violated connectivity inequalities (3), and then we look for violated parity inequalities (4). Throughout, $(\overline{x},\overline{y})$ denotes the current LP solution and, for each depot $d\in D$, $(\overline{x}^d,\overline{y}^d)$ the partial LP solution associated with the depot d, i.e., the components of $(\overline{x},\overline{y})$ associated with d. Furthermore, $G^d_{\overline{x},\overline{y}}=(V^d, E_{\overline{x}^d,\overline{y}^d})$ denotes the support graph of the partial solution $(\overline{x}^d,\overline{y}^d)$ for depot $d\in D$, obtained from G by eliminating all edges in E with $\overline{x}^d_{e}=0$ and all vertices that are not incident with any edge of $E_{\overline{x}^d,\overline{y}^d}$.

5.2.1 Separation of connectivity inequalities (3)

To separate the connectivity inequalities (3), for each depot $d\in D$, we first check if $G^d_{\overline{x},\overline{y}}$ is connected. If it is not, each connected component C with vertex set $V(C)\subseteq V^d{\setminus } D$ defines a violated connectivity constraint (3) for depot d. When $G^d_{\overline{x},\overline{y}}$ is connected we build the tree of min-cuts $T^d$ (see, for instance, Gusfield 1993) of $G^d_{\overline{x},\overline{y}}$ with capacities given by $\overline{x}^d_e+\overline{y}^d_e$. Then, we use an adaptation of the algorithm of Belenguer and Benavent (1998). For each edge $e = (u, v)$ in $E_{\overline{x}^d,\overline{y}^d}$ with $u, v\in V{\setminus } D$, the minimum cut $\delta (S)$ such that $e\in \gamma (S)$ is easily obtained from the min-cut-tree $T^d$. If the value of the min-cut is smaller than $2\overline{x}^d_e$ then the inequality (3) associated with S and d is violated by $(\overline{x}^d,\overline{y}^d)$. The above separation is exact and similar to the procedure used by other authors to separate constraints (3) for other arc routing problems (Ahr 2004; Aráoz et al. 2009a; Corberán et al. 2011).

5.2.2 Separation of parity inequalities (4)

For a given vector $(\overline{x},\overline{y})$, the separation problem for inequalities (4) is to find $d\in D$, $S \subset V$, $H \subseteq \delta (S)$, |H| odd such that the associated parity inequality (4) is violated by $(\overline{x},\overline{y})$, or to prove that no such inequality exists. The algorithm that we use follows the spirit of the separation used by other authors with similar parity constraints for other arc routing problems with binary variables (Aráoz et al. 2009b, a; Corberán et al. 2011). For each $d\in D$, the algorithm starts by building the tree of min-cuts of the support graph $G^d_{\overline{x},\overline{y}}$, $T^b$, with capacities vector b defined as follows. Each edge $e = (u, v)\in E_{\overline{x}^d,\overline{y}^d}$ is assigned a capacity given by $b_e=\mathrm{{min}}\{(\overline{x}^d_{e}-\overline{y}^{d}_{e}), 1-(\overline{x}^{d}_{e}-\overline{y}^{d}_{e})\}$. This criterion dictates whether edge e should be assigned to H or to $\delta (S){\setminus } H$ if the selected cut-set contains edge e, to obtain the smallest possible value of the left-hand side of (4).

When $T^b$ has a cut $\delta (S)$ of capacity smaller than one, i.e., $b(\delta (S))<1$, we consider its vertex set S, and the set of edges $H=\{e\in \delta (S)\mid (\overline{x}^{d}_{e}-\overline{y}^{d}_{e}) \ge 0.5\}$, which, as explained, produces the smallest possible value on the left-hand side of (4). When |H| is odd, H defines, together with S, a violated inequality of type (4). Otherwise, if |H| is even, since all capacities are non-negative, the smallest increment in the value of the left-hand side of (4) that guarantees that |H| is odd is obtained by either removing one edge from H (and transferring it to $\delta (S){\setminus } H$) or by adding to H one edge currently in $\delta (S){\setminus } H$. By doing so, the variation in |H| is of just one unit, so the new set H will be odd. The above-mentioned smallest increment can be easily computed as

$$\begin{aligned} \Delta =\mathrm{{min}}\left\{ \min \left\{ \overline{x}^{d}_{e}-\overline{y}^{d}_{e}: e \in \delta (S){\setminus } H\right\} , \min \left\{ 1-\left( \overline{x}^{d}_{e}-\overline{y}^{d}_{e}\right) : e \in H \right\} \right\} , \end{aligned}$$

where the first term represents the minimum increment in the left-hand side if an edge of $\delta (S){\setminus } H$ is transferred to H, and the second term represents the minimum increment if an edge of H is transferred to $\delta (S){\setminus } H$. When $b(\delta (S))+\Delta < 1$, the updated set H defines a violated inequality (4) for d and S for the current solution $(\overline{x}^d,\overline{y}^d)$.

It is possible that the minimum cut-set of $T^b$ does not produce a violated inequality (4) even it it exists. This is only possible if the set H associated with the minimum cut in $T^b$ is even. Fortunately, in the study by Letchford and Salazar-González (2015), it is proven that exploring as explained above all the cut-sets of $T^b$ define an exact algorithm for knowing whether or not a violated inequality (4) exists. The order of such an algorithm is dominated by that of the algorithm that obtains the min-cut tree $T^b$. In practice, however, this upper limit on the order of the algorithm is very seldom reached. On the one hand, each connected component of $G^d_{\overline{x},\overline{y}}$ for the capacities vector b already defines some of the subsets S of the tree $T^b$ and connected components can be obtained with a small computational burden. On the other hand, when $G^d_{\overline{x},\overline{y}}$ defines one single connected component but a violated inequality exists, most often the cut-set producing the violated inequality will be identified before completing the full cut-tree $T^b$. Thus, in most cases, only if no violated inequality (4) exists it will be necessary to compute all the min-cuts that define $T^b$.

Summarizing, for a fixed depot $d\in D$, the exact separation for inequalities (4) reduces to finding the set S such that $\delta (S)$ contains the best possible set H, and indicates that, in the worst case, this problem can be solved by finding the complete tree of min-cuts of the support graph $G^d_{\overline{x},\overline{y}}$, for the capacities vector b defined above. It is important to recall that the smallest value of the left-hand side of inequality (4) after making H odd is not necessarily associated with the smallest min-cut of the tree.

6 Computational experiments

In this section, we describe the computational experiments we have run to evaluate the performance of the proposed algorithm. Programs have been coded in C++ using CPLEX 12.5 Concert technology for the solution of the LP relaxations. The maximum computing time has been set to four hours. Moreover, the cuts generated by CPLEX have been disabled.

All the instances were run on an Intel Core 2 CPU, 2.67 GHz and 8.00 GB RAM. Since there were no available MDRPP benchmark instances, we have generated test instances with two and four depots from 118 well-known RPP benchmark instances. The original RPP benchmark instances are divided into five groups. The first group ALB contains two data sets ALBAIDAA and ALBAIDAB, obtained from the Albaida, Spain Graph (see Corberán and Sanchis 1994, 1998). The second group contains the 24 instances, labeled P, of Christofides et al. (1981). The last 3 groups contain instances from (Hertz et al. 1999): 36 instances with vertices of degree 4 and disconnected required edges sets (labeled D), 36 grid instances (labeled G), and 20 randomly generated instances (labeled R). In all cases, we inherited the set of required edges and the cost function c from the original RPP instances.

Table 1 depicts information on these instances, which have been grouped according to their characteristics and sizes. The meaning of the columns is as follows: column under $\sharp$ inst gives the number of instances in the group; columns under $|V_{0}|$ and $|E_{0}|$ give, respectively, the number of vertices and edges of the original graph; the columns under |R| and |K| give, respectively, the number of required edges and the number of connected components in the graph induced by those required edges. In the above columns, when not all the instances of the group had the same value, the minimum and maximum values of the group are given. The remaining columns in the table give information on the effect of the graph transformation. In particular, columns under $|V|/|V_{0}|$ and $|E|/|E_{0}|$, respectively, correspond to the average ratios of the number of vertices or edges in the transformed graph related to the original graph. As it is known, the transformed graph is considerably smaller than the original graph, in terms of the number of vertices and edges.

Table 1 Instances summary

For the computational experiments and regarding the set of depots, we have considered two different cases: two and four depots. Depots have been chosen randomly from the set of vertices, fulfilling that no connected component has more than one depot. For this, for each selected number of depots $|D|\in \{2, 4\}$ we have proceeded as follows. First, we randomly generate |D| different numbers, $k_i$, $i=1,\dots , |D|$, from an integer uniform distribution U [1, |K|], which give the indices of the clusters were the depots are located. Then, for each selected cluster, $k_i$ the index of the node of $V_{k_i}$ that becomes the depot is obtained by randomly generating a number $v_i$ from an integer uniform distribution $U [1,|V_{k_i}|]$. To compare the results obtained with two and four depots, the instances that have fewer than four connected components have been removed from the experiment. Finally, the experiments have been run with two groups of 103 instances each.

Table 2 Summary of results for MC-MDRPP for instances with two depots

Table 3 Summary of results for MC-MDRPP for instances with four depots

6.1 Minimizing the overall routing costs: results for MC-MDRPP

The results for the MC-MDRPP for the instances with two and four depots are summarized in Tables 2 and 3, respectively. For each group of instances, columns 2–5 give information about the root node of the enumeration tree, while columns 6–11 give the results of the search tree. Column under $\sharp \mathrm{{opt}}_{0}$ shows the number of instances in the group that have been optimally solved in the root node. Column under $\mathrm{{gap}}_{0}$ gives the average percentage gap at the root node with respect to the optimal or best known solution at termination. The following two columns, under $\mathrm{{cutsC}}_0$ and $\mathrm{{cutsP}}_0$, give the average number of connectivity (3), and parity (4) cuts generated at the root node, respectively. Similarly, the next four columns under $\sharp$opt, gap, cutsC and cutsP give the same information at termination: number of instances that have been optimally solved, the average percentage gap with respect to the optimal or best known solution and the average number of connectivity and parity cuts generated after the root node, respectively. Column under $\sharp$Nod shows the average number of nodes that were explored in the search tree. Finally, the column under cpu gives the overall computing time in seconds. These times do not include the preprocessing time for the reduction of the graph neither the time for loading the formulation, which are negligible as compared to the solution times reported in the tables. Detailed results for each instance can be found in the Appendix.

For 36 two-depot instances, a provable optimal solution was obtained already at the root node. At termination, optimality of the current solution was proven for 100 of the 103 two-depot instances. The unsolved instances are D35, G33 and G34 with percentage optimality gaps at termination of 6.34, 9.88 and 15.36 %, respectively.

For the four-depot instances, optimality was proven at the root node for 53 instances and at termination for 95 of the 103 benchmark instances. No feasible integer solution was found within the time limit for any of the eight unsolved instances: two instances in group D100 (D34–D35) and six instances in group G100 (G30–G35).

As for the number of added inequalities, there were considerably more connectivity cuts than parity cuts, although in some cases the number of added cuts was not very large.

The computational effort required for solving the instances to optimality, can be evaluated by the required solving computing times. In this sense, only 5 instances with two depots and 14 of instances with four depots required more than one hour (including those instances for which no feasible solution was found within the time limit). Moreover, in 82 two-depot and 76 four-depot instances, respectively, the optimal solution was found in less than 1 minute. If we compare the difficulty in solving instances with two and four depots in terms of the required computing times, we can see that the algorithm is, in general, faster when the instances have fewer depots.

Observe that the proposed algorithm was able to solve at the root node more four-depot than two-depot instances, even if the former involve a larger number of variables. If we analyze those instances, we can find a pattern. In general, the solved instances belong to groups of small size and, also, they have a small number of connected components.

The results of the computational experiments also allow us to observe whether in the optimal solutions, connected components are fully served by the same depot. Our results indicate that connected components are split into 22 of the two-depot instances and into 30 of the four-depot ones.

Table 4 Summary of results for MM-MDRPP for instances with two depots

Table 5 Summary of results for MM-MDRPP for instances with four depots

6.2 Balancing the length of the routes: results for MM-MDRPP

The analysis of the solutions structures shows that in some instances, the routes produced by MC-MDRPP are unbalanced in terms of their length. Below we present the results of a new series of computational experiments that have been run with the formulation for the MM-MDRPP. For these experiments we have considered the 78 two-depot instances with up to 50 nodes, and the set of 60 four-depot instances that consists of all instances with up to 40 nodes plus the R50 set. For the excluded instances, in most cases, it was not possible to solve them to optimality and percentage optimality gaps at termination were quite big.

The results of the new experiments are summarized in Tables 4 and 5, where columns have the same meaning as before. It can be seen that, in general, the gap at the root node, the number of cuts, the number of explored nodes and the computing times are worse than with the MC-MDRPP. Still, the proposed algorithm found the optimal solution for all the tested MM-MDRPP instances but one, the exception being instance D26.

Table 6 Summary of results for MM-K-RPP for instances with two routes

Table 7 Summary of results for MM-K-RPP for instances with four routes

Comparing the optimal solutions to both models, we observe that, as could be expected, the overall routing costs are, in general, higher in optimal MM-MDRPP solutions than in optimal MC-MDRPP solutions. Even if there are 19 two-depot instances and 20 four-depot instances where the overall length of all routes is the same in both models, the average overall length increase is 13.09 % for the two-depot instances and 21.14 % for the four-depot instances. The maximum increases are 52.80 % in instance R17 with two depots, and 73.69 % in instance R11 with four depots.

Nevertheless, we can also observe that when using model MM-MDRPP, the length of the maximum route usually decreases noticeably with respect to the maximum length in an optimal MC-MDRPP solution. Even if there are 13 two-depot instances and 21 four-depot instances where the length of the longest route does not change, on average the length of the maximum route decreases in 19 % for the two-depot instances and 27.20 % for the four-depot instances. The maximum decreases are 46.15 % in instance G25 with two depots, and 64.71 % in instance G16 with four depots.

6.3 Balancing the length of the routes from one single depot

In this section, we present the results of the last series of experiments we have run. They correspond to the undirected MM-K-RPP, which considers K vehicles located at a one single depot and minimizes the length of the longest route. As mentioned in the introduction, the MM-K-RPP is a particular case of the MM-MDRPP, by considering K depots co-located at the same vertex and performing one single route from each co-located depot. For our experiments, we have considered all instances with up to 40 nodes. For each instance, we have randomly selected one of the depots, which has been replicated K times, and all other previous depots have been ignored.

Tables 6 and 7 give the results obtained for $K\in \{2, 4\}$. Comparing optimal solutions to the MM-K-RPP and the MM-MDRPP, we observe that the cost of the longest route in optimal MM-K-RPP solutions increases considerably in comparison to the MM-MDRPP. Consequently, the total routing cost increases as well. The average maximum length increases in 26.84 % for the two-depot instances and in 102 % for the four-depot instances. This represents a total increase of overall length of 31.29 and 116.50 %, respectively, on average.

The computational effort required for solving the MM-K-RPP instances to optimality is higher than the previous experiments, for instances of the same size and characteristics. In comparison with the MM-MDRPP, the computing time of the MM-K-RPP increases around 1604 % for two-depot instances and 644 % for four-depot instances. Furthermore, 8 four-depot instances could not be optimality solved within the limit time. We attribute this increase in the difficulty for optimally solving the instances to the symmetry that now appears for the routes, as they can now be interchanged.

7 Conclusions

In this work, we have introduced multi-depot rural postman problems on undirected graphs and studied some of its properties and dominance relations for two variants of the problem. In one model, the objective is to minimize the overall routing costs, whereas the second model uses a min-max objective function aiming at minimizing the length of the longest route. MILP formulations, which only use binary variables, have been presented for both models where, as usual, the families of constraints that enforce connectivity and parity of solutions are of exponential size. We have proposed an exact branch-and-cut algorithm where the separation problem of both families is solved exactly with adaptations of well-known algorithms. The performance of the algorithm has been tested for the two proposed models. For this, in each case, we have solved two sets of instances, with two and four depots, respectively, with 103 instances each of them. For the min-cost objective, 35 and 51 % of the instances of the first and second sets, respectively, were optimally solved at the root node. At termination, these percentages rise to 97 and 92 % of instances optimally solved, for the first and second set, respectively. Regardless of the difficulty of the problem, the results produced by the algorithm are quite satisfactory for the model with the min-cost objective. The numerical experiments with the model where the objective is the minimization of the longest route indicate that computationally the new formulation becomes notably more demanding. Nevertheless, the formulation for this min-max version is indeed successful in producing balanced routes.

The proposed algorithm produces, in general, quite good results for both models although that its performance decreases as the number of depots increase. The reason is that the number of variables of the proposed formulations becomes too high so as to efficiently solve medium size instances. For both models, the performance algorithm could be enhanced with the inclusion of some ad hoc heuristic.

Appendix

1.1 MC-MDRPP results

See Tables 8, 9, 10, 11, 12, 13.

Table 8 MC-MDRPP results for instances of the group ALBAIDA and P

Table 9 MC-MDRPP results for instances of the group D16 and D36

Table 10 MC-MDRPP results for instances of the group D64 and D100

Table 11 MC-MDRPP results for instances of the group G16 and G36

Table 12 MC-MDRPP results for instances of the group G64 and G100

Table 13 MC-MDRPP results for instances of the group R20, R30, R40 and R50

1.2 MM-MDRPP results

See Tables 14, 15, 16, 17.

Table 14 MM-MDRPP results for instances of the group P

Table 15 MM-MDRPP results for instances of the group D16, D36, and D64

Table 16 MM-MDRPP results for instances of the group G16, G36 and G64

Table 17 MM-MDRPP results for instances of the group R20, R30, R40, and R50