A Decision Model of Reserve Coverage Selection for Multi-level Service Facilities Based on Improved NSGA-II Algorithm

doi:10.12005/orms.2019.0009

Abstract

Abstract: In order to deal with the problem of differentiated demand of disaster service in the process of cross-regional emergencies, a multi-level reserve coverage decision model of emergency reserve facilities is established, that is, a demand point is provided by different emergency facilities. In the process of modeling, the situation of the service provided by other facilities is considered in the busy state of the facility, which makes the model more practical. For the first time, the NSGA-II algorithm is improved by designing the segmented chromosome coding method to improve the operation efficiency to solve the multi-target location decision problem. The Pareto solution distribution obtained under the improved method is compared with the simulation results under the NSGA-II algorithm, and the spatial distribution scheme is obtained according to the deployment strategy of the facility. It proves the feasibility of the model and the effectiveness of the improved NSGA-II algorithm in solving the multi-objective location decision-making problem. The model can provide a valid basis for the decision-makers to a certain extent.

Key words: differentiated demand, multi-level backup coverage model, chromosome coding, improved NSGA-II algorithm

摘要： 为了应对跨区域突发事件过程中受灾点服务差异化需求的问题,建立了应急储备设施点的多级备用覆盖选址决策模型,即一个需求点由多个应急设施提供不同质量水平的服务,并考虑设施繁忙状态下由其他设施点提供服务的状况,使模型更加符合实际应用。首次通过设计分段的染色体编码方式改进NSGA-II算法提升运算效率以更好地解决多目标选址决策问题,将改进方法下得到的Pareto解分布与NSGA-II算法下的仿真结果进行对比分析,结合设施点的部署策略得到不同的空间布局方案。证明了模型的可行性及改进NSGA-II算法在解决设施点多目标选址决策问题时的有效性。

关键词: 差异化需求, 多级备用覆盖模型, 染色体编码, 改进NSGA-II算法

CLC Number:

O224
C934

SONG Yan, TENG Chen-mei, JIANG Jin-gui. A Decision Model of Reserve Coverage Selection for Multi-level Service Facilities Based on Improved NSGA-II Algorithm[J]. Operations Research and Management Science, 2019, 28(1): 71-78.

宋艳, 滕辰妹, 姜金贵. 基于改进NSGA-II算法的多级服务设施备用覆盖选址决策模型[J]. 运筹与管理, 2019, 28(1): 71-78.

References

