<figure><img src="image_1.png" /></figure>

HAL
open science

# Probe Machine Based Consecutive Route Filtering Approach to Symmetric Travelling Salesman Problem

Md. Azizur Rahman, Jinwen Ma

<figure><img src="image_2.png" /></figure>

## ► To cite this version:

Md. Azizur Rahman, Jinwen Ma. Probe Machine Based Consecutive Route Filtering Approach to Symmetric Travelling Salesman Problem. 2nd International Conference on Intelligence Science (ICIS), Nov 2018, Beijing, China. pp.378-387, 10.1007/978-3-030-01313-4_41. http-02118813

HAL Id: hal-02118813

https://inria.hal.science/hal-02118813

Submitted on 3 May 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Probe Machine Based Consecutive Route Filtering Approach to Symmetric Travelling Salesman Problem

Md. Azizur Rahman and Jinwen Ma*

Department of Information Science
School of Mathematical Sciences & LMAM
Peking University, Beijing, 100871, P.R. China
mdazizur201171@pku.edu.cn, jwma@math.pku.edu.cn

**Abstract.** The travelling salesman problem (TSP) is one of the NPC combinatorial optimization problems and still now it remains as an interesting and challenging problem in the field of combinatorial optimization. In this paper, we propose a consecutive route filtering approach to solving the symmetric TSP with the help of probe concept such that the worse routes are filtered out step by step by using a rigorous predesigned step proportion. In this way, it is important to set up a reasonable value of the step proportion which is needed in each step during the filtering process. Actually, our proposed algorithm is implemented on the set of symmetric TSP benchmarks with both small and large numbers of cities from the TSPLIB dataset. It is demonstrated by the experimental results that our proposed algorithm can obtain the best results in some cases and generally get the approximation results close to the best known solutions.

**Keywords:** Probe Machine· Travelling Salesman Problem· Filtering Proportion· Discrete Optimization.

## 1 Introduction

In the field of combinatorial optimization, TSP is arguably the most prominent, popular, and widely studied problem. It belongs to the class of NP-complete problems [1], i.e., the most difficult problems without any exact algorithm to effectively solve it in polynomial time. In fact, with the increase of number of cities, the executive time of any existing algorithm increases super-polynomially or even almost exponentially [2]. So, its improvement has been drawn much attention to researchers due to the growing demands from vast practical applications in different areas relevant to real life such as vehicle routing, drilling holes in a circuit board, overhauling gas turbine engine, X-ray diffraction, storage and picking of stock in warehousing, computer wiring, interview scheduling, crew scheduling,

<footnote>* Corresponding author.</footnote>
mission planning, DNA sequencing, data association, image processing, pattern recognition and so on [3, 4].

Originally, this problem comes into being with a salesman who wants to visit every city exactly once from a list of cities to sell his products and finally return to the starting city where his purpose is to minimize the total tour cost. In graph theory, the symmetric TSP is defined by a complete undirected graph $G = (V, E)$, where $V = \{v_1, v_2, \dots, v_N\}$ is the set of nodes and $E = \{(v_i, v_j) : v_i, v_j \in V, i \neq j\}$ represent the set of edges [3]. Moreover, a symmetric cost matrix $D_{N \times N}$ is assigned on $E$ for representing the weight of edges. Also, the TSP can be stated as a permutation problem [24, 25] with the motive of finding a permutation $\psi$ among $N$ cities that minimize the following objective function:

$$f(\psi) = \sum_{i=1}^{N-1} d_{\psi(i), \psi(i+1)} + d_{\psi(N), \psi(1)} \quad (1)$$

where $\psi(i)$ indicate the city which is visited at step $i$, $i = 1, 2, \dots, N$ and $f(\psi)$ is the cost of a permutation $\psi$. The Euclidean distance $d_{i,j}$, between any two cities $i(x_1, y_1)$ and $j(x_2, y_2)$ is calculated by:

$$d_{i,j} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \quad (2)$$

In the case of symmetric TSP, the distance from city $i$ to city $j$ is the same as the distance from city $j$ to city $i$, i.e., $d_{i,j} = d_{j,i}$.

