关于地面搜索问题的简化模型关于地面搜索问题的简化模型

赵宇杰 周玲 梁晔 王哲慧 李志乾

【摘要】本文建立了关于“地面搜索”问题的简洁数学模型。将平地矩形区域划分成小的矩形带状，综合最大流思想进行分析推理，得到了搜索队员能够采用的最短路径搜索方式。此模型原理简单，方法实用。

【关键词】最大流问题；最短路径；带状区域

地面搜索问题对现实的防灾抗灾工作,起着不可忽视的作用。在抗灾救灾的紧急情况下，制订搜索队伍的行进路线，对预定区域进行快速的全面搜索显得尤为重要。

本文建立了关于“地面搜索”问题的数学模型：首先采用图解法对所给平地矩形区域划分成小的矩形单元；其次，对每个搜索队员的搜索面积做了分析，区域划分的原则是将总长与总宽按照队员组合所得的最大搜索距离的整数倍进行分解，把整个区域划分成相互不重叠的带状（矩形）区域；再次，综合最大流思想进行分析推理，得到了搜索队员的最佳组合就是并排搜索；最后利用最短路径方法，得出最优的结果。依据这个结果为“地面搜索”提供了一个比较清晰直观的最短路径安排方式。

问题叙述：对于一个平地矩形目标区域，大小为11200 m×7200 m，需要进行全境搜索。搜索时要求如下：出发点在区域中心；搜索完成后需要进行集结，结束点在左侧短边中点；每个人搜索时的可探测半径为20 m，搜索时平均行进速度为0。6 m/s；不需搜索而只是行进时,平均速度为1。2 m/s。每个人带有GPS定位仪、步话机，步话机通讯半径为1000 m。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。

现在有如下问题需要解决：假定有一支20人一组的搜索队伍,拥有1台卫星电话。请设计一种耗时最短的搜索方式，求出搜索完整个区域的时间，看能否在48小时内完成搜索任务；如果不能完成，需要增加到多少人才可以完成。

模型的建立与算法：

一、模型假设

搜索人员的通讯良好,每个人单独向组长汇报无干扰；搜索人员的身体素质及搜索能力相同；不考虑余震带来的其他干扰,如道路中断或阻塞；该区域中天气对搜索任务无明显影响；每个搜索人员所带食物及生活用品等充足；该搜索组在搜索途中无滞留。

二、模型的建立

1。最大流问题的基本假设为:

(1)网络中所有流起源于一个节点,这个节点叫做发点S(也称为源或始点)；所有的流终止于另一个节点,这个节点叫做收点E(也称为汇或终点)；

(2)其余所有的节点叫做转运点；

(3)通过每一段弧的流只允许沿着弧的箭头所指的方向流动。由发点发出的所有弧背向发点,而所有终结于收点的弧都指向收点；

(4)最大流问题的目标是使得从发点到收点的总流量的大小可以用两种等价的方法来衡量,分别叫做从出发点出发的流量和进入收点的流量。

2。根据最大流的定义，与本题目对比，可以将人数的多少与流量的大小相类比，让所有的搜索人员在划分的区域内并排搜索，保证搜索区域不重复并且搜索时间尽可能的少。搜索人员的路径是一个有向的流动，单位时间内通过的人数不可能超过最多人数，每个拐点处通过的人数也应相等，流入的流量应等于流出的流量，即为实际的人数。

三、模型的分析与求解

以20人为一组的搜索队伍，最短搜索路径为图1所示。