唐德權(quán)，史偉奇

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

0 引 言

車輛路徑問題(vehicle routing problem,VRP)一直是網(wǎng)絡(luò)優(yōu)化問題中最基本的問題之一[1]。由于其應(yīng)用的廣泛性和經(jīng)濟(jì)上的重大價(jià)值，倍受國內(nèi)外學(xué)者的廣泛關(guān)注[2]。VRP是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個(gè)車隊(duì)負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，達(dá)到諸如路程最短、成本最小、耗費(fèi)時(shí)間最少等目的[3]。Flood提出的旅行商問題[4](traveling saleman problem,TSP)是VRP的特例，Gaery[5]已證明TSP問題是NP難題，因此VRP也屬于NP難題。

為了滿足目前大量車輛數(shù)據(jù)處理難的問題，嘗試?yán)么髷?shù)據(jù)知識服務(wù)平臺對數(shù)據(jù)進(jìn)行計(jì)算、分析和處理，并對傳統(tǒng)車輛路徑調(diào)度算法進(jìn)行優(yōu)化改進(jìn)[6]，為全局優(yōu)化線路提供決策依據(jù)。

文中提出一種基于大數(shù)據(jù)知識服務(wù)平臺的車輛路徑調(diào)度體系結(jié)構(gòu)，利用大數(shù)據(jù)計(jì)算工具和相關(guān)知識服務(wù)從各種來源收集數(shù)據(jù)，并且高效實(shí)時(shí)地對數(shù)據(jù)進(jìn)行存儲(chǔ)、處理和分析,為車輛路徑調(diào)度算法提供一個(gè)可伸縮的、高效和優(yōu)化的集成操作環(huán)境。

1 問題描述

1.1 VRP問題

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

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

圖1 VRP示意

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

(1)

1.2 大數(shù)據(jù)知識服務(wù)平臺車輛路徑調(diào)度體系結(jié)構(gòu)

(1)數(shù)據(jù)收集器。

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

(2)數(shù)據(jù)管理模塊。

對收集到的數(shù)據(jù)進(jìn)行處理、分析、過濾和存儲(chǔ)，然后收集到數(shù)據(jù)庫,形成一個(gè)HDFS能管理的數(shù)據(jù)結(jié)構(gòu)。

(3)數(shù)據(jù)挖掘模塊。

因?yàn)槭笻DFS和MapReduce優(yōu)化處理大文件、數(shù)據(jù)轉(zhuǎn)到一個(gè)記錄結(jié)構(gòu)文件更有效，所以數(shù)據(jù)挖掘要將聚集本地磁盤的車輛位置和傳感器非結(jié)構(gòu)化流數(shù)據(jù)轉(zhuǎn)換為結(jié)構(gòu)化記錄文件，并在非結(jié)構(gòu)化序列文件中解析記錄和提取傳感器相關(guān)知識，最后數(shù)據(jù)挖掘模塊將結(jié)構(gòu)化的記錄移動(dòng)到HDFS。

(4)能源經(jīng)濟(jì)政策和節(jié)能減排數(shù)據(jù)庫。

主要功能是用大數(shù)據(jù)分析平臺評價(jià)車輛路徑綜合管理指標(biāo)。大數(shù)據(jù)分析平臺需要法律政策數(shù)據(jù)庫系統(tǒng)和統(tǒng)計(jì)數(shù)據(jù)庫系統(tǒng)的支撐，主要包括評價(jià)指標(biāo)庫、標(biāo)桿庫、空間數(shù)據(jù)庫、政策法規(guī)庫等，實(shí)現(xiàn)指標(biāo)庫管理、指標(biāo)體系管理、標(biāo)桿庫管理、指標(biāo)查詢、指標(biāo)體系查詢、指標(biāo)對標(biāo)評價(jià)、達(dá)標(biāo)率統(tǒng)計(jì)、報(bào)表統(tǒng)計(jì)等功能，這些法律法規(guī)數(shù)據(jù)是車輛路徑調(diào)度管理決策依據(jù)。

(5)控制器。

