Une nouvelle mesure de distance pour l'ACVRP

Abstract

Le problème de tournées de véhicules avec contraintes de capacité (CVRP) a pour but est de satisfaire la demande d'un ensemble de clients grâce à une flotte de véhicules ayant chacun une capacité limitée tout en minimisant la distance totale parcourue. Le problème asymétrique de tournées de véhicules avec contraintes de capacité (ACVRP) est un cas particulier du CVRPqui tient compte des spécificités des véhicules et/ou de la direction des tournées envisagées. Nous proposons une représentation des solutions de l'ACVRP et une relation de voisinage basée sur un opérateur d'échange. Puis, nous définissons une distance entre les solutions de l'ACVRP correspondant au nombre minimal d'application de l'opérateur d'échange nécessaire pour passer d'une solution à une autre. Nous donnons, enfin, un algorithme de calcul de cette distance ainsi que les expérimentations qui ont permis de montrer sa robustesse.