# Paris fixed-endpoint route comparison

Computed 2026-09-29. Start: **Eiffel Tower**. Finish: **Sacré-Cœur**. Each of the eight requested intermediate stops appears exactly once in every route.

## Results

| Method | Great-circle distance (km) | Gap to exact shortest |
|---|---:|---:|
| Committed geography-based route | 13.374 | 10.359% |
| Nearest neighbor | 13.374 | 10.359% |
| 2-opt from committed route | 12.118 | 0.000% |
| Exact shortest route | 12.118 | 0.000% |

Gap = (method distance / exact distance − 1) × 100. Unrounded distances were 13.373781 km and 12.118469 km, respectively.

**Committed and nearest-neighbor order:** Eiffel Tower → Arc de Triomphe → Place de la Concorde → Palais Garnier → Louvre Museum → Sainte-Chapelle → Notre-Dame de Paris → Panthéon → Luxembourg Gardens → Sacré-Cœur.

**2-opt and exact order:** Eiffel Tower → Arc de Triomphe → Place de la Concorde → Luxembourg Gardens → Panthéon → Notre-Dame de Paris → Sainte-Chapelle → Louvre Museum → Palais Garnier → Sacré-Cœur.

## Method

Coordinates are representative WGS84 landmark points transcribed from the linked Wikidata coordinate-location statements below. The Eiffel Tower point is also referenced there to Cartes.gouv.fr. The garden and square points are representative points, and building points are not selected entrances. Converted DMS coordinates were used at full available precision for computation; six-decimal values below are for display. Each segment uses the haversine great-circle formula with mean Earth radius 6,371.0088 km. The fixed route was saved in [the committed route record](paris_committed_route.md) **before optimization**.

Nearest neighbor begins at Eiffel Tower, repeatedly picks the closest unvisited intermediate point, and appends Sacré-Cœur last; index order breaks ties. Best-improvement 2-opt starts with the committed route and reverses interior subsequences until no improvement remains. The exact result checks every 8! = 40,320 permutation of intermediate stops with fixed endpoints. The notebook also checked endpoint and one-visit constraints, that no benchmark was shorter than the exact result, and that no single 2-opt reversal improved the final 2-opt route.

## Verified landmark points

| Landmark | Latitude | Longitude | Source |
|---|---:|---:|---|
| Eiffel Tower | 48.858297 | 2.294478 | [Wikidata Q243](https://www.wikidata.org/wiki/Q243) |
| Arc de Triomphe | 48.873778 | 2.295028 | [Wikidata Q64436](https://www.wikidata.org/wiki/Q64436) |
| Place de la Concorde | 48.865633 | 2.321236 | [Wikidata Q189503](https://www.wikidata.org/wiki/Q189503) |
| Louvre Museum | 48.861111 | 2.335833 | [Wikidata Q19675](https://www.wikidata.org/wiki/Q19675) |
| Sainte-Chapelle | 48.855369 | 2.345028 | [Wikidata Q193193](https://www.wikidata.org/wiki/Q193193) |
| Notre-Dame de Paris | 48.853056 | 2.349722 | [Wikidata Q2981](https://www.wikidata.org/wiki/Q2981) |
| Panthéon | 48.846197 | 2.346106 | [Wikidata Q188856](https://www.wikidata.org/wiki/Q188856) |
| Luxembourg Gardens | 48.846944 | 2.337222 | [Wikidata Q309458](https://www.wikidata.org/wiki/Q309458) |
| Palais Garnier | 48.871944 | 2.331667 | [Wikidata Q187840](https://www.wikidata.org/wiki/Q187840) |
| Sacré-Cœur | 48.886639 | 2.342944 | [Wikidata Q28785](https://www.wikidata.org/wiki/Q28785) |

The [route map](paris_route_map.png) plots straight segments between these points. **This is not a live walking or traffic plan.** Street crossings, route availability, entrances, opening hours, queues, transport modes, and travel times are outside the model; actual travel distances and the best practical visiting order may differ.
