A shortest path routing problem with resource allocation (Q581257)

The shortest path problem in a network is considered under the condition that the time to go from vertex i to vertex j is a function \(t_{ij}(m)\) of the amount n of resources used in the process. A slight modification of the well-known dynamic programming algorithm for the original shortest path problem is used to solve this problem. The authors examine also the case that allocations of zero are allowed and prove an existence and uniqueness assertion about the solution. Finally numerical examples are given.