UM MODELO DE PROGRAMAÇÃO LINEAR INTEIRA MISTA PARA UM PROBLEMA DE LOCALIZAÇÃO DE HUBS COM COBERTURA MÁXIMA
DOI:
https://doi.org/10.56083/RCV3N3-020Keywords:
Programação Inteira, Localização de Hubs, Cobertura MáximaAbstract
No Problema da Cobertura Máxima p-Hub com Alocação r (r-PCMpH), duas decisões são tomadas: a localização de p hubs e a atribuição de cada ponto não hub a exatamente r hubs localizados (r≤p). Essas decisões geram um custo de serviço para cada par origem-destino (O/D) da rede. Após as decisões de localização e alocação, o fluxo de cada par O/D é dito estar coberto se o seu custo não ultrapassa um raio pré-estabelecido. Neste contexto, o objetivo do problema é tomar as decisões de localização e alocação de modo a maximizar a soma total dos fluxos cobertos. É apresentada uma nova formulação para o problema que utiliza um conjunto de desigualdades válidas propostas recentemente na literatura para um caso particular do r-PCMpH. É proposto que as desigualdades sejam geradas sob demanda, seguindo uma abordagem clássica de branch-and-cut. Para provar a robustez do método proposto, são apresentados vários experimentos computacionais que mostram que o mesmo supera a melhor formulação exata encontrada na literatura para todas as instâncias comparadas, sendo capaz de obter soluções ótimas de várias instâncias grandes pela primeira vez.
References
BUTTON, K., 2002. Debunking some common myths about airport hubs. Journal of Air Transport Management 8 (3), 177 – 188. DOI: https://doi.org/10.1016/S0969-6997(02)00002-9
CAMPBELL, J. F., 1994. Integer programming formulations of discrete hub location problems. European Journal of Operational Research 72 (2), 387–405. DOI: https://doi.org/10.1016/0377-2217(94)90318-2
CONTRERAS, I., O’KELLY, M., 2019. Hub location problems. In: Location science. Springer, pp. 327–363. DOI: https://doi.org/10.1007/978-3-030-32177-2_12
DOGLIO, P., ROBOREDO, M. C., e PESSOA, A. A. (2020). Um modelo de programação linear inteira mista para um problema de localização de hubs com cobertura máxima. In Anais do LII SBPO, João Pessoa-PB. SOBRAPO.
ERNST, A. T., HAMACHER, H., JIANG, H., KRISHNAMOORTHY, M., WOEGINGER, G., 2009. Uncapacitated single and multiple allocation p-hub center problems. Computers & Operations Research 36 (7), 2230–2241. DOI: https://doi.org/10.1016/j.cor.2008.08.021
ERNST, A. T., KRISHNAMOORTHY, M., 1996. Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location science 4 (3), 139–154. DOI: https://doi.org/10.1016/S0966-8349(96)00011-3
FARAHANI, R. Z., HEKMATFAR, M., ARABANI, A. B., NIKBAKHSH, E., 2013. Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering 64 (4), 1096–1109. DOI: https://doi.org/10.1016/j.cie.2013.01.012
HWANG, Y. H., LEE, Y. H., 2012. Uncapacitated single allocation p-hub maximal covering problem. Computers & Industrial Engineering 63 (2), 382–389. DOI: https://doi.org/10.1016/j.cie.2012.03.014
ISHFAQ, R., SOX, C. R., 2011. Hub location–allocation in intermodal logistic networks. European Journal of Operational Research 210 (2), 213 – 230. DOI: https://doi.org/10.1016/j.ejor.2010.09.017
JANKOVIĆ, O., MIŠKOVIĆ, S., STANIMIROVIĆ, Z., TODOSIJEVIĆ, R., Dec. 2017. Novel formulations and VNS-based heuristics for single and multiple allocation p-hub maximal covering problems. Annals of Operations Research 259 (1-2), 191–216. DOI: https://doi.org/10.1007/s10479-017-2508-1
JANKOVIĆ, O., STANIMIROVIĆ, Z., Apr. 2017. A general variable neighborhood search for solving the uncapacitated r -allocation p -hub maximal covering problem. Electronic Notes in Discrete Mathematics 58, 23–30. DOI: https://doi.org/10.1016/j.endm.2017.03.004
KIM, H., O’KELLY, M. E., 2009. Reliable p-hub location problems in telecommunication networks. Geographical Analysis 41 (3), 283–306. DOI: https://doi.org/10.1111/j.1538-4632.2009.00755.x
O’KELLY, M. E., 1986. A quadratic integer program for the location of interacting hub facilities. European journal of operational research 32 (3), 393–404. DOI: https://doi.org/10.1016/S0377-2217(87)80007-3
PEKER, M., KARA, B. Y., 2015. The p-hub maximal covering problem and extensions for gradual decay functions. Omega 54, 158–172. DOI: https://doi.org/10.1016/j.omega.2015.01.009
QU, B., WENG, K., 2009. Path relinking approach for multiple allocation hub maximal covering problem. Computers & Mathematics with Applications 57 (11), 1890–1894. DOI: https://doi.org/10.1016/j.camwa.2008.10.004
SILVA, M. R., CUNHA, C. B., Nov. 2017. A tabu search heuristic for the uncapacitated single allocation p -hub maximal covering problem. European Journal of Operational Research 262 (3), 954–965. DOI: https://doi.org/10.1016/j.ejor.2017.03.066
STANČIĆ, O., STANIMIROVIĆ, Z., TODOSIJEVIĆ, R., MIŠKOVIĆ, S., 2022. Mathematical formulations and solution methods for the uncapacitated r-allocation p-hub maximal covering problem. Discrete Optimization 43, 100672. DOI: https://doi.org/10.1016/j.disopt.2021.100672
WENG, K., Yang, C., MA, Y., 2006. Two artificial intelligence heuristics in solving multiple allocation hub maximal covering problem. In: International Conference on Intelligent Computing. Springer, pp. 737–744. DOI: https://doi.org/10.1007/11816157_90
