一种考虑多地貌的灾后多种交通工具接力救援方法

摘要

本发明公开了一种考虑多地貌的灾后多种交通工具接力救援方法，属于救援技术领域，针对地貌的不同，给出不同交通工具通行的难易程度以及对伤员的伤害程度；根据地貌的不同对灾区环境进行分区，并统计分区个数；判断救援交通工具能否直接到达某一分区，根据具体的地貌和分区情况，给出交通工具的直接到达矩阵；将救援时间，救援人数，以及救援成本作为目标函数，构建以救援人数为主要目标的数学模型；对所有交通工具的接力路径采用微粒群算法优化以得到每个交通工具所经过的分区。本发明根据幸存者数量和最小车辆容量，确定实际参与救援的车辆个数，由此确定微粒的长度和维度，可以保证机器人在尽可能短的时间和尽可能少的成本下，救援最多幸存者。

说明书

技术领域

本发明属于救援技术领域，具体涉及一种考虑多地貌的灾后多种交通工具接力救援方法。

背景技术

从古至今，洪水、地震、火灾以及诸多人为因素导致的灾害对人类造成了重大损失，而且由此引发的灾难可能会引起一连串的连锁效应，比如，地震造成的山体滑坡，洪水造成的溃坝洪灾，从而给人们的生命安全以及生产生活造成重大损失。更重要的是，上述连锁灾难给救援也带来了极大不便。

灾难发生后，地貌环境会发生变化，对于某些交通工具来说，其出行极度受限，因此，为了更快的完成救援工作，需要根据地貌环境联合多种交通工具，通过不同交通工具的接力来完成救援。

值得注意的是，不同的交通工具适用于不同的地形地貌，比如，直升机适用于所有地貌，然而考虑成本因素，直升机更适用于山地救援，大型卡车适用丘陵救援，而救护车则更适应在平原上行驶等。容易知道，灾难发生后，环境恶劣变化，人员也存在一定程度的伤亡，灾难救援必须争分夺秒，同时还需要保证幸存者的生命体征无碍，这些都是在救援的过程中需要考虑的问题。

一般的，灾难救援分为三个过程，一是生命探寻，通过无人机群遍历整个环境寻找具有生命体征的幸存者，快速定位其位置；二是具体救援，根据生命体征信息，采用最快对幸存者损失最小的方式，将其救出；三是将幸存者从灾区救出送入就近的救助中心或医院，对其进行治疗或者康复休息。这三个过程中，对于生命体征信息采集，目前无人机控制技术已经发展的很成熟了，已有的技术可以进行较快且准确的对生命体征进行探寻；而具体的救援过程目前也有很多有效的救援策略。本发明针对后最后一个过程，考虑灾后多地貌环境，给出具体的接力救援策略，以期快速将幸存者送入医院，保证救援的人数最多，同时花费的时间和成本较小。

对于具体的救援场景，如果在山区地形环境情况下，需要直升机等的配合；但是，如果将幸存者送入就近救助中心或医院，考虑到直升机的稀缺性，成本以及后续具体救援情况，可以联合救护车等交通工具来实施救援；此外，在丘陵等地貌中，越野车，卡车等可以有效通行，采用上述交通工具来运输伤员的效率最高。不同的地形地貌需要考虑不同的交通工具，而多种交通工具之间的接力及选择则对救援结果的影响较大，从而会影响整个救援的效率。

发明内容

发明目的：为了解决现有技术存在的问题，本发明提供一种考虑多地貌的灾后多种交通工具接力救援方法，促进救援任务快速有效地完成，以救援尽可能多的幸存者。

一种考虑多地貌的灾后多种交通工具接力救援方法，包括如下步骤：

1)针对灾后环境，进行分区，并给出直接到达矩阵R；

2)建立救援人数，救援时间以及救援成本的数学模型，进而得到救援问题的目标函数；其中，数学模型中决策变量为各车辆行驶的路径P，其中P

3)采用粒子群优化算法(PSO)进行求解，包括如下步骤：

步骤3.1：初始化粒子，包括粒子群的规模，粒子的位置和速度等；

