基于大數據平臺的動態車輛路徑調度算法

,,

(1.湖南師范大學 數學與計算機科學學院,長沙 410081; 2.湖南警察學院 信息技術系,長沙 410138)

0 概述

近年來,研究者對智能交通系統(Intelligent Transportation Systems,ITS)的研究越來越多,而智能交通系統中的車輛路徑問題(Vehicle Routing Problem,VRP)是目前電子商務物流配送決策中的熱點問題[1],也是帶多個約束條件的NP-難問題,如帶時間窗約束的車輛路徑問題[2](Vehicle Routing Problem with Time Windows,VRPTW)難以用常規方法求解,因而人們多致力于啟發式算法的研究。車輛路徑問題目前要處理來自多個數據源向其提供的數據收集服務[3],文獻[4]描述已經改變了傳統智能交通系統(TTS)的數據驅動。通過從各種來源收集大量的數據加工成有用的數據信息,數據驅動可以為車輛路徑優化提供新的服務[5],為動態車輛路徑問題提供新的依據。收集和組織來自多個實時不同來源數據,為智能交通供應鏈的決策提供依據是目前的主要挑戰[6],這主要是因為數據庫的規模非常大,同時沒有可用的實時分析工具。

當前智能交通系統路徑算法主要面臨的困難[7]有:從廣泛攜帶傳感器的車輛搜集所需位置數據集;收集從大量實時車輛數據提高及時警報;大量數據需要組織和實時處理;用于數據收集系統結構應該較易部署、低成本,以確保廣泛使用。本文利用大數據平臺對多源大量數據計算的優勢,構建動態車輛路徑調度模塊的體系框架,同時提出基于大數據平臺的動態車輛路徑調度算法(BDVRA)。該算法采用動態時間序列構建目標函數模型[8],實時設置警報標志動態修改車輛路徑調度策略。

1 基本問題模型

為說明動態車輛路徑問題[9],通過實例來說明實時更新路線的車輛路徑調度策略,如圖1所示。此問題涉及到食品供應鏈的供應節點和目標節點,供應節點可以是新鮮食品生產收集中心或暫時存儲食品倉庫的任意分布點,目的地可以是出售新鮮食品零售商店或被運送到其他地點之前冷藏保存食品倉庫的任意分布點。圖1中涉及到的所有車輛可以在任意位置開始或結束路線,路線的數量等于車輛的數量,即每輛車安排一條路線。每輛車在有限能力提供有限車載量的食品給目標節點,初始方案是每輛車在每個供應節點僅訪問一次。大數據分析計算平臺用于實時監控從所有的車輛和車輛路線上獲取的數據,如果在運輸途中供應食物的可能在某種條件導致變質,那么車輛路徑要實時更新變化。圖1顯示了從車輛實時數據分析后生成一個動態調度的實例,如:車輛P1在路徑1-2上產生一個警報而延誤了目標節點3的如期交貨時間,這個警報觸發了創建新路徑模塊,車輛1從節點2重新路由到目標節點4,而車輛2重新路由到目標節點3,車輛3重新路由到目標節點6。

圖1 基于警報實時更新路線示意圖

定義1(VRPTW問題) 設物流中心倉庫有k輛車,N={s},s=1,2,…,k,其中k為待定車輛數,每輛車載重能力為Ns=D;要為q個節點用戶供應,用戶節點集為U={m},m=0,1,…,q,當m=0時為中心倉庫;用戶m的需求量為dm,因此d0=0;用戶m的時間窗口為[xm,ym];從用戶m到用戶n的路程為Umn,行駛時間為Tmn;設車輛s到達用戶m的時間為Wms,則Wms∈[xm,ym]。如何進行車輛路徑調度,使調用的車輛數k最少,且總行車成本P最小。

根據VRPTW問題定義,其數學模型可以概述為:如果車輛s訪問客戶m后訪問客戶n,則Ymns=1;否則Ymns=0,其目標函數的一般形式[10]為:

(1)

n=1,2,…,k,s=1,2,…,q,n≠s

(2)

(3)

為了得出圖1中基于警報實時更新車輛路徑問題的數學模型,用一個時間序列的路線圖來描述,如圖2所示。

圖2 車輛路線時序示意圖

在圖2中,N是目標總數,K是車輛數,M是一輛車在一條路徑最大目標數,Di是從供應節點到目標節點i所需時間,Tmk0是車輛k第m趟開始時間,Tmk1是車輛k第m趟到達目標節點時間,Tmk2是車輛k第m趟到達目標節點時間,Si是在目標節點i的處理時間,Ri是車輛行駛到目標節點i的時間窗口,Wj0是到達目標節點j時間窗口的開始時間,Wj1是到達目標節點j時間窗口的結束時間。Xikm∈{0,1}是決策變量,其中,i∈{1,2,…,N},k∈{1,2,…,K},m∈{1,2,…,M}。如果目標節點i有車輛k的第m趟,則Xikm=1;否則Xikm=0。根據圖1的數學模型,可以得出圖2中食物供應運輸總成本的目標函數F:

(4)

