# A Novel Metaheuristic for Travelling Salesman Problem

Authors: Vahid Zharfi; Abolfazl Mirzazadeh
Journal: Journal of Industrial Engineering
 (2013)

---

## Abstract

One of the well-known combinatorial optimization problems is travelling salesman problem (TSP). This problem is in the fields of logistics, transportation, and distribution. TSP is among the NP-hard problems, and many different metaheuristics are used to solve this problem in an acceptable time especially when the number of cities is high. In this paper, a new meta-heuristic is proposed to solve TSP which is based on new insight into network routing problems.


---

## Body

## 1. Introduction

Although there are various classic methods for solving optimization problems, but they are not always able to solve real and applied optimization problems. It is generally believed that these problems are known as difficult and complicated problems. TSP is a typical example of a very hard combinatorial optimization problem. TSP can be modelled as an undirected weighted graph, such that cities are the graph’s vertices, paths are the graph’s edges, and a path’s distance is the edge’s length. It is a minimization problem starting and finishing at a specified vertex after having visited each other’s vertex exactly once. Metaheuristics can solve high-dimensional problems quickly. Heuristics may be classified into two families: specific heuristics and metaheuristics. Specific heuristics are tailored and designed to solve a specific problem and/or instance. Metaheuristics are general-purpose algorithms that can be applied to solve almost any optimization problem. They may be viewed as upper level general methodologies that can be used as a guiding strategy in designing underlying heuristics to solve specific optimization problems [1]. The word metaheuristic was first used by Glover [2] during introducing tabu search concepts.Metaheuristics gained more popularity in few recent decades, and various algorithms are proposed to solve the problem such as Genetic Algorithm [3–5], Ant Colony [6–10], Particle Swarm [11], and Simulated Annealing [12, 13].In this paper, a novel metaheuristic is proposed for solving TSP. This algorithm is used to foresee the best next city so as to gain shorter rout. The 2-Opt and 3-Opt algorithms are also used in local search. They are probably the most basic local search heuristics for the TSP.The paper is organized as follows: Section2 illustrates the background theory of suggested algorithm. In Section 3, formulating algorithms are presented. Algorithm improvement by using k-Opt is discussed in Section 4. The algorithm is employed into several standard TSP instances in the next section and the results are reported. According to the obtained results, it is noticeable that the algorithm achieves proper answers, quickly so that the answer of the first iteration will be a good and acceptable answer.Finally, Section6 concludes the paper.


## 2. Background Theory of the Algorithm

