An Empirical Study: Integrating Relative Coordinates with Simulated Annealing to Solve a Traveling Salesman Problem

An Empirical Study: Integrating Relative Coordinates with Simulated Annealing to Solve a Traveling Salesman Problem

Zhendong Huang Xiaojun LiuYingshan Tan 

Institute of Logistics Science and Engineering, Shanghai Maritime University, Shanghai, China

Department of Logistics Management and Engineering, Zhuhai College of Jilin University, Zhuhai, China

Department of Logistics Management and Engineering, Zhuhai College of Jilin University, Zhuhai, China

Corresponding Author Email: 
lxj02041820@163.com
Page: 
175-178
|
DOI: 
https://doi.org/10.18280/mmep.030404
Received: 
N/A
|
Accepted: 
N/A
|
Published: 
31 December 2016
| Citation

OPEN ACCESS

Abstract: 

Travelling Salesman Problem is one of the typical NP-hard problems in combinatorial optimization, which is easy to be described but hard to be solved. Its possible amounts of path increase exponentially with the amounts of city, so it is very difficult to solve it. First this paper introduces Travelling Salesman Problem, gives TSP mathematical description and practical application. In turn, a precise algorithm——the simulated annealing algorithm to the address of TSP is given. And then this paper describes the basic principle of simulated annealing, highlights the basic ideas and key technology. This paper presents a case empirical study of ANJI-CEVA AUTOMOTIVE LOGISTICS CO., LTD. We formulated their problem as a traveling salesman problem and, with the use of relative coordinates of the locations as problem parameters, solved the traveling salesman problem by simulated annealing and our final solution is shown to be a circular path.

Keywords: 

simulated annealing method, traveling salesman problem, city’s relative coordinates

1. Background

Logistics industry is the most important industries in the 21st century. Distribution is critical in logistics. Trucks often need to visit multiple distribution centers and multiple suppliers. This makes the route planning particularly important. Usually, there are a large number of different possible distribution paths. Therefore, enterprises need to adopt a scientific method to select the best path to save logistics costs.

Traveling Salesman Problem (TSP) [1] is defined as follows: there is a traveling businessman who needs to visit a set of cities, with the rules that each city is visited exactly once and the businessman has to return to the starting city at the end. The businessman has to find out the shortest path subject to the above requirements.

TSP is a combination optimization problem, more specifically a route planning problem. We used simulated annealing method to solve a TSP. We found out a shortest path to save transportation costs and improved the efficiency of the distribution procedure for the enterprise.

In the last ten years, there were tremendous studies with the applications of TSP in many fields. For instance, in the classical TSP field, Wang Hui and Xiutang Geng used Neural Networks and ant colony algorithm to solve the TSP [1][2]. In Asymmetrical TSP research filed, Yuichi Nagata and David Soler proposed a new competitive genetic algorithm to solve their problem [3]. J. Majumdar and A.K. Bhunia proposed the ATSP problem [4]. In the field of TSP with pickup and delivery, Hipo1ito Hemandez—Perez established a TSPPD 0-1 integer linear model and developed a branch-and-cut algorithm [5]. Xie Binglei and Huo Jia-zhen expanded the guidelines of the heuristic algorithm such as simulated annealing method and climbing method-Mepolis accepted criteria [6]. In Multiple TSP research field, Anand J. Kulkarni and K. Tai successfully proved by using the method of optimizing PC combination optimization problem [7]. Shuai Yuan, Bradley Skinner, Shoudong Huang, Dikai Liu proposed a new crossover operator to solve a traveling salesman problem [8]. In the research field of large scale TSPs, Chao Ding, Ye Cheng, Miao He showed that clustering of large TSP TLGA is more effective and efficient than the classical genetic algorithm [9]. T.Lust and A.Jaszkiewicz proposed a two-phase Pareto Local Search (2ppls) method with speed-up techniques for the heuristic resolution of the objective traveling salesman problem [10].

Simulated annealing method is one of the most effective methods to solve the TSP problems.  In 1953, M.N Rosenbluth proposed simulated annealing method, which is a heuristic based on Monte Carlo iterative solution method, in the same year that Metropolis published the theory in a newspaper. Scott Kirkpatrick further studied its applications in combination optimization problems in 1983 [11]. Vlado Cerny conducted an independent study on simulated annealing in 1985 [12].

