Solveur CVRP

Pseudocode

Le CVRP est le VRP avec une limite de charge par véhicule. Cette seule contrainte change quels regroupements sont seulement réalisables, et donc toute la structure de la recherche.

CVRP(depot, clients, capacite Q):
    // Construction par economies de Clarke-Wright
    demarrer avec une tournee dediee par client
    pour chaque paire (i, j):
        economie[i][j] = d(dep,i) + d(dep,j) - d(i,j)
    trier les paires par economie decroissante

    pour chaque paire (i, j) dans cet ordre:
        si i et j sont dans des tournees differentes
           et sont tous deux extremites de leur tournee
           et demande(tournee_i) + demande(tournee_j) <= Q:
            fusionner les deux tournees

    // Ensuite: 2-opt interne et mouvements entre tournees,
    // en rejetant toujours ceux qui violent la capacite

La valeur d'économie mesure ce que l'on gagne à servir i et j sur la même tournée plutôt que par deux allers-retours distincts. Le test de capacité est ce qui distingue le CVRP du VRP: une fusion peut être très rentable en distance et purement et simplement inadmissible en charge. Toute recherche locale ultérieure doit répéter ce test à chaque mouvement, car un échange entre tournées améliorant la distance peut rendre une tournée irréalisable.

Exemple détaillé, étape par étape

Achemine cinq clients avec un véhicule de capacité 10 et observe comment la contrainte de charge rejette la fusion la plus rentable.

Graphe d'exemple: Dépôt plus cinq clients de demandes C1 égale 4, C2 égale 4, C3 égale 3, C4 égale 3 et C5 égale 2. Chaque véhicule peut transporter 10 unités.

1. Démarrer avec des tournées dédiées. Cinq tournées, une par client, chacune un aller-retour depuis le dépôt. C'est réalisable mais coûteux, et c'est le point de départ de la méthode des économies.
2. Fusionner par économie décroissante. La paire de plus grande économie est C1 et C2, qui sont de surcroît géographiquement proches. Leur demande combinée vaut 4 + 4 = 8, dans la capacité 10, la fusion est donc acceptée.
3. La fusion rentable suivante est rejetée. La meilleure économie suivante ajouterait C3 à cette même tournée. La distance s'améliorerait nettement, mais la demande passerait à 8 + 3 = 11, au-dessus de la capacité 10. La fusion est rejetée alors qu'elle est la meilleure en distance.
4. Poursuivre avec les fusions admissibles. C3, C4 et C5 fusionnent entre eux pour une demande totale de 3 + 3 + 2 = 8, dans la capacité. Restent deux tournées: une avec C1 et C2 de charge 8, et une avec C3, C4 et C5 de charge 8.

La solution utilise deux véhicules de charges 8 et 8, alors que la fusion la plus attrayante en distance aurait été d'ajouter C3 à la première tournée. Ce rejet constitue toute la différence entre VRP et CVRP: dans le VRP pur cette fusion aurait été acceptée et la solution serait plus courte mais irréalisable. Note en outre que la demande totale vaut 16 et la capacité par véhicule 10, deux véhicules constituent donc le minimum; aucune solution à un seul véhicule n'existe, si bonne que soit l'optimisation.

Complexité et son origine

Temps: NP-difficile; Clarke-Wright O(n^2 log n) · Espace: O(n^2)

La construction par économies de Clarke-Wright calcule une valeur d'économie pour chacune des O(n au carré) paires et les trie, ce qui domine le coût avec O(n au carré log n). Chaque tentative de fusion est un test en temps constant sur les charges et les extrémités de tournées si l'on maintient les structures adéquates. La recherche locale ultérieure coûte O(n au carré) par passe. Le problème lui-même est NP-difficile, puisqu'il contient le TSP, et l'ajout de la capacité le durcit encore en découpant l'espace des solutions réalisables de façon irrégulière. Les méthodes exactes par génération de colonnes résolvent des instances de référence d'une centaine de clients; au-delà on emploie des métaheuristiques. Une borne inférieure utile et gratuite est la demande totale divisée par la capacité, arrondie au supérieur, qui donne le nombre minimal de véhicules.

Quand utiliser Routage de Véhicules avec Capacité (CVRP), et quand l'éviter

Chaque contrainte supplémentaire définit une variante distincte avec sa propre littérature et ses propres solveurs.

Pièges fréquents

• Ne vérifier la capacité qu à la construction. Tout mouvement de recherche locale, déplacer un client, en échanger deux, inverser un segment entre tournées, peut violer la capacité. Le test doit être répété à chaque mouvement et non uniquement pendant la construction initiale.
• Oublier la borne inférieure par demande totale. La demande totale divisée par la capacité, arrondie au supérieur, donne le nombre minimal de véhicules. Elle se calcule gratuitement et indique immédiatement si une solution à moins de véhicules est seulement possible, tout en servant à évaluer la qualité de celle dont tu disposes.
• Supposer que moins de véhicules est toujours mieux. Réduire la flotte allonge chaque tournée, et s'il existe des coûts horaires de conducteur ou des limites de journée, la solution à moins de véhicules peut revenir plus cher. Optimise le coût réel, pas le nombre de véhicules.
• Modéliser des demandes fractionnables quand elles ne le sont pas. Le CVRP standard suppose que chaque client est servi intégralement en une seule visite. Si une livraison peut réellement être scindée entre deux véhicules, il s'agit du VRP à livraisons fractionnées, un problème distinct aux solutions structurellement différentes et souvent moins coûteuses.
• Négliger la charge au retour. En collecte, la charge augmente le long de la tournée au lieu de diminuer, la contrainte déterminante se situe donc en fin de parcours et non au début. Mêler livraisons et collectes sur une même tournée impose de vérifier la charge à chaque arrêt.

Questions fréquentes

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

Le CVRP cherche l'ensemble de tournées le moins coûteux pour une flotte partant d'un dépôt, où chaque client a une demande et où aucun véhicule ne peut dépasser sa capacité de charge. C'est la variante standard du VRP en logistique réelle et en distribution de marchandises.

Quelle est la différence entre VRP et CVRP?

Le VRP achemine une flotte sans limite de charge; le CVRP ajoute une capacité par véhicule qu'aucune tournée ne peut dépasser. Cette contrainte change quels regroupements de clients sont seulement réalisables, si bien que des solutions plus courtes en distance peuvent être écartées comme irréalisables, comme dans l'exemple où la fusion la plus rentable est rejetée pour un dépassement d'une seule unité.

Comment fonctionne l'algorithme des économies de Clarke-Wright?

Il démarre avec une tournée dédiée par client et calcule, pour chaque paire, la distance économisée en les servant sur la même tournée plutôt que par deux trajets séparés. Il parcourt ensuite les paires par économie décroissante et fusionne les tournées correspondantes dès lors que les deux clients sont extrémités de tournée et que la charge combinée respecte la capacité.

Quel est le nombre minimal de véhicules dans un CVRP?

Au moins la demande totale divisée par la capacité d'un véhicule, arrondie au supérieur. C'est une borne inférieure issue du problème de bin packing, calculable instantanément et utile aussi bien pour savoir si une solution à peu de véhicules est possible que pour évaluer la qualité de la solution courante.

À quoi sert le CVRP?

À planifier la livraison de marchandises, la distribution alimentaire et de boissons, la logistique de conteneurs, la collecte des déchets et le réapprovisionnement de magasins. C'est le modèle standard partout où une flotte de capacité finie doit servir un ensemble de clients aux demandes connues depuis un dépôt central.