基于双层规划模型下的路径安排问题研究

杨甜甜，石建军，刘金超

(1.北京工业大学;2.北京市交通工程重点实验室)

1 交通网络描述

在一个多起点多讫点的强连通的交通网络G(N，A)中，定义N 为网络节点的集合;A 为有向路段集;r、s 分别为出行起点和讫点;a(l，m)为节点l 到m 的路段;Al和Bl分别为进入和离开节点l 的路段集合;la表示路段a 的起点，ma表示路段a 的终点;对于∀t∈［0，T］引入一下变量。

Mrs:起讫点rs 之间所有出行者构成的集合;

τa(t):时刻t 进入路段a 的交通流通过路段a 所需要的实际时间;

θz:出行者z 对禁行的敏感度;

根据元胞传输模型(CTM)的特点，我们能够计算出模拟车辆的路段平均出行时间τa(t)

由式(1)可以得出，出行者从路段a1到达讫点s 的出行时间可以按式(2)进行计算

由先进先出条件，(t－1)+τa(t－1)＜t +τa(t)，当时，

拥堵延误是指除自由流走行时间外车流通过元胞的附加时间，由此我们可以得出

当交通路网中某一路段产生拥堵时，说明此路段属于非正常行驶路段，后续车辆不能通过此路段完成正常通行，需进行道路的换行。对此，我们定义禁行区域割集(L·)的概念，即一个路段的集合，当集合中这些路段被移除时，外部出行者将无法通过该禁行区域(如图1)。基于此，我们可以抑制交通拥堵的产生，达到缓解拥堵的目的，并进一步改善禁行区域内的交通拥堵，在总体上提高路网的性能。

图1 禁行区域图

2 下层目标规划

当路网中的某些路段处于拥堵状态时，出行者(驾驶员)在出行过程中就会出现路径的选择行为，而这种行为包括出行者原本计划驶入的路段属于禁行割集路段以及未驶入但以一定的敏感度重新进行路径的选择。

对于做出这些路径选择行为的出行者，我们可以做出如下的假设。

(1)对于在交叉口进行路径选择的出行者而言，路网结构已经发生变化，出行者在进行路径选择的时候不能选择进行区域内部的路段以及下属路段。

(2)由于拥堵的发生，出行者无法像往常一样进行正常行驶并对现实路况进行估计，只能根据经验进行选择，而其选择的依据则是其对各个时刻，当路网不发生拥堵时的的经验阻抗，这样，出行者采恩那个尽快的抵达目的地，完成出行过程。

由以上的假设，我们可以给出出行者在禁行期间根据自身经验在交叉口的平均走行时间的路径选择行为。

式(8)目标函数描述了出行者的路段选择行为，当遇到车辆禁行后，出行者会根据路段经验平均出行时间在后续的决策点上选择尽快到达出行讫点的路段，也就是说，在任意时刻根据路段经验阻抗进行一次全有全无分配。ub(t)=表示路段的流入量与出行者路段选择结果的集合是等价关系。

中央控制指挥中心(RCCC =route choice control center)利用自身的优势，给出行者提供未知的路况，辅助出行者进行决策。在交通拥堵状况下，当出行者需要进行路径选择时，中央控制指挥中心接到请求信息后，给出行者下发路径路况信息，使得出行者在没有遭遇拥堵排队之前，提前了解前方路况，在到达拥堵区域之前提前分流，使进入拥堵区域的出行者减少，进一步抑制拥堵的传播。

基于中央控制指挥中心的分流，做出如下假设。

(1)该控制方式是反应式的，即当驾驶员进行路径请求的时候才会给出行者下发相应的路径信息，因此对于控制中心来说，只有当出行者进行路径请求时，其才会对路网中的车辆进行预测。

(2)没有向控制中心发送请求信息也没有接受可变信息诱导的出行者，在其出行过程中，我们可以将其当成定量因素分析，其出行路线不改变。按原计划进行行驶。

(3)接受RCCC 路径安排(路径诱导)信息的出行者，在后续的交叉口根据路段实际走行时间选择到达目的地的路段集合。所以对于接受由RCCC 安排路径的出行者来说，在拥堵期间内，他们所行驶的路线已经处于均衡状态，想单方面通过改变路径更快的完成行程(降低出行阻抗)是不可能的。

所以接受控制中心路径安排(路径诱导)的出行者z∈I·的达到均衡状态需满足以下约束条件

根据式(9)、(10)、(11)不等式我们将出行者限定为接受了控制中心路径诱导的用户，而这些不等式是基于路段实际阻抗动态用户均衡条件的变形。其中路段的流入量等价于出行者对路径选择结果的集合。即

图2 车辆诱导示意图

如图2 所示，假设在路段1 出行者对控制指挥中心发出路径请求，控制中心接受并受理出行者的请求，在控制指挥中心作用时段内离开该路段的出行者都将受影响。假设原本计划通过路径1→30→11→36→21 到达出行讫点17 的出行者，控制中心接到请求后根据路网检测得知路段36 发生拥堵并蔓延至路段11，此时，控制中心会在尽量减少出行者用时的情况下，为其安排路径并在驶出相应路段后重新建立对路径的选择，在之后的交叉口选择使其尽快到达出行终点的路段，如路径1→30→28→19→21 或是1→3→38→13→44 完成出行。

根据以上假设，我们可以用下面的模型来描述受控制中心路径诱导影响的出行者在交叉口的路径选择行为

向控制中心(RCCC)进行路径请求的出行者的集合为

用该目标函数的变分不等式可以描述出行者的路径选择行为，出行者在控制中心路径诱导的作用下根据路段实际走行时间，在后续的决策点选择尽快到达出行讫点的路段集合的行为。

3 上层目标规划

