基于雙區(qū)間索引最短路徑問題研究

張紅巖

摘要：物流配送行業(yè)的迅速發(fā)展，使得物流配送網(wǎng)絡(luò)圖的規(guī)模迅速增加，數(shù)據(jù)量增長較快?，F(xiàn)有的最短路徑問題大多基于傳統(tǒng)的最短路徑算法，在處理大規(guī)模網(wǎng)絡(luò)圖時存在計算較慢，甚至無法計算的問題。提出了基于雙區(qū)間索引的最短路徑算法，對圖中每個頂點(diǎn)建立雙區(qū)間索引，根據(jù)索引值對頂點(diǎn)的可達(dá)性進(jìn)行快速判斷，把可達(dá)性查詢問題應(yīng)用于物流配送網(wǎng)絡(luò)中求解最短路徑問題，可達(dá)到降低物流配送網(wǎng)絡(luò)圖規(guī)模，減少計算量，提高計算效率的效果。

關(guān)鍵詞：物流配送網(wǎng)絡(luò)；最短路徑；雙區(qū)間索引；可達(dá)性查詢

中圖分類號：TB文獻(xiàn)標(biāo)識碼：Adoi：10.19311/j.cnki.16723198.2018.02.091

1引言

近年來，市場經(jīng)濟(jì)快速發(fā)展，物流行業(yè)作為企業(yè)之間和企業(yè)與客戶之間聯(lián)系的橋梁發(fā)揮著巨大的作用。此外，對于以利潤最大化為最終目標(biāo)的現(xiàn)代化企業(yè)來講，物流配送行業(yè)的優(yōu)化，成為企業(yè)增加利潤的一個重要來源。因此，互聯(lián)網(wǎng)信息技術(shù)下物流行業(yè)發(fā)展迅速，并占據(jù)越來越重要的地位。

物流配送業(yè)務(wù)不同于一般的運(yùn)輸業(yè)務(wù)，它是集運(yùn)輸行業(yè)、現(xiàn)代信息網(wǎng)絡(luò)及后續(xù)加工管理等一系列活動于一體的綜合業(yè)務(wù)領(lǐng)域。隨著我國經(jīng)濟(jì)快速發(fā)展，物流配送業(yè)務(wù)活動內(nèi)容逐漸豐富，整體功能增加，使得物流配送網(wǎng)絡(luò)包含的物流節(jié)點(diǎn)越來越多，物流配送路線越來越復(fù)雜。因此，復(fù)雜物流配送網(wǎng)絡(luò)中的路徑優(yōu)化問題成為現(xiàn)代物流運(yùn)輸領(lǐng)域中一個重點(diǎn)問題。

物流配送活動中最基本的問題即最短路徑問題，旨在尋找一條從配送起始點(diǎn)到目標(biāo)節(jié)點(diǎn)總距離最短的路徑。傳統(tǒng)的物流配送最短路徑問題主要注重于計算配送中心到目標(biāo)節(jié)點(diǎn)的最短距離，而忽略了現(xiàn)實(shí)配送活動中的費(fèi)用等路徑代價問題，應(yīng)用到現(xiàn)實(shí)業(yè)務(wù)中具有一定的局限性。在現(xiàn)代物流配送活動中，對實(shí)際物流配送活動中的約束條件考慮更加全面，注重物流配送過程中的成本和代價的計算，在盡量滿足這些條件的前提下來得到整體最優(yōu)路徑。

本文研究的內(nèi)容是物流配送網(wǎng)絡(luò)圖中最短路徑的快速求解問題，并與可達(dá)性查詢問題相結(jié)合，提出了基于雙區(qū)間索引的剪枝策略，來縮減物流網(wǎng)絡(luò)圖的規(guī)模，從而提高求解最短路徑的效率。并參考文獻(xiàn)中提出的雙區(qū)間索引，應(yīng)用于本文中的物流網(wǎng)絡(luò)圖上。在現(xiàn)有的求解最短路徑算法的基礎(chǔ)上，提出了結(jié)合剪枝策略的最短路徑求解算法，并通過實(shí)例驗(yàn)證了本文算法的高效性。

2建立索引

雙區(qū)間索引是指分別為圖中的每個頂點(diǎn)建立先序索引區(qū)間和后序索引區(qū)間，分別記作Lu[x，y]和Ru[x，y]?；舅枷霝榛趫D的遍歷方式，分別對圖中頂點(diǎn)進(jìn)行先序遍歷和后序遍歷，各頂點(diǎn)的索引值依據(jù)頂點(diǎn)在圖中的遍歷順序得到，通過各頂點(diǎn)索引區(qū)間的包含關(guān)系，來判斷圖中頂點(diǎn)之間的可達(dá)性。

