Path Through Specified Nodes and Links in a Network

Authors

  • Santosh Kumar OAM Department of Mathematical and Geospatial Sciences, School of Sciences, RMIT University, Melbourne, Australia
  • Elias Munapo School of Economics and Decision Sciences, North West University, Mafikeng Campus, Mafikeng, South Africa
  • Philimon Nyamugure Department of Statistics and Operations Research, National University of Science and Technology, Box AC 939, Ascot, Bulawayo, Zimbabwe
  • Trust Tawanda Department of Statistics and Operations Research, National University of Science and Technology, Box AC 939, Ascot, Bulawayo, Zimbabwe

DOI:

https://doi.org/10.13052/jgeu0975-1416.1225

Keywords:

Specified nodes, specified links, specified elements, conditional spanning network, index restricted network

Abstract

A constrained shortest route problem in graph theory is about determination of a shortest path between two given nodes of the network that also visits a given set of specified nodes or a set of specified links before arriving to the destination. These earlier approaches did not consider specified elements containing both nodes and links of the given network. This paper finds a shortest path joining the origin node to the destination node, which is constrained to pass through a set of ‘K’ specified elements of the given network, where K1 number of elements represent nodes, 0<K1<K, and K2 number of elements represent links, where K1+K2=K. Alternatively, if the specified elements representing nodes are contained in the set Sn and the remaining elements representing links by the set Sl, and the set of specified elements denoted by the set Se, then Se={Sn ∪ Sl}. Such restricted path will also have real-life applications. Depending upon the configuration of the specified elements, these constrained paths may have loops. The approach discussed in this paper is a heuristic approach, which finds the required constrained path in a real time.

Downloads

Download data is not yet available.

Author Biographies

Santosh Kumar OAM, Department of Mathematical and Geospatial Sciences, School of Sciences, RMIT University, Melbourne, Australia

Santosh Kumar OAM received PhD degree in Operations Research from Delhi University. He is author and co-author of over 210 papers and 4 books in the field of Operations Research. His contributions in the field of OR have been recognized in the form of ‘Ren Pots’ award from the Australian Society for operations Research (ASOR) in 2009 and a recognition award from the South African OR Society as a non-member of the society and a non-resident of South Africa in 2011. He was the President of the Asia Pacific Operations Research societies (1995–97), where ASOR was a member along with 7 other countries in the region. He is currently an Honorary Professor at RMIT University, Melbourne. He is a Fellow of the Institute of Mathematics and its Applications, UK. On 14th June 2021, he was awarded a medal of the Order of Australia (OAM).

Elias Munapo, School of Economics and Decision Sciences, North West University, Mafikeng Campus, Mafikeng, South Africa

Elias Munapo holds a BSc. (Hons) Applied Mathematics (1997), MSc. Operations Research (2002) and a PhD Operations Research (2010), all from the National University of science and Technology (N.U.S.T.), Zimbabwe. A certificate in outcomes-based assessment in Higher Education and Open distance learning, University of South Africa (UNISA), certificate in University Education Induction Program, University of KwaZulu-Natal (UKZN). He is a Professional Natural Scientist certified by the South African Council for Natural Scientific Professions (SACNASP), 2012; and NRF rated in South Africa. He has published/co-published over 120 articles and two books. He has also edited/co-edited 7 books and is a guest editor of Applied Sciences, Algorithms and Next Energy journals which are under MDPI. He has supervised/co-supervised eleven doctoral students and over 30 students at Master level. He is a member of the Operations Research Society of South Africa, Executive Committee Member 2012–13, South African Council for Natural Scientific Professions (SACNASP) as a Certified Natural Scientist, European Conference on Operational Research (EURO) and the International Federation of Operations Research Societies (IFORS), and a member of the International Conference on Optimization (ICO) and is part of the team preparing to host ICO 2026 at Johannesburg.

Philimon Nyamugure, Department of Statistics and Operations Research, National University of Science and Technology, Box AC 939, Ascot, Bulawayo, Zimbabwe

