基于拉格朗日松弛的水灾逃生路径规划

锁启凤，张仲荣，窦 站

(1.兰州交通大学数理学院，兰州 730070; 2.中国科学院海西研究院泉州装备制造研究所，泉州 362200；3.北京化工大学机械工程学院，北京 100029)

在交通路网中选择一条最短路径问题被称为标准最短路径(shortest path, SP)问题，该问题可以通过一些有效的算法得到最优解决，如Suzuki等[1]通过启发式算法解决多目标车辆路径优化问题。Zhao等[2]提出多目标启发式函数的蚁群算法解决冷链物流配送路径优化问题。然而出行者希望选择的路径不仅最节约时间，而且其他资源(如长度、油耗等)不能超过预设值，则有了约束最短路径(constrained shortest path, CSP)问题。CSP问题最早由Witzgall、Goldman和Joksch提出并研究[3]，该问题包含一个或多个有上限的附加约束，在实际生活中应用广泛[4-5]。附加的约束使得CSP问题是一个NP难(non-deterministic polynomial hard)问题[6]，因此CSP问题与SP问题不同，不能直接通过标号设置或标号修正算法来解决。近几十年来，研究人员提出了一些有效的算法来求解CSP问题。如Rivera等[7]利用动态规划方法求解单边约束的CSP问题，提出了基于流程的模型和集合划分模型。现实路网中存在不确定因素，如通过某路段的时间、疏散人员的数量以及道路通畅情况等。近年来，研究人员对CSP问题中的不确定因素很感兴趣，Liu[8]系统地提出了不确定随机网络的概念。Wang等[9]考虑到疏散时间的不确定性，提出了一种计算每条路径的模糊期望行程时间的有效方法。Shen[10]考虑交通路网中的诸多不确定因素提出城市物流配送路径优化模型。

目前CSP问题大多仅在确定性条件下考虑，随机条件下的CSP问题得到关注较少。因此考虑不确定路网随机条件下的CSP问题非常有意义。为找出满足多个约束的最小期望通行时间路径，首先提出用随机出行时间来表示交通网络的不确定性随机约束最短路径问题(stochastic constraint short-circuit problem, SCSP)。同时，为了刻画路段通行时间的相关性，采用路网的联合概率质量函数来表示路网通行时间。其次针对SCSP问题，建立一个0-1整数规划模型来寻找期望时间最小的先验最优路径，引入唯一的通路选择约束以确保最终只生成最优路径。接着设计一个基于拉格朗日松弛的算法框架来解决提出的模型。提出拉格朗日松弛法，将难约束松弛到目标函数中。松弛模型可以进一步分解为两个子问题。一是每个支点上的标准SP问题，可以通过标号修正算法解决;二是通过给定的拉格朗日乘子可以得到的常数。最终提出最小上界和下界间隙的次梯度算法嵌入k-最短路径算法，以解决在求解松弛模型时生成路径的不可行性问题。

1 问题描述

图1 疏散路网示意图

2 模型建立

2.1 目标函数

(1)

(2)

2.2 约束条件

(3)

(4)

(5)

(6)

s.t.

(7)

与传统疏散时间固定的模式不同，式(7)在疏散时间是一个随机变量的基础上建立。设计拉格朗日松弛算法，将难约束松弛到目标函数中，采用次梯度算法嵌入标号修正算法及k-最短路算法求解最优值。

3 算法设计

3.1 拉格朗日松弛算法

拉格朗日松弛算法起源于20世纪60年代，基本思路[12]是在原模型的目标函数中引入几个拉格朗日乘子，将模型中的难约束吸收到目标函数中，把原模型松弛成一个较容易求解的拉格朗日对偶模型。

定理1松弛模型(ZLR)与只包含简单约束的原模型(ZIP)有相同的复杂度，如果包含了难约束的原模型(ZIP)可行域非空，则∀λ≥0⟹ZLR(λ)≤ZIP，其中λ称为拉格朗日乘子。

(8)

整理得松弛模型为

mints(β,χ,δ,γ)=

(9)

进一步将松弛模型分为两个子问题，给定拉格朗日乘子后，子问题2是一个常数，子问题1可以看作是所有家庭的最优路径之和，因此只需求解单一家庭疏散路径问题。

子问题1：

ZP1S(β,χ,δ,k,s)=

(10)

子问题2：

(11)

(12)

根据定理1知，原模型的最优解求解为

(13)

3.2 次梯度算法

次梯度算法可有效求解拉格朗日松弛问题[13]，该算法通过调整拉格朗日乘子更新模型的下界及上界。迭代过程中，下界是每组拉格朗日乘子对应的松弛模型的最优目标值，上界是O-D所有可行路径的最小有效通行时间。不超出迭代上限的前提下，随着迭代次数的增加，下界逐渐上升。上下界之间的差值越小说明得到的近似解的质量越高。如果上下界间的差值为零，说明得到精确解。由于考虑了边际约束，松弛模型的解不一定为原模型的解，用k-最短路算法调整非可行解。设计算法的步骤如下。

