Ant Colony Optimization for K-Independent
Average Traveling Salesman Problem
Anonymous author
No Institute Given

Abstract. In this paper, we propose a K-independent average traveling salesman problem (KI-Average-TSP) extended from the TSP. Thisis an optimization problem that minimizes the weighted sum of the average and standard deviation of K circuits’ costs, with mutually independent edges. As a method to solve the KI-Average-TSP, we propose
K-independent average ant colony optimization (KI-Average-ACO) extended from the original ACO. KI-Average-ACO moves K ants simultaneously using the following two heuristcs to prevent diﬀerent circuits
from sharing the same edge. The ﬁrst heuristic uses a degree of possible
options representing the number of vertices that an ant can reach fromits current vertex. The destination of ants is stochastically determinedby this value to reduce the circuit construction failure rate. The second
heuristic, named 2-best-opt, uses a greedy algorithm in reconstructing abetter path to obtain K circuits if circuit construction fails. Comparison
results between the approximate solution obtained using KI-AverageACO and the solution obtained using a quadratic programming method
for binary search show that the number of circuits for KI-Average-ACO
was higher, and KI-Average-ACO obtained a better approximate solution
than the quadratic programming method.
Keywords: Ant Colony Optimization · Traveling Salesman Problem ·Heuristics

1

Introduction

One of the common combinatorial optimization problems is the traveling salesman problem (TSP) [6]. Given distances (edges) connecting cities, the TSP ﬁnds
the shortest routes to visit all cities. The TSP is applied to various problems, suchas vehicle routing and job-shop scheduling [5]. However, optimization problems
in the real world are considered more complicated than the TSP. For example,
in a transportation company’s delivery plans, even if the company constructs
the shortest circuits to access cities, these routes may become inaccessible due
to road damage or accidents.
In this study, we consider constructing mutually independent circuits with noshared edges to improve reliability and propose a K-independent average TSP(KI-Average-TSP) that minimizes the weighted sum of the average and standard
deviations of K circuits’ costs, where the circuits are mutually independent, that2

Anonymous author

Fig. 1. An example of K-Independent paths (with K = 2), where multiple paths do
not share the same edge in N = 8 complete graph.

is, there are no shared edges among the circuits. Compared to a study to ﬁnd
multiple independent Hamiltonian paths in a graph [11], this study minimizes
the cost by considering the standard deviation in a complete graph so that theK circuits act as backup routes. Fig. 1 shows an example of K = 2 circuits in acomplete graph of N = 8 vertices.
To solve the problem, we propose an ant colony optimization (ACO)-based
K-independent average ACO (KI-Average-ACO). ACO [2, 7] is known as a metaheuristic solution to the TSP using ant swarm characteristics and simulates thepheromone communication of ants on a graph to ﬁnd the approximate shortest
path. In our optimization algorithm, K ants move simultaneously, making it
possible for K ants to use equally favorable edges and reducing the standard
deviation. However, as the ants move, the number of reachable vertices for theants decreases, and the circuit construction failure rate increases. Therefore, we
introduce two heuristics to reduce the failure rate of circuit construction. The
key concept of the ﬁrst heuristic is a degree of possible options that represents
the number of vertices an ant can reach from its current vertex. The destination of ants is stochastically determined by this number to reduce the circuit
construction failure rate. The second heuristic, called 2-best-opt, is an algorithm
based on the idea of 2-opt [3, 6]. It uses a greedy algorithm in reconstructing abetter path to obtain K circuits if circuit construction fails.
In this paper, we evaluated our proposed method by comparing the approximate solution obtained using KI-Average-ACO with the solution obtained using
a quadratic programming method for a binary search. Comparison results showedthat the number of circuits for KI-Average-ACO was higher, and KI-AverageACO obtained a better approximate solution than the quadratic programming
method.
Related Work. ACO is a search algorithm that is inspired by the process
by which ants use pheromones to discover the shortest path to food [2]. In
particular, it is known as metaheuristics for ﬁnding approximate solutions toshortest path problems, as typiﬁed by the TSP. An application of ACO is thevehicle routing problem [10], which delivers resources from a depot to customers
through delivery vehicles. Another application is the multiple TSP [4], which

