A Transport Improvement Problem Transformable to a Best-Path Problem

For each arc (i, j) of a transport network, suppose given an initial traversal disutility d(i, j) and a function f(i, j, r) describing the reduced disutility that would result from applying r units of resources to “improve” the arc. For each origin-destination pair, there arises the problem of how a limited resource budget should be allocated among the arcs so as to optimize a best path from origin to destination in the improved network. It is shown here that this problem is transformable to a best-path problem in an enlarged network. The allowable investment levels in individual arcs can be constrained as desired.