控制器模塊通過車輛路徑調(diào)度算法向所有車輛發(fā)送當(dāng)前最小成本路線，同時(shí)控制器能將當(dāng)前附近的車輛新路徑線路和附加信息增加到動(dòng)態(tài)車輛路徑數(shù)據(jù)中，用于實(shí)時(shí)更新路徑數(shù)據(jù)。

大數(shù)據(jù)知識服務(wù)平臺體系結(jié)構(gòu)如圖2所示。

圖2 大數(shù)據(jù)知識服務(wù)平臺車輛路徑調(diào)度體系結(jié)構(gòu)

2 大數(shù)據(jù)知識服務(wù)平臺車輛路徑調(diào)度算法

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

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

輸入：車輛集K={1,2,…,k},目標(biāo)節(jié)點(diǎn)集N={0,1,…,n},N=0時(shí)為中心倉庫；

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

P0：從大數(shù)據(jù)知識服務(wù)平臺獲取處理車輛路徑數(shù)據(jù)集；

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

P2：如果所有節(jié)點(diǎn)都被訪問，則轉(zhuǎn)P10；

P3：否則，計(jì)算未被訪問節(jié)點(diǎn)成本按升序?qū)⑺鼈儾迦氲谝还?jié)點(diǎn)；

P4：在可行的時(shí)間和能力的限制條件下，從排序的列表中選擇第一個(gè)成本最少的節(jié)點(diǎn)c1；

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

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

P7：如果節(jié)點(diǎn)Ni的邊(ci,cj)之間的成本最低，插入(ci,cj)線路并更新當(dāng)前路線的成本。轉(zhuǎn)到P6；

P8：否則轉(zhuǎn)到P9；

P9：從N0開始規(guī)劃一條新路線，并且置R=R+1，轉(zhuǎn)P2；

P10：結(jié)束。

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

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

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

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

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

T3：大數(shù)據(jù)知識服務(wù)計(jì)算，強(qiáng)化當(dāng)前區(qū)域的解決方案P，更新候選列表保證列表的頂部為最佳解決方案；

T4：設(shè)置S0等于候選列表第一個(gè)解；

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

T6:如果Ci

T7:判斷是否用隨機(jī)跳產(chǎn)生隨機(jī)解做多元化和更新的候選列表；

T8:如果迭代的總數(shù)小于最大允許迭代次數(shù),則進(jìn)入T3；

T9:否則，算法結(jié)束。

3 數(shù)據(jù)模擬實(shí)驗(yàn)

為了驗(yàn)證基于大數(shù)據(jù)知識服務(wù)平臺動(dòng)態(tài)車輛路徑算法的正確性和有效性，開發(fā)了一個(gè)原型系統(tǒng)。數(shù)據(jù)來源于某物流配送公司，分別用10/4、50/10、100/20、500/50、1 000/100(路徑節(jié)點(diǎn)數(shù)/車輛數(shù))數(shù)據(jù)對算法進(jìn)行測試。

為了評估大數(shù)據(jù)計(jì)算平臺框架處理的性能,使用Amazon Elastic Compute Cloud (EC2)基礎(chǔ)設(shè)施進(jìn)行實(shí)驗(yàn)，結(jié)果如圖3和圖4所示。

圖3 PFIH與PFIH-BDP時(shí)間性能比較

圖4 TS和TS-BDP時(shí)間性能比較

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

4 結(jié)束語

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

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

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

[3] 殷 龍,衡紅軍.基于最鄰近算法的機(jī)場特種車輛調(diào)度應(yīng)用研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2016，26(7):151-155.

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

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

[6] 趙傳信,張雪東,季一木.改進(jìn)的粒子群算法在VRP中的應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展,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].管理工程學(xué)報(bào),2005,19(1):124-130.

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

[10] 張建勇,李 軍,郭耀煌.帶模糊預(yù)約時(shí)間的動(dòng)態(tài)VRP的插入啟發(fā)式算法[J].西南交通大學(xué)學(xué)報(bào),2008,43(1):107-113.

[11] 袁慶達(dá),閆 昱,周再玲.Tabu Search算法在優(yōu)化配送路線問題中的應(yīng)用[J].計(jì)算機(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] 李 剛,劉景發(fā).基于禁忌搜索的啟發(fā)式算法求解帶平衡約束的圓形裝填問題[J].中國科學(xué):信息科學(xué),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.