|
Travelling Salesman
Problem
Solves the TSP (Travelling Salesman Problem) via enumeration.
|
|
|
| nod |
> |
Number of nodes ("cities"),
|nod| ≤ … (run example). · |
| For the symmetrical problem, supply:
the first line, with a dummy value [say,
cost(1, 1) = ∞]; and the
lower triangle matrix. (For infinity, enter -1.) |
Cost
(distance) matrix |
|
Solves the TSP via enumeration. This exhaustive
approach is very time-ineffective, and is presented only to supply
a secure solution to a TSP. [The other TSP problem in this site
may be solved here by simply changing nod to the value therein.]
The method consists of examining every TSP tour permutation,
calculating its cost (or total distance), and showing a new permutation
whenever the cost is a new minimum. The last cost shown will be
the minimum cost.
Results (with n for nod) will be:
node permutation no. "§ i)", node vector,
(next line) current least distance, "Dist.",
with ordered distances shown. |
| References and
further reading: |
|
• Wagner, H. M., 1972,
"Introduction to Operations Research, with applications
to managerial decisions", John Wiley, New York, NY (USA). |
