Traveling Salesman Problem

Solve the classic problem with your own data. The problem can be described as follows: Given a list of cities and the distances (or some other notion of costs) between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? [1]

 

Mathematically, let a directed graph G = (V, E) be given, where V = {1, ..., n} is a set of nodes, E <= V x V is a set of arcs. Let also each arc e = (i,j) be assigned a cost c[i,j], which can be proportional to distance between node i to node j, or time required travel the arc (i,j). The problem is to find a closed path of minimal length going through each node of G exactly once.

Also known as simple vehicle routing problem, this model and its variations are used to solve many different problems.

Input required:
- Parameters (constants):
   - Number of cities (or nodes)
   - The distance matrix (or cost matrix) between cities

[1] Wikipedia: Traveling Salesman Problem. Retrieved on Oct 06, 2017.