高 攀，方 威

(長沙理工大學交通運輸工程學院，湖南 長沙 410004)

基于區(qū)間交叉熵的魯棒最短路模型和算法研究

高 攀，方 威

(長沙理工大學交通運輸工程學院，湖南 長沙 410004)

由于交通需求是區(qū)間數(shù)，路段阻抗也必然是區(qū)間數(shù)，這導致區(qū)間阻抗下的魯棒最短路成為研究的核心問題。文章運用行為經(jīng)濟學的參照系理論，分別用下界與上界為阻抗，計算得到區(qū)間最短路，以此為參照，考慮最壞情形，構(gòu)造魯棒有效路徑的兩個判斷標準，得到有效路徑集合；運用交叉熵理論，計算有效路徑與參照區(qū)間最短路的交叉熵，構(gòu)建基于最小交叉熵的魯棒最短路模型。

交叉熵；有效路徑；魯棒最短路；區(qū)間阻抗

0 引言

近年來，網(wǎng)絡(luò)優(yōu)化問題在運籌學中成了一項很重要的研究內(nèi)容，它包括最短路問題、網(wǎng)絡(luò)流問題、車輛路徑問題和中國郵遞員問題等等。最短路問題的重點是用最小的距離、時間或成本尋找一條從起點到終點的路，它是網(wǎng)絡(luò)理論中的最基本問題。隨著不確定理論在各個領(lǐng)域的不斷推廣與深化研究，在交通方面，考慮不確定性的交通分配問題也越來越受到國內(nèi)外專家的關(guān)注。周和平等(2003、2005)分別將需求視為區(qū)間隨機數(shù)與區(qū)間模糊數(shù)，運用模擬的反推技術(shù)，得到區(qū)間OD矩陣[1，2]，Bertsimas D等(2003)主要研究數(shù)據(jù)不確定離散優(yōu)化以及能控制在保守度以內(nèi)的網(wǎng)絡(luò)流問題，為此建立了一個魯棒整數(shù)規(guī)劃模型[3]。最短路的選擇是交通分配的基礎(chǔ)，只有確定了最短路，才能進行之后的交通分配。所以，找尋最短路是交通分配中最重要、也最基礎(chǔ)的一環(huán)。

本文考慮的是區(qū)間需求，這導致網(wǎng)絡(luò)中的路段上阻抗也為區(qū)間值，這樣就不能很輕松地得到網(wǎng)絡(luò)上的最短路，因為區(qū)間數(shù)不是一個確定的數(shù)，并且在區(qū)間重疊的情況下也很難定義最短路。為此，本文將區(qū)間阻抗下的最短路問題轉(zhuǎn)化為了最短路徑行為選擇問題。本文提出了參照最短路的概念，以參照最短路為評價標準，并利用實際最短路分布逼近參照最短路分布的特點，建立了交叉熵最短路模型，并給出了相應(yīng)的求解算法。

1 區(qū)間阻抗下參照最短路定義

(1)網(wǎng)絡(luò)中只有一個起點和一個終點，并且是無循環(huán)的；

(2)網(wǎng)絡(luò)中任意弧段上的阻抗都是相互獨立的；

(3)區(qū)間阻抗是服從正態(tài)分布的隨機變量。

在定義參照最短路之前，需注意上界最短路和下界最短路。對于一個區(qū)間阻抗下的不確定性網(wǎng)絡(luò)，當把阻抗全部取區(qū)間上界時，得到一個確定性的網(wǎng)絡(luò)，這時的最短路就是上界最短路；當把阻抗全部取區(qū)間下界時，得到另一個確定性的網(wǎng)絡(luò)，這時的最短路就是下界最短路。分別取上界最短路的上界和下界最短路的下界，得到一條虛擬路徑，即參照最短路。

為了對參照最短路的定義進行更好的解釋，以下給出一個簡單的有向網(wǎng)絡(luò)圖(見圖1)，該網(wǎng)絡(luò)由4個節(jié)點5個路段組成，其中r為起點，s為終點，弧邊上的數(shù)據(jù)表示路段上的區(qū)間阻抗值。

圖1 簡單區(qū)間網(wǎng)絡(luò)圖

當路段阻抗全部取區(qū)間上界時，可得圖2。

圖2 區(qū)間上界網(wǎng)絡(luò)圖

