Performance Evaluation of Ant Colony Systems for the Single-Depot Multiple Traveling Salesman Problem

Abstract

Derived from the well-known Traveling Salesman problem (TSP), the multiple-Traveling Salesman problem (multiple-TSP) with single depot is a straightforward generalization: several salesmen located in a given city (the depot) need to visit a set of interconnected cities, such that each city is visited exactly once (by a single salesman) while the total cost of their tours is minimized. Designed for shortest path problems and with proven efficiency for TSP, Ant Colony Systems (ACS) are a natural choice for multiple-TSP as well. Although several variations of ant algorithms for multiple-TSP are reported in the literature, there is no clear evidence on their comparative performance. The contribution of this paper is twofold: it provides a benchmark for single-depot-multiple-TSP with reported optima and performs a thorough experimental evaluation of several variations of the ACS on this problem.

1 Introduction

The traveling salesman problem (TSP) is one of the most famous combinatorial optimization problems. The multiple traveling salesman problem (multiple-TSP) is an extension of this well-known problem that involves further a new parameter - the number of salesmen. It can accommodate easily related real-world problems, especially routing and scheduling problems. The problem is NP-hard and is difficult to solve. One solution is to transform the problem, with $m$ salesmen and $n$ cities, into a TSP with $n+m-1$ cities by adding $m-1$ artificial depots $n+1, ..., n+m-1$. The resulting TSP is highly degenerate and more difficult to solve than an ordinary TSP with the same number of cities.

There are various approaches in literature to solve variants of the multiple-TSP. A detailed overview of the problem’s variants and methods used for solving them is available in [1]. Exact algorithms, like cutting planes [2] or branch and bound [3] were developed, but they can obtain optimal solutions only for small size instances in acceptable time. Due to the combinatorial complexity of the problem, heuristics to solve real-world instances were also employed. For large dimensions of the problem, heuristic approaches like k-opt approach [4], or metaheuristics like Tabu Search [5], Genetic Algorithms [6–9], Ant Colony Optimization [10], Neural Networks [11] are necessary to solve it. In [12] two new swarm intelligence based metaheuristics, artificial bee colony and invasive weed optimization, are proposed for solving the single depot multiple-TSP. Another approach, relying on a market-based solution, is employed in [13] for a multiple-TSP with multiple depots, where agents and tasks operate in a market to achieve near-optimal solutions.

With a proven efficiency on the standard TSP, ant algorithms were also adapted for the multiple-TSP. In [14] the ant colony optimization is used to solve the multiple-TSP with the ability constraint. The problem imposes that the number of cities which are traveled by each salesman to be upper bounded by a value. The problem was converted to TSP. In [10] two objectives were considered: minimizing the total tour length of all the salesmen and minimizing the maximum tour length of each salesman. The ACO algorithm follows the MAX-MIN Ant System scheme and integrates a local improvement procedure. In [15] is presented an algorithm based on multiple artificial ant colonies, that cooperate by means of frequent pheromone exchanges in order to find a competitive solution to the multiple-TSP. A multi-depot variant of multiple-TSP is considered in [16], where lower and upper bounds are imposed on the number of cities visited in a tour and the objective is to minimize the total distance traveled by all the salesmen.

Another criterion, much less addressed, but important in real-world applications is the balancing of workloads amongst salesmen. Such a criterion is addressed in [17], where a team of ants construct in parallel solutions to the multiple-TSP with MinMax objective. In order to achieve balanced tours, the moving member of a team is chosen as being the one with the minimum route length. In [18], the authors present a comparison of evolutionary computation algorithms and paradigms for the euclidean multiple traveling salesman problem. The authors are concerned with the first level of optimization, the optimal subdivision of cities into groups. To this end, the chromosome representation makes use of the neighborhood attractor schema which is a variation of k-means. The shrink-wrap algorithm is used to determine the circuit path lengths. Another clustering approach to solve the multiple-TSP is proposed in [19]. The clustering algorithm minimizes the variation of distances traveled within each cluster. A good balance of workloads among clusters is achieved.

