基于多目标分布估计算法的地铁网络化应急站点选址
|
摘要
为提升地铁网络的应急救援能力,提出兼顾地下和地面交通两种运输方式的应急资源网络化共享模式,并建立多目标优化模型,对应急站点进行优化选址。模型以应急站点数量最少和总响应时间最短为优化目标,地铁车站重要程度为关键因素,求解各地铁车站的优化覆盖方案。提出了一种多目标分布估计算法,该算法采用拥挤比较算子和锦标赛选择算法获取优势群体,借助概率模型描述可行解的离散分布,并不断更新概率模型来实现种群的进化。运用建立的模型和算法求解北京市局部地铁网络应急站点选址问题,最终获得满足地面交通运输时效、并符合问题优化目标的Pareto最优解集。与NSGE-Ⅱ算法相比,多目标分布估计算法提前123代开始收敛,且针对最小化问题,多目标分布估计算法最优解的两个目标函数值较NSGE-Ⅱ算法分别减小64%和29%。可见,模型符合地铁应急站点选址问题的决策规则;多目标分布估计算法有效地缩小了决策空间,它比NSGE-Ⅱ算法更快地收敛,且能够获得更为优化的应急站点选址方案。
The paper intends to propose a network sharing mode of emergency resources in hoping to improve the emergency rescue capability of the subway network. The said model we have brought about is mainly based on the underground transportation feature with the supplementary functions of the ground-surface traffic and transportation so as to establish a multi-objective optimization model to optimize the locations of emergency stations and take into comprehensive account the allocation cost,the traffic velocity and reliability of the transportation means. The model in our mind should take the minimum number of emergency stations and the shortest total response time of the subway transportation as the optimistic objectives,the emergency rescue time minimalist of the ground transportation,with the availability of the subway stations as the key factors. A multi-objective distribution estimation algorithm was proposed to solve the location model. The said algorithm can help us to obtain the dominant part of the population through a comparison operator and tournament selection algorithm by means of a probability model by continuous updating of the said probability model. And,then,a coding scheme can be laid out according to the type of the decision variables and constraints of the problem so as to clarify the fitness functions according to the objective functions. The model and the algorithm here described can be taken to solve the emergency station location problem of Beijing local subway network.The Pareto optimal solution set we have suggested here can also meet the time limit of the ground transportation and optimize the objectives of the problem. More specifically speaking,the multiobjective distribution estimation algorithm is supposed to converge in the 23-rd generation,with the 2 objective functions of the optimal solution being set up at 12. 3 and 12,respectively.And,in so doing,the multi-objective distribution estimation algorithm may begin to converge 123 generations earlier than NSGE-Ⅱ algorithm. For the minimization problem in this paper,the 2 objective function strategies of the optimal solution for the multi-objective distribution estimation algorithm can be reduced by 64% and 29%,respectively,in comparison with the NSGEⅡ algorithm. It can thus be seen that the model can prove to be in conformity with the decision rules of the subway emergency resource location problem,whereas the multi-objective distribution estimation algorithm can converge faster than that of NSGE-Ⅱ so as to realize more optimized emergency station allocation strategies.
The paper intends to propose a network sharing mode of emergency resources in hoping to improve the emergency rescue capability of the subway network. The said model we have brought about is mainly based on the underground transportation feature with the supplementary functions of the ground-surface traffic and transportation so as to establish a multi-objective optimization model to optimize the locations of emergency stations and take into comprehensive account the allocation cost,the traffic velocity and reliability of the transportation means. The model in our mind should take the minimum number of emergency stations and the shortest total response time of the subway transportation as the optimistic objectives,the emergency rescue time minimalist of the ground transportation,with the availability of the subway stations as the key factors. A multi-objective distribution estimation algorithm was proposed to solve the location model. The said algorithm can help us to obtain the dominant part of the population through a comparison operator and tournament selection algorithm by means of a probability model by continuous updating of the said probability model. And,then,a coding scheme can be laid out according to the type of the decision variables and constraints of the problem so as to clarify the fitness functions according to the objective functions. The model and the algorithm here described can be taken to solve the emergency station location problem of Beijing local subway network.The Pareto optimal solution set we have suggested here can also meet the time limit of the ground transportation and optimize the objectives of the problem. More specifically speaking,the multiobjective distribution estimation algorithm is supposed to converge in the 23-rd generation,with the 2 objective functions of the optimal solution being set up at 12. 3 and 12,respectively.And,in so doing,the multi-objective distribution estimation algorithm may begin to converge 123 generations earlier than NSGE-Ⅱ algorithm. For the minimization problem in this paper,the 2 objective function strategies of the optimal solution for the multi-objective distribution estimation algorithm can be reduced by 64% and 29%,respectively,in comparison with the NSGEⅡ algorithm. It can thus be seen that the model can prove to be in conformity with the decision rules of the subway emergency resource location problem,whereas the multi-objective distribution estimation algorithm can converge faster than that of NSGE-Ⅱ so as to realize more optimized emergency station allocation strategies.
引文
[1] VALINSKY D. A determination of the optimum location of fire-fighting units in New York City[J]. Operations Research,1955,3(4):494-512.
[2] HAKIMI S L. Optimum locations of switching centers and the absolute centers and medians of a graph[J]. Operations Research,1964,12(3):450-459.
[3] TOREGAS C,SWAIN R,REVELLE C,et al. The location of emergency service facilities[J]. Operations Research,1971,19(6):1363-1373.
[4] WANG Wei(王炜),LIU Mao(刘茂). Multi-staged location-choosing model for optimizing the location-choice of the emergency resource depots in Tianjin[J]. Journal of Safety and Environment(安全与环境学报),2009,9(1):164-168.
[5] CHANTA S,MAYORGA M E,MCLAY L A. Improving emergency service in rural areas:a bi-objective covering location model for EMS systems[J]. Annals of Operations Research,2014,221(1):133-159.
[6] HU Anbing(胡安兵). Freeway emergency location model and application using genetic algorithm[J]. Journal of Transport Information and Safety(交通信息与安全),2013,31(5):104-106.
[7] UNO T,KATO K,KATAGIRI H. An application of interactive fuzzy satisficing approach with particle swarm optimization for multiobjective emergency facility location problem with A-distance[C]//Proceedings of 2007 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making. Honolulu:IEEE Press, 2007:368-373.
[8] LI Weijun(李卫军),WANG Juan(王娟),MA Jian(马剑). Optimal allocation of emergency resource for urban rail transit network[J]. Modern Urban Transit(现代城市轨道交通),2009(4):9-13.
[9] SUN Caihong(孙彩红). Study on the configuration optimization method of subway emergency resources based on network(基于网络化的地铁应急资源配置优化方法研究)[D]. Beijing:Beijing Jiaotong University,2010.
[10] SUN Xiaolin(孙晓临). Optimization research on emergency rescue stations sitting and resources settings of urban rail transit network(城市轨道交通网络应急救援站设置与资源配备优化研究)[D]. Beijing:Beijing Jiaotong University,2012.
[11] CAO Liu(曹琉),HU Rui(胡锐),GUO Zhaoneng(郭兆能),et al. Emergency resource location and distribution of urban rail transit[J]. Transport Research(交通运输研究),2016,2(4):54-61.
[12] WEN Renqiang(文仁强),CHEN Jianguo(陈建国),YUAN Hongyong(袁宏永),et al. Post-disaster emergency resource location and allocation based on the ant colony optimal algorithm for multi-level emergency response[J]. Journal of Tsinghua University:Science and Technology(清华大学学报:自然科学版),2012,52(11):1591-1596.
[13] LUSCOMBE R,KOZAN E. Dynamic resource allocation to improve emergency department efficiency in real time[J]. European Journal of Operational Research,2016,255(2):593-603.
[14] ZOGRAFOS K G,NATHANAIL T,MICHALOPOULOS P. Analytical framework for minimizing freeway incident response time[J]. Journal of Transportation Engineering,1993,119(4):535-549.
[2] HAKIMI S L. Optimum locations of switching centers and the absolute centers and medians of a graph[J]. Operations Research,1964,12(3):450-459.
[3] TOREGAS C,SWAIN R,REVELLE C,et al. The location of emergency service facilities[J]. Operations Research,1971,19(6):1363-1373.
[4] WANG Wei(王炜),LIU Mao(刘茂). Multi-staged location-choosing model for optimizing the location-choice of the emergency resource depots in Tianjin[J]. Journal of Safety and Environment(安全与环境学报),2009,9(1):164-168.
[5] CHANTA S,MAYORGA M E,MCLAY L A. Improving emergency service in rural areas:a bi-objective covering location model for EMS systems[J]. Annals of Operations Research,2014,221(1):133-159.
[6] HU Anbing(胡安兵). Freeway emergency location model and application using genetic algorithm[J]. Journal of Transport Information and Safety(交通信息与安全),2013,31(5):104-106.
[7] UNO T,KATO K,KATAGIRI H. An application of interactive fuzzy satisficing approach with particle swarm optimization for multiobjective emergency facility location problem with A-distance[C]//Proceedings of 2007 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making. Honolulu:IEEE Press, 2007:368-373.
[8] LI Weijun(李卫军),WANG Juan(王娟),MA Jian(马剑). Optimal allocation of emergency resource for urban rail transit network[J]. Modern Urban Transit(现代城市轨道交通),2009(4):9-13.
[9] SUN Caihong(孙彩红). Study on the configuration optimization method of subway emergency resources based on network(基于网络化的地铁应急资源配置优化方法研究)[D]. Beijing:Beijing Jiaotong University,2010.
[10] SUN Xiaolin(孙晓临). Optimization research on emergency rescue stations sitting and resources settings of urban rail transit network(城市轨道交通网络应急救援站设置与资源配备优化研究)[D]. Beijing:Beijing Jiaotong University,2012.
[11] CAO Liu(曹琉),HU Rui(胡锐),GUO Zhaoneng(郭兆能),et al. Emergency resource location and distribution of urban rail transit[J]. Transport Research(交通运输研究),2016,2(4):54-61.
[12] WEN Renqiang(文仁强),CHEN Jianguo(陈建国),YUAN Hongyong(袁宏永),et al. Post-disaster emergency resource location and allocation based on the ant colony optimal algorithm for multi-level emergency response[J]. Journal of Tsinghua University:Science and Technology(清华大学学报:自然科学版),2012,52(11):1591-1596.
[13] LUSCOMBE R,KOZAN E. Dynamic resource allocation to improve emergency department efficiency in real time[J]. European Journal of Operational Research,2016,255(2):593-603.
[14] ZOGRAFOS K G,NATHANAIL T,MICHALOPOULOS P. Analytical framework for minimizing freeway incident response time[J]. Journal of Transportation Engineering,1993,119(4):535-549.