Although the TSP problem is quite simple, the main complexity comes from the large number of possible solutions. To solve an $N$-city symmetric TSP problem, $(N-1)!/2$ different possible routes arise so that the direct optimization procedure cannot accomplish in a polynomial time. For this reason, researchers have been trying to solve this problem in two alternative ways instead of finding the exact solution. The first way is to develop an optimization algorithm to ensure the optimal solution with longer running time, while the second way is to develop a heuristical algorithm which can reduce the computational time significantly and provide only near-optimal solution.

The objective of this work is to propose a new algorithm to solve the symmetric TSP with the help of probe machine. The proposed approach is able to filter out worse routes and keep potential routes step by step by using an appropriate choice of proportion value. The rest of the paper is organized as follows. We review some related works in Section 2. Section 3 presents our proposed framework. The experimental results are summarized in Section 4 and the final section gives the conclusion and future research.

## 2 Related Work

During the past decades, various TSP algorithms have been proposed for finding an optimal or near-optimal solution. Branch and bound algorithm [5], dynamic programming algorithm [6] and cutting plane algorithms [7] are most popular
and well known. However, these algorithms are limited to small size instances
and unable to implement in large-scale problems. To get rid of this limitation,
researchers have developed the heuristic methods. In fact, the nearest neighbour
algorithm (NNA) [8] is a simple and easily implementable heuristic algorithm. It
starts with a randomly chosen city and adds the nearest unvisited city step by
step until all the cities are contained in the tour. Rosenkrantz et al. [9] developed
a repetitive nearest neighbour algorithm (RNNA) and insertion algorithm (IA)
to extend the NNA.

Several algorithms were reported to launch with a complete route and im-
prove it iteratively through a simple modification. 2-opt [10] and 3-opt [11] are
exoteric methods in this category, where a few edges (2 for 2-opt and 3 for 3-opt)
are firstly removed from the current tour and then replace them by the corre-
sponding number of different edges to obtain a shorter tour. Lin and Kernighan
[12] enlarged this concept to k-opt where k is chosen in a reasonable way. The
variable neighbourhood search (VNS) [13,14] was also based on the neighbours
that are obtained iteratively by a systematic change of the node of the initial
tour. Most recently, Hore et al. [15] made a significant improvement on the VNS
algorithm.

In this context, population-based metaheuristic algorithms draw much more
attention among the researchers in the long run. Simulated annealing (SA) [16]
can be successfully applied to get a global optimal solution, but it requires longer
computational time. Several types of Genetic algorithms (GAs) [17] are also in-
troduced to rely on the principles of natural selection and genetics, and there are
some developments using the assorted operator and selection methods [18]. Ant
colony optimization (ACO) [19] is an alternative technique which depends on
the foraging behaviour of ant colony and its modifications are also reported in
some works [20-22]. Recent population-based algorithm referred to as Symbiotic
organisms search (SOS) proposed by Cheng and Prayogo [23] employs the opti-
mization scheme through the mutualism, commensalism and parasitism phase,
and an extension of this algorithm developed by Ezugwu et al. [24] strengthens
the use of the mutation operator in the local search process.

However, population-based methods can solve the TSP problem quickly, but
might be easily trapped into a local optimum solution because there are a group
of random numbers and fine-tuning parameters in the process. Certainly, some
hybrid algorithms can be established to enhance the overall algorithm perfor-
mance. Recently, Ezugwu et al. [25] proposed a hybrid optimization algorithm
which fuses the SOS and SA algorithm together. On the other hand, Ozden et al.
[26] demonstrated how the parallel computing techniques can be used for TSP
and significantly decrease the overall computational time with the increase of
CPU utilization.

## 3 Proposed Algorithm

In the proposed framework, we take an attempt to solve the symmetric TSP
with the help of probe concept by using a rigorous step proportion value which
filters out worse route gradually and finally reaches to an optimal route. For an N-city problem, the process needs to complete [N/2] steps, where

$$ [N/2] = \begin{cases} \frac{N}{2} & \text{if N is even} \\ \frac{N-1}{2} & \text{if N is odd} \end{cases} \qquad (3) $$

The concept of probe, working steps of our proposed framework and the filtering proportion value in each step are given in details in the following subsection consecutively.

## 3.1 Probe Concept

