Laboratoire de Génie Informatique et d’Automatique de l’Artois

Séminaire

Un décodeur pour le problème Arc-Routing et son application à l’optimisation heuristique

Le 26 novembre 2013 à 14h30 Salle des séminaires du LGI2A, FSA, Béthune
Daniel PORUMBEL Maître de conférences LGI2A

Contributeurs : Daniel Porumbel, Tienté Hsu, Hamid Allaoui, Gilles Goncalves

Résumé : La première partie du séminaire présente le problème d’Arc-Routing, ses applications et quelques généralités. L’objectif du problème est
de trouver un ensemble de routes de *distance totale minimale* capable
de *servir* certaines arrêtes (arcs) d’un graphe (réseau).
Selon la signification de la syntagme ’servir une arrête’, on peut
trouver plusieurs applications, comme le nettoyage de routes, la
maintenances de lignes ferroviaires, électriques, câbles
téléphoniques, ramassage d’ordures.

La deuxième partie porte sur des problématiques de résolution. Le
problème de arc-routing a été traditionnellement abordé par des
heuristiques basée sur des représentations (solutions candidates)
assez complexes. On propose un décodeur exacte qui a comme objectif de
transformer un objet mathématique assez simple (une permutation) en
une solution Arc-Routing (qui est un objet plus complexe, avec des
routes, des retours au dépôt, sens de traversées). L’objectif d’un tel
décodeur est de placer la résolution dans l’espace de permutations et
quelques recherches locale ont été implémentés.

En manipulant que des permutations, la taille de l’espace de recherche
(le nombre de solutions candidates) a été aussi minimisé, i.e., par
rapport aux précédents travaux, la taille a été réduite de m !2^m à m !.
Pour une petite instance de la littérature (m = 11), cela nous a même
permis de tester tous l’espace de recherche réduit et donc de fournir
la solution exacte (programmation Java, tests sur un ordinateur très
commun). Passer de 11 ! à 15 ! reste quand même très difficile,
peut-être même pour sur des ordinateurs hors du commun.