Travelling Salesman Problem Using Simulated Annealing
The Traveling Salesman Problem (TSP) was introduced by K.Menge in 1932 and has raised a lot of interest in many researching fields since then¹. TSP is a proven NP hard combinatorial problem that entails a salesman having n cities and needing to visit each city once and only once and return to the first city that began the route. TSP has had many real-world applications such as routing in network engineering, critical distribution for logistics companies worldwide, vehicle routing, supply chain management etc. Several optimization algorithms have been used to arrive at a global optimum, finding the shortest route that satisfies the mentioned constraints. These are genetic algorithms, ant colony optimization, simulated annealing, Dijkstra algorithms, neural networks, etc.
Simulated annealing is a computational method borrowing inspiration from the field of physics introduced by. It simulates the physical process of solid annealing. In this process, a material such as metal or glass is raised to a high temperature and then left to cool, allowing the local regions of order to grow outward, thereby reducing stress and increasing the ductile strength of the material. It is a method generally known to escape local optima. However, it was not until³ that it was presented as an independent metaheuristic method for solving discrete and continuous optimization problems.
TSP
The dataset used in this exercise is a symmetric TSP which means that the distance from city i to city j is the same distance from city j to city i for all cities in the route. The dataset can be found here, along with other TSP datasets.
Each node in the Traveling Salesman problem dataset represents a city. The TSP comes with the following constraints:
• The starting node must be the end node.
• Each node must be visited once and only once.
These nodes are connected to form routes. Each route represents a possible solution/candidate/individual. The fitness of these individuals is taken to be the inverse of the total distance travelled taking that route. The distance travelled between node i and node j is given by:
where i ≠ j. We take the fitness to be the inverse of the distance travelled in the entire route (Fij = 1/dij) because we want to maximize fitness when our algorithm selects a candidate.
An example of an individual representation of a route with 10 cities is “1–4–3–2–5–6–7–8–9–10”.
Simulated Annealing
This method has been commonly referred to as one of the oldest metaheuristic models². It has great performance in avoiding local minima. In order to do this, the algorithm accepts worse candidates with a probability dependent on the temperature (a control variable) and the fitness difference given by the formula below:
p — the probability of accepting the new solution candidate, y.
x — initial solution candidate (In this case, that is a route)
y — new solution candidate
f(x) — is the function that measures the performance of the solution candidate (Fitness function)
T — the temperature which is the control parameter.
The code below shows how to calculate the fitness using tsp95lib:
The Algorithm implemented can be summarized by the flow chart below:
Because our probability of accepting worse new candidates is dependent on the temperature, as the temperature cools, eventually we will only accept candidates that are better than the present one.
Generating Candidate Solutions
Because the simulated annealing algorithm compares different candidate solutions and decides which one is taken at each iteration, it is necessary to be able to generate these solutions. In this article, four methods were used, three of which were inspired from²:
- Inverse operator (x): This changes the order of routes between two randomly selected nodes i and j. Where i,j ≤ 0 ≤ n such that x¹[i] = x[j], x¹[i+1] = x[j-1], etc. Hopefully, an example makes it clearer. Let’s say the initial route is ‘1–2–3–4–5–6’, this operator could produce ‘1–4–3–2–5–6’. The random positions selected in this example are city 2 and city 5. The minimum integer between i and j will be ‘i’ and the maximum would be taken as ‘j’.
- Swap operator (x): This exchanges the position of two cities in a route. Two positions, i and j are selected at random and the cities in these positions are swapped with each other. ‘1–2–3–4–5–6’ could become ‘1–5–3–4–2–6’.
- Insert operator(x): · This operator selects a city at random position ‘i’ and moves it to a random position ‘j’ elsewhere in the route.
- Insert subroutes(x): This is similar to the swap route operator but rather than inserting a city in a different position, a range of cities are selected as a sub route and inserted at a random position.
Termination Condition
While several simulated annealing algorithms terminate once the temperature reaches 0. To have a very large search space, this algorithm only terminates once a candidate has been selected 1500 times and the same fitness score has occurred 150000 times. You can change these values to your liking. An initial temperature of 5000 was used. Usually, it is good practice to run the algorithm more than once to get a more general solution. I ran this 10 times and took an average of the results. I thought it was also pretty cool to visualize what the optimal route looked like on one of the datasets.
The complete code (Can also be gotten from my Github):
Conclusion
The drawback to simulated annealing is its high convergence time. This is why other optimization methods are preferred such as genetic algorithms, greedy permuting methods, ant colony optimization, hill-climbing etc. There have been several attempts to combine many of these methods which have been successful. Simulated annealing is a great tool in finding your global optima.
References
- G. Ye and X. Rui, ‘An improved simulated annealing and genetic algorithm for TSP’, in 2013 5th IEEE International Conference on Broadband Network & Multimedia Technology, Nov. 2013, pp. 6–9. DOI: 10.1109/ICBNMT.2013.6823904.
- S. Zhan, J. Lin, Z. Zhang, and Y. Zhong, ‘List-Based Simulated Annealing Algorithm for Traveling Salesman Problem’, Comput. Intell. Neurosci., vol. 2016, p. 1712630, Mar. 2016, DOI: 10.1155/2016/1712630.
- J. Liu and W. Li, ‘Greedy Permuting Method for Genetic Algorithm on Traveling Salesman Problem’, in 2018 8th International Conference on Electronics Information and Emergency Communication (ICEIEC), Jun. 2018, pp. 47–51. doi: 10.1109/ICEIEC.2018.8473531.
