A multi-objective genetic algorithm for a bi-objective facility location problem with partial coverage. (English) Zbl 1338.90373
Summary: In this study, we present a bi-objective facility location model that considers both partial coverage and service to uncovered demands. Due to limited number of facilities to be opened, some of the demand nodes may not be within full or partial coverage distance of a facility. However, a demand node that is not within the coverage distance of a facility should get service from the nearest facility within the shortest possible time. In this model, it is assumed that demand nodes within the predefined distance of opened facilities are fully covered, and after that distance the coverage level decreases linearly. The objectives are defined as the maximization of full and partial coverage, and the minimization of the maximum distance between uncovered demand nodes and their nearest facilities. We develop a new multi-objective genetic algorithm (MOGA) called modified SPEA-II (mSPEA-II). In this method, the fitness function of SPEA-II is modified and the crowding distance of NSGA-II is used. The performance of mSPEA-II is tested on randomly generated problems of different sizes. The results are compared with the solutions of the most well-known MOGAs, NSGA-II and SPEA-II. Computational experiments show that mSPEA-II outperforms both NSGA-II and SPEA-II.
MSC:
| 90C29 | Multi-objective and goal programming |
| 90B80 | Discrete location and assignment |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
multi-objective genetic algorithm; facility location; maximal coverage; partial coverage; P-centerReferences:
| [1] | Alberto I, Mateo PM (2011) A crossover operator that uses Pareto optimality in its definition. TOP 19(1):67-92 · Zbl 1225.90113 · doi:10.1007/s11750-009-0082-7 |
| [2] | Alcaraz J, Landete M, Monge JF (2012) Design and analysis of hybrid metaheuristics for the reliability p-median problem. Eur J Oper Res 222(1):54-64 · Zbl 1253.90130 · doi:10.1016/j.ejor.2012.04.016 |
| [3] | Araz C, Selim H, Ozkarahan I (2007) A fuzzy multi-objective covering-based vehicle location model for emergency services. Comput Oper Res 34:705-726 · Zbl 1120.90352 · doi:10.1016/j.cor.2005.03.021 |
| [4] | Aytug H, Khouja M, Vergara FE (2003) Use of genetic algorithms to solve production and operations management problems: a review. Int J Prod Res 41(17):3955-4009 · doi:10.1080/00207540310001626319 |
| [5] | Badri MA, Mortagy AK, Alsayed CA (1998) A multi-objective model for locating fire stations. Eur J Oper Res 110:243-260 · Zbl 0948.90094 · doi:10.1016/S0377-2217(97)00247-6 |
| [6] | Berman O, Krass D, Drezner Z (2003) The gradual covering decay location problem on a network. Eur J Oper Res 151:474-480 · Zbl 1053.90076 · doi:10.1016/S0377-2217(02)00604-5 |
| [7] | Berman O, Drezner Z, Krass D (2010) Generalized coverage: new developments in covering location models. Comput Oper Res 37:1675-1687 · Zbl 1188.90147 · doi:10.1016/j.cor.2009.11.003 |
| [8] | Bhattacharya R, Bandyopadhyay S (2010) Solving conflicting bi-objective facility location problem by NSGA-II evolutionary algorithm. Int J Adv Manuf Technol 51:397-414 · doi:10.1007/s00170-010-2622-6 |
| [9] | Bosman PAN, Thiernes D (2003) The balance between proximity and diversity in multi-objective evolutionary algorithms. IEEE Trans Evolut Comput 7(2):174-188 · doi:10.1109/TEVC.2003.810761 |
| [10] | Brooke A, Kendrick D, Meeraus A (1992) GAMS: a user’s guide, release 2.25. The Scientific Press, South San Francisco · Zbl 1261.90011 |
| [11] | Church R, ReVelle C (1974) The maximal covering location problem. Pap Reg Scie Assoc 32:101-118 · doi:10.1007/BF01942293 |
| [12] | Church R, Current J, Storbeck J (1991) A bicriterion maximal covering location formulation which considers the satisfaction of uncovered demand. Dec Sci 22(1):38-52 · doi:10.1111/j.1540-5915.1991.tb01260.x |
| [13] | Coello Coello C, Lamont GB, van Veldhuizen DA (2007) Evolutionary algorithms for solving multi-objective problems. Springer, Berlin · Zbl 1142.90029 |
| [14] | Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, New York · Zbl 0970.90091 |
| [15] | Deb K, Pratap A, Agarwal S (2002) A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evolut Comput 6(2):182-197 · doi:10.1109/4235.996017 |
| [16] | Durillo JJ, Nebro AJ, Luna F, Alba E (2009) On the effect of the steady-state selection scheme in multi-objective genetic algorithms. In: Ehrgott M, Fonseca CM, Gandibleux X, Hao JK, Sevaux M (eds) Evolutionary multi-criteria optimization: 5th international conference. Springer, Nantes, pp 184-195 |
| [17] | Eskandari H, Geiger CD, Lamont GB (2007) FastPGA: a dynamic problem sizing approach for solving expensive multiobjective optimization problems. In: Obayashi S, Deb K, Poloni C, Hiroyasu T, Murata T (eds) Proceedings of evolutionary multi-criterion optimization (EMO 2007), Lecture notes in computer science, vol 4403. Springer, Berlin, pp 141-155 · Zbl 1163.90598 |
| [18] | Farahani RZ, SteadieSeifi M, Asgari N (2010) Multiple criteria facility location problems: a survey. Appl Math Modell 34:1689-1709 · Zbl 1193.90143 · doi:10.1016/j.apm.2009.10.005 |
| [19] | Fazel Zarandi MH, Dvari S, Haddad Sisakht SA (2011) The large scale maximal covering location problem. Sci Iran 18(6):1564-1570 · doi:10.1016/j.scient.2011.11.008 |
| [20] | Ghosh A, Dehuri S (2004) Evolutionary algorithms for multi-criterion optimization: a survey. Int J Comput Inf Sci 2(1):38-57 |
| [21] | Goldberg JB (2004) Operations research models for the deployment of emergency services vehicles. EMS Manag J 1:20-39 |
| [22] | Gutjahr WJ, Doerner KF, Nolz PC (2009) Multi-criteria location planning for public facilities in tsunami-prone coastal areas. OR Spect 31:651-678 · Zbl 1163.90598 · doi:10.1007/s00291-008-0126-7 |
| [23] | Haimes YY, Ladson LS, Wismer DA (1971) Bicriterion formulation of problems of integrated system identification and system optimization. IEEE Trans Syst Man Cybern 1(3):296-297 · Zbl 0224.93016 · doi:10.1109/TSMC.1971.4308298 |
| [24] | Hogan K, Revelle C (1986) Concepts and applications of backup coverage. Manag Sci 32(11):1434-1444 · doi:10.1287/mnsc.32.11.1434 |
| [25] | Hosage CM, Goodchild MF (1986) Discrete space location-allocation solutions from genetic algorithms. Ann Oper Res 6:35-46 · doi:10.1007/BF02027381 |
| [26] | Iris C, Asan SS (2012) A review of genetic algorithm applications in supply chain network design. In: Kahraman C (ed) Computational intelligence systems in industrial engineering—with recent theory and applications. Atlantic Press, Paris, pp 203-228 · Zbl 1193.90143 |
| [27] | Ishibuchi H, Tsukamoto N, Nojima Y (2008) Evolutionary many-objective optimization: a short review. In: Proceedings of 2008 IEEE congress on evolutionary computation. Hong Kong, pp 2424-2431 |
| [28] | Jaramillo JH, Bhadury J, Batta R (2002) On the use of genetic algorithms to solve location problems. Comput Oper Res 29:761-779 · Zbl 0995.90060 · doi:10.1016/S0305-0548(01)00021-1 |
| [29] | Karasakal O, Karasakal E (2004) A maximal covering location model in the presence of partial coverage. Comput Oper Res 31:1515-1526 · Zbl 1107.90028 · doi:10.1016/S0305-0548(03)00105-9 |
| [30] | Konak A, Coit D, Smith A (2006) Multi-objective optimization using genetic algorithms: a tutorial. Reliab Eng Syst Saf 91:992-1007 · doi:10.1016/j.ress.2005.11.018 |
| [31] | Li X, Yeh AG (2004) Integration of genetic algorithms and GIS for optimal location search. Int J Geograph Inf Sci 19(5):581-601 · doi:10.1080/13658810500032388 |
| [32] | Li X, Zhoa Z, Zhu X, Wyatt T (2011) Covering models and optimization techniques for emergency response facility location and planning: a review. Math Methods Oper Res 74:281-310 · Zbl 1261.90011 · doi:10.1007/s00186-011-0363-4 |
| [33] | Mahdavie I, Shiripour S, Amiri-Aref M, Otagshara MM, Amiri NM (2012) Multi-facility location problems in the presence of a probabilistic line barrier: a mixed integer quadratic programming model. Int J Prod Res 50(15):3988-4008 · doi:10.1080/00207543.2011.579639 |
| [34] | Medaglia AL, Villegas JG, Rodríguez-Coca DM (2009) Hybrid biobjective evolutionary algorithms for the design of a hospital waste management network. J Heurist 15:153-176 · Zbl 1176.90662 · doi:10.1007/s10732-008-9070-6 |
| [35] | Megiddo N, Zemel E, Hakimi SL (1983) The maximum coverage location problem. SIAM J Algebr Discret Methods 4(2):253-261 · Zbl 0514.90019 · doi:10.1137/0604028 |
| [36] | Michalewicz Z (1996) Genetic algorithms \[+\]+ data structures \[== evolution\] programs. Springer, Berlin · Zbl 0841.68047 · doi:10.1007/978-3-662-03315-9 |
| [37] | Mingjun J, Tang H, Guo J (2004) A single-point mutation evolutionary programming. Inf Process Lett 30(6):293-299 · Zbl 1176.90442 |
| [38] | Mladenovic N, Brimberg J, Hansen P, Moreno-Perez JA (2007) The p-median problem: a survey of metaheuristic approaches. Eur J Oper Res 179:927-939 · Zbl 1163.90610 · doi:10.1016/j.ejor.2005.05.034 |
| [39] | Pohl AJ, Lamonth GB (2008) Multi-objevtive UAV mission planning using evolutionary computation. In: Mason SJ, Hill RR, Monch L, Rose O, Jefferson T, Fowler JW (eds) Proceedings of the 2008 winter simulation conference. WSC, Florida USA, pp 1268-1279 · Zbl 1253.90130 |
| [40] | ReVelle C, Scholssberg M, Williams J (2008) Solving the maximal covering location problem with heuristic concentration. Comput Oper Res 35(2):427-435 · Zbl 1141.90472 · doi:10.1016/j.cor.2006.03.007 |
| [41] | Schilling D, Jayaraman V, Barkhi R (1993) A review of covering problems in facility location. Locat Sci 1:25-55 · Zbl 0923.90108 |
| [42] | Storbeck JE, Vohra R (1988) A simple trade-off model for maximal and multiple coverage. Geograph Anal 20(3):220-230 · doi:10.1111/j.1538-4632.1988.tb00177.x |
| [43] | Villegas JG, Palacios F, Medaglia AL (2006) Solution methods for the bi-objective (cost-coverage) unconstrained facility location problem with an illustrative example. Ann Oper Res 147:109-141 · Zbl 1183.90293 · doi:10.1007/s10479-006-0061-4 |
| [44] | Yang L, Jones BF, Yang S (2007) A fuzzy multi-objective programming for optimization of fire station locations through genetic algorithms. Eur J Oper Res 181:903-905 · Zbl 1131.90409 · doi:10.1016/j.ejor.2006.07.003 |
| [45] | Yigit V, Aydin ME, Turkbey O (2006) Solving large-scale uncapacitated facility location problems with evolutionary simulated annealing. Int J Prod Res 44(22):4773-4791 · Zbl 1114.90430 · doi:10.1080/00207540600621003 |
| [46] | Zhou A, Qu BY, Li H, Zhao SZ, Suganthan PN, Zhang Q (2011) Mutiobjective evolutionary algorithms: a survey of the state of the art. Swarm Evolut Comput 1:32-49 · doi:10.1016/j.swevo.2011.03.001 |
| [47] | Zitzler E, Thiele L (1998) Multi-objective optimization using evolutionary algorithms—a comparative case study. In: Eiben AE, Back T, Schoenauer M, Schwefel HP (eds) Proceedings of the fifth international conference on parallel problem solving from nature, Lecture notes in computer science, vol 1498. Springer, Amsterdam, pp 292-301 · Zbl 0923.90108 |
| [48] | Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength pareto evolutionary algorithm. In: Technical report 103. Computer engineering and networks laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland · Zbl 1141.90472 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
