1 Introduction

Multi-Depot Multiple Traveling Salesman Problem (MDMTSP) is a generalization of the well-known Traveling Salesman Problem (TSP), which consists of determining a set of routes for the salesmen that jointly visit a set of given clients, such that each salesman starts from and returns to one depot among a set of available depots and the total cost of the routes is minimized. We denote the set of clients by J and the set of potential depots by I. Let G=(V,E) be an undirected graph with V=I∪J, and E={(i,j):i∈V,j∈J}. The cost of any edge (i,j)∈E is denoted by c ij . Costs are assumed to be symmetric, i.e. c ij =c ji and routes visiting only one client, called return trips, are allowed. This problem has some applications as in the motion planning of a set of unmanned aerial vehicles (Yadlapalli et al. 2007, 2009, Malik et al. 2007; Rathinam et al. 2007) and the routing of service technicians where the technicians are leaving from multiple depots (Parragh 2010). If costs satisfy the triangular inequality, it is easy to show that there is always an optimal solution in which at most one route will start and end at each depot. Therefore, in this case the TSP reduces to the MDMTSP with |I|=1, so this problem is NP-hard.

The TSP is undoubtedly one of the most widely studied problems in the area of combinatorial optimization and there are a lot of literature reviews on it, see for example Gutin and Punnen (2002) and Applegate et al. (2006). We concentrate here on reviewing the literature on problems nearer to the MDMTSP.

As far as we know, there is no reference in the literature that deals with the MDMTSP as we define it in this paper, and the literature on similar problems is very scarce. The nearest problem to the MDMTSP is the Generalized Multiple Depot, Multiple Traveling Salesman Problem (GMTSP), studied by Malik et al. (2007), in which there are m salesmen, located at different depots, but at most p of them can be used. They assume that the costs are symmetric and satisfy the triangular inequality and propose a 2-approximation algorithm. Yadlapalli et al. (2009) study a variant of the GMTSP where each route must contain at least three nodes and propose a formulation for the GMTSP using binary variables and a lagrangean relaxation in the same spirit as Held-Karp’s method for the TSP. This method combined with subgradient optimization allows them obtaining an improved lower bound. A lagrangean heuristic based on this method is also proposed. They present computational results for instances with a number of nodes between 15 and 45 and a number of salesmen between 3 and 10. Yadlapalli et al. (2007) study the same problem with asymmetric costs and allowing trips with two nodes. They also present a binary formulation, a similar lagrangean relaxation and lagrangean heuristic that is applied to a set of instances with up to 50 nodes and 7 salesmen.

Bektas (2006) presents an overview of the Multiple Traveling Salesman Problem (mTSP) and some of its variants, including the multi-depot case. In the mTSP there are m salesmen that have to visit a set of customers from a single depot and every salesman must visit at least one customer. Bektas (2006) reviews the applications, exact and heuristic solution procedures and transformations to the TSP for these problems, although the review concentrates on the mTSP.

Kara and Bektas (2006) propose integer formulations with a polynomial number of constraints for the mTSP and for a multi-depot mTSP that is denoted by MmTSP. In the MmTSP there are m i salesmen located at each depot i, all the salesmen have to be used and the number of customers visited by a salesman must lie between given upper and lower bounds. They study two variants of the MmTSP: the fixed destination MmTSP in which the salesmen have to return to their original depots, and the nonfixed destination MmTSP in which the salesmen do not have to return to their original depots but the number of salesmen at each depot should remain the same as it was at the beginning. The proposed formulations are tested on a large set of randomly generated instances with the number of nodes being 100 or 120, the number of depots 3, 4 or 5 and up to 2 salesmen at each depot. All the instances were optimally solved with a time limit of 3 hours. GuoXing (1995) proposed a polynomial transformation of the MmTSP with asymmetric costs into an asymmetric TSP; this transformation cannot be adapted easily to the MDMTSP that we study in this paper because it uses the fact that in the MmTSP the number of salesmen used at each depot is known. Kara and Bektas (2006) have also tried to use this transformation to solve the MmTSP and conclude that it is preferable to solve the MmTSP directly. Benavent and Martínez (2011) present a polynomial transformation of the symmetric MDMTSP to the symmetric TSP, assuming that the costs satisfy the triangular inequality.

The MDMTSP can also be considered as a special case of other routing problems in which the vehicles have limited capacities. Multi-Depot Vehicle Routing Problem (MDVRP) consists of finding a set of routes based at a set of given depots to serve the demand of a set of customers with vehicles of limited capacity. Laporte et al. (1988) study different variants of this problem with asymmetric costs and propose a Branch-and-Bound algorithm that solves instances with up to 80 customers and 3 depots. Laporte et al. (1984) propose a Branch-and-bound algorithm for the symmetric case. Recently, Baldacci and Mingozzi (2009) have designed an exact solution framework to solve different routing problems that can be applied to the MDVRP and solve instances with up to 200 nodes and 4 depots. Several heuristics have been proposed for the MDVRP, among which we can mention the tabu-search of Cordeau et al. (1997).

The Location Routing Problem (LRP) generalizes the MDVRP in the sense that there are opening costs for the depots and, in addition to the vehicles, the depots can also have a limited capacity. Exact methods for the LRP are the Branch-and-Cut algorithms of Laporte et al. (1986) and of Belenguer et al. (2011), the last one having been able to solve instances with up to 50 customers and 5 possible depots. A lot of heuristic procedures exist for the LRP, one of the most effective being that proposed by Prins et al. (2007).

In the Plant-cycle Location Problem (PCLP) introduced by Labbé et al. (2004), salesmen are substituted by plants; there are assignment costs of the clients to the plants and opening costs for the plants. The goal is to assign the clients to the plants and, for each plant, to find a cycle containing the plant and the clients assigned to it, if any, in such a way that the sum of the routing costs, opening costs and assignment costs is minimized. They present a Branch-and-Cut algorithm that solves real-world data instances with up to 120 clients and 16 potential plants.

