Solveur de Tournées de Véhicules

Pseudocode

Le problème de tournées de véhicules généralise le TSP à une flotte. L'approche pratique suit le schéma regrouper d'abord, router ensuite: répartir les clients entre les véhicules puis résoudre un TSP par véhicule.

VRP(depot, clients, nbVehicules):
    // Phase 1: repartir les clients entre les vehicules
    groupes = regrouper(clients, nbVehicules)
    // par secteurs angulaires, k-moyennes ou economies de Clarke-Wright

    // Phase 2: router chaque vehicule
    pour chaque groupe g:
        tournee[g] = resoudreTSP(depot + g)

    // Phase 3: amelioration entre tournees
    repeter jusqu a absence d amelioration:
        essayer de deplacer un client vers une autre tournee
        essayer d echanger des clients entre deux tournees
        reoptimiser en 2-opt les tournees modifiees

La phase 3 sépare une solution médiocre d'une bonne. Regrouper puis router produit des tournées convenables, mais les frontières entre groupes sont souvent mal tracées, et déplacer un seul client d'une tournée surchargée vers sa voisine rapporte fréquemment davantage que toute réoptimisation interne. Les mouvements entre tournées sont donc essentiels et non un ornement final.

Exemple détaillé, étape par étape

Répartis six clients entre deux véhicules depuis un dépôt unique et observe pourquoi l'amélioration entre tournées compte.

Graphe d'exemple: Un dépôt central et six clients répartis autour: trois groupés au nord et trois au sud, mais l'un des clients du nord se trouve nettement plus près du groupe sud que du reste de son propre groupe.

1. Phase 1, regrouper par secteur. Un balayage angulaire depuis le dépôt divise les clients en un secteur nord et un secteur sud, trois et trois. C'est équilibré et géométriquement naturel.
2. Phase 2, router chaque groupe. Chaque véhicule résout un TSP sur son propre groupe plus le dépôt, par plus proche voisin suivi de 2-opt. Les deux tournées sont internement propres, sans croisement.
3. Le problème de frontière. Le client du nord réellement plus proche du groupe sud impose à son véhicule un long détour. Aucun 2-opt interne à la tournée nord n'y remédie, car le problème n'est pas l'ordre de visite mais l'appartenance au groupe.
4. Phase 3, déplacer entre tournées. Déplacer ce client vers la tournée sud raccourcit fortement la tournée nord et allonge peu la tournée sud, la distance totale diminue donc. Un 2-opt est ensuite réappliqué aux deux tournées.

La répartition finale n'est plus équilibrée en nombre, quatre clients contre deux, et pourtant la distance totale est moindre. C'est le point central du VRP: regrouper par géométrie produit des groupes d'allure soignée, mais l'objectif est la distance totale et non la symétrie. Toute implémentation qui s'arrête après regroupement et routage laisse sur la table des gains typiquement compris entre 10 et 20 pour cent.

Complexité et son origine

Temps: NP-difficile; heuristiques O(n^2) à O(n^3) · Espace: O(n^2)

Le VRP contient le TSP comme cas particulier, avec un seul véhicule et sans capacité, il est donc immédiatement NP-difficile. L'énumération exacte est impensable hors instances minuscules; les méthodes exactes modernes, fondées sur la génération de colonnes et la séparation et coupe, résolvent des instances d'une centaine de clients au prix d'un effort considérable. Ce sont les heuristiques qui servent en production: la construction par économies de Clarke-Wright est en O(n au carré log n), dominée par le tri des économies, regrouper puis router coûte le regroupement plus un TSP par véhicule, et la recherche locale entre tournées coûte O(n au carré) par passe. La matrice des distances occupe à elle seule O(n au carré), ce qui constitue en pratique la contrainte mémoire dominante sur les grandes instances.

Quand utiliser Répartition de Flotte (mTSP), et quand l'éviter

Identifie d'abord les contraintes réelles de ton problème, car chacune le pousse vers une famille différente.

Pièges fréquents

• S arrêter après regroupement et routage. Les frontières entre groupes sont presque jamais optimales, et l'amélioration entre tournées récupère typiquement 10 à 20 pour cent de la distance. Omettre la phase 3 est l'erreur la plus fréquente et la plus coûteuse.
• Insister sur des tournées équilibrées. Répartir les clients à parts égales entre véhicules paraît ordonné mais minimise rarement la distance. Si l'objectif est le coût total, laisse les tailles de tournées se déséquilibrer; si l'objectif est l'équité entre conducteurs, dis-le explicitement et modélise-le comme contrainte.
• Utiliser la distance à vol d oiseau sur un réseau routier. La distance euclidienne ignore les sens uniques, les rivières et les autoroutes. En ville, les temps de conduite réels peuvent dépasser la ligne droite de plus du double, et des tournées optimisées sur la mauvaise métrique ne sont pas optimales sur la vraie.
• Traiter le nombre de véhicules comme fixe alors qu il ne l est pas. Il est parfois moins coûteux d'utiliser un véhicule de moins avec des tournées plus longues qu'un conducteur et un véhicule supplémentaires. Si la taille de flotte est une décision et non une donnée, intègre-la au modèle au lieu de la figer par habitude.
• Ignorer les temps de service. Le temps de déchargement à chaque arrêt domine souvent le temps de conduite en distribution urbaine dense. N'optimiser que la distance parcourue produit des tournées qui ne tiennent pas dans la journée de travail.

Questions fréquentes

Qu'est-ce que le problème de tournées de véhicules?

Le VRP cherche l'ensemble de tournées le moins coûteux pour une flotte partant d'un dépôt et devant servir un ensemble de clients, chaque véhicule revenant au dépôt. Il généralise le problème du voyageur de commerce à plusieurs véhicules et fonde la planification de livraison, la collecte des déchets et la distribution de marchandises.

Quelle est la différence entre TSP et VRP?

Le TSP achemine un unique véhicule à travers toutes les villes sans autre contrainte que de visiter chacune une fois. Le VRP achemine une flotte depuis un dépôt et décide en outre quels clients sont affectés à quel véhicule. Le TSP est le cas particulier du VRP à un véhicule et capacité illimitée.

Comment résout-on un VRP en pratique?

Par le schéma regrouper d'abord, router ensuite: répartir les clients entre véhicules par secteurs angulaires, k-moyennes ou économies de Clarke-Wright, résoudre un TSP pour chaque véhicule, puis améliorer en déplaçant et échangeant des clients entre tournées. Cette dernière phase est essentielle, les frontières entre groupes étant rarement optimales.

Pourquoi le VRP est-il difficile?

Parce qu'il contient le TSP comme cas particulier et y ajoute la décision d'affectation. Il faut décider simultanément quels clients vont ensemble et dans quel ordre ils sont visités, et ces deux décisions interagissent. Il est NP-difficile, et les méthodes exactes actuelles traitent l'ordre de 100 clients au prix d'un effort considérable.

Les tournées doivent-elles être équilibrées?

Seulement si l'équité entre conducteurs est un objectif explicite. Si l'objectif est la distance ou le coût total, imposer des tournées de même taille dégrade presque toujours la solution. Une répartition déséquilibrée qui réduit la distance totale est la bonne réponse, sauf contrainte contraire.