一种灾难下车辆救援方案的快速制定方法

摘要

本发明公开了一种灾难下车辆救援方案的快速制定方法，包括：获取灾难救援调度请求信息，构建并计算网络流模型得到所有救援车辆总旅行时间以及时间阈值，并基于车流构建救援任务，并将起点为车库的救援任务分配给停留在该车库的救援车辆，并将起点为避难所的待分配救援任务分配给该避难所中已旅行时间最短的救援车辆，如果完成救援任务的时间高于时间阈值则更换起点，并更换后避难所中已旅行时间最短的救援车辆分配给更换避难所救援任务，将完成救援任务的时间不大于或大于但更接近时间阈值所对应的救援车辆分配给对应的救援任务中。该方法能够快速的将救援车辆分配到救援地点，并能够较为快速的完成救援。

说明书

技术领域

本发明属于物联网领域，具体涉及一种灾难下车辆救援方案的快速制 定方法。

背景技术

灾难是自人类存在以来无法避开的、无规律、不受人类主观意志控制 的事件，如地震、洪水、海啸、火灾、疫情；而由于生态环境的变化，或 者人类处理的不当，如交通事故、爆炸、恐怖袭击、战争等事件也时有发 生。近年来，世界灾难事故种类增多、发生趋于频繁、对社会影响面大。 然而，对一些重大灾难的防御效果不十分理想，灾难事件已成为当今社会 一个重要的公共问题。由于受经济发展水平制约，各地灾害救援发展极不 平衡，人员、技术、物资、装备缺乏，严重制约着灾难救援的效果和成果。

重大灾难发生时，安排灾民从受灾地区及时转移是保护人们免受灾害 可能影响的有效行动之一。由于灾难的后果和人们不稳定的身体和精神状 况而造成的财产损失，人们可能无法驾驶自己的汽车。因此，政府往往提 供大容量的公共交通车辆作为救援车辆到灾区接送灾民转移至避难所。此 外，在救援阶段，时间总是至关重要的，任何延误都可能造成一些可以避 免的损失。人们暴露在灾难中的时间越长，他们遭受伤亡的可能性就越大。因此，救援方案应该优先以最小化救援时间为目标。利用有限的救援车辆 和物资，尽快地将受灾人员从灾区救出送往安全的避难所或安置点，是救 灾过程中重要的工作之一。

近年来，许多研究人员通过经典的车辆路径规划方法构建大规模的救 援问题的模型，即每辆车的路径由一组二进制变量表示进行建模。虽然通 过求解这类模型可以得到每个车辆的时间表，但是对于大规模的问题，变 量的数量是巨大的，求解耗时。另一种对应车辆救援问题的建模方法是枚 举所有疏散的可行路径，在此基础上，将每辆车路径的选择表示为一个二 值变量。这样将路径规划问题转换为了资源分配问题，并一定程度上减少了变量的数目，降低了计算量。然而，在大规模疏散问题中，所有可能的 路径难以枚举。也一些研究者通过使用网络流方法来减小车辆索引变量， 该方法构建的网络流模型的输出不是车辆路径，而是每段路上通过的车流 量和人流量，难以作为救援方案用于救援。此外，不幸的是，救援方案的 优化是NP困难的。在面临大规模的救援问题时，无论利用现有的精确算 法还是启发式算法，制定出一个较优的救援方案都需要花费大量的计算时 间。虽然制定好的救援方案对于救援工作很重要，但在灾难情况下，指挥 部门应该快速制定救援方案，至少应该远小于所需的救援时间本身。因此， 设计车辆救援方案的快速制定方法，以保证在重点灾害发生时能够在第一 时间能够实施高效的救援工作尤为重要。

发明内容

本发明提供了一种灾难下车辆救援方案的快速制定方法，该方法能够 快速的将救援车辆分配到救援地点，并且制定的救援方案的救援时间较短。

一种灾难下车辆救援方案的快速制定方法，包括：

(1)获取灾难救援调度请求信息，灾难救援调度请求信息至少包括 受灾地，避难所地点，救援车辆数目，车库，以及车库、避难所地点和受 灾地三者之间的最优路径和每条路径的旅行时间；

(2)基于灾难救援调度请求信息构建以所有救援车辆总旅行时间最 小为目标的网络流模型，基于约束条件通过线性规划求解器求解网络流模 型得到所有救援车辆总旅行时间、优化救援路径和每条救援路径的救援车 辆数目，将所有救援车辆总旅行时间平均分配到每一个救援车辆，将分配 结果作为完成救援的时间阈值；