As far as we know, there is no polyhedral study of any of these multi-depot problems. In this paper we present an integer formulation of the MDMTSP and study the associated polyhedron. This study is the basis of a Branch-and-Cut algorithm that optimally solves large MDMTSP instances. One of our motivations for studying the MDMTSP is to contribute to the study of other multi-depot routing problems. We hope that the results we obtain for the MDMTSP will be useful in the resolution of more realistic routing problems like the MDVRP and the LRP.

The remainder of this article is organized as follows: In Sect. 2 the MDMTSP is formulated as an integer lineal program, and the notation and some basic results that will be used throughout the paper are introduced. In Sect. 3 we define the polyhedron associated with the MDMTSP and derive some facet-defining results including the study of the inequalities present in the formulation, the inequalities derived from the TSP, and two new families of valid constraints. A Branch-and-Cut algorithm based on the polyhedral description of the MDMTSP is described in Sect. 4. Section 5 presents computational results on two sets of instances.

2 Integer formulation of the MDMTSP

Recall that the MDMTSP is defined on a set of clients J and a set of potential depots I. Unless otherwise stated, we will denote: |J|=q, and |I|=p and assume that p≥1 and q≥1. Let G=(V,E) be an undirected graph where V=I∪J, and E={(i,j):∀i∈V,∀j∈J} (note that E does not include any edge between depots). The cost of edge e=(i,j) is denoted by c ij =c e . A set of routes such that each route contains exactly one depot and each customer is visited exactly once by the set of routes is called a MDMTSP solution. Each route is assumed to be performed by a salesman or, equivalently, by a vehicle. Throughout the paper, the MDMTSP defined on the set of potential depots I and set of clients J will be denoted by MDMTSP(I,J).

For each edge e=(i,j),i,j∈J, we define one binary variable x ij which takes the value 1 if the edge e is traveled by one route and 0 otherwise. For each edge e=(i,j),i∈I,j∈J we define a variable x ij which takes the value 2 if one vehicle does a trip between depot i to client j and immediately comes back to the depot (this is called a return trip), the value 1 if the edge e is traveled once by one vehicle, and 0 otherwise. For two node subsets S,S′⊆V, define (S:S′)={(i,j):i∈S,j∈S′}. Given a node subset, S⊆V, let us denote δ(S)=(S:V\S) and γ(S)={(i,j)∈E:i,j∈S}. If S={v}, we simply write δ(v) instead of δ({v}). Finally, for F⊆E, define x(F)=∑(i,j)∈F x ij . We simply write x(S:S′) instead of x((S:S′)). We propose the following formulation for the MDMTSP:

(1)
(2)
(3)
(4)
(5)
(6)

Degree equations (1), ensure that all the clients are visited exactly once by the set of tours. Inequalities (2) are the very well-known subtour elimination inequalities. Inequalities (3), called path elimination constraints, were introduced by Laporte et al. (1986) and modified by Belenguer et al. (2011). These inequalities prevent solutions that include a path starting at one depot and ending at a different one. Thus, a solution including a path i 1,j 1,…,j t ,i 2, where i 1,i 2∈I, and j 1,…,j t ∈J,t≥3 violates inequality (3) with I′={i 1},S={j 2,…,j t−1},j=j 1, and l=j t . Let us show that these inequalities are valid for the MDMTSP. Note first that any feasible MDMTSP solution satisfies x(γ(S∪{j,l}))≤|S|+1 because a subtour that only contains customers is forbidden. Consider two cases:

  1. (a)

    If x(γ(S∪{j,l}))=|S|+1 then the solution contains a path where all the customers in S∪{j,l} are consecutive. Therefore, neither j nor l are visited by return trips, so ∑ i∈I′ x ij ≤1 and ∑ k∈I\I′ x kl ≤1. Note that ∑ i∈I′ x ij =∑ k∈I\I′ x kl =1 cannot hold, because it would mean that the solution contains a path starting at a depot in I′ and ending at a depot in I\I′, which is forbidden. Then, ∑ i∈I′ x ij +∑ k∈I\I′ x kl ≤1 holds and the inequality (3) is satisfied.

  2. (b)

    Let us assume that x(γ(S∪{j,l}))≤|S|. Then, if ∑ i∈I′ x ij +∑ k∈I\I′ x kl ≤3 the inequality (3) is clearly satisfied. On the other hand, if ∑ i∈I′ x ij +∑ k∈I\I′ x kl =4, it means that customers j and l are visited by different return trips, so there exists no edge in the solution with one endpoint in S and the other in {j,l}, so x(γ(S∪{j,l}))=x(γ(S))≤|S|−1 and (3) is satisfied.

Inequalities (4) are in the same spirit as (3) that are not valid if S={∅}. It can easily be checked that they are valid and avoid solutions containing a path that connects two different depots and visits only two clients.

This formulation allows solutions with paths connecting two depots and visiting only one client, called 2-paths. However, if one solution of the MDMTSP contains a 2-path i 1,j,i 2, where i 1,i 2∈I, and j∈J, then the solution which visits the client j by a return trip from the nearest depot does not have a greater cost, so this kind of solutions will never appear in an optimal solution.

3 The MDMTSP polyhedron

Denote by P (I,J) the polytope defined by the convex hull of feasible solutions of the MDMTSP(I,J). That is:

$$P_{(I,J)} = \mathit{conv}\{ x \in\mathbb{R}^{|E|}:x\ \text{satisfies (1) to (6) and contains no 2-path}\} .$$

Let K n denote the complete graph on n vertices and let E n be its set of edges. Given a subset of edges A⊆E n , we denote by \(x^{A} \in\mathbb{R}^{|E_{n}|}\) the incidence vector associated with A, that is, \(x_{e}^{A} = 1\), if e∈A, and \(x_{e}^{A} = 0\) if e∉A. Then the polytopes associated to the Traveling Salesman Problem, P TSP(n), and the Hamiltonian Path Problem, P HP(n), are defined as follows:

Grötschel and Padberg (1979) proved that \(\dim( P_{\mathit{TSP}( n )} ) =\frac{n(n - 1)}{2} - n\) for all n≥3, while Queyranne and Wang (1993) proved that \(\dim( P_{\mathit{HP}( n )} ) = \frac{n(n - 1)}{2} - 1\). A null vector of any dimension will be denoted by 0 and given a set of vectors R,aff(R) will denote the affine hull of R.

Theorem 1

\(\dim( P_{( I,J )} ) = \frac{q^{2} - q}{2} + pq -q\).

Proof

The number of variables is \(\frac{q^{2} - q}{2} + pq\) and all solutions satisfy the q linearly independent degree equations (1), so \(\dim( P_{( I,J )} ) \le\frac{q(q - 1)}{2} + pq - q\). Let us denote this quantity by d, then we have to find d+1 affinely independent (or linearly independent, because 0∉aff(P (I,J))) MDMTSP solutions.

The first solution, denoted by B 1, consists of visiting each client with a return trip from depot d 1∈I. If q>1, there are \(\frac{q(q - 1)}{2}\) affinely independent Hamiltonian paths on the set of clients J and these paths are also linearly independent because 0∉aff(P HP(q)). By joining the terminal vertices of each path to depot d 1 we obtain the same number of MDMTSP(I,J) solutions. Let us denote this set of solutions by B 2.

If p>1, for each d i ∈I\{d 1} and each j∈J, we may build a solution that visits client j by a return trip from d i and all the other clients with a unique route from d 1. Thus, we may build q(p−1) additional MDMTSP(I,J) solutions. Let us denote this set of solutions by B 3. Thus, in total we have constructed d+1 solutions. These solutions are depicted as the block matrix of Fig. 1 whose rows correspond to the solution blocks and whose columns correspond to subsets of edges (for simplicity, the number of depots is assumed to be two in Fig. 1). A constant in a cell corresponds to a submatrix of the appropriate dimensions with all its entries equal to the constant. Note that the matrix is block-triangular and the diagonal blocks are non singular, so the whole matrix has full rank, thus proving that the d+1 solutions constructed are linearly independent.

Fig. 1
figure 1

MDMTSP solutions of Theorem 1

Full size image

 □

In the remainder of this section we study the conditions under which several families of inequalities (including those appearing in the MDMTSP formulation) define facets of P (I,J). The proofs of these results are rather technical and sometimes tedious. For this reason we chose not including all of them in this paper. The interested reader can find all the proofs in Benavent and Martínez (2011).

3.1 Trivial inequalities

In this section we study which trivial inequalities are facet-inducing inequalities for the MDMTSP(I,J) polyhedron.

Theorem 2

If q≥4, the inequality x e ≥0 defines a facet of P (I,J) for each e∈γ(J).

Proof

See Benavent and Martínez (2011). □

Inequalities x e ≤1,e∈γ(J) are a particular case of subtour elimination constraints (2) with |S|=2, and are studied in Sect. 3.4.

Theorem 3

If q≥4, the inequality x e ≥0 defines a facet of P (I,J) for each e∈(I:J).

Proof

See Benavent and Martínez (2011). □

For any e=(i,j)∈(I:J), the inequality x e ≤2 does not define a facet of P (I,J) because any solution satisfying x e =2 also satisfies x jl =0, for all l∈J, which implies that the dimension of the face induced by the inequality x e ≤2 is less than dim(P (I,J))−1 if q>2.

3.2 Depot lifting

Let fx≥f 0 be a valid inequality for MDMTSP(I,J). An inequality f ∗ x≥f 0 for the MDMTSP(I∪I′,J), with |I′|≥1, is said to have been obtained from fx≥f 0 by lifting depot d 0∈I to the set of depots I′, if:

