Solving min‐max shortest‐path problems on a network

Ishwar Murthy and Shenq‐Shyong Her

Naval Research Logistics (NRL), 1992, vol. 39, issue 5, 669-683

Abstract: In this article we consider the problem of determining a path between two nodes in a network that minimizes the maximum of r path length values associated with it. This problem has a direct application in scheduling. It also has indirect applications in a class of routing problems and when considering multiobjective shortest‐path problems. We present a label‐correcting procedure for this problem. We also develop two pruning techniques, which, when incorporated in the label‐correcting algorithm, recognize and discard many paths that are not part of the optimal path. Our computational results indicate that these techniques are able to speed up the label‐correcting procedure by many orders of magnitude for hard problem instances, thereby enabling them to be solved in a reasonable time. © 1992 John Wiley & Sons, Inc.

Date: 1992
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199208)39:53.0.CO;2-W

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:39:y:1992:i:5:p:669-683

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().