1 引言

钻井过程存在着大量复杂和不确定性因素, 钻井事故随时都有可能发生. 当事故发生时, 及时地进行应急救援十分必要. 要使救援人员和物资尽可能最快地到达待救援事故点, 合理地规划最优救援路径尤为重要. 传统的路径规划算法(如Dijkstra算法、A*算法)存在计算效率低、易陷入局部最优等缺点. 近年来, 随着各种基于生物学的智能算法的出现, 蚁群算法在路径规划领域中得到应用. 蚁群算法是一种适于解决组合优化问题的启发式搜索算法, 但当问题规模较大时易陷入局部困境^[1]. 为此, 学者们对该算法进行改进, 如徐坤等^[2]将信息素挥发因子采用莱维飞行模式更新, 提高了算法的全局寻优能力; 王帅等^[3]将蚁群算法与遗传算法结合, 改进算法参数信息, 提高了搜索范围的多样性, 但收敛速度有待改善. 当前, 针对蚁群算法在救援车辆路径规划方面的应用研究还不够完善, 大多是针对多个救援点组合优化支援单个受灾点, 未综合考虑实时路况、天气等因素对救援路径选择的影响. 而对于突发情况下的钻井应急救援, 通常待救援点不止一个, 且油田井场路网复杂, 直接利用基本蚁群算法进行救援车辆路径规划时会存在一定的局限性, 因此, 本文提出基于改进蚁群算法的钻井救援车辆路径规划研究, 旨在为钻井事故应急救援规划出最优的物资配送路径, 以提高应急救援效率.

2 基于改进蚁群算法的路径规划算法 2.1 蚁群算法基本原理及数学模型

蚁群算法是从蚂蚁觅食的群体行为启发而得出^[2], 蚁群在觅食过程中会在其走过的路径上留下一种信息素^[4], 而蚂蚁群体总是倾向在信息素浓度高的路线上觅食, 相同时间内较短路径上的信息素含量最高, 因此蚁群能准确找到食物与巢穴之间的最短路径. 蚁群算法的数学模型通常借助TSP问题进行描述^[5].

蚂蚁k (k=1, 2, …, m)在运动过程中, 根据各条路径上的信息量及路径的启发信息来计算状态转移概率. 在t时刻, 蚂蚁k由城市i转移到城市j的状态转移概率 $ p_{ij}^k(t) $ 定义为^[6]:

