Genetic Algorithm Applied to Problem Solving p-hub Multiple Unallocated Center
Abstract
This work addresses a variant of the p-hub Center (pHCP) problem, named the Unassigned Multi-Allocation Center p-Hub Problem (UMApHCP). The problem is to define p hubs in a complete graph so that the maximum transport cost of the graph is minimized. A Hybrid Genetic Algorithm (GA) is used to solve the problem addressed, with the initial population generated by the GRASP metaheuristic construction phase. In addition to each hub configuration generated by the GA, a polynomial-time algorithm is applied to determine the optimal allocation of the nodes of the graph. To evaluate the GA, 2 sets of instances with up to 300 nodes and 40 hubs available in the literature were used. Computational tests are performed in order to prove the efficiency of the proposal.
References
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.
