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

高 攀，方 威

(長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410004)

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

高 攀，方 威

(長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410004)

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)路段阻抗全部取區(qū)間下界時(shí)，可得圖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ū)間阻抗下魯棒有效路徑判斷的兩個(gè)標(biāo)準(zhǔn)

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

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

(1)

(2)

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

為了對(duì)魯棒有效路徑的定義進(jìn)行更好的解釋?zhuān)砸詧D1為例進(jìn)行簡(jiǎn)單的判斷：

從r開(kāi)始選擇下一節(jié)點(diǎn)。對(duì)于節(jié)點(diǎn)1：

標(biāo)準(zhǔn)一：2.5+4.4<8.1，符合；

標(biāo)準(zhǔn)二：3.8+1.9<8.1，符合。

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

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

標(biāo)準(zhǔn)一：0.5+4.6>4.2，不符合；

標(biāo)準(zhǔn)二：1.1+2.2<4.2，符合。

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

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

(1)參數(shù)定義

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

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

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

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

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

Prs：r到s任意路徑；

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

(2)目標(biāo)函數(shù)

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

(3)

(3)約束條件

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

(4)

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

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

(5)

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

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

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

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

步驟2：通過(guò)上界最短路和下界最短路確定參照最短路，并以此為評(píng)價(jià)標(biāo)準(zhǔn)；

步驟3：按照魯棒有效節(jié)點(diǎn)的兩個(gè)判斷標(biāo)準(zhǔn)，找到所有魯棒有效路徑；

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

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

5 算例分析

為了對(duì)上述算法進(jìn)行詳細(xì)介紹，以圖4為例進(jìn)行計(jì)算：

圖4 算例分析圖

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

Step3：通過(guò)魯棒有效節(jié)點(diǎn)的判斷標(biāo)準(zhǔn)，找到所有魯棒有效路徑r-1-s，r-2-s，r-1-2-s；

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

為了驗(yàn)證算法的有效性，下面采取魯棒優(yōu)化理論中常用的兩個(gè)標(biāo)準(zhǔn)，魯棒偏差標(biāo)準(zhǔn)和相對(duì)魯棒標(biāo)準(zhǔn)來(lái)對(duì)圖4的最短路進(jìn)行計(jì)算。

方法一，以魯棒偏差標(biāo)準(zhǔn)進(jìn)行計(jì)算：

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

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

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

Step4：計(jì)算結(jié)束，魯棒成本最小的即為魯棒最短路，因此，以魯棒偏差標(biāo)準(zhǔn)無(wú)法得到圖4的魯棒最短路。

方法二，以相對(duì)魯棒標(biāo)準(zhǔn)進(jìn)行計(jì)算：

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

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

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

Step4：計(jì)算魯棒有效路徑的魯棒成本與此情景下最短路阻抗的比值，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：計(jì)算結(jié)束，比值最小的即為魯棒最短路，因此，以相對(duì)魯棒標(biāo)準(zhǔn)得到圖4的魯棒最短路為r-1-2-s。

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

6 結(jié)語(yǔ)

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

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

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

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

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

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

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

[7]秦 鳴，姜 培.基于有效路徑的多路徑交通流分配[J].交通標(biāo)準(zhǔn)化，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—)，在讀碩士研究生，研究方向：交通運(yùn)輸規(guī)劃與管理；

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

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

U491

A

10.13282/j.cnki.wccst.2016.12.017

1673-4874(2016)12-0057-05

2016-10-26