Program > By author > Hsu Tienté

Le Capacitated Arc Routing Problem (CARP) demande de visiter
m arrêtes pondérées d'un graphe avec un ensemble de tournées de longueur
totale minimale. Nous présentons une représentation à base
de permutations non orientées pour coder les solutions candidates. Étant
donné une permutation s, nous proposons un décodeur exact
qui donne la meilleure solution pour servir les m arrêtes dans
l'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 un
sens de traversée sur chaque arrête) [1], soit avec des
codages plus explicites. Le décodage des permutations
orientées est basé sur l'algorithme d'Ulusoy [2], de complexité
O(mw), où w est le plus grand nombre de services effectués
dans une tournée [1,sec3].

Le décodeur proposé a l'avantage d'avoir la même
complexité que l'algorithme d'Ulusoy ci-dessus (rapport interne [3]).
De plus, l'espace de recherche compte m! permutations, ce qui représente une
réduction de 2^m par rapport à l'espace de recherche à base
de permutations orientées (m!2^m). Cela nous a permis même
de tester assez facilement toutes les solution candidates
pour de petites instances (m=11). Finalement, notre
représentation permet d'accéder à une vaste littérature sur
l'optimisation dans des espaces à base de permutations,
e.g., il est possible d'adapter facilement tous les
opé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 memetic
algorithms for arc routing problems. AOR,131(1-4),2004.
[2]G.Ulusoy.The fleet size and mix problem for capacitated
arc routing. EJOR,22(3),1985.
[3]www.lgi2a.univ-artois.fr/~porumbel/carp.pdf