$$f_{lj}^{*} = \left\{ \begin{array}{l@{\quad }l} f_{d_{0}j}&\forall( l,j) \in(I':J) \\ f_{lj} &\forall(l,j) \notin(I':J). \\\end{array}\right.$$

Note that the edges incident with the new depots have the same coefficients in the lifted inequality as the corresponding edges incident with depot d 0.

The lifted inequality f ∗ x≥f 0 is valid for the MDMTSP(I∪I′,J) because if a solution y ∗ existed such that f ∗ y ∗<f 0, we could build a solution y for the MDMTSP(I,J) by changing all the edges incident with depots in I′ by the corresponding edges incident with depot d 0, and fy=f ∗ y ∗<f 0, which contradicts that fx≥f 0 is valid. Theorem 4 shows that the property of being facet-inducing is also inherited by the lifted inequality.

Theorem 4

Let ax≥a 0 be a non-trivial inequality that defines a facet of P (I,J). Then, an inequality obtained from ax≥a 0 by lifting depot d 0∈I to the set of depots I′ defines a facet of P (I∪I′,J).

Proof

See Benavent and Martínez (2011). □

3.3 Path elimination constraints

In this section we prove that path elimination constraints (3) define facets of P (I,J). Path elimination inequalities (4) are also facet-inducing for P (I,J), but the proof is very similar and is omitted here.

In the proof of the next and subsequent theorems, we use a similar strategy: most of the solutions are generated by blocks, where each block B k ,k=1,2,… , contains a set of solutions that use the edges of a set, say E k , which is not used by the solutions of the preceding blocks. Furthermore, each solution of block B k uses a single edge of E k that is not used by any other solution of the same block, thus making it evident that all the solutions are linearly independent. We denote by r k the rank of the matrix formed by the corresponding solution vectors of block B k restricted to E k . To facilitate understanding, a representative solution of each block is depicted in a figure (like Fig. 2). We use the following convention in the pictures: solid edges correspond to edges that are fixed in the block, while pointed and dashed edges may change in each solution of the block; a dashed edge indicates an edge that belongs to only one solution of the block. Finally, return trips are depicted by a line with a double arrow.

Fig. 2
figure 2

Block solutions of Theorem 5

Full size image

Theorem 5

Let j,l∈J,I′⊂I, and S⊆J\{j,l} such that S≠∅,I′≠∅ and I\I′≠∅. Then the path elimination inequality

$$\sum _{i \in I'}x_{ij} + 2x( \gamma( S \cup\{ j,l \} )) + \sum _{k \in I\backslash I'}x_{kl} \le 2| S | + 3\quad \text{defines a facet of}\ P_{(I,J)}.$$

Proof

Thanks to the depot lifting Theorem 4 we may assume that |I|=2, with |I′|=1 and |I\I′|=1. Let d and h be the depots in I′ and I\I′ respectively, and define T=S∪{j,l}, and q′=|T| (note that q′≥3). We will prove the theorem by assuming that J\T≠∅, in the case where J=T the proof is very similar and is omitted here. Let F be the face induced by the path elimination inequality (3). We have to build \(\frac{q^{2} + q}{2}\) linearly independent MDMTSP(I,J) solutions of F.

To build the first block B 1, we consider solutions where all the clients in J\T are visited from depot d by return trips and clients in T are visited from depot d in the same route. Inequality x dj ≤1 induces a facet of the polytope associated with the TSP of node set T∪{d} (Grötschel and Padberg 1979). Then there are \(r_{1} = \frac{q'^{2} + q'}{2} - q' - 1\) linearly independent routes using the edge (d,j) and visiting all the clients in T (see Fig. 2). Note that each one of these solutions are in F because they use the edge (d,j) and satisfy x(γ(S∪{j,l}))=|S|+1. In this block E 1=γ(T∪{d}).

The next block of solutions B 2 uses one of the routes used in B 1 containing the node set T∪{d}, and different ways of visiting the clients in J\T from depot d (see Fig. 2 (B 2)). Note that the solutions in B 1 do not use any edge of γ(J/T). Given that |J\T|=q−q′, there are \(r_{2}= \frac{( q - q' )(q - q' - 1)}{2}\) linearly independent Hamiltonian paths on the node set J\T, which can be converted into routes by connecting their extremes nodes to depot d. Note that E 2=γ(J/T) and that the components of these solutions that correspond to edges in E 2 form a non-singular matrix.

Block B 3 contains solutions that each use a different edge (l,t) for every t∈J\T. See Fig. 2 (B 3). These solutions are all in the face F and the restriction to the set of edges E 3=({l}:J/T) is the identity matrix, so r 3=q−q′.

The next block, B 4, uses edges with one endpoint in S and the other in J\T. For every pair of clients s∈S, and t∈J\T we may build a solution such as the one depicted in Fig. 2 (B 4). In this case E 4=(S:J/T) and r 4=(q′−2)(q−q′). Block B 5 contains solutions as depicted in Fig. 2 (B 5). In each solution a client in J\T is visited with a return trip from depot h while the remaining clients in J\T are visited by return trips from depot d. For this block, E 5=({h}:(J\T)) and r 5=q−q′. Block B 6 contains only one solution where client l is visited by a return trip from depot h so E 6={(l,h)} and r 6=1.

Note that all the solutions in blocks B 1 to B 6 satisfy the equation x dj =1. The next solution is depicted in Fig. 2 (x ∗) and satisfies x dj =2; therefore, it is affinely independent of them (and linearly independent, because 0∉aff(MDMTSP(I,J))). Up to now we have built

$$r_{1} + r_{2} +r_{3} + r_{4} + r_{5} + r_{6} + 1 = \frac{q^{2} - q + 2}{2}\quad \text{affinely independent solutions}.$$

The next block, B 7, contains r 7=q′−1 solutions each one using an edge of E 7=({h}:S∪{j}). Finally, the r 8=q−q′ solutions of block B 8 use different edges of E 8=(J\T:{j}) (see Fig. 2 (B 7 and B 8)). It can easily be checked that \(\frac{q^{2} - q + 2}{2} +r_{7} + r_{8} = \frac{q^{2} + q}{2}\), so the proof is completed. □

3.4 TSP derived inequalities

Given the great similarity between the MDMTSP and the classical TSP it is natural to ask if valid and facet-inducing inequalities for the TSP can be used to derive valid and facet-inducing inequalities for the MDMTSP. In this section we show that the answer is indeed affirmative, in particular, facet-inducing inequalities of the TSP polytope written in tight triangular form (TT form) (see Naddef and Rinaldi 1993) can be used to derive facet-inducing inequalities of the MDMTSP polytope P (I,J).

Given a TSP instance, we will denote its corresponding node set by V TSP . We say that a valid inequality ax≥a 0 for the TSP is written in TT-form if for all i,j,k∈V TSP ,a ik ≤a ij +a jk , and for all i∈V TSP , there are j,k∈V TSP such that a jk =a ij +a ik .

Consider the MDMTSP(I,J), and let d 1∈I. Let a′x≥a 0 be a valid and non-trivial inequality for the TSP defined on the node set J∪{d 1}, then the MDMTSP inequality ax≥a 0, where \(a_{ij} = a'_{ij}\forall i,j \in J\), and \(a_{ij} =a'_{d_{1}j}\forall i \in I\) and j∈J is said to be an extended inequality from a′x≥a 0.

Theorem 6

Let ax≥a 0 be an MDMTSP extended inequality from a′x≥a 0, which is a valid and non-trivial inequality for the TSP written in TT form. Then the inequality ax≥a 0 is valid for the MDMTSP.

Proof

Suppose that ax≥a 0 is not valid for the MDMTSP, so there is one solution x ∗ satisfying ax ∗<a 0. Given that \(a_{ij} = a'_{d_{1}j}\forall i \in I;\forall j \in J\), we can assume that the solution x ∗ uses only the depot d 1∈I, because if x ∗ used other depots we can change the edges incident with these depots for edges incident with d 1. Furthermore, we can assume that x ∗ uses only one route: if, for instance, x ∗ contains two routes (d 1,j 1,…,j r ,d 1) and (d 1,l 1,…,l r′,d 1), we could merge them into a single route (d 1,j 1,…,j r ,l 1,…,l r′,d 1) that would also violate the constraint ax≥a 0 because the coefficients satisfy the triangular inequality. However, if we discard the depots I\{d 1} in x ∗, we obtain a solution for the TSP defined on the node set J∪{d 1} that violates a′x≥a 0, which is a contradiction. □

Theorem 7

Let ax≥a 0 be an MDMTSP extended inequality from a non-trivial inequality for the TSP written in TT form, a′x≥a 0, that defines a facet of the TSP polytope. Then ax≥a 0 defines a facet of P (I,J).

Proof

Thanks to the depot lifting Theorem 4 we can assume that I={d 1}. Recall from the definition of extended inequality that a′x≥a 0 is an inequality for the TSP instance with V TSP =J∪{d 1}. Then, by hypothesis, a′x≥a 0 defines a facet of P TSP(q+1), so there are \(\frac{(q + 1)q}{2} - q - 1\) linear independently TSP tours satisfying a′x=a 0. These tours are also MDMTSP({d 1},J) solutions satisfying ax=a 0, and these solutions also verify equation x(δ(d 1))=2. Given that inequality a′x≥a 0 is written in TT form, there are two nodes, say k and l, such that \(a'_{kl} = a'_{d_{1}k} + a'_{d_{1}l}\). Let x be a TSP solution satisfying a′x=a 0 such that x kl =1 (such a solution exists because a′x≥a 0 is non-trivial). If we substitute edge (k,l) by edges (d 1,k) and (d 1,l) in x, we obtain a MDMTSP({d 1},J) solution, say x′, with two routes based at depot d 1. This solution satisfies ax′=a 0 and x′(δ(d 1))=4, so it is affinely independent with the preceding ones and given that \(0 \notin \mathit{aff}( P_{(\{ d_{1}\} ,J)} )\), it is also linearly independent. Thus we have \(\frac{(q + 1)q}{2} - q\) linearly independent solutions of \(P_{(\{ d_{1}\} ,J)}\) and the proof is complete. □

Note that the condition stating that the TSP inequality is in TT form is too restrictive; in fact the extended inequality is facet-inducing for the MDMTSP(I,J) if the TSP inequality is facet-inducing for the TSP polyhedron and there is an MDMTSP(I,J) solution satisfying ax=a 0 and x(δ(d))>2 for a depot d∈I.

There are many families of valid and facet-inducing inequalities for the TSP that can be written in TT form and that can be used to derive valid and facet-inducing inequalities for the MDMTSP. In particular, it is known that TSP subtour elimination inequalities can be written in TT form and are facet-inducing of P TSP(n) if n≥4. The corresponding extended inequalities for the MDMTSP are, in fact, the subtour elimination inequalities (2). Therefore, as a consequence of Theorem 7, inequalities (2) are facet-inducing for P (I,J) if q≥3.

Comb inequalities are other facet-inducing inequalities for the TSP that are very important, especially when solving the TSP by Branch-and-Cut. They were introduced by Chvátal (1973), and Grötschel and Padberg (1979), and can be written in TT form. A comb inequality is usually defined by a set H⊂V TSP , called handle, and an odd number t≥3 of vertex subsets {T 1,…,T t }, called teeth, such that:

$$\begin{array}{l@{\quad }l}\text{(C.1)} &H \cap T_{i} \ne\emptyset\quad \forall i = 1, \ldots,t,\\[2mm]\text{(C.2)} &T_{i}\backslash H \ne\emptyset\quad \forall i = 1, \ldots,t,\\[2mm]\text{(C.3)}& T_{i} \cap T_{j} = \emptyset \quad 1 \le i < j \le t.\end{array}$$

Conditions (C.1), (C.2) say that every tooth T i intersects the handle H and condition (C.3) that no two teeth intersect. The corresponding comb inequality in TT form is:

$$ x\left( \delta( H ) \right) + \sum _{j =1}^{t}x\left( \delta( T_{j} ) \right) \ge 3t + 1.$$
(7)

Grötschel and Padberg (1979) showed that (7) define a facet of P TSP(n) if n≥6. Given the instance MDMTSP(I,J), let H,T 1,…,T t be the handle and teeth, respectively, that define a comb inequality in the associated TSP instance with V TSP =J∪{d 1}. The corresponding extended inequality for the MDMTSP(I,J) can be written as in (7) and is facet-inducing for P (I,J). We will call these inequalities TSP-combs. Depending on which part of the comb contains node d 1 in the original TSP inequality, different types of TSP-combs are obtained for the MDMTSP:

  • If \(d_{1} \notin H \cup( \bigcup_{i = 1}^{t} T_{i} )\), then all the depots will be outside the TSP-comb, that is \(I \cap(H\cup( \bigcup_{i = 1}^{t} T_{i} ) = \emptyset\).

  • If \(d_{1} \in H\backslash( \bigcup_{i = 1}^{t} T_{i})\), then all the depots will be in the handle but in no tooth in the TSP-comb, that is \(I \subseteq H\backslash( \bigcup_{i = 1}^{t} T_{i})\).

  • If d 1∈T i ∩H for some i∈{1,…,t}, then all the depots will be in T i ∩H in the TSP-comb, that is I⊆T i ∩H for some i∈{1,…,t}.

  • If d 1∈T i \H for some i∈{1,…,t}, then all the depots will be in T i \H in the TSP-comb, that is I⊆T i \H for some i∈{1,…,t}.

3.5 New comb inequalities for the MDMTSP

As stated above, in the TSP-combs the whole set of depots I is contained in the same part of the structure of the comb. In this subsection we present two new families of inequalities that are also defined by a handle and a number of teeth, so they can be considered a kind of comb, but in these new combs, the depots may be simultaneously in different parts of the comb structure. These new constraints are closely related to the multi-depot characteristic of our problem and have been shown to be very useful in the Branch-and-Cut algorithm described in Sect. 4.

3.5.1 H-comb inequalities

This new inequality has the same expression as the usual comb inequality (7), but in this case the handle must contain at least one depot and at least one depot must be outside the comb. More precisely, the H-comb inequality is defined by a subset H⊂I∪J, called a handle, satisfying H∩I≠∅ and I\H≠∅, and an odd number of subsets of J,T 1,…,T t ⊆J,t≥1, called teeth, satisfying conditions (C.1), (C.2) and (C.3). The corresponding H-comb inequality for the MDMTSP(I,J) is (7).

Note that if I\H=∅ and t≥3, then the inequality is in fact a TSP-comb. On the other hand, if I\H=∅ and t=1, then the inequality (7) is not facet-inducing as all the solutions satisfying x(δ(H))+x(δ(T 1))=4 also satisfy the equation x(δ(H))=2, that cannot be generated as a linear combination of the degree equations (1) and the equation x(δ(H))+x(δ(T 1))=4. This is the same situation for the TSP in which a comb with one tooth is not a facet-inducing inequality.

Theorem 8

H-comb inequalities are valid for the MDMTSP.

Proof

Let H be the handle and T 1,…,T t be the teeth of the H-comb and let x be the vector associated with an MDMTSP solution. For each i=1,…,t, we define:

$$c_{i} = \left\{ \begin{array}{l@{\quad }l} 1& \text{if}\ x\ \text{contains at least one edge between}\ H \cap T_{i}\ \text{and}\ T_{i}\backslash H, \\ 0 & \text{otherwise}. \\\end{array} \right.$$

Obviously, \(\sum_{i = 1}^{t} c_{i} \le t\), and given that the teeth are pairwise disjoint, it holds that \(x( \delta( H ) ) \ge\sum_{i = 1}^{t}c_{i}\). Then \(x( \delta( H ) ) \ge 2\sum_{i = 1}^{t} c_{i} - \sum_{i =1}^{t} c_{i} \ge 2\sum_{i = 1}^{t} c_{i} - t\), and, since x(δ(H)) must be even and t is odd, we conclude that \(x( \delta( H ) ) \ge 2\sum_{i = 1}^{t} c_{i} - t + 1\). On the other hand, for each tooth T i , if c i =0, then x(δ(T i ))≥4, because both H∩T i and T i \H contain at least one client and no depot, we therefore conclude that x(δ(T i ))≥4−2c i . Adding these inequalities for all i=1,…,t to the above derived inequality for x(δ(H)), we obtain inequality (7). □

Note that the number of teeth can be equal to one in the H-combs. We have proved that H-comb inequalities with at least three teeth are facet-inducing for the MDMTSP polyhedron but the proof is omitted here for the sake of brevity.

Theorem 9

H-comb inequalities (7) with at least 3 teeth (t≥3) define facets of P (I,J).

Proof

See Benavent and Martínez (2011). □

H-comb inequalities with only one tooth are also facet-inducing of the MDMTSP(I,J) polyhedron under mild conditions (see Benavent and Martínez 2011). Here we present the proof for the case where the tooth contains only one client outside the handle.

Theorem 10

H-comb inequalities with one handle H and one tooth T, such that |T\H|=1 are facet-inducing for P (I,J).

Proof

Let us denote the only client in T\H by k. Thanks to the depot lifting theorem we can assume that there is only one depot in the handle, say d, and one depot outside the handle, say h. Then we have to build \(\frac{q^{2} + q}{2}\) linearly independent MDMTSP solutions satisfying (7) with equality.

Let us denote by q′ the number of clients in J\(H∪T). The first block B 1 contains solutions where clients in H∪T are visited from depot d and the clients outside the comb are visited from depot h. Taking into account the dimension of the polyhedron P ({h},J\(H∪T)), there are \(b'_{1} =\frac{q'( q' - 1 )}{2} + 1\) linearly independent solutions that visit the clients in J\(H∪T) using edges in γ({h}∪J\(H∪T)), and these solutions can be completed with a fixed route based at depot d that visits the clients of H∪T, like the one depicted in Fig. 3 (B 1). On the other hand, if we assume that |T∩H|≥2, given that the subtour inequality x(δ(T∩H))≥2 is facet-inducing for the polytope P ({d},J∩(H∪T)), there are \(b''_{1} = \frac{( q - q')(q - q' - 1)}{2}\) linearly independent solutions that use edges from γ(H∪T); all of these solutions can be completed with a fixed route visiting all the clients in J\(H∪T) from depot h. It is easy to see that by combining these two sets of solutions we obtain \(r_{1} = b'_{1} + b''_{1} - 1\) linearly independent solutions that satisfy (7) with equality. Note that in the case where |T∩H|=1, every solution in the polyhedron P ({d},J∩(H∪T)) can be used to visit the clients of J∩(H∪T), so in this case we have in fact one more solution, r 1+1.

Fig. 3
figure 3

Block solutions of Theorem 10

Full size image

In B 2 we build r 2=q′+1 solutions using exactly one edge in the set E 2=({k}:V\(H∪T)). The first solution visits k with a return trip from h, and the remaining solutions use edge (k,h) and one edge (k,t), where t∈J\(H∪T) (see Fig. 3 (B 2)). Block B 3 contains r 3=(q′+1)|T∩H| solutions, one solution for each edge with one endpoint in T∩H and the other in V\(H∪T), see Fig. 3 (B 3). Block B 4 contains solutions using edges of E 4=(J∩H\T:V\(H∪T)), that is r 4=(q′+1)|H\T| solutions (note that r 2+r 3+r 4=(q′+1)(q−q′) solutions). Finally, block B 5 contains q′ solutions using edges of E 5=({d}:J\(H∪T)), see Fig. 3 (B 5). Note that all the solutions constructed so far satisfy the equation x(δ(T∩H))=2. If |T∩H|≥2, we can construct an additional solution x′ that satisfies x(δ(T∩H))=4, see Fig. 3 (x′), so it is linearly independent with all the previous solutions (if |T∩H|=1 this solution is not needed, as stated before). Therefore, we have \(b'_{1} + b''_{1} + ( q' + 1 )( q - q' ) + q' = \frac{q^{2} +q}{2}\) and the proof is complete. □

3.5.2 T-comb inequalities

These inequalities also have a similar structure to the combs but in this case all the teeth must contain at least one depot. The T-comb inequality is defined on a subset of clients H⊂J, called the handle, and t≥1 subsets of I∪J,T 1,…,T t , called teeth, satisfying conditions (C.1), (C.2), (C.3), and:

$$\begin{array}{l@{\quad }l}\text{(C.4)}& T_{i} \cap I \ne\emptyset\quad \forall i \in\{ 1, \ldots,t\},\\[4mm]\text{(C.5)}& H\backslash\bigcup_{i = 1}^{t} T_{i} \ne\emptyset,\quad \text{and}\\[4mm]\text{(C.6)}& I\backslash\bigcup_{i = 1}^{t} T_{i} \ne\emptyset.\end{array}$$

The T-comb inequality is:

$$ x\left( \delta( H ) \right) + \sum _{j =1}^{t}x\left( \delta( T_{j} ) \right) \ge 2t + 2.$$
(8)

Note that the number of teeth can be even and the right-hand side of the inequality is different to that in the preceding comb inequalities.

Theorem 11

T-comb inequalities are valid for the MDMTSP.

Proof

We prove the validity by induction on t, the number of teeth. If t=1 the inequality is the same as the H-comb inequality with one tooth which has been shown to be valid. Let us assume that the inequality is valid for H-combs with less than t teeth, and let us show that it is valid for an H-comb with t teeth, like in (8). Consider a feasible solution that satisfies x(δ(T t ))≥2, then, given that the comb inequality with the same handle and the first t−1 teeth is valid, it is obvious that (8) is satisfied by this solution. Let us now consider a feasible solution for which x(δ(T t ))=0 holds, and consider now a comb with the first t−1 teeth and handle H′=H\(T t ∩H), then, by the induction hypothesis \(x( \delta( H' ) ) + \sum _{j =1}^{t - 1}x( \delta( T_{j} ) ) \ge 2t\). Note that x(δ(H))=x(δ(H′))+x(T t ∩H:V\H′)−x(T t ∩H:H′); if x(δ(T t ))=0, then x(T t ∩H:H′)=0 and all the clients in T t ∩H will be visited from a depot in T t \H so x(T t ∩H:V\H′)≥2, which implies that x(δ(H))≥x(δ(H′))+2. This inequality together with the one satisfied by the induction hypothesis, implies that this feasible solution also satisfies (8). □

Theorem 12

T-comb inequalities (8) with handle H and teeth T 1,…,T t ,t≥2 are facet-inducing for P (I,J).

Proof

See Benavent and Martínez (2011). □

4 Branch & Cut algorithm

The MDMTSP formulation and the additional constraints described in Sect. 3 have been embedded in a cutting plane algorithm to produce a valid lower bound (LB) for the problem. This cutting plane is the core of a Branch-and-Cut algorithm for finding the optimal solution of the MDMTSP. The cutting plane algorithm is an iterative procedure that works as follows. Initially, we build a linear program (LP) including the objective function, the degree constraints and the bounding inequalities 0≤x ij ≤1, if i,j∈J, and 0≤x ij ≤2, if i∈I,andj∈J. At each iteration, we solve the current LP, look for a set of valid inequalities that are violated by the optimal LP solution, add them to the LP and proceed as before. If in an iteration no violated inequality is found and the LP solution is integer, then the optimal solution has been found; otherwise, we resort to branching.

4.1 Separation algorithms

Separation algorithms try to find valid inequalities of a given family that are violated by the current LP solution. Let \(\bar{x}\) be the optimal solution of the current LP. Denote by \(G(\bar{x})\) the support graph associated with a given LP solution \(\bar{x}\), that is, \(G(\bar{x})\) is the weighted graph induced by the edges e such that \(\bar{x}_{e} > 0\). The graph that results from shrinking all the possible depots I of the support graph in a single vertex will be denoted by \(G'(\bar{x})\).

As mentioned before, some of the inequalities for the MDMTSP also appear in the formulation of other related problems. In those cases we have used separation algorithms already designed for those inequalities. Thus, the subtour elimination inequalities were separated using procedures designed for the TSP: the shrinking procedure described by Padberg and Rinaldi (1990), and the function CCtsp_exact_subtours of the Concorde callable library (http://www.tsp.gatech.edu/concorde/DOC/concorde_funcs.html) that implements an exact separation algorithm consisting of finding a minimum weighted cut in \(G'(\bar{x})\).

The shrinking procedure is also used to separate the path elimination constraints (3) and (4). This procedure is based on the idea of sequentially shrinking edges whose weight is equal to one in the support graph. In our problem, only edges with both end-points in J were shrunk. If the shrunk graph contains a vertex, say v, linked to more than one depot, we check whether a path elimination constraint is violated. Note that vertex v will in fact correspond to a path in \(G(\bar{x})\) where all the edges have weight 1. Then identifying the extremes of this path as the clients j and l, is quite easy to check if there is a subset of depots I′ for which the corresponding path elimination inequality is violated by \(\bar{x}\). Note that if \(\bar{x}\) is integer this procedure will find a violated path constraint if any exists.

Two heuristic procedures were used to separate TSP-comb inequalities in the graph. The first one is the routine COMBSEP_SeparateCombs of Lysgaard’s CVRPSEP library (http://www.hha.dk/~lys/CVRPSEP.htm) that is devoted to separating strengthened combs in the CVRP. It has been used in our problem by simply defining the capacity of the vehicles as a large number. The second one adapts the procedure proposed by Grötschel and Holland (1987) for the TSP to work on graph \(G(\bar{x})\), which contains several depots. This procedure may find not only violated TSP-combs, but also violated H-combs.

Finally, we have implemented two new heuristic algorithms to separate T-comb inequalities. The first one looks for violated T-combs with only one tooth and works as follows. First, the tooth T is built by starting with a set that contains only one depot, and then customers are added to the tooth one by one in such a way that, at each step, \(\bar{x}(\delta( T ))\) is as small as possible. Whenever a set T is found such that \(\bar{x}( \delta( T ) ) < 2\), we look for an appropriate handle H starting with H=T∩J and adding customers to it sequentially in such a way that \(\bar{x}(\delta( H ))\) is kept as small as possible. If a handle is found such that \(\bar{x}( \delta( H ) ) +\bar{x}( \delta( T ) ) < 4\), we get a violated T-comb inequality. This procedure is applied for each depot and at most one violated T-comb inequality is generated for each depot. The second heuristic looks for T-combs with several teeth. First, a set of teeth are built in the same way as before, starting each tooth with a different depot. Then, for every subset of this set of teeth such that: (i) they are pairwise disjoint, (ii) belong to the same connected component of \(G(\bar{x})\), and (iii) do not together contain all the customers of that connected component, an appropriate handle H is built. The construction of H starts with the set of customers of the corresponding connected component and customers are removed sequentially in such a way that \(\bar{x}(\delta( H ))\) is kept as small as possible (the customers of the teeth are not removed). Every time a customer is removed, the T-comb inequality is checked.

4.2 Branch-and-Cut strategies

The separation procedures were called in the following order: (1) shrinking procedure for subtour and path elimination inequalities, (2) exact procedure for subtour inequalities, (3) procedure to look for T-combs with one tooth, (4) procedure to look for T-combs with several teeth, (5) modified Grötschel and Holland procedure for TSP-combs and H-combs, (6) Lysgaard procedure for combs. Whenever at least one violated inequality is found by any procedure, the following ones are not called and the LP is re-optimized.

The cutting plane algorithm was implemented in C++ and embedded in a Branch-and-Cut procedure using the commercial solver CPLEX 9 through Concert Technology. The branching variable and the next node to separate are determined by CPLEX using the Strong Branching strategy.

5 Computational results

The Branch-and-Cut code written in C++ was run on an Intel Core i5 at 2.4 GHz with 4GB of RAM under Windows 7, and applied to two sets of Euclidean instances. The first set contains 30 instances that have been generated from LRP instances by simply considering a very large capacity for the vehicles and depots and zero opening costs for the depots. The complete set of instances can be downloaded from http://prodhonc.free.fr/ (see Instances Benchmarks 1 and 2). Some of these instances become identical when the capacity of the vehicles is increased and they were discarded. The first numbers in the name of these instances are the number of customers and the number of potential depots, respectively; furthermore, the name includes a suffix s∈{i,f} that indicates how traveling costs have been calculated: i for Euclidean distances multiplied by 100 and rounded up to the nearest integer, and f for not rounded Euclidean distances. This first set contains instances with a number of customers from 20 to 200 and a number of potential depots from 5 to 10. The second set of instances were generated from two TSP instances of the TSPLIB (Reinelt 1991): a280 and bier127, with 280 and 127 nodes respectively. From each of these instances four MDMTSP instances were generated by randomly choosing 1, 5, 10, and 25 nodes as potential depots. Note that the instances with one depot are equivalent to TSP instances, respectively. Traveling costs are Euclidean distances rounded to the nearest integer in these instances.

Tables 1 and 2 show the results obtained by the Branch-and-Cut algorithm applied to the first and second sets of instances respectively. The first two columns give the instance name and the optimal cost (OPT). The next two columns display the total running time in seconds (Time), and the time spent to separate inequalities (TimeSEP), the remaining time having been spent to solve the LPs. The next three columns give the total number of nodes in the Branch-and-cut tree (BCnodes), the total number of constraints generated (Cuts) and the number of routes in the optimal solutions (Routes). Routes visiting only one customer from a depot that is located at the same point as the customer were discarded when counting the number of routes.

Table 1 Results of the Branch-and-Cut on LRP instances
Full size table
Table 2 Results of the Branch-and-Cut on TSP instances
Full size table

The results presented in Tables 1 and 2 indicate that the proposed Branch-and-Cut algorithm can solve instances involving more than 200 customers and up to 25 possible depots within modest computing times. Note that all the instances were solved with a maximum CPU time of 1297.5 seconds and 23 out of 30 instances were solved in the root node, including one instance with 275 customers. In general, instances obtained from the TSP seem to be easier than those obtained from LRP instances.

It is also interesting to see the contribution of the H-comb and T-comb constraints, which are completely new and specific to the MDMTSP, to strengthen the linear relaxation. We have made two versions of the cutting plane algorithm to study this contribution. The first version, called base, uses only the separation procedures for the subtour elimination, path elimination and TSP-comb constraints, and the second version, called base+nc, also includes the separation procedures for the new H-comb and T-comb constraints. The average results obtained by these two versions of the cutting plane algorithm are shown in Table 3. Here, LRPm and TSPm denote the sets of instances generated from LRP and TSP instances, respectively. Table 3 shows the average deviations in % (GAP) of the lower bound obtained by each version of the code to the optimal cost, the number of instances for which the corresponding lower bound was equal to the optimal cost (LBopt), and the average CPU time. Table 3 also shows the average gap closed by the new constraints which is computed, for each instance, as 100(LB1-LB0)/(OPT-LB0), where LB0 is the lower bound obtained with the base code, and LB1 is the lower bound obtained by the code base+nc that includes the new constraints. Note that the gap closed by the new constraints in each set of instances is 93.6% and 80.43% on average, respectively. Furthermore, the lower bound obtained by the base+nc code is equal to the optimal cost in 26 instances, while the base code reaches the optimal cost only in four instances. These results show that the new constraints are very useful in closing the integrality gap because they are specific for the case where several depots are available; we hope that they will also be useful in other multi-depot problems like the LRP and the MDVRP.

Table 3 The effect of using the new comb constraints
Full size table

6 Conclusions

We have presented what we believe to be the first polyhedral study of a multi-depot routing problem. An integer linear programming formulation including several classes of facet-defining inequalities was proposed, together with a Branch-and-Cut algorithm. The proposed approach was tested on two classes of instances. The largest solved involved 255 customers and 25 potential depots. We hope that the results presented in this paper could also help in the exact resolution of other multi-depot problems like the Multi-Depot Vehicle Routing Problem and the Location Routing Problem.