The TSP family

Read first

• Post 1: What is the TSP? A tour visits every stop once and returns. Its cost is the sum of its legs. In an asymmetric instance, d(i, j) and d(j, i) can differ, so direction matters.
• Post 2: Why is the TSP hard? Brute force prices all (n − 1)!/2 tours. On our eight stops that is 2,520 tours, and the optimum is A-B-C-D-H-E-F-G-A at 315. The TSP is NP-hard, so in practice we choose between proven optimal and good enough.

The question this post answers: what happens to the problem, and to its best answer, when we add the rules real routes carry?

Intuition

The textbook TSP has one salesman, no clock, and no choice about which stops to visit. None of my production routes look like that. Each extra rule turns the TSP into a named relative. I will add them one at a time to the same eight stops and solve each version exactly. With so few stops I can still enumerate every option, so every number below is a true optimum, not a heuristic result.

Here are the stops and distances again. A is the depot, coordinates are in kilometres, and the matrix is in units of 100 m, rounded.

1. A one-way street (asymmetric TSP). Make the trip from H back to D a 50-unit detour, while D→H stays 28. A tour and its reverse are now different tours, so there are 7! = 5,040 of them instead of 2,520. The optimum is still A-B-C-D-H-E-F-G-A at 315, because it drives D→H. Its mirror image costs 337. The diagram below shows the one pair of stops whose two directions now differ.

flowchart LR
  D -->|28| H
  H -->|"50, detour"| D

2. Time windows (TSPTW). Let one matrix unit take one minute of driving, leave A at minute 0, and require B to be reached by minute 60 and F by minute 140. If you arrive before a window opens you wait; arriving after it closes is not allowed. Enumerating all 5,040 directed orders, I find that only 144 are feasible. The old optimum fails: it reaches F at minute 237. Its reverse fails too, because it reaches B at minute 274. The new optimum is A-B-G-F-E-H-D-C-A at 359, which reaches B at 41 and F at 128. Two windows cost 44 units, 14% more distance.

Notice that the windows made a symmetric instance behave like an asymmetric one. The distances did not change, but the direction of travel decides when you reach each stop.

3. Optional stops with penalties (prize-collecting). Now every stop is optional, but skipping one costs its prize. B to G are worth 100 each and H is worth 30. The objective is distance plus the prizes of skipped stops. Visiting H costs 42 extra (D→H→E is 28 + 50, against D→E at 36), and H is only worth 30. So the best answer skips H: A-B-C-D-E-F-G-A covers 273, plus the 30 penalty, total 303. That beats visiting everything for 315.

4. A distance budget (orienteering). Same idea turned around: maximize the prize collected, subject to a route of length at most 200. Give the stops these prizes: B 10, C 20, D 30, E 20, F 10, G 10, H 40. The best route is A-B-C-D-G-A. It collects 70 and covers 199. H has the biggest prize, but it is too far away to fit together with the stops near A.

5. Two salesmen (multiple TSP). Two salesmen leave A, each must visit at least one stop, and together they cover every stop once. If the goal is total distance, the best split is A-B-C-D-H-E-F-A (298) plus A-G-A (72), total 370. That is worse than one salesman’s 315: when distances obey the triangle inequality, a second route never makes the total shorter. The goal that makes a second salesman useful is the longest route, which is what you minimize when a shift has to end on time. Minimizing the longer route gives A-B-C-F-A (232) and A-D-H-E-G-A (233). The longest route drops from 315 to 233; the total rises to 465.

The table below sums up the five variants on the same eight stops.

Step through the diagram below to see five of these optimal answers on the same eight stops. Marked (filled) stops are the ones a route skips. As in earlier posts, the lengths shown are unrounded kilometres, so they can differ by a few tenths from the matrix values in the table.

The formal idea

All five variants keep the TSP’s ingredients: stops 1 to n, stop 1 as the depot, and costs d(i, j) ≥ 0. Each changes one part of the definition.

Asymmetric TSP. Drop the condition d(i, j) = d(j, i). A tour is still a cyclic permutation π, and its cost is still c(π) = d(π₁, π₂) + … + d(πₙ, π₁), but there are (n − 1)! distinct tours, because the reverse of a tour is a different tour. A symmetric instance is just an asymmetric one whose matrix happens to equal its transpose, so any ATSP method also solves the symmetric TSP.

Multiple TSP. Use m salesmen, all starting and ending at the depot. A solution is m routes R₁, …, Rₘ that start and end at the depot, with every other stop on exactly one route. Usually each route must visit at least one stop. Two common objectives are total cost, Σₖ c(Rₖ), and longest route, maxₖ c(Rₖ). Add a capacity to each salesman and a demand to each stop, and the multiple TSP becomes the capacitated vehicle routing problem. That is why I call it the bridge to the VRP.

