A shortest path routing problem with resource allocation

DOI10.1016/0022-247X(87)90022-9MaRDI QIDQ581257zbMATH OpenFDO

Authors N. G. F. Sancho, Giorgio Pederzoli

Publication date 1987

Published in Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-247X(87)90022-9

zbMATH Keywords

resource conditionshortest path

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Review text

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.

Recommendations

• An algorithm for the resource constrained shortest path problem
• Some dynamic time-optimality problems on networks with allocation of several resource types
• An Appraisal of Some Shortest-Path Algorithms
• An approach to the shortest path problem with time-varying
• scientific article; zbMATH DE number 1114039

Cites work

• scientific article; zbMATH DE number 3805267 (Why is no real title available?)
• Introduction to the mathematical theory of control processes. Vol. II:Nonlinear processes
• The art and theory of dynamic programming
• The optimal route problem and the method of approximation in policy space
• Validity of Local Search in Multiparametric and Vector Linear Programming

Cited in

(10)

• Some dynamic time-optimality problems on networks with allocation of several resource types
• scientific article; zbMATH DE number 1670670 (Why is no real title available?)
• Mathematical modeling for equipment updating based on shortest path
• A New Necessary Condition for Shortest Path Routing
• Maximum Reliability throught a Newtork with Resource Contraints
• scientific article; zbMATH DE number 3968370 (Why is no real title available?)
• An algorithm for the resource constrained shortest path problem
• Letter to the editor: A variant on the shortest-route problem
• Algebraic theory on shortest paths for all flows
• An algorithm to determine a path with minimal cost/capacity ratio

This page was built for publication: A shortest path routing problem with resource allocation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q581257)