A shortest path routing problem with resource allocation

AbstractThis paper considers a variation of the short path problem in which the time required to traverse an arc is a function of the discrete amount of resource used up while traversing the arc. A short path is sought subject to a limit on the amount of resource available. Two algorithms are proposed for the solutions of this problem. A rather strict monotonicity assumptions ensures that all available resources will be used