The Problem That Stole Its Name From a Sport

Today’s course was point-to-point: find the controls in order or you’re disqualified. But there’s a second flavour of the sport, Score-O, where the controls are scattered with different point values and you have a fixed time budget — say 60 minutes — to bag as many points as you can, in whatever order you like, then sprint back before the clock buzzes. Overshoot the limit and you start bleeding penalty points.

That exact setup has a name in the operations-research literature: the Orienteering Problem. Tsiligirides wrote it up in 1984, borrowing the sport wholesale, and the mathematicians never gave it back. It’s a nasty little thing — a prize-collecting cousin of the travelling salesman, NP-hard, no tidy exact answer once you have more than a handful of controls.

So you cheat, the way a runner cheats when there’s no time to think: at every control, look at what’s reachable and go to whichever gives the most points per metre of detour. Pure greed.

controls <- data.frame(
  x   = c(0, 2, 5, 3, 7), y = c(0, 4, 1, 6, 5),
  pts = c(0, 30, 20, 40, 50))
budget <- 20; here <- 1; visited <- 1; score <- 0
repeat {
  d <- sqrt((controls$x - controls$x[here])^2 + (controls$y - controls$y[here])^2)
  ratio <- ifelse(seq_along(d) %in% visited | d > budget, -Inf, controls$pts / d)
  nxt <- which.max(ratio)
  if (ratio[nxt] == -Inf) break
  budget <- budget - d[nxt]; here <- nxt
  visited <- c(visited, nxt); score <- score + controls$pts[nxt]
}
cat("Score:", score, " Route:", visited, "\n")

Score: 140  Route: 1 2 4 5 3

With my toy map it happens to sweep every control, but the ratio test is what keeps it honest — a fat 50-pointer eight kilometres away loses to a modest 30-pointer next door. Here it is again in the language the ’80s would have actually reached for:

program ScoreO;
const
  x:   array[1..5] of real = (0, 2, 5, 3, 7);
  y:   array[1..5] of real = (0, 4, 1, 6, 5);
  pts: array[1..5] of real = (0, 30, 20, 40, 50);
var
  seen: array[1..5] of boolean;
  i, here, best: integer;
  budget, d, bestr, score: real;
begin
  for i := 1 to 5 do seen[i] := false;
  budget := 20; here := 1; seen[1] := true; score := 0;
  repeat
    best := 0; bestr := 0;
    for i := 1 to 5 do begin
      d := sqrt(sqr(x[i]-x[here]) + sqr(y[i]-y[here]));
      if (not seen[i]) and (d <= budget) and (pts[i]/d > bestr) then
        begin bestr := pts[i]/d; best := i end;
    end;
    if best = 0 then break;
    d := sqrt(sqr(x[best]-x[here]) + sqr(y[best]-y[here]));
    budget := budget - d; here := best; seen[best] := true;
    score := score + pts[best]; write(best, ' ');
  until false;
  writeln; writeln('Score: ', score:0:0);
end.

The greedy route is often a few percent off the true optimum, and it can strand you far from the finish with the budget spent — which is precisely the mistake I watched a faster runner make today, hoovering up close controls and then jogging home empty because the clock ran out mid-forest. The algorithm doesn’t plan the return leg. Neither did he. My own error was duller and more geometric, but that’s the other post.