2-opt, clustering, insertion : les heuristiques d'optimisation décodées

Pourquoi des heuristiques ?

Calculer la tournée parfaite est un problème NP-difficile : au-delà de quelques dizaines d'arrêts, aucun ordinateur ne peut tester toutes les combinaisons. On renonce donc à l'optimum garanti pour viser une excellente solution, obtenue vite. C'est exactement ce que font les heuristiques. Trois familles se complètent.

1. Le regroupement (clustering)

Avant d'ordonner quoi que ce soit, on découpe les adresses en grappes géographiques cohérentes. Un véhicule = une zone. Cette étape évite l'erreur la plus coûteuse : faire traverser la ville à un chauffeur pour un arrêt isolé. Le clustering ne calcule pas l'ordre, il définit le périmètre de chaque tournée.

2. L'amélioration locale : 2-opt

Une fois une tournée construite, on l'améliore. La méthode 2-opt, proposée par Croes en 1958, est la plus connue : elle retire deux segments de l'itinéraire et les reconnecte dans l'autre sens. Si la distance totale baisse, on garde ; sinon, on annule. Répétée des milliers de fois en une fraction de seconde, cette opération « défait les croisements » et tend vers une tournée fluide. C'est un classique précisément parce qu'il est simple et redoutablement efficace.

3. L'insertion la moins coûteuse

Comment ajouter un nouvel arrêt à une tournée déjà calculée — par exemple une commande urgente arrivée en cours de journée ? L'heuristique d'insertion teste chaque position possible et choisit celle qui ajoute le moins de kilomètres. C'est ce qui permet d'absorber les imprévus sans tout recalculer.

Comment elles travaillent ensemble

Un bon moteur enchaîne ces logiques : clustering pour répartir, construction initiale, puis 2-opt pour polir, et insertion pour les ajouts à chaud. Le tout sous contraintes réelles (capacité, fenêtres horaires, compétences). L'utilisateur, lui, ne voit qu'un bouton « optimiser » et un gain de kilomètres affiché avant/après.

Une optimisation prête à l'emploi, sans doctorat en maths. Essayez dropfleet gratuitement 14 jours — sans carte bancaire, prêt en 5 minutes.