Simulated annealing is an extension of local search algorithm for solving combinatorial optimization problems.  Different from greedy heuristics, simulated annealing method can solve the problem that a search heuristic is trapped at a local optimum, so that its final solution has a better objective value.

2. Using Simulated Annealing to Solve the TSP with City Relative Coordinates

The method of simulated annealing simulates the process of solid annealing, through rising the temperature high enough, then slowly cooling down until solid internal energy to a minimum. When the method is applied to solve the TSP model, solid internal energy can be seen as the objective function, the temperature is regarded as a control parameter. When the temperature is low, for each temperature using the Metropolis criterion [13] and 2 - opt mapping [14], we repeat the current solution “to produce the new calculating objective difference - to accept or abandon” iteration. And gradually lowering the temperature, the algorithm terminates and the current solution is an approximate optimal solution.

In NP-complete problems, simulated annealing algorithm can get an approximate optimal solution in polynomial time. Simulated annealing algorithm has an advantage of finding the global minimum, but there are also disadvantages of slow convergence.

According to the previous description in TSP, it is easy to know the objective function through the total distance of all suppliers, as the parameters are the differences between different suppliers’ locations. Therefore, the TSP problem can be solved.

Distances between cities, are calculated using the Cartesian coordinates of the cities on the map. Due to choose the origin of varying according to the actual situation, so the rectangular coordinate system on the locations of each city can only be relative coordinates (rather than fixed locations). And TSP objective function is only related to the sum of the distance between the cities, so in the absence of error measurement, the use of relative coordinates has flexibility in the solving process. (In this article, the suppliers and cities are treated in a similar fashion.)

We solve the TSP by using a simulated annealing algorithm, which is described as follows. [15]:

(1) The initial temperature, the temperature decline rate and the final temperature setting

The initial temperature, the temperature decline rate and the final temperature are the three important factors affecting the performance of simulated annealing. To explore a larger solution space, the initial temperature should be set to a high value, while the temperature decay rate and the termination temperature should be set to low values. In 1983, Kirkpatrick et al. set the initial temperature to 10, the temperature decline rate to 0.9. In this paper, in order to improve search performance, the initial temperature, the temperature decline rate and the termination temperatures were respectively set to 2000, 0.95, 1-10E (termination temperature as close to zero as possible).

(2) Inner loop

For a given temperature T, by satisfying the conditions stated in sections (C) to (F). The inner loop aims to continuously produce new solutions and find out an optimal solution. This prevents the search process from being trapped at some local optimum.

(3) Generate new solution P ‘(the new path generation)

Use 2-opt mapping [10], let k and m be the two cities to exchange positions in the path sequence.

We randomly generate two different numbers k and m, which are between 1 and 8, with k <m, then the original path: (S1, S2, ..., Sk, Sk +1, ..., Sm, ..., C8) becomes the new path: (C1, C2, ..., Sm, Sk +1, ..., Sk, ..., S8)

(4) Acceptance criteria of the new solution

We solve the PO area to produce another inner path P1, and calculate the difference in between the two objective values:

$\Delta t=C(P 1)-C(P 0)$                                   (1)

METROPOLIS guidelines with the acceptance probability:

$P=\left\{\begin{array}{ll}1 & \text { if } \mathrm{C}(\mathrm{P} 1)-\mathrm{C}(\mathrm{P} 0)<0 \\ \exp \left(\frac{\Delta t}{T}\right) & \text { Otherwise }\end{array}\right.$                          (2)

If P0= (S1, S2, S3, S4, S5, S6, S7, S8), P1= (S1, S2, S4, S3, S5, S6, S7, S8), the C (P0) =29013.9260, C (P1) = 23415.4468. Because C (P1) - C (P0) < 0, so P0 will replace P1 as the new solution.

That is, when the new path is shorter than the original path, the new path is accepted and its current solution; otherwise, the probability of accepting the new solution is exp (t / T). Simulated annealing algorithm is associated with a probability to accept a worse solution. This allows the algorithm to escape from a local optimum and hence it may be able to attain the global optimum.

(5) The end of the inner loop

If the algorithm meets the termination condition, then we regard the current best solution as the optimal solution and the inner loop stops. The algorithm terminates when it has rejected 10,000 consecutive new solutions.

(6) The outer loop and the cooling process

T ∈ R is a control parameter (temperature). The initial value of the temperature T is 2000. The algorithm slowly decreases the value of T and repeats the procedure until the termination criterion is met. Then the algorithm goes back to step 2 as long as T > 0. Therefore, degradation algorithm simulation can be viewed as the analog control parameter decremented Metropolis algorithm iteration.

In this study, the temperature decay rate and termination temperatures were set to 0.95 and 1-10E. Temperature decay rate can reduce a small portion of the temperature, thereby increasing the number of iterations to achieve “slowly cooling” effect. Low termination temperature can make the algorithm more effectively.

According to the above description we solve the TSP based on simulated annealing method to write the c + + code. Through the input coordinates the optimization of the path of the city, the program is mainly composed of four modules, the main program code is as follows:

Main program code: int main()

 {

    init();

    printf(“initial path length: %.4f\n”, bestpath.Length);

         for(int i=0;i<N;)

         {

                   printf(“%d->“, bestpath.City[++i]);

         }

         printf(“%d”, bestpath.City[1]);

        printf(“\n”);

    sa();

    printf(“the optimal path length: %.4f\n”, bestpath.Length);

for(int j=0;j<N;)

         {

                   printf(“%d->“, bestpath.City[++j]);

         }

         printf(“%d”, bestpath.City[1]);

        printf(“\n”);

    return 0;

}

3. Empirical Analysis

3.1 Data sources

Based on Anji’s actual data of “western jiading,town”, there are 17 suppliers. Through a 12m truck after packing plan, it is concluded that the car needs the information of distribution of suppliers (Suchi for incoming warehouse logistics center, that is the distribution vehicle departure and eventually return). The 12m long cargo truck loaded involving eight suppliers as shown in TABLE 1.

Table 1. The coordinates of 12m long cargo truck loaded involving eight suppliers

Code

Address

The X axis (unit: m)

The Y axis (unit: m)

S1

BaoAn road No. 5155(Suchi logistics center)

1967

1067

S2

Jiading Bole south road No. 100

7300

6400

S3

Jiading industrial zone Hongde road No. 1155

6200

4600

S4

Malu town, Jiading district, Baoan road No. 2990

9067

3167

S5

Jiading Yongsheng road No. 2001

6400

5266

S6

Jiading Zhaoxian road No.385

5533

4967

S7

Jiaxin road No.1123

8667

4267

S8

Juchi road 288 Lane 23

4533

4733

3.2 Basic assumptions

We used a the simulated annealing method to solve the TSP, according to the actual situation of the Anji distribution problem. We made the following assumptions.

  1. All the assumptions in TSP have to be satisfied.
  2. The goods are delivered to 3 or more distribution points.
  3. The starting point and distribution point has been the construction of the highway between the delivery point.
  4. There is only one starting vehicle.
  5. Every truck has been identified to corresponding distribution points.
  6. The starting point and distribution point can be found on the map to determine the relative coordinates.
  7. The original distribution path is not an optimal path.

The above assumptions provides the conditions for the establishment of the model.

3.3 Results analysis

We used the simulated annealing algorithm to test with the initial solution P = (S1, S2, S3, S4, S5, S6, S7, S8) and obtained the optimal path is 1 → 4 → 7 → 2 → 5 → 3 → 6 → 8 → 1. The total length of this loop is 19514.2203; while the total length of the initial path 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 1 is 29013.9260.

According to the results, we can get the following conclusions:

(1)The first conclusion

By optimizing the path using simulated annealing method, we can calculate the best pick cycling routes of the area of “Western Jiading”. The total length is 19514.2203 meters. This solution  saves around 9500 meters from the initial solution.

(2)The second conclusion

The length of initial path will vary because of different vendor location entries sequence (the initial solution). However, it is certain that the total number of kilometers shortest cycle paths around 19,514 meters.

(3)The third conclusion

We plot the initial path in Figure 1 and the optimal path in Figure 2.

Figure 1. The initial pick up route of “Western Jiading”

Figure 2. The best pick up route of “Western Jiading”

By comparing these two figures, we show that the simulated annealing method can make a complex original planning path into a circulation path. This path also complies with all the requirements of TSP and is the shortest one.

4. Summary

According to the previous introduction in using simulated annealing method to solve the TSP and the analysis of the example above, we can clearly see that simulated annealing method is able to find out the shortest cycle path quickly and effectively.

In fact, by the algorithm we are able to obtain the best path. The optimized path, compared to the original path, reduces a length of 9500 meters. The results also demonstrated the effectiveness of the simulated annealing algorithm. We used relative coordinates, which allow us to calculate the distances between the suppliers without taking the location of the origin into account. This provides us more flexibility in the establishment of the coordinates system.

Objectively speaking, there is not existing an optimal algorithm for solving TSP problem, the application of each algorithm has its limitations: classic algorithms pursue exact solutions, but the algorithm ignores the consumption of time and space and the feasibility is not high. And modern popular algorithm is the pursuit of approximate solution, reduce the consumption of time and space, but on the results are often not satisfactory. In the future on the study on the algorithm of the TSP should grasp the three aspects: continue to improve existing TSP algorithm, by adopting the idea of artificial intelligence, creating new TSP algorithm, setting the advantages of each algorithm, carrying on the research of hybrid TSP algorithm. At present there are certain achievements. In the near future, there are some better solutions for TSP problem.

  References

[1] Wang Hui, “Comparison of several intelligent algorithms for solving TSP problem in industrial engineering,” Systems Engineering Procedia, vol. 4, pp. 226–235, 2012.

[2] Xiutang Geng, Zhihua Chen, Wei Yang, Deqian Shi, and Kai Zhao, “Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search,”Applied Soft Computing, vol. 11, pp. 3680–3689, 2011.

[3] Yuichi Nagata and David Soler, “A new genetic algorithm for the asymmetric traveling salesman problem,” Expert Systems with Applications, vol. 39, pp. 8947–8953, 2012.

[4] J. Majumdar and A. K. Bhunia, “Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times,” Journal of Computational and Applied Mathematics, vol. 235, pp. 3063–3078, 2011.

[5]  Hipo1ito Hemandez—Perez, Juan—Joso and Salazar-Gonzo1ez, “A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery,” Discrete Applied Mathematics, vol. 145, pp. 126-139, 2004.

[6] Xie Binglei and Huo Jiazhen, “Heuristic algorithm for solving the traveling salesman problem with collecting,” Journal of Tongji University (Natural Science Edition), vol. 1, pp. 63-77, 2006.

[7] Anand J. Kulkarni and K. Tai, “Probability collectives: A multi-agent approach for solving combinatorial optimization problems,” Applied Soft Computing, vol. 10, pp. 759-771, 2010.

[8] Shuai Yuan, Bradley Skinner, Shoudong Huang and Dikai Liu, “ A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms,” European Journal of Operational Research, vol. 228, pp. 72-82, 2013.

[9] Chao Ding,Ye Cheng and Miao He, “Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs,” Tsinghua Science & Technology, vol. 12, pp. 459–465, 2007.

[10] T.Lust and A.Jaszkiewicz, “Speed-up techniques for solving large-scale biobjective TSP,” Computers & Operations Research, vol. 37, pp. 521–533, 2010. 

[11] Kirkpatrick, S. Gelatt, C. D.Vecchi and M. P, “Optimization by simulated annealing,” Science, vol. 4598, pp. 671–680, 1983.

[12] V. Černý, “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm,” Journal of Optimization Theory and Applications, vol.45, pp. 41–51, 1985.

[13] N. Metropolis, A. R.osenbluth, M. Rosenbluth, A. Teller and E. Teller, “Equation of state calculations by fast computing machines,” Journal of Biochemical & Biophysical Methods, vol. 21, pp. 1087-1092, 1953.

[14] M Hasegawa, T Ikeguchi and K Aihara, “Combination of chaotic neurodynamics with the 2-opt algorithm to solve traveling salesman problems,” Physical Review Letters, vol.12, pp. 2344-2347, 1997.

[15] Wang Yin-nian and Ge Hong-wei, “Improved simulated annealing genetic algorithm for solving TSP problem,” Computer Engineering and Applications, vol. 465, pp. 44-47, 2010.