ACO for KI-Average-TSP

3builds a partial traveling circuit in which multiple salesmen share each other’svisits to cities from a depot.
On the other hand, a few studies have been conducted on algorithms to ﬁnd
multiple independent circuits in a complete graph. Teng [11] reported properties
such as the conditions for establishing multiple Hamiltonian paths in a given
graph. However, algorithms for constructing circuists that are independent ofeach other have not yet been investigated.
Paper Organization. The organization of this paper is as follows. Section 2 deﬁnes KI-Average-TSP and a related problem named KI-Total-TSP. Section 3 introduces our optimization algorithm named KI-Average-ACO. Section 4 presents
experimental results. Finally, Section 5 concludes the paper and presents future
work.

2

Problem Description

In this section, we give the deﬁnition of our target problem named K-indipendent
average traveling salesman problem (KI-Average-TSP). In addition, although
not directly dealt with in this study, we also deﬁne K-independent total traveling salesman problem (KI-Total-TSP), which is another optimization problem related to KI-Average-TSP. The former is the problem of ﬁnding the Kindependent circuits that minimize the weighted sum of average and standard
deviation in a given complete graph, while the latter is the problem that removes
the term of standard deviation from the objective function in KI-Average-TSP
and minimizes only the total cost of K-independent circuits.
Here, let G = (V, E, d) (with |V | = N, |E| = N (N2−1) ) be a weighted undirected complete graph, where dij is the weight of edge (i, j) and N is the numberof cities.

2.1

K-Independent Average TSP

KI-Average-TSP is a problem to minimize the weighted sum of the average andstandard deviations of K independent circuits’ cost in a graph G. The deﬁnitionis as follows.

Deﬁnition 1. KI-Average-TSP is a problem to perform the following optimization in graph G = (V, E).

4Anonymous authorminsubject tocostavg + γ · costθsd∑
xijk ≤ 1(1)(∀i, j (i ̸= j))(2)

xijk = 1(∀i, k)(3)

xjik = 1(∀i, k)(4)(∀i, j, k)

(5)

k∈K

∑

j∈V

∑

j∈V

uik + 1 − (N − 1)(1 − xijk ) ≤ ujk
xijk ∈ {0, 1}(6)

0 ≤ uik ≤ N − 1

(7)

where
1
costsum ,K√
1 ∑∑ ∑
1 ∑ ∑∑((
dij · xijk − (dij · xijk′ ))2 ).
costsd =K
K′costavg =k∈K i∈V j∈V

(8)
(9)

i∈V j∈V k ∈K

The value xijk represents the probability of ant k using the edge connecting
vertex i to vertex j. The value uik is the arc-constraint to excludes subtours basedon the Miller ‒ Tucker ‒ Zemlin formulation[8]. Hereafter, the total cost of theK circuits is expressed as costsum . The weighted sum is represented as costssd =costavg + γ · costθsd , where costavg and costθsd respectively represent the averageand standard deviation of K circuits’ costs. Variables γ, θ are parameters forweighting the average and standard deviation respectively, and the constraints
is the same as in KI-Total-TSP.
2.2

K-Independent Total TSP

The KI-Total-TSP is a problem to minimize the total cost in K circuits among
the combinations of K independent circuits in the graph G. The deﬁnition is asfollows.
Deﬁnition 2. KI-Total-TSP is a problem to perform the following optimizationin graph G = (V, E, d).

min

∑∑ ∑

dij · xijk

(10)i∈V j∈V k∈K

with the same constraint conditions as in the KI-Average-TSP (i.e., Eqs. 2–7).

ACO for KI-Average-TSP

5

We would like to note that the problems introduced above are complementary
to each other. That is, the solution of KI-Average-TSP is useful when ﬁnding K
circuits with similar utility values. On the other hand, KI-Total-TSP is usefulwhen ﬁnding K circuits with ranked utility values. Speciﬁcally, the former is acase, where multiple packets are sent simultaneously through K routes, while
the latter is a case, where spare routes should be prepared for a failure of thecurrent route.

3

K-Independent Average ACO

3.1

Overview