Actually, the probe is a tool which is used to detect a certain substance accurately. The hypothetical probe machine was introduced by Xu [27], in which there were two types of probes: connective and transitive probes. The connective probes were used to connect two data, while the transitive probes were used to pass information from one data to another data through the data fibers. The probe machine was used to solve two types of NP-complete problems: Hamilton and the graph colouring problem. By the inspiration of his work, we try to present a new type of probe and also present a new filtering mechanism for solving the symmetric TSP using a proportion value. Here, each of the sub-route treats as a probe which is able to automatically find out two unvisited cities and connect them through their wings. In this way, each probe gradually enhances in every step and continue until all cities are included in the route. A sample of 3 cities probe and 5, 7, 9 cities probes generated from 3 cities probe in first four steps are shown in Fig.1. In the Fig.1., the sample probes are denoted by $x_{ijk}$, $x_{ijklm}$, $x_{ijklmnp}$, $x_{ijklmnpst}$ and their wings are as follows:

$$ \omega(x_{ijk}) = \{x_{ijk}^j, x_{ijk}^k\}, \omega(x_{ijklm}) = \{x_{ijklm}^l, x_{ijklm}^m\} $$

$$ \omega(x_{ijklmnp}) = \{x_{ijklmnp}^n, x_{ijklmnp}^p\}, \omega(x_{ijklmnpst}) = \{x_{ijklmnpst}^s, x_{ijklmnpst}^t\} $$

## 3.2 Working Steps

The proposed algorithm accomplishes two tasks in each step. That is, it firstly generates the possible probes and then filters out the worse probes. The whole process consists of several steps which are described in details in the followings:

**Step-1:** In the first step, the process generates three city probes by considering two paths for each city position. The two path is constructed with an internal city having other two cities that are adjacent to the internal city. More formally, consider $c_i$, $c_j$ and $c_k$ are three different cities, where $c_i$ is the internal city with $c_j$ and $c_k$ are two different cities both are adjacent to $c_i$, then the set of all two paths with internal city $c_i$ is denoted by $F^2(c_i)$ and is defined by Eq. (4)[27]:

$$ F^2(c_i) = \{c_j c_i c_k \triangleq x_{ijk} : c_j, c_k \in I(c_i); i, j, k \text{ are mutually different}\} \quad (4) $$
<figure><img src="image_4.png" /><figcaption>Fig. 1. A sample of 3, 5, 7 and 9 cities probes with their wings.</figcaption></figure>

where $I(c_i)$ is the set of cities adjacent to $c_i$ and $x_{ijk}$ represent the probe that covers three cities $c_i$, $c_j$ and $c_k$. Thus, we construct all possible three cities probe for an $N$-city problem as follows:

$$X_3 = \cup_{i=1}^{N} F^2(c_i) = \cup_{i=1}^{N} \{x_{ijk} : c_j, c_k \in I(c_i); i \neq j, k; k \neq j\} \quad (5)$$

So there are $N_3 = |X_3| = \frac{N(N-1)(N-2)}{2}$ such types of 3 city probes produced in the first step for an $N$-city symmetric problem. Each probe $x_{ijk}$ has exactly two types of wings $x_{ijk}^j$ and $x_{ijk}^k$, and this wing includes two other unvisited cities automatically on the probe in next step.

The filtering process starts after the probes have been created. In this phase, the system keeps some potential probes by using a proportion value defined in subsection 3.3 and we consider these probes as good probes. The algorithm adopts Euclidean distance (defined in Eq. (2)) to calculate the cost of the probes, and based on the cost it keeps the best $N_{G_3}$ probes. Consequently, those probes are good whose best order lies within the range $[1, N_{G_3}]$, where $N_{G_3}$ indicates the total number of good probes with 3 cities. If we choose $\alpha_3$ as a proportion value in the first step, then the total number of good probes is as follows:

$$N_{G_3} = |G_3| = \alpha_3 N_3, G_3 \subset X_3 \quad (6)$$

where $G_3$ is the set of all good probes after completing the filtering task in first step.

**Step-2:** Based on good probes obtained from the first step, the algorithm produces 5 cities probe in the second step. Each good probes enlarge the route through the wings by adding two unvisited cities. In this step, the system needs to add exactly two cities in the probe from the remaining ($N - 3$) unvisited cities. So based on $G_3$, the probe can be built by the following ways:

