Development of an algorithm for capacity expansion on a network design problem under congestion effects
DOI:
https://doi.org/10.5585/exactaep.2021.19783Keywords:
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
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. 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
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Autores
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Autores que tiverem artigos aceitos para publicação na Revista Exacta concordam com os seguintes termos:
- A Cessão dos Direitos Autorais da publicação do artigo à Revista Exacta;
- Os autores que tiverem seus trabalhos aceitos e publicados na Revista Exacta estão sujeitos a Política de Direitos Autorais CC BY NC SA https://creativecommons.org/licenses/by-nc-sa/4.0/;
- A publicação do artigo pela Revista Exacta, em caráter de exclusividade e em meio eletrônico;
- A indexação do artigo em bases de dados nacionais e internacionais, diretórios, bibliotecas digitais e bases bibliométricas em que a Revista estiver e vir a estar indexada.
