Desenvolvimento de um algoritmo para a expansão de capacidade do problema de projeto de redes sob efeito de congestionamento

Túlio Bitencourt de Freitas; Karolliny Danielle Santos; Edwaldo Soares Rodrigues

doi:10.5585/exactaep.2021.19783

Authors

Túlio Bitencourt de Freitas Universidade do Estado de Minas Gerais (UEMG) https://orcid.org/0000-0002-1713-1096
Karolliny Danielle Santos Universidade do Estado de Minas Gerais (UEMG) https://orcid.org/0000-0003-4537-2919
Edwaldo Soares Rodrigues Universidade do Estado de Minas Gerais (UEMG) https://orcid.org/0000-0002-1546-5500

DOI:

https://doi.org/10.5585/exactaep.2021.19783

Keywords:

Operational Research. Network Design. Capacity Expansion. Congestion. Link Installation.

Abstract

A field of Operational Research heavily studied is the network design problem. Some problems affect the networks directly, decreasing your quality of service, like congestion, which is the main problem approached in this paper. In this way, the objective is to develop an algorithm capable of dealing with network design problem under congestion effects. The mathematical formulation of the problem was elaborated, approaching capacity expansion, which expands the quantity of commodities sent on the expanded link and the installation of new links: then, the algorithm was developed. The tests conducted in this paper were based on Nugent instances, the results obtained were presented, and, for better understanding, the 15 nodes instance was graphically represented. Finally, the algorithm developed was capable of modifying the network according to the link capacity expansion, and, treat the congestion effect, improving the network quality of service.

Downloads

Download data is not yet available.

Author Biographies

Túlio Bitencourt de Freitas, Universidade do Estado de Minas Gerais (UEMG)

Graduando de Bacharelado em Engenharia de Computação na Universidade do Estado de Minas Gerais – UEMG. Divinópolis, Minas Gerais, Brasil. tulio.1692492@discente.uemg.br

Karolliny Danielle Santos, Universidade do Estado de Minas Gerais (UEMG)

Doutorado em Engenharia de Produção pela Universidade Federal de Minas Gerais - UFMG. Professora designada da Universidade do Estado de Minas Gerais - UEMG. Divinópolis, Minas Gerais, Brasil.

Edwaldo Soares Rodrigues, Universidade do Estado de Minas Gerais (UEMG)

Mestre em Ciência da Computação pela Universidade Federal de Ouro Preto - UFOP. Professor designado na Universidade do Estado de Minas Gerais - UEMG. Divinópolis, Minas Gerais, Brasil.

References

Atamturk, A., & Gunluk, O. (2017). On Capacity Models for Network Design. arXiv preprint arXiv:1711.10147. doi:https://doi.org/10.1287/trsc.18.1.1

Baskan, O. (2014). Harmony search algorithm for continuous network design problem with link capacity expansions. KSCE Journal of Civil Engineering, 18(1), 273-283. doi:https://doi.org/10.1007/s12205-013-0122-6

Belieres, S., Hewitt, M., & Jozefowiez, N. &. (2021). Meta partial benders decomposition for the logistics service network design problem. European Journal of Operational Research. doi:https://doi.org/10.1016/j.ejor.2021.07.056

Bharath-Kumar, K., & Jaffe, J. (1983). Routing to multiple destinations in computer networks. IEEE Transactions on communications, 31(3), pp. 343-351. doi:10.1109/TCOM.1983.1095818

Conceição, L., & Correia, G. H. (2020). The reversible lane network design problem (RL-NDP) for smart cities with automated traffic. Sustainability, 12(3), 1226. doi:https://doi.org/10.3390/su12031226

Contreras, I. F. (2009). Tight bounds from a path based formulation for the tree of hub location problem. Computers & Operations Research, 36(12), 3117-3127.

Contreras, I., Fernández, E., & Marín, A. (2009). Tight bounds from a path based formulation for the tree of hub location problem. Computers & Operations Research, 36(12), 3117-3127. doi:https://doi.org/10.1016/j.cor.2008.12.009

Contreras, I., Fernández, E., & Marín, A. (2010). The tree of hubs location problem. European Journal of Operational Research, 202(2), 390-400. doi:https://doi.org/10.1016/j.ejor.2009.05.044

Cordeau, J. F., Pasin, F., & Solomon, M. M. (2006). An integrated model for logistics network design. Annals of operations research, 144, pp. 59-82. doi:https://doi.org/10.1007/s10479-006-0001-3

Dantzig, G. B. (1962). Linear Programming and Extensions. Princeton University Press. doi:https://doi.org/10.1515/9781400884179

Fathollahi-Fard, A. M., Hajiaghaei-Keshteli, M., & Mirjalili, S. (2018). Hybrid optimizers to solve a tri-level programming model for a tire closed-loop supply chain network design problem. Applied Soft Computing, 70, 701-722. doi:https://doi.org/10.1016/j.asoc.2018.06.021

Fathollahi-Fard, A. M., Hajiaghaei-Keshteli, M., & Tian, G. &. (2020). An adaptive Lagrangian relaxation-based algorithm for a coordinated water supply and wastewater collection network design problem. Information Sciences, 512, 1335-1359. doi:https://doi.org/10.1016/j.ins.2019.10.062