$$X_5 = \{c_l c_j c_i c_k c_m \triangleq x_{ijklm} : c_j c_i c_k \in G_3; c_l, c_m \in R_{N-3}(c_j c_i c_k); i \neq j \neq k \neq l \neq m\} \quad (7)$$
where $R_{N-3}(c_j c_i c_k)$ is the set of remaining unvisited cities corresponding to good probe $c_j c_i c_k$, i.e., $R_{N-3}(c_j c_i c_k) = \{c_1, c_2, \dots, c_N\} - \{c_i, c_j, c_k\}$. It is noted that the two city $c_l$ and $c_m$ are chosen in both order from $R_{N-3}(c_j c_i c_k)$. Hence, the total produced probe is estimated based on Eq. (8):

$$N_5 = |X_5| = 2N_{G_3}\binom{N-3}{2} = N_{G_3}(N-3)(N-4) \quad (8)$$

After generating 5 cities probe the process also takes a filtering proportion value in this step which gives some good probes and this probe will be used in the next step to create 7 cities probe. Therefore, the number of good probes at the end of this stage can be calculated by the following equation:

$$N_{G_5} = |G_5| = \alpha_5 N_5, G_5 \subset X_5 \quad (9)$$

where $\alpha_5$ represent the filtering proportion value in the step and $G_5$ is the set of all good 5 cities probe, respectively.

**Step-(k+1):** The $(k+1)^{th}$ step of the procedure starts with the good probes $(G_{2k+1})$ and their corresponding cost which are obtained from $k^{th}$ step, where

$$N_{G_{2k+1}} = |G_{2k+1}| = \alpha_{2k+1} N_{2k+1} \quad (10)$$

In the above Eq. (10), $N_{G_{2k+1}}$ indicates the number of total good probes, $\alpha_{2k+1}$ is the filtering proportion value and $N_{2k+1}$ represent the set of possible generated probes in $k^{th}$ step. There are $(2k+1)$ cities in each probe of the above mentioned good probes. In fact, when the algorithm arrive in this step, it needs to include $(N - 2k - 1)$ more cities in the probe. By adding two cities from $(N - 2k - 1)$, each probe becomes $(2k+3)$ cities probe. The set of creates probe in the current step based on good probes $(G_{2k+1})$ is denoted by $X_{2k+3}$ and is defined by:

$$X_{2k+3} = \underbrace{\{c_s \quad \overbrace{c_l c_j \dots c_k c_m}^{(2k+1)\text{cities good probe}} \quad c_t : c_l \dots c_m \in G_{2k+1}; c_s, c_t \in R_{N-2k-1}(c_l \dots c_m), s \neq t\}}_{(2k+3)\text{cities probe}} \quad (11)$$

The two cities $c_s$ and $c_t$ are taken in both ways, i.e., $(c_s, c_t)$ and $(c_t, c_s)$ both are included and $R_{N-2k-1}(c_l \dots c_m) = \{c_1, c_2, \dots, c_N\} - \{c_l, c_j, \dots, c_k, c_m\}$. The total produced probes in this step as shown in Eq. (12):

$$N_{2k+3} = |X_{2k+3}| = 2N_{G_{2k+1}}\binom{N-2k-1}{2} = N_{G_{2k+1}}(N-2k-1)(N-2k-2) \quad (12)$$

Now, the algorithm adopts a filtering proportion value $\alpha_{2k+3}$ that filled out the potential probe. So the number of good probes with $(2k+3)$ cities obtained as:

$$N_{G_{2k+3}} = |G_{2k+3}| = \alpha_{2k+3} N_{2k+3}, G_{2k+3} \subset X_{2k+3} \quad (13)$$

where $G_{2k+3}$ is the set of all good probes at the end of this step.

In this way, the probe construction and filtering mechanism continue until all the cities are contained in the probe. When the algorithm reaches in the
last step, it generates probes of N cities and finds out the best probes from all generated probes. It is important to mention that in the last step of the even number of problems, there is one city remaining to visit, in this case the probe uses any one of its wings to include the city properly.

### 3.3 Filtering Proportion in Each Step

