论文研究-基于改进蚁群算法的救护车应急救援路径规划.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.88M 资料格式：pdf 举报版权申诉

weixin_38743968-11727523-16359648101636330031.pdf-第1页.png

第1页 / 共7页

weixin_38743968-11727523-16359648101636330031.pdf-第2页.png

第2页 / 共7页

weixin_38743968-11727523-16359648101636330031.pdf-第3页.png

第3页 / 共7页

weixin_38743968-11727523-16359648101636330031.pdf-第4页.png

第4页 / 共7页

weixin_38743968-11727523-16359648101636330031.pdf-第5页.png

第5页 / 共7页

weixin_38743968-11727523-16359648101636330031.pdf-第6页.png

第6页 / 共7页

weixin_38743968-11727523-16359648101636330031.pdf-第7页.png

第7页 / 共7页

文本预览

Computer Engineering and Applications 计算机工程与应用 2018，54（13） 153 基于改进蚁群算法的救护车应急救援路径规划孔林 1，张国富 1，2，苏兆品 1，2，蒋建国 1，2 KONG Lin1, ZHANG Guofu1，2, SU Zhaopin1，2, JIANG Jianguo1，2 1. 合肥工业大学计算机与信息学院，合肥 230009 2. 安全关键工业测控技术教育部工程研究中心，合肥 230009 1.School of Computer and Information, Hefei University of Technology, Hefei 230009, China 2.Engineering Research Center of Safety Critical Industrial Measurement and Control Technology, Ministry of Education, Hefei 230009, China KONG Lin, ZHANG Guofu, SU Zhaopin, et al. Ambulance emergency rescue routing planning for improved ant colony algorithm. Computer Engineering and Applications, 2018, 54（13）：153-159. Abstract：The parallel scheduling of ambulance and the problem of mass casualty rescue have been the priority problem in the field of emergency rescue. This paper firstly cites a model of ambulance concurrent allocation and scheduling optimization for a number of wounded patients with different degree of injury, according to the severity of the injury will be the classification of all the injured, on the basis of this different priorities for ambulance scheduling and rescue. In the heuristic algorithm, Ant Colony Optimization（ACO）pheromone global update strategy is improved to achieve the simul- taneous optimization of multiple scheduling routes. Comparative experiments show that the proposed model and intelligent algorithm has better performance in the case of ambulance resources inadequately, the algorithm can generate a set of effective and feasible solutions and gives the wounded rescue routes and response time to each ambulance. Key words：ambulance emergency allocation; scheduling routes; Ant Colony Optimization（ACO）摘要：救护车并行调度与大规模伤员救援一直是应急救援过程中需要优先解决的问题。引用一种面向多位受伤程度不同的伤员的救护车并发调度与分配优化模型，依据伤情轻重将所有伤者进行分类，按不同优先级进行救护车的调度与救援；采用蚁群优化智能算法求解这个复杂的优化问题。在启发式算法中，改进蚁群优化中的信息素更新策略以实现多个调度路径的同时优化。对比实验表明，所提模型与智能算法在救护车资源不是很充足的情况下具有更好的性能，能够产生一组有效可行的解，并可以同时给出各个救护车响应各伤员的救援路径和响应时间。关键词：救护车应急分配；路径调度；蚁群优化文献标志码：A 中图分类号：TP273 doi：10.3778/j.issn.1002-8331.1702-0215 1 引言近年来，伴随着全球气候的快速变化，地震、台风、洪水等自然灾害频频发生[1]，同时由于各国经济的快速发展，发生火灾和大中型工业类事故的数量正在快速增加，自然灾害以及突发人为事故造成人员伤亡和财产损失数目越来越大，灾害应急管理方法作为一门新兴的研究领域正引起包括我国在内的各国政府的高度关注[2]。如何高效地给出应急救援方案不仅是救援人员开展紧急救助的先决条件，同时可以减少救援时间、减轻人员及财产损失、减少次生灾害可能带来的二次伤害。灾害救助核心是受伤人员的救援、转运，主要任务是利用智能决策理论和计算机等辅助工具帮助指挥者制定合理、基金项目：安徽省自然科学基金（No.1608085MF132）。作者简介：孔林（1992—），男，研究生，主要研究领域为应急资源调度、应急决策，E-mail：1052685713@qq.com；张国富（1979—），男，博士，副教授，主要研究领域为结盟博弈、计算智能、灾害应急响应、多目标优化；苏兆品（1983—），女，博士，副教授，主要研究方向为智能优化、多媒体安全（语音安全）、资源调度；蒋建国（1955—），男，硕士，教授，主要研究方向为数字图像分析与处理、分布式智能系统、DSP 技术应用。收稿日期：2017-02-23 修回日期：2017-04-01 文章编号：1002-8331（2018）13-0153-07 CNKI 网络出版：2017-06-27, http://kns.cnki.net/kcms/detail/11.2127.TP.20170627.1713.014.html 计算机工程与应用www.ceaj.org

