
182 High Performance Programming for Soft Computing
8.3 Ant Colony Optimization for Hole Making NC Sequences:
A Special Case of the Traveling Salesman Problem (TSP)
The TSP problem (M. Dorigo 1997a,b) is the problem of a salesman who,
starting from his hometown, wants to fi nd a shortest tour that takes him
through a given set of customer cities and then back home, visiting each
customer city exactly once. The TSP can be represented by a completed
weighted graph G = (N, A) with N being the set of nodes representing the
cities, and A being the set of arcs. Each arc (i,j) ¢ A has an assigned value
(length) d
ij
which is the distance between cities ...