由圖2可知，圖1的上界最短路為r-2-s，路徑區(qū)間阻抗為[4.5，8.1]。

當路段阻抗全部取區(qū)間下界時，可得圖3。

圖3 區(qū)間下界網(wǎng)絡(luò)圖

由圖3可知，圖2的下界最短路為r-1-s，路徑區(qū)間阻抗為[4.4，8.2]。

根據(jù)上述定義，由下界最短路的下界和上界最短路的上界就構(gòu)成了參照最短路的路徑區(qū)間阻抗，因此圖2中參照最短路的路徑區(qū)間阻抗為[4.4，8.1]。

2 區(qū)間阻抗下魯棒有效路徑判斷的兩個標準

關(guān)于有效路徑的定義，傳統(tǒng)有效路徑的定義是：當路段(i，j)的上游端點i比下游端點j距離起點r更近，同時又有i比j距離終點s更遠，則該路段可以成為有效路段，由有效路段組成的可行路徑即有效路徑[4，5]。黃海軍等(2003)考慮到實際交通網(wǎng)絡(luò)中流量非常小的路徑不會影響最后的交通分配，重新定義了有效路徑[6]。秦鳴等(2010)介紹了三種有效路徑的定義方法并做了比較，對于確定阻抗下的有效路徑搜尋有一定實際意義，但對于區(qū)間阻抗下的有效路徑依然無能為力[7]。在本研究中，網(wǎng)絡(luò)中的路段阻抗是不確定的，是一個區(qū)間數(shù)，因此本文提出了魯棒有效路徑的概念。

魯棒有效路徑是由魯棒有效節(jié)點組成的路徑，而魯棒有效節(jié)點的判斷可以依照以下兩個標準。(1)從i出發(fā)選擇下一節(jié)點j，如果選擇不當，i-j阻抗取區(qū)間上界值，那么j-s的阻抗取下界最短路的阻抗。此時，應(yīng)滿足j-s的阻抗加上i-j的阻抗比i-s的上界最短路阻抗值要??；(2)從i出發(fā)選擇下一節(jié)點j，如果選擇得當，i-j阻抗取區(qū)間下界值，那么j-s的阻抗取上界最短路的阻抗。此時，同樣應(yīng)滿足j-s的阻抗加上i-j的阻抗比i-s的上界最短路阻抗值要小。如果同時滿足這兩個標準，便成為所尋找的魯棒有效節(jié)點。魯棒有效節(jié)點可以用公式(1)、(2)進行判斷：

(1)

(2)

式中，lij，uij——分別為路段(i，j)阻抗的下界、上界值；

為了對魯棒有效路徑的定義進行更好的解釋，仍以圖1為例進行簡單的判斷：

從r開始選擇下一節(jié)點。對于節(jié)點1：

標準一：2.5+4.4<8.1，符合；

標準二：3.8+1.9<8.1，符合。

因此對于r而言，節(jié)點1是魯棒有效節(jié)點。

從節(jié)點1開始選擇下一節(jié)點，如果選擇終點s，選擇結(jié)束，則r-1-s為魯棒有效路徑；如果選擇節(jié)點2，對于節(jié)點2：

標準一：0.5+4.6>4.2，不符合；

標準二：1.1+2.2<4.2，符合。

因此對于節(jié)點1而言，節(jié)點2不是魯棒有效節(jié)點，則r-1-2-s不是魯棒有效路徑。其它有效節(jié)點的判斷與此類似，不一一判斷。

3 區(qū)間阻抗下最短路模型的構(gòu)建

(1)參數(shù)定義

N：網(wǎng)絡(luò)中所有節(jié)點的集合，包括起點r和終點s；

A：網(wǎng)絡(luò)中節(jié)點間路段的集合；

i，j，k：網(wǎng)絡(luò)中節(jié)點的記號；

lij，uij：分別為路段(i，j)阻抗的下界值、上界值；

xij：0-1決策變量，當路段(i，j)被選中取值1，反之則取值0；

Prs：r到s任意路徑；

yPrs：r到s任意路徑的路徑阻抗；

(2)目標函數(shù)

