Solving min-max shortest-path problems on a network. (English) Zbl 0761.90095
Summary: 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.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90B35 | Deterministic scheduling theory in operations research |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
| 90B06 | Transportation, logistics and supply chain management |
References:
| [1] | Aneja, Networks 13 pp 295– (1983) |
| [2] | Beasley, Networks 19 pp 379– (1989) |
| [3] | ”On the Relationship of the Tchebycheff Norm and the Efficient Frontier of Multiple-Criteria Objectives”, Lecture Notes in Economic and Mathematical Systems, Springer-Verlag, Berlin, 1976, Vol. 135, pp. 76–85. |
| [4] | Desrochers, INFOR 26 pp 193– (1988) |
| [5] | Desrochers, American Journal of Mathematical and Management Science 6 pp 301– (1986) · Zbl 0632.90087 · doi:10.1080/01966324.1986.10737198 |
| [6] | Dial, Networks 9 pp 215– (1979) |
| [7] | Fisher, Management Science 27 pp 1– (1981) |
| [8] | and , ”A Performance Comparison of Labeling Algorithms for Calculating Shortest Path Trees”, Technical Note No. 772, National Bureau of Standards, Washington, DC, 1973. · doi:10.6028/NBS.TN.772 |
| [9] | ”Bicriterion Path Problems”, in Multiple Criteria Decision Making Theory and Application, G. Fandel and T. Gal, Eds., 1980, pp. 109–127. |
| [10] | Held, Mathematical Programming 5 pp 62– (1974) |
| [11] | Horowitz, Journal of the Association for Computing Machinary 23 pp 317– (1976) · Zbl 0329.68041 · doi:10.1145/321941.321951 |
| [12] | Jaffe, Networks. 14 pp 95– (1984) |
| [13] | Joksh, Journal of the Mathematical Analysis and Applications 14 pp 191– (1966) |
| [14] | Mole, Operational Research Quarterly 27 pp 503– (1976) |
| [15] | , and , ”An Empirical Investigation on the Number of Pareto-Optimal Paths Obtained for Bicriterion Shortest Path Problems”, Working Paper, Q. B. A. Department, Louisiana State University, 1988. |
| [16] | and , ”Effective Pruning Methods in Labeling Algorithms to Solve Constrained Shortest Path Problems”, Working Paper, Q. B. A. Department, Louisiana State University, 1989. |
| [17] | Orloff, Transportation Science 10 pp 149– (1976) |
| [18] | Rana, Transportation Science 22 pp 83– (1988) |
| [19] | Sahni, Journal of the Association for Computing Machinary 23 pp 116– (1976) · Zbl 0326.68024 · doi:10.1145/321921.321934 |
| [20] | Sakawa, Large Scale Systems 5 pp 69– (1983) · Zbl 0527.93050 |
| [21] | Multiple Criteria Optimization: Theory, Computation, and Application, Robert E. Krieger, Malabar, FL, 1989. · Zbl 0742.90068 |
| [22] | Steuer, Mathematical Programming 26 pp 326– (1983) |
| [23] | Steuer, Large Scale Systems 10 pp 243– (1986) |
| [24] | Vincke, Cahiers du Centre d’Etudes de Recherche Operationnelle 16 pp 425– (1974) |
| [25] | Warburton, Operations Research 35 pp 70– (1987) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
