基于雙區間索引最短路徑問題研究

張紅巖

摘要：物流配送行業的迅速發展，使得物流配送網絡圖的規模迅速增加，數據量增長較快。現有的最短路徑問題大多基于傳統的最短路徑算法，在處理大規模網絡圖時存在計算較慢，甚至無法計算的問題。提出了基于雙區間索引的最短路徑算法，對圖中每個頂點建立雙區間索引，根據索引值對頂點的可達性進行快速判斷，把可達性查詢問題應用于物流配送網絡中求解最短路徑問題，可達到降低物流配送網絡圖規模，減少計算量，提高計算效率的效果。

關鍵詞：物流配送網絡；最短路徑；雙區間索引；可達性查詢

中圖分類號：TB文獻標識碼：Adoi：10.19311/j.cnki.16723198.2018.02.091

1引言

近年來，市場經濟快速發展，物流行業作為企業之間和企業與客戶之間聯系的橋梁發揮著巨大的作用。此外，對于以利潤最大化為最終目標的現代化企業來講，物流配送行業的優化，成為企業增加利潤的一個重要來源。因此，互聯網信息技術下物流行業發展迅速，并占據越來越重要的地位。

物流配送業務不同于一般的運輸業務，它是集運輸行業、現代信息網絡及后續加工管理等一系列活動于一體的綜合業務領域。隨著我國經濟快速發展，物流配送業務活動內容逐漸豐富，整體功能增加，使得物流配送網絡包含的物流節點越來越多，物流配送路線越來越復雜。因此，復雜物流配送網絡中的路徑優化問題成為現代物流運輸領域中一個重點問題。

物流配送活動中最基本的問題即最短路徑問題，旨在尋找一條從配送起始點到目標節點總距離最短的路徑。傳統的物流配送最短路徑問題主要注重于計算配送中心到目標節點的最短距離，而忽略了現實配送活動中的費用等路徑代價問題，應用到現實業務中具有一定的局限性。在現代物流配送活動中，對實際物流配送活動中的約束條件考慮更加全面，注重物流配送過程中的成本和代價的計算，在盡量滿足這些條件的前提下來得到整體最優路徑。

本文研究的內容是物流配送網絡圖中最短路徑的快速求解問題，并與可達性查詢問題相結合，提出了基于雙區間索引的剪枝策略，來縮減物流網絡圖的規模，從而提高求解最短路徑的效率。并參考文獻中提出的雙區間索引，應用于本文中的物流網絡圖上。在現有的求解最短路徑算法的基礎上，提出了結合剪枝策略的最短路徑求解算法，并通過實例驗證了本文算法的高效性。

2建立索引

雙區間索引是指分別為圖中的每個頂點建立先序索引區間和后序索引區間，分別記作Lu[x，y]和Ru[x，y]。基本思想為基于圖的遍歷方式，分別對圖中頂點進行先序遍歷和后序遍歷，各頂點的索引值依據頂點在圖中的遍歷順序得到，通過各頂點索引區間的包含關系，來判斷圖中頂點之間的可達性。

2.1先序索引區間方法

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

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

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

2.2后序索引區間方法

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

2.3圖例說明

圖1展示了該圖中各頂點的雙區間索引。

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

圖1先序/后序索引區間

3基于雙區間索引的剪枝算法

根據雙區間索引，可對圖中頂點間的不可達性進行判斷，并對不可達頂點進行剪枝，剪枝過程根據下述定理進行判斷。

定理：對于圖中的每一個頂點對（u，t），若LtLu或RtRu，則頂點u不可達頂點t（區間包含，不一定可達）。

證明：反證法。假定LtLu，且頂點u可達頂點t。根據雙區間所索引建立的過程，可知頂點u可達頂點t時，Lt（x）Lu（x）且Lt（y）

SymbolcB@ Lu（y），因此可知頂點u和頂點t的索引區間LtLu，這與LtLu矛盾，因此LtLu時，頂點u不可達頂點t。同理，可證明當RtRu時，頂點u不可達頂點t。證畢。

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

4結束語

本文把可達性查詢問題應用于物流配送網絡的最短路徑求解問題中，提出了基于雙區間索引的最短路徑算法。對物流配送網絡圖中的每個頂點分別建立先序索引區間及后序索引區間，根據各頂點索引區間的包含關系，判斷物流配送網絡圖中頂點間的不可達性，對不可達的頂點進行剪枝，在計算中不再考慮不可達的頂點，然后與傳統的最短路徑算法相結合，形成了基于雙區間索引的最短路徑算法，達到了縮減網絡圖規模，提高計算效率的效果。通過實例進行對比，證明了本文算法的高效性。

參考文獻

[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]忻瑞嬋.物流配送系統中大規模最短路徑算法的研究[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]關菲，張強.模糊多目標物流配送中心選址模型及其求解算法[J].中國管理科學， 2013，21（S1）：5762.

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

[6]韓世蓮，李旭宏，劉新旺.物流運輸網絡模糊最短路徑的偏好解[J].交通運輸工程學報，2005，（02）：122126.

[7]唐晉韜，王挺，王戟.適合復雜網絡分析的最短路徑近似算法[J].軟件學報， 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算法中多鄰接點與多條最短路徑問題[J].計算機科學， 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