Artificial Immune Systems for Solving the Uncapacitated Single-Allocation p-Hub Median Problem

• Gabriel L. Nobrega UNB
• Vinicius J. Tasso UNB
• Allan G. Souza UNB
• Stephanie A. Fernandez UNB
• Daniel G. Silva UNB

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

Resumo

Optimization problems such as the Uncapacitated Single-Allocation p-Hub Median Problem represent good models for real network design issues, hence an increasing research interest has emerged. A good hub location reduces costs and improves the quality of delivered services on network-based systems. In this work, two artificial immune systems are employed in order to address the problem, where the numerical results indicate good quality of solutions.

Referências

Abdinnour-Helm, S. (1998). A hybrid heuristic for the uncapacitated hub location problem. European Journal of Operational Research, 106(2-3):489–499.

Chaves, A. A., de Assis Correa, F., and Lorena, L. A. N. (2007). Clustering search heuristic for the capacitated p-median problem. In Innovations in Hybrid Intelligent Systems, pages 136–143. Springer.

Chen, J.-F. (2007). A hybrid heuristic for the uncapacitated single allocation hub location problem. Omega, 35(2):211–220.

de Castro, L. N. and Von Zuben, F. J. (2002). Learning and Optimization Using the Clonal Selection Principle. IEEE Transactions on Evolutionary Computation, 6(3):239–251.

De França, F. O., Coelho, G. P., Castro, P. A. D., and Von Zuben, F. J. (2010). Conceptual and Practical Aspects of the aiNet Family of Algorithms. International Journal of Natural Computing Research, 1(1):1–35.

de Morais, V. W. C., Maravilha, A. L., de Assis, L. P., and Andrade, A. V. (2011). Abordagem Imunológica ao Problema de Roteamento de Veículos com Coleta e Entrega Simultâneas. In XLIII Simpósio Brasileiro de Pesquisa Operacional (SBPO), pages 1422–1433, Ubatuba-SP.

Dias, T. M., Attux, R., Romano, J. M. T., and Suyama, R. (2009). Blind Source Separation of Post-Nonlinear Mixtures Using Evolutionary Computation and Gaussianization. ICA 2009, LNCS 5441, 5441:235–242.

Díaz, J. A. and Fernandez, E. (2006). Hybrid scatter search and path relinking for the capacitated p-median problem. European Journal of Operational Research, 169(2):570–585.

Ernst, A. T. and Krishnamoorthy, M. (1998). Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem. European Journal of Operational Research, 104(1):100–112.

Ernst, A. T. and Krishnamoorthy, M. (1999). Solution algorithms for the capacitated single allocation hub location problem. Annals of Operations Research, 86:141–159.

Fernandez, S. A., Perez, A. A., de Armas, J., Silva, D. G., and Ferone, D. (2018). A twostage biased-randomized iterated local search for the uncapacitated single allocation p-hub median problem. Transactions on Emerging Telecommunications Technologies.

Lorena, L. A. and Pereira, M. A. (2002). A lagrangean/surrogate heuristic for the maximal covering location problem using hillman’s edition. International Journal of Industrial Engineering, 9:57–67.

Naeem, M. and Ombuki-Berman, B. (2010). An efficient genetic algorithm for the uncapacitated single allocation hub location problem. In Evolutionary Computation (CEC), 2010 IEEE Congress on, pages 1–8. IEEE.

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.

Pankratz, G. (2005). Dynamic vehicle routing by means of a genetic algorithm. International Journal of Physical Distribution & Logistics Management, 35(5):362–383.

Pizzolato, N. D., Barcelos, F. B., and Nogueira Lorena, L. A. (2004). School location methodology in urban areas of developing countries. International Transactions in Operational Research, 11(6):667–681.

Randall, M. (2008). Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation. Computational Optimization and Applications, 39(2):239–261.

Resende, M. G. C. and Pardalos, P. M. (2008). Handbook of optimization in telecommunications. Springer Science & Business Media.

Rosário, R., Carnieri, C., and Steiner, M. T. A. (2002). Proposta de solução para o problema das p-medianas na localização de unidades de saúde 24 horas. XXII ENEGEP.

Silva, D. G., Attux, R., Nadalin, E. Z., Duarte, L. T., and Suyama, R. (2011). An Immune- Inspired Information-Theoretic Approach to the Problem of ICA Over a Galois Field. In 2011 IEEE Information Theory Workshop, pages 618–622. IEEE.

Silva, D. G., Montalv˜ao, J., Attux, R., and Coradine, L. C. (2015). An immune-inspired, information-theoretic framework for blind inversion of Wiener systems. Signal Processing, 113:18–31.

Silva, D. G., Nadalin, E. Z., Coelho, G. P., Duarte, L. T., Suyama, R., Attux, R., Von Zuben,

F. J., and Montalv˜ao, J. (2014). A Michigan-like immune-inspired framework for performing independent component analysis over Galois fields of prime order. Signal Processing, 96:153–163.

Topcuoglu, H., Corut, F., Ermis, M., and Yilmaz, G. (2005). Solving the uncapacitated hub location problem using genetic algorithms. Computers & Operations Research, 32(4):967–984.

Wada, C., Consolaro, D. M., Ferrari, R., Suyama, R., Attux, R., and Von Zuben, F. J. (2009). Nonlinear Blind Source Deconvolution Using Recurrent Prediction-Error Filters and an Artificial Immune System. ICA 2009, LNCS 5441, 5441:371–378.