Capacitated Arc Routing: Représentation Simplifiée, Décodeur Exact et Meta-heuristiques

International audienceLe Capacitated Arc Routing Problem (CARP) demande de visiter m arrêtes pondérées d'un graphe avec un ensemble de tournées de longueurtotale minimale. Nous présentons une représentation à basede permutations non orientées pour coder les solutions candidates. Étantdonné une permutation s, nous proposons un décodeur exact qui donne la meilleure solution pour servir les m arrêtes dansl'ordre s(1), s(2), ...s (m)Les solutions candidates pour CARP ont souvent étéreprésentées soit comme des permutations orientées (avec unsens de traversée sur chaque arrête) [1], soit avec descodages plus explicites. Le décodage des permutationsorientées est basé sur l'algorithme d'Ulusoy [2], de complexitéO(mw), où w est le plus grand nombre de services effectuésdans une tournée [1,sec3].Le décodeur proposé a l'avantage d'avoir la mêmecomplexité que l'algorithme d'Ulusoy ci-dessus (rapport interne [3]). De plus, l'espace de recherche compte m! permutations, ce qui représente uneréduction de 2^m par rapport à l'espace de recherche à basede permutations orientées (m!2^m). Cela nous a permis mêmede tester assez facilement toutes les solution candidatespour de petites instances (m=11). Finalement, notrereprésentation permet d'accéder à une vaste littérature surl'optimisation dans des espaces à base de permutations,e.g., il est possible d'adapter facilement tous lesopérateurs conçus pour le TSP. Des recherches locales ontété implémentées et les résultats sont prometteurs.[1]P.Lacomme,C.Prins,W.~Ramdane-Chèrif. Competitive memeticalgorithms for arc routing problems. AOR,131(1-4),2004.[2]G.Ulusoy.The fleet size and mix problem for capacitatedarc routing. EJOR,22(3),1985.[3]www.lgi2a.univ-artois.fr/~porumbel/carp.pdf