Fontaine, P., Crainic, T. G., Gendreau, M., & & Minner, S. (2020). Population-based risk equilibration for the multimode hazmat transport network design problem. European Journal of Operational Research, 284(1), 188-200. doi:https://doi.org/10.1016/j.ejor.2019.12.028

Garuba, F., Goerigk, M., & Jacko, P. (2009). Robust network capacity expansion with non-linear costs. doi:10.4230/OASIcs.ATMOS.2019.

Hatefi, S. M., Moshashaee, S. M., & Mahdavi, I. (2019). A bi-objective programming model for reliable supply chain network design under facility disruption. International Journal of Integrated Engineering, 11(6), 80-92. doi:https://doi.org/10.30880/ijie.2019.11.06.009

Hellsten, E. O., & Sacramento, D. &. (2021). A Branch-And-Price Algorithm for Solving The Single-Hub Feeder Network Design Problem. European Journal of Operational Research. doi:https://doi.org/10.1016/j.ejor.2021.08.046

Janatyan, N., Zandieh, M., & Alem-Tabriz, A. &. (2021). A robust optimization model for sustainable pharmaceutical distribution network design: a case study. Annals of Operations Research, 1-20. doi:https://doi.org/10.1007/s10479-020-03900-5

Koza, D. F., & Desaulniers, G. &. (2020). Integrated liner shipping network design and scheduling. Transportation Science, 54(2), pp. 512-533. doi:https://doi.org/10.1287/trsc.2018.0888

Leblanc, L. J. (1975). An algorithm for the discrete network design problem. Transportation Science, 9(3), 183-199. doi:https://doi.org/10.1287/trsc.9.3.183

Liang, Y., Lu, M., & Shen, Z. J. (2021). Data Center Network Design for Internet‐Related Services and Cloud Computing. Production and Operations Management. doi:https://doi.org/10.1016/j.ejor.2021.08.046

Nagurney, A. (2002). network Economics: an introduction. Isenberg School of Management, University of Massachusetts.

Nagurney, A., & Qiang, Q. (2007). A network efficiency measure for congested networks. EPL (Europhysics Letters), 79(3), 38005.

Nikoo, N., Babaei, M., & Mohaymany, A. S. (2018). Emergency transportation network design problem: Identification and evaluation of disaster response routes. International journal of disaster risk reduction, 27, 7-20. doi:https://doi.org/10.1016/j.ijdrr.2017.07.003

Nugent, C. E., Vollmann, T. E., & Ruml, J. (1968). An experimental comparison of techniques for the assignment of facilities to locations. Operations research, 16(1), 150-173. doi:https://doi.org/10.1287/opre.16.1.150

Ordóñez, F., & Zhao, J. (2007). Robust capacity expansion of network flows. Networks: An International Journal, 50(2), 136-145. doi:doi.org/10.1002/net.20183

Ouorou, A., Luna, H. P., & Mahey, P. (2001). Multicommodity network expansion under elastic demands. Optimization and Engineering, 2(3), 277-292. doi:https://doi.org/10.1023/A:1015314432240

Ramírez-Rosado, I. J., & Domínguez-Navarro, J. A. (2006). New multiobjective tabu search algorithm for fuzzy optimal planning of power distribution systems. (Vol. 21(1)). IEEE Transactions on Power systems. doi:10.1109/TPWRS.2005.860946

ramírez-Rosado, I. J.-N. (2006). New multiobjective tabu search algorithm for fuzzy optimal planning of power distribution systems. (Vol. 21(1)). IEEE Transactions on Power systems.

Randazzo, C. D., & Luna, H. P. (2001). A comparison of optimal methods for local access uncapacitated network design. Annals of Operations Research, 106(1), 263-286. doi:https://doi.org/10.1023/A:1014569927266

Santos, K. D., de Miranda Júnior, G., & de Camargo, R. S. (2016). APROXIMAÇÃO EXTERNA/DECOMPOSIÇÃO DE BENDERS PARA PROJETO DE REDES SOB CONGESTIONAMENTO VIA λ-ÓTIMO. doi:10.5151/marine-spolm2015-140578

Schumacher, K. M., Li‐Yang Chen, R., Cohn, A. E., & Castaing, J. (2016). Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support. Naval Research Logistics (NRL), 63(3), 236-246. doi:https://doi.org/10.1002/nav.21685

Yang, H., & Bell, M. G. (1998). A capacity paradox in network design and how to avoid it. Transportation Research Part A: Policy and Practice, 32(7), 539-545. doi:https://doi.org/10.1016/S0965-8564(98)00017-2

Yildiz, H., Yoon, J., Talluri, S., & Ho, W. (2016). Reliable supply chain network design. Decision Sciences, 47(4), 661-698. doi:https://doi.org/10.1111/deci.12160

Yu, H., Sun, X., Solvang, W. D., & Laporte, G. &. (2020). A stochastic network design problem for hazardous waste management. Journal of cleaner production, 277,123566. doi:https://doi.org/10.1016/j.jclepro.2020.123566