Tournées de véhicules avec contraintes de clustering

International audienceDe nombreuses applications de la logistique imposent que les clients à livrer soient regroupés en sous-ensembles (clusters) ce qui facilite la livraison ou tout travail amont ou aval de traitement des clients. On est alors face à un problème de " Clustered CVRP ". Le problème est celui du CVRP avec la contrainte supplémentaire que chaque cluster doit être visité intégralement par un même véhicule (ce véhicule peut visiter plusieurs clusters). Notre approche divise le problème en deux parties (stratégique et opérationnelle). Dans l'étape stratégique, on décide de l'ordre de visite des clusters et des affectations de ces clusters aux véhicules. Cette étape est réalisée à partir d'un algorithme de la littérature (Record-To-Record Travel Algorithm). Dans la partie opérationnelle, on indique dans quel ordre les clients seront visités à l'intérieur de chaque cluster. Ce sous-problème est le Shortest Hamiltonian Path Problem (NP-Difficile) qui est abordé à l'aide de plusieurs approches (MILP, Algorithmes de Christophides et de Lin-Kernighan). Les deux étapes sont itérées au sein d'une approche de type multi-start avec des phases d'intensification et de shaking. Les tests numériques montrent la validité de cette approche