[1] Hakimi S L. Optimum locations of switching centers and the absolute centers and medians of a graph[J]. Operations Research, 1964, 12: 450-459.
[2] Toregas C, Revelle C, Bergman L. The location of emergency services[J]. Operations Research, 1971, 19(6): 93-95.
[3] Church R, Velle C R. The maximal covering location problem[J]. Papers in Regional Science, 1974, 32(1): 101-118.
[4] Daskin M S, Stern E H. A hierarchical objective set covering model for emergency medical service vehicle deployment[J]. Transportation Science, 1981, 15(2): 137-152.
[5] Aly A A, White J A. Probabilistic formation of the emergency service location problem[J]. Journal of Operational Research Society, 1978, 29(12): 1167-1179.
[6] Berman O, Krass D, Drezner Z. The gradual covering decay location problem on a network[J]. European Journal of Operational Research, 2003, 151(3): 474-480.
[7] Moore G C, Revelle C. The hierarchical service location problem[J]. Management Science, 1982, 28(7): 775-780.
[8] Daskin M S. Network and discrete location: Models, algorithms, and applications[M]. New York: Wiley Interscience, 1995.
[9] Dökmeci V F. A quantitative model to plan regional health facility systems[J]. Management Science, 1977, 24(4): 411-419.
[10] Church R L, Eaton D J. Hierarchical location analysis using covering objectives[J]. Spatial analysis and location-allocation models, 1987: 163-185.
[11] Butler T W, Karwan K R, Sweigart J R. Multi-level strategic evaluation of hospital plans and decisions[J]. Journal of the Operational Research Society, 1992, 43(7): 665-675.
[12] Boffey B, Yates D, Galvo R D. An algorithm to locate perinatal facilities in the municipality of Rio de Janeiro[J]. Journal of the Operational Research Society, 2003, 54(1): 21-31.
[13] Eitan Y, Narula S C, Tien J M. A generalized approach to modeling the hierarchical location-allocation problem[J]. IEEE Transactions on Systems Man & Cybernetics, 1991, 21(1): 39-46.
[14] Tien J M, El-Tell K, Simons G R. Improved formulations to the hierarchical health facility location-allocation problem[J]. IEEE Transactions on Systems Man & Cybernetics, 1970, SMC- 13(6): 1128-1132.
[15] Banerji S, Fisher H B. Hierarchical location analysis for integrated area planning in rural india[J]. Papers in Regional Science, 1974, 33(1): 177-194.
[16] Calvo A B, Marks D H. Location of health care facilities: an analytic approach[J]. Socio-Economic Planning Sciences, 1973, 7(5): 407-22.
[17] Dökmeci V F. An optimization model for a hierarchical spatial system[J]. Journal of Regional Science, 1973, 13(3): 439-451.
[18] Narula S C, Ogbu U I. A hierarchical location-allocation problem[J]. Omega, 1979, 7: 137-143.
[19] Schultz G P. The logic of health care facility planning[J]. Socio-Economic Planning Science, 1970, 4(3): 383-393.
[20] Narula S C. Hierarchical location-allocation problems: a classification scheme[J]. European Journal of Operational Research, 1984, 15(1): 93-99.
[21] Serra D, ReVelle C. The pq-median problem: location and districting of hierarchical facilities[J]. Location Science, 1993, 1(4).
[22] Ahin G, ven, Ral H. A Review of hierarchical facility location models[J]. Computers & Operations Research, 2007, 34(8): 2310-2331.
[23] Farahani R Z, Hekmatfar M, Fahimnia B, Kazemzadeh N. Hierarchical facility location problem: models, classifications, techniques, and applications[J]. Computers & Industrial Engineering, 2014, 68(1): 104-117.
[24] Daskin M S, Hogan K, ReVelle C S. Integration of multiple, excess, backup, and expected covering models[J]. Environment and Planning B Planning and Design, 1988, 15(1): 15-35.
[25] Berman O, Krass D. Facility location problems with stochastic demands and congestion[J]. Drezner Z. hamacher H.w.facility location Applications & theory, 2002, 41(5): 329-371.
[26] Araz C, Selim H, Ozkarahan I. A fuzzy multi-objective covering-based vehicle location model for emergency services[J]. Computers & Operations Research, 2007, 34(3): 705-726.
[27] Erdemir E T, Batte R, Rogerson P A, Blatt A, Flanigan M. Joint ground and air emergency medical services coverage models: a greedy heuristic solution approach[J]. European Journal of Operational Research, 2010, 207(2): 736-749.
[28] 肖俊华,侯云先.应急物资储备库多级覆盖选址模型的构建[J].统计与决策,2012(23):45-48.
[29] 葛春景,王霞,关贤军.重大突发事件应急设施多重覆盖选址模型及算法[J].运筹与管理,2011,20(5):50-56.
[30] Hajipour V, Fattahi P, Tavana M, Caprio D D. Multi-objective multi-layer congested facility location-allocation problem optimization with Pareto-based meta-heuristics[J]. Applied Mathematical Modelling, 2016, 40(7-8): 4948-4969.
[31] 付德强,张伟,吴先锋,李昌兵.基于NSGA-II的灾害随机环境下应急储备库多目标选址决策模型研究[J].软科学,2013,11:48-52.
[32] 付德强,王旭,张伟.基于NSGA-II的应急储备库多目标选址决策模型及算法研究[J].运筹与管理,2014,04:64-69.
[33] Deb K, Agrawal S, Pratap A, Meyarivan T. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[A], International Conference on Parallel Problem Solving from Nature[C], Paris: 2000. 849-858.
[34] Moradijalal M, Rodin S I, Mari?o M A. Use of genetic algorithm in optimization of irrigation pumping stations[J]. Journal of Irrigation & Drainage Engineering, 2004, 130(5): 357-365.
[35] Kim M H, Park N, McKay R I, Shin H, Lee Y G, Jeong K S, Kim D K. Improvement of complex and refractory ecological models: riverine water quality modeling using evolutionary computation[J]. Ecological Modelling, 2014, 291(291): 205-217.
[36] Kim D K, Jeong K S, Whigham P A, Joo G J. Winter diatom blooms in a regulated river in South Korea: explanations based on evolutionary computation[J]. Freshwater Biology, 2007, 52(10): 2021-2041.
[37] Jeong K S, Jang J D, Kim D K, Joo G J. Waterfowls habitat modeling: Simulation of nest site selection for the migratory little tern(Sterna albifrons) in the Nakdong estuary[J]. Ecological Modelling, 2011, 222(17): 3149-3156.
[38] Jeong K S, Kim M H, Jo H, Gim G A, Kim D K, Joo G J. Search of optimal locations for species-or group-specific primer design in DNA sequences: Non-dominated Sorting Genetic Algorithm II (NSGA-II)[J]. Ecological Informatics, 2015, 29: 214-220.
[39] Blankenship L E, Yayanos A A. Universal primers and PCR of gut contents to study marine invertebrate diets[J]. Molecular Ecology, 2005, 14(3): 891-899.
[40] Darling J A, Mahon A R. From molecules to management: adopting DNA-based methods for monitoring biological invasions in aquatic environments[J]. Environmental Research, 2011, 111(7): 978-988.
[41] Deagle B E, Tollit D J. Quantitative analysis of prey DNA in pinniped faces: potential to estimate diet composition[J]. Conservation Genetics, 2007, 8(3): 743-747.
[42] Jo H, Gim J A, Jeong K S, Kim H S, Joo G J. Application of DNA barcoding for identification of freshwater carnivorous fish diets: is number of prey items dependent on size class for micropterus salmoides[J]. Ecology & Evolution, 2014, 4: 219-229.
[43] Thomsen P F, Kielgast J, Iversen L L, et al. Monitoring endangered freshwater biodiversity using environmental DNA[J]. Molecular Ecology, 2012, 21(11): 2565-2573.
[44] 侯帅,王汉斌,王亚阳.基于NSGA-II的煤矿矿区应急救援站选址研究[J].中国煤炭,2015,12:115-119.
[45] 李栋学,刘茂.NSGA-II在应急物资储备库选址中的应用[J].工业安全与环保,2009,03:1-3.
[46] 杨剑浩,姚志刚,白鹏霞,等.基于NSGA-II算法的双目标服务网点选址优化[J].物流技术,2011,15:98-100+137.
[47] 谢承旺,李凯,廖国勇.一种带差分局部搜索的改进型NSGA-II算法[J].计算机科学,2013,(10):235-238+273.
[48] 肖怀硕,李清泉,张岩,等.基于非支配排序遗传改进算法的故障限流器的优化配置[J].电网技术,2016,(08):2444-2450.
[49] 罗辞勇,陈民铀,张聪誉.采用循环拥挤排序策略的改进NSGA-II算法[J].控制与决策,2010,(02):227-231.
[50] 李琳,吴鑫淼,郄志红.基于改进NSGA-II算法的水资源优化配置研究[J].水电能源科学,2015,(04):34-37.