×

Microcomputer-based algorithms for large scale shortest path problems. (English) Zbl 0586.90086

This paper reports on the implementation and computational testing in the microcomputer environment of several versions of a threshold-based in- core/out-of-core shortest path algorithm for finding the shortest path from one node to all other nodes in a network. These variants were compared to the best in-core/out-of-core label-correcting code, C5V7, developed in the 1970’s. All codes were written in Pascal and tested on an 8088 microprocessor-based computer with a hard disk unit (IBM PC/XT) under the MS-DOS operating system. The results of the empirical study on a diverse set of medium and large-scale random and city transit grid networks provide new insights for the design of in-core/out-of-core shortest path algorithms and demonstrate the remarkable capability of a threshold-based algorithm to be fine tuned to a particular problem topology, processing environment, or computer configuration. In addition these results demonstrate the feasibility and computational tractability of solving large scale shortest path problems with microcomputers. The best approach solved a variety of problems ranging in size up to 15,000 nodes and 600,000 arcs in 10 minutes or less of wall clock time.

MSC:

90C35 Programming involving graphs or networks
05C35 Extremal problems in graph theory
65K05 Numerical mathematical programming methods
05C38 Paths and cycles

Software:

VRP; Algorithm 360
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adolphson, D., Testing and implementation of a micro-computer network optimization system, (TIMS/ORSA National Meeting. TIMS/ORSA National Meeting, San Francisco (1984))
[2] Barr, R., Micro-computer based network optimization programming, (TIMS/ORSA National Meeting. TIMS/ORSA National Meeting, San Francisco (1984))
[3] Bellman, R., On a routing problem, Quart. Appl. Math., 16, 87-90 (1958) · Zbl 0081.14403
[4] Bennington, G., Applying network analysis, J. Industrial Engg., 6, 17-25 (1974)
[5] Bradley, G., Survey of deterministic networks, AIIE Trans., 7, 222-234 (1975)
[6] Christofides, N.; Mingozzia, A.; Toth, P., Exact algorithms for the vehicle routing problem, based on spanning trees and shortest path relaxations, Math. Programming, 20, 255-282 (1981) · Zbl 0461.90067
[7] Davis, E., Networks: resource allocation, J. Industrial Engg., 6, 22-32 (1974)
[8] Denardo, E.; Fox, B., Shortest-route methods: 1. Reaching, pruning, and buckets, Oper. Res., 27, 161-186 (1979) · Zbl 0391.90089
[9] Derigs, U., A shortest augmenting path method for solving minimal perfect matching problems, Networks, 11, 379-390 (1981) · Zbl 0475.05069
[10] Dial, R., Algorithm 360 shortest path forest with topological ordering, Comm. ACM, 12, 632-633 (1969)
[11] Dial, R.; Glover, F.; Karney, D.; Klingman, D., A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees, Networks, 9, 215-248 (1979) · Zbl 0414.68035
[12] Dijkstra, E., A note on two problems in connection with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002
[13] Doulbiez, P.; Ras, M., Optimal network capacity planning: A shortest path scheme, Oper. Res., 23, 810-818 (1975) · Zbl 0307.90026
[14] Elam, J.; Klingman, D.; Mulvey, J., An evaluation of mathematical programming and minicomputers, Europ. J. Oper. Res., 3, 30-39 (1979) · Zbl 0387.90110
[15] Engquist, M., A successive shortest path algorithm for the assignment problem, INFOR, 20, 86-101 (1982)
[16] Ford, L., Network Flow Theory, ((1956), The Rand Corporation), P-293
[17] Frieze, A., Shortest path algorithms for knapsack type problems, Math. Programming, 11, 150-157 (1976) · Zbl 0352.90040
[18] Fulkerson, D., Flow networks and combinatorial operations research, Amer. Math. Monthly, 73, 115-138 (1966) · Zbl 0168.40706
[19] Gallo, G.; Pallottino, S.; Ruggen, C.; Starchi, G., Shortest paths: A. bibliography, SOFTMAT Document 81-P1-4-SOFTMAT-27 (1982), Rome, Italy
[20] Garcia-Diaz, A.; Liebman, J., An investment staging model for a bridge replacement problem, Oper. Res., 28, 736-753 (1980) · Zbl 0451.90063
[21] Gilsinn, J.; Witzgall, C., A performance comparison of labeling algorithms for calculating shortest path trees, (NBS Technical Note 772 (1973), U.S. Dept. of Commerce)
[22] Glover, F.; Glover, R.; Klingman, D., Computational study of an improved shortest path algorithm, Networks, 14, 25-37 (1984)
[23] Glover, F.; Klingman, D., Network applications in industry and government, AIIE Trans., 363-376 (1977)
[24] F. Glover, R. Glover and D. Klingman, Threshold assignment algorithm, Math. Programming Study, to appear.; F. Glover, R. Glover and D. Klingman, Threshold assignment algorithm, Math. Programming Study, to appear. · Zbl 0605.90099
[25] Glover, F.; Klingman, D.; Phillips, N., A new polynomially bounded shortest path algorithm, Oper. Res., 33, 65-73 (1985) · Zbl 0578.90089
[26] Glover, F.; Klingman, D.; Phillips, N.; Schneider, R., New polynomial shortest path algorithms and their computational attributes, Management Sci. (1985), to appear · Zbl 0609.90103
[27] Golden, B.; Magnanti, T., Transportation planning: Network models and their implementation, (Studies in Operations Management (1978), North-Holland: North-Holland Amsterdam), 365-518
[28] Houck, D.; Picard, J.; Queyranne, M.; Vermuganti, R., The travelling salesman problem as a constrained shortest path problem: Theory and computational experience, Opsearch, 17, 93-109 (1980) · Zbl 0446.90084
[29] Hung, M.; Rom, W., Solving the assignment problem by relaxation, Oper. Res., 28, 969-982 (1980) · Zbl 0441.90062
[30] Kargaonker, M., Production smoothing under piecewise concave costs, capacity constraints and non-decreasing requirements, Management Sci., 24, 302-311 (1977) · Zbl 0371.90050
[31] Karney, D.; Klingman, D., Implementation and computational study on an in-core, out-of-core primal network code, Oper. Res., 24, 1056-1077 (1976) · Zbl 0339.90041
[32] Klingman, D.; Mote, J.; Whitman, D., Computational analysis of in-core out-of-core shortest path algorithms, (Research Report CCS 322 (1978), Center for Cybernetic Studies, The University of Texas at Austin)
[33] Klingman, D.; Mulvey, J., Applicability of shortest-path and minimum cost flow network algorithms for minicomputers and micro-processors, (Proc. 9th Internat. Mathematical Programming Symposium. Proc. 9th Internat. Mathematical Programming Symposium, Budapest, Hungary (August 1976))
[34] Mandl, C., Evaluation and optimization of urban public transportation networks, Europ. J. Oper. Res., 5, 396-404 (1980) · Zbl 0441.90030
[35] Moore, E., The shortest path through a maze, (Proc. Internat. Symposium on the Theory of Switching, Part II. Proc. Internat. Symposium on the Theory of Switching, Part II, 1957. Proc. Internat. Symposium on the Theory of Switching, Part II. Proc. Internat. Symposium on the Theory of Switching, Part II, 1957, The Annals of the Computation Laboratory of Harvard University, 30 (1959), Harvard University Press)
[36] Pape, U., Implementation and efficiency of Moore-algorithms for the shortest route problem, Math. Programming, 7, 212-222 (1974) · Zbl 0288.90080
[37] Ross, T.; Soland, R., A branch and bound algorithm for the generalized assignment problem, Math. Programming, 8, 91-105 (1975) · Zbl 0308.90028
[38] Schwartz, M.; Stern, T., Routing techniques used in computer communications networks, IEEE Trans. Comm., 28, 539-552 (1980)
[39] Shier, D.; Witzgall, C., Properties of labeling methods for determining shortest path trees, J. Res. Nat. Bur. Standards, 86, 317-330 (1981) · Zbl 0463.68061
[40] Whiting, P.; Hiller, J., A method for finding the shortest routing through a road network, Oper. Res. Quart., 11, 37-40 (1960)
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.