The filtering proportion plays a vital role in our proposed framework. Usually, an inappropriate choice of proportion value leads to trap the whole process and yields a worse solution as well as take longer running time. So it is very challenging task to design an efficient filtering proportion value that keeps potential probes from produced probes in each step. In this work, we address a filtering proportion value of $k^{th}$ step through the experiments by trial and error method that is denoted as $\alpha_{2k+1}$ and defined as:

$$ \alpha_{2k+1} = \frac{C}{N + \sqrt{k}}; k = 1, 2, 3, \dots \qquad (14) $$

where N represents the number of cities and C is the constant. The above proportion value has been chosen in such a way that it decreases slowly step by step, i.e., it maintains the relation $\alpha_3 > \alpha_5 > \dots > \alpha_{2k+1} > \alpha_{2k+3} > \dots$. During the experiment, we found that the number of good probes increases with the gradually decreases of proportion value in each step, but after a certain step later it also starts to decrease. In some cases, we use some strategies in the remaining steps such as trade off to decrease the proportion value and sometimes it is increased by $\frac{1}{(N-2k-1)(N-2k-2)}$. By the experiment, we estimated that the value of C lie within the interval $[\frac{2(N+1)}{N(N-1)(N-2)}, \frac{800(N+1)}{N(N-1)(N-2)}]$ for our computational results.

## 4 Experimental Results

