Résolution de problèmes de tournées par la recherche des groupes homologiques du graphe modifié par

Mots-clés : VRP, topologie, groupe homologique, force layout, PLNE, smith normal form

Encadrants : Guillaume Bouleux, Lorraine Trilling
guillaume.bouleux@insa-lyon.fr, lorraine.trilling@insa-lyon.fr

1 Introduction
La résolution de problèmes de tournées de véhicule (VRP) nécessite bien souvent une approche
par Programmation Linéaire (PL) en intégrant les différentes contraintes structurelles
du problème sous-jacent. Il s?agit en fait de trouver dans le graphe associé un circuit hamiltonien.
Fréquemment pour les instances de grande taille, les contraintes conduisent à des temps
de résolution trop importants, il apparaît alors nécessaire de guider l?algorithme.
Nous proposons donc d?utiliser le groupe homologique [4] pour guider la recherche d?optimum,
en utilisant le force layout [6] pour la prise en compte de contraintes spécifiques au problème.
Afin d?illustrer l?idée proposée dans ce sujet, prenons le cas d?une tournée où un ensemble de
praticiens doivent rendre visite à des patients. Dans cet exemple, leur position est représentée
par la FIG. 1 ci-dessous.

FIG.1