TSP with time windows. Give each stop i a window [eᵢ, lᵢ], where eᵢ is the earliest start and lᵢ is the latest, and give each pair a travel time t(i, j). Let aᵢ be the time the route reaches stop i and sᵢ the time service starts there. Service starts at sᵢ = max(aᵢ, eᵢ), so arriving early means waiting. A route is feasible only if sᵢ ≤ lᵢ at every stop. Savelsbergh (1985) proved that deciding whether any feasible TSPTW tour exists is strongly NP-complete, even when travel times obey the triangle inequality. Finding a good tour is NP-hard, and on a tight instance so is finding any tour at all.

Prize-collecting TSP. Give each stop a prize pᵢ ≥ 0. A solution visits a subset S of the stops that includes the depot. Balas (1989) defined the prize-collecting TSP with a penalty for every unvisited stop and a minimum total prize to collect. The version I solved above has penalties but no minimum: minimize c(tour over S) + Σ of pᵢ over stops not in S. Feillet, Dejax and Gendreau (2005) survey this family, which they call TSPs with profits. In their classification, the version with no minimum is the profitable tour problem: maximize the prize collected minus the route cost. Subtract that from the total of all prizes and you get my objective, so the two have the same optimal tours.

Orienteering. The name comes from the sport. Tsiligirides (1984) applied heuristics to it under that name, and Golden, Levy and Vohra (1987) defined the orienteering problem this way: given a start, an end and a time limit T_max, choose a subset of stops and an order that maximizes total prize, subject to route length ≤ T_max. In my example the start and the end are both A. Orienteering is at least as hard as the TSP: set every prize to 1 and ask whether all n stops can be collected within T_max, and you are asking the TSP decision question from Post 2.

The diagram below shows how the variants relate: each arrow adds one ingredient, and the bottom row is where the rest of this series goes.

flowchart TD
  TSP["TSP: one salesman, visit all"] --> ATSP["ATSP: d(i,j) ≠ d(j,i)"]
  TSP --> MTSP["mTSP: m salesmen"]
  TSP --> TSPTW["TSPTW: time windows"]
  TSP --> OPT["Stops become optional"]
  OPT --> PC["Prize-collecting: pay for skips"]
  OPT --> OP["Orienteering: length budget"]
  MTSP --> CVRP["CVRP: add capacities"]
  CVRP --> VRPTW["VRPTW: add time windows"]
  TSPTW --> VRPTW
  OP --> TOP["Team orienteering: several vehicles"]

Common misconceptions

“Adding salesmen always shortens the total distance.” With triangle-inequality distances, splitting one tour into two never lowers the total. On our stops two salesmen cost at least 370 against 315 for one. A second vehicle helps when the limit is per route, such as the length of a shift, or when capacity forces it.

“Time windows are a small add-on to the TSP.” They change what a feasible answer is. On our stops, two windows cut the feasible orders from 5,040 to 144 and made the old optimum illegal in both directions. Finding a feasible TSPTW tour is itself NP-complete.

“Prize-collecting and orienteering are the same problem.” They trade off the same two things in opposite ways. Prize-collecting pays for distance and pays a penalty for every skipped stop, with no hard limit. Orienteering ignores distance cost and caps route length. The answers differ: in my examples the prize-collecting route covers 273 units and the orienteering route stops at 199 units.

“A symmetric matrix means direction doesn’t matter.” Not once the clock matters. The time-window answer, A-B-G-F-E-H-D-C-A, is feasible only in that direction: driven in reverse it reaches B at minute 318.

Try it in Python

Every number in this post came from enumeration, and the whole thing fits in one short script. The search underneath is the same brute force as Post 2.

import math
from itertools import combinations, permutations

STOPS = {"A": (2, 2), "B": (6, 1), "C": (9, 3), "D": (8, 7),
         "E": (5, 9), "F": (1, 8), "G": (4, 5), "H": (10, 9)}  # km; A is the depot
OTHERS = "BCDEFGH"


def d(a, b):
    """Straight-line distance in units of 100 m, rounded."""
    (x1, y1), (x2, y2) = STOPS[a], STOPS[b]
    return int(10 * math.hypot(x1 - x2, y1 - y2) + 0.5)


def cost(order):
    """Length of the route A -> order -> A."""
    route = ["A", *order, "A"]
    return sum(d(a, b) for a, b in zip(route, route[1:]))


def arrival_times(order):
    """Minute of arrival at each stop, driving one distance unit per minute."""
    times, now, here = {}, 0, "A"
    for stop in order:
        now += d(here, stop)
        times[stop], here = now, stop
    return times