(3)基于每条救援路径中的救援车辆数目得到每辆救援车辆的路径， 即车流，将流入受灾地车流与流出受灾地车流进行配对得到以受灾地为中 心的救援任务，每个救援任务包括多个路径，将多个路径的旅行时间的和 作为每个救援任务的旅行时间；

(4)向救援任务分配救援车辆，将起点为车库的救援任务作为第一 救援任务分配给停留在该车库的救援车辆；将起点为避难所的救援任务中 首先分配救援车辆的任务作为第二救援任务，对第二救援任务进行车辆分 配，具体步骤为：从停留在避难所的救援车辆中筛选出已旅行时间最短的 救援车辆作为第一救援车辆，将第一救援车辆的已旅行时间与第二救援任 务旅行时间的和作为第二救援任务完成时间，当第二救援任务完成时间小 于时间阈值时，则将第一救援车辆分配到第二救援任务，当第二救援任务 完成时间大于时间阈值时，则将第二救援任务的起点变更为其他避难所， 并从其他避难所中选择已旅行时间最短的救援车辆作为第二救援车辆，将 第二救援车辆的已旅行时间与变更起点后的第二救援任务的旅行时间的 和作为第三救援任务完成时间，当第三救援任务完成时间小于时间阈值时， 则将第二救援车辆分配到变更起点后的第二救援任务，若第二救援任务完 成时间与第三救援任务完成时间均大于时间阈值时，则将更接近时间阈值 的救援任务完成时间对应的救援车辆分配给对应的救援任务，并将更接近 时间阈值的救援任务完成时间作为新的时间阈值；

按照对第二救援任务分配救援车辆的方法依次为其余起点为避难所 的待分配救援任务分配救援车辆，以完成救援方案的制定。

利用Dijkstra算法计算路网中车库、避难所地点和受灾地三者之间的 最优路径和每条路径的旅行时间。

基于约束条件通过线性规划求解器求解网络流模型得到所有救援车 辆总旅行时间，约束条件为：

其中，d为救援车辆的起点，即车库，B

s为避难所，S为避难所的集合，X

X

约束条件还包括：

其中，X

基于灾难救援调度请求信息构建以所有救援车辆总旅行时间最小为 目标的网络流模型，网络流模型目标T

其中，i,j为路径上的两个路网节点，路网节点为车库、避难所地点 或受灾地，I为两个路网节点的路径，δ

将网络流模型参数和约束条件输入线性规划求解器得到最小的所有 救援车辆总旅行时间，线性规划求解器为CPLEX或Lingo。

基于每条救援路径中的救援车辆数目得到每辆救援车辆的路径，即车 流，车流f

将流入受灾地车流与流出受灾地车流进行配对得到以受灾地为中心 的救援任务，包括：

将流入受灾地车流基于该车流的旅行时间递增排序，将流出受灾地车 流基于该车流的旅行时间递减排序，递增排序的车流数量与递减排序的车 流数量相同，将递增排序与递减排序的相同位置的车流进行配对得到以受 灾地为中心的救援任务。

将起点为避难所的待分配救援任务中首先进行车辆分配的任务作为 第二救援任务，确定第二救援任务的具体步骤为：

将起点为避难所的待分配救援任务基于救援任务旅行时间递减排序， 首先对救援任务旅行时间最长的待分配救援任务作为第二救援任务进行 车辆分配。

与现有技术相比，本发明的有益效果为：

本发明首先通过线性规划求解器对灾难救援调度网络流模型进行求 解得到所有救援车辆最小总旅行时间，并将所有救援车辆最小总旅行时间 平均分配给每一个救援车辆得到时间阈值，然后基于进出受灾地的车流构 建以受灾地为中心的救援任务，并将救援任务起点的救灾车辆分配给救援 任务，如果救援时间不满足时间阈值则更换其他起点的救灾车辆给救援任 务直至满足或接近时间阈值，进而即能够快速的将救援车辆分配给救援任 务，还能够使得最终救援调度方案具有较少的救援时间。

附图说明

图1为本发明具体实施方式提供的灾难下车辆救援方案的快速制定方 法流程图；

图2为本发明具体实施方式提供的灾难下车辆救援方案的快速制定方 法流程框图片；

图3为本发明具体实施方式提供的线性规划求解器求解网络流模型得 到优化救援路径图；

图4为本发明具体实施方式提供的灾难下车辆救援方案的快速制定方 法用于车辆分配流程图；

