Abstract: Background and Objective: The Travelling Salesman Problem (TSP) is a challenging problem in combinatorial optimization whose main purpose is to find the shortest path reaching all interconnected cities by straight lines. In spite of many available heuristic methods for solving TSPs, no attempts have been made to evaluate and compare their performances. The purpose of this study is to carry out a comparative evaluation study on Simulated Annealing (SA) and several variation of Tabu Search (TS). Materials and Method: This study considers four heuristic methods, i.e., Simulated Annealing (SA), conventional Tabu Search (TS), Improved Tabu Search (ITS) and modified Reactive Tabu Search (RTS) to solve symmetric TSPs. The algorithms were tested on five chosen benchmark problems. Their performances were compared and the appropriate algorithm for solving TSPs was then identified. The solution quality was evaluated using empirical testing, benchmark solutions and probabilistic analyses. Results: The analysis of computational results showed that the modified RTS algorithm provided a better solution quality in terms of minimizing the objective function of TSPs, while the SA algorithm was useful for obtaining instant solutions for TSPs with a large number of cities. The modified RTS algorithm also performed better compared to the existing heuristic methods. Conclusion: This study has explored the most effective heuristic method for solving TSPs based on the intended solution quality. The algorithms proposed in this study should be considered in solving symmetric travelling salesman problems.
INTRODUCTION
The Traveling Salesman Problem (TSP) is one of the challenging classical combinatorial optimization problems1-3. It can be described as a salesman touring and visiting all of his/her customers at different cities exactly once before returning to his/her home so as to minimize the total distance of the tour. This concept has been applied to many real-life applications, e.g., vehicle routing4, data clustering5 and material handling in a warehouse6,7.
Over the recent decades, the TSP has attracted attention of numerous researchers where various exact e.g., branch and bound and linear programming2 and heuristic algorithms e.g., neural network8 and ant colony9 have been proposed to solve it. Since the exact algorithms only work well for TSPs containing a small number of cities, the heuristic methods are used to find solutions and demonstrate their efficiency for extremely large TSPs. Most widely known heuristic methods for solving TSPs are Genetic Algorithms (GA)10-12, SA1,7 and TS13,14.
These algorithms have been found to be very effective and robust in solving numerous TSPs and can handle TSPs with missing parameters. The survey and comparison of the algorithms has been documented in the literature2,15. Their performances in solving TSPs have also been evaluated and compared in previous studies. For example, Youssef et al.16 compared the performances of TS, GA and SA in terms of the quality of solution, searching progress, the number of iterations and the number of solutions at cost function intervals. Adewole et al.17 meanwhile examined the performances of GA and SA on several benchmarks with a number of cities. Other comparative studies of GA and SA include18-20. All these studies reported that TS performed better than SA in terms of CPU time needed to reach a quality solution.
The performances of TS and SA in solving other types of problems have also been conducted. Hussin and Stutzl21 as an example examined the dependencies of relative performances of TS and SA variants on instance sizes in the Quadratic Assignment Problem (QAP). Battiti and Tecchiolli20 and Chiang and Chiang22 also examined the performances of TS and SA in the QAP and reported that TS performed better than SA. The TS has been claimed to have an advantage over other heuristics techniques because of its intelligent use of memory along with responsive exploration in the solution space23. In spite of this fact, however not any studies comparing the performances of SA and different variations of TS in solving TSPs have been found. This therefore a comparative evaluation study on SA and several variations of TS which known has not been done before is inspired.
The objective of this study is to evaluate the performance of four heuristic methods, i.e., SA, TS, ITS and modified RTS in solving symmetric TSPs. This study extends the work of Lim et al.24,25 who proposed some successful heuristic methods to solve symmetric TSPs whose bi-directional distances between a pair of cities are identical. In brief, they first introduced the ITS algorithm integrating two heuristic algorithms i.e., SA and TS. To improve the solution quality, they then developed the RTS algorithm which dynamically adjusts its tabu list size. In the mean time, Hong et al.26 presented an empirical work to provide a comparable annealing schedule of the SA algorithm. They showed that with the right setting of an annealing schedule, a good solution quality could be achieved. In this study, the performances of the SA, TS, ITS and modified RTS algorithms to solve symmetric TSPs will be evaluated and compared. These four algorithms were analyzed using theoretical analyses and empirical testing. From the analysis of the results, the best algorithm for solving symmetric TSPs can then be identified and reported.
MATERIALS AND METHODSHeuristics methods
Simulated Annealing (SA): The SA is a meta-heuristic optimization method founded on the annealing process of metal re-crystallization27. If this process is allocated with enough time, SA could then find the optimal solution of a considered problem. Based on this analogy of how metal is cool and annealed, each step of the SA algorithm replaces the current solution by a random nearby solution which is gradually decreased during the searching process.
The basic procedure of SA starts with an initial solution which then gradually moves to a nearby solution obtained by a local search. In order to obtain the nearby solution, 2-opt switch procedures which swap 2 cities have been used. The SA algorithm could escape from a local minimum by accepting non-improving moves based on the transition probability controlled by two factors i.e., the difference between the objective functions and the temperature as follows:
where, δ is the cost difference between the candidate neighboring solution and the current solution and tk is the current temperature.
The basic algorithm of SA is as in Fig. 1. The algorithm continues searching as temperature declines and stops once the temperature becomes zero. Thus, the efficiency of the annealing process is significantly affected by its annealing schedule which is controlled by the initial temperature, the cooling rate and the number of iterations which should be performed at each temperature. A favorable annealing schedule through the use of a statistical framework for solving symmetric TSPs has been discussed in detail by Hong et al.26.
Tabu Search (TS): The TS is a meta-heuristic search method created by Glover28. It utilizes a hill climbing search strategy based on a set of elementary moves to diversify the search and a systematic use of memory to avoid any traps at local optimal points. Its key strategy is to move from solution to solution by accepting non-improving moves to the best solution in the neighborhood of the local optimal29. The main advantage of TS lies in the intelligent use of memory along with responsive exploration in the solution space23. The TS does not remember the current and the best solution.However, it keeps memory on the tourthrough the last solution visited to guide the move from the current to the next solution.
In TS, the memory ability is represented by its tabu list size. The use of memory helps intensify in elite regions or diversify the search towards unexplored regions. The balance between the intensification and diversification strategies is used to control and run the search process. To ensure an efficient search process, TS requires search parameters whose values significantly depend on the types of problems. Parameter tuning especially for the tabu list size is often needed to obtain good results29.
The TS has been proved to successfully solve TSPs. However, since its performance depends significantly on its initial solution30, Lim et al.24,25 developed a modified version of TS called the Improve Tabu Search (ITS) algorithm to enhance the initial value of TS Unfortunately, besides the initial solution, the conventional TS and ITS algorithms are still suffering from parameter tuning in their tabu list sizes. In order to dynamically tune the tabu list size, they then presented the modified RTS algorithm to achieve a good balance between intensification and diversification.
| Fig. 1: | Pseudo code of SA |
| Fig. 2: | Pseudo code of improved TS |
Conventional TS: In conventional TS, randomly generate its initial solution and all possible neighbourhood solutions are then started with the 2-opt switch procedures. A new solution is generated by a move which swaps two cities at the current solution. These search processes continue until stopping criteria are met e.g., when the search process has reached the specified number of iterations.
Improved Tabu Search (ITS): The distinct feature of the ITS algorithm is the initial solution generation to promise its good performance31. An initial solution chosen from a local optimal configuration will generate a high quality solution. Lim et al.24 showed that a better performance could be achieved when combining the SA and TS algorithms.
Figure 2 shows the algorithm of ITS. At the beginning, the SA algorithm have been used to generate an initial solution for the ITS algorithm. After that, its neighborhood was explored to get the best neighborhood solution as the current solution using the 2-opt switch procedures. Next, TS algorithm was performing to search the best neighborhood solution as the new current solution for the next iteration. The search process continues until stopping criteria are met. In ITS, the memory on the search process is do not preserve and the tabu list size is always static which is set based on the number of cities of a considered problem.
Modified RTS: The problem of parameter tuning in TS is recovered in RTS which was initially introduced by Battiti and Tecchiolli32. Basically, RTS attempts to remedy the difficulty in choosing an appropriate tabu list size without prior knowledge about the search space structure. The RTS algorithm maintains the basic steps of TS except that its tabu list size is adaptive to a considered problem and the current solution of the search process. Through this appropriate parameter values, a good balance between intensification and diversification can be achieved without requiring a lot of prior experience or appropriate parameter values of the problem. Thus, RTS is one the reactive search methods employing two mechanisms i.e., feedback schemes and escape strategies.
Based on the RTS algorithm, Lim et al.25 developed the modified RTS algorithm which is slightly difference with the RTS algorithm in terms of the reactive mechanism. The algoritm is shown in Fig. 3. In Battiti and Tecchiolli’s algorithm32, its tabu list size depends on the repetition of configuration. However, in modified RTS algorithm, the tabu list size depends on the number of iterations when the solutions do not override the aspiration level. The judgment was made since the repetition of configurations in TSPs is less significant as the number of cities increases. Thus, the RTS algorithm is not so effective in solving TSPs with a large number of cities.
Generally, the procedures of the modified RTS and ITS are the same except their tabu list sizes. In modified RTS, an initial tabu list size was generating based on the number of available cities and keep the memory on the search process. The algorithm then searches the best neighborhood solution as the new current solution for the next iteration and keeps updating the search process. The tabu list size is increased by 1 if the solutions are not improved for a specified number of iterations and reset back to the initial tabu list size if it achieves a specified value of the tabu list size. The search process continues until stopping criteria are met.
RESULTS AND DISCUSSION
Two experiments were conducted to evaluate and compare the four heuristic methods. The first experiment studied the behavior of SA’s schedules to select its suitable schedule for the second experiment. Five dataset will be used to evaluate the performance of the proposed algorithms. These five chosen benchmark problems of symmetric TSPs are hagaregn20, wi29, dj38, eil51 and eil76 ranging in the size of cities from 20-76. These data sets were obtained through three different open access websites. The hagaregn20 was generated using hagaregn applet (http://hagaregn.org.uk/npsudoku/data/demo20.txt “Last Time Access on This Date December 03, 2015”). Meanwhile, wi29 and dj38 are the TSP instances obtained from the World TSP (http://www. tsp.gatech.edu/world/) representing 29 cities in Western Sahara, North Africa and 38 cities in Republic of Djibouti, Horn of Africa, respectively. The other data sets were taken from the TSPLIB library (http://www2.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/ “Last Time Access on This Date December 03, 2015”). The locations of the cities in the data sets are displayed in node coordinates. The distance between two cities is computed using the Euclidean distance Eq. 1 which is then round off to integer numbers:
| (1) |
First experiment: The SA algorithm on a 20-city problem, hagaregn20 was implemented to assist us choose relevant parameter values for SA. Different combinations of annealing schedules were used to select the suitable cooling rate and initial temperature.
Six different cooling rates i.e., 0.5, 0.8, 0.9, 0.99, 0.999 and 0.9999 and three different initial temperatures i.e., 10000, 100000 and 1000000, which formed eighteen combinations of annealing schedules were used in this experiment. Each combination was solved by a number of independent runs each of which consisted of fifty trials. For each trial, the minimum distance was recorded.
The average distance results for the tour from the fifty trials are summarized in Table 1. The data in Table 1 were run as a randomized complete block design to determine the significant difference between the cooling rate and initial temperature. The two-way analysis of variance (ANOVA) was performed using IBM SPSS Statistics 19. The outputs are shown in Table 2 and 3.
Table 3 shows that different cooling rates can affect the performance of SA since there is a significant difference among the five different cooling rates. However, there is no significant difference in performance of SA with different initial temperatures.
| Table 1: | Average distance obtained from 50 trials |
| Fig. 3: | Pseudo code of modified RTS |
Therefore, a reasonable value, 10000, as the initial temperature in the SA algorithm is selected. The results from Table 3 suggested that a slow cooling rate of β = 0.9999 is the best performance among the five different cooling rates.
| Table 2: | Two-way ANOVA output for parameter selection in SA |
| a: R squared = 0.984 (Adjusted R squared = 0.973) and univariate analysis of variance, tests of between-subjects effects dependent variable: Average_dist, df: Degree of freedom | |
| Table 3: | Post hoc test output for six different cooling rates |
| Based on observed means, the error term is mean square (Error) = 147.908 and multiple comparisons average_dist (LSD) | |
| Table 4: | Parameters for the SA algorithm |
Thus, these two parameters were used in evaluating the performance of SA. The parameter values for SA are summarized in Table 4.
Second experiment: The SA, TS, ITS and modified RTS algorithms using Microsoft Visual C++ were executed33. These algorithms were then tested on five chosen benchmark problems of symmetric TSPs which ran on an Intel® CoreTM i3 M390@2.67 GHz CPU. Each benchmark was solved using a number of independent runs; each of which consists of thirty trials. For each trial, a tour was determined by the four variant heuristics algorithms. The parameter settings for the SA algorithm were determined through the empirical testing and statistical analyses from the first experiment as shown in Table 4. Meanwhile, the parameter settings for the TS algorithm are shown in Table 5.
For each trial, the minimum distance of the tour and its computational time were recorded.
For each algorithm, the relative differences, RDbs and RDav, to access its performance will be computed. The RDbs and RDav are computed as follows:
The relative differences were chosen as performance indexes (in percentage) to compare the performances of the four algorithms. A smaller value of the index indicates better algorithm performance, where the performance index of 0 is the optimal performance. The results of the relative differences for the problems are shown in Table 6 and 7. The Opt column shows the benchmark solutions as reported in the literature.
Based on the descriptive statistics in Table 6 and 7, all the performance indexes of the modified RTS algorithm for both RDav and RDbs were relatively smaller than the performance indexes of the other algorithms.
| Table 5: | Parameter settings for the TS algorithm |
| Table 6: | Results of best relative difference (%) for TSP |
| Table 7: | Results of average relative difference (%) for TSP |
This shows that the modified RTS is the best algorithm for solving TSPs in terms of the solution quality. Apart from the descriptive statistics, an inferential statistical test using IBM SPSS Statistics19 also have been employed to discover any significant differences among the performances of the three TS algorithms i.e., conventional TS, ITS and modified RTS. For each data set, there are two kinds of independent sample tests based on the assumptions of the data which are normality and homogeneity of variance.
| Table 8: | Results of assumption tests |
If both of the assumptions are met, the parametric test i.e., one-way analysis of variance (ANOVA) will be used. Otherwise, if either one assumption is violated, the nonparametric test i.e., the Kruskal Wallis test should be used.
For the conventional TS, ITS and modified RTS algorithms, the Shapiro-Wilk normality test using thirty trials for each data set was conducted to show the results of the assumption tests in Table 8. Based on Table 8, only the 5th TSP data set i.e., eil76 fulfilled the assumption of normality since the probability value (p-value) for the other three algorithms were greater than 0.05. However, the variances among the TS algorithms were not constant for the eil76 problem through the levene test. Therefore, the assumptions of the data have been violated for all of the data sets. Thus, Kruskal Wallis test was used in the further data analysis. The results of the Kruskal Wallis test are shown in Table 9.
Table 9 presents that the performance indexes among the three variants of the TS algorithms i.e., conventional TS, ITS and modified RTS differ significantly for each data set since their the p-values were small and less than 0.05.
| Table 9: | Results of Kruskal Wallis test |
The Kruskal Wallis test could not carry out to judge which TS algorithm is much efficiency. Thus, the pairwise comparisons were used to overcome this problem. The results of pairwise comparison are shown in Fig. 4.
Based on the inferential statistics in Fig. 4, the modified RTS is much better than other variant of TS algorithms for each tested data set since all the mean rank of the modified RTS is significantly lower than the other TS algorithms. Apart from the solution quality, the performance of the algorithms was also evaluated based on the computational time needed to obtain the solution. The average computational time (sec) for each algorithm from the thirty trials is summarized in Table 10.
The computational time for each algorithm is not much different when solving a problem with a small sample size (<30 cities). The SA needs less than 20 sec to solve the problem with 76 cities, while the variant of TS algorithms need about 32 min to solve the same problem.
| Fig. 4: | Results of pairwise comparison for the TS algorithm |
| Table 10: | Average computational time in seconds for SA and TS algorithms |
| Table 11: | Comparison of the modified RTS with other various techniques to solve TSP |
However, when the size increases, the computational time for the variants of TS algorithms dramatically increases. The SA algorithm needs less time to obtain the tour compared to the variants of TS algorithms.
Table 11 shows the comparison of the proposed method, modified RTS, with the methods that are applied by various researchers35,36 to solve TSP. Since, the modified RTS algorithm provides a good solution quality in this study. Therefore, the modified RTS is used to do the comparison with other methods that done by various researches. The comparison methods are Particle Swarm Optimization (PSO) and Basic Evolutionary Approach (BEA). The best and average computational results are recorded. Different number of independent runs is done by various researchers to obtain the average result while the best result is given in the brackets. From Table 11, the modified RTS can find better average results than the average results obtained by the four recent algorithms. Furthermore, the computational time for BEA is much slower than the proposed method. The BEA needs as much as 1827 sec and 9547 to solve the problem with 29 cities and 76 cities, respectively.
CONCLUSION
This study presents four heuristic algorithms, i.e., SA, conventional TS, ITS and modified RTS to solve symmetric TSPs. The performances of the four algorithms have been compared to identify the most effective algorithm for solving TSPs. The experiments showed that the modified RTS algorithm provides a good solution quality in terms of minimizing the objective function. Even when compared to the other methods that done by various researchers also prove that the modified RTS is comparable or sometimes better. However, the modified RTS algorithm and the other TS algorithms are more time consuming in obtaining the results for the problem with a large number of cities compared to the SA algorithm. Generally, modified RTS is more effective in producing a good solution quality while SA may be used to obtain instant solutions. As a conclusion, the algorithms proposed in this study should be considered in solving symmetric travelling salesman problems.
To enhance the algorithms, some considerations are suggested. Firstly, dynamic stopping criteria could be applied to increase the efficiency of the algorithms. Next, different move procedures such as 3-opt or multi-opt switch procedures can be used to construct the neighborhood structure. This study can expedite the search process and decrease the computational time. Last but not least, diversification such as multi-start may be applied to improve the quality of solution.