Notes From Industry

How to Solve the Traveling Salesman Problem — A Comparative Analysis

Through 3 optimization methods: dynamic programming, simulated annealing, and 2-opt.

Photo by Caleb Jones on Unsplash

I am sure you already heard about the traveling salesman problem or TSP. There are many applications for this problem and many solutions with different performances. Here, I want to share my recent experience in solving the traveling salesman problem, especially with the 2-opt method, one of the easiest yet most effective methods to solve this problem.

If you just want to read about the 2-opt, you can jump directly to the end of this article. You can also use the Python package that I developed below to solve a TSP.

py2opt

I want to share my experience solving a TSP with 120 cities to visit in this article. The problem had to be solved in less than 5 minutes to be used in practice. I aimed to solve this problem with the following methods:

• dynamic programming,
• simulated annealing, and
• 2-opt.

First, let me explain TSP briefly.

Artificial Intelligence: Unorthodox Lessons: How to Gain Insight and Build Innovative Solutions

Traveling Salesman Problem

The traveling salesman problem is a classic problem in combinatorial optimization. This problem is finding the shortest path a salesman should take to traverse a list of cities and return to the origin city. The list of cities and the distance between each pair are provided.

TSP is beneficial in various real-life applications such as planning or logistics. For example, a concert tour manager who…