Philimon Nyamugure has a BSc (Hons) 1998, MSc – 2002; Post Graduate Diploma in Higher Education, 2013, all from NUST; PhD in Statistics, University of Limpopo, 2017. He joined NUST in 2003 and was Chairperson for the Departments of Applied Mathematics (2009–2013) and Chairman, Department of Statistics and Operations Research (2013–2019). Became Executive Dean of the Faculty of Applied Science from 2020 to date. A University Senator from 2009 and Councillor from 2020 up to date. He received an award for the best PhD presenter in the School of Mathematical and Computer Sciences, University of Limpopo. Best Senior presenter, Faculty of Applied Sciences, and in 2017 Fulbright Research Award for African Scholars. Involved in several community engagement programs including National University of Science and Technology Schools Enrichment Program (NUSTSEP). He is currently an Executive Dean and a Professor at NUST.

Trust Tawanda, Department of Statistics and Operations Research, National University of Science and Technology, Box AC 939, Ascot, Bulawayo, Zimbabwe

Trust Tawanda is a seasoned academic and researcher with a strong background in Operations Research and Statistics. He holds a Bachelor of Science (Hons) in Operations Research and Statistics (2013), a Master of Science in Operations Research and Statistics (2017), and a PhD in Operations Research (2024) from the National University of Science and Technology (NUST) in Zimbabwe. Currently, he is pursuing a Post Graduate Diploma in Higher and Tertiary Education (PGDHTE) at Great Zimbabwe University (GZU). As a Senior Lecturer in the Department of Statistics and Operations Research at NUST’s Faculty of Applied Sciences, he teaches and conducts research in his areas of expertise, which include network optimization problems, transportation problems, travelling salesman problems, and assignment problems. He has a notable publication record, with papers and book chapters to his credit. His academic journey and research endeavors demonstrate his commitment to advancing knowledge in Operations Research.

References

S. Zhang, Z. Luo, L. Yang, F. Teng, and L. Tianrui, A survey of route recommendations: Methods, applications, and opportunities, Information Fusion Volume 108, August 2024, 102413, Elsevier, https:/doi.org/10.1016/j.inffus.2024.102413.

S. Sohrabi, Y. Weng, S. Das, S. Paal, Safe route-finding: A review of literature and future directions, Accident Analysis & Prevention, Vol. 177, 2022, 106816, https:/doi.org/10.1016/j.aap.2022.106816.

H. Joksch, The shortest route problem with constraints, Journal of Mathematical Analysis and Applications, 1966, DOI:10.1016/0022-247X(66)90020-5.

R.K. Ahuja, K. Mehlhorn, J.B. Orlin, and R.E. Tarjan, Faster algorithms for the shortest path problem, Journal of the Association of Computing Machinery, Vol. 37, 1990, pp. 213–223.

R.E. Bellman, Dynamic programming treatment of travelling salesman problems, J of ACM, Vol. 9, 1962, pp. 61–63.

R.E. Beckwith, Dynamic programming and network routing: An introduction to the technique of functional equations, Dynamic programming workshop, Boulder, Colorado, 1961.

G.B. Dantzig, Discrete variable extremum problems, Opns. Res. Vol. 5, pp. 266–76, 1957.

E.J. Dijkstra, A note on two problems in connection with graphs, Numerische Mathematik. 1: 269–271, 1959. doi:10.1007/BF01386390.S2CID123284777.

R.C. Garg, and S. Kumar, Shortest connected graph through dynamic programming, Maths Magazine, Vol. 41, No. 4, pp. 170–73, 1968.

R.M. Peart, R.M. Randolf, and T.E. Bartlet, The shortest route problem, Opns. Res., Vol. 8, pp. 866–868, 1960.

M. Pollack, and W. Weibenson, Solution of the shortest route problem – A review, Opns. Res., Vol. 8, pp. 224–230, 1960.

K. Mehlhorn, P. Sanders, Chapter 10: Shortest Paths, Algorithms and Data Structures: The Basic Toolbox. Springer. Doi:10.1007/978-3-540-77978-0, ISBN 978-3=540-77977-3, 2008.

R. Kalaba, On some communicating network routing problems, Combinatorial Analysis, Proc. Symposium Appl. Math., 10, 1960.

