突发性片堵塞下两车信息共享的加拿大旅行者问题

苏 兵，林 刚，程新峰，孙璐璐

(西安工业大学经济管理学院，陕西 西安 710032)

1 引言

加拿大旅行者问题(Canadian Traveler Problem，CTP)是指旅行者从起点出发去终点的过程中遭遇无法预知突发性堵塞下如何制定实时路径选择策略使花费时间尽可能少的问题[1-2]。对这个受不确定因素影响较大的问题，国内外学者采用在线问题与竞争策略的理论开展了相关研究[3-6]，主要讨论了堵塞信息完全未知和有限预知情形下的单一路段堵塞的单车路径选择策略。对于堵塞信息完全未知的情形，建立一般网络中路段堵塞不可恢复下的单车在线路径选择模型，设计贪婪策略和复位策略并证明策略竞争比[7-10]；建立方格路网中路段堵塞不可恢复下的单车在线路径选择模型，设计方向贪婪策略和多选择移动策略并证明策略竞争比[11]；建立连续网络中路段堵塞可恢复下的单车在线路径选择模型，设计等待策略和移动策略并证明策略竞争比[12]。对于堵塞信息有限预知情形下即单车到达某一节点时可以预知相邻节点一条关联边堵塞信息，建立一般离散网络中路段堵塞可恢复的单车在线路径选择模型，设计等待策略和贪婪策略并证明策略竞争比，建立一条路上路段堵塞可恢复的单车在线路径选择模型，设计混合策略并证明策略竞争比[13-15]。现有加拿大旅行者问题研究主要是在单车遭遇突发性路段堵塞的假设下进行的。然而在实际中，网络中经常会发生片堵塞，即多条相关联路段同时堵塞的情形[16]，物流企业也经常会派出多辆车组成车队从相同起点到目的点进行货运，如果在运输过程中会遭遇突发性片堵塞，若每一车辆都能有限预知堵塞信息且车辆间可以进行信息共享，如何制定多车行进策略使车辆所花费的总时间尽可能少是亟待解决的难题，但此问题在以往研究中未涉及。

针对该问题，本文假设车辆数为2，提出突发性片堵塞下两车信息共享的加拿大旅行者问题，采用在线问题与竞争策略的理论和方法，建立在信息有限预知即车辆到达某一节点(预知点)时可以预知相邻节点的多条关联路段所构成的片堵塞信息情形下的两车在线路径选择模型，设计混合贪婪策略，分析策略在所选路径是否经过信息预知点到片堵塞起始点的路段(预知路段)等不同情形下车辆的总费用，证明混合贪婪策略的竞争比，并用实例验证模型和策略的有效性。

2 问题描述与基本假设

图1 问题描述示意图

为了便于讨论问题，提出以下基本假设。

(1)两车在到达预知点时可以获知片堵塞中各条边的堵塞信息；

(2)k个片堵塞RB={RB1,…,RBλ,…,RBk}相互独立，且依次顺序出现；

(3)G在删除堵塞边集Eλ之后依然连通；

(4)两车遇到的片堵塞皆为树形片堵塞即以一个节点为中心，与之相关联多条边发生堵塞；

(5)片堵塞中每条路段的堵塞都是可恢复的，并且在到达下一个预知点时，上一个片堵塞已经恢复畅通。

以上问题是一个在线问题，可以设计有效的在线策略来解决。假设Copt(R)是该问题对应离线问题的最优费用，CA(R)是问题在所设计在线策略A下的费用，如果存在与序列事件无关的常数α和β使得CA(R)≤αCopt(R)+β成立，则称α为策略A的竞争比。竞争比是对在线策略执行效果的衡量, 如果竞争比较大,说明在线问题在所设计策略下的费用同与之对应离线问题的最优费用偏离较大，竞争比越接近于 1, 策略的执行效果越好。

3 两车信息共享的片堵塞加拿大旅行者问题策略设计及其竞争比

在实际中通常会采取让两车同时出发且按照同一路径行进的策略，一旦这一路径发生突发性堵塞，则两车均会因遭遇堵塞而蒙受时间损失。因此，是否可以选择让两车分先后出发，先出发的车可以发送信息，后出发的车可以接收信息。当先出发的车遭遇堵塞时，迅速将堵塞信息传递给后出发的车，使得后出发的车能够据此做出路径选择，最终使得两车花费的总时间尽可能的少。

策略设计思路：让1辆车先沿最短路径从u1点出发后在u2点预知到片堵塞，并将堵塞的时间与位置信息传递给仍在u1点等待的另1辆车，当两车预知到堵塞信息后会进行如下判断，若任意一车预知路段的通行时间大于最短路径上堵塞边的恢复时间，则该车沿最短路径行进即可，若任意一车预知路段的通行时间小于最短路径上堵塞边的恢复时间，则根据预知路段长度与绕行临界值的大小关系的比较，来确定重选的最短路径是否经过预知路段，得到重新选出的最短路径，该车沿新最短路径行进。当每次遇到堵塞时都按照这种原则进行决策，本文将这种原则称为混合贪婪策略。

3.1 混合贪婪策略

令两车分别为C1车和C2车，C1车的预知路段定义为C1-预知路段，C2车的预知路段定义为C2-预知路段。