In this model, it is supposed that every node in the network is a vibration source and has a special weight which vibrates the edges, so that the nodes with the heavier weight release more vibration. This emitted force by a node distributes in edges that are connected to. Shared amount of each node is dependent on the edges distances. Shorter edges have more quota of this force. In other words, if the length of an edge connected to the node is shorter, less vibration falls down along the edge and it is vibrated more intensely. There is a simple network (Figure1) to illustrate the theory. The searcher is located at the node a in the following figure and wants to move to the next node after a.Figure 1
Routing in a network.Signs which lead toa are amount of vibrations that each edge indicates. Therefore, vibration of the edges can be considered as tendency that each neighbour node has in order to be selected by the searcher.Nodec as a sample has relationship with nodes a,b, and d. The distance for each edge is determined, and the sum of the inverted distances equals (1/5+1+1/3)=23/15. Weight of this node is wc. Therefore, the vibration that this node sends to the node a equals:
(1)(1/5)(23/15)×wc=0.13×wc.Also, about nodesb and d, the amount of vibration which is sent to node a is, respectively,
(2)(1/2)(3/2)×wb=0.33×wb,(1/3)(2/3)×wd=0.05×wd.If all weights are considered equal to 1, the searcher receives a total vibration with an amount of(0.13+0.33+0.50)=0.96 in node a. As a result, the searcher at the node a selects c with 14% possibility (0.13/0.96), b with 34% possibility (0.33/0.96), and d with 52% possibility (0.50/0.96).Movement from nodec in addition to direct route c→a can be transferred to node a of other routes such as “c→d→a" and “c→b→a.” If we also consider binary routes, calculations would be changed. Thus, by considering routes with maximum two edges, there are three different routes from c to a (Table 1). Also, about nodes b and d, similar calculations will be performed (Tables 2 and 3).Table 1
Emitted force by node “c” in the network.
Origin
Destination
Route
Route distance
Inversion of route distance
Final edge of the route
Amount of vibration in the final edge
c
a
c →b→a
3
0.33
b →a
(
0.33
/
2.28
)
×
w
c
c
a
c →a
5
0.20
c →a
(
0.20
/
2.28
)
×
w
c
c
a
c →d→a
6
0.16
d →a
(
0.16
/
2.28
)
×
w
c
c
b
c →a→b
7
0.14
a →b
(
0.14
/
2.28
)
×
w
c
c
b
c →b
1
1.00
c →b
(
1.00
/
2.28
)
×
w
c
c
d
c →a→d
8
0.12
a →d
(
0.12
/
2.28
)
×
w
c
c
d
c →d
3
0.33
c →d
(
0.33
/
2.28
)
×
w
c
Total
2.28
w
cTable 2
Emitted force by node “b” in the network.
Origin
Destination
Route
Route distance
Inversion of route distance
Final edge of the route
Vibration force in the final edge
b
a
b →a
2
0.50
b →a
(
0.50
/
2.25
)
×
w
b
b
a
b →c→a
6
0.16
c →a
(
0.16
/
2.25
)
×
w
b
b
c
b →a→c
7
0.14
a →c
(
0.14
/
2.25
)
×
w
b
b
c
b →c
1
1.00
b →c
(
1.00
/
2.25
)
×
w
b
b
d
b →a→d
5
0.20
a →d
(
0.20
/
2.25
)
×
w
b
b
d
b →c→d
4
0.25
c →d
(
0.25
/
2.25
)
×
w
b
Total
2.25
w
bTable 3
Emitted force by node “d” in the network.
Origin
Destination
Route
Route distance
Inversion of route distance
Final edge of the route
Vibration force in the final edge
d
a
d →c →a
8
0.12
c →a
(
0.12
/
1.35
)
×
w
d
d
a
d →a
3
0.33
d →a
(
0.33
/
1.35
)
×
w
d
d
b
d →a →b
5
0.20
a →b
(
0.20
/
1.35
)
×
w
d
d
b
d →c →b
4
0.25
c →b
(
0.25
/
1.35
)
×
w
d
d
c
d →a →c
8
0.12
a →c
(
0.12
/
1.35
)
×
w
d
d
c
d →c
3
0.33
d →c
(
0.33
/
1.35
)
×
w
d
Total
1.35
w
dAccording to the tables, it is possible to obtain an amount of vibration in each edge. For example, edge “c→a” receives a force with an amount of (0.20/2.28)×wc unit of c, (0.16/2.25)×wb unit of b, and a force with an amount of (0.12/1.35)×wd unit of node d. Therefore, “c→a” edge vibrates as follows:
(3)(0.202.28)×wc+(0.162.25)×wb+(0.121.35)×wd.It is supposed that all weights are 1. Therefore, the amount of vibration in “c→a” is 0.25. Similarly, “b→a” and “d→a” are 0.37 and 0.31, respectively. It should be mentioned that the total amount of these three values is not necessarily equal to 1. In the investigated example final total amount of vibration force of the three edges which end with a is 0.93.Now, the searcher is faced with vibrant edges in nodea Therefore, it selects “b→a” with 40% possibility (0.40/0.93) and moves toward “b,” selects “c→a” with 27% possibility (0.25/0.93) and moves toward “c,” or also selects “d→a” with 33% possibility (0.31/0.93) and moves toward node “d.” Total amount of these possibilities equals 1.


## 3. Model Formulation

