突發(fā)性片堵塞下兩車信息共享的加拿大旅行者問題

蘇 兵，林 剛，程新峰，孫璐璐

(西安工業(yè)大學(xué)經(jīng)濟管理學(xué)院，陜西 西安 710032)

1 引言

加拿大旅行者問題(Canadian Traveler Problem，CTP)是指旅行者從起點出發(fā)去終點的過程中遭遇無法預(yù)知突發(fā)性堵塞下如何制定實時路徑選擇策略使花費時間盡可能少的問題[1-2]。對這個受不確定因素影響較大的問題，國內(nèi)外學(xué)者采用在線問題與競爭策略的理論開展了相關(guān)研究[3-6]，主要討論了堵塞信息完全未知和有限預(yù)知情形下的單一路段堵塞的單車路徑選擇策略。對于堵塞信息完全未知的情形，建立一般網(wǎng)絡(luò)中路段堵塞不可恢復(fù)下的單車在線路徑選擇模型，設(shè)計貪婪策略和復(fù)位策略并證明策略競爭比[7-10]；建立方格路網(wǎng)中路段堵塞不可恢復(fù)下的單車在線路徑選擇模型，設(shè)計方向貪婪策略和多選擇移動策略并證明策略競爭比[11]；建立連續(xù)網(wǎng)絡(luò)中路段堵塞可恢復(fù)下的單車在線路徑選擇模型，設(shè)計等待策略和移動策略并證明策略競爭比[12]。對于堵塞信息有限預(yù)知情形下即單車到達某一節(jié)點時可以預(yù)知相鄰節(jié)點一條關(guān)聯(lián)邊堵塞信息，建立一般離散網(wǎng)絡(luò)中路段堵塞可恢復(fù)的單車在線路徑選擇模型，設(shè)計等待策略和貪婪策略并證明策略競爭比，建立一條路上路段堵塞可恢復(fù)的單車在線路徑選擇模型，設(shè)計混合策略并證明策略競爭比[13-15]。現(xiàn)有加拿大旅行者問題研究主要是在單車遭遇突發(fā)性路段堵塞的假設(shè)下進行的。然而在實際中，網(wǎng)絡(luò)中經(jīng)常會發(fā)生片堵塞，即多條相關(guān)聯(lián)路段同時堵塞的情形[16]，物流企業(yè)也經(jīng)常會派出多輛車組成車隊從相同起點到目的點進行貨運，如果在運輸過程中會遭遇突發(fā)性片堵塞，若每一車輛都能有限預(yù)知堵塞信息且車輛間可以進行信息共享，如何制定多車行進策略使車輛所花費的總時間盡可能少是亟待解決的難題，但此問題在以往研究中未涉及。

針對該問題，本文假設(shè)車輛數(shù)為2，提出突發(fā)性片堵塞下兩車信息共享的加拿大旅行者問題，采用在線問題與競爭策略的理論和方法，建立在信息有限預(yù)知即車輛到達某一節(jié)點(預(yù)知點)時可以預(yù)知相鄰節(jié)點的多條關(guān)聯(lián)路段所構(gòu)成的片堵塞信息情形下的兩車在線路徑選擇模型，設(shè)計混合貪婪策略，分析策略在所選路徑是否經(jīng)過信息預(yù)知點到片堵塞起始點的路段(預(yù)知路段)等不同情形下車輛的總費用，證明混合貪婪策略的競爭比，并用實例驗證模型和策略的有效性。

2 問題描述與基本假設(shè)

圖1 問題描述示意圖

為了便于討論問題，提出以下基本假設(shè)。

(1)兩車在到達預(yù)知點時可以獲知片堵塞中各條邊的堵塞信息；

(2)k個片堵塞RB={RB1,…,RBλ,…,RBk}相互獨立，且依次順序出現(xiàn)；

(3)G在刪除堵塞邊集Eλ之后依然連通；

(4)兩車遇到的片堵塞皆為樹形片堵塞即以一個節(jié)點為中心，與之相關(guān)聯(lián)多條邊發(fā)生堵塞；

(5)片堵塞中每條路段的堵塞都是可恢復(fù)的，并且在到達下一個預(yù)知點時，上一個片堵塞已經(jīng)恢復(fù)暢通。

以上問題是一個在線問題，可以設(shè)計有效的在線策略來解決。假設(shè)Copt(R)是該問題對應(yīng)離線問題的最優(yōu)費用，CA(R)是問題在所設(shè)計在線策略A下的費用，如果存在與序列事件無關(guān)的常數(shù)α和β使得CA(R)≤αCopt(R)+β成立，則稱α為策略A的競爭比。競爭比是對在線策略執(zhí)行效果的衡量, 如果競爭比較大,說明在線問題在所設(shè)計策略下的費用同與之對應(yīng)離線問題的最優(yōu)費用偏離較大，競爭比越接近于 1, 策略的執(zhí)行效果越好。