In this section, we explain the proposed K-independent average ant colony optimization (KI-Average-ACO) algorithm for solving KI-Average-TSP. Consideringthat it is diﬃcult to calculate the exact solution to KI-Average-TSP in a feasible
time, we propose KI-Average-ACO to obtain an approximate solution.
Unlike the original ACO, KI-Average-ACO averages the cost of K circuits
by repeatedly moving K ants along one edge at a time. However, because theconstruction failure rate increases when K ants move simultaneously, we use twoheuristics. The ﬁrst heuristic uses a degree of possible options, which indicatesthe feasible vertices the ant can reach. Ants move to vertices with fewer destinations using this index, putting oﬀ many potential movable vertices. The second
is 2-best-opt, which searches eﬃciently by reconstructing failed circuits greedily using 2-opt. Using these heuristics, it is possible to reduce the construction
failure rate while averaging the moving cost of K circuits, rather than repeating
ACO. The pseudocode of KI-Average-ACO is presented in Algorithm 1.
3.2

Simulaneous Movement of Ants

KI-Average-ACO diﬀers from the original ACO in moving K ants along one edge
at a time. In the original Ant System [1] and Max-Min Ant System [9], some ants
constructs a path. If these algorithms are applied to KI-Average-TSP repeatedly,
some ants constructs a circuit using preferable edges greedily. Consequently, thecost of the circuit in the latter half of the construction increases, the shape becomes complicated, and the averaging cannot be satisﬁed. In contrast, in Line17
in the pseudocode, KI-Average-ACO moves K ants along one edge at a time,so that all ants can use their preferred edges. In Line19, ants are arranged indescending order of moving cost so far after every movement, and the next ants
move in this order. As a result, it is possible to perform the averaging of thecost in a greedy manner, because ants, which have consumed bigger moving costso far, can move to smaller-cost and pheromone-rich edges more preferentially.
We would like to note that the cost of an edge used becomes inﬁnite and thepheromone value becomes zero to ensure that it is not used as much as possible
again.

6

Anonymous author

Algorithm 1 KI-Average-ACO
1: function ki_average_aco(G, N, K)
2:
aco(G)▷ init G’s pheromone with Ant System
3:
ants = [ ]4:for i = 1 to K do
5:ants.append(Ant())
6:
end for7:
for t = 1 to T do
8:
make_tsps(G, N, K, ants)
9:2_best_opt(G, K, ants)
10:
pheromone_update(G, ants)
11:
end for
12: end function
13:
14: function make_tsps(G, N, K, ants)
15:
for i = 1 to N do
16:
for j = 1 to K do
17:ants[j].move_one_edge(G)▷ use the degree of possible options
18:
end for19:
ants.sort(key=ant.costsum , reverse=true) ▷ sort ants in descending order20:
end for
21: end function
22:
23: function 2_best_opt(G, N, K, ants)
24:
for i = 1 to K do
25:
if ants[i].path has duplicated edge then26:
ant = ants[i]27:alts = [ ]28:for j = 1 to N do29:
for k = 1 to N do30:
at = ant.2_opt(ant.path[j], ant.path[k])31:
if at.path has no contradiction then32:
alts.append(at)33:
end if34:
end for35:
end for36:
alts.sort(key=ant.costsum )37:
ants[i] = alts[0]▷ use best swap reducing cost38:
end if
39:
end for
40: end function
41:
42: function pheromone_update(G, ants)
43:
if ants has no duplicated edge then44:
update(G, ants)
45:
end if
46: end function

ACO for KI-Average-TSP

3.3

7

Heuristic with Degree of Possible Options

KI-Average-ACO moves K ants simultaneously. As a result, close to the K-th
movement, there are possibilities that ants may reuse edges used by other ants,
thereby increasing the construction failure. Therefore, to increase the number ofsuccesses, we introduce the heuristic with the degree of possible options. This
is incorporated into the transition probability equation in Line 17 in the pseudocode.
Assume that each of the K ants has already moved t times out of N times, andthe set of vertices visited by ant h is Uh . Here, we deﬁne Rht (x) ⊆ V as a functionthat returns a set of vertices where ant h can move consistently from vertex x tovertex y. The word “consistent” averages that vertex y ∈ Rht (x) satisﬁes y ∈/ Uhand the edge (x, y) is not yet used by other ants 1, 2, . . . , h − 1, h + 1, . . . , K.
At this time, transition probability equation Pijh that ant h selects the next
vertex j from the vertex i is deﬁned by Eq. 11.
[τij ]α [ηij ]β1,× tα [η ]β
|R
[τ
]
t
iu
u∈N (i) iu
h (j)|