图5为本发明具体实施方式提供的灾难下车辆救援方案的快速制定方 法用于兴国洪水下救援车辆所用的救援时间图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进 行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例， 而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没 有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的 范围。

一种灾难下车辆救援方案的快速制定方法，如图1-4所示，具体步骤 为：

S1：采集并汇总灾难救援信息，所述灾难救援调度请求信息至少包括 受灾人数及地点，避难所地点及容量，可用的救援车辆数目及车库，灾害 下的道路通行时间，即车库、避难所地点和受灾地三者之间的最优路径和 每条路径的旅行时间。

如图2所示，共有三辆可用于救援的车辆，分别停靠在d

S2：将受灾点的需求和避难所的容量分别简化为车辆的整数倍；利用 Dijkstra算法计算路网中车库、避难所地点和受灾地三者之间的最优路径 和每条路径的旅行时间。

如图2，3所示，若每辆救援车辆能够承载的人数为20人，则三个受 灾点所需的救援车辆数分别为3辆、2辆和1辆，而两个避难所分别可以 容纳的4车和3车人。路网节点间的旅行时间，具体数值如下：

S3：基于灾难救援调度请求信息构建以所有救援车辆总旅行时间最小 为目标的网络流模型。

3.1：网络流模型目标T

其中，i,j为路径上的两个路网节点，路网节点为车库、避难所地点 或受灾地，I为两个路网节点的路径，δ

3.2：网络流模型的约束条件为：

其中，d为救援车辆的起点，即车库，B

s为避难所，S为避难所的集合，X

X

其中，公式(2)表示所有从车库d出发至受灾地的救援车辆数目不 小于车库d所拥有的救援车辆数目B

如图3所示，模型中各参数取值为：

(3)利用CPLEX线性规划求解器，以线性规划算法求解网络流模型。 由线性规划求解所得的最优路径及解如图3所示：

其他X

S4：网络流模型的解X

以受灾点p

S5：将救援车辆分配给救援任务，具体步骤如下：

5.1：为实现最终的救援方案的旅行时间尽可能的小，设置参数T

5.2：首先将起点为车库的任务分配给该车库内的救援车辆；如图4 所示，将救援任务1，2，4先分别分配给三辆救援车辆车。

5.3：将起点为避难所的待分配救援任务基于救援任务旅行时间递减排 序，首先对救援任务旅行时间最长的待分配救援任务作为第二救援任务分 配车辆，具体步骤如下：

从停留在避难所的救援车辆中筛选出已旅行时间最短的救援车辆作 为第一救援车辆。将第一救援车辆的已旅行时间设为T

按照对第二救援任务分配救援车辆的方法依次为其余起点为避难所 的待分配救援任务分配救援车辆，以完成救援方案的制定。

基于上述的对第二救援任务分配救援车辆的方法，本申请的案例中的 第二救援任务为救援任务5τ

救援任务5的起点为s

5.4：判断是否有任务未分配，如果有，返回步骤5.3再次选择任务分 配给车辆，如果所有任务都分配完成，则将救援方案输出。对于本申请的 案例，如图4所示，依次再将救援任务6分配给救援车辆1，救援任务3 修改起点至s

如图5所示，在兴国洪水中，利用本申请提供的灾难下车辆救援方案 的快速制定方法，将不同救援车辆数目进行分配的车辆调度方案所花费的 计算时间，从图中可以看出，车辆调度方案制定所花费时间在0.03s一下， 能够较快速的制定车辆调度方案。

本发明的有益效果是：该重大灾难下车辆救援方案的快速制定方法， 通过处理灾情数据，构建网络流模型将原本最小化救援时间，即最小化最 大车辆旅行时间的NP难问题简化为目标为最小所有车辆总旅行时间的问 题。虽然该问题仍然为一个整数规划问题，却可以利用线性规划算法在多 项式时间内可以求解的线性规划问题，快速求得整数解；基于网络流模型 的解，构建尽可能相等旅行时间的救援任务，并将这些救援任务尽可能平 均的分配给所有可用的救援车辆，以实现将求得的最小总旅行时间的解尽 可能平均分配以快速构建逼近最小救援时间的救援方案；本发明能够保证 在重大灾难下，受灾范围较大，受灾人数众多时，能快速生成救援计划， 提高了灾难后救援工作效率，同时制定的救援计划旨在充分利用所有可用 救援车辆在最短时间内以最快路径救出所有受灾者，保证了救援的高效性。