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

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

1 引言

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

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

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

圖1 問題描述示意圖

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

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

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

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

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

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

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

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

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

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

3.1 混合貪婪策略

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

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

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

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

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

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

下面對(duì)策略的4種情形進(jìn)行分析。

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

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

在情形1下，混合貪婪策略下所花費(fèi)的時(shí)間計(jì)算如下。

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

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

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

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

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

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

在情形2下，混合貪婪策略下所花費(fèi)的時(shí)間計(jì)算如下。

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

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

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

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

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

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

在情形3下，混合貪婪策略下所花費(fèi)的時(shí)間計(jì)算如下。

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

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

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

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

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

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

在情形4下，混合貪婪策略下所花費(fèi)的時(shí)間計(jì)算如下。

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

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

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

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

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

表1 混合貪婪策略競爭比

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

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

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

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

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

5 結(jié)語

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