k=1,2,…,K,s=1,2,…,q,n≠s

(5)

(6)

其中,ai是與目標節點i關聯的遲到罰款系數,即目標函數F的值由從供應節點到目標節點運輸成本和從供應節點到目標節點延遲罰款組成。

2 大數據平臺動態車輛路徑調度策略

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

圖3 大數據平臺動態車輛路徑體系結構

對收集到的數據進行處理以生成警報,在用戶指定的過濾器創建警報。警報創建模塊收集到一個警報位置(警報數據庫),被組織成一個HDFS可管理的數據結構。通過較少時間窗口的實時車輛位置和傳感器收集到的數據創建實時警報,也可以從過去的車輛位置和傳感器數據創建離線警報。因為使HDFS和MapReduce優化處理大文件、數據轉到一個記錄結構文件更有效,所以數據挖掘要將聚集本地磁盤的車輛位置和傳感器非結構化流數據轉換為結構化記錄文件,并通過在非結構化序列文件中解析記錄和提取傳感器相關知識,最后數據挖掘模塊將結構化的記錄移動到HDFS中。控制器模塊通過動態車輛路徑調度算法向所有車輛發送生成的新路徑線路,同時控制器能將當前附近的車輛新路徑線路和附加信息增加到動態車輛路徑數據中,用于實時更新路徑數據。

基于車輛實時數據的動態車輛路徑模塊的目的是降低新鮮食品的變質程度達到最小化。由于交通狀況變化,原來的路徑計劃進度一般會發生偏差,此外環境的變化,如:溫度的增加會導致冷卻系統故障。大數據分析平臺可以對所有動態車輛有一個全局視圖,在大數據計算平臺上動態車輛路徑模塊能為發生警報的車輛及時創建新線路。例如,一輛汽車在預定時間內不能達到預定目的地,可以在一個的食物變質有限時間窗口開始前,重新選擇到一個最接近目標的線路。應用大數據平臺,動態車輛路徑模塊了解車輛的狀態變量(如卡車容量、位置、速度、容器溫度等)對創建新線路很重要,這個新的路線能降低運輸車輛產生成本和食品變質率。目前常見的研究主要是利用車輛靜態的時間窗口優化車輛路徑減低運輸成本,本文利用大數據分析計算平臺支持多種車輛動態路徑算法的優勢,提出了一種新的動態車輛路徑算法。

基于大數據計算平臺動態車輛路徑調度算法,依托大數據計算平臺對數據處理的效率,如果某輛車在當前路徑有一個警報發生時,算法將基于當前位置和現有車載能力為車輛生成一個新的順序路徑表。如果找到一個可行的解決方案,新的順序路徑表通過車輛由控制器模塊發送到當前所有連接平臺的在線車輛。如果沒有找到可行解,當前車輛獲得本地生成的警報進行修復車輛路徑,例如:當前某車輛可以路由到最近的交貨地點,轉向原來沒有計劃的車輛路徑。本文算法應用大數據計算平臺為工具,采用目標函數及約束條件實現車輛運輸總成本最小化的優化解。

算法基于大數據計算平臺動態車輛路徑算法

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

輸出每輛車的最優路徑及路徑序列S={s1,s2,…,sk}

步驟1從大數據計算平臺獲取處理車輛路徑數據集;

步驟2初始化,從源端N0開始,初始化一個空路由表S,并置N=0;

步驟3如果所有目標節點N都被路由,則轉步驟5;

步驟4否則,計算其他沒有被路由目標點的成本函數F;

步驟4.1如果有目標節點發生警報,則獲得當前的位置和未路由的其他目標節點Ni;

步驟4.2目標節點Ni作為一個新的輸入,N=N+1;

步驟4.3找到了可行解,發送新的解給所有的車輛Ki;

步驟4.4否則,在當前位置標記警報,獲得局部解并為車輛提高警惕,轉步驟3;

步驟5整理調度序列S={s1,s2,…,sk},并輸出,結束。

3 實驗分析

為了驗證基于大數據計算平臺動態車輛路徑算法的正確性和效率,采用Sioux Fall網絡[12]進行數值模擬,網絡中包括24個節點和76條路段,節點之間的線路雙向運行的時間做了簡單修正,數值模擬的網絡如圖4所示。

圖4 Sioux Fall網絡

初始路線通過數據收集器從車輛主節點和傳感裝置收集動態時序數據得到,使用大數據分析軟件Hadoop進行預處理數據分析,MapReduce框架負責處理并行編程中分布式存儲、工作調度、負載均衡、容錯均衡、容錯處理以及網絡通信等復雜問題。本文求解BDVRA問題得到的初始路線如表1所示。

表1 初始線路

在模擬過程中,分別采用4條初始線路對本文算法以及傳統推動插入啟發式(Push-forward Insertion Heuristic,PFIH)算法[13]和基于禁忌(Tabu)搜索車輛路徑算法[14]進行數值模擬實驗。從表2可以看出,采用本文算法獲取的線路優化結果明顯優于傳統算法,表明本文算法是有效的;采用本文算法獲取的最優解,明顯優于PFIH和Tabu搜索算法,具體的結果如表2所示。