$ {p}_{ij}^{k}(t)=\left\{\begin{array}{l} \frac{{\left[{\tau }_{ij}(t)\right]}^{\alpha }\cdot {\left[{\eta }_{ij}(t)\right]}^{\beta }}{{\displaystyle \sum _{s\in allowe{d}_{k}}{\left[{\tau }_{is}(t)\right]}^{\alpha }}\cdot {\left[{\eta }_{is}(t)\right]}^{\beta }},\quad {j}\in allowe{d}_{{k}}\hfill \\ 0, \qquad\qquad\qquad\qquad\qquad 其他 \end{array} \right.$

(1)

其中, $ allowe{d_k} $ 表示蚂蚁k下一步允许选择的城市, $ {\tau _{ij}}(t) $ 为城市i到j的信息素含量; $ {\eta _{ij}}(t) $ 为启发函数, 与路径长度成反比, 即 $ {\eta _{ij}}(t) = 1/{d_{ij}} $ ; α为信息素在路径选择中的重要度; β为启发信息的重程度. 蚂蚁积累的信息素越多, $ {\tau _{ij}}(t) $ 越大, 路径越短, $ {\eta _{ij}}(t) $ 越大, 则蚂蚁选择该路径的概率 $ p_{ij}^k(t) $ 越大.

2.2 改进蚁群算法

基本蚁群算法在求解转移概率时仅依据路径上的信息素含量和路径长度, 未考虑外界影响因素, 如天气、道路拥堵及道路等级等; 另外, 蚂蚁搜索最优解时根据信息素浓度进行状态转移, 若刚开始某路径上累积较多信息素, 蚂蚁会大概率选择该路径, 但此路径不一定最优, 从而导致陷入局部最优. 为此本文在救援路径规划时, 对蚁群算法进行以下两方面的改进:

(1)对转移概率的改进

在实际救援路径选择时, 有的路径虽短, 但由于道路狭窄不平或拥堵等, 通过该路径所需时间反而较长, 因此, 要想规划出一条用时最短的救援路线, 还需考虑影响车辆通行时间的外界因素, 包括天气、道路拥堵及道路等级. 而这些因素对车辆通行的影响程度(即权重)各不相同, 为此本文利用层次分析法(AHP)确定它们的权重^[7]. 先将层次结构分为目标层Z和准则层A, 设目标层的路径权重为W_ij, 准则层各指标为: 道路长度、交通流量、道路等级和天气状况, 它们对于目标层的权重分别为: w₁、w₂、w₃、w₄, 见图1.

为计算权重系数w₁、w₂、w₃、w₄, 根据文献[7]的数据和决策者经验判断, 构造判断矩阵A, 见表1.

利用Matlab编程计算得到矩阵的最大特征值 $ {\lambda _{\max }} $ 为4.0247, 对应的特征向量W为(0.9146, 0.2495, 0.2192, 0.2305), 经归一化处理后为(0.5667, 0.1546, 0.1358, 0.1428), 通过一致性检验后, 可计算出整个网络中各条路径的权重值:

${W_{ij}} = \frac{s}{v} \times ({w_1} + {w_2} \times \varphi + {w_3} \times f + {w_4} \times w) $

其中, w₁、w₂、w₃、w₄为准则层各因素对目标层的权重系数, s为道路长度, v为道路设计的平均时速; $ \varphi $ 为交通流量, 将当前流量与设计的流量作比较, 取值为[0, 1]的实数; f为道路等级, 依据道路设计时速、红绿灯数、适应的交通量划分为5个等级, 赋值为(0.2, 0.4, 0.6, 0.8, 1.0); w为天气状况, 表示车辆行驶的适宜度, 取值为[0, 1]内实数.

将权重值引入式(1)中, 得状态转移概率为:

$ {p}_{ij}^{k}(t)=\left\{\begin{array}{l}\frac{{\left[{\tau }_{ij}(t)\right]}^{\alpha }\cdot {\left[{\eta }_{ij}(t)\right]}^{\beta }{\left[{w}_{ij}(t)\right]}^{\lambda }}{{\displaystyle \sum _{s\subset {{allowed}}_{k}}{\left[{\tau }_{is}(t)\right]}^{\alpha }}\cdot {\left[{\eta }_{is}(t)\right]}^{\beta }{\left[{w}_{is}(t)\right]}^{\lambda }},\;\;\; 若j\in {{allowed}}_{k}\hfill \\ 0, \qquad\qquad\qquad\qquad\qquad\qquad\;\; 其他\hfill \end{array}\right. $

(2)

其中, $ {w_{ij}}(t) $ 为路径(i, j)在t时刻的权重值, λ为权重指数, 根据实际情况和具体要求确定.

(2)对选择路径的策略进行改进

为避免蚂蚁一开始选择路径就陷入局部最优, 改进其选择路径的策略: 为蚂蚁设置一个绝对感觉阈限 $ {q_0} $ , 若路径上信息素的刺激量达到 $ {q_0} $ , 蚂蚁才选择该路径, 否则忽略. 这样蚂蚁在初始阶段不会集中于某些路径, 会选择较多不同路径, 从而在一定程度上削弱算法陷入局部最优的趋势.

第k只蚂蚁按式(3)的概率从状态i转至j:

$ j=\left\{\begin{array}{ll}\mathrm{max}\left\{{\tau }_{is}^{\alpha }\cdot {\eta }_{is}^{\beta }\cdot {w}_{is}^{\lambda }\right\}, s\in {{allowed}}_{k}, \hfill & 若q \leqslant {q}_{0}\hfill \\ 依概率{p}_{ij}^{k}选择j, \hfill & 否则\hfill \end{array}\right. $

(3)

其中, $ {q_0} \in (0, 1) $ , q是(0, 1)均匀分布的随机数.

2.3 基于改进蚁群算法的救援车辆路径规划

现实中钻井救援车辆路径规划问题很复杂, 为便于求解, 本文对有些问题进行了简化: (1)只有一个救援中心, 救援车完成救援后都回到救援中心, 等待下一次救援; (2)仅考虑救援车路上的行驶时间, 不考虑为事故点服务的时间. 设事故点(即待救援点)个数为n, 救援中心有m辆型号相同的车, 由于救援对时间要求高, 因此目标函数是求救援点到达所有事故点用时最少的行驶路线, 定义为:

$ \min Z = \sum\limits_{i = 0}^n {\sum\limits_{j = 0}^n {\sum\limits_{k = 1}^m {{t_{ijk}}} } } $

(4)

其中, $ {t_{ijk}} $ 表示车辆k经过路径(i, j)的时间. 考虑到影响道路通行的天气、道路状况等外界因素, 在求解时本文使用当量长度 $ {D_{ij}} $ 代替实际路径长度 $ {d_{ij}} $ , 其定义为:

$ {D_{ij}} = \left( {1 + {f_{ij}} + {\varphi _{ij}} + {w_{ij}}} \right) \times {d_{ij}} $

(5)

其中, $ {f_{ij}} $ 、 $ {\varphi _{ij}} $ 、 $ {w_{ij}} $ 分别表示道路状况、交通状况、天气情况等因素对救援路径选择的影响. 其影响程度系数 $ \gamma $ 的计算方法为: 设考虑和不考虑某影响因素时通过路径(i, j)的时间分别为 $ {T_{ij}} $ 、 $ {t_{ij}} $ , 则:

$ \gamma = \frac{{{T_{ij}} - {t_{ij}}}}{{{t_{ij}}}} $

(6)

假设当前路段(i, j)车辆所占车道的交通流量为 $ \varphi $ , 其理想流量为 $ {\phi _{ij}} $ , 当前车辆行驶速度为v, 则当前路段上平均行车速度为: $ {v_{ij}} = v \times \dfrac{\varphi }{{{\phi _{ij}}}} $ , 因此行驶时间为: $ {t_{ij}} = \dfrac{{{D_{ij}}}}{{{v_{ij}}}} $ .

由于本文路径规划的目标函数是求取救援时间最少的路径, 因此利用蚁群算法求转移概率时, t时刻蚂蚁k从节点i转移到节点j的启发函数为:

$ {\eta _{ij}}(t) = \frac{1}{{{t_{ij}}}} $

(7)

3 仿真实验

为了验证本文所提出的路径规划算法的有效性, 采用Matlab编程实现该算法并进行如下实验: 建立有12个节点的路网, 节点0为救援中心, 节点1~节点11表示各事故点, 现救援车需从节点0将物资运送到各事故点进行救援, 各事故点的坐标及其物资需求量见表2.

蚁群算法相关参数设置为: 蚂蚁数量m=20, $ \alpha = 1 $ , $ \;\beta = 1 $ , 权重指数 $ \lambda = 2 $ , 通过求解得到最优路径规划结果和每次迭代的最短路径见图2, 其最优路径为:

0→3→8→9→5→0; 0→1→11→6→2→4→0; 0→7→10→0, 救援路径全长为: 498.8.

若采用基本蚁群算法进行救援路径规划(见图3), 通过求解得到的最优路径为:

0→3→8→9→5→11→1→0; 0→6→2→4→10→0; 0→7→0, 救援路径全长为: 451.3.

从以上结果可以看出: 利用改进的蚁群算法进行路径规划得到的救援路径总长度比基本蚁群算法得到的路径总长度有所增加, 但前者考虑了真实路网中影响车辆运行时间的外界因素(如天气、交通流量等), 其路径更切实际, 且算法在收敛速度、最优解的搜索空间方面都有较大的提高, 从而使实际上完成救援物资配送所需的总时间更短.

4 应用实例

我们结合所承担的陕西省自然科学研究计划项目“基于物联网的油田事故灾难应急救援向导式动态管理方法研究”, 依据本文提出的路径规划方法, 开发了“油田事故应急救援物资配送路径规划系统”, 并选择了XX油田发生过多次事故的典型区块对系统进行了应用测试. 以XX油田的典型钻井区块为例, 事故点分别为YC_101、YC_102、YC_103、YC_104、YC_105、YC_106、YC_107、YC_108、YC_109、YC_110, 其位置分布见图4, 救援中心用 $ \therefore $ 标注, 事故点用 $ 0 $ 表示, 设各事故点救援物资需求量(单位为t)分别为0.2、1.2、1.5、0.6、0.7、1.6、0.4、0.7、1.3、0.6, 利用本文算法求出的最优救援路经(见图4不同颜色标注)为:

① 救援中心→YC_107→YC_103→YC_102→YC_101→YC_106→救援中心

② 救援中心→YC_109→YC_110→YC_105→YC_104→YC_108→救援中心

根据以往该区块的事故救援情况, 上述路径规划结果与实际路网相符.

5 结论

利用改进蚁群算法进行钻井救援车辆路径规划的方法, 不仅保留了基本蚁群算法的优点, 还克服了它易陷入局部最优的缺点, 同时由于考虑了影响道路通行的外界因素, 使整个算法具有更强的实用性. 通过仿真实验与应用测试表明, 该路径规划方法能满足油田钻井应急救援应用要求.