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

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

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 e a instalação de novos links; sendo, em seguida, desenvolvido o algoritmo. Na realização de testes neste artigo 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.

Palavras-chave

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

Texto completo:

PDF

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

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

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

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

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

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

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

Direitos autorais 2021 Exacta