混合贪婪策略(M-GSA*)，两车分先后从u1点出发，C1车沿事先选定的最短路径行进，当C1车到达u2点后C2车出发，两车行进规则如下：当遭遇片堵塞RB1时①若C1车在u2点预知到u3点的关联边发生片堵塞，则u2点为预知点，此时C1车在预知点将片堵塞信息传递给C2车，然后C1车比较C1-预知路段长度与对应绕行临界值的大小关系后，重选最短路径行进，而C2车也比较C2-预知路段长度与对应绕行临界值的大小关系后，重选最短路径行进。②若C1车在u2点未预知到堵塞，则两车沿最短路径行进，当C1车预知到片堵塞后将片堵塞信息传递给C2车，然后C1车和C2车分别比较对应预知路段长度与对应绕行临界值的大小后，重选最短路径行进。当遭遇片堵塞{RB2,…,RBλ,…,RBk}时，任意一车遭遇到片堵塞后，根据同一原则处理直至最终到达vn。

混合贪婪策略的具体情形如图2所示。

图2 混合贪婪策略情形分析图

3.2 混合贪婪策略的竞争比证明

令S(v1,vn)和T[S(v1,vn)]表示在出行前选定的未遭遇突发性片堵塞的从v1到vn的最短路径及其通行时间，S′(v1,vn)和T[S′(v1,vn)]表示删去遭遇片堵塞中的边后的从v1到vn的最短路径及其通行时间。

下面对策略的4种情形进行分析。

此时C1车沿预知路段行进比不经过预知路段所用时间要少，同样C2车沿预知路段行进比不经过预知路段所用时间要少，此时该情形下的最坏情况为两车都会经过片堵塞中的某条堵塞边。如图3所示。

图3 情形1下混合贪婪策略的竞争分析

在情形1下，混合贪婪策略下所花费的时间计算如下。

当遭遇1个片堵塞RB1时，

当依次遭遇2个片堵塞RB1，RB2时，

运用数学归纳法，依次类推可得当遭遇k个片堵塞时混合贪婪策略所花费的时间为：

该在线问题对应的离线问题的最优时间为COPT=2·T(S(v1,vn))

此时C1车沿预知路段行进比不经过预知路段所用时间要少，而C2车不经过预知路段比沿预知路段行进所用时间要少。该情形下C1车经过片堵塞中的某条堵塞边，而C2车选择从预知点的前一节点绕行。如图4所示。

图4 情形2下混合贪婪策略的竞争分析

在情形2下，混合贪婪策略下所花费的时间计算如下。

当遭遇1个片堵塞RB1时，

当依次遭遇2个片堵塞RB1，RB2时，

运用数学归纳法，依次类推可得当遭遇k个片堵塞时混合贪婪策略所花费的时间为

该在线问题对应的离线问题的最优时间为COPT=2·T(S(v1,vn))

此时C1车不经过预知路段比沿预知路段行进所用时间要少，而C2车沿预知路段行进比不经过预知路段所用时间要少。该情形下C1车选择从预知点绕行，而C2车经过预知路段并经过片堵塞中的一条堵塞边。如图5所示。

图5 情形3下混合贪婪策略的竞争分析

在情形3下，混合贪婪策略下所花费的时间计算如下。

当遭遇1个片堵塞RB1时，

当依次遭遇2个片堵塞RB1，RB2时，

运用数学归纳法，依次类推可得当遭遇k个片堵塞时混合贪婪策略所花费的时间为

该在线问题对应的离线问题的最优时间为COPT=2·T(S(v1,vn))

此时C1车不经过预知路段比沿预知路段行进所用时间要少，同样C2车不经过预知路段比沿预知路段行进所用时间要少。该情形下C1车选择从预知点绕行，而C2车选择从预知点的前一个节点绕行。如图6所示。

图6 情形4下混合贪婪策略的竞争分析

在情形4下，混合贪婪策略下所花费的时间计算如下。

当遭遇1个片堵塞RB1时，

当依次遭遇2个片堵塞RB1，RB2时，

运用数学归纳法，依次类推可得当遭遇k个片堵塞时混合贪婪策略所花费的时间为：

该在线问题对应的离线问题的最优时间为COPT=2·T(S(v1,vn))

整理以上4种情形并得到混合贪婪策略的竞争比如表1所示。

表1 混合贪婪策略竞争比

综上所述可得定理1如下。

4 上海市局部路网实例分析

上海市陆家嘴金融贸易区局部路网及其抽象图如图7和图8所示，路段上的数字为路段实际长度。以下将分析突发性片堵塞下混合贪婪策略在两车信息共享情形下的总费用并与两车对堵塞信息均未知情形下的总费用进行比较。

图7 上海市陆家嘴局部路网图

图8 上海市陆家嘴局部路网抽象图

5 结语

突发性片堵塞下两车信息共享的加拿大旅行者问题是重要的研究问题且在以往研究并未涉及。本文结合车辆可以提前获知即将遭遇的片堵塞信息的情形，针对突发性片堵塞下两车信息共享的实时的加拿大旅行者问题，建立在线路径选择模型，给出混合贪婪策略。结合片堵塞多个路段同时发生堵塞的特点，通过比较预知路段长度与绕行临界值的大小关系，分析策略情形，证明混合贪婪策略竞争比为1/2k(αf-1)+1/2βxk+1/2βvk。研究结果表明，在实际中多个运输车辆出行时，应尽量运用各种手段预知道路堵塞的信息并相互共享，可以有效降低片堵塞对实际出行的影响。本文研究结论可对信息可提前获知的多车信息共享下的路径规划以及交管部门制定有效的交通诱导策略提供重要依据。