一種改進的車輛路徑調度算法研究

唐德權，史偉奇

(湖南警察學院 信息技術系，湖南 長沙 410138)

0 引 言

車輛路徑問題(vehicle routing problem,VRP)一直是網絡優化問題中最基本的問題之一[1]。由于其應用的廣泛性和經濟上的重大價值，倍受國內外學者的廣泛關注[2]。VRP是指一定數量的客戶，各自有不同數量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當的行車路線，目標是使得客戶的需求得到滿足，并能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的[3]。Flood提出的旅行商問題[4](traveling saleman problem,TSP)是VRP的特例，Gaery[5]已證明TSP問題是NP難題，因此VRP也屬于NP難題。

為了滿足目前大量車輛數據處理難的問題，嘗試利用大數據知識服務平臺對數據進行計算、分析和處理，并對傳統車輛路徑調度算法進行優化改進[6]，為全局優化線路提供決策依據。

文中提出一種基于大數據知識服務平臺的車輛路徑調度體系結構，利用大數據計算工具和相關知識服務從各種來源收集數據，并且高效實時地對數據進行存儲、處理和分析,為車輛路徑調度算法提供一個可伸縮的、高效和優化的集成操作環境。

1 問題描述

1.1 VRP問題

VRP的一般定義為一個三元組的圖G，即G=(V,E,C)，其中V={v0,v1,…,vn}是頂點集合，E={(vi,vj)|(vi,vj)∈V2,i≠j}是邊集合，C=(cij)(vi,vj)∈E是邊的權，表示距離、時間或運輸成本，頂點v0稱為倉庫，其余的頂點V代表需要服務的顧客或需求方[7]。VRP在于連接一組路線基于K相同的車輛在倉庫,這樣每個頂點訪問一次,同時達到目標函數即使得整個路線成本最小化[8]。

設有一倉庫V0，共有M輛貨車，車輛容量為Q，有N位顧客，每位顧客的需求量為D。車輛從V0出發，對顧客進行配送服務，最后返回V0，要求整個路線的頂點都被配送，每位顧客配送一次即可完成，且不能超過車輛容量Q，目標是車輛路線的總成本最小。在實際車輛路線圖中的權值C可能是時間或距離等問題的描述,如圖1所示。

圖1 VRP示意

根據VRPTW問題的定義，其數學模型可以描述為：如果車輛s訪問客戶m后訪問客戶n，則Ymns=1,否則Ymns=0。目標函數定義為：

(1)

1.2 大數據知識服務平臺車輛路徑調度體系結構

(1)數據收集器。

數據收集器從車輛主節點和傳感裝置收集動態時序數據，每個傳入的數據流映射到一個數據收集器節點[9]。每個數據收集器節點有數據聚合器、數據過濾器和數據存儲服務器模塊。對大量原始位置和傳感器車輛數據流形式的原始數據，使用大數據分析軟件Hadoop進行預處理數據分析。Hadoop是一個能夠對大量數據進行分布式處理的軟件框架，對數據預處理更有效率。另外，Hadoop實現了一個分布式文件系統(Hadoop distributed file system，HDFS)。在Hadoop中，用于執行MapReduce任務的機器角色有兩個：一個是JobTracker；另一個是TaskTracker。JobTracker用于調度工作，TaskTracker用于執行工作。一個Hadoop集群中只有一臺JobTracker。在分布式計算中，MapReduce框架負責處理并行編程中分布式存儲、工作調度、負載均衡、容錯均衡、容錯處理以及網絡通信等復雜問題，把處理過程高度抽象為兩個函數：map和reduce。map負責把任務分解成多個任務，reduce負責把分解后多任務處理的結果匯總起來。

(2)數據管理模塊。

對收集到的數據進行處理、分析、過濾和存儲，然后收集到數據庫,形成一個HDFS能管理的數據結構。

(3)數據挖掘模塊。