步骤3.2：解码并根据问题的目标函数来评价每个粒子，并从中选出个体极值(pbest)和全局极值(gbest)；

步骤3.3：对于每个粒子，执行如下操作：

步骤3.31：更新每个粒子的速度和位置；

步骤3.32：根据已建立的目标函数来评价每个粒子的适应值；

步骤3.33：更新pbest和gbest；

步骤3.4：判断算法是否满足结束条件，如果是，算法结束，输出全局极值；否则，返回步骤3.3。

进一步地，所述的分区具体方法如下：

步骤一：以灾区和医院为对角顶点，构建出一个矩形救援地图；

步骤二：连接矩形的另外两个顶点，得到矩形的另外一条对角线，即为第一层分区，记为分区线l

步骤三：以灾区和医院两个顶点为起点，根据环境地貌的异同，继续采用直线划分，得到的直线为分区线l

步骤四：在两个分区线l

步骤五：根据分区线l

步骤六：分区结束，统计分区的个数ZN。

3、根据权利要求1所述的一种考虑多地貌的灾后多种交通工具接力救援方法，其特征在于，步骤1)中，所划分的分区中，两个分区之间的直接到达矩阵R

其中，r

进一步地，步骤2)中，所述的救援时间为所有交通工具行驶时间的最大值，即不同交通工具经过U个地貌中总的行驶时间，如公式(2)所示：

其中，T表示救援时间；v

进一步地，步骤2)中，所述的救援人数S如公式(3)所示：

其中，ST

进一步地，步骤2)中，假设第i个车辆行驶正常行驶时，其单位长度成本为C

其中，Weg

进一步地，步骤2)中，所述的目标函数，如公式(5)所列：

s.t.

y

Weg

其中，F表示目标函数，

进一步地，步骤2)中，对于M个幸存者的救援，首先需要对其进行分配车辆，确定每辆车中的幸存者数量Weg，具体的分配策略如下：

步骤2.1：确定实际参与救援车辆的个数VN

步骤2.2：随机选取VN

步骤2.3：计算剩余幸存者数量，判断是否完成分配，如果为0，则转入步骤2.5；如果剩余数量大于VN

步骤2.4：对剩下的幸存者，随机选取对应于剩余幸存者数量的车辆进行分配；

步骤2.5：统计每辆车上的幸存者数量Weg

进一步地，步骤3)中的算法设计，首先，要明确问题的解(车辆行驶路径)与微粒之间的关系，其次，需要确定微粒的长度和维度，具体步骤如下：

步骤3.1：对分区线l

步骤3.2：对于步骤3.1所得的两个集合，对分区线l

步骤3.3：采用相同的方法，对分区线l

