Proposition de sujet de stage

Etude algorithmique des problèmes de plus courts chemin avec contraintes de ressources

Encadrement

Sylvain Durand(LIRMM / Projet Algorithmique et Performances des Réseaux), Dominique Feillet (LIA / Projet RO)

Mots clés

Optimisation, méthodes exactes, heuristiques, approximation.

Le problème

Ce sujet s’inscrit dans le cadre d’une collaboration entre le LIRMM et le LIA (Laboratoire d’Informatique d’Avignon). L’objet de cette collaboration est d’évaluer, de comparer et de mutualiser l’information fournie par trois approches de résolution de problèmes d’optimisation combinatoires très différentes : la résolution exacte, la résolution approchée avec garantie de performance, la résolution approchée sans garantie de performance.

Ce sujet a pour but d’étudier cette problématique dans le cadre d’un problème d’optimisation combinatoire très classique dans le domaine du transport : le problème de plus court chemin avec contraintes de ressources (SPPRC, pour Shortest Path Problem with Resource Constraints).

Comme son nom l’indique, le SPPRC est une extension du problème de recherche d’un plus court chemin dans un graphe, dans laquelle des contraintes rendent invalides certains chemins. Les interdictions sont modélisées par l’intermédiaires de ressources en définissant pour chaque ressource :
- une fonction d’extension de ressource pour chaque arc du graphe, indiquant comment évolue la consommation de la ressource lorsqu’un arc est emprunté ;
- une contrainte pour chaque sommet du graphe, indiquant une valeur maximale sur la consommation de la ressource permettant d’atteindre le sommet.

Les ressources considérées peuvent par exemple être le temps, lorsqu’une heure d’arrivée au plus tard est imposée à la destination finale (ou à certains sommets du graphe), la charge, lorsque le chemin emprunté correspond à l’itinéraire d’un véhicule de capacité limitée et effectuant des chargements le long du chemin, etc.

Le SPPRC est principalement connu pour son rôle en tant que sous-problème dans les méthodes de résolution par génération de colonnes de problèmes de tournées de véhicules [4]. Il apparaît également dans divers autres contextes, comme par exemple des opérateurs de voisinages [1,5].

Le SPPRC est NP-difficile au sens faible. Il a été largement étudié et des algorithmes de programmation dynamique efficaces ont été proposés pour sa résolution. Plusieurs variantes heuristiques de ces algorithmes ont également été développées [4]. Des algorithmes avec garantie de performances existent enfin dans certains cas particuliers [2,6].

Le début du stage sera consacré à une revue détaillée de la littérature, notamment pour ce qui concerne les algorithmes avec garanties de performance. A notre connaissance, seuls quelques cas particuliers (une ressource, graphe acyclique, pas de contraintes sur les sommets, …) sont actuellement traités. Nous essaierons dans un premier temps d’étendre ces résultats, ou d’en proposer de nouveaux, selon les particularités du problème :
- graphe acyclique / quelconque
- coût positifs / quelconques
- chemins élémentaires / non élémentaires [3]
- type et nombre de ressources (temps, charge, requêtes origine-destination, liste de chemins interdits [7]…)
- etc.

Selon l’avancement, le stage se concentrera ensuite sur la manière dont ses résultats peuvent être utilisés pour aider des méthodes de résolution exactes ou heuristiques.

Bibliographie

[1] Bontoux B. et D. Feillet, « Ant colony optimization for the traveling purchaser problem », rapport technique LIA, 2005

[2] Ergun F., R. Sinha et L. Zhang, « An improved FPTAS for restricted shortest path », Information Processing Letters, Volume 83, Issue 5, 2002, Pages 287-291

[3] Feillet D., P. dejax, M. Gendreau, C. Gueguen, « An exact algorithm for the elementary shortest path problem with resource constraints : application to some vehicle routing problems », Networks, Volume 44, Pages 216-229, 2004

[4] Irnich S., G. Desaulniers « Shortest path problems with resource constraints », in « Column generation », éditeurs G. Desaulniers, J. Desrosiers et M.M. Solomon

[5] Garaix T., C. Artigues, D. Feillet et D. Josselin, « Résolution de problèmes de transport à la demande avec chemins alternatifs », rapport technique LIA, 2005

[6] Lorenz D.H. et D. Raz. « A simple efficient approximation scheme for the restricted shortest path problem », Operations Research Letters, Volume 28, Issue 5, 2001, Pages 213-219

[7] Villeneuve D. et G. Desaulniers, « The shortest path problem with forbidden paths », European Journal of Operational Research, Volume 165, Issue 1, 2005, Pages 97-107