Step 1初始化。

Step 2求解松弛模型。

(1)用标号修正算法求解子问题1，进而求解模型(9)的最优解，记为下界。

(2)判断(1)得到的解可行与否，可行转至Step 4，否则转至Step 3。

Step 3执行调整算法调节不可行解。

Step 4计算差值。

(1)计算模型(7)的目标值，记为上界。

(2)计算上下界间的差值。

Step 5更新拉格朗日乘子。

(14)

(15)

已有学者证明了φk在次梯度算法中的有效性[14]，其中λk是大于0小于2的标量，初始量λ0取0。UBk和LRk分别为第k次迭代模型的上界和下界。

(16)

Step 6终止。

若迭代次数k>kmax(kmax为最大迭代次数)或者上下界差值小于预设阈值，算法终止；否则，令k=k+1，转至Step 2。

3.3 标号修正算法

算法的主要特征是：为每条路段设置一个距离标号用于表示在一定的限定条件下起点到该节点的最短路径。迭代计算中所有的距离标号都是临时标号。计算结束时，取消限定条件所有临时标号转变成永久标号。

3.4 k-最短路算法

k-最短路删除路径算法的主要思想是[15]：给定有向图G(V,A),V是节点集合,A是弧集合，假设图G删去最短路径p0得到图G1，则图G的第二短路径p1是图G1中的最短路径，图G的第三短路径是删去p1和p2后的G3的最短路径，依次计算得到前K条最短路径。

4 算例分析

将设计的框架应用于如图2(b)所示的福建省龙岩市何家陂水库下游的居民区验证其有效性。居民区路网为如图2(c)所示的具有67个节点99条路径的中等规模路网。为保证数据更接近实际情况，用ArcGIS缓冲出疏散路段的长度及宽度，缓冲出宽度的路网如图3所示。路网的破坏程度与灾害强度成正比。将灾害强度分成九个场景，基于场景的通行时间根据灾害强度在[4 180]内以升序的形式随机生成。各场景发生的概率根据路网破坏程度以降序的方式生成；路段通行能力根据路段宽度以升序的方式生成。从不同O-D及不同场景数量两方面设计试验。计算的过程中将模型的上界设为常数，通过不断更新下界得到最优解。算法运行于Microsoft Visual Studio 2015软件平台上，计算机CPU为inter(R)Xeon(R)E5-2699 V4 @2.20 GHz,内存416 GB,操作系统为Windows 10.0。

图2 研究区域

图3 带有路面宽度的路网

图4是9个场景下寻找O-D(57-10)的最优路径的迭代过程。迭代 15 次的结果显示，随着拉格朗日乘子更新，前7次迭代得到的解不断更新，第8次迭代解不再改进，表明已找到最优路径。

图4 上下界趋势

表1给出 200 个家庭，5组O-D中 7 个不同场景数量的试验结果，场景数量分别为3，4，5，6，7，8，9。分析不同场景数量的计算结果可知，除场景5外，其他场景最优解上下界的相对差值稳定在 1.40%～2.20%，场景5中，找到的最优路径有最小的期望通行时间，但它的路径长度和广义消耗较大因此相对差值为9.66%。为了更直观，图5给出不同场景下上下界的差值。其中，相对差值计算公式

图5 上下界差值

表1 不同场景数量的计算结果

(17)

式(17)中：UBk和LRk分别为最优解的上界和下界。

O-D(61-16)的试验结果如表2所示，当边际约束路径长度上限设为3 800 时，计算出的最优路径为第 10 组结果。而路径长度上限设为4 000 时，得到的最优路径为第11组结果。5 组不同O-D的最优路径如表3所示，图6是实际地图中O-D(61-16和57-10)的最优路径。

图6 O-D(61-16和57-10)的最优路径

表2 O-D(61-16)的实验结果

表3 不同O-D的最优路径结果

5 结论

SCS问题是求解随机交通网络中带边约束的最优出行时间路径。通过考虑随机环境下的边际约束，生成的最短路径可以帮助逃生人员规划路径。针对SCSP问题，首先建立了具有随机时间的0-1整数规划模型。为了降低SCSP模型的计算复杂度，采用拉格朗日松弛法将难约束对偶化为目标函数。松弛模型可以通过精确的标号修正算法来求解。在此基础上，提出了一种嵌入k-最短路径算法的次梯度算法，该算法可以使上界和下界之间的间隙最小，从而得到最优解。将该框架应用于龙岩市新罗区示例中，实验网络的上界和下界之间的相对差距相当小，这表明所提出的模型和算法框架的有效性。基于此框架进一步的工作可以建立考虑路段高程的逃生路径规划模型。