步骤3.4：采用上述方法，一共循环的次数为max{l

微粒编码采用整数形式，第i个微粒表示为：

步骤1：从

步骤2：根据步骤1所得取余结果，从第一个旋转集合ZR中取出对应于取余结果的整数，由此得到车辆经过的一个区域的编号；

步骤3：接着对x

步骤4：根据步骤3所得的车辆行驶区域编号，从TN中取出相对应区域车辆种类的个数，记为TN

步骤5：从

步骤6：依次从x

步骤7：解码结束，输出解码后的结果。

根据直接到达矩阵R来修正产生的不可行解；假设第i个微粒的第j行

步骤1：寻找到达矩阵R的第p

步骤2：针对步骤3.4所得集合ZR中的第p

步骤3：判断步骤2中元素，是否为第U个元素，如果是，则结束修正操作，输出修正后的结果；如果不是，则对P

微粒的速度和位置更新公式

本发明采用整数编码，因为微粒的位置和速度更新公式如公式(10)和(11)所示：

其中，

Pbest和gbest更新方法

个体极值pbest和全局极值gbest指导微粒的进化方向，随着算法的运行，微粒根据公式(10)和(11)在不断进化，那么微粒的个体极值和全局极值也会在进化中不断更新，从而更好的指引微粒来搜索更好的解，因此，个体极值pbest和全局极值gbest的选择非常重要，gbest从pbest中选择，因此，首先给出pbest的选择方法。

个体极值更新的思想为：如果当前微粒的适应值F(Curpar)与pbest的适应值F(pbest)之差大于某一阈值Δ

在获得pbest之后，给出gbest的选择策略：如果当前微粒的适应值F(Curpar)与gbest的适应值F(gbest)的大小，如果F(Curpar)＞F(gbest)，则gbest更新为当前微粒；否则，gbest保持不变。

有益效果：与现有技术相比，本发明的一种考虑多地貌的灾后多种交通工具接力救援方法，可在救援时间以及救援成本较少的情况下，救援尽可能多的幸存者，有效完成多地貌环境下的救援任务。考虑灾区环境复杂多变，根据地貌的异同，对环境进行划分，给出交通工具的直接到达矩阵；考虑不同的地貌仅允许某一或某些交通工具通行，本发明采用多种交通工具进行接力救援，如此接力，保证了救援的顺利进行，提高了救援效率；根据多种交通工具的在某一地貌中的通行难度和对幸存者的伤害程度，考虑救援时间，救援人数以及救援成本三个目标，并根据目标的重要程度将上述三个目标加权构建成一个单目标函数，简化了问题，缩短了算法的运行时间，这对救援来说，具有重要的意义；采用微粒群算法进行问题求解，一个问题的解对于一个微粒，通过微粒的解码方法，不会发生重复救援的情况，避免了冲突的发生，更重要的是，多个交通工具的接力救援，可以有效节省成本，加快救援任务的完成，进而救援尽可能多的幸存者。

附图说明

图1为机器人救援环境示意图；

图2为分区方法示意图；

图3为PSO算法求解流程图。

具体实施方式

下面结合附图和具体实施实例对本发明进一步说明。以下实施例仅用于更加清楚地说明本发明的技术方案，而不能以此来限制本发明的保护范围。

本发明考虑上述多地貌多交通工具的接力救援问题，期望给出一条最优或者次优的救援路线，保证救援任务快速有效地完成，以救援尽可能多的幸存者。由此可见，上述问题是一个多地貌多车辆多路程规划问题，这是一个NP难问题，该问题的求解一般采用进化优化方法求解，考虑到微粒群进化优化方法广泛应用于路径规划问题，本发明拟采用微粒群算法来求解上述问题。

一、问题与环境描述

1.1环境描述

为了有效求解上述问题，不失一般性，现做出如下假设：

1、后续二次灾难发生，不会大幅度影响灾区以及灾区以外的地貌；

2、所有交通工具的电量或者油量均满足整个救援行动的使用；

3、每种交通工具在行驶的过程中速度是恒定的；

4、同一类型车辆在同一地貌中分布位置及通行困难程度相同，且同一车辆在同一地貌中对幸存者的伤害是相同的；

基于以上假设，本发明所要求解的问题如下：灾后环境中，存在N个不同的地貌，V个不同类型的交通工具，第j类交通工具在第i个地貌中的个数为

1.2环境描述

图1为多种交通工具实施救援的示意图，从图中可以看出，幸存者分布在灾区的不同位置，同一类型的交通工具分布位置相同，比如卡车分布在公路上，也可以分布在丘陵或者草地上；救护车分布在公路上；而直升机可以分布在所有的地貌上，等等，所以在执行救援的过程中，不仅要考虑各种交通工具的用途，还要考虑不同地貌，同时，幸存者的存活时间也是一个需要重点考虑的因素，这样才能达到在救援尽可能多幸存者的前提下，保证救援成本和时间最小。

然而，不同的交通工具，在不同地貌上的通行难度不同，同时对幸存者的伤害程度也不一样，比如：直升机上配有专业的救援设备，可以有效延长生命期限，因此对幸存者有正向的保护作用；而卡车行驶在颠簸的草地或丘陵，且车中没有配备较专业的救援设备，会加速生命期限的消耗，对幸存者有反向的伤害作用；此外，卡车在灾后地貌中行驶，较之在平坦的公路上也更为困难。基于以上分析，表1给出不同地貌情况下各种交通工具的通行难度，以及对幸存者的伤害指数。其中，A/B中，A表示通行难度，A越大表示通行的难度越大，0表示通畅无阻，1表示无法通行；B表示交通工具在不同地貌上行驶时，对幸存者的伤害程度，B越大表示伤害越大，B>0表示有伤害；而B<0则表示得到救助，对生命强度起到增强的作用。

表1通行难度与伤害指数

1.3地形处理

从图1可以看出，地貌分区相对来说较为明显，为了简化后续计算，首先需要对地形进行处理，在对地图采用已有且成熟的过分割方法的基础上，本发明提出一种分区方法，针对灾后环境，考虑实际救援环境地貌，最多分区四次，具体方法如下：

步骤一：以灾区(起点)和医院(终点)为对角顶点，构建出一个矩形救援地图。以图1为例，构建的矩形地图如图2所示，空心圆表示灾区，空心方形表示医院；

步骤二：连接矩形的另外两个顶点，得到矩形的另外一条对角线，即为第一层分区，记为分区线l

步骤三：以灾区和医院两个顶点为起点，根据环境地貌，继续采用直线划分，得到的直线为分区线l

步骤四：在两个分区线l

步骤五：根据分区线l

步骤六：分区结束，统计分区的个数ZN。

如图2所示，将图1救援环境分成13个地貌，从图2可以看出，除了直升机，其他交通工具无法做到直接从分区1直接达到分区11，此外，交通工具无法从分区8直接到达分区4，两个分区的直接到达的可能性为0，基于以上分析，本发明给出直接到达矩阵R

其中，r

为了更好的说明直接到达矩阵的构建方法，以图2为例，可以看出，同一个区域是直接到达的，但是为了使车辆不停滞在某一区域，本发明设定r

二、模型构建

考虑到救援问题的特殊性，本发明所要优化的目标为救援人数，救援时间以及救援成本，要求在救援最多幸存者的前提下，以尽可能少的成本和最短的时间来完成救援任务。采用上述信息，给出上述三个目标的数学模型。

本发明中的决策变量为各车辆行驶的路径P，其中P

2.1救援时间

基于上述分析，给出不同交通工具经过U个地貌中所需要的行驶时间，由于各个交通工具的救援工作并行进行，本发明的救援时间为所有交通工具行驶时间的最大值，具体的计算公式如公式(2)所示。

其中，T表示救援时间；v

2.2救援人数

救援人数是救援过程中最重要的指标，其与幸存者的生命期限密切相关，如果幸存者被送到医院，仍然在其生命期限之内，则表示成功将其救援，此时，救援人数加1；如果超过其生命期限，则表示救援失败，此时，救援人数不发生变化。基于上述分析，给出救援人数的数学表达式，如公式(3)所示。

其中，ST

2.3救援成本

本发明中，救援成本主要表现在车辆的行驶成本，如果车辆投入使用则需要计算成本，如果没有投入使用，则不计算成本；假设第i个车辆行驶正常行驶时，其单位长度成本为C

其中，Weg

2.4数学模型

由上述分析可以知道，救援人数最多是救援的最主要目标，救援时间和救援成本是次目标，基于此，给出本发明所研究救援问题的目标函数，如公式(5)所列：

s.t.

y

Weg

其中，F表示本发明所要求解的目标函数，

三、算法求解

本发明拟采用粒子群优化算法(PSO)进行求解，PSO算法的求解流程如图3所示。具体地：

步骤1：初始化粒子，包括粒子群的规模，粒子的位置和速度等；

步骤2：解码并根据建立的问题目标函数来评价每个粒子，并从中选出个体极值(pbest)和全局极值(gbest)；

步骤3：对于每个粒子，执行如下操作：

步骤3.1：更新每个粒子的速度和位置；

步骤3.2：根据已建立的目标函数来评价每个粒子的适应值；

步骤3.3：更新pbest和gbest；

步骤4：判断算法是否满足结束条件，如果是，结束，输出全局极值；否则，返回步骤3。

3.1人员分配

对于M个幸存者的救援，首先需要对其进行分配车辆，具体的分配策略如下：

步骤1：确定实际参与救援车辆的个数VN

步骤2：随机选取VN

步骤3：计算剩余幸存者数量，判断是否完成分配，如果为0，则转入步骤5；如果剩余数量大于VN

步骤4：对剩下的幸存者，随机选取对应于剩余幸存者数量的车辆进行分配；

步骤5：统计每辆车上的幸存者数量Weg

3.2微粒长度和维度确定

在采用微粒群算法求解上述问题之前，首先要明确问题的解(车辆行驶路径)与微粒之间的关系，其次，需要确定微粒的长度和维度。

对于问题解与微粒之间的关系，本发明中一个微粒表示所用投入使用车辆的路径，也即，表示问题的一个解，其中，微粒的维度表示车辆经过的区域编号，长度则表示投入使用的车辆个数。具体地，微粒的维度和长度需要根据具体的区域划分来决定，那么，具体的微粒的维度和长度如何确定呢？

根据3.1节内容可知，需要确定每个车辆的行驶路径，那么，微粒的维度则为始发区域参与救援的车辆个数VN

根据1.3节地形处理方法，对分区线级别相同的区域进行归类，以确定微粒的长度，具体步骤如下：

步骤1：对分区线l

步骤2：对于步骤2所得的两个集合，对分区线l

步骤3：采用相同的方法，对分区线l

步骤4：采用上述方法，一共循环的次数为max{l

注：遇到某一边集合不需要归类的情况，为了保证集合的等级的一致性，剩下的集合归类则在内部划分，不再拆分成单独一个集合，见步骤3。此外，在旋转90°的时候，内部拆分后的集合保持不变，见步骤4。

3.3微粒编码和解码

由于问题求解的是车辆行驶经过地貌分区的编号，所以，本发明的微粒编码采用整数形式，第i个微粒表示为：

要解决上述问题，需要对微粒进行解码，假设第i个微粒的第j维可以表示为：

步骤1：从

步骤2：根据步骤1所得取余结果，从集合ZR中取出对应于取余结果的整数，由此得到车辆经过的一个区域的编号；

步骤3：接着对x

步骤4：根据步骤3所得的车辆行驶区域编号，从TN中取出相对应区域车辆种类的个数，记为TN

步骤5：从x

步骤6：依次从

步骤7：解码结束，输出解码后的结果。

注：考虑到救援车辆不断的来回运输，因此，TN中各个元素的数量是变化的，在某一地形区域派出一辆车运输的时候，相对应车辆的个数减去1，如果减到0，则相应的车辆种类减1；而当车辆运输回来之后，相对应的车辆的个数加1，车辆的种类数则保持不变。

3.4修正操作

解码后的微粒可能会存在不可行解，不可行主要体现在微粒解码后，某一或几个车辆的行驶路径中，两个相邻的区域无法直接到达。考虑上述不可行解存在的情况，本发明根据直接到达矩阵R来修正产生的不可行解。假设第i个微粒的第j行

步骤1：寻找到达矩阵R的第p

步骤2：针对3.2节步骤4所得的集合ZR中的第p

步骤3：判断步骤2中所取元素是否为第U个元素，如果是，则结束修正操作，输出修正后的结果；如果不是，则对P

以图1的救援场景为例，路径集合为

3.5微粒的速度和位置更新公式

本发明采用整数编码，因为微粒的位置和速度更新公式如公式(10)和(11)所示：

其中，

3.6Pbest和gbest更新方法

个体极值pbest和全局极值gbest指导微粒的进化方向，随着算法的运行，微粒根据公式(10)和(11)在不断进化，那么微粒的个体极值和全局极值也会在进化中不断更新，从而更好的指引微粒来搜索更好的解，因此，个体极值pbest和全局极值gbest的选择非常重要，gbest从pbest中选择，因此，首先给出pbest的选择方法。

个体极值更新的思想为：如果当前微粒的适应值F(Curpar)与pbest的适应值F(pbest)之差大于某一阈值Δ

在获得pbest之后，给出gbest的选择策略：如果当前微粒的适应值F(Curpar)与gbest的适应值F(gbest)的大小，如果F(Curpar)＞F(gbest)，则gbest更新为当前微粒；否则，gbest保持不变。