Cost Optimisation Tool for Multicommodity Network Flow Problem in Telecommunications

Authors

  • Snežana MLADENOVIĆ University of Belgrade, Faculty of Transport and Traffic Engineering
  • Ivana STEFANOVIĆ Academy of Technical and Art Applied Studies, School of Electrical and Computer Engineering https://orcid.org/0000-0002-8025-8970
  • Slađana JANKOVIĆ University of Belgrade, Faculty of Transport and Traffic Engineering
  • Ana UZELAC University of Belgrade, Faculty of Transport and Traffic Engineering
  • Goran MARKOVIĆ University of Belgrade, Faculty of Transport and Traffic Engineering
  • Stefan ZDRAVKOVIĆ University of Belgrade, Faculty of Transport and Traffic Engineering

DOI:

https://doi.org/10.7307/ptt.v36i4.577

Keywords:

data transmission cost optimisation, capacity of telecommunication links, network flow, link failure, declarative programming

Abstract

In this paper, we consider the problem of minimising the cost of data transmission as a function of the capacity of telecommunication links. To solve this problem, we first formulated a mathematical model, and then we designed and developed a software that enables the optimisation of the given or randomly generated telecommunications network. Declarative programming is a good choice for optimisation problems because it is enough to specify only the relations that must be satisfied, without giving any effective procedure for finding the values for the decision variables. To test the application, we developed a software that randomly generates a telecommunications network that meets the given requirements. This enables us to test the application on an arbitrary number of different telecommunication networks with different numbers of nodes and links, and analyse the impact of changing network parameters on the flow and results of the optimisation. As telecommunications networks operate in conditions of uncertainty, the subject of special analysis was the potential failure of some of the network links. The paper presents and thoroughly analyses the optimisation results for several selected networks, as well as summary results for a number of telecommunications networks.

Author Biographies

Snežana MLADENOVIĆ, University of Belgrade, Faculty of Transport and Traffic Engineering

Dr Snežana Mladenović is a full professor of the scientific field of computer science at the University of Belgrade – The Faculty of transport and traffic engineering. Professor Mladenović uses her many years of experience in the field of application of information technologies in traffic, transport, logistics, and telecommunications. Her narrowest area of research is optimization (algorithms, applications, techniques, methods).

Scientific interests: optimization (algorithms, applications, techniques, methods, languages) data management, relational and non-relational databases.

Ivana STEFANOVIĆ, Academy of Technical and Art Applied Studies, School of Electrical and Computer Engineering

MSc Ivana Stefanović works as a teaching assistant at the Academy of Technical and Art Applied Studies, School of Electrical and Computer Engineering, in the scientific field of electronics and telecommunications. Ivana Stefanović has over ten years of expertise teaching telecommunications networks and traffic. As a Ph.D. student, her primary research interest is in telecommunication network optimization using various methodologies, algorithms, and machine learning.

Scientific interests: telecommunications, networks, optimization and machine learning.

Slađana JANKOVIĆ, University of Belgrade, Faculty of Transport and Traffic Engineering

Dr Slađana Janković is a full professor of the scientific field of computer science at the University of Belgrade – The Faculty of transport and traffic engineering. Professor Janković uses more than 20 years of experience in the field of application of information technologies in traffic, transport, logistics, and telecommunications. Her narrowest area of research are: object oriented programming, databases, Big Data technologies and Big Data analytics.

Scientific interests: machine learning, data management, relational and non-relational databases, object oriented programming, information systems development, cloud computing.

Ana UZELAC, University of Belgrade, Faculty of Transport and Traffic Engineering

Dr. Ana Uzelac, an esteemed Assistant Professor in Computer Science at the University of Belgrade’s Faculty of Transport and Traffic Engineering, leverages extensive experience in information technologies across traffic, transport, logistics, and telecom sectors. Her expertise focuses on data science, particularly its innovative applications within the traffic domain. Dr. Uzelac is renowned for integrating cutting-edge research with practical solutions to advance the field.

Scientific interests. application of data science in traffic systems, particularly integrating information technologies with traffic, transport, logistics, and telecommunications to develop innovative, data-driven solutions.

Goran MARKOVIĆ, University of Belgrade, Faculty of Transport and Traffic Engineering