對于確定性邊權(quán)的最短路問題，一般就是將邊權(quán)作為評價指標，那么具有最小邊權(quán)的路徑即為最短路徑。本文中邊權(quán)為區(qū)間數(shù)，各條路徑之間無法直接比較，為了解決這個問題，運用行為經(jīng)濟學中的參照系理論，特引入了參照最短路的概念。以參照最短路為評價標準，在假設(shè)路徑阻抗值服從正態(tài)分布的基礎(chǔ)上，與參照最短路分布最接近的魯棒有效路徑即認為是魯棒最短路徑，根據(jù)以上描述，運用交叉熵理論構(gòu)建模型，數(shù)學表達式為：

(3)

(3)約束條件

①平衡流約束，即保證所選擇的路段構(gòu)成了一條從起點到終點的完整連通路徑。

(4)

②有效節(jié)點約束，保證選取的路徑是魯棒有效路徑。

基于以上的定義及相關(guān)描述，區(qū)間阻抗下的網(wǎng)絡(luò)最短路問題可以建立以下模型：

(5)

以上模型為本文建立的魯棒最短路模型，該模型很好地描述了具有區(qū)間阻抗下的網(wǎng)絡(luò)最短路問題，減少了網(wǎng)絡(luò)的不確定性，又保留了最大的不確定性。以下將探討此模型的求解。

4 最短路算法設(shè)計

最短路算法是設(shè)計交通分配算法的基礎(chǔ)，其目的是找到起點到終點之間的最短路徑，傳統(tǒng)方法用的是Dijkstra算法和Floyd算法。兩者的區(qū)別在于：Dijkstra算法只可以求解網(wǎng)絡(luò)中某一固定節(jié)點到另一節(jié)點之間的最短路，而Floyd算法可以算出網(wǎng)絡(luò)中任意一對起、終點之間的最短路。由于本文中涉及到路段阻抗為區(qū)間值，傳統(tǒng)算法無法進行有效計算，因此本文將運用交叉熵理論，設(shè)計解決區(qū)間阻抗下網(wǎng)絡(luò)的最短路問題，相關(guān)計算步驟如下：

步驟1：對區(qū)間阻抗下的網(wǎng)絡(luò)全取區(qū)間上界，然后用Dijkstra算法求得上界最短路，同理，全取區(qū)間下界可得到下界最短路；

步驟2：通過上界最短路和下界最短路確定參照最短路，并以此為評價標準；

步驟3：按照魯棒有效節(jié)點的兩個判斷標準，找到所有魯棒有效路徑；

步驟4：使所有的魯棒有效路徑與參照最短路進行比較，得到熵最小的即為魯棒最短路；

步驟5：計算結(jié)束，輸出OD對間的魯棒最短路。

5 算例分析

為了對上述算法進行詳細介紹，以圖4為例進行計算：

圖4 算例分析圖

Step1：對區(qū)間阻抗下網(wǎng)絡(luò)分別取上、下界值，用Dijkstra算法求得上界最短路與下界最短路：r-2-s，r-1-s；其路徑阻抗分別為[6，10]，[4，12]；

Step3：通過魯棒有效節(jié)點的判斷標準，找到所有魯棒有效路徑r-1-s，r-2-s，r-1-2-s；

Step5：計算結(jié)束，圖4的魯棒最短路為r-1-s。

為了驗證算法的有效性，下面采取魯棒優(yōu)化理論中常用的兩個標準，魯棒偏差標準和相對魯棒標準來對圖4的最短路進行計算。

方法一，以魯棒偏差標準進行計算：

Step1：找出網(wǎng)絡(luò)中魯棒有效路徑：r-1-s，r-2-s，r-1-2-s；

Step2：定義魯棒成本，任意選擇一條路徑，此路徑上的路段阻抗全取上界值，其余路段阻抗全取下界值得到一條最短路，魯棒成本就是所選路徑阻抗與最短路阻抗的差；

Step3：計算魯棒有效路徑的魯棒成本，R(r-1-s)=6，R(r-1-2-s)=6，R(r-2-s)=6；

Step4：計算結(jié)束，魯棒成本最小的即為魯棒最短路，因此，以魯棒偏差標準無法得到圖4的魯棒最短路。

方法二，以相對魯棒標準進行計算：

Step1：找出網(wǎng)絡(luò)中魯棒有效路徑：r-1-s，r-2-s，r-1-2-s；

