The Travelling Salesman Problem
Description
The problem can simply be stated as:
- given a finite number of cities
- along with the cost of travel between each pair of them,
- find the cheapest way of visiting all the cities and returning to your starting point.
Business and Industrial Applications
This problem has a lot of business and industrial applications such as, among others:
- vehicle routing,
- drilling of printed circuit boards,
- material handling in a warehouse,
- sequencing of jobs on a single machine,
- assignment of routes for planes of a specified fleet.
Data
Data (GR17 and GR21 instances) provided in the problem definition - Java file (8kb) [view] - is taken from TSPLIB.
Given two cities i and j, XX a TSP instance,
XX[i][j] represents the costs of the travel from i to j.
Modelling & Solving
We use a simple constraint model - Java file (8kb) [view] - defining,
for each city i,
the next (variable next[i]) and previous (variable prev[i]) cities to be visited by the travelling salesman.
The salesman's journey has to form a cycle, this can be easily
enforced by using the Cycle constraint both on next and prev.
To solve the problem, we use a cost-based solver: Java file (1kb) [view].
Results
The following results include the computation of an optimal solution and the proof of its optimality.
| Instance | Time (ms) | Backtracks |
|---|---|---|
| GR17 | 1699 | 2867 |
| GR21 | 655 | 833 |