消防出警路线选择算法的研究

瞿诗高 (长江大学工程技术学院,湖北荆州434020)

我国每年有大量的火灾发生,对人民生命财产安全造成了严重的威胁。如果能够提高消防战士的出警速度,减少消防官兵到达火灾现场所需要的时间,将会极大地减少火灾带来的损害。我国现有的消防系统在出警道路的选择上采用人工方式,即由调度人员根据火警现场、道路等情况为出警战士选择和指示出警道路。当可选道路较多、人流等复杂情况下,调度人员就无法确保选出最优出警路线。为此,笔者基于遗传算法研究了一种消防出警道路选择算法,利用该算法可选择最佳消防出警路线,从而保证消防战士利用最短出警时间到达火警现场。

1 数学模型

1.1 主要定义

使用有向图G(V,E)表示当前的道路交通图(见图1)。其中,V={v0,v1,…,vn},是道路的拐点的集合,v0是消防队的位置;E为道路的集合,其元素eij用于描述从道路节点vi到vj的道路,该元素使用三元组(lij,wij,dij)进行描述,其中lij表示道路的长度,wij表示道路的宽度,dij表示道路当前的人流密度。

Psd表示从节点vs到节点vd之间的通路表达式:

图1 有向图G(V,E)

1.2 相关计算

消防车通过道路eij的时间为tij,即:

式中,v表示当前消防车的行驶速度,m/s。

消防车通过通路Psd的时间Ts d为消防车通过道路eij的时间之和:

通路Ps d的长度L(Psd)表示该通路上所有道路的长度之和:

1.3 优化目标的设定

由于消防出警的目标是以最快的速度到达火警现场,因此,将消防出警道路选择问题描述为:已知道路交通情况,包括每条道路的宽度、长度、人流密度等的情况下,将车辆出警时间最小化,同时将出警通路长度最小化,即在有向图上寻找2个目标节点之间的一条可行路径 (见图2)。

图2 节点1-节点5之间的一条可行路径

2 消防出警路线选择算法

路径选择算法是NP难问题[1],当消防出警路线较多时,可选择遗传算法[2]求解。下面对该算法进行具体描述。

2.1 解的编码

采用数值编码方式,遗传算法中的每个染色体对应一个解,染色体的长度等于n(n代表道路交通路中的节点数量);基因值为0,表示对应的道路拐点在通路上,否则不在。由此,染色体是以1开头的一组基因。种群中的染色体是随机生成的,种群规模为P。染色体中的基因组可能无法构成一条通路,否则为不合法染色体,应由新生成的染色体替换。

2.2 适应度函数设计

将Tsd和L(Psd)的加权和作为算法的适应度函数:

式中,s是问题的解;α和β代表权重系数,α+β=1,由于减少时间是最重要的优化目标,因而α需要占更大比例。

2.3 遗传算子及算法中止条件

1)遗传算子 遗传算子分为如下3种:①交叉算子。在交叉操作中采用单点平行交叉策略,随机选择某个基因位执行交叉。②变异算子。在变异操作中也采用单点变异策略,根据交叉概率用随机生成的新数值替换随机选取的基因位al的值。为保证新的染色体合法,新基因位的取值范围要满足解的编码规范。在进化过程中,每代的最优染色体不参与变异操作。③选择算子。选择操作中应用精英保留策略,即最优染色体直接进入下一代种群中,其余染色体通过赌轮法进行选择[3]。

2)终止条件 使用最大不进化代数作为算法终止条件,若安全阀中的精英染色体经过最大进化次数后仍没有更新,即种群没有进化,则算法结束。

2.4 算法流程

使用遗传算法的基本步骤如下:①根据结点编码和种群规模P,随机生成P个染色体,作为初种群。②根据式 (5)计算每个染色体的适应度函数值即适应值。③根据交叉和变异算子对种群执行交叉和变异操作,则种群中规模会增加。④根据选择算子执行选择操作,使新种群的规模恢复到P。⑤根据终止条件,判断是否满足终止条件,如果不满足终止条件,则转步骤②。⑥算法结束。

3 仿真试验

大连市局部道路交通图如图3所示。笔者根据该交通图进行仿真试验。种群规模取20,消防站的位置和起火点从节点中随机选择,试验数据为算法运行500次所得结果的平均值。试验结果如表1所示。

从表1可以看出,随着最大不进化代数的增加,算法的解与最优解适应度比值也随之增加,说明解的搜索空间增大,算法的解在逐步优化。仿真试验表明,利用该算法可以选择最优消防出警路线,从而保证消防战士在最短时间内到达火警现场。

表1 算法解与最优解的比较

图3 大连市局部道路交通图

4 结 语

为解决消防战士出警道路选择的问题,研究了基于遗传算法的出警道路选择算法。仿真试验表明,笔者提出的算法是可行的,并且可以获得与最优解较为接近的近优解,从而解决目前国内消防出警依靠人工调度的问题。

[1]王宇,许都.多约束路由的简单求解方法 [J].计算机应用研究,2007,24(11):268-277.

[2]刘立平,牛熠.遗传算法综述 [J].东莞理工学院学报,2005,12(3):68-72.

[3]吉根林.遗传算法研究综述 [J].计算机应用与软件,2004,21(2):69-73.