Algorithm for finding subcritical paths on network diagrams
https://doi.org/10.32362/2500-316X-2023-11-1-60-69
Abstract
Objectives. Network diagrams are used as an information support element in planning and project management processes for structuring planned work and calculating project efficiency characteristics. In order to optimize and balance resources used in projects, it becomes necessary to locate in these models not only the critical path of the maximum weighted length, but also the subcritical paths closest to it having a shorter length in relation to it. The aim of the work is to synthesize and analyze an algorithm for finding k-shortest paths between the input and output network vertices, on which basis the above-mentioned subcritical paths can be identified.
Methods. The provisions of graph theory and group theory, as well as the method of dynamic programming, were used.
Results. An algorithm for finding k-shortest paths in contourless directed graphs having a strict order relation was developed. Abstract elements were defined according to group theory in graphs as p-contours, between which a multilevel structure of relations for implementing the necessary search of paths was then established. For substantiating the efficiency of the constructed algorithm, the validity of the main provisions was demonstrated as follows: firstly, the multilevel system of relations is exhaustive; secondly, there is no loss in the final solution during the operation of the algorithm; thirdly, the paths obtained as a result of the work of the algorithm satisfy the main required relation between them. Numerically, the algorithm was implemented by the dynamic programming method extended by means of an additional functional relationship, implying the presence of suboptimal policies.
Conclusions. The conducted runs of computational experiments confirmed the operability and efficiency of the software-implemented algorithm. The performed analysis demonstrated the good convergence characteristics of the proposed algorithm as compared with other algorithms of this class applied to network diagrams. On this basis, it can be recommended for practical use in project management information systems.
About the Author
M. A. Аnfyorov
MIREA – Russian Technological University
Russian Federation
Competing Interests:
Russian Federation
Mikhail A. Аnfyorov, Dr. Sci. (Eng.), Professor, Domain-Specific Information Systems Department, Institute of Cybersecurity and Digital Technologies
78, Vernadskogo pr., Moscow, 119454
Competing Interests:
The author declares no conflicts of interest
References
1. Hagstrom J.N. Computing the probability distribution of project duration in a PERT network. Networks. 1990; 20(2):231–244. https://doi.org/10.1002/net.3230200208
2. Kamburowski J., Michael D.J., Stallmann M.F.M. Minimizing the complexity of an activity network. Networks. 2000;36(1):47–52. https://doi.org/10.1002/1097-0037(200008)36:1%3C47::AID-NET5%3E3.0.CO;2-Q
3. Bianco L., Caramia M. A new formulation of the resource-unconstrained project scheduling problem with generalized precedence relations to minimize the completion time. Networks. 2010;56(4):263–271. https://doi.org/10.1002/net.20388
4. Brennan M. PERT and CPM: a selected bibliography. Monticello, Ill.: Council of Planning Librarians, 1968. 11 p.
5. Alagheband A., Soukhakian M.A. An efficient algorithm for calculating the exact overall time distribution function of a project with uncertain task durations. Indian Journal of Science and Technology. 2012;5(9):3310–3316. https://doi.org/10.17485/ijst/2012/v5i9.20
6. Damci A., Polat G., Akin F.D., et al. Use of float consumption rate in resource leveling of construction projects. Front. Eng. Manag. 2022;9:135–147. https://doi.org/10.1007/s42524-020-0118-0
7. Willis R.J. Critical path analysis and resource constrained project scheduling – Theory and practice. Eur. J. Oper. Res. 1985;21(2):149–155. https://doi.org/10.1016/0377-2217(85)90026-8
8. Bowers J.A. Criticality in resource constrained networks. J. Oper. Res. Soc. 1995;46(1):80–91. https://doi.org/10.1057/jors.1995.9
9. Shtub A. The trade-off between the net present cost of a project and the probability to complete it on schedule. J. Oper. Manag. 1986;6(3–4):461–470. https://doi.org/10.1016/0272-6963(86)90017-3
10. Shtub A. The integration of CPM and material management in project management. Constr. Manag. Econ. 1988;6(4):261–272. https://doi.org/10.1080/01446198800000023
11. Ananthanarayanan P.S. Project Technology and Management. In: S. Seetharaman (Ed.). Treatise on Process Metallurgy. V. 3. Industrial Processes. Elsevier; 2014. P. 1145–1191. https://doi.org/10.1016/B978-0-08-096988-6.00038-9
12. García-Heredia D., Molina E., Laguna M., et al. A solution method for the shared resource-constrained multi-shortest path problem. Expert Systems with Applications. 2021;182:115193. https://doi.org/10.1016/j.eswa.2021.115193
13. Fulkerson D.R. Expected critical path lengths in PERT networks: Oper. Res. 1962;10(6):745–912. https://doi.org/10.1287/opre.10.6.808
14. Bellman R. On a routing problem. Quart. Appl. Math. 1958;16(1):87–90. https://doi.org/10.1090/qam/102435
15. Stern R., Goldenberg M., Saffidine A., et al. Heuristic search for one-to-many shortest path queries. Ann. Math. Artif. Intell. 2021;89:1175–1214. https://doi.org/10.1007/s10472-021-09775-x
16. Dreyfus S.E. An appraisal of some shortest-path algorithms. Operations Research. 1969;17(3):395–412. https://doi.org/10.1287/opre.17.3.395
17. Clarke S., Krikorian A., Rausan J. Computing the N best loopless paths in a network. J. Soc. Indust. Appl. Math. 1963;11(4):1096–1102. https://doi.org/10.1137/0111081
18. Pollack M. Solutions of the kth best route through a network – A review. J. Math. Anal. Appl. 1961;3(3): 547–559. https://doi.org/10.1016/0022-247X(61)90076-2
19. Shier D.R. Iterative methods for determining the k shortest paths in a network. Networks. 1976;6(3):205–229. https://doi.org/10.1002/net.3230060303
20. Shier D.R. On algorithms for finding the k shortest paths in a network. Networks. 1979;9(3):195–214. https://doi.org/10.1002/net.3230090303
21. Minieka E., Shier D.R. A note on an algebra for the k best routes in a network. IMA J. Appl. Math. 1973;11(2): 145–149. https://doi.org/10.1093/imamat/11.2.145
22. Eppstein D. Finding the k shortest paths. SIAM J. Comput. 1999;28(2):652–673. https://doi.org/10.1137/S0097539795290477
23. Yen J.Y. Finding the K shortest loopless paths in a network. Manag. Sci. 1971;17(11–Theory Series):712–716. Available from URL: http://www.jstor.org/stable/2629312
24. Hershberger J., Maxel M., Suri S. Finding the k shortest simple paths: A new algorithm and its implementation. ACM Trans. Algor. 2007;3(4): Art. 45(19 p.) https://doi.org/10.1145/1290672.1290682
25. Chen B.Y., Chen X.-W., Chen H.-P., et al. A fast algorithm for finding K shortest paths using generalized spur path reuse technique. Transactions in GIS. 2021;25(1): 516–533. https://doi.org/10.1111/tgis.12699
26. Hu X.-B., Zhang C., Zhang G.-P., et al. Finding the k shortest paths by ripple-spreading algorithms. Eng. Appl. Artif. Intell. 2020;87:Art.103229. https://doi.org/10.1016/j.engappai.2019.08.023
27. Hamed A.Y. A genetic algorithm for finding the k shortest paths in a network. Egypt. Inform. J. 2010;11(2):75–79. https://doi.org/10.1016/j.eij.2010.10.004
28. Hu X.-B., Zhou J., Li H., et al. Finding the k shortest paths for co-evolutionary path optimization. In: IEEE Symposium Series on Computational Intelligence. November 18–21, 2018; Bangalore, India. P. 1906–1912. https://doi.org/10.1109/SSCI.2018.8628928
29. Liu G., Qiu Z., Chen W. An iterative algorithm for single-pair K shortest paths computation. WSEAS Transactions on Information Science and Applications. 2015;12(Art. 30):305–314. Available from URL: https://wseas.org/wseas/cms.action?id=10185
30. Guo J., Jia L. A new algorithm for finding the K shortest paths in a time-schedule network with constraints on arcs. J. Algorithms Comput. Technol. 2017;11(2):170–177. https://doi.org/10.1177/1748301816680470
31. Xu W., He S., Song R., et al. Finding the K shortest paths in a schedule-based transit network. Comput. Oper. Res. 2012;39(8):1812–1826. https://doi.org/10.1016/j.cor.2010.02.005
32. Jin W., Chen S., Jiang H. Finding the K shortest paths in a time-schedule network with constraints on arcs. Comput. Oper. Res. 2013;40(12):2975–2982. https://doi.org/10.1016/j.cor.2013.07.005
33. Kaufmann A., Debazeille G. La méthode du chemin critique. Paris: Dunod; 1964. 170 p.
34. Bellman R., Kalaba R. On kth best policies. J. Soc. Ind. Appl. Math. 1960;8(4)582–588. Available from URL: https://www.jstor.org/stable/2099049
35. Shier D.R. Computational Experience with an algorithm for finding the k shortest paths in a network. J. Res. Natl. Bureau Stand. 1974;78B(3)139–165. https://doi.org/10.6028/JRES.078B.020
Supplementary files
|
|
1. Comparative analysis of algorithms: z = 1600; 1 – Algorithm used in this work; 2 – Double sweep algorithm | |
| Subject | ||
| Type | Исследовательские инструменты | |
View
(38KB)
|
Indexing metadata ▾ | |
- An algorithm for finding k-shortest paths in contourless directed graphs having a strict order relation was developed.
- Abstract elements were defined according to group theory in graphs as p-contours, between which a multilevel structure of relations for implementing the necessary search of paths was then established.
- For substantiating the efficiency of the constructed algorithm, the validity of the main provisions was demonstrated as follows: firstly, the multilevel system of relations is exhaustive; secondly, there is no loss in the final solution during the operation of the algorithm; thirdly, the paths obtained as a result of the work of the algorithm satisfy the main required relation between them.
- Numerically, the algorithm was implemented by the dynamic programming method.
Review
For citations:
Аnfyorov M.A. Algorithm for finding subcritical paths on network diagrams. Russian Technological Journal. 2023;11(1):60-69. https://doi.org/10.32362/2500-316X-2023-11-1-60-69
Views:
595
Email this article 