Pijh = ∑

(11)

h

ηij =

1
dij

(12)

where τij is the pheromone quantity of the edge (i, j) and ηij is the heuristic
value. Nht (i) is a set of vertices where an ant h can move from vertex i in
the t-th move. In Eq. 11, the transition probability is divided by the numberof vertices |Rht (j)| that ant h can move from vertex j. Using this operation,
ants can preferentially move to vertices that have little non-aﬀordably movablevertices. This reduces the construction failure rate. Although the time complexity
is increased by O(N ) during the moving process, the construction failure rate is
reduced and an approximate solution can be more eﬃciently searched.
3.4

2-best-opt

In Line9, we use the heuristic called 2-best-opt to improve paths after constructing the circuits to further increase the success probability of constructing
independent circuits and minimizing costssd . Procedures of the 2-best-opt are
depicted from Line23 to 40.
Assume that in the K paths after the construction, an edge e = (a, b) isredundantly used in multiple paths of F (> 1) ants. At this time, 2-best-opt is
performed for each of the l1 , l2 , . . . , lF paths of F ants. 2-best-opt is the following
operation and is shown in Fig. 2 and from Line23 to 40.
Consider a case where an edge e = (a, b) is redundantly used by other pathsof a certain path l and other N − 1 edges e′ = (c, d) of the path l are exchangedby 2-opt. At this time, if the two new edges e1 = (a, c) and e2 = (b, d) are not
yet used for any K paths, the number of use of edges can be reduced without
contradiction, and the edge e′ is added to the replacement candidate set S in

8Anonymous author

!

"

!

#

Fig. 2. The example of 2-best-opt which is trying to swap e = (a, b) and e′ = (c, d)because the edge e is used twice. Swapped edges e1 = (a, c), e2 = (b, d) can reduceusage count in e = (a, b) .

Line 30 to 33. Then, among the exchange candidates of these edges, an edgee′ ∈ S is selected and swapped by e in 2-opt, so that the moving cost of the pathl becomes the smallest by exchanging with the edge e in Line 36 and 37.
Using this 2-best-opt, the overlapping edges causing the failure can be corrected greedily and the construction failure rate and costssd can be reduced.
3.5

Pheromone Update

After performing 2-best-opt, in Line 10, if K paths are reconstructed and are
independent of each other, the pheromone update equation, Eq. 13, is executed.

