An evolutionary approach for obnoxious cooperative maximum covering location problem

被引:4
作者
Chappidi, Edukondalu [1 ]
Singh, Alok [1 ]
机构
[1] Univ Hyderabad, Sch Comp & Informat Sci, Hyderabad 500046, Telangana, India
关键词
Genetic algorithms; Obnoxious facilities; Location covering problems; Obnoxious cooperative maximum covering location problem; FACILITY LOCATION; ALGORITHM;
D O I
10.1007/s10489-022-03239-3
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This paper proposes a steady state genetic algorithm based approach for solving the obnoxious cooperative maximum covering location problem (OCMCLP) on a network. In cooperative coverage models, it is assumed that each facility emits a signal that decays over distance. At each demand point the cumulative signal strength received from all the facilities is calculated. A demand point is deemed to be covered if the total signal strength received by it is not less than a given threshold. All facilities contribute to the coverage of each demand point. Such models are different from the individual coverage models where the coverage of a demand point is decided by the single facility closest to that demand point. Given a graph with the set of demand points, the set of edges between these demand points, and the non-negative real weights associated with each demand point indicating the total demand at each point, the OCMCLP is concerned with locating p obnoxious (undesirable) facilities either at the demand points or along the edges in such a manner that maximizes the uncovered demand. The proposed genetic algorithm based approach makes use of crossover and mutation operators designed as per the characteristics of the OCMCLP. Solutions obtained through these genetic operators are improved further by a local search strategy. The performance of the proposed approach has been evaluated on the standard benchmark instances available in the literature. Computational results clearly show our proposed approach to be better in comparison to the existing state-of-the-art approaches for the OCMCLP.
引用
收藏
页码:16651 / 16666
页数:16
相关论文
共 38 条
[1]   Cooperative Covering Problems on Networks [J].
Averbakh, Igor ;
Berman, Oded ;
Krass, Dmitry ;
Kalcsics, Joerg ;
Nickel, Stefan .
NETWORKS, 2014, 63 (04) :334-349
[2]   Cooperative cover location problems: The planar case [J].
Berman, Oded ;
Drezner, Zvi ;
Krass, Dmitry .
IIE TRANSACTIONS, 2010, 42 (03) :232-246
[3]   Locating an undesirable facility by generalized cutting planes [J].
Carrizosa, E ;
Plastria, F .
MATHEMATICS OF OPERATIONS RESEARCH, 1998, 23 (03) :680-694
[4]   Hybrid evolutionary approaches for the single machine order acceptance and scheduling problem [J].
Chaurasia, Sachchida Nand ;
Singh, Alok .
APPLIED SOFT COMPUTING, 2017, 52 :725-747
[5]  
Church R., 1974, Papers Regional Sci. Assoc., V32, P101, DOI [10.1111/j.1435-5597.1974.tb00902.x, DOI 10.1007/BF01434264]
[6]  
Church R. L., 1978, Transportation Science, V12, P107, DOI 10.1287/trsc.12.2.107
[7]  
Church RL, 2019, CONTRIBUTIONS LOCATI, P69, DOI DOI 10.1007/978-3-030-19111-5_2
[8]  
Davis, 1991, HDB GENETIC ALGORITH
[9]   A survey on new generation metaheuristic algorithms [J].
Dokeroglu, Tansel ;
Sevinc, Ender ;
Kucukyilmaz, Tayfun ;
Cosar, Ahmet .
COMPUTERS & INDUSTRIAL ENGINEERING, 2019, 137
[10]   Location of a facility minimizing nuisance to or from a planar network [J].
Drezner, Tammy ;
Drezner, Zvi ;
Scott, Carlton H. .
COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (01) :135-148