Goran Marković, Ph.D. is a full professor at the University of Belgrade – Faculty of Transport and Traffic Engineering (FTTE). He received his B.Sc. (in 1996), M.Sc. (in 2002) and Ph.D. (in 2007) degrees from the University of Belgrade, all in telecommunication traffic and networks engineering. Since 1996, he has been employed at the University of Belgrade - FTTE, where he is currently the head of Department for Telecommunication Traffic and Networks.

Scientific interests: telecommunication networks design and optimization, tele-traffic engineering, optical networking, application of advanced communication technologies in intelligent transportation and traffic systems (ITS).

Stefan ZDRAVKOVIĆ, University of Belgrade, Faculty of Transport and Traffic Engineering

Dr Stefan Zdravković is an associate professor in the scientific field of computer science at the University of Belgrade – The Faculty of Transport and Traffic Engineering. As a teacher, he is always motivated to introduce students to programming innovatively and creatively while developing an engineering approach to solving problems. He has published over 30 scientific papers at national and international conferences and several papers in international journals.

Scientific interests: object-oriented programming, mobile programming, machine learning, and databases.

References

Oki E. Linear programming and algorithms for communication networks: A practical guide to network design, control, and management. Broken Sound Parkway NW, USA: Taylor & Francis Group; 2013.

Pioro M, Medhi D. Routing, flow, and capacity design in communication and computer networks. San Francisco, USA: Elsevier Inc; 2004.

Medhi D, Ramasamy K. Network routing algorithms, protocols, and architectures. San Francisco, USA: Elsevier Inc; 2007.

Resende M, Pardalos P. Handbook of optimization in telecommunications. Boston, MA, US: Springer; 2006.

Salimifard K, Bigharaz S. The multicommodity network flow problem: State of the art classification, applications, and solution methods. Operational Research. 2022;22:1-47. DOI: 10.1007/s12351-020-00564-8.

Eriskin L. A Lagrangean relaxation-based solution approach for multicommodity network design problem with capacity violations. Journal of Naval Sciences and Engineering. 2021;17(2):241-263. https://dergipark.org.tr/en/pub/jnse/issue/65720/932377.

Tsai K, et al. Multi-commodity flow routing for large-scale leo satellite networks using deep reinforcement learning. Proceedings of the IEEE Wireless Communications and Networking Conference 2022, 10–13 April 2022, Austin, TX, USA. 2022. p. 626-631. DOI: 10.1109/WCNC51071.2022.9771734.

Max-Onakpoya E, Baker CE. Assessing a synergistic use of alternate broadband delivery models in rural areas. Proceedings of the IEEE International Conference on Pervasive Computing and Communications Workshops and other Affiliated Events (PerCom Workshops) 2022, 21-25 March 2022, Pisa, Italy. 2022. p. 5-8. DOI: 10.1109/PerComWorkshops53856.2022.9767252.

Kovács P. Minimum-cost flow algorithms: An experimental evaluation. Optimization Methods and Software. 2015;30(1):94-127. DOI: 10.1080/10556788.2014.895828.

Chaturvedi A, et al. Improved throughput for all-or-nothing multicommodity flows with arbitrary demands. ACM SIGMETRICS Performance Evaluation Review. 2021;49(3):22-27. DOI: 10.1145/3529113.3529121.

Dilpriya TAH, Lanel GHJ, Vidanage BVNC. A strategy to strengthen and enhance the telecommunication network in Sri Lanka by using concepts of graph theory and linear programming models. International Journal of Natural Sciences Research. 2022;10(1):1-20. DOI: 10.18488/63.v10i1.2913.

Antić M. Optimization of non-blocking packet networks using the practical routing protocol with load balancing. PhD Thesis. University of Belgrade, School of Electrical Engineering; 2014.

Khezri S, Khodayifar S. Joint chance-constrained multi-objective multi-commodity minimum cost network flow problem with copula theory. Computers & Operations Research. 2023;156(106260). DOI:10.1016/j.cor.2023.106260.

Xu L, Haddad Vanier S. Branch-and-price for energy optimization in multi-hop wireless networks. Networks. 2022;80(1):123-148. DOI: 10.1002/net.22083.

