Let's Connect
Follow Us
Watch Us
(+385) 1 2380 262
journal.prometfpz.unizg.hr
Promet - Traffic&Transportation journal

Accelerating Discoveries in Traffic Science

Accelerating Discoveries in Traffic Science

Sign In or Register Submit

PDF
PUBLISHED
27.08.2024
DOI
https://doi.org/10.7307/ptt.v36i4.577
ISSUE
2024 (Vol 36), Issue 4
LICENSE
Copyright (c) 2024 Snežana MLADENOVIĆ, Ivana STEFANOVIĆ, Slađana JANKOVIĆ, Ana UZELAC, Goran MARKOVIĆ, Stefan ZDRAVKOVIĆ
Creative Commons 4.0 logo
This work is licensed under a
Creative Commons Attribution-NonCommercial-
NoDerivatives 4.0 International License.

Cost Optimisation Tool for Multicommodity Network Flow Problem in Telecommunications

Authors:Snežana MLADENOVIĆ, Ivana STEFANOVIĆ, Slađana JANKOVIĆ, Ana UZELAC, Goran MARKOVIĆ, Stefan ZDRAVKOVIĆ

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.

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

References

  1. [1] 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.
  2. [2] Pioro M, Medhi D. Routing, flow, and capacity design in communication and computer networks. San Francisco, USA: Elsevier Inc; 2004.
  3. [3] Medhi D, Ramasamy K. Network routing algorithms, protocols, and architectures. San Francisco, USA: Elsevier Inc; 2007.
  4. [4] Resende M, Pardalos P. Handbook of optimization in telecommunications. Boston, MA, US: Springer; 2006.
  5. [5] 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.
  6. [6] 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.
  7. [7] 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.
  8. [8] 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.
  9. [9] 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.
  10. [10] 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.
  11. [11] 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.
  12. [12] 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.
  13. [13] 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.
  14. [14] 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.
  15. [15] 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.
  16. [16] 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.
  17. [17] 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].
  18. [18] Sifaleras A. Minimum cost network flow: Problems, algorithms, and software. Yugoslav Journal of Operation Research. 2013;23(1):3-17. DOI: 10.2298/YJOR121120001S.
  19. [19] 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.
  20. [20] Mladenović S, et al. Heuristic based real-time train rescheduling system. Networks. 2016;67(1):32-48. DOI: 10.1002/net.21625.
  21. [21] 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.
  22. [22] 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.
  23. [23] 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.
  24. [24] 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.
  25. [25] 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.
  26. [26] 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.
  27. [27] 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.
  28. [28] 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.
Show more

SPECIAL ISSUE CALL

Innovation and New Technologies in Transport and Logistics

Guest Editor: Eleonora Papadimitriou, PhD

Editors: Dario Babić, PhD; Marko Matulin, PhD; Marko Ševrović, PhD.

RECENT PAPERS

Browse through the selection of our recent research
A Review of Expert Systems Integration in Signal Plan OptimisationEstimating Vehicle Turn-In Rate of Expressway Rest Areas via ETC Gantry Data – An ADPC-GMM ApproachFactors Influencing Sustained Use of Shared E-Scooter Services in Urban TaiwanVehicle Trajectory Prediction Based on GAT and LSTM Networks in Urban Environments

Accelerating Discoveries in Traffic Science |
2024 © Promet - Traffic&Transportation journal