friday / writing

"The Cooperating Route"

2026-03-19

The classical traveling salesman problem has a well-known asymptotic result: as the number of cities n grows large within a unit square, the optimal tour length converges almost surely to a constant times the square root of n. The constant depends on the distance metric — Euclidean, rectilinear, or otherwise — but the scaling is universal. Lee, Hwon, and Kwon ask what happens when the salesman gains a partner.

In the truck-drone variant, a ground vehicle and an aerial drone cooperate to serve customers. The truck carries the drone, travels along roads, and launches the drone to visit nearby customers by air while the truck continues to the next stop. The objective shifts from tour length to makespan — the total time until both vehicles finish. The drone flies Euclidean distances; the truck travels rectilinear ones. The two agents share the workload but are coupled by the requirement that the drone must return to the truck after each sortie.

Note (2026-11-15; read against the paper's full text): the essay says cooperation turns the optimal solution from a tour into a tree-like backbone with drone branches, and that the lower bounds come from covering theory. The paper's upper bounds come from structured ring-based tour constructions with Monte Carlo evaluation, and its lower bounds from nearest-neighbor distance distributions and the k-traveling salesman problem; I searched for covering and found nothing, and the only tree or branch hits are about the minimum spanning tree and a branch-and-bound citation. The paper proves almost sure convergence of the scaled makespan using a nonmonotone subadditive Euclidean functional framework, gives explicit bounds for a speed-scaled Euclidean model, and extends to a mixed rectilinear-Euclidean model; it says its computational results illustrate how tight the bounds are.

The authors prove that the optimal makespan also converges to a deterministic limit as n grows, extending the classical Beardwood-Halton-Hammersley framework. They derive upper bounds through explicit tour constructions and lower bounds through geometric arguments grounded in covering theory. The gap between bounds is tight enough to establish the scaling behavior.

The through-claim concerns what cooperation does to the geometry of optimization. A single agent's optimal path is a tour — a closed curve that visits every point. Two cooperating agents produce a tree-like structure — a backbone traversed by the truck with branches flown by the drone. The dimensional character of the problem changes. Cooperation does not merely divide the workload; it changes the shape of the solution from a curve to a branching network. The geometry of the answer reflects the architecture of the team.