Séminaire conjoint CRT-Chaire de recherche du Canada en distributique

TITRE : The Elementary Resource-Constrained Shortest Path Problem

CONFÉRENCIÈRE : Irina Dumitrescu, Canada Research Chair in Distribution Management, HEC Montréal

DATE et ENDROIT : 6 octobre 2005, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l'Université de Montréal

RESPONSABLE : Jean-François Cordeau (340-6278)

RÉSUMÉ : Given a directed graph that has a (possibly negative) cost associated with each arc, a number of resources, each of them having a specified limit, and a nonnegative quantity of each resource consumed on each arc, the Elementary Resource Constrained Shortest Path Problem (ERCSPP) is to find the least cost path with no repeated nodes between two specified nodes so that the accumulated quantity of each resource consumed on all arcs in the path does not exceed its limit. We will present a label setting algorithm for solving the ERCSPP, which uses node resources to forbid repetition of nodes on the path, and several state-space augmenting strategies for accelerating run times.