2.1先序索引區(qū)間方法

先序索引是指依據(jù)頂點(diǎn)從左到右的后根次序遍歷，然后按照圖中頂點(diǎn)的遍歷次序，為圖中的每一個頂點(diǎn)u，建立標(biāo)簽區(qū)間Lu[x，y]，其中Lu（y）表示頂點(diǎn)u在后根次序遍歷網(wǎng)絡(luò)圖的過程中被訪問的順序，該遍歷順序從1開始，對圖中的頂點(diǎn)按照先左后右的順序依次訪問，直到圖中所有的節(jié)點(diǎn)都訪問一次且僅能被訪問一次為止。該方法保證每一個頂點(diǎn)的孩子節(jié)點(diǎn)的索引值Lt（y）都小于該頂點(diǎn)的索引值Lu（y），即每一個起始頂點(diǎn)的所有可達(dá)頂點(diǎn)的索引值 都小于該起始頂點(diǎn)索引值。

對于每一個頂點(diǎn)u的索引值Lu（x）是通過取該頂點(diǎn)的所有孩子節(jié)點(diǎn)的索引Lt（x）的最小值得到的，特殊的對于所有出度為0的頂點(diǎn)，其索引Lu（x）的值等于其索引Lu（y）的值。該方法可保證每一個頂點(diǎn)的父節(jié)點(diǎn)的索引值Lt（x）都是小于或等于該頂點(diǎn)的索引值Lu（x），即每一個起始頂點(diǎn)的可達(dá)頂點(diǎn)的索引值大于或等于該起始頂點(diǎn)的索引值。因此Lu（x）的計算方法如下：

Lu（x）=Lu（y）min {Lt（x）|t是u的孩子頂點(diǎn)}u的出度為0u的出度不為0（1）

2.2后序索引區(qū)間方法

與先序索引區(qū)間類似，后序索引區(qū)間是指依據(jù)頂點(diǎn)從右到左的后根次序遍歷，然后按照圖中頂點(diǎn)的遍歷次序，為圖中的每一個頂點(diǎn)u，建立標(biāo)簽區(qū)間Ru[x，y]，具體方法參照先序索引區(qū)間，這里不再贅述。

2.3圖例說明

圖1展示了該圖中各頂點(diǎn)的雙區(qū)間索引。

例1：以圖1為例簡要說明頂點(diǎn)的索引區(qū)間Lu[x，y]和Ru[x，y]是如何計算獲得的。圖中的頂點(diǎn)按照從左到右的后根遍歷次序?yàn)椋?、9、8、7、10、5、4、3、2、1、12…，首先對于出度為0的頂點(diǎn)，由于頂點(diǎn)6的訪問次序?yàn)?，所以L6[x，y]=[1， 1]。其次，對于出度不為0的頂點(diǎn)，由于頂點(diǎn)8在上述訪問序列的第3個位置，并且頂點(diǎn)8的出度為1，指向了頂點(diǎn)9，因此L8[x，y]=[2，3]；同理，頂點(diǎn)5在上述訪問序列的第6個位置，并且頂點(diǎn)5的出度為3，分別指向了頂點(diǎn)6、頂點(diǎn)7和頂點(diǎn)10，又由于上述3個頂點(diǎn)的Lu（x）值L6x=1

圖1先序/后序索引區(qū)間

3基于雙區(qū)間索引的剪枝算法

根據(jù)雙區(qū)間索引，可對圖中頂點(diǎn)間的不可達(dá)性進(jìn)行判斷，并對不可達(dá)頂點(diǎn)進(jìn)行剪枝，剪枝過程根據(jù)下述定理進(jìn)行判斷。

定理：對于圖中的每一個頂點(diǎn)對（u，t），若LtLu或RtRu，則頂點(diǎn)u不可達(dá)頂點(diǎn)t（區(qū)間包含，不一定可達(dá)）。

證明：反證法。假定LtLu，且頂點(diǎn)u可達(dá)頂點(diǎn)t。根據(jù)雙區(qū)間所索引建立的過程，可知頂點(diǎn)u可達(dá)頂點(diǎn)t時，Lt（x）Lu（x）且Lt（y）

