Python Code of the 2-Opt Algorithm for Solving the Traveling Salesman Problems

Hello everyone and welcome. In this post, I’m going to show you a Python code of the 2-Opt Algorithm for solving the traveling salesman problems (TSP). The 2-Opt Algorithm is quite simple but very effective for solving TSP. It is very simple to modify this Python code to solve new TSP instances.

The 2-opt algorithm is a simple local search algorithm for solving the traveling salesman problem. The 2-opt algorithm was first proposed by Croes in 1958, although the basic move had already been suggested by Flood. The main idea behind it is to take a route that crosses over itself and reorder it. A complete 2-opt local search will compare every possible valid combination of the swapping mechanism. This technique can be applied to the travelling salesman problem as well as many related problems. These include the vehicle routing problem (VRP) as well as the capacitated VRP, which require minor modification of the algorithm.

Here are the details of the case study problem. In this video, we use a TSP instance with 20 cities located at the following co-ordinates. To solve new TSP instances, we just need to update these co-ordinates. The rest of the Python code can be kept the same.

Let’s see how the 2-opt algorithm solves the traveling salesman problem with 20 cities.

For more videos like this, check my YouTube channel here.

import numpy as np
import matplotlib.pyplot as plt

#         location    x           y
city_list=np.array([[0.9511,    0.3090],
                   [0.3090,   -0.9511],
                   [-0.8090,    0.5878],
                   [0.0000,    1.0000],
                   [0.5878,   -0.8090],
                   [-0.5878,   -0.8090],
                   [0.5878,    0.8090],
                   [0.9511,   -0.3090],
                   [-0.3090,   -0.9511],
                   [-0.9511,    0.3090],
                   [0.8090,    0.5878],
                   [-0.5878,    0.8090],
                   [-0.3090,    0.9511],
                   [0.3090,    0.9511],
                   [-0.9511,   -0.3090],
                   [-1.0000,    0.0000],
                   [-0.0000,   -1.0000],
                   [0.8090,   -0.5878],
                   [-0.8090,   -0.5878],
                   [1.0000,   -0.0000]]) 
                 
 
solution = np.arange(city_list.shape[0]) 
city_locations = np.concatenate((np.array([city_list[solution[i]] ...


plt.scatter(city_list[:,0],city_list[:,1])
plt.plot(city_locations[:,0],city_locations[:,1])
plt.title("Initial solution") 
plt.show()


...
current_best_distance = distance_calculation(solution,city_list) 

...

plt.figure()
city_locations = np.concatenate((np.array([city_list[solution[i]] ...
plt.scatter(city_list[:,0],city_list[:,1])
plt.plot(city_locations[:,0],city_locations[:,1])
plt.title("Final solution") 
plt.show()
    
print('final solution', solution)    
print('best distance: ', distance_calculation(solution,city_list)) 
.
.
.
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 €4.99 but today it’s only €2.99 (save €2 today – available for a limited time only)

Download the whole Python code here (Membership Code ID: 022)

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!