Back

G-96-48

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

, , and

BibTeX reference

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

This cahier was revised in January 1999