clementbouni-arch/Tour-of-Cameroon-2027

Tour of Cameroon 2027 is a machine learning and optimization project that uses clustering and TSP heuristics to divide 100 Cameroonian localities into 10 stages and optimize the visiting route within each stage, reducing the total distance by approximately 61%. # 🚴 Tour of Cameroon 2027 — Clustering & Route Optimization **Splitting 100 Cameroonian localities into 10 coherent stages, then computing the shortest visiting order within each — using unsupervised Machine Learning and combinatorial optimization heuristics.** --- ## 🎯 The problem The Cameroon Cycling Federation is preparing the relaunch of the **Tour of Cameroon**, with a route crossing **100 representative localities** across the country's 10 regions. Two questions need to be answered: 1. **How should these 100 localities be grouped into 10 stages**, so that each stage covers geographically close towns? 2. **For each stage, what visiting order minimizes the distance traveled**, from the starting village to the finishing village? The first question is an **unsupervised clustering** problem: there's no "correct answer" provided, the algorithm has to discover coherent groups on its own. The second hides one of the most famous problems in computer science: the **traveling salesman problem** (TSP), for which no known algorithm guarantees the optimal solution in reasonable time once the number of cities grows. ## 🧠 The approach ### Step 1 — Clustering: splitting the country into stages - GPS coordinates (degrees) projected into a Cartesian plane in kilometers, so distances have a correct geometric meaning - Two algorithms tested and compared: **K-Means** and **Agglomerative Hierarchical Clustering (AHC)** - Automatic selection of the best candidate, combining: - a geometric metric (**silhouette score**) - a business rule (no single-locality stage) ### Step 2 — TSP: optimizing each stage - Vectorized (NumPy) computation of the distance matrix using the **haversine formula** (great-circle distance on a sphere — the same formula used inside a GPS) - A first route built with a **greedy** (nearest-neighbor) heuristic - Refinement via **2-opt** local search (removes route crossings) - Every possible starting point is tried for each stage, keeping the best resu …