European Portal TSP
Find a short tour on 1000 European cities. You may add teleportation portals.
Find a minimum-length closed tour visiting each given city exactly once. You may add up to 20 portal pairs (ids ≥ 1000 with chosen coordinates). Traveling between the two nodes of the same pair costs zero, all other movements are Euclidean. The distance between the two points of a portal pair is at max 800. (TSP stands for Traveling Salesman Problem)
Instance: N=1000 cities. The header line is "N maxPairs maxPairDistance portalIdMin". Then N lines "id x y".
Solution format: Text with two sections. First line: "P m" (0 ≤ m ≤ 20). Next m lines: "idA idB xA yA xB yB" for each portal pair (ids ≥ 1000, unique, endpoints ≤ 800 apart). Then a line "T" and one line listing the tour node ids (all cities exactly once, portals are optional and may repeat).
Scoring: Total tour length using 0-cost edges inside each portal pair (smaller is better).
Solution example: Download example