Stratégie multi-démarrage et synthèse

Le point de départ influence le résultat

L’heuristique du plus proche voisin dépend de son point de départ : démarrer d’un point excentré ou d’un point central ne produit pas le même chemin. Plutôt que de deviner le meilleur départ, on les essaie tous :

def best_route_multi_start(D):
    n = D.shape[0]
    best_path, best_dist = None, math.inf
    for start in range(n):
        candidate = two_opt_refine(nearest_neighbor_route(start, D), D)
        dist = path_distance(candidate, D)
        if dist < best_dist:
            best_dist, best_path = dist, candidate
    return best_path, best_dist

Ce coût supplémentaire (n exécutions de glouton + 2-opt au lieu d’une seule) reste largement praticable pour des zones de quelques dizaines de points — bien loin de l’explosion factorielle de la force brute.

Le plan de collecte complet

for zone in sorted(points["zone"].unique()):
    sous_points = points[points["zone"] == zone].reset_index(drop=True)
    D = build_distance_matrix(sous_points)
    best_path, best_dist = best_route_multi_start(D)
    print(f"Zone {zone}: {len(sous_points)} points, distance optimisee={best_dist:.1f} km")

total_distance = sum(p["distance_km"] for p in plans.values())
print("Distance totale du plan de collecte:", total_distance)

Zone 1: 35 points, distance ordre brut=2194.1 km, distance optimisee=645.7 km (gain 70.6%)
Zone 2: 40 points, distance ordre brut=2673.7 km, distance optimisee=700.5 km (gain 73.8%)
Zone 3: 25 points, distance ordre brut=1855.3 km, distance optimisee=651.7 km (gain 64.9%)
Zone 4: 30 points, distance ordre brut=1701.2 km, distance optimisee=559.0 km (gain 67.1%)

Distance totale du plan de collecte: 2556.9 km

Un gain de 65 à 74 % selon la zone, pour un coût de calcul négligeable — le genre de résultat qui justifie, dans un contexte réel, de systématiser cette approche plutôt que de laisser chaque chauffeur improviser son parcours.

Bilan du module

1. Clustering non supervisé : K-Means (centroïdes) et CAH (fusions hiérarchiques), comparés via le score de silhouette et une contrainte métier — jamais une métrique seule.
2. Projection géographique : corriger la distorsion des degrés avant tout calcul de distance euclidienne.
3. Optimisation combinatoire : la force brute explose factoriellement ; une heuristique gloutonne, raffinée par recherche locale (2-opt) et multi-démarrage, approche une bonne solution en temps praticable.

Limites assumées

• Les distances sont à vol d’oiseau (haversine), pas des distances routières réelles — un vrai système de production s’appuierait sur une API de routage (OSRM, Google Maps Directions).
• Aucune contrainte de capacité de camion (volume maximal transportable) n’est modélisée ici.
• Pour aller plus loin : OR-Tools (Google) propose des solveurs de tournées bien plus riches (fenêtres de temps, capacités multiples, plusieurs dépôts).

Prochaine étape

👉 Module 6 : Deep Learning

---

Junior TSAFACK – 12/09/2026