因為使HDFS和MapReduce優化處理大文件、數據轉到一個記錄結構文件更有效，所以數據挖掘要將聚集本地磁盤的車輛位置和傳感器非結構化流數據轉換為結構化記錄文件，并在非結構化序列文件中解析記錄和提取傳感器相關知識，最后數據挖掘模塊將結構化的記錄移動到HDFS。

(4)能源經濟政策和節能減排數據庫。

主要功能是用大數據分析平臺評價車輛路徑綜合管理指標。大數據分析平臺需要法律政策數據庫系統和統計數據庫系統的支撐，主要包括評價指標庫、標桿庫、空間數據庫、政策法規庫等，實現指標庫管理、指標體系管理、標桿庫管理、指標查詢、指標體系查詢、指標對標評價、達標率統計、報表統計等功能，這些法律法規數據是車輛路徑調度管理決策依據。

(5)控制器。

控制器模塊通過車輛路徑調度算法向所有車輛發送當前最小成本路線，同時控制器能將當前附近的車輛新路徑線路和附加信息增加到動態車輛路徑數據中，用于實時更新路徑數據。

大數據知識服務平臺體系結構如圖2所示。

圖2 大數據知識服務平臺車輛路徑調度體系結構

2 大數據知識服務平臺車輛路徑調度算法

用式(1)作為最小化目標函數的約束條件,基于大數據知識服務平臺對傳統的車輛路徑調度算法-向前推動插入啟發式[10](push forward insertion heuristic,PFIH)和禁忌搜索[11](tabu search,TS)進行改進。解決方案是通過最小化的目標函數，為每輛車選擇一條目標函數最小到達目的地路徑的順序[12]。TS是一種亞啟發式(meta-heuristic)隨機搜索算法[13]，它從一個初始可行解出發，選擇一系列的特定搜索方向(移動)作為試探，選擇實現讓特定目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中采用了一種靈活的“記憶”技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是Tabu表的建立。首先利用PFIH產生初始解決方案[14]，再利用禁忌搜索的車輛路徑(路線)算法得到全局車輛優化路徑。

算法1：基于大數據知識服務平臺PFIH產生初始解的算法(PFIH based on big data platform,PFIH-BDP)。

輸入：車輛集K={1,2,…,k},目標節點集N={0,1,…,n},N=0時為中心倉庫；

輸出：初始路徑序列P={p1,p2,…,pk}。

P0：從大數據知識服務平臺獲取處理車輛路徑數據集；

P1：從(N=0)開始，初始化一個空路線集，并且置R=1；

P2：如果所有節點都被訪問，則轉P10；

P3：否則，計算未被訪問節點成本按升序將它們插入第一節點；

P4：在可行的時間和能力的限制條件下，從排序的列表中選擇第一個成本最少的節點c1；

P5：將c1附加到當前路線R，并更新路線的總成本；

P6：計算N中沒有被訪問的節點,計算邊(ci,cj),并按序插入到R中；

P7：如果節點Ni的邊(ci,cj)之間的成本最低，插入(ci,cj)線路并更新當前路線的成本。轉到P6；

P8：否則轉到P9；

P9：從N0開始規劃一條新路線，并且置R=R+1，轉P2；

P10：結束。

算法2：基于大數據知識服務平臺禁忌搜索(tabu search based on big data platform,TS-BDP)的車輛路徑算法。

輸入：初始路徑序列P={p1,p2,…,pk}；

輸出：每輛車的最優路徑及路徑序列T={t1,t2,…,tk}。

T1：使用PFIH得到初始路徑P，并設置全局最佳解決方案等于當前的解決方案P=S*；

T2：初始化禁忌列表和候選列表并添加當前解決tabu列表中；

T3：大數據知識服務計算，強化當前區域的解決方案P，更新候選列表保證列表的頂部為最佳解決方案；

T4：設置S0等于候選列表第一個解；

T5:如果S0在禁忌列表中，從候選列表選擇下一個最佳解并將它置為S0；