J.P. Saksena, and S. Kumar, The routing problem with ‘K’ specified nodes, Opns. Res., Vol. 14, No. 5, pp. 909–913, 1966.

S.M. Sinha, and C.P. Bajaj, The maximum capacity route through a set of specified nodes, Cahiers du Centre d’Etudes de Recherche Operationnelle, Vol. 11, pp. 133–138, 1969.

S.M. Sinha, and C.P. Bajaj, The maximum capacity route through a set of specified nodes, Opsearch, Vol. 7, pp. 96–114, 1970.

S. Kumar, S., and H. Arora, K shortest paths and paths through R-specified edges in a protean network, ASOR Bulletin, Vol. 14, No. 2, pp. 3–8, 1995.

H. Arora, and S. Kumar, Path through k-specified edges in a liner graph, Opsearch, Vol. 30, No. 2, pp. 163–73, 1993.

J.B. Kruskal, On the shortest spanning tree of a graph and the travelling salesman problem, Proc. Amer. Math. Soc., 7, pp. 48–50, 1956.

E. Munapo, S. Kumar, M. Lesaona, and P. Nyamugure, A minimum spanning tree with node index

=2, ASOR Bulletion, Vol. 34, Issue 1, pp. 1–14, 2016. (www.asor.org.au)

S. Kumar, E. Munapo, M. Leasoana, and P. Nyamugure, Is the travelling salesman problem actually NP Hard?, Chapter 3 in Engineering and Technology, Recent Innovations and Research, Editor Ashok Mathani, International Research Publication House, ISBN 798-93-86138-06-4, pp. 37–58, 2016.

S. Kumar, E. Munapo, C. Sigauke, M. Al-Rabeeah, The minimum spanning tree with index

=2 is equivalent to the minimum travelling salesman tour, Chapter 8, Mathematics in Engineering Sciences: Novel Theories, Technologies and Applications, ISBN 9781351266321, Editor, Mange Ram, CRC Press (http:/www.crcpress.com) pp. 227–243, 2019.

S. Kumar, E. Munapo, M. Lesaona, and P. Nyamugure, A minimum spanning tree approximation to the routing problem thorough ‘K’ specified nodes, Journal of Economics, Vol. 5, No. 3, pp. 307–312, 2014.

S. Kumar, E. Munapo, P. Nyamugure, T. Tawanda, Minimum spanning tree approach to path through K specified links, Journal of Graphic Era University, Vol. 11, 2, 2023, pp. 221–238.

E. Munapo, B.C. Jones, and S. Kumar, A minimum incoming weight label method and its application to CPM network, ORiON, Vol. 24, South African Journal of OR 2008.

S. Kumar, E. Munapo, O. Ncube, C. Saguke, and P. Nyamugure, A minimum weight labelling method for determination of a shortest route in a non-directed network, Int J Syst. Assur. Eng. Manag. DOI 10.1007/s13198-012-0140-7, Springer, ISSN 0975-6809, Vol. 4, No. 1, pp. 13–18, 2013.

F.B. Zhan, Three fastest shortest path algorithms on real road networks: Data structures and procedures, Journal of the Geographic Information and Decision Analysis, Vol. 1, No. 1, pp. 70–82, 1997.

E. Munapo, and S. Kumar, Linear Integer programming: Theory, Applications, Recent Developments, De Gruyter Publication, ISBN 978-3-11-070292-7, 2022.

C. Zhang, An extended Benders decomposition method for unique shortest path problem, Opsearch, Vol. 61, No. 3, pp. 989–1012, 2024.

S. Kumar, E. Munapo, Innovative ways of developing and using specific purpose alternatives for solving hard combinatorial network routing problems, Applied Math, Vol. 4, pp. 791–805, 2024. https:/doi.org/10.3390/appliedmath4020042.

Downloads

Published

2024-09-23

How to Cite

Kumar OAM, S., Munapo, E., Nyamugure, P., & Tawanda, T. (2024). Path Through Specified Nodes and Links in a Network. Journal of Graphic Era University, 12(02), 263–282. https://doi.org/10.13052/jgeu0975-1416.1225

Issue

2024: Vol 12 Iss 2

Section

Articles

Most read articles by the same author(s)