Premium
Solving min‐max shortest‐path problems on a network
Author(s) -
Murthy Ishwar,
Her ShenqShyong
Publication year - 1992
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199208)39:5<669::aid-nav3220390506>3.0.co;2-w
Subject(s) - shortest path problem , mathematical optimization , longest path problem , computer science , k shortest path routing , path (computing) , pruning , constrained shortest path first , scheduling (production processes) , mathematics , algorithm , theoretical computer science , graph , agronomy , biology , programming language
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.