Fowler S, Li Y, Pollastro A, Napoli S. Simple network design and power allocation for 5g device-to-device communication. Proceedings of the IEEE 19th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), 1-3 Dec. 2014, Athens, Greece. 2014. p. 203-207. DOI:10.1109/CAMAD.2014.7033235.

Raayatpanah MA, et al. Design of survivable wireless backhaul networks with reliability considerations. Computers & Operations Research. 2023;151(106120). DOI: 10.1016/j.cor.2022.106120.

IBM. IBM ILOG CPLEX Optimization studio CPLEX user’s manual. 2017;12(8). https://perso.ensta-paris.fr/~diam/ro/online/cplex/cplex1271_pdfs/usrcplex.pdf [Accessed 28th November 2022].

Sifaleras A. Minimum cost network flow: Problems, algorithms, and software. Yugoslav Journal of Operation Research. 2013;23(1):3-17. DOI: 10.2298/YJOR121120001S.

Eshtehadi R, Demir E, Huang Y. Solving the vehicle routing problem with multi-compartment vehicles for city logistics. Computers & Operations Research. 2020;115(104859). DOI: 10.1016/j.cor.2019.104859.

Mladenović S, et al. Heuristic based real-time train rescheduling system. Networks. 2016;67(1):32-48. DOI: 10.1002/net.21625.

Tran VM, Vu THN. Leveraging CPLEX to solve the vehicle routing problem with time windows. Proceedings of the 13th International Conference on Knowledge and Systems Engineering (KSE), 10-12 Nov. 2021, Bangkok, Thailand. 2021. p. 1-6. DOI: 10.1109/KSE53942.2021.9648591.

Guo Y, Shahraki AA. Selection of rail station locations on an intercity route regarding maximum users’ economic profits. Promet – Traffic&Transportation. 2023;35(4):595-606. DOI: 10.7307/ptt.v35i4.241.

Bugarčić P, Jevtić N, Malnar M. Reinforcement learning-based routing protocols in vehicular and flying ad hoc networks–a literature survey. Promet – Traffic&Transportation. 2022;34(6):893-906. DOI: 10.7307/ptt.v34i6.4159.

Aktaş S, Alemdar H, Ergüt S. Towards 5G and beyond radio link diagnosis: Radio link failure prediction by using historical weather, link parameters. Computers and Electrical Engineering. 2022;99(107742). DOI: 10.1016/j.compeleceng.2022.107742.

Patel S, Pathak H. A mathematical framework for link failure time estimation in MANETs. Engineering Science and Technology, an International Journal. 2022;25(100984). DOI: 10.1016/j.jestch.2021.04.003.

Moshiri M, Safaei F, Samei Z. A novel recovery strategy based on link prediction and hyperbolic geometry of complex networks. Journal of Complex Networks. 2021;9(4):cnab007. DOI: 10.1093/comnet/cnab007.

Bakhshi Kiadehi K, Rahmani AM, Sabbagh Molahosseini A. A fault-tolerant architecture for internet-of-things based on software-defined networks. Telecommunication Systems. 2021;77:155-169. DOI:10.1007/s11235-020-00750-1.

Lagos C, at al. Combining tabu search and genetic algorithms to solve the capacitated multicommodity network flow problem. Studies in Informatics and Control. 2014;23(3):265-276. DOI: 10.24846/v23i3y201405.

Downloads

Published

27-08-2024

How to Cite

MLADENOVIĆ, S., STEFANOVIĆ, I., JANKOVIĆ, S., UZELAC, A., MARKOVIĆ, G., & ZDRAVKOVIĆ, S. (2024). Cost Optimisation Tool for Multicommodity Network Flow Problem in Telecommunications. Promet - Traffic&Transportation, 36(4), 608–622. https://doi.org/10.7307/ptt.v36i4.577

Issue

Vol. 36 No. 4 (2024)

Section

Articles

License

Copyright (c) 2024 Snežana MLADENOVIĆ, Ivana STEFANOVIĆ, Slađana JANKOVIĆ, Ana UZELAC, Goran MARKOVIĆ, Stefan ZDRAVKOVIĆ

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Most read articles by the same author(s)