Groupe d’études et de recherche en analyse des décisions

G-96-48

A Two-Phase Resource Constrained Shortest Path Algorithm for Acyclic Graphs

, et

We consider a resource constrained shortest path problem in acyclic graphs, where resource windows are associated with the arcs, while lower and upper threshold and resetting values are given at the vertices to control the updating of the resource usage. Resource consumptions are not restricted to non-decreasing functions along the paths. The proposed formulation does not involve resource duplication when updating is not allowed at the vertices. This is an extension of the vertex-dependent windows formulation of the resource constrained shortest path problem where updating is allowed only for resource usage values that are smaller than the lower end of the corresponding windows. Pseudo-polynomial algorithms, based on dynamic programming and on a two-phase approach, are presented for the problem. The two-phase algorithm significantly reduces the practical computational burden for reoptimization if some vertices are removed or are fixed, or if arc costs are modified. Moreover, worst case complexity results indicate that the complexity of the generalized permanent labelling algorithm proposed by Desrochers and Soumis (1988) is over-estimated.

, 25 pages

Ce cahier a été révisé en janvier 1999