In the previous section we got acquainted with the method of routing by the algorithm. As mentioned, edges with more vibration are selected with more possibility.The vibration of a supposed edge “j→i” is derived from two factors:(i)
direct force which is emitted fromjth node;(ii)
indirect forces that are emitted from other nodes and distribute up to “j→i.”  In other words, it is released from node k(k≠i,j) to node i after passing node j:(4)Dkji={dkj+djiifk≠i,j,djiifk=j≠i,Dkji=1dkji.In this relationdkji is the distance of the route initiated from k that ends in i after passing j. Through definition Dk is sum of inverted distances of routes connected to k which has up to two edges (see (5)); it is possible to gain the force which is applied from node k to edge j→i by:
(5)Dk=∑i≠k∑j≠kDkji,(6)rkji=(DkjiDk)×wk,so thatwk represents weight of kth node. rkji is the applied force for “j→i” resulting from k. Vibration of “j→i” equals
(7)vji=∑krkji.The final result of the previous calculations is matrixV=(vji) in which vji represents vibration degree in the edge “j→i.” It is necessary to use another element in order to increase ability of this matrix. To do so we can use vision power matrix.In distance matrix,dji represents the length of an edge which is connector of nodes i and j. The vision matrix Γ=(γij) is defined as follows:
(8)γij=1dij.By combination of two matrixesΓ and V, it is possible to use both visual sense and mechanical sensor of the searcher for detection and recognition of the best route.The result of performed calculations in this section is possibility matrixP=(pij):
(9)Pij=vijα·γijβ∑i∑jvijα·γijβ.The parameters∝ and β are investigated from the obtained results. A proper amount of these parameters is dependent on nature and structure of the investigated problem. Adjustment of ∝ and β has an important role in algorithm efficiency. Investigation of the obtained results shows that ∝=8 and β=2 are appropriate for most of the instances.


## 4. Algorithm Improvement by Local Search

The suggested algorithm searches to get to the best route in the network globally. But it makes less chance to envelop all answers. Consequently, local search is necessary in order to cover the solution space more entirely. A local search algorithm starts from a candidate solution and then iteratively moves to a neighbour solution.In optimization, 2-Opt and 3-Opt are simple local search algorithms for solving the travelling salesman problem [14, 15]. In this paper, we propose to combine the 2-Opt, 3-Opt, and the suggested algorithm to improve the answers. The algorithm steps are as follows:Initialize matrixPFor (i < Iteration Max) do:While the searcher complete a solutionChoose probabilistically the next state to move;Add that move to the tabu list;endImplementation of the 2-Opt and 3-Opt;If (local best solution better than global solution)Save local best solution as global solution;endUpdate matrixP for each edge that the searcher chose(Increase elements of matrixP related to the selectedroute up toq percent);end


## 5. Computational Results

In this section we are going to solve different standard examples by using the proposed algorithm. A large number of standard samples are available in public references. These references include famous samples for combinatorial optimization problems. One of the valid references in travelling salesman problems is TSPLIB [16].


### 5.1. Quality of Solutions

In order to estimate the algorithm function from absolute difference obtained by optimized answer, the following relation is used:(10)|f(s)-f(s*)|f(s*),
so that s is the obtained answer and s* is the optimized answer.


### 5.2. Robustness

Metaheuristics must be able to act properly in an extended range of samples or problems with the same parameters. It is possible to adjust metaheuristic parameters for a collection of samples in a good way which has less efficiency for other samples.Different problems of travelling salesman have been solved with different sizes and structures by the algorithm. For all instances, 9, 2, and 0.2% are allocated for∝,β, and q, respectively (Table 4).Table 4
Searching for optimized solution of different travelling salesman problems.
Instance
Best known
First sol.
Best sol.
Average sol.
Worst sol.
Error
ftv33
1286
1462
1286
1286
1286
0.0000000
ftv38
1530
1591
1530
1535
1546
0.0032679
swiss42
1273
1364
1273
1273
1273
0.0000000
ftv44
1613
1742
1615
1619
1625
0.0037197
ry48p
14422
15341
14466
14493
14507
0.0049230
berlin52
7542
7951
7542
7542
7542
0.0000000
ftv64
1839
2022
1909
1925
1940
0.0467645
eil76
538
559
538
538
538
0.0000000
eil101
629
717
630
638
650
0.0143084The optimal path length of the algorithm’s iterations for berlin52 is shown in Figure2.Figure 2
The optimal path length of proposed algorithm for berlin52.According to the obtained results, it is noticeable that the algorithm achieves proper answers quickly so that the answer of the first iteration will be a good and acceptable answer. Accordingly, although the suggested algorithm shows its success alone in this issue, it can be used as a powerful initial solution generator for other solution-based metaheuristics in order to use advantages of other algorithms and getting more close to the optimized answer.


## 5.1. Quality of Solutions

In order to estimate the algorithm function from absolute difference obtained by optimized answer, the following relation is used:(10)|f(s)-f(s*)|f(s*),
so that s is the obtained answer and s* is the optimized answer.


## 5.2. Robustness

Metaheuristics must be able to act properly in an extended range of samples or problems with the same parameters. It is possible to adjust metaheuristic parameters for a collection of samples in a good way which has less efficiency for other samples.Different problems of travelling salesman have been solved with different sizes and structures by the algorithm. For all instances, 9, 2, and 0.2% are allocated for∝,β, and q, respectively (Table 4).Table 4
Searching for optimized solution of different travelling salesman problems.
Instance
Best known
First sol.
Best sol.
Average sol.
Worst sol.
Error
ftv33
1286
1462
1286
1286
1286
0.0000000
ftv38
1530
1591
1530
1535
1546
0.0032679
swiss42
1273
1364
1273
1273
1273
0.0000000
ftv44
1613
1742
1615
1619
1625
0.0037197
ry48p
14422
15341
14466
14493
14507
0.0049230
berlin52
7542
7951
7542
7542
7542
0.0000000
ftv64
1839
2022
1909
1925
1940
0.0467645
eil76
538
559
538
538
538
0.0000000
eil101
629
717
630
638
650
0.0143084The optimal path length of the algorithm’s iterations for berlin52 is shown in Figure2.Figure 2
The optimal path length of proposed algorithm for berlin52.According to the obtained results, it is noticeable that the algorithm achieves proper answers quickly so that the answer of the first iteration will be a good and acceptable answer. Accordingly, although the suggested algorithm shows its success alone in this issue, it can be used as a powerful initial solution generator for other solution-based metaheuristics in order to use advantages of other algorithms and getting more close to the optimized answer.


## 6. Conclusion

In this paper we presented a new metaheuristic that has new insight into network problems. At the end of every iteration, the algorithm also tries to improve both the performance of the algorithm and the quality of solutions for the Tsp by using local search algorithms in the name of 2-Opt and 3-Opt. As a result, the proposed algorithm can be used for variety network problems due to its insight to these kinds of problems. Therefore, through extending this behaviour we can move toward solving different optimization problems by this algorithm in a way that each position of problem solutions represents a node and each algorithm step is passing from one state to another state. Future work will be conducted to improve the proposed algorithm and examine other local search algorithms to enhance the performance of the method for improving solutions. Additional improvements might lie on the combination of our approach with the other metaheuristics like genetic algorithm, tabu search, simulated annealing, and so on.



---

*Source: 347825-2013-07-18.xml*