Step2：定義魯棒成本，任意選擇一條路徑，此路徑上的路段阻抗全取上界值，其余路段阻抗全取下界值得到一條最短路，魯棒成本就是所選路徑阻抗與最短路阻抗的差；

Step3：計算魯棒有效路徑的魯棒成本，R(r-1-s)=6，R(r-1-2-s)=6，R(r-2-s)=6；

Step4：計算魯棒有效路徑的魯棒成本與此情景下最短路阻抗的比值，R(r-1-s)=6/6=1，R(r-1-2-s)=6/7=0.86，R(r-2-s)=6/4=1.5；

Step5：計算結(jié)束，比值最小的即為魯棒最短路，因此，以相對魯棒標準得到圖4的魯棒最短路為r-1-2-s。

基于圖4對三種方法進行比較，本文找出的魯棒最短路為r-1-s，路徑阻抗為[4，12]；相對魯棒方法找出的魯棒最短路為r-1-2-s，路徑阻抗為[7，13]；魯棒偏差方法無法得到魯棒最短路。從直觀上判斷，路徑r-1-s更符合人們的行為選擇，因此本文提出的基于交叉熵模型的算法在尋找最短路時有一定的優(yōu)勢。

6 結(jié)語

本文在分析傳統(tǒng)最短路問題的基礎(chǔ)上，考慮區(qū)間阻抗下網(wǎng)絡(luò)的特殊性，提出了上界最短路、下界最短路以及參照最短路的概念，并針對傳統(tǒng)有效路徑提出了魯棒有效路徑的概念，根據(jù)交叉熵的理論，建立了魯棒最短路模型，并設(shè)計了對應(yīng)的求解算法，有效地解決了區(qū)間阻抗下的網(wǎng)絡(luò)最短路問題。

[1]周和平，晏克非，胡列格.基于隨機模擬的遺傳算法在OD反推中的應(yīng)用研究[J].系統(tǒng)工程，2003，21(4)：115-119.

[2]周和平，晏克非，胡列格.基于隨機模糊路段流量的OD反推的不確定規(guī)劃模型與算法研究[J].鐵道科學與工程學報，2005，2(5)：69-74.

[3]BertsimasD，SimM.Robustdiscreteoptimizationandnetworkflows[J].Mathematicalprogramming，2003，98(1-3)：49-71.

[4]賴樹坤，姚憲輝，彭 愚.交通網(wǎng)絡(luò)中有效路徑確定方法的探討[J].交通標準化，2008(1)：137-140.

[5]YangXF，LiuLF，Yin-ZhenaLI，etal.DeterminingtheEfficientPathsBasedonEffectDegree[J].JournalofTransportationSystemsEngineering&InformationTechnology，2011，11(6)：104-110.

[6]李志純，黃海軍.隨機交通分配中有效路徑的確定方法[J].交通運輸系統(tǒng)工程與信息，2003，3(1)：28-32.

[7]秦 鳴，姜 培.基于有效路徑的多路徑交通流分配[J].交通標準化，2010(7)：30-33.

Research on Robust Shortest Path Model and Algorithm Based on Interval Cross Entropy

GAO Pan，F(xiàn)ANG Wei

(School of Traffic and Transportation Engineering，Changsha University of Science &Technology，Changsha，Hunan，410004)

As the traffic demand is the interval number，and the road segment impedance must also be the interval number，which leads to the robust shortest path under interval impedance becoming the core research problem.By using the reference frame theory of behavioral economics，this article respectively used the lower bound and upper bound as the impedance，calculated the interval shortest path，which were used as the reference，and considering the worst case，it constructed two judgment criteria of robust effective path，and obtained the effective path set；by using the cross entropy，it calculated the cross-entropy between the effective path and the reference interval shortest path，and constructed the robust shortest path model based on minimum cross-entropy.

Cross entropy；Effective path；Robust shortest path；Interval impedance

高 攀(1993—)，在讀碩士研究生，研究方向：交通運輸規(guī)劃與管理；

方 威(1991—)，在讀碩士研究生，研究方向：交通運輸規(guī)劃與管理。

交通運輸部應(yīng)用基礎(chǔ)研究項目(2014319825 190)

U491

A

10.13282/j.cnki.wccst.2016.12.017

1673-4874(2016)12-0057-05

2016-10-26