An efficient genetic algorithm for the Uncapacitated r-allocation p-hub maximal covering problem
DOI:
https://doi.org/10.2298/YJOR170120011JKeywords:
p-Hub maximal covering problem, binary coverage, heuristic, genetic algorithmAbstract
This paper deals with the Uncapacitated r-allocation p-hub Maximal Covering Problem (UrApHMCP) with a binary coverage criterion. This problem consists of choosing p hub locations from a set of nodes so as to maximize the total demand covered under the r-allocation strategy. The general assumption is that the transportation between the nonhub nodes is possible only via hub nodes, while each non-hub node is assigned to at most r hubs. An integer linear programming formulation of the UrApHMCP is presented and tested within the framework of a commercial CPLEX solver. In order to solve the problem on large scale hub instances that cannot be handled by the CPLEX, a Genetic Algorithm (GA) is proposed. The results of computational experiments on standard p-hub benchmark instances with up to 200 nodes demonstrate efficiency and effectiveness of the proposed GA method.References
Abdinnour-Helm, S., and Venkataramanan, M.A., ”Solution approaches to hub location problems”, Annals of Operations Research, 78 (1998) 31-50.
Alumur, S., and Kara, B., ”A Hub Covering Network Design Problem for Cargo Applications in Turkey”, Journal of Operational Research Society, 60 (10) (2009) 1349-1359.
Alumur, S., and Kara, B., ”Network hub location problems: The state of the art”, European Journal of Operational Research, 190 (1) (2008) 1-21.
Beasley, D., Bull, D., and Martin, R., ”An overview of genetic algorithms: Part 1. Fundamentals”, University Computing, 15 (1993) 58-58.
Beasley, D., Bull, D., and Martin, R., ”An overview of genetic algorithms: Part 2, research topics”, University Computing, 15 (4) (1993) 170-181.
Brimberg, J., Mladenović, N., Todosijević, R., and Urošević, D., ”A basic variable neighborhood search heuristic for the uncapacitated multiple allocation p-hub center problem”, Optimization Letters, (2015) 1-15.
Campbell, J.F., ”Integer programming formulations of discrete hub location problems”, European Journal of Operational Research, 72 (2) (1994) 387-405.
Church, R., and ReVelle, C., ”The maximal covering location problem”, Papers in Regional Science, 32 (1) (1974) 101-118.
Eremeev, A.V., and Kovalenko, J.V., ”Optimal recombination in genetic algorithms for combinatorial optimization problems-Part I”, Yugoslav Journal of Operations Research, 24 (1) (2014) 1-20.
Eremeev, A.V., and Kovalenko, J.V., ”Optimal recombination in genetic algorithms for combinatorial optimization problems-Part II”, Yugoslav Journal of Operations Research, 24 (2) (2014) 165-186.
Ernst, A.T., Jiang, H., Krishnamoorthy, M., and Baatar, H., ”Reformulations and computational results for uncapacitated single and multiple allocation hub covering problems”, Working Paper Series, 1 (2011) 1-18.
Ernst, A.T., and Krishnamoorthy, M., ”Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem”, European Journal of Operational Research, 104 (1) (1998) 100-112.
Filipović, V., ”Fine-grained tournament selection operator in genetic algorithms”, Computing and Informatics, 22 (2) (2012) 143-161.
Goldberg, D.E., Genetic algorithms in search, optimization and machine learning, Addison-Wesley, 1989.
Goldberg, D.E., and Holland, J.H., ”Genetic algorithms and machine learning”, Machine Learning, 3 (2) (1988) 95-99.
Holland, J.H., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, The University of Michigan Press, Ann Arbor, 1975.
Hwang, Y.H., and Lee, Y.H., ”Uncapacitated single allocation p-hub maximal covering problem”, Computers & Industrial Engineering, 63 (2) (2012) 382-389.
Kara, B., and Tansel, B., ”The single-assignment hub covering problem: Models and linearizations”, Journal of the Operational Research Society, 51 (1) (2003) 59-64.
Kratica, J., Stanimirović, Z., Tošić, D., and Filipović, V., ”Two Genetic Algorithms for Solving the Uncapacitated Single Allocation p-Hub Median Problem”, European Journal of Operational Research, 182 (2007) 15-28.
Marić, M., Stanimirović, Z., and Stanojević, P., ”An efficient memetic algorithm for the uncapacitated single allocation hub location problem”, Soft Computing, 17 (3) (2013) 445-466.
Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer, Berlin, Heidelberg, 1996.
O’Kelly, M.E., ”A quadratic integer program for the location of interacting hub facilities”, European Journal of Operational Research, 32 (3) (1987) 393-404.
Peiró, J., Corberán, Á., and Martí, R., ”GRASP for the uncapacitated r-allocation p-hub median problem”, Computers & Operations Research, 43 (2014) 50-60.
Peker, M., and Kara, B.Y., ”The p-hub maximal covering problem and extensions for gradual decay functions”, Omega, 54 (2015) 158–172.
Stanimirović, Z., ”A genetic algorithm approach for the capacitated single allocation p-hub median problem”, Computing and Informatics, 29 (1) (2010) 117-132.
Stanojević, P., Marić, M., and Stanimirović, Z., ”A hybridization of an evolutionary algorithm and a parallel branch and bound for solving the capacitated single allocation hub location problem”, Applied Soft Computing, 33 (2015) 24-36.
Topcuoglu, H., Corut, F., Ermiş, M., and Yilmaz, G., ”Solving the uncapacitated hub location problem using genetic algorithms”, Computers & Operations Research, 32 (4) (2005) 967-984.
Wagner, B., ”Model formulations for hub covering problems”, Journal of the Operational Research Society, 59 (7) (2008) 932-938.
Weng, K., Yang, C., and Ma, Y., ”Two artificial intelligence heuristics in solving multiple allocation hub maximal covering problem”, In Intelligent Computing, Springer, Berlin, Heidelberg, 2006.
Yaman, H., ”Allocation strategies in hub networks”, European Journal of Operational Research, 211 (3) (2011) 442-451.
Downloads
Published
Issue
Section
License
Copyright (c) 2018 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
