×

zbMATH — the first resource for mathematics

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
Software:
FastPGA; SPEA2; GAMS; Genocop
PDF BibTeX Cite
Full Text: DOI
References:
[1] Alberto, I; Mateo, PM, A crossover operator that uses Pareto optimality in its definition, TOP, 19, 67-92, (2011) · Zbl 1225.90113
[2] Alcaraz, J; Landete, M; Monge, JF, Design and analysis of hybrid metaheuristics for the reliability p-Median problem, Eur J Oper Res, 222, 54-64, (2012) · Zbl 1253.90130
[3] Araz, C; Selim, H; Ozkarahan, I, A fuzzy multi-objective covering-based vehicle location model for emergency services, Comput Oper Res, 34, 705-726, (2007) · Zbl 1120.90352
[4] Aytug, H; Khouja, M; Vergara, FE, Use of genetic algorithms to solve production and operations management problems: a review, Int J Prod Res, 41, 3955-4009, (2003)
[5] Badri, MA; Mortagy, AK; Alsayed, CA, A multi-objective model for locating fire stations, Eur J Oper Res, 110, 243-260, (1998) · Zbl 0948.90094
[6] Berman, O; Krass, D; Drezner, Z, The gradual covering decay location problem on a network, Eur J Oper Res, 151, 474-480, (2003) · Zbl 1053.90076
[7] Berman, O; Drezner, Z; Krass, D, Generalized coverage: new developments in covering location models, Comput Oper Res, 37, 1675-1687, (2010) · Zbl 1188.90147
[8] Bhattacharya, R; Bandyopadhyay, S, Solving conflicting bi-objective facility location problem by NSGA-II evolutionary algorithm, Int J Adv Manuf Technol, 51, 397-414, (2010)
[9] Bosman, PAN; Thiernes, D, The balance between proximity and diversity in multi-objective evolutionary algorithms, IEEE Trans Evolut Comput, 7, 174-188, (2003)
[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, The maximal covering location problem, Pap Reg Scie Assoc, 32, 101-118, (1974)
[12] Church, R; Current, J; Storbeck, J, A bicriterion maximal covering location formulation which considers the satisfaction of uncovered demand, Dec Sci, 22, 38-52, (1991)
[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, A fast and elitist multi-objective genetic algorithm: NSGA-II, IEEE Trans Evolut Comput, 6, 182-197, (2002)
[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, Multiple criteria facility location problems: a survey, Appl Math Modell, 34, 1689-1709, (2010) · Zbl 1193.90143
[19] Fazel Zarandi, MH; Dvari, S; Haddad Sisakht, SA, The large scale maximal covering location problem, Sci Iran, 18, 1564-1570, (2011)
[20] Ghosh, A; Dehuri, S, Evolutionary algorithms for multi-criterion optimization: a survey, Int J Comput Inf Sci, 2, 38-57, (2004)
[21] Goldberg, JB, Operations research models for the deployment of emergency services vehicles, EMS Manag J, 1, 20-39, (2004)
[22] Gutjahr, WJ; Doerner, KF; Nolz, PC, Multi-criteria location planning for public facilities in tsunami-prone coastal areas, OR Spect, 31, 651-678, (2009) · Zbl 1163.90598
[23] Haimes, YY; Ladson, LS; Wismer, DA, Bicriterion formulation of problems of integrated system identification and system optimization, IEEE Trans Syst Man Cybern, 1, 296-297, (1971) · Zbl 0224.93016
[24] Hogan, K; Revelle, C, Concepts and applications of backup coverage, Manag Sci, 32, 1434-1444, (1986)
[25] Hosage, CM; Goodchild, MF, Discrete space location-allocation solutions from genetic algorithms, Ann Oper Res, 6, 35-46, (1986)
[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, On the use of genetic algorithms to solve location problems, Comput Oper Res, 29, 761-779, (2002) · Zbl 0995.90060
[29] Karasakal, O; Karasakal, E, A maximal covering location model in the presence of partial coverage, Comput Oper Res, 31, 1515-1526, (2004) · Zbl 1107.90028
[30] Konak, A; Coit, D; Smith, A, Multi-objective optimization using genetic algorithms: a tutorial, Reliab Eng Syst Saf, 91, 992-1007, (2006)
[31] Li, X; Yeh, AG, Integration of genetic algorithms and GIS for optimal location search, Int J Geograph Inf Sci, 19, 581-601, (2004)
[32] Li, X; Zhoa, Z; Zhu, X; Wyatt, T, Covering models and optimization techniques for emergency response facility location and planning: a review, Math Methods Oper Res, 74, 281-310, (2011) · Zbl 1261.90011
[33] Mahdavie, I; Shiripour, S; Amiri-Aref, M; Otagshara, MM; Amiri, NM, Multi-facility location problems in the presence of a probabilistic line barrier: a mixed integer quadratic programming model, Int J Prod Res, 50, 3988-4008, (2012)
[34] Medaglia, AL; Villegas, JG; Rodríguez-Coca, DM, Hybrid biobjective evolutionary algorithms for the design of a hospital waste management network, J Heurist, 15, 153-176, (2009) · Zbl 1176.90662
[35] Megiddo, N; Zemel, E; Hakimi, SL, The maximum coverage location problem, SIAM J Algebr Discret Methods, 4, 253-261, (1983) · Zbl 0514.90019
[36] Michalewicz Z (1996) Genetic algorithms \(+\) data structures \(=\) evolution programs. Springer, Berlin · Zbl 0841.68047
[37] Mingjun, J; Tang, H; Guo, J, A single-point mutation evolutionary programming, Inf Process Lett, 30, 293-299, (2004) · Zbl 1176.90442
[38] Mladenovic, N; Brimberg, J; Hansen, P; Moreno-Perez, JA, The p-Median problem: a survey of metaheuristic approaches, Eur J Oper Res, 179, 927-939, (2007) · Zbl 1163.90610
[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, Solving the maximal covering location problem with heuristic concentration, Comput Oper Res, 35, 427-435, (2008) · Zbl 1141.90472
[41] Schilling, D; Jayaraman, V; Barkhi, R, A review of covering problems in facility location, Locat Sci, 1, 25-55, (1993) · Zbl 0923.90108
[42] Storbeck, JE; Vohra, R, A simple trade-off model for maximal and multiple coverage, Geograph Anal, 20, 220-230, (1988)
[43] Villegas, JG; Palacios, F; Medaglia, AL, Solution methods for the bi-objective (cost-coverage) unconstrained facility location problem with an illustrative example, Ann Oper Res, 147, 109-141, (2006) · Zbl 1183.90293
[44] Yang, L; Jones, BF; Yang, S, A fuzzy multi-objective programming for optimization of fire station locations through genetic algorithms, Eur J Oper Res, 181, 903-905, (2007) · Zbl 1131.90409
[45] Yigit, V; Aydin, ME; Turkbey, O, Solving large-scale uncapacitated facility location problems with evolutionary simulated annealing, Int J Prod Res, 44, 4773-4791, (2006) · Zbl 1114.90430
[46] Zhou, A; Qu, BY; Li, H; Zhao, SZ; Suganthan, PN; Zhang, Q, Mutiobjective evolutionary algorithms: a survey of the state of the art, Swarm Evolut Comput, 1, 32-49, (2011)
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.