3 兩車信息共享的片堵塞加拿大旅行者問題策略設(shè)計及其競爭比

在實際中通常會采取讓兩車同時出發(fā)且按照同一路徑行進的策略，一旦這一路徑發(fā)生突發(fā)性堵塞，則兩車均會因遭遇堵塞而蒙受時間損失。因此，是否可以選擇讓兩車分先后出發(fā)，先出發(fā)的車可以發(fā)送信息，后出發(fā)的車可以接收信息。當(dāng)先出發(fā)的車遭遇堵塞時，迅速將堵塞信息傳遞給后出發(fā)的車，使得后出發(fā)的車能夠據(jù)此做出路徑選擇，最終使得兩車花費的總時間盡可能的少。

策略設(shè)計思路：讓1輛車先沿最短路徑從u1點出發(fā)后在u2點預(yù)知到片堵塞，并將堵塞的時間與位置信息傳遞給仍在u1點等待的另1輛車，當(dāng)兩車預(yù)知到堵塞信息后會進行如下判斷，若任意一車預(yù)知路段的通行時間大于最短路徑上堵塞邊的恢復(fù)時間，則該車沿最短路徑行進即可，若任意一車預(yù)知路段的通行時間小于最短路徑上堵塞邊的恢復(fù)時間，則根據(jù)預(yù)知路段長度與繞行臨界值的大小關(guān)系的比較，來確定重選的最短路徑是否經(jīng)過預(yù)知路段，得到重新選出的最短路徑，該車沿新最短路徑行進。當(dāng)每次遇到堵塞時都按照這種原則進行決策，本文將這種原則稱為混合貪婪策略。

3.1 混合貪婪策略

令兩車分別為C1車和C2車，C1車的預(yù)知路段定義為C1-預(yù)知路段，C2車的預(yù)知路段定義為C2-預(yù)知路段。

混合貪婪策略(M-GSA*)，兩車分先后從u1點出發(fā)，C1車沿事先選定的最短路徑行進，當(dāng)C1車到達u2點后C2車出發(fā)，兩車行進規(guī)則如下：當(dāng)遭遇片堵塞RB1時①若C1車在u2點預(yù)知到u3點的關(guān)聯(lián)邊發(fā)生片堵塞，則u2點為預(yù)知點，此時C1車在預(yù)知點將片堵塞信息傳遞給C2車，然后C1車比較C1-預(yù)知路段長度與對應(yīng)繞行臨界值的大小關(guān)系后，重選最短路徑行進，而C2車也比較C2-預(yù)知路段長度與對應(yīng)繞行臨界值的大小關(guān)系后，重選最短路徑行進。②若C1車在u2點未預(yù)知到堵塞，則兩車沿最短路徑行進，當(dāng)C1車預(yù)知到片堵塞后將片堵塞信息傳遞給C2車，然后C1車和C2車分別比較對應(yīng)預(yù)知路段長度與對應(yīng)繞行臨界值的大小后，重選最短路徑行進。當(dāng)遭遇片堵塞{RB2,…,RBλ,…,RBk}時，任意一車遭遇到片堵塞后，根據(jù)同一原則處理直至最終到達vn。

混合貪婪策略的具體情形如圖2所示。

圖2 混合貪婪策略情形分析圖

3.2 混合貪婪策略的競爭比證明

令S(v1,vn)和T[S(v1,vn)]表示在出行前選定的未遭遇突發(fā)性片堵塞的從v1到vn的最短路徑及其通行時間，S′(v1,vn)和T[S′(v1,vn)]表示刪去遭遇片堵塞中的邊后的從v1到vn的最短路徑及其通行時間。

下面對策略的4種情形進行分析。

此時C1車沿預(yù)知路段行進比不經(jīng)過預(yù)知路段所用時間要少，同樣C2車沿預(yù)知路段行進比不經(jīng)過預(yù)知路段所用時間要少，此時該情形下的最壞情況為兩車都會經(jīng)過片堵塞中的某條堵塞邊。如圖3所示。

圖3 情形1下混合貪婪策略的競爭分析

在情形1下，混合貪婪策略下所花費的時間計算如下。

當(dāng)遭遇1個片堵塞RB1時，

當(dāng)依次遭遇2個片堵塞RB1，RB2時，

