Trouver le meilleur ordre de passage porte un nom, et c'est un des problèmes les plus étudiés de l'informatique. Comprendre pourquoi il est difficile explique tout le reste : pourquoi Excel n'y arrive pas, et pourquoi un bon outil ne promet jamais l'optimum absolu.
Vous avez une liste d'adresses et un point de départ. Dans quel ordre les visiter pour parcourir le moins de route possible en revenant au dépôt ? C'est tout. Et c'est le problème du voyageur de commerce.
Il paraît simple parce qu'un humain en résout une version approchée sans y penser, à dix arrêts, sur une carte. La difficulté n'apparaît qu'avec le nombre.
Le nombre d'ordres possibles est la factorielle du nombre d'arrêts. Ça ne parle à personne tant qu'on n'a pas vu les chiffres.
| Arrêts | Ordres possibles | Temps pour tous les essayer |
|---|---|---|
| 5 | 120 | instantané |
| 10 | 3,6 millions | quelques secondes |
| 15 | 1 300 milliards | plusieurs jours |
| 20 | 2,4 milliards de milliards | des dizaines d'années |
| 60 | plus que d'atomes dans l'univers observable | hors de portée, définitivement |
Un ordinateur mille fois plus rapide ne change rien : il gagne trois arrêts. C'est ce qui rend le problème intéressant, et c'est pourquoi personne ne l'attaque en essayant toutes les possibilités.
Il ne cherche pas le meilleur ordre : il cherche un très bon ordre, vite, et sait s'arrêter. La méthode tient en trois temps.
En pratique, on arrive à quelques pour cent de l'optimum théorique en quelques secondes. Le pour-cent restant coûterait des heures de calcul et ne vaut rien sur le terrain, où un camion mal garé coûte déjà plus cher.
C'est la conséquence la plus utile de tout ceci. Un tri classe chaque ligne selon une clé qui lui appartient : un code postal, un nom de rue, une distance au dépôt.
Or le coût d'un arrêt ne lui appartient pas : il dépend entièrement de celui qui le précède et de celui qui le suit. Aucune colonne de tableur ne porte cette information, donc aucun tri ne peut la prendre en compte, quel que soit le talent de celui qui trie.
Ce n'est pas une vue de l'esprit : sur six tournées mesurées, le tri par code postal a donné un trajet plus long que le fichier non trié dans deux cas. Les chiffres sont dans le guide ce que coûte une tournée mal ordonnée.
Trois conséquences pratiques, et c'est tout ce qu'il faut retenir :
Les cinq causes de décalage, comment repérer les points douteux avant de partir.
Lire le guideLe calcul en trois termes, les erreurs qui font déborder, et l'effet de la densité.
Lire le guideDes zones compactes plutôt que des paquets égaux, et pourquoi le code postal échoue.
Lire le guideNon, et probablement jamais au sens strict : personne ne connaît de méthode qui trouve la solution optimale rapidement quand le nombre d'arrêts grandit. En revanche, obtenir une solution à quelques pour cent de l'optimum en quelques secondes est un problème résolu depuis longtemps, et c'est ce qui compte sur le terrain.
Parce qu'aucun des deux ne cherche l'optimum : ils cherchent une bonne solution avec des heuristiques et un budget de temps différents. Deux ordres différents peuvent parfaitement donner deux distances très proches, à moins d'un pour cent l'une de l'autre.
Pas mieux que les algorithmes spécialisés qui l'attaquent depuis cinquante ans. L'optimisation de tournées est un domaine mature où les méthodes classiques, amélioration locale et recherche par voisinage, restent les plus efficaces.
Plusieurs centaines sans difficulté, et plusieurs milliers avec un peu plus de temps de calcul. La contrainte pratique n'est pas le solveur mais la mesure des distances routières entre tous les points, qui grandit comme le carré du nombre d'arrêts.
Déposez votre fichier et regardez l'ordre de passage que l'outil propose, en essai gratuit pendant 24h. Votre e-mail suffit, sans carte bancaire.
Tournée GPS