SymbolcB@ Lu（y），因此可知頂點(diǎn)u和頂點(diǎn)t的索引區(qū)間LtLu，這與LtLu矛盾，因此LtLu時，頂點(diǎn)u不可達(dá)頂點(diǎn)t。同理，可證明當(dāng)RtRu時，頂點(diǎn)u不可達(dá)頂點(diǎn)t。證畢。

例2：以圖1為例，來說明基于雙區(qū)間索引的剪枝算法的計算過程。在計算頂點(diǎn)15到頂點(diǎn)6的最短路徑的過程中，應(yīng)用剪枝定理進(jìn)行不可達(dá)性判斷，可以將1，2，3，9等13個頂點(diǎn)剪枝。在剪枝后的網(wǎng)絡(luò)圖上應(yīng)用Dijkstra算法為例計算最短路徑，最終可獲得最短路徑序列為15→5→6，最短路徑距離為11，在這一計算過程中只需要計算16個頂點(diǎn)。然而，在原始的網(wǎng)絡(luò)圖上應(yīng)用Dijkstra算法可求得最短路徑序列仍為15→5→6，路徑距離也為11，但該計算過程需要計算22個頂點(diǎn)。通過對比，不難發(fā)現(xiàn)應(yīng)用基于雙區(qū)間索引的剪枝算法可有效減少算法的計算量，提高了計算效率。

4結(jié)束語

本文把可達(dá)性查詢問題應(yīng)用于物流配送網(wǎng)絡(luò)的最短路徑求解問題中，提出了基于雙區(qū)間索引的最短路徑算法。對物流配送網(wǎng)絡(luò)圖中的每個頂點(diǎn)分別建立先序索引區(qū)間及后序索引區(qū)間，根據(jù)各頂點(diǎn)索引區(qū)間的包含關(guān)系，判斷物流配送網(wǎng)絡(luò)圖中頂點(diǎn)間的不可達(dá)性，對不可達(dá)的頂點(diǎn)進(jìn)行剪枝，在計算中不再考慮不可達(dá)的頂點(diǎn)，然后與傳統(tǒng)的最短路徑算法相結(jié)合，形成了基于雙區(qū)間索引的最短路徑算法，達(dá)到了縮減網(wǎng)絡(luò)圖規(guī)模，提高計算效率的效果。通過實(shí)例進(jìn)行對比，證明了本文算法的高效性。

參考文獻(xiàn)

[1]Agrawal S， Singh RK， Murtaza Q. Outsourcing decisions in reverse logistics： Sustainable balanced scorecard and graph theoretic approach[J].Resources， Conservation and Recycling， 2016，108： 4153.

[2]忻瑞嬋.物流配送系統(tǒng)中大規(guī)模最短路徑算法的研究[J].中國管理信息化，2008，（05）：6769.

[3]Van Schaik S J， De Moor O. A memory efficient reachability data structure through bit vector compression[C]. Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data， 2011：913924.

[4]關(guān)菲，張強(qiáng).模糊多目標(biāo)物流配送中心選址模型及其求解算法[J].中國管理科學(xué)， 2013，21（S1）：5762.

[5]胡祥培，孫麗君，王雅楠.物流配送系統(tǒng)干擾管理模型研究[J].管理科學(xué)學(xué)報， 2011，14（01）：5060.

[6]韓世蓮，李旭宏，劉新旺.物流運(yùn)輸網(wǎng)絡(luò)模糊最短路徑的偏好解[J].交通運(yùn)輸工程學(xué)報，2005，（02）：122126.

[7]唐晉韜，王挺，王戟.適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J].軟件學(xué)報， 2011，（10）：22792290.

[8]Sommer C.Shortest-path queries in static networks[J].ACM Computing Surveys （CSUR），2014，46（4）：45.

[9]Kuperstein I， Grieco L， Cohen D P A， et al. The shortest path is not the one you know： Application of biological network resources in precision oncology research[J]. Mutagenesis， 2015， 30（2）： 191204.

[10]王樹西，李安渝.Dijkstra算法中多鄰接點(diǎn)與多條最短路徑問題[J].計算機(jī)科學(xué)， 2014，41（06）：217224.

[11]Bader J S， Chaudhuri A， RothBerg J M. Gaining Confidence in High-through put Protein Interaction Networks[J]. Nature Biotechnology， 2003，22（1）：7885.

[12]Yildirim H， Chaoji V， Zaki M J. Grail： Scalable reachability index for large graphs[J]. The Proceedings of the VLDB Endowment （PVLDB） Journal， 2010，3（1）： 276284.endprint