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

Autores

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

Palavras-chave:

Pesquisa Operacional. Projeto de Redes. Expansão de Capacidade. Congestionamento. Instalação de Links.

Resumo

Uma área da Pesquisa Operacional bastante estudada é o problema de projeto de redes. Alguns problemas impactam diretamente nas redes, diminuindo sua qualidade de serviço, como o congestionamento, sendo o principal problema abordado neste trabalho. Dessa forma, objetiva-se desenvolver um algoritmo capaz de tratar o problema de projetos de rede sob efeito de congestionamento. A formulação matemática do problema foi elaborada, abrangendo a expansão de capacidade, onde a quantidade de commodities enviada nos links é expandida bem como a instalação de novos links; em seguida, foi desenvolvido o algoritmo. Na realização de testes foram utilizadas as instâncias de Nugent, os resultados obtidos foram apresentados, e, para melhor compreensão dos mesmos, foi representada graficamente a instância de 15 nós. Finalmente, conclui-se que o algoritmo foi capaz de modificar a rede de acordo com a expansão de capacidade nos links, e, tratar o congestionamento, melhorando a qualidade de serviço das redes.

Downloads

Não há dados estatísticos.

Biografia do Autor

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.

Referências

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