運用數(shù)學(xué)歸納法，依次類推可得當(dāng)遭遇k個片堵塞時混合貪婪策略所花費的時間為：

該在線問題對應(yīng)的離線問題的最優(yōu)時間為COPT=2·T(S(v1,vn))

此時C1車沿預(yù)知路段行進比不經(jīng)過預(yù)知路段所用時間要少，而C2車不經(jīng)過預(yù)知路段比沿預(yù)知路段行進所用時間要少。該情形下C1車經(jīng)過片堵塞中的某條堵塞邊，而C2車選擇從預(yù)知點的前一節(jié)點繞行。如圖4所示。

圖4 情形2下混合貪婪策略的競爭分析

在情形2下，混合貪婪策略下所花費的時間計算如下。

當(dāng)遭遇1個片堵塞RB1時，

當(dāng)依次遭遇2個片堵塞RB1，RB2時，

運用數(shù)學(xué)歸納法，依次類推可得當(dāng)遭遇k個片堵塞時混合貪婪策略所花費的時間為

該在線問題對應(yīng)的離線問題的最優(yōu)時間為COPT=2·T(S(v1,vn))

此時C1車不經(jīng)過預(yù)知路段比沿預(yù)知路段行進所用時間要少，而C2車沿預(yù)知路段行進比不經(jīng)過預(yù)知路段所用時間要少。該情形下C1車選擇從預(yù)知點繞行，而C2車經(jīng)過預(yù)知路段并經(jīng)過片堵塞中的一條堵塞邊。如圖5所示。

圖5 情形3下混合貪婪策略的競爭分析

在情形3下，混合貪婪策略下所花費的時間計算如下。

當(dāng)遭遇1個片堵塞RB1時，

當(dāng)依次遭遇2個片堵塞RB1，RB2時，

運用數(shù)學(xué)歸納法，依次類推可得當(dāng)遭遇k個片堵塞時混合貪婪策略所花費的時間為

該在線問題對應(yīng)的離線問題的最優(yōu)時間為COPT=2·T(S(v1,vn))

此時C1車不經(jīng)過預(yù)知路段比沿預(yù)知路段行進所用時間要少，同樣C2車不經(jīng)過預(yù)知路段比沿預(yù)知路段行進所用時間要少。該情形下C1車選擇從預(yù)知點繞行，而C2車選擇從預(yù)知點的前一個節(jié)點繞行。如圖6所示。

圖6 情形4下混合貪婪策略的競爭分析

在情形4下，混合貪婪策略下所花費的時間計算如下。

當(dāng)遭遇1個片堵塞RB1時，

當(dāng)依次遭遇2個片堵塞RB1，RB2時，

運用數(shù)學(xué)歸納法，依次類推可得當(dāng)遭遇k個片堵塞時混合貪婪策略所花費的時間為：

該在線問題對應(yīng)的離線問題的最優(yōu)時間為COPT=2·T(S(v1,vn))

整理以上4種情形并得到混合貪婪策略的競爭比如表1所示。

表1 混合貪婪策略競爭比

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

4 上海市局部路網(wǎng)實例分析

上海市陸家嘴金融貿(mào)易區(qū)局部路網(wǎng)及其抽象圖如圖7和圖8所示，路段上的數(shù)字為路段實際長度。以下將分析突發(fā)性片堵塞下混合貪婪策略在兩車信息共享情形下的總費用并與兩車對堵塞信息均未知情形下的總費用進行比較。

圖7 上海市陸家嘴局部路網(wǎng)圖

圖8 上海市陸家嘴局部路網(wǎng)抽象圖

5 結(jié)語

突發(fā)性片堵塞下兩車信息共享的加拿大旅行者問題是重要的研究問題且在以往研究并未涉及。本文結(jié)合車輛可以提前獲知即將遭遇的片堵塞信息的情形，針對突發(fā)性片堵塞下兩車信息共享的實時的加拿大旅行者問題，建立在線路徑選擇模型，給出混合貪婪策略。結(jié)合片堵塞多個路段同時發(fā)生堵塞的特點，通過比較預(yù)知路段長度與繞行臨界值的大小關(guān)系，分析策略情形，證明混合貪婪策略競爭比為1/2k(αf-1)+1/2βxk+1/2βvk。研究結(jié)果表明，在實際中多個運輸車輛出行時，應(yīng)盡量運用各種手段預(yù)知道路堵塞的信息并相互共享，可以有效降低片堵塞對實際出行的影響。本文研究結(jié)論可對信息可提前獲知的多車信息共享下的路徑規(guī)劃以及交管部門制定有效的交通誘導(dǎo)策略提供重要依據(jù)。