T6:如果Ci

T7:判斷是否用隨機跳產生隨機解做多元化和更新的候選列表；

T8:如果迭代的總數小于最大允許迭代次數,則進入T3；

T9:否則，算法結束。

3 數據模擬實驗

為了驗證基于大數據知識服務平臺動態車輛路徑算法的正確性和有效性，開發了一個原型系統。數據來源于某物流配送公司，分別用10/4、50/10、100/20、500/50、1 000/100(路徑節點數/車輛數)數據對算法進行測試。

為了評估大數據計算平臺框架處理的性能,使用Amazon Elastic Compute Cloud (EC2)基礎設施進行實驗，結果如圖3和圖4所示。

圖3 PFIH與PFIH-BDP時間性能比較

圖4 TS和TS-BDP時間性能比較

由圖3和圖4所示，與傳統PFIH和TS算法相比較，基于大數據知識服務平臺的兩種改進算法在時間性能上具有一定優勢。與傳統算法相比，隨著數據量增加，兩種算法的運行時間都隨之上升。但數據量在500/50時，PFIH和TS算法的時間急劇上升，而基于大數據知識服務平臺的算法由于利用大數據計算平臺對初始數據進行了處理，在時間性能上有明顯優勢。

4 結束語

提出一種基于大數據知識服務平臺的車輛路徑調度算法。該算法利用大數據超性能計算工具對傳統算法進行優化，增強了算法收集和處理車輛數據的能力，提高了算法的時間性能。模擬實驗表明，改進后的兩個算法能夠有效處理車輛路徑調度問題，同時解決了傳統算法尋找最優解的問題，具有重要的參考價值。雖然該算法在數據模擬實驗中得到了較好的時間性能指標，但在實際應用中仍受到了一些限制，未來的研究工作將進一步對該算法進行優化。

[1] 湯雅連.配送中心選址與車輛路徑問題的優化[J].北京聯合大學學報：自然科學版，2014，28(3):47-52.

[2] 張 強,荊 剛,陳建嶺.車輛路線問題研究現狀及發展方向[J].交通科技,2004(1):60-62.

[3] 殷 龍,衡紅軍.基于最鄰近算法的機場特種車輛調度應用研究[J].計算機技術與發展,2016，26(7):151-155.

[4] 姜坤霖,李美安,張宏偉.面向旅行商問題的蟻群算法改進[J].計算機應用,2015，35:114-117.

[5] 祝崇雋,劉 民,吳 澄.供應鏈中車輛路徑問題的研究進展及前景[J].計算機集成制造系統，2001,7(11):1-6.

[6] 趙傳信,張雪東,季一木.改進的粒子群算法在VRP中的應用[J].計算機技術與發展,2008，18(6):240-242.

[7] CLAES R,HOLVOET T,WEYNS D.A decentralized approach for anticipatory vehicle routing using delegate multiagent systems[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(2):364-373.

[8] 劉云忠,宣慧玉.車輛路徑問題的模型及算法研究綜述[J].管理工程學報,2005,19(1):124-130.

[9] 鐘雪靈,王雄志.開放式車輛路徑問題的混合算法[J].計算機仿真,2011,28(8):207-210.

[10] 張建勇,李 軍,郭耀煌.帶模糊預約時間的動態VRP的插入啟發式算法[J].西南交通大學學報,2008,43(1):107-113.

[11] 袁慶達,閆 昱,周再玲.Tabu Search算法在優化配送路線問題中的應用[J].計算機工程,2001,27(11):86-89.

[12] SCHMITT E,JULA H.Vehicle route guidance systems:classification and comparison[C]//IEEE intelligent transportation systems conference.Toronto:IEEE,2006:242-247.

[13] 李 剛,劉景發.基于禁忌搜索的啟發式算法求解帶平衡約束的圓形裝填問題[J].中國科學:信息科學,2011,41(9):1076-1088.

[14] SOLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research,1987,35(2):254-265.