In this section, we conduct a number of experiments for measuring the capability of our proposed framework based on several TSPLIB [28, 29] datasets ranging from 14 up to 1432 cities. Actually, TSPLIB is a publicly available library that contains the sample of TSP instances and their corresponding optimum solutions. The technical computations in this study are performed in MATLAB R2016b software by using 4 core GPU system. The average required time is measured by running each instance ten (10) consecutive times. The experimental results from our experiments have been displayed in Table 1. In the left part of the table, the first column represents the serial number (S/N) of the instances, the second column contains the name of each instance, in the third column “Scale” denote the total number of cities in each instance, the fourth column “Results” stands for the length of obtained solution from the experiment, the fifth one represent average required times (in seconds) of each instance, the sixth column available for the best known results (BKR) obtained from the TSPLIB and the right part of the table brings similar indicator as the left part.
<table><caption>**Table 1.** The computational results of the proposed algorithm for the symmetric TSP</caption><thead><tr><th>S/N</th><th>Instances</th><th>Scale</th><th>Results</th><th>Time(Se.)</th><th>BKR</th><th>S/N</th><th>Instances</th><th>Scale</th><th>Results</th><th>Time(Se.)</th><th>BKR</th></tr></thead><tbody><tr><td>1</td><td>burma14</td><td>14</td><td>3323</td><td>2.1148</td><td>3323</td><td>38</td><td>u159</td><td>159</td><td>51624</td><td>137.3</td><td>42080</td></tr><tr><td>2</td><td>p01</td><td>15</td><td>291</td><td>0.0101</td><td>291</td><td>39</td><td>si175</td><td>175</td><td>22051</td><td>166.0453</td><td>21407</td></tr><tr><td>3</td><td>ulysses16</td><td>16</td><td>6859</td><td>4.1738</td><td>6859</td><td>40</td><td>brg180</td><td>180</td><td>1960</td><td>347.3403</td><td>1950</td></tr><tr><td>4</td><td>gr17</td><td>17</td><td>2085</td><td>0.0181</td><td>2085</td><td>41</td><td>rat195</td><td>195</td><td>2512.8</td><td>6.1452</td><td>2323</td></tr><tr><td>5</td><td>gr21</td><td>21</td><td>2707</td><td>0.3412</td><td>2707</td><td>42</td><td>d198</td><td>198</td><td>17366</td><td>2.2832</td><td>15780</td></tr><tr><td>6</td><td>gr24</td><td>24</td><td>1272</td><td>31.278</td><td>1272</td><td>43</td><td>kroA200</td><td>200</td><td>35420</td><td>2.1057</td><td>29368</td></tr><tr><td>7</td><td>fri26</td><td>26</td><td>937</td><td>0.4982</td><td>937</td><td>44</td><td>kroB200</td><td>200</td><td>35895</td><td>2.3493</td><td>29437</td></tr><tr><td>8</td><td>bays29</td><td>29</td><td>2093</td><td>613.2</td><td>2020</td><td>45</td><td>ts225</td><td>225</td><td>135000</td><td>958.7</td><td>126643</td></tr><tr><td>9</td><td>bayg29</td><td>29</td><td>1667</td><td>0.0282</td><td>1610</td><td>46</td><td>tsp225</td><td>225</td><td>4550.5</td><td>16.8851</td><td>3916</td></tr><tr><td>10</td><td>dantzig42</td><td>42</td><td>762</td><td>93.6</td><td>699</td><td>47</td><td>pr226</td><td>226</td><td>94850</td><td>863.8</td><td>80369</td></tr><tr><td>11</td><td>swiss42</td><td>42</td><td>1376</td><td>11.8</td><td>1273</td><td>48</td><td>gil262</td><td>262</td><td>2736.7</td><td>12.0015</td><td>2378</td></tr><tr><td>12</td><td>att48</td><td>48</td><td>10671</td><td>1265.2</td><td>10628</td><td>49</td><td>a280</td><td>280</td><td>3111.8</td><td>8.1597</td><td>2579</td></tr><tr><td>13</td><td>hk48</td><td>48</td><td>11461</td><td>206.8</td><td>11461</td><td>50</td><td>pr299</td><td>299</td><td>57931</td><td>43.1237</td><td>48191</td></tr><tr><td>14</td><td>eil51</td><td>51</td><td>455.86</td><td>17.48</td><td>426</td><td>51</td><td>lin318</td><td>318</td><td>52547</td><td>65.6026</td><td>42029</td></tr><tr><td>15</td><td>berlin52</td><td>52</td><td>7982.2</td><td>3.3017</td><td>7542</td><td>52</td><td>rd400</td><td>400</td><td>18581</td><td>101.6123</td><td>15281</td></tr><tr><td>16</td><td>brazil58</td><td>58</td><td>25649</td><td>2.2556</td><td>25395</td><td>53</td><td>fl417</td><td>417</td><td>15406</td><td>44.7756</td><td>11861</td></tr><tr><td>17</td><td>st70</td><td>70</td><td>762.34</td><td>0.1033</td><td>675</td><td>54</td><td>pcb442</td><td>442</td><td>61346</td><td>55.0617</td><td>50778</td></tr><tr><td>18</td><td>eil76</td><td>76</td><td>601.46</td><td>39.8</td><td>538</td><td>55</td><td>d493</td><td>493</td><td>42408</td><td>136.3764</td><td>35002</td></tr><tr><td>19</td><td>pr76</td><td>76</td><td>124740</td><td>63.4</td><td>108159</td><td>56</td><td>att532</td><td>532</td><td>34239</td><td>258.6158</td><td>27686</td></tr><tr><td>20</td><td>gr96</td><td>96</td><td>61741</td><td>2119.6</td><td>55209</td><td>57</td><td>si535</td><td>535</td><td>50286</td><td>322.1954</td><td>48450</td></tr><tr><td>21</td><td>rat99</td><td>99</td><td>1443.6</td><td>0.9600</td><td>1211</td><td>58</td><td>pa561</td><td>561</td><td>3313</td><td>248.8954</td><td>2763</td></tr><tr><td>22</td><td>rd100</td><td>100</td><td>9283</td><td>21.5</td><td>7910</td><td>59</td><td>u574</td><td>574</td><td>46191</td><td>290.0283</td><td>36905</td></tr><tr><td>23</td><td>kroA100</td><td>100</td><td>24511</td><td>0.2025</td><td>21282</td><td>60</td><td>rat575</td><td>575</td><td>8066.2</td><td>272.50</td><td>6773</td></tr><tr><td>24</td><td>kroB100</td><td>100</td><td>23568</td><td>0.3084</td><td>22141</td><td>61</td><td>p654</td><td>654</td><td>48380</td><td>1489.9</td><td>34643</td></tr><tr><td>25</td><td>kroD100</td><td>100</td><td>25767</td><td>45.3334</td><td>21294</td><td>62</td><td>d657</td><td>657</td><td>63099</td><td>282.42</td><td>48912</td></tr><tr><td>26</td><td>kroE100</td><td>100</td><td>24571</td><td>0.4640</td><td>22068</td><td>63</td><td>u724</td><td>724</td><td>50391</td><td>399.1771</td><td>41910</td></tr><tr><td>27</td><td>eil101</td><td>101</td><td>729.2</td><td>83.4142</td><td>629</td><td>64</td><td>rat783</td><td>783</td><td>11140</td><td>558.2935</td><td>8806</td></tr><tr><td>28</td><td>lin105</td><td>105</td><td>16638</td><td>68.2125</td><td>14379</td><td>65</td><td>pr1002</td><td>1002</td><td>314850</td><td>1566.7</td><td>259045</td></tr><tr><td>29</td><td>pr107</td><td>107</td><td>50448</td><td>36.26</td><td>44303</td><td>66</td><td>si1032</td><td>1032</td><td>96145</td><td>1737.3</td><td>92650</td></tr><tr><td>30</td><td>gr120</td><td>120</td><td>8255</td><td>59.3458</td><td>6942</td><td>67</td><td>u1060</td><td>1060</td><td>287620</td><td>2584.8</td><td>224094</td></tr><tr><td>31</td><td>pr124</td><td>124</td><td>70605</td><td>80.9855</td><td>59030</td><td>68</td><td>vm1084</td><td>1084</td><td>305270</td><td>2816.4</td><td>239297</td></tr><tr><td>32</td><td>bier127</td><td>127</td><td>132320</td><td>383.1</td><td>118282</td><td>69</td><td>pcb1173</td><td>1173</td><td>73093</td><td>2408.1</td><td>56892</td></tr><tr><td>33</td><td>ch130</td><td>130</td><td>7002</td><td>1.2577</td><td>6110</td><td>70</td><td>d1291</td><td>1291</td><td>64050.8</td><td>4280.1</td><td>50801</td></tr><tr><td>34</td><td>pr136</td><td>136</td><td>116580</td><td>2.2622</td><td>96772</td><td>71</td><td>rl1304</td><td>1304</td><td>323060</td><td>4228.5</td><td>252948</td></tr><tr><td>35</td><td>pr144</td><td>144</td><td>62370</td><td>356.24</td><td>58537</td><td>72</td><td>rl1323</td><td>1323</td><td>357230</td><td>4386.1</td><td>270199</td></tr><tr><td>36</td><td>ch150</td><td>150</td><td>7195.8</td><td>0.800</td><td>6528</td><td>73</td><td>nrw1379</td><td>1379</td><td>68157</td><td>4541.2</td><td>56638</td></tr><tr><td>37</td><td>kroB150</td><td>150</td><td>29319</td><td>5.7321</td><td>26130</td><td>74</td><td>u1432</td><td>1432</td><td>190400</td><td>5494.4</td><td>152970</td></tr></tbody></table>
# 5 Conclusion and Future Research