对于交通管理者来说，其想要达到的是整个系统的路网最优，而若达到这种最优状态，则需保证在路径诱导之前使得整个路网的总阻抗达到最小。对于这个问题，我们可以通过区域割集的概念来解决。当禁行区域确定后，我们只需确定哪些交叉口可以通过，哪些属于禁止的。我们可以用一个变量来描述一个交叉口在路径诱导控制期间是否通行还是禁止。例如，给定一个交叉口i，xi=1 表示该交叉口在路径诱导控制期间不能够正常行驶通过，即i∈L·;而xi=0 表示该交叉口在路径诱导控制期间可以正常通行，即i∈/L·。

我们把拥堵延误和自由走行时间作为系统总阻抗，在一定程度上，它们能够更好更直接的反映交通网络的拥堵程度和路网状态。因此交通管理者将最小化系统广义费用(本文采用系统总行程时间)作为上层目标来研究，以期达到系统最优。则上层问题可以描述为如下优化问题:

s.t.

基于此，我们构建出了出行者和交通管理者在控制指挥中心作用下的路径诱导的双层规划模型。

4 案例分析

4.1 方案设计

为了验证所提出的规划模型，文章选取实际路网中的某一区域作为仿真参考区域，如图3 所示，该路网中有20 个交叉口，30 个路段。仿真长度为12 格、9 格等(一格代表实际路段的长度为200 m)。为了更加细致的描述车辆的运行状态和交通流的实时分布状况，路段和交叉口并没有按同比例进行缩放。路网中各路段的实际长度和仿真长度见表1，其中实际长度的单位为m，仿真长度的单位为格。各参数如下:时间间隔，主路的速度限制为60 km/h，服务流率为1 800 pcu/h/车道，次要道路速度限制为40 km/h，服务流率为1 800 pcu/h/车道。

表1 仿真路网路段长度

图3 实际路网图

在仿真过程中，设置了三种情境。见图3。

情境1:路网中的出行者不接受任何外界信息，在给定目的地后，出行者完全根据自己的经验进行路线的选择。情境2:路网中的出行者接受传统导航给出额路线信息，如出行时间、出行距离、路线的复杂度、平均速度等等。但是出行者得到信息后还是根据自己的经验进行路线的选择。情境3:出行者接受来自控制中心(RCCC)给出的信息，并按照RCCC 给出的动态系统最优路线进行行驶。

在三种情境下各在三种不同的交通量下进行仿真:低交通量(14 000 vph)、中等交通量(2 8000 vph)、高交通量(42 000)。见图4。

图4 仿真界面图

4.2 分析及结果仿真结果见表2，表3，表4。

表2 仿真结果(低交通量)

表3 仿真结果(中等交通量)

表4 仿真结果(高交通量)

从仿真结果看以看出，在低交通量的情况下，不同情境下的路网状态差异很小，这个时候整体路网的交通状况很好;在中等交通量的情况下，情境2 和情境3 都能够改善路网状态，但是情境3 相对于情境2 下平均速度要高，平均出行时间要低;在高交通量的情况下，情境3 下比其他两个情境下更能够改善路网状态。但是当交通量继续增大时，在情境3 下也不能够有效的改善路网状态，因为此时路网中已没有可替代的路径可供选择。

图5 不同导航装配率的平均区间速度

图6 不同导航装配率的平均区间行程时间

图7 不同导航装配率的平均出行距离

从图5，图6，图7 不同装配率的仿真结果图可以看出，在情境2 下的最佳传统导航的装配率为45%，此时平均速度达到最大值而平均出行时间达到最小。在情境3 下，新型的系统导航仪(基于RCCC)的最佳装配率为65%，此时平均速度达到最大，平均出行时间达到最小。也就是说，路网性能达到最优，此时的路网最为畅通，交通流分布均衡。

当路网达到最优状态时平均出行距离并没有达到最小值，因为为了整体路网的性能，有时会建议车辆绕行，以保证大多数驾驶员的利益。

情境3 下的的最佳装配率比情境2 的最佳装配率要高，这意味着，当驾驶员和路网系统管理者进行协商后，可以更加有效的改善路网的性能。

5 结 论

双层规划问题是现如今的NP 难题，其模型的搭建求解过程是非常复杂的。对于求解双层规划问题，比较广泛的一类方法是非数值优化方法。本文中使用遗传算法进行求解。而具体的优化算法及相应的分析还需要相关的编程来实现。

以动态网络交通流为背景，探讨了基于控制中心解决交通网络拥堵问题。道路发生拥堵会使得出行者进行路径选择，出行者的路径选择又会产生新的交通问题。而交通管理者希望整体的路网达到系统最优。出行者依据控制指挥中心计算出来的最优系统路径进行行驶，因此，该问题可以描述为一个双层规划问题。上层为交通管理者希望达到的最优目标，下层问题描述出行者的路径选择行为。通过案例分析表明了模型的可行性。通过对该双层规划问题进行求解以期望采用控制指挥中心给出的路径能够使得出行者和交通管理者达到共赢。在达到为车辆安排路径的基础上，车辆能够按照中心给定的路线和速度进行行驶，这可以在宏观上达到节能减排的作用。并考虑到，随着技术的革新，无人(自动)驾驶成为一种可能。希望在此基础上，能够为以后车辆的自动驾驶安排路径。

［1］罗朝辉，梁碧清，韦增欣.动态交通方式划分与系统最优配流模型［J］.河北科技大学学报，2012，33(1):79－82.

［2］高自友.现代物流与交通运输系统［M］.北京:人民交通出版社，2003.

［3］高自友，任华玲.城市动态交通流分配模型与算法［M］.北京:人民文通出版社，2005.

［4］龙建成.城市道路交通拥堵传播规律及消散控制策略研究［D］.北京:北京交通大学，2009.