154 2018，54（13） Computer Engineering and Applications 计算机工程与应用高效的救援方案。本文主要研究在救援过程中如何高效规划救护车分配方案，使停放在医院的车辆及时到达伤员所在地进行救治，减小因为不合理分配导致的人员伤亡。近些年，国内外专家学者对救护车为代表的救援物资分配与调度问题研究现状如下所述。救护车调度首先需要确定目标区域内的车辆调度平台，通过平台指挥车辆到达该区域不同受灾点。Brot- corne[3] 在这方面提出了数学模型和算法。早期 Fitzsim- mons 和 Srikar[4]同样对该类覆盖选址模型问题做了相似研究。Gendreau[5]针对救援过程中闲置车辆再分配和救援覆盖范围的变化问题进行研究，并引出救护车动态定位问题。近期，国内外研究目标主要聚焦于依据真实的路况拥挤信息和救援物资水平进行车辆规划。例如 Schmid 和 Doerner[6]优先考虑一天中不断变化的救护车路网通行状况给救援带来的影响，在规划车辆行驶路径的同时通过变邻域搜索算法不断优化同一时间点内变化的交通量。Knight[7]提出预估可能受灾点和受伤者数目，预先作出不同反应的模型解决此类救援问题。Toro- Díaz[8]使用遗传算法解决超负荷数量的求助伤员问题。 Andersson 和 Värbrand[9]根据求救紧急水平和路径拥挤情况综合分配救护车。Schmid[10]用近似动态规划的方法把车辆调度和再分配结合在一起，达到最小化救援时间的目的。Campbell[11]用启发式方法解决旅行商问题和车辆路径问题，使到达最后一个救援点的时间最小或平均救援时间最小。Panchamgam[12]将各需求点按标准分为不同等级，按优先级依次提供救援。 Yi 与 Özdamar[13]提出最小未满足量和最小救援时间为目标函数的数学模型解决上述问题，并要求最后将伤员带回医院和救助中心。Özdamar 和 Demir[14]提出了上述类似模型确保救援高效、合理。Talarico[15]首先将所有伤者进行分级操作，其次规定不同类型伤者的救援方式以及医院的救护车数量和容纳能力，最后使用改进的大规模邻域算法实现设定的实验。杨文国等[16]考虑伤员数量持续增长，将所有伤员按照拥挤程度划分为大小不同的伤员蔟，然后进行救护车分配。从上述研究可以看出灾害救援和物资分配是目前研究非常活跃的领域。经过上述分析，文献[3-6]主要针对物资和车辆的调度，将救援问题转化为路径搜索问题，对救治和转移特定伤员考虑较少。文献[12-14]将多求救点的救援请求进行排序通过串行的方式响应，避免同时响应带来的物资冲突，此方法难以适用于大规模救援场景。因此，本文使用改进的蚁群算法，对多个医院同时响应多种不同类型的伤员提出的车辆分配路径进行优化，基于蚁群算法设计救护车配送路径，对蚂蚁搜索不同路径过程中信息素更新策略进行优化，将车辆的路径搜索与分配集成解决。 2 问题描述 ) 救护车路径选择问题是如何为需要救助的每位伤员规划一条合理的道路，确保每辆救护车能够快速到达现场进行救援。表 1 表示模型中字母所代表的含义。 P 表示所有伤者 P = R ⋃ G ，R 表示数量为 n 的重伤者集合 R = ( r1,r2,…,rn , n ≥ 0 ，所有重伤者必须转移至附近医院中进行救治。 H 表示附近所有医院集合 H =(h1, h2,…,hv),v > 0 。G 表示数量为 m 的轻伤者集合 G =(g1, g2,…,gm),m ≥ 0 ，所有轻伤者可以就地治疗，不必转送到医院。 K 表示数量为 i 的救护车集合 K =(K1,K2,…, Ki),i ≥ 0 ，规定每辆救护车最初停放在各医院。定义 A 为交通网络图中所有节点 A ={P × P} ⋃{P × H} ⋃{H × H}， tij( i,j ∈ A 表示救护车经过节点 i 和 j 所需时间。 di 表示每个伤者 i ∈ R ⋃ G 的救治时间，对于重伤者表示将其送到医院前的救治所需时间，对轻伤者则表示就地救治所需时间。 Ch 表示该医院接纳重伤者的最大能力。本文预设所有医院的容纳能力之和满足救援所有重伤者的需求。所有救护车接收到重伤者直接返回医院，接受和治疗轻伤者则可继续救治下一位伤者。 ) 表 1 救护车路径搜索模型的符号含义参数类型参数名参数解释数集参数决策变量 R G K A P H Ch dR dG dh WG WR tij Uih bi eR eG 一系列重伤者集合一系列轻伤者集合所有医院救护车集合交通网络图弧线集伤者总集合一系列医院集合医院 h 的最大容纳能力 h ∈ H 重伤者救治时间（定值）轻伤者救治时间（定值）重伤者抵达医院后下架时间赋予轻伤者的优先级赋予重伤者的优先级车辆通过节点 i 与 j 需时间 ( i,j ∈ A ) 二进制变量，当且仅当重伤者送入医院为 1 救护车访问 i 的时刻 i ∈ p 救治最后重伤者完成时刻救治最后轻伤者完成时刻为评估所得解的优劣，将救治完最后一位重伤者和轻伤者的时刻之和作为目标函数值，对重伤者表示运送最后一位到达医院时刻 eR ，对轻伤者则表示救治完最后一位轻伤者时刻 eG 。将路径选择优化问题转化为求救援伤员最小完成时间问题，此外 eG 与 eR 的重要性用 WR 与 WG 来衡量。例如当设置 WR ≫ WG 时，表示重伤者的优先级特别高，应予以优先救治。救护车路径搜索问题模型如下： WR ⋅ eR + WG ⋅ eG ∑ )Xhj ∈ { ( j ∈ P ⋃ H }0,1 , h ∈ H （1）（2）计算机工程与应用www.ceaj.org

孔林，张国富，苏兆品，等：基于改进蚁群算法的救护车应急救援路径规划 2018，54（13） 155 ij ∈ P ⋃ H h ∈ H i ∈ R ) （5）（4）（3） Xji = 1, ∀i ∈ P tih + dh , i ∈ R,h ∈ H Xij = ∑ ij ∈ P ⋃ H Uih = 1, ∀i ∈ R ∑ ∑ ∑ Uih ≤ Ch, h ∈ H eR ≥ bi + dR + Uih( （6） eG ≥ bi + dG, i ∈ G （7） bi ≥ 0, ∀i ∈ P ⋃ H （8） dR ≥ 0, ∀R ∈ P ⋃ H （9） dG ≥ 0, ∀G ∈ P ⋃ H （10） Xij ∈ { }0,1 , ∀i,j ∈ A （11） WR + WG = 1, R ⋃ G = P （12）目标函数（1）表示救援完所有重伤者与轻伤者的时刻之和，其值越大所选路径耗时越长，值越小路径耗时越短，用来衡量所选路径优劣。（2）当值为 1 时，救护车从医院出发驶向节点 j ，同时表示救援开始前每辆救护车均停在医院。（3）表示一辆救护车救援一位伤员成功后离开当前节点，对轻伤者说明救治完成后转至下一位伤者，对重伤者表示送回医院。（4）当值为 1 时，表示救护车所载重伤者已转移回医院。（5）要求每个医院接纳的病人总数不超过医院总的容纳能力。（6）表示救治完所有重伤者的时间应不小于任意一位重伤者的救援时间。（7）同样表示救治完所有轻伤者的时间应不小于任意一位轻伤者的救援时间。（8）bi 代表救护车到达伤者 i 的时刻。（9）、（10）中，dR、dG 分别代表轻/重伤者救治时间，本文均将其设置为常量。（11）当值为 1 时，表示救护车经过节点 i 和 j 组成的弧段。（12）中 WR 与 WG 表示轻重伤者救治的优先级，根据实际救援过程中统计的轻重伤者所占比例进行设定。 3 并行搜索 } 灾难发生后，应急指挥中心将会密集接收到伤者求救信号，快速高效规划路径、配置救护车成为首要任务，本文采用多救护车并行搜索减小救援总时间。举例说明并行搜索优势和可能出现的问题。图 1 的坐标区域为虚拟地图，将所有伤者、医院简化为图中坐标点，两点之间连线即代表其距离。现假设有医院 H ={ h1,h2 ，每家医院容纳病人数均 a1,a2 有救护车两辆，h2 ={ }a3 有为 3 人，其中医院 h1 ={ 一辆救护车。目前急需救援重伤者 R ={ r1,r2,r3 ，轻伤者 G ={ g1,g2⋯g7 ，简化重伤者救治时间 dR = 30 ，轻伤者救治时间 dG = 10 ，并设救护车医院下架时间 dh = 0 。图 1 显示 3 辆救护车可能行驶路径。从图中可看出每辆救护行驶两条路径，如救护车 a1 首先响应重伤患者 r1 ，并将其送至医院 h1 ，任务完成后继续响应轻伤患者 g4、g2、g1 ，救护车 a1、a2 与 a3 类似。 } } } 120 100 80 60 40 20 y g3 a1 r1 a2 h2 g7 0 20 40 g1 g2 h1 a1 g4 a2 r2 a1 路径 a2 路径 a3 路径 a3 g6 60 x r3 a3 g5 80 100 120 图 1 范例所寻路径图 2 显示范例路径时间集，即救护车完成所有伤员救援时刻值。图中救援完成最后一位重伤者时刻 eR = 151 ，最后一位轻伤者时刻 eG = 269 。注意，为减小救援总时间，路径起始点和结束点可以在不同医院，图中救护车 a2 行驶路径可代表此类情况。 g7g6g5g4g3g2g1r3r2r1h2h1 点始起 7 6 4 5 3 1 2 3 1 2 0 25 50 75 100 125 150 175 200 225 250 275 时间区间图 2 范例路径时间集救护车并行搜索可能出现如下问题：图中救护车 a3 根据计算的最短距离首先响应轻伤者 g7、g6 ，然后响应重伤者 r3 ，将 r3 送至医院 h2 后响应轻伤者 g5 ，计算此路径总用时为 258，与图中路径用时 261 相比减小约为 1.16%，相差幅度非常小。但救治重伤者时刻为 145，与图中路径用时 112.5 相比增加约为 23%，大大增加救援重伤者所需时间，因此，此路径在实际救援过程中应给予排除。为解决上述路径搜索问题，提出根据伤者伤情不同，设置救护车响应优先级 WR 与 WG ，根据伤员所占比例人为设置不同的初始值，使救护车偏向响应受伤程度不同伤者，WR + WG = 1。例如，图1中设置WR ≫ WG，所有救护车优先救治重伤患者，完成救援后依次响应轻伤患者。从图 2 可看出，所有重伤患者响应时间均最短，轻伤患者也得到有效救治。 4 改进的并行搜索蚁群优化算法本文所解决的问题可归属于基于图结构的优化问题，各医院、伤者类似于图中的各节点，因此与蚁群优化算法具有很强的契合性。大量的文献验证表明，蚁群优化在处理图结构优化问题时要比其他算法更加简单、灵计算机工程与应用www.ceaj.org020406080100120204060801001200h1h2r1r2r3g1g2g3g4g5g6起始点255075100125150175200225250275时间g7

156 2018，54（13） Computer Engineering and Applications 计算机工程与应用活和高效[17]，因此，本文选用蚁群算法搜索医院与伤者之间的路径。为验证本文算法有效性，实验同 Talarico[15] 使用的优化 LNS（Large Neighborhood Search）算法解决救护车响应伤员救援问题结果对比，通过对比实验数据表明改进的蚁群算法在救护车资源稀缺环境下救治伤员表现较好。 4.1 改进蚁群算法搜索救援路径蚁群算法搜索路径和算法中信息素更新策略改进如下：步骤 1 算法初始化，设置蚁群迭代次数 I = 100 ，蚂蚁数 M = 50 ，α = 1 ，β = 1 ，ρ = 0.7 ，τ0 = 1 。步骤 2 输入医院数 H ，车辆数 K ，重伤者数 R ，轻伤者数 G ，偏好 WR 、WG ，目标值 S = 0 。步骤 3 ∀m ∈ M 的蚂蚁进行搜索，任选节点 j ∈ A ，首先判断节点内型：（1）若节点 j 被判为重伤者，停止节点搜索，转向搜索医院，重新设定启发信息、信息素消减系数，σ = 0.7 ， π0 = 1 ，找出节点通向所有医院路径 L ={ } l1,l2,…,ln , n > 0 ，排除不满足式（2）、（4）、（5）条件的路径，依据条件式（13）、（14）、（15）选出最优路径，计算行驶时间 S1 ，同时记录路径中所有轻伤者数 g ，更新 R = R - 1，G = G - g ， S = S + S1 。（2）若节点 j 为轻伤者，就地治疗，依据条件式（16）、（17）、（18）选出最优路径，计算行驶时间 S2 ，更新 G = G - 1 ，S = S + S2 。步骤 4 选择下一个节点，重复步骤 3，当 R = 0 ，且 G = 0 时停止，I = I - 1 ，输出目标值 S 。步骤 5 重复步骤 3、步骤 4，当 I = 0 ，停止搜索，输出目标值 S 。在处理医院救护车到每个伤员的路径节点选择过程中，基于时间因素优先选择距离伤者路程最短的救护车，因此启发式信息应该与医院到伤者间的路程距离成反比。定义节点间弧度 ( i,j 上的启发式信息： ) φij = 1 tij , i,j ∈ A 此外，τij( )t 表示 t 时刻节点 i,j 间残留的信息量。初始时刻，各条路径上信息量相等：τij( )t = c( c为常数，用参数 1 - ρ 表示信息素的消逝程度，经过 n 时刻蚂蚁完成一次循环，各条路径上信息量要根据下式作调整： ) k = 1 Δτ k ij t + n = ρ ⋅ τij( )t + Δτij τij( ) Δτij = ∑ m Δτ k ij 表示第 k 只蚂蚁在本次循环中留在路径 i,j 上的信息量，Δτij 表示本次循环中所有经历过路径 i,j 的蚂蚁留在该路径上的信息量的增量。蚂蚁在运动过程中， ij( )t 表示在 t 时根据路径上的信息量决定转移方向，pk 刻蚂蚁 k 由位置 i 转移到位置 j 的概率： ij( )t = pk ij ( )t ij ( )t ,μ β ì π α ïï is ( )t ,μ β is ( )t í ∑π α ïï 0, otherwise î , j ∈ allowekk, s ∈ allowekk ) 其中 allowekk = ( 0,1,…,n _tabuk ，表示蚂蚁 k 下一步选择的节点。集合 tabuk 用以记录蚂蚁 k 已经到达过节点的集合，并且其存储值随着蚂蚁的搜索进程做动态变化。 α、β 分别表示蚂蚁在运动过程中所积累的信息素及期望信息，在蚂蚁选择路径中所起的不同作用。节点间分两步进行转移，首先对节点 i 进行判断： i ∈ R, 结束转移 i = ì í i ∈ G, 继续转移 î 首先判断蚂蚁目前所在节点类型，当节点被认定为重伤者，结束搜索下一位伤者节点，转为继续搜索离蚂蚁最近的医院位置，并将蚂蚁目前所在位置作为搜索初始点，蚂蚁在搜索地图上所有医院节点之前，重新定义路径的启发信息与残留信息量，与上文类似，蚂蚁对地图上所有节点重新搜索，保存搜索的所有路径，同时根据条件式（2）、（4）、（5）判断路径代表的医院有无救护车和容纳能力，舍弃无用路径，比较剩余的所有路径选择出最优解。保存路径信息且记录路径所经过轻伤者节点个数。当节点被判断为轻伤者，救助轻伤者，继续搜索下一位伤者节点，并且按照原转移策略进行搜索选择下一个节点 j 。当蚂蚁转移到节点 j 后再次进行上述节点类型判断，计算路径行驶距离并保存。 4.2 救援节点转移策略经过上述搜索，对于同一个重伤者 j 将会产生 3 种不同类型的路径结果，如式（13）、（14）、（15）所示： ) thj + ( bi + dR + tih + dh + thj + n ⋅ dG, i,j ∈ R tqj + bj + dR + n ⋅ dG , q ∈ G,j ∈ R 2 - Xhj - Ujh ⋅ M + n ⋅ dG , h ∈ H, j ∈ R （13）（14）（15）式（13）表示医院响应重伤者所需时间，其中 thj 表示救护车从医院 h 到达重伤者 j 所需时间，Xhj 和 Ujh 由式（2）、（4）可知用以判断医院有无救护车进行救援和有无能力接纳伤者。 M 表示车辆到达救援点的时间上限值，n 表示该条路径包含轻伤者的节点个数，dG 表示轻伤者救援时间，n ⋅ dG 的值代表救护车从医院向重伤者节点行驶过程中救治经过所有的轻伤者所耗总时间。式（14）表示车辆从救援重伤者 i 后转向重伤者 j 并将其送至医院时间。其中 bi 表示到达重伤者 i 的时刻， dR 表示重伤者的救治时间，tih 指将其送至医院时间， dh 指到达医院后下架以及运送时间，救护车从重伤者节点 i 行驶到目标医院过程中，遇到轻伤者或重伤者将不响应求救信号。 thj 代表车辆再次从医院出发到达重伤者 j 的时间，本次救治行驶路径中的轻伤者并计算从医院到重伤者路程中救治轻伤者总耗时。式（15）表示救计算机工程与应用www.ceaj.org

孔林，张国富，苏兆品，等：基于改进蚁群算法的救护车应急救援路径规划 2018，54（13） 157 治完轻伤者 q 后继续救治重伤者 j 所需时间，同样需要考虑路径中轻伤者响应问题。因此，在救治重伤者 j 时需要通过作对比找出最优路径和最小响应时间。当所有重伤者救治完成后，判断地图中是否有尚未救治的轻伤者，如果存在则继续救援。同理，对于轻伤者 i 同样会产生 3 种不同类型路径结果，如式（16）、（17）、（18）所示： ) 1 - Xhi ⋅ M, h ∈ H, i ∈ G bi + ( bj + dG + tji, i,j ∈ G bj + dR + tjh + dh + thi, h ∈ H,j ∈ R,i ∈ G （16）（17）（18）式（16）表示医院响应轻伤者所需时间。式（17）表示救治完轻伤者 j 后响应轻伤者 i 所需时间，其中 bj 代表到达伤者 j 的时刻，dG 代表救治时间，对于轻伤者本文将其设置为常量。式（18）表示车辆从救治完重伤者 j 后转向救治轻伤者 i 所需时间，其中 bj + dR + tjh + dh 表示将重伤者 j 送至医院所需时间，thi 表示从医院到达伤者 i 的时间。因此，在救治轻伤者 i 时同样需要比较以上 3 种情况，选择最优解并输出。 5 实验结果与分析为验证本文方法有效性，分别设计如下两种实验环 | R ，所有医院拥有的救护车境：模拟环境 1 中，∑ | n hi = i = 1 总数量等于重伤者总数量，救护车资源不是特别充分，但基本可以满足所有重伤员需求；模拟环境 2 中， ∑ n hi < | R ，所有医院救护车总数量小于重伤者数量，救 i = 1 护车资源出现匮乏，无法同时满足所有重伤者求救；此 | R + G ，即所有医院拥有的救护车外，存在 | |R < ∑ | | n hi < i = 1 总量大于所有重伤者总需求量，救护车资源同时救援所有重伤者之外还出现富余，这种情况考虑救护车资源的分配问题较为简单，先满足所有重伤者需求，将剩余车辆响应轻伤者，同时不断分配救援完重伤者的车辆响应轻伤者，因此本文不做过多分析。还存在 ∑ | R + G ， | n hi > i = 1 即医院拥有的救护车总量大于伤者总量，这种情况不需考虑救护车分配问题，因此本文不考虑。目前针对救护车路径应急搜索这一特定方向，国内，文献[17]对类似问题做了研究，其方法主要将密集伤员划分为大小不同的伤员蔟，对于距离较远的单个或几个节点考虑较少，且没有使用启发式算法进行搜索，因此本文不与其方法做对比。国外，Schmid[6]、Talarico[15] 等做过相关工作，其中 Talarico[15]使用优化的 LNS 算法处理救护车的路径选择和伤员救护，在单目标问题上具有一定的优势。因此，选择与 Talarico[15]提出的 LNS 算法做对比。同样选择若干实验数据将本文算法和 LNS 算法及文仁强[18]的双蚁群算法实验结果对比，指出各自算法应用范围和存在的优缺点，以及本文选择蚁群算法的原因和实验达到的效果。 5.1 实验参数选择启发式算法如蚁群优化算法、粒子群算法的参数选择与具体应用对象之间存在一定关联性，因此不同的参数取值可能会导致算法性能产生一定波动。本文主要采用实验法，通过结合已有的工作和测试结果获得一组较优参数值，该方法在目前经常使用。本文参数设计如下：蚁群算法中蚂蚁数 50，迭代次数 100，α = 1 ，β = 1 ， ρ = 0.7 ，τ0 = 1 ，σ = 0.7 ，π0 = 1 ；大规模邻域算法中迭代 ® 次数 I = 100 。每个实验样本均为随机生成，在 Intel CoreTM i5-4460 CPU@ 3.20 GHz，内存 8 GB，操作系统 Windows 7 的台式计算机上独立运行。 5.2 不同偏好和规模下的性能对比为解释选择蚁群算法作为本文实验的解决方法的原因，实验首先选择模拟环境 1 的多个参数对比 ACO 算法、LNS 算法以及 Two-ACO 算法运行效果，如表 2 所示。下文所有表中，目标解均表示搜索起始点到终点的最优路线值，运行时间表示各算法找到目标解的耗时。从表 2 实验数据可以看出，LNS 算法用时普遍较长且搜寻路径结果较差，Two-ACO 算法运行时间居中，实验效果在规模较小时最好，这是由于使用两个蚁群搜索的原因，随着伤员规模不断增加，节点选择策略没有优化，寻找路径效果不如本文算法。因此本文选用改进的蚁群算法解决模型和问题。分析本文模型和算法在相同规模（医院、救护车、病人总数均相同）和不同规模对救援效果的影响，做如下两种设置：模拟环境 1 中医院数量、救护车数量、重伤者数量均相同，轻伤者数量逐渐增加，因重伤者数量不变，偏好表 2 不同算法的实验效果（模拟环境 1：重伤者数=车辆数）医院数总人数重伤者数车辆数 2 2 3 3 4 4 6 8 8 10 10 13 2 2 3 3 4 4 2 2 3 3 4 4 目标解 ACO 350 422 563 632 688 737 LNS 325 387 577 648 703 756 Two-ACO 341 397 566 638 695 742 ACO 1.917 2.237 3.218 3.475 3.952 4.113 Two-ACO 运行时间/s LNS 3.174 3.527 4.873 5.317 5.728 6.337 1.747 2.154 3.327 3.556 4.173 4.552 计算机工程与应用www.ceaj.org

158 2018，54（13） Computer Engineering and Applications 计算机工程与应用值不变，均设定为 WR = 0.75 ，WG = 0.25 。模拟环境 2 中医院数量、救护车数量、重伤者数量、轻伤者数量均逐渐增加，分别设定偏好 WR = 0.75 ， WG = 0.25 ，WR = 0.5 ，WG = 0.5 ，WR = 0.25 ，WG = 0.75 3 种情况。表 3、表 4 分别表示在模拟环境 1（救护车数量=重伤者数量）与模拟环境 2（救护车数量<重伤者数量）中， WR 与 WG 值的设置对轻伤者和重伤者救援产生明显效果，均提高了重伤者救援效率，同样救援效果随轻伤者人数增加而提高。图 3、图 4 表示随着救援规模逐渐扩大，本文的算法得到的救援路径小于对比算法 LNS。分析两种不同优化算法运行机制可知，LNS 算法首先人为设定搜索规模，将图中所有节点划分为大小不同的模块；其次在设定的迭代次数内随机选择图中节点进行路径搜索，将搜索结果保存，完成所有迭代后结束搜索，比较所有解集选择最优路径；最后救护车按照已选路径进行搜索，行驶过程中不响应求救信息。通过对比本文优化的蚁群算法可看出 LNS 存在如下不足：人为设定的搜索规模使实验结果带有很大不确定性，不同的搜索规模会得到各种救护车行驶路径、医院接纳伤员策略，所有结果均需人为判断和比较，以此为基础寻找合适规模的地图分割医院数总人数重伤轻伤车辆数目标解（ACO）运行时间（ACO）/s 目标解（LNS）运行时间（LNS）/s 表 3 模拟环境 1 下的实验结果（重伤者数=车辆数） 2 2 2 3 3 3 4 4 4 4 6 8 10 6 8 10 10 13 16 19 2 2 2 3 3 3 4 4 4 4 4 6 8 3 5 7 6 9 12 15 2 2 2 3 3 3 4 4 4 4 350 422 473 455 563 632 688 737 795 831 1.917 2.237 2.713 2.945 3.218 3.475 3.952 4.113 4.682 4.977 325 387 457 432 577 648 703 756 804 862 3.174 3.527 3.986 4.327 4.873 5.317 5.728 6.337 6.819 7.543 医院数总人数重伤轻伤车辆数目标解（ACO）运行时间（ACO）/s 目标解（LNS）运行时间（LNS）/s 表 4 模拟环境 2 下的实验结果（重伤者数>车辆数） 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 值数函标目均平 900 800 700 600 500 400 300 5 25 25 25 30 30 30 35 35 35 40 40 40 45 45 45 50 50 50 6 12 19 8 15 22 9 17 26 10 20 30 11 22 34 13 25 38 19 13 6 22 15 8 27 18 9 30 20 10 34 23 11 37 25 12 5 10 15 5 10 15 5 10 15 5 10 15 5 10 15 5 10 15 872 994 1 097 927 1 038 1 113 986 1 105 1 183 1 021 1 153 1 285 1 103 1 201 1 320 1 123 1 257 1 427 1 600 1 500 1 400 1 300 1 200 1 100 1 000 900 800 值数函标目均平 ACO 医院数=2 LNS 医院数=2 ACO 医院数=3 LNS 医院数=3 ACO 医院数=4 LNS 医院数=4 10 15 总伤者数 20 图 3 模拟环境 1 对比图 5.113 6.531 7.533 5.531 6.852 7.927 5.924 7.315 8.144 6.427 7.732 8.941 6.965 8.037 9.051 7.334 8.627 9.831 902 1 025 1 117 957 1 074 1 189 1 017 1 128 1 254 1 083 1 177 1 307 1 154 1 235 1 385 1 207 1 304 1 526 7.873 8.524 9.173 8.124 9.014 9.617 8.673 9.557 10.115 9.117 10.118 10.634 9.615 10.623 11.275 10.103 11.104 11.725 ACO 偏好 25% LNS 偏好 25% ACO 偏好 50% LNS 偏好 50% ACO 偏好 75% LNS 偏好 75% 25 30 35 40 总伤者数 45 50 图 4 模拟环境 2 对比图计算机工程与应用www.ceaj.org

孔林，张国富，苏兆品，等：基于改进蚁群算法的救护车应急救援路径规划 2018，54（13） 159 方法；其次，救护车依据所分配路径行驶，途中不响应伤者求救信息。本文救护车依据 4.2 节的转移策略，在行驶途中对于伤员求救分为两种应对方法：一是救护车救援重伤者在其驶向重伤者节点过程中救治路径中遇到的轻伤者，到达目标节点后不在响应求救信息，只负责将病人送至附近医院；二是救护车救治轻伤者依据响应最短距离目标原则，一次救治伤员。通过上述分析可知改进的蚁群算法在救治伤者和规划路径方面存在优势，特别当伤者规模较大、救护车资源稀缺时，救援方法更为有效；并且模拟环境 2 的效果好于模拟环境 1 的效果。这是因为受到总救护车资源数量限制，当重伤患者人数逐渐增加而救护车数量保持不变时，车辆往返节点与医院的次数不断增减，同时救治轻伤者的数量也不断增加，与对比算法相比节省了救援总时间。同时，两种环境下本文算法运行时间均小于对比实验。表 3与图 4表示在医院、救护车数量相同、医院容纳能力相同条件下，伤者总人数不断增加会导致救援总时间逐渐增加。同时，占总救援人数比例不同的重伤者对救援总时间也产生很大影响，从中可看出随着重伤患者人数增加，有限救护车不得不转运更多重伤者，使得救援总时间也随之增加，并且救援轻伤患者总时间也逐渐增加。 6 结论本文针对灾害救援过程中救护车路径规划和伤员紧急运送这一难点问题，构建一个面向多个医院、多辆救护车同时响应求救信息的数学模型，提出对伤者进行分级并设定偏好，基于并发蚁群优化算法实现救援路径规划和救护车分配调度，提高总体救援时间的同时特别优化了救护车响应重伤者时间，修正蚁群算法中信息素更新策略。在设定的两种模拟环境中，与已有文献进行的对比实验表明，本文算法在合理的偏好设定条件下能够提供更高质量的解集。但是，本文对于救护车应急救援中的分配和调度只是在综合已有全部求救信息后进行的，当面临一些特大自然灾害（如地震）中，一般会伴随着很多次生灾害（如山体滑坡、泥石流），这时伤者人数和救援信息在不断增加，如何实现实时有效救护车路径规划和伤者救援仍需要做大量工作，包括指挥中心如何实时接收求救信息，救护车位置如何实时定位，医院当前接纳伤员数如何及时汇总等均需解决。下一步的研究主要是修改数学模型和改进蚁群算法以适用于实时救援环境，结合 GPS（全球定位系统）技术和 GIS（地理信息系统）技术搭建一套用于救援的工作平台等。参考文献： [1] Wang Z.A preliminary report on the great Wenchuan earthquake[J].Earthquake Engineering and Engineering Vibration，2008，7（2）：225-234. [2] Bilham R.Disaster management：Preparing for the worst[J]. Nature，2013，502：438-439. [3] Brotcorne L，Laporte G，Semet F.Ambulance location and relocation models[J].European Journal of Operational Research，2003，147（3）：451-463. [4] Fitzsimmons J A，Srikar B N.Emergency ambulance location using the contiguous zone search routine[J]. Journal of Operations Management，1982，2（4）：225-237. [5] Gendreau M，Laporte G，Semet F.A dynamic model and parallel tabu search heuristic for real- time ambulance relocation[J].Parallel Computing，2001，27（12）：1641-1653. [6] Schmid V，Doerner K F.Ambulance location and relocation problems with time- dependent times[J].European Journal of Operational Research，2010，207（3）：1293-1303. [7] Knight V A，Harper P R，Smith L.Ambulance allocation for maximal survival with heterogeneous outcome mea- sures[J].Omega，2012，40（6）：918-926. travel [8] Toro-Díaz H，Mayorga M E，Chanta S，et al.Joint location and dispatching decisions for Emergency Medical Services[J]. Computers & Industrial Engineering，2013，64（4）：917-928. [9] Andersson T，Värbrand P.Decision support tools for ambu- lance dispatch and relocation[J].Journal of the Operational Research Society，2007，58（2）：195-201. [10] Schmid V.Solving the dynamic ambulance relocation and dispatching problem using approximate dynamic program- ming[J].European Journal of Operational Research，2012， 219（3）：611. [11] Campbell A M，Vandenbussche D，Hermann W.Routing for relief efforts[J].Transportation Science，2008，42（2）： 127-145. [12] Panchamgam K，Xiong Y，Golden B，et al.The hierarchical traveling salesman problem[J].Optimization Letters，2013， 7（7）：1517-1524. [13] Yi W，Özdamar L.A dynamic logistics coordination model for evacuation and support in disaster response activities[J].European Journal of Operational Research， 2007，179（3）：1177-1193. [14] Özdamar L，Demir O.A hierarchical clustering and routing procedure for large scale disaster relief logistics plan- ning[J].Transportation Research：Part E，2012，48（3）： 591-602. [15] Talarico L，Meisel F，Sörensen K.Ambulance routing for response with patient groups[J].Computers & disaster Operations Research，2015，56：120-133. [16] 杨文国，黄钧，郭田德 . 大规模突发事件中伤员救助的救护车分配优化模型[J]. 系统工程理论与实践，2010，30（7）： 1218-1224. [17] 王旭坪，马超，阮俊虎 . 考虑公众心理风险感知的应急物资优化调度[J].系统工程理论与实践，2013，33（7）：1735-1742. [18] 文仁强，钟少波，袁宏永，等 . 应急资源多目标优化调度模型与多蚁群优化算法研究[J]. 计算机研究与发展，2013， 50（7）：1464-1472. 计算机工程与应用www.ceaj.org

分享到：

赞收藏

资料库

论文研究-基于改进蚁群算法的救护车应急救援路径规划.pdf

相关推荐

开发技术

热门标签

最新资料