We have established a consecutive route filtering approach with the help of probe concept by using an appropriate filtering proportion value in each step as a new approach to solving the symmetric TSP. From our experimental results, it is found that the proposed approach can effectively reach at the optimum point to all of the tested datasets that contain up to 26 cities and also for the 48 cities dataset (hk48, Instance no. 13 in Table 1.). It is also noted that our obtained solutions are close to the best known solution of some other datasets whereas, the performance of our implemented algorithm is also satisfactory on big scale datasets. In the future, we try to investigate more effective and efficient filtering approach to implement this framework to solve the existing asymmetric travelling salesman problems (aTSPs) and the multi travelling salesman problems (mTSPs). In addition, it is also a good direction to fuse this algorithm with the other existing heuristic or meta-heuristic algorithms together in our further study.

# Acknowledgment

This work is supported by the Natural Science Foundation of China for Grant 61171138.

# References

1. Papadimitriou, C.H.: The euclidean traveling salesman problem is NP-complete. Theoretical Computer Science 4(3), 237-244 (1977)

2. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)

3. Matai, R., Singh, S.P., Mittal, M.L.: Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches. Traveling Salesman Problem, Theory and Applications. Prof. Donald Davendra (Ed.), InTech, 1-24 (2010)

4. MacGregor, J.N., Chu, Y.: Human Performance on the Traveling Salesman and Related Problems: A Review. The Journal of Problem Solving 3(2), Article 2 (2011)

