Solving min-max shortest-path problems on a network

✍ Scribed by Ishwar Murthy; Shenq-Shyong Her

• Publisher: John Wiley and Sons
• Year: 1992
• Tongue: English
• Weight: 877 KB
• Volume: 39
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/1520-6750(199208)39:5<669::aid-nav3220390506>3.0.co;2-w

✦ Synopsis

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 shortestpath 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.