def label(order):
    return "A-" + "-".join(order) + "-A"


# Solve the plain TSP once for every subset of stops: cheapest route through exactly that subset.
best = {}
for size in range(len(OTHERS) + 1):
    for subset in combinations(OTHERS, size):
        best[subset] = min((cost(order), order) for order in permutations(subset))

# 1. Plain TSP
length, order = best[tuple(OTHERS)]
print(f"TSP:                distance {length}, {label(order)}")

# 2. Time windows: B by minute 60, F by minute 140. Direction matters, so check all 7! orders.
latest = {"B": 60, "F": 140}
feasible = [order for order in permutations(OTHERS)
            if all(arrival_times(order)[stop] <= t for stop, t in latest.items())]
length, order = min((cost(order), order) for order in feasible)
print(f"TSP + time windows: distance {length}, {label(order)} ({len(feasible)} feasible orders)")

# 3. Prize-collecting: route length plus the prize of every skipped stop
prize = {"B": 100, "C": 100, "D": 100, "E": 100, "F": 100, "G": 100, "H": 30}
def penalty(subset):
    return sum(prize[s] for s in OTHERS if s not in subset)
subset = min(best, key=lambda s: best[s][0] + penalty(s))
print(f"Prize-collecting:   objective {best[subset][0] + penalty(subset)}, {label(best[subset][1])}")

# 4. Orienteering: most prize collected with a route of length at most 200
value = {"B": 10, "C": 20, "D": 30, "E": 20, "F": 10, "G": 10, "H": 40}
within_budget = [s for s in best if best[s][0] <= 200]
subset = max(within_budget, key=lambda s: sum(value[x] for x in s))
print(f"Orienteering:       prize {sum(value[x] for x in subset)}, length {best[subset][0]}, "
      f"{label(best[subset][1])}")

# 5. Two salesmen, each with at least one stop: make the longer route as short as possible.
#    Each split is listed once: the first salesman always takes stop B.
splits = []
for subset in best:
    rest = tuple(s for s in OTHERS if s not in subset)
    if "B" in subset and rest:
        splits.append((subset, rest))
first, second = min(splits, key=lambda split: max(best[split[0]][0], best[split[1]][0]))
(len1, order1), (len2, order2) = best[first], best[second]
print(f"Two salesmen:       longest {max(len1, len2)}, "
      f"{label(order1)} ({len1}) and {label(order2)} ({len2})")

It prints:

Notice that the expensive part, finding the best route through each subset of stops, runs once and is stored in best. Each variant then only changes what counts as a valid answer and what gets scored. Time windows filter orders (feasible). Prizes change the score (penalty). The length budget filters subsets (within_budget). Two salesmen change the shape of an answer from one route to a pair (splits). Real routing engines are organised the same way, with search in place of enumeration.

Exercise

Change F’s window from “by 140” to “by 110” and drop B’s window. Without a computer, decide whether the original optimum, A-B-C-D-H-E-F-G-A, or its reverse is feasible. Then decide whether the optimal cost changes.

Hint: in reverse, the tour visits G first and then F. Add up the minutes from A.

What this method can’t do yet

Every optimum in this post came from enumeration: 2,520 or 5,040 orders for the full tours, and every subset of stops for the prize versions. That works for eight stops. Put berlin52’s 52 cities into the time-window version and there are 51! ≈ 1.55 × 10⁶⁶ directed orders to check. Heuristics will return good answers, but they cannot tell you whether those answers are optimal. Can we still solve these exactly, without listing every tour? Post 4, “Dynamic programming: Held-Karp”, starts the answer with a method that is exponential, but far less so than brute force.

References

• Balas, E. (1989). “The Prize Collecting Traveling Salesman Problem.” Networks 19(6): 621–636.
• Bektaş, T. (2006). “The Multiple Traveling Salesman Problem: An Overview of Formulations and Solution Procedures.” Omega 34(3): 209–219.
• Feillet, D., Dejax, P., and Gendreau, M. (2005). “Traveling Salesman Problems with Profits.” Transportation Science 39(2): 188–205.
• Golden, B. L., Levy, L., and Vohra, R. (1987). “The Orienteering Problem.” Naval Research Logistics 34(3): 307–318.
• Savelsbergh, M. W. P. (1985). “Local Search in Routing Problems with Time Windows.” Annals of Operations Research 4: 285–305.
• Tsiligirides, T. (1984). “Heuristic Methods Applied to Orienteering.” Journal of the Operational Research Society 35(9): 797–809.

See the whole series · ← All writing