Algoritmo Genético Aplicado à Solução do Problema p-hub Centro Não Capacitado de Múltiplas Alocações

• Jardell da Silva CEFET-MG
• Flavio Martins CEFET-MG
• Maria Silva CEFET-MG
• Sérgio de Souza CEFET-MG

DOI: https://doi.org/10.5753/eniac.2019.9340

Resumo

Este trabalho estuda a solução de uma variante do problema p-Hub Centro (pHCP), denominada problema p-Hub Centro não capacitado de múltipla alocação (UMApHCP), usando algoritmo genético híbrido. O problema consiste em definir p hubs em um grafo completo, de forma que o custo máximo de transporte do grafo seja minimizado. Para a geração da população inicial, usa-se a fase de construção da metaheurística GRASP. Além disso, para cada configuração de hub gerada pelo AG, um algoritmo de tempo polinomial é aplicado para determinar a alocação ótima dos nós do grafo. Para avaliar esta implementação, utilizou-se de 2 conjuntos de instâncias, disponíveis na literatura, com até 300 nós e até 40 hubs. Testes computacionais são realizados para comprovar a eficiência da proposta.

Palavras-chave: Otimização, UMApHCP, Metaheurística, Algoritmo Genético

Referências

Brimberg, J., Mladenović, N., Todosijević, R., and Urošević, D. (2017a). A basic variable neighborhood search heuristic for the uncapacitated multiple allocation p-hub center problem. Optimization Letters, 11:313–327.

Brimberg, J., Mladenović, N., Todosijević, R., and Urošević, D. (2017b). General vble neighborhood search for the uncapacitated single allocation p-hub center problem. Optimization Letters, 11:377.

Campbell, A. M., Lowe, T. J., and Zhang, L. (2007). The p-hub center allocation problem. European Journal of Operational Research, 176(2):819–835.

Campbell, J. F. (1994). Integer programming formulations of discrete hub location problems. European Journal of Operational Research, 72(2):387 – 405.

Farahani, R. Z., Hekmatfar, M., Arabani, A. B., and Nikbakhsh, E. (2013). Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering, 64:1096–1109.

Feo, T. A. and Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 9:849–859.

Kara, B. Y. and Tansel, B. c. (2000). On the single-assignment p-hub center problem. European Journal of Operational Research, 125(3):648–655.

Meyer, T., Ernst, A. T., and Krishnamoorthy, M. (2009). A 2-phase algorithm for solving the single allocation p-hub center problem. Computers and Operations Research, 36(12):3143 – 3151.

O’kelly, M. E. (1987). A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research, 32(3):393 – 404.