A permutation arranges sequence elements so each occurs exactly once. In route optimization, a permutation of graph vertices represents a candidate tour: visit every vertex once, then return to the starting vertex. section 17.2.2 section 17.2.4
When permutations encode a traveling-salesperson solution, preserve these constraints and implementation choices:
- Use every vertex exactly once; represent each gene as a vertex index, with no repeated value. section 18.2.1
- Evaluate adjacent edges and include the wraparound edge from the final vertex to the first. section 17.2.4
- Fix a required starting vertex to remove equivalent cyclic shifts; six vertices therefore shrink from 720 arrangements to 120. section 17.2.3
- Choose transitions according to the search behavior needed: adjacent swaps make local changes, arbitrary swaps explore farther, and random permutation makes large jumps. section 17.2.4
A six-vertex tour
For six cities, [New Carthage, Happy Harbor, Gotham City, Metropolis, Opal City, Civic City] is one permutation. Rotating the same sequence produces an equivalent closed tour, while reversing it can produce another equivalent solution in an undirected graph. section 17.2.2 section 17.2.3
Listing 17.2 Cost function for TSP
function tspTourCost(graph, P) #1
cost ← 0
for k in {0..|P|} do #2
cost ← cost + graph.edgeBetween(P[k], P[(k+1)%|P|]).weight #3
return cost
Inspect the cost-function pseudocode to see how a permutation becomes a closed tour by summing edge weights with modular wraparound. section 17.2.4
