A tour is a closed sequence of locations: start at one location, visit every required location, and return to the start. In route optimization, each move has a cost such as distance, travel time, or delivery expense; the objective is to minimize the total cost. section 17.2
A single shortest path solves only one delivery at a time. A delivery truck carrying several shipments instead needs one tour through its assigned destinations, beginning and ending at the warehouse. The problem assumes the load and destinations are already fixed; assigning deliveries across trucks is a separate optimization. section 17.2
When representing and comparing tours, make these constraints explicit:
- Visit each required city exactly once before returning to the starting city. section 17.2
- Fix the starting location when possible. Rotating a closed tour produces the same solution, so fixing one city removes equivalent permutations; six vertices reduce from 720 sequences to 120. section 17.2.3
- For an undirected graph, reversing a tour may preserve its cost, leaving at most two equivalent solutions after fixing the start. section 17.2.3
Equivalent closed tours
The sequences [Opal City, Civic City, New Carthage, Happy Harbor, Gotham City, Metropolis] and [New Carthage, Happy Harbor, Gotham City, Metropolis, Opal City, Civic City] describe the same closed tour when the starting point is allowed to shift. With New Carthage fixed as the start, reversing the order gives another equally costly solution in an undirected graph. section 17.2.3
Figure 17.8 An example map, mixing the DC Universe’s cities and other real ones, with some distances: because this is a complete graph with close to fifty edges, we are only showing a few numbers, almost only for the edges in the best tour (the thicker edges).
Use the map to inspect a complete graph of cities, edge costs, and a highlighted shortest tour. section 17.2
