Dr.PandaHello everyone!
In this post, I am going to show you how to solve Travelling Salesman Problem (TSP) using 2-Opt Algorithm. This 2-Opt Algorithm is coded in Python. If you want this 2-Opt Algorithm in Matlab, please let me know by leaving a comment below.
Did you know that TSP was first formulated in 1930 and it is one of the most intensively studied problems in optimization. Finding the global optimal solution for a general TSP is computationally difficult, especially for large-scale instances. The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified TSP can appear as a sub-problem in many areas, such as DNA sequencing (Wikipedia).
Here is a basic concept of the 2-Opt Algorithm.
Now, let’s apply the 2-Opt Algorithm to solve this case study problem. Suppose we want to visit 15 major cities in Europe as shown in this Map. Question here is how to find the shortest route or path that visits each city exactly once and returns to the origin city? Exact locations of all cities in terms of x and y coordinates are given here.
The Google map:
Please remember to put your Google map in a right place as shown here. Otherwise, the Google map cannot be visualized.
Finally, let’s have a quick look at my Python code of the 2-Opt algorithm. Let’s see how it works:
Python Code of the 2-Opt Algorithm
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import image as mpimg
image = mpimg.imread("map.png")
plt.imshow(image)
plt.show()
# location x y
city_list=np.array([[30, 172], # London
[127, 777], # Barcelona
[136, 339], # Paris
[216, 211], # Brussels
[241, 112], # Amsterdam
[416, 552], # Milan
[448, 34], # Hamburg
[513, 389], # Munich
[587, 104], # Berlin
[631, 262], # Prague
[690, 528], # Zagreb
[710, 382], # Vienna
[820, 422], # Budapest
[545, 743], # Rome
[901, 126]]) # Warsaw
solution = np.arange(city_list.shape[0])
city_locations = np.concatenate((np.array([city_list[solution[i]] for i in range(len(solution))]),np.array([city_list[0]])))
plt.scatter(city_list[:,0],city_list[:,1])
plt.plot(city_locations[:,0],city_locations[:,1])
plt.title("Initial solution")
plt.show()
distance_calculation = lambda r,c: np.sum([np.linalg.norm(c[r[p]]-c[r[p-1]]) for p in range(len(r))])
swap_algorithm = lambda r,i,k: np.concatenate((r[0:i],r[k:-len(r)+i-1:-1],r[k+1:len(r)]))
current_best_distance = distance_calculation(solution,city_list)
z = 0
for repeat in range(3):
for swap1 in range(1,len(solution)-2):
for swap2 in range(swap1+1,len(solution)):
new_solution = swap_algorithm(solution,swap1,swap2)
.
.
.
Sorry! This is only a half of the Python code.
Notice: It would take you from 1 to 3 hours to re-type the Python code yourself; or with just €2.99 (the cost of a cup of coffee), you can download/copy the whole Python code within 2 minutes. It’s your choice to make.
Original price is €5.99 but today it’s only €2.99 (save €3 today – available for a limited time only)
Download the whole Python code here (Membership Code ID: 036)
No need to build the Python code from scratch because it’s very time-consuming. My idol, Jim Rohn, once said: “Time is more value than money. You can get more money, but you cannot get more time”. If you think this code can be used in your research/teaching work, you should download it and then customize/modify/apply it to your work, without any obligation of citing the original source if you don’t want. However, redistribution (i.e., downloading the code/script here and then making it available on another site on the Internet) is strictly prohibited.
If you have any question or problem, please contact Dr. Panda by email: learnwithpanda2018@gmail.com
Thank you very much and good luck with your research and publications!