The current paper aims at proposing and evaluating several variations of the Ant Colony System (ACS) for the single-depot multiple-TSP. The paper is structured as follows. Section 2 defines the problem as an integer linear program (ILP) that can be solved to optimality with dedicated software. Section 3 reviews the standard formulation of the Ant Colony System. A number of 5 variants of the standard ACS adapted for the single-depot multiple-TSP problem are subsequently described in Sect. 4. Experiments and results are presented in Sect. 5.

2 The Single-Depot Multiple Traveling Salesman Problem

There are several integer linear programming formulations for the multiple-TSP. We have used the variant that restricts the minimal number of nodes that a salesman may visit [20]. Such restrictions appear in real-life applications where the purpose is to have a good balance of workloads for the salesmen.

Let $G=(V,A)$ be a directed graph where $V$ is the set of nodes and $A$ is the set of arcs and $C=(c_{ij})$ is the cost (distance) matrix associated with each arc $(i,j)\in A$. Let $n$ be the number of cities and $m$ be the number of salesmen. All salesmen are located at the depot city 1. They start and end at the same depot, and each other node is located in only one tour. The number of nodes a salesman can visit lies within a predetermined interval. The problem is to find the tours of each salesman such that the previous restrictions are satisfied and the overall cost of visiting all nodes is minimized.

The problem is formulated as the following:

$$\begin{aligned}&\text {min}&\sum _{(i,j)\in A} c_{ij}x_{ij} \end{aligned}$$

(1)

$$\begin{aligned}&\text {s.t.}&\sum _{j=2} x_{1j} =m \end{aligned}$$

(2)

$$\begin{aligned}&\sum _{j=2} x_{j1} =m \end{aligned}$$

(3)

$$\begin{aligned}&\sum _{i=1}^n x_{ij} =1, \; j=2, .., n \end{aligned}$$

(4)

$$\begin{aligned}&\sum _{j=1}^n x_{ij} =1, \; i=2, .., n \end{aligned}$$

(5)

$$\begin{aligned}&u_i +(L-2)x_{1i}-x_{i1} \le L-1, \; i=2, .., n \end{aligned}$$

(6)

$$\begin{aligned}&u_i +x_{1i}+(2-K)x_{i1} \ge 2, \; i=2, .., n \end{aligned}$$

(7)

$$\begin{aligned}&x_{1i}+x_{i1} \le 1, \; i=2, .., n \end{aligned}$$

(8)

$$\begin{aligned}&u_i-u_j+Lx_{ij}+(L-2)x_{ji} \le L-1, \; 2 \le i \ne j \le n \end{aligned}$$

(9)

$$\begin{aligned}&x_{ij} \in \{0,1\}, \; \forall (i,j) \in A . \end{aligned}$$

(10)

where $x_{ij}$ is a binary variable that is equal to 1 if the arc $(i,j)$ is contained in the optimal solution and 0 otherwise. $u_i$ denotes the number of nodes visited on that salesman’s path from the origin to node $i$, for any salesman, i.e. the position of node $i$ in a tour. $L$ is the maximum number of nodes a salesman may visit, and $K$ the minimum number of nodes a salesman must visit.

Constraints (2) and (3) ensure that exactly $m$ salesmen depart from and return to the depot. Constraints (4) and (5) are the degree constraints, i.e. exactly one tour enters and exits each node. Constraints (6) and (7) are bounding constraints, their corresponding inequalities serve as upper and lower bound constraints on the number of nodes visited by each salesman. Inequality (8) forbids a vehicle from visiting only a single node. The inequalities from (9) ensure that $u_j=u_i+1$ if and only if $x_{ij}=1$. Constraints (9) are the classical subtour elimination constraints that prevent the formation of any subtour between nodes in $V\setminus \{1\}$. The formulation is valid if $2 \le K \le \lfloor (n-1)/m \rfloor$ and $L \ge K$. Constraint (8) becomes redundant when $K \ge 4$.

3 The Ant Colony System

The fundamental idea of the ant colony algorithms is inspired by the way the natural ants succeed in finding food. The ants communicate via the pheromone trails in order to find the shortest paths from the nest to the food sources.

The algorithms investigated in this paper are based on the original version of the Ant Colony System designed by Dorigo and Gambardella for the Traveling Salesman problem [21]. In this section we review the main steps of the standard algorithm for solving TSP, leaving the presentation of its variations for multiple-TSP for the next section.

3.1 Route Selection