5. Finke, G., Claus, A., Gunn, E.: A two-commodity network flow approach to the traveling salesman problem. Congressus Numerantium 41, 167-178 (1984)

6. Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics 10(1), 196-210 (1962)

7. Fleischmann, B.: A cutting plane procedure for the travelling salesman problem on road networks. European Journal of Operational Research 21(3), 307-317 (1985)

8. Bellmore, M., Nemhauser, G.L.: The traveling salesman problem: A survey. Operations Research 16(3), 538-558 (1968)

9. Rosenkrantz, D.J., Stearns, R.E., Philip, M.L.I.: An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing 6(3), 563-581 (1977)

10. Croes, G.A.: A method for solving traveling-salesman problems. Operations Research 6(6), 791-812 (1958)
11. Lin, S.: Computer solutions of the travelling salesman problem. Bell Systems Technical Journal **44**(10), 2245-2269 (1965)

12. Lin, S., Kernighan, B.W: An effective heuristic algorithm for the traveling salesman problem. Operations Research **21**(2), 498-516 (1973)

13. Hansen, P., Mladenović, N.: An introduction to variable neighborhood search. In: S. Voss, S. Martello, I. Osman, C. C. Roucairol (Eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, MA, USA, 433-458 (1999)

14. Hansen, P., Mladenović, N.: Variable neighborhood search: principles and applications. European Journal of Operational Research **130**(3), 449-467 (2001)

15. Hore, S., Chatterjee, A., Dewanji, A.: Improving variable neighborhood search to solve the traveling salesman problem. Applied Soft Computing **68**, 83-91 (2018)

16. Kirkpatrick, S., Gelatt, C.D., Vecchi, M.: Optimization by simulated annealing. Science, New Series **220**(4598), 671-680 (1983)

17. Whitley, D.: A genetic algorithm tutorial. Statistics and Computing **4**(2), 65-85 (1994)

18. Guo, D., Chen, H., Wang, B.: An Improved Genetic Algorithm with Decision Function for Solving Travelling Salesman Problem. Proceeding of 12th ISKE. IEEE Conferences, Nanjing, China, pp. 1-7 (2017). https://doi.org/10.1109/ISKE.2017.8258774

19. Colorni, A., Dorigo, M., Maniezzo, V.: Distributed Optimization by Ant Colonies. In: Varela, F. and Bourgine, P., Eds., Proceedings of European Conference on Artificial Life, Paris, France, pp. 134-142 (1991)

20. Shufen, L., Huang, L., Lu, H.: Pheromone Model Selection in Ant Colony Optimization for the Travelling Salesman Problem. Chinese Journal of Electronics **26**(2), 223-229 (2017)

21. Xiong, N., Wu, W., Wu, C.: An Improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks. Autonomous and Sustainable Computing for preparing the Internet of Things Environment **9**(6), 985 (2017)

22. Ratanavilisagul, C.: Modified Ant Colony Optimization with Pheromone Mutation for Travelling Salesman Problem. Proceeding of 14th ECTI-CON. IEEE Conferences, Phuket, Thailand, pp. 411-414 (2017). https://doi.org/10.1109/ECTICon.2017.8096261

23. Cheng, M-Y., Prayogo, D.: Symbiotic Organisms Search: A new metaheuristic optimization algorithm. Computers and Structures **139**, 98-112 (2014)

24. Ezugwu, A.E.-S., Adewumi, A.O.: Discrete symbiotic organisms search algorithm for travelling salesman problem. Expert Systems With Applications **87**, 70-78 (2017)

25. Ezugwu, A.E.-S., Adewumi, A.O., Frîncu, M. E.: Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem. Expert Systems With Applications **77**(1), 189-210 (2017)

26. Ozden, S.G., Smith, A.E., Gue, K.R.: Solving large batches of travelling salesman problems with parallel and distributed computing. Computers and Operations Research **85**, 87-96 (2017)

27. Xu, J.: Probe Machine. IEEE transactions on neural networks and learning systems **27**(7), 1405-1416 (2016)

28. TSPLIB. http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html. Last accessed 16 June 2018

29. https://people.sc.fsu.edu/jburkardt/datasets/tsp/tsp.html. Last accessed 24 June 2018