Paris Metro Lines – Optimization challenges

Each of the 2 metro lines uses 10–20 distinct existing stations, and each consecutive pair of stations must have an allowed tunnel. A station may appear on both lines. Both lines share a fixed 40 km construction budget. They are added to the original Metro graph, and the score is the total weighted travel time saved, using demand data between pairs of stations. Transfers at stations are free.

A Paris Metro train pulling into a station at night.

Show mathematical formulationHide mathematical formulation

Let \(G_0=(V,E_0)\) be the existing undirected Metro graph, with travel time \(\tau_e\) on every existing edge. Let \(C\) be the undirected candidate-tunnel set. Each \(e\in C\) has construction length \(\ell_e\) and travel time \(\tau_e\). A solution consists of two ordered open paths \(S_j=(v_{j,0},\ldots,v_{j,k_j-1})\), for \(j\in\{1,2\}\). Stations are distinct within each path, but the two paths may share stations. \(10\le k_j\le20\) \(\{v_{j,i},v_{j,i+1}\}\in C\) for every \(j\) and \(0\le i<k_j-1\) \(\sum_{j=1}^{2}\sum_{i=0}^{k_j-2}\ell_{\{v_{j,i},v_{j,i+1}\}}\le40\text{ km}\) Let \(E(S_1,S_2)\) be the union of both path-edge sets and \(G_S=(V,E_0\cup E(S_1,S_2))\). Transfers are free because existing and new edges share the same station vertices. For each scored station pair \((a,b)\in D\), let \(t_0(a,b)\) and \(t_S(a,b)\) be shortest-path travel times in \(G_0\) and \(G_S\). Maximize \(\sum_{(a,b)\in D} d_{ab}(t_0(a,b)-t_S(a,b))\).

Instance: 302 Metro stations, 358 existing edges, 11092 allowed tunnels and 13031 scored origin-destination pairs. The compact text file contains planar kilometre coordinates and all data required to solve the problem. The full JSON additionally contains display names, geographic coordinates, line memberships and map geometry. This JSON data is not necessary for solving the problem.

Show data formatHide data format

RULES lineCount minStationsPerLine maxStationsPerLine constructionBudgetKm

STATIONS count
  index identifier xKm yKm

EXISTING_EDGES count
  indexA indexB travelMinutes

CANDIDATE_TUNNELS count
  indexA indexB constructionKm travelMinutes

DEMAND_PAIRS count
  indexA indexB demandWeight

Indices are zero-based. Edges are undirected.
(indexA, indexB) and (indexB, indexA) are the same demand pair.
Each pair adds demandWeight × travel-time saving to the score.
Lines beginning with # are comments.
Solutions use station identifiers, not indices.

Download data (txt) Download full details (JSON) Download local scorer Data notes Candidate tunnels visualizer

Solution format: 2 text lines. Each text line contains 10–20 station identifiers separated by spaces, in travel order.

Scoring: \(\text{Score}=\sum_{(a,b)} d(a,b)(t_{old}(a,b)-t_{new}(a,b))\) Higher is better. It means that for every station pair, we multiply its demand by the reduction in shortest-path travel time.

Solution example: Download example