Each ant builds a route by iteratively selecting a node it has not visited yet. At each step in this process, the nodes not selected yet form the candidate set. The node to be added to the current route is chosen relative to the current position of the ant, in a probabilistic manner, from the candidate set. The probability assigned to a node $s$ in the candidate set $C$, considering that node $r$ is the current position of the ant, is computed with Eq. (11):

$$\begin{aligned} p(r,s) = \frac{\tau (r,s)\cdot \eta ^{\beta }(r,s)}{\sum _{u\in C}\tau (r,u)\cdot \eta ^{\beta }(r,u)} \end{aligned}$$

(11)

where $\tau$ is the pheromone, $\eta$ is the inverse of the cost measure (distance) $\delta (r,s)$, and $\beta$ is a parameter that specifies the relative importance of pheromone vs. distance. The product $\tau (r,s)\cdot \eta ^{\beta }(r,s)$ can be viewed as the fitness of node $s$, while the probabilistic selection based on the probabilities defined in Eq. (11) corresponds to the roulette wheel selection in genetic algorithms. The selection of the next node for tour construction in ACS can be synthesised by the following equation:

$$ s = \left\{ \begin{array}{l l} \arg \nolimits \max _{s \in C}{\tau (r,s)\cdot \eta ^{\beta }(r,s)}, &{} \text {if } rand(0,1) < q_0\\ S, &{} \text {otherwise} \end{array} \right. $$

where $q_0$ is a parameter and $S$ is a random variable with the probability distribution given by Eq. (11).

3.2 Local Pheromone Update

Each time an ant builds a route, it changes the pheromone level on each edge it traverses. The pheromone of each edge traversed is updated by Eq. (12):

$$\begin{aligned} \tau (r,s)=(1-\rho )\cdot \tau (r,s)+\rho \cdot \Delta \tau (r,s) \end{aligned}$$

(12)

where $\rho \in (0,1)$ is a local pheromone decay parameter. The purpose of the local pheromone update is to ensure that the same links are not included again and again forming very similar tours.

3.3 Global Pheromone Update

Usually, ants search for food in a neighborhood of the best tour. In order to make the search more directed, after all ants have completed their tours, the globally updating phase of the pheromone follows. Only the edges included in the best global solution receive pheromone in this phase. The pheromone level is updated by applying the following rule:

$$\begin{aligned} \tau (r,s)=(1-\alpha )\cdot \tau (r,s)+\alpha \cdot \Delta \tau (r,s) \end{aligned}$$

(13)

where

$$ \Delta \tau (r,s) = \left\{ \begin{array}{l l} (L_{gb})^{-1} , &{} \text {if } (r,s)\in \text {global-best-tour}\\ 0, &{} \text {otherwise} \end{array} \right. $$

where $\alpha \in (0,1)$ is the pheromone decay parameter and $L_{gb}$ is the length of the globally best tour encountered. By this rule, only the edges that belong to the globally best tour receive reinforcement.

4 Algorithms Investigated for Multiple-TSP

4.1 Problem Decomposition with k-Means Followed by ACS for TSP (kM-ACS)

One possible approach to tackle the multiple-TSP problem is to decompose the problem instance into a number of small subproblems equal to the number of salesmen; subsequently, each subproblem can be solved by the standard ACS resulting in one (near)optimal subtour for the corresponding salesman. The problem decomposition can be performed by means of clustering algorithms, with the aim to group closely interconnected cities. Among the popular clustering algorithms, k-Means seems to be the most appropriate choice due to its reduced time and space complexity and, more important, due to the fact that it is known to generate groups of equal volumes. The latter characteristic is desirable for the multiple-TSP problem, where we aim to obtain balanced subtours.

To split one single-depot multiple-TSP instance into several TSP instances, we need to adapt the k-Means algorithm. Our problem formulation necessitates that the depot should be included in each of the TSP subproblems generated. Since k-Means is a crisp-clustering algorithm, when applied the multiple-TSP instance, it will generate disjoint sets of cities. To obtain an optimal clustering of the cities where all groups share the depot city, the assignment step is changed in k-Means: at every iteration in k-Means, all the cities are assigned to the cluster based on their distances to the centroids, with the exception of the depot which is assigned to every cluster; thus, all the centroids will be biased towards the location of the depot. This modification discourages the clustering algorithm from forming isolated groups, at far distances from the depot. After the cities are clustered into $m$ groups (where $m$ is the number of salesmen), $m$ independent runs of the ACS are performed, one for each group; in this step, $m$ smaller TSP instances are practically solved. The final solution for the multiple-TSP problem is obtained by aggregating the solutions obtained in the ACS runs, as subtours to be assigned to the $m$ salesmen. This version of the algorithm is denoted in the experimental section by $kM-ACS$.

4.2 ACS with Global-Solution Pheromone Update (g-ACS)

Several salesmen can compete towards building the subtours in one run of the ACS, idea found also in [14]. In such an approach, for a problem instance with $m$ salesmen, $m$ salesmen are placed at the depot location - each ant corresponding to a team of $m$ salesmen. At each step, one salesman is chosen at random (selection with replacement). The selected salesman chooses the next city in its subtour in agreement with the route selection mechanism in ACS, detailed in Sect. 3.1; the candidate set of nodes consists of the nodes that are not selected in any of the $m$ subtours under construction. This process is repeated until a complete solution is obtained (when the candidate set of nodes is empty). Each traversed edge receives the quantity of pheromone computed with Eq. (12), regardless of which salesman traverses it.

At each iteration of the algorithm, several groups of salesmen, each of size $m$, build complete solutions as explained above. From these solutions, the one with the smallest cost - measured as the sum of the costs of the $m$ subtours - is considered to be the global best at the given iteration. The best-so-far solution (global best - the best solution encountered during the run) is updated if necessary. Then, the edges encountered in the subtours of the global best solution are updated with Eq. (13), where $L_{gb}$ is the total cost of the global solution. This version of the ACS algorithm is denoted in the experimental section as $g-ACS$.

4.3 ACS with Subtour Pheromone Update (s-ACS)

Another version we propose, denoted as $s-ACS$, is a small variation of the previous algorithm. The difference between the two consists only in the third phase of the ACS algorithm - the global pheromone update. $s-ACS$ does not use the same pheromone quantity on each edge, but differentiates the edges based on the subtour to which they are assigned. Thus, we refine/update Eq. (13) by including subtour information as follows:

$$\begin{aligned} \tau (r,s)=(1-\alpha )\cdot \tau (r,s)+\alpha \cdot \Delta \tau (r,s) \end{aligned}$$

(14)

where

$$ \Delta \tau (r,s) = \left\{ \begin{array}{l l} (L_{k})^{-1} , &{} \text {if } (r,s)\in \text {subtour k in global-best-tour} \\ 0, &{} \text {otherwise} \end{array} \right. $$

According to the new equation, each edge included in the best solution encountered so far (the global best solution) receives a quantity of pheromone inverse proportional with the cost of the subtour to which it belongs.

4.4 ACS with Global-Solution Pheromone Update and Bounded Tours (gb-ACS)

Another variation we propose, is to enforce within the $g-ACS$ algorithm the bounds imposed by the problem with regard to the number of cities to be included in each subtour. Although in the phase of solution construction, the salesman designated to add one more city to its subtour is uniformly drawn at random (i.e. each salesman has the same probability), experimental studies showed that the solution built is sometimes highly unbalanced with regard to the number of cities included in the subtours. This is justified, since the law of large numbers from statistics is not applicable to the size of the problems we deal with. The bounds on the size of each subtour are imposed by changing the way salesmen are selected when constructing the solution. Here, we use a selection strategy without replacement: in a first step, the lower bound $K$ on the number of cities to be included in each subtour is guaranteed by sampling at random from a population of size $K\cdot m$ without replacement, consisting of $K$ instances of each of the $m$ salesmen. When this sampling procedure ends (all instances are used during solution construction), all $m$ subtours consist of the minimum number of cities allowed. A similar salesman selection scheme begins (without replacement) with a population of size $(L-K)\cdot m$ ($L-K$ instances of each of the $m$ salesmen) to guarantee that the maximum bound imposed on the size of each subtour is not exceeded. This sampling phase ends when a complete solution is built. This variant of the $g-ACS$ algorithm where bounds are enforced, is called gb-ACS.

4.5 ACS with Subtour Pheromone Update and Bounded Tours (sb-ACS)

The bounds on the size of the subtours are imposed in the same manner in the ACS algorithm with pheromone updates based on the cost of the subtours ($s-ACS$). This leads to new variant denoted as $sb-ACS$.

5 Experiments

5.1 Problem Instances

Although multiple-TSP is, by its formulation, only one step away from the standard TSP problem which provides very popular benchmarks such as TSPLIB¹, there is no freely available benchmark for multiple-TSP at this moment to test the performance of various heuristics. To fill this gap, we formulate several problem instances for multiple-TSP and provide exact solutions by solving them in CPLEX². The problem instances we propose are based on the TSPLIB benchmark. Specifically, we extracted from TSPLIB four instances of various size and distribution and we transformed them in multiple-TSP instances by setting the number of salesmen to be, by turn, 2, 3, 5 and 7. The selected TSPLIB instances were chosen so that to reflect different distributions of cities and different positions of the depot city. These settings generate from each TSPLIB instance, 4 multiple-TSP instances. The depot, for each instance, is considered to be the first city in the file. The problem instances along with the distribution of cities and position of depot city, the optimal solutions and their visualisations are publicly available as multiple-TSPLIB.³

As stated in Sect. 2, we impose bounds on the number of cities each salesman needs to visit. If considered as a problem with a single objective - that of minimising the total cost of visiting all the cities - and no bounds are imposed on the number of cities to be visited by each salesman, the multiple-TSP with single depot is an ill-posed problem: the optimal solution is obtained when one salesman visits all the cities while the rest do not have assigned any work. This is obvious by comparing the total costs obtained on the same TSPLIB instance with different numbers of salesmen: when increasing the number of salesmen, the total cost increases.

The use of several salesmen in practice for single-depot-multiple-TSP does not aim to obtain better costs compared to the case when a single salesman is used, but aims at shortening the time needed to serve all the clients or is triggered by the limited capacity of each agent - problem closely related to the Capacitated Vehicle Routing. From the first point of view, single-depot-multiple-TSP is inherently a bi-objective optimization problem: the total cost should be minimized while maintaining the subtours as balanced as possible; the bi-objective formulation will be the scope of our future studies. In fact, imposing bounds on the number of cities visited by each salesman, increases significantly the complexity of the multiple-TSP problem being solved. Obtaining with CPLEX the optimal solution for MTSPLIB instances, when no bounding constraints were considered, lasted at most 17 min. This is a major difference compared with the time required by CPLEX to solve MTSPLIB instances when these bounding constraints are included; the reported solution for the rat99-m7 problem instance was obtained with CPLEX after 14 h. All the runs were performed on a PC with 8 GB RAM, processor Intel Core i5-4590S 3.00 GHz using 4 processing units (multi-threaded implementation of CPLEX). In comparison, one run of any ACS variant described in this paper required on average 1 s and 11 ms in a single-threaded implementation.

With the aim of obtaining balanced solutions, we chose to set the bounds ($L$ and $K$) on the number of cities to be included in each subtour, by running 30 times k-Means clustering algorithm, on the same problem instance to split the cities in $m$ groups; the partition with the lowest sum of the within-cluster variances was used to set $K$ equal to the size of the smallest cluster and $L$ equal to the size of the largest cluster.

5.2 Parameters Setup

The standard ACS algorithm introduces some numerical parameters which, usually, are empirically optimized. As suggested in [21], we set $q_0 = 0.9$, $\alpha = 0.1$, $\rho = 0.1$, $\beta = 2.0$ in all tested algorithms. The number of ants in $kM-ACS$ was set to 10 for each TSP subproblem (corresponding to each of the $m$ clusters), corresponding to a total of $10 \cdot m$ ants used to solve each of the multiple-TSP problem instances. The number of ants used in all the other versions is also set to $10 \cdot m$ in the following way: at each iteration of these algorithms 10 groups of ants, each of size $m$, build in parallel, independently, 10 complete candidate solutions. Each algorithm is ran for 1 400 iterations for the problem instances with 51 and 52 cities, 1 800 iterations for eil76 problem instances and 2 200 iterations for rat99 problem instances.

5.3 Results

We provide results for each investigated algorithm regarding both the total cost of the solutions and the balancing degree of the subtours. For all algorithms, we report the average cost of the solutions over 50 runs.

In order to evaluate the balancing degree, for each solution returned at the end of a run we compute the amplitude of the costs of its subtours as the difference between the cost of the longest subtour and the cost of the shortest subtour of the solution. We report the average amplitude over 50 runs for each algorithm. Please note that the amplitude is computed taking into account subtour costs and not subtour cardinalities (the number of cities in each subtour), because the two criteria are not equivalent.

Figure 1 illustrates the evolution of the best cost (best solution) during the run of the algorithms for the eil76-m5 problem; the curves are obtained as averages over 10 runs for each algorithm. As anticipated, kM-ACS shows the highest convergence rate, because it solves in parallel several smaller and simpler problems. However, the performance with regard to the best solution it can achieve is limited, because of the problem decomposition scheme which imposes rigid boundaries on the candidate solution space; in this regard, the non-deterministic character of k-Means introduced by random initializations is an advantage. The best performance on this problem instance is recorded by gb-ACS - the bounded version of g-ACS which uses the cost of the global solution (and not of the individual subtours) for pheromone update.

Fig. 1.

Evolution of the cost of the best solution during the run of the algorithms for eil76-m5, averaged over 10 runs.

Table 1 report the costs of the optimal solutions and their corresponding amplitudes, as obtained with CPLEX, and the performance of all the ACS variants we propose - as averages over 50 runs. For each problem instance and ACS variant, along with the average cost we also report the standard error of the mean multiplied with the 0.975 quantile of the Student’s t distribution (used to compute confidence intervals). Where CPLEX was stopped before finding the optimal solution, both the upper (corresponding to the best known solution) and the lower bound on the cost are given; the amplitude in this case is computed on the best known solution. In each table, the best value from a row was highlighted with boldface. Similar graphics for berlin52, eil76 and rat99 instances can be found at this address⁴. They weren’t included here due to page limits.

Table 1. The performance of the ACS variants for the eil51 instance

Figure 2 illustrate, for eil51 problem, the distribution of the costs and the amplitudes of subtour costs for the solutions obtained in 50 runs of each algorithm. On each chart corresponding to a TSP instance, 4 groups are emphasized, corresponding to the 4 distinct settings of the number of salesmen (2, 3, 5 and 7). The increase in the total cost with the increase of parameter $m$ is evident. For each of the four groups in each chart, we have 6 sets of solutions: corresponding to the best known solution - obtained with CPLEX (this behaves as lower bound for the ACS-based algorithms), to $kM-ACS$, to the two versions of ACS adapted for multiple-TSP that do not enforce bounds on the size of the subtours and the two ACS versions with bounds. Similar figures along with the representation of the confidence intervals for the mean of the costs can be found at this address⁵. They weren’t included here due to page limits.

Evident in the boxplots but also from the size of the confidence intervals, kM-ACS is the most stable algorithm. With a quick convergence, this algorithm even achieves on some problem instances (eil51-m5, eil76-m7, rat99-5, rat99-7) the best cost (proven by statistical tests on the means). It seems that this algorithm is a good choice for very large instances, with high number of cities and many salesmen. Among the two bounded variants - $gb-ACS$ and $sb-ACS$ - $gb-ACS$ converges more quickly, achieving at the same time better solutions. Comparing the two unbounded variants - $g-ACS$ and $s-ACS$ - the same conclusion can be drawn: the version laying equal pheromone quantities on the edges of the best solutions (irrespective of the cost of the subtour) achieves better costs. However, $g-ACS$ returns solutions which are highly unbalanced compared to $s-ACS$ and this is a real concern for its applicability in practice.

Fig. 2.

Results obtained in 50 runs for eil51: (a) total cost, (b) amplitude of the costs of subtours; the groups correspond to different settings for $m$: 2, 3, 5, 7

6 Conclusions

Inspired by the ant colonies behavior in nature, the Ant Colony System proved to be an efficient approach for searching for an optimal path in a graph. As shown in our study, this meta-heuristic can be easily adapted for the multiple traveling salesman problem. For real world, large instances of multiple-TSP, which become untractable with exact deterministic algorithms, the ant colony system is a viable solution. Future work will be conducted towards studying the bi-objective formulation of multiple-TSP, by means of ACSs.