Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is one of the most famous combinatorial optimization problems. The TSP goal is to find the shortest possible route that visits each city once and returns to the original city. It is classified as an NP-hard problem in the field of combinatorial optimization.

The origin of the traveling salesman problem is not very clear; it is mentioned in an 1832 manual for traveling salesman, which included example tours of 45 German cities but was not formulated as a mathematical problem. However, in the 1800s, mathematicians William Rowan Hamilton and Thomas Kirkman devised mathematical formulations of the problem.

It seems that the general form of the Traveling Salesman Problem was first studied by Karl Menger in Vienna and Harvard in the 1930s.

The problem became more and more popular in the 1950s and 1960s. In particular, George Dantzig, D. Ray Fulkerson, and Selmer M. Johnson at the RAND Corporation solved the 48-state problem by formulating it as a linear programming problem. The methods they described in their paper on this topic set the foundation for future work in combinatorial optimization, especially highlighting the importance of cutting planes.

In the early 1970s, the concept of P vs. NP problems created excitement in the theoretical computer science community. In 1972, Richard Karp demonstrated that the Hamiltonian cycle problem was NP-complete, implying that the traveling salesman problem was NP-hard.

Increasingly sophisticated codes led to rapid increases in the sizes of the traveling salesman problems solved. Dantzig, Fulkerson, and Johnson had solved a 48-city instance of the problem in 1954. Martin Grötechel more than doubled this 23 years later, solving a 120-city instance in 1977. Harlan Crowder and Manfred W. Padberg again more than doubled this in just 3 years, with a 318-city solution.

In 1987, rapid improvements were made, culminating in a 2,392-city solution by Padberg and Giovanni Rinaldi. In the following two decades, great strides were made with David L. Applegate, Robert E. Bixby, Vasek Chvátal, & William J. Cook solving a 3,308-city instance in 1992, a 7,397-city instance in 1994, a 24,978-city instance in 2004, and an 85,900-city instance in 2006 – which is the largest 2-D Euclidean TSP instance ever solved. William Cook et. al. wrote a program called Concorde TSP Solver for solving the TSP. Concorde is a computer code for the symmetric TSP and some related network optimization problems. The code is written in the ANSI C programming language and it has been used to obtain the optimal solutions to the full set of 110 TSPLIB instances, the largest instance is a 109,399 node 3-D “star” instance.

The continued interest in the TSP can be explained by its success as a general engine of discovery and a steady stream of new applications. Some of the general applications of the TSP are as follows:

  • Scheduling and routing problems
  • Genome sequencing
  • Drilling problems
  • Aiming telescopes and x-rays
  • Data clustering
  • Machine scheduling

This modeling example is at the advanced level, where we assume that you know Python and the Gurobi Python API and you have advanced knowledge of building mathematical optimization models. Typically, the objective function and/or constraints of these examples are complex or required advanced features of the Gurobi Python API.


 

Request a Gurobi Evaluation License or Free Academic License

Modeling examples are coded using the Gurobi Python API in Jupyter Notebook. In order to use the Jupyter Notebooks, you must have a Gurobi License. If you do not have a license, you can request an Evaluation License as a Commercial User or download a free license as an Academic User.

Commercial Users: Free Evaluation Version Academic Users: Free Academic Version

 


 

Access the Jupyter Notebook Modeling Example

Click on the button below to be directed to GitHub where you can download the repository for the Traveling Salesman Jupyter Notebook modeling example.

Traveling Salesman Problem