Optimization challenges

Visualize and submit solutions to optimization problems, and compete on the leaderboards.

France Roadshow

Plan a route from Paris and reach as much of the French population as possible.

Start in Paris and visit any sequence of distinct eligible cities. The route may finish anywhere, but its total length must not exceed 2100 km. An event reaches every population point within 35 km of a visited city. Each population point is counted at most once, even when several events reach it.

A winding coastal road near Cassis, France.
Show mathematical formulationHide mathematical formulation
Let \(C\) be the set of eligible cities, \(s\in C\) Paris, and \(P\) the set of population points. Each \(p\in P\) has weight \(w_p\ge0\). A solution is an ordered sequence of distinct cities \(S=(v_0,\ldots,v_{k-1})\), with \(v_0=s\). It is an open route: there is no edge from the final city back to Paris. \(\sum_{i=1}^{k-1}\|v_i-v_{i-1}\|\le 2100\text{ km}\) A population point is reached when \(\min_{v\in S}\|p-v\|\le 35\text{ km}\). Maximize \(\sum_{p\in P}w_p\,\mathbf{1}[p\text{ is reached}]\). A point covered by several cities is counted once.

Instance: 1200 eligible cities and 21722 weighted population points in continental metropolitan France. Coordinates and distances use the fixed planar kilometre system in the instance.

Show data formatHide data format 
RULES maxRouteLengthKm coverageRadiusKm startCityIdentifier

CITIES count
  index identifier xKm yKm

POPULATION_POINTS count
  index xKm yKm population

Indices are zero-based.
Distances are Euclidean in kilometres.
Lines beginning with # are comments.
Download data (txt) Download full details (JSON) Download local scorer Data notes

Solution format: One distinct city identifier per line, in travel order. The first identifier must be Paris_75056.

Scoring: \(\text{Score}(S)=\sum_{p\in P} w_p\,\mathbf{1}\!\left[\min_{v\in S}\|p-v\|\le R\right]\) Higher is better. The score is the total population of points within the coverage radius of at least one visited city.

Solution example: Download example