表2 3種算法優化結果比較

將模擬數值增加,進一步測試本文算法的時間性能,分別用10/4、50/10、100/20、500/50、1 000/100(分別表示路徑節點數/車輛數)數值對3種算法進行測試。本文為了評估大數據計算平臺框架處理的性能,進行了上述不同數量的車輛,同時使用Amazon Elastic Compute Cloud(EC2)基礎設施[15]進行實驗。圖5和圖6顯示了本文BDVRA算法與傳統基于推動插入啟發式(PFIH)算法和基于禁忌(Tabu)搜索車輛路徑算法在時間性能上進行比較。

圖5 3種算法運行的時間性能比較

圖6 3種算法目標函數F值比較

可以看出,隨著數據量增加時3種算法的運行時間和目標函數F值都隨之上升。但數據量在500/50時,PFIH和禁忌(Tabu)搜索算法明顯急劇上升,BDVRA由于利用大數據計算平臺對初始數據處理,在時間性能上有明顯優勢,如圖5所示。在整個車輛運輸總成本上,由于利用標記警報動態修改路徑算法,目標函數F的值也比其他2種算法優越,如圖6所示。

4 結束語

車輛路徑最優調度問題是一種組合優化問題,如果節點數量較多、車輛狀態無掌控、實時環境變化等,則無法獲取準確的最優解。為對車輛的運行路線進行合理的規劃,確保車輛總成本最小化,本文提出基于大數據計算模型的車輛路徑調度算法。該算法首先應用大數據計算平臺對數據進行收集、存儲、處理和分析計算,然后利用平臺MapReduce實現以幾秒鐘的時間上限創建實時警報并修改車輛路徑。該算法提高了數據分析處理速度,對推動啟發式搜索PFIH和禁忌(Tabu)搜索算法進行了優化,增強了算法實時動態處理能力,提高了算法尋優性能。下一步繼續將本文BDVRA算法應用到多個目標的動態車輛路徑調度問題中,求得多個解以有利于決策者做出正確的決策,為研究動態車輛路徑調度問題提供一種新的途徑與方法。

[1] 曹劍東,鄭四發,李 兵,等.動態車輛調度系統設計與開發[J].計算機工程,2008,34(7):280-282.

[2] 王 君,李 波,盧志剛.帶時間窗動態車輛路徑問題的優化調度策略[J].計算機工程,2012,38(13):137-141.

[3] 李妍峰,高自友,李 軍.基于實時交通信息的城市動態網絡車輛路徑優化問題[J].系統工程理論與實踐,2013,33(7):1813-1819.

[4] ZHANG J,WANG F,WANG K,et al.Data-driven Intelligent Transportation Systems:A Survey[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(4):1624-1639.

[5] CLAES R,HOLVOET T,WEYNS D.A Decentralized Approach for Anticipatory Vehicle Routing Using Delegate Multi-agent Systems[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(2):364-373.

[6] STEIL D A,PATE J R,KRAFT N A,et al.Patrol Routing Expression,Execution,Evaluation,and Engage-ment[J].IEEE Transactions on Intelligent Trans-portation Systems,2011,12(1):58-72.

[7] SCHMITT E,JULA H.Vehicle Route Guidance Systems:Classification and Comparison[C]//Proceedings of IEEE ITSC’06.Toronto,Canada:[s.n.],2006:242-247.

[6] PEARAFTIS H N.Dynamic;Vehicle Routing Problems[M].Berlin,Germany:Springer,1988.

[8] GHIANI G,GUERRIERO F,LAPORTE G,et al.Real-time Vehicle Routing:Solution Concepts,Algorithms and Parallel Computing Strategies[J].European Journal of Operational Research,2003,151(1):1-11.

[9] PILLAC V,GENDREAU M,GUERET C,et al.A Review of Dynamic Vehicle Routing Problems[J].European Journal of Operational Research,2013,225(1):1-11.

[10] POTVIN J Y,XU Y,BENYAHIA I.Vehicle Routing and Scheduling with Dynamic Travel Times[J].Com-puter & Operation Research,2006,33(4):1129-1137.

[11] TANIGUCHI E,SHIMAMOTO H.Intelligent Transportation System Based Dynamic Vehicle Routing and Scheduling with Variable Travel Times[J].Transportations Research Part C:Emerging Technologies,2004,12(3/4):235-250.

[12] LEBLANC L,MORLOK E K J,PIERSKALLA W P.An Efficient Approach to Solving the Road Network Equilibrium Traffic Assignment Problem[J].Trans-portations Research,1975,9(5):309-318.

[13] SOLOMON M M.Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J].Operations Research,1987,35(2):254-265.

[14] GLOVER F.Tabu Search Part I[J].ORSA Journal on Computing,1989,1(3):190-206.

[15] THANGIAH S R,OSMAN I H,VINAYAGAMOORTHY R.Algorithms for the Vehicle Routing Problems with Time Deadlines[J].American Journal of Mathematical and Management Sciences,1993,13(3/4):323-355.