Mesurer une distance réelle et l'explosion combinatoire

La distance du grand cercle

La projection en kilomètres de la leçon 2 était une approximation locale, suffisante pour clusteriser. Pour mesurer précisément la distance entre deux points GPS, la formule de référence est la distance de haversine, qui tient compte de la courbure terrestre :

import math

def haversine_km(lat1, lon1, lat2, lon2):
    R = 6371.0  # rayon terrestre moyen, en km
    phi1, phi2 = math.radians(lat1), math.radians(lat2)
    dphi = math.radians(lat2 - lat1)
    dlambda = math.radians(lon2 - lon1)
    a = math.sin(dphi / 2) ** 2 + math.cos(phi1) * math.cos(phi2) * math.sin(dlambda / 2) ** 2
    return R * 2 * math.asin(math.sqrt(a))

Une matrice de distances précalculée

Le trajet optimal d’une zone demandera de comparer de nombreux ordres de passage possibles ; recalculer la distance entre deux points à chaque comparaison serait redondant. On précalcule donc une fois pour toutes une matrice carrée des distances entre tous les points d’une même zone :

def build_distance_matrix(sous_points):
    n = len(sous_points)
    D = np.zeros((n, n))
    coords = sous_points[["latitude", "longitude"]].values
    for i in range(n):
        for j in range(i + 1, n):
            d = haversine_km(coords[i, 0], coords[i, 1], coords[j, 0], coords[j, 1])
            D[i, j] = D[j, i] = d
    return D

Pourquoi ne pas simplement essayer tous les ordres possibles ?

Trouver l’ordre de passage le plus court parmi n points est le problème du voyageur de commerce (TSP). Le nombre d’ordres possibles croît selon (n-1)! — une croissance factorielle, pas polynomiale. Pour la zone 2 (40 points), le nombre d’ordres possibles dépasse 10⁴⁶ : même en évaluant un milliard d’ordres par seconde, la force brute prendrait bien plus longtemps que l’âge de l’univers. Il faut une heuristique : une méthode qui trouve une bonne solution, sans garantir l’optimale, en un temps raisonnable.

Une nuance : chemin ouvert, pas cycle fermé

Le TSP classique cherche un cycle (retour au point de départ). Ici, un camion part d’un point, collecte, et s’arrête au dernier point — sans retour. C’est un chemin ouvert, une variante légèrement différente : la distance totale se limite aux n-1 liaisons du chemin, sans ajouter la liaison retour vers le point de départ.

def path_distance(path, D):
    return sum(D[path[i], path[i + 1]] for i in range(len(path) - 1))

Prochaine étape

👉 Heuristique gloutonne et recherche locale 2-opt

---

Junior TSAFACK – 12/09/2026