τij (t + 1) = ρ · τij (t) +{∆hij =

K∑∆hij ,(13)h=1
1
Ch +costθsd((i, j) ∈ lh )0(otherwise)(14)

where ρ is the retention rate of the pheromone, Ch is the cost of the circuit
constructed by ant h, lh is the path of ant h, and θ is equal to θ in Eq. 1. However,if the K paths are not independent of each other, the updating equation for thepheromone on the graph and the evaporation of pheromone are not performed
from Line 43 to 45. This tries to centralize searching by updating.

4

Empirical Study

4.1

Parameters and Settings

This section presents two experiments to evaluate our algorithm. In the ﬁrst
experiment, the performance of the two heuristics used in KI-Average-ACO wasACO for KI-Average-TSP

9evaluated. In the second experiment, KI-Average-TSPs were solved using KIAverage-ACO and a combinatorial optimization method to compare their solutions and the time taken to obtain these solutions.
Table 1. Parameter Settings.
ParameterValueα (pheromone rate)
β (heuristic rate)ρ (pheromone residual rate)
Number of ants
AT (number of the cycles in Ant System)
KT (number of the cycles in KI-Average-ACO)
LT (number of trials)

1
3
0.97
N
200
1000
10

The parameters in the experiments are as shown in Table 1. Here, AT represents the number of cycles to initialize the pheromone using the Ant System on
the graph before starting KI-Average-ACO. KT represents the number of cycles
that KI-Average-ACO executes to build K paths. LT represents the number ofexperimental trials performed.
4.2

Performance Evaluation of Heuristics

To evaluate the performance of the heuristics used in KI-Average-ACO, we considered four cases with and without each heuristic and compared them by solving
KI-Average TSP for each case. In every case, the pheromone was always updated.
As the graphs used for the optimization problems, we selected three graphs
ulysses22, bays29, and att48, which have a diﬀerent number of vertices fromTSPLIB, the dataset often used for performance evaluations of TSP solution
algorithms.
We attempted to construct K = 6 circuits in each graph. We measured theweighted cost costssd , execution time, and construction failure rate. Even if only
one edge is duplicated, this is considered as a construction failure. For example, if
the construction failure rate is 0.48, this means that one or more edges have beenused in duplicates in 480 of 1,000 trials. The results of the above experiments
are shown in Table 2. Here, DPO, 2BO, DPO+2BO, and NONE represent cases,
where only the heuristic with degree of possible options was used, only 2-bestopt was used, both two heuristics were used, and neither of the two was used,
respectively.
Table 2 shows the comparison results of the heuristic performance in KIAverage-ACO. These results show that 2-best-opt, in particular, improves thecircuit construction failure rate in all three graphs. Moreover, the execution timeof 2-best-opt is not long, so this heuristic would be feasible. On the other hand,heuristic with the degree of possible options did not contribute to reduce the cost

10

Anonymous author
Table 2. Performance of Heuristics in KI-Average-ACO.
ProblemHeuristics

Cost of solution

Required time

Failure rate

NONE
DPO
ulysses22
2BO
DPO+2BO

4

6.39 × 10
5.22 × 104
5.33 × 104
5.84 × 104

14
55
16
57

0.999
0.999
0.0
0.0

bays29

NONE
DPO
2BO
DPO+2BO

1.15 × 104
1.01 × 104
8.97 × 103
9.83 × 103

32
126
34
126

0.994
0.970
0.0
0.0

att48

NONE
DPO
2BO
DPO+2BO

2.96 × 105
4.12 × 105
2.91 × 105
3.43 × 105

70
488
72
489

0.989
0.964
0.0
0.0

of the solution even though the execution time was longer than that of 2-best-opt.
This is because the execution time of this heuristic takes O(N ), and costly edges
were also selected to give priority to the reduction of the circuit construction
failure rate. However, for ulysses22, the cost of solution was the smallest whenheuristic with the degree of possible options was used. This suggests that thisheuristic may also be useful depending on the problem type.
4.3

Performance Evaluation of KI-Average-ACO

We evaluated the performance of KI-Average-ACO. Speciﬁcally, we compared
the costs of solutions obtained using KI-Average-ACO to that obtained using
a combinatorial optimization algorithm. In the experiments, we used the graphgr17 with N = 17 as a problem to solve. The weighted parameters γ and θ ofthe KI-Average-TSPs were set as 1 and 2, respectively.
In general, it is diﬃcult to ﬁnd the exact solution for KI-Average-TSP. Indeed,in our preliminary experiments, we observed that exact solutions could be foundonly for problems, where the size of the graph is N < 8 and the number ofcircuits is K < 3 in a feasible time. Therefore, we evaluated the performance of
KI-Average-ACO and the combinatorial optimization algorithm by comparing
the costs of approximate solutions instead of exact solutions. The combinatorial
optimization algorithm used as the comparison target is as follows. Since thestandard deviation can be calculated from K circuits, binary search was used
to determine whether the maximum diﬀerence d of costs between the K circuits
could be less than or equal to a certain threshold value. Repeating this operation,
while gradually lowering the threshold value within a predetermined time limit,
minimized the maximum diﬀerence in the costs of K circuits (thus, the standard
deviation was also minimized). In this case, the time limit was set to 300 seconds.
Figure 3 shows the experimental results. The horizontal and vertical axes of
the graph represent the K number of circuits in the problem and the total costs

ACO for KI-Average-TSP

11

N
N

., $YHUDJH $&202:HLJKWHG &RVWV

N
N
N
N
N
N

.

Fig. 3. Costs of Solutions for KI-Average-TSP.

of the solutions, respectively. “KI-Average-ACO” and “MO” represent the results
obtained using our algorithm and the mathematical optimization algorithm, respectively. Here, the plots of MO for K = 6, 7 are lost because MO did not ﬁnd
any solution within the time limit. This ﬁgure shows that for K = 1, 2, 3, thetotal cost of the solutions obtained by the proposed algorithm was almost thesame as that of MO. Furthermore, for K = 4, 5, 6, 7, our algorithm obtained better solutions. We would like to remark on the result when K = 8. It is consideredthat the reason why MO obtained a solution in this case is that the solution has
to use all edges, so it is no longer necessary to decide whether or not to use edges
in the solution. On the other hand, this did not bring any beneﬁt to the solution of our algorithm even though it took more time to calculate as the problem
became more complicated. As a result, no solution could be found. However,this is a special case, and overall, we have observed that it is useful, especiallywhen the problems are complicated compared to the mathematical optimization
algorithm.

5

Conclusions and Future WorkIn this study, we proposed two problems named KI-Average-TSP and KI-TotalTSP, which were extensions of the TSP. We also proposed KI-Average-ACO, an
optimization algorithm to solve KI-Average-TSP. The idea behind our algorithm
is to move K ants simultaneously. However, to reduce the failure rate of circuit
construction, we introduced two heuristics with the degree of possible options
and 2-best-opt, a heuristic based on 2-opt. We evaluated the performance of
our algorithm and the eﬀectiveness of the heuristics. In the experiments, weobserved that 2-best-opt signiﬁcantly contributed to reducing solution costs andconstruction failure rates. In addition, the solution cost of KI-Average-ACO was12Anonymous author

reduced when the circuit to be constructed was larger compared to the solution
cost of the mathematical optimization algorithm for binary search.
One of the important future directions is to apply our algorithm to realistic
problems. In particular, we would like to generalize KI-Average-TSP to formulate
an optimization problem that allows m < K edges to be shared between circuits
and to ﬁnd its solution algorithm.

References
1. Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony ofcooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part
B (Cybernetics) 26(1), 29–41 (1996)
2. Dorigo, M., Stützle, T.: Ant colony optimization: overview and recent advances.
In: Handbook of metaheuristics, pp. 311–351. Springer (2019)
3. Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: A case study inlocal optimization. Local search in combinatorial optimization 1(1), 215–310 (1997)
4. Junjie, P., Wang, D.: An ant colony optimization algorithm for multiple travelling
salesman problem. pp. 210–213 (01 2006). https://doi.org/10.1109/ICICIC.2006.40
5. Lenstra, J.K., Kan, A.R.: Some simple applications of the travelling salesman problem. Journal of the Operational Research Society 26(4), 717–733 (1975)
6. Lin, S., Kernighan, B.W.: An eﬀective heuristic algorithm for the travelingsalesman problem. Operations research 21(2), 498–516 (1973)
7. Matai, R., Singh, S.P., Mittal, M.L.: Traveling salesman problem: an overview ofapplications, formulations, and solution approaches. Traveling salesman problem,
theory and applications 1 (2010)
8. Pataki, G.: Teaching integer programming formulations using the traveling salesman problem. SIAM review 45(1), 116–123 (2003)
9. Stützle, T., Hoos, H.H.: Max–min ant system. Future generation computer systems
16(8), 889–914 (2000)
10. Tan, W.F., Lee, L.S., Majid, Z.A., Seow, H.V.: Ant colony optimization for capacitated vehicle routing problem. Journal of Computer Science 8(6), 846–852 (2012)
11. Teng, Y.H., Tan, J.J., Ho, T.Y., Hsu, L.H.: On mutually independent hamiltonian paths. Applied Mathematics Letters 19(4), 345 – 350(2006). https://doi.org/https://doi.org/10.1016/j.aml.2005.05.012, http://www.
sciencedirect.com/science/article/pii/S0893965905002387