陳 燕, 于 放, 田 月, 劉 璐

1(中國(guó)科學(xué)院大學(xué), 北京 100049)

2(中國(guó)科學(xué)院 沈陽(yáng)計(jì)算技術(shù)研究所, 沈陽(yáng) 110168)

移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)等技術(shù)快速走向應(yīng)用, 現(xiàn)代物流技術(shù)正在實(shí)現(xiàn)跨越式發(fā)展.這種進(jìn)步正在深刻影響著社會(huì)信息化進(jìn)程, 以物流技術(shù)的發(fā)展?fàn)恳祟惿鐣?huì)的不斷進(jìn)步.正是現(xiàn)代物流技術(shù)的進(jìn)步使得人們能夠足不出戶的實(shí)現(xiàn)商品的消費(fèi), 交易便捷化也進(jìn)一步要求現(xiàn)代物流技術(shù)能夠更為快速地實(shí)現(xiàn)商品的配送.

車輛調(diào)度問(wèn)題主要分為靜態(tài)和動(dòng)態(tài)兩類.靜態(tài)車輛無(wú)法適應(yīng)動(dòng)態(tài)的運(yùn)營(yíng)環(huán)境, 現(xiàn)代車輛調(diào)度問(wèn)題研究熱點(diǎn)集中于動(dòng)態(tài)車輛調(diào)度以及結(jié)合數(shù)字地圖導(dǎo)航技術(shù)的動(dòng)態(tài)路徑規(guī)劃等方面.如馮亮等針對(duì)客戶需求、配送車輛實(shí)時(shí)匹配需求, 以GPS/GIS地圖數(shù)據(jù)為基礎(chǔ), 應(yīng)用混合遺傳算法實(shí)現(xiàn)了動(dòng)態(tài)車輛調(diào)度及路徑規(guī)劃, 能夠有效提升物流配送效率、降低物流企業(yè)成本以及改善物流服務(wù)質(zhì)量[1].并提出以客戶需求、配送車輛/節(jié)點(diǎn)以及路網(wǎng)狀態(tài)等為約束條件, 構(gòu)建了混合整數(shù)線性規(guī)劃模型, 同樣實(shí)現(xiàn)了動(dòng)態(tài)快速的車輛動(dòng)態(tài)調(diào)度及路徑規(guī)劃[2].對(duì)于能夠獲取公交車輛GPS數(shù)據(jù)的應(yīng)用場(chǎng)景, 針對(duì)公交車輛動(dòng)態(tài)調(diào)度問(wèn)題, 可利用大數(shù)據(jù)實(shí)現(xiàn)公交車輛相關(guān)參數(shù)的預(yù)測(cè), 并利用改進(jìn)遺傳算法實(shí)現(xiàn)車輛的高效調(diào)度[3].針對(duì)實(shí)時(shí)性要求更高的應(yīng)急車輛調(diào)度及配置問(wèn)題, 研究學(xué)者利用城市快速路網(wǎng)相對(duì)固定的特征, 通過(guò)構(gòu)建路網(wǎng)模型, 并利用混合蛙跳算法實(shí)現(xiàn)了快速準(zhǔn)確的路徑實(shí)時(shí)動(dòng)態(tài)規(guī)劃[4].而對(duì)于網(wǎng)購(gòu)配送過(guò)程中, 末端配送存在的需求隨機(jī)性強(qiáng)、配送服務(wù)時(shí)效性要求高等問(wèn)題, 提出了移動(dòng)配送模式, 并以配送與懲罰成本為目標(biāo)函數(shù), 對(duì)移動(dòng)配送模式的實(shí)時(shí)動(dòng)態(tài)求解進(jìn)行了驗(yàn)證, 從研究成果看該模型能夠有效提升配送反應(yīng)效率, 實(shí)現(xiàn)了高效車輛調(diào)度[5].顯然針對(duì)不同的應(yīng)用場(chǎng)景, 現(xiàn)有研究的算法難以通用化, 特別是大規(guī)模、高實(shí)時(shí)性的車輛調(diào)度問(wèn)題, 傳統(tǒng)啟發(fā)式算法是難以在實(shí)際應(yīng)用場(chǎng)景中確保實(shí)時(shí)性的.本文主要實(shí)現(xiàn)的就是現(xiàn)有車輛調(diào)度算法的高效并行處理,以提高處理大規(guī)模、高實(shí)時(shí)性車輛調(diào)度問(wèn)題的能力.

為此本文針對(duì)動(dòng)態(tài)車輛調(diào)度過(guò)程中對(duì)算法實(shí)時(shí)性要求高, 傳統(tǒng)啟發(fā)式算法性能難以滿足不確定環(huán)境下多約束的大規(guī)模車輛調(diào)度的現(xiàn)狀, 提出基于Hadoop的車輛調(diào)度算法優(yōu)化, 實(shí)現(xiàn)傳統(tǒng)啟發(fā)式算法的高效并行計(jì)算, 提升算法的加速比及擴(kuò)展性, 能夠有效大規(guī)模動(dòng)態(tài)車輛實(shí)時(shí)調(diào)度問(wèn)題.

1 傳統(tǒng)啟發(fā)式算法

1.1 遺傳算法基本原理

遺傳算法 (Genetic Algorithm, 簡(jiǎn)稱 GA)是應(yīng)用最早的現(xiàn)代啟發(fā)式優(yōu)化算法之一, 其基本原理是借鑒自然界生物“優(yōu)勝劣汰、適者生存”的進(jìn)化機(jī)制, 以遺傳變異理論為基礎(chǔ), 實(shí)現(xiàn)代際間的迭代搜索, 從而實(shí)現(xiàn)隨機(jī)全局搜索以及優(yōu)化.

遺傳算法通過(guò)設(shè)計(jì)一種代表生物進(jìn)化基因的編碼來(lái)實(shí)現(xiàn)代際間的迭代搜索, 其基本要素包括:編碼、種群、適應(yīng)度評(píng)估、選擇、交叉、變異等.通常包含以下步驟:(1)將問(wèn)題的參數(shù)進(jìn)行編碼;(2)生成初始群體;(3)計(jì)算群體中各個(gè)體的適應(yīng)度函數(shù)值;(4)按選擇策略選擇將要進(jìn)入下一代的個(gè)體;(5)按交叉概率Pc進(jìn)行交叉操作;(6)按變異概率Pm進(jìn)行變異操作;(7)如果不滿足終止準(zhǔn)則, 則轉(zhuǎn)到(3), 否則轉(zhuǎn)入下一步;(8)將適應(yīng)度函數(shù)值最優(yōu)的個(gè)體作為該問(wèn)題的最優(yōu)解,輸出[6].

1.2 粒子群算法基本原理

粒子群算法(PSO)屬于群智能算法的一種, 是通過(guò)模擬鳥(niǎo)群捕食行為設(shè)計(jì)的.假設(shè)區(qū)域里就只有一塊食物(即通常優(yōu)化問(wèn)題中所講的最優(yōu)解), 鳥(niǎo)群的任務(wù)是找到這個(gè)食物源.鳥(niǎo)群在整個(gè)搜尋的過(guò)程中, 通過(guò)相互傳遞各自的信息, 讓其他的鳥(niǎo)知道自己的位置, 通過(guò)這樣的協(xié)作, 來(lái)判斷自己找到的是不是最優(yōu)解, 同時(shí)也將最優(yōu)解的信息傳遞給整個(gè)鳥(niǎo)群, 最終, 整個(gè)鳥(niǎo)群都能聚集在食物源周圍, 即得到問(wèn)題最優(yōu)解.

粒子群算法通過(guò)設(shè)計(jì)一種無(wú)質(zhì)量的粒子來(lái)模擬鳥(niǎo)群中的鳥(niǎo), 粒子僅具有兩個(gè)屬性:速度V和位置X, 速度代表移動(dòng)的快慢, 位置代表移動(dòng)的方向.每個(gè)粒子在搜索空間中單獨(dú)的搜尋最優(yōu)解, 并將其記為當(dāng)前個(gè)體極值Pbest, 并將個(gè)體極值與整個(gè)粒子群里的其他粒子共享, 找到最優(yōu)的那個(gè)個(gè)體極值作為整個(gè)粒子群的當(dāng)前全局最優(yōu)解Gbest, 粒子群中的所有粒子根據(jù)自己找到的當(dāng)前個(gè)體極值Pbest和整個(gè)粒子群共享的當(dāng)前全局最優(yōu)解Gbest來(lái)調(diào)整自己的速度和位置.粒子群算法的思想相對(duì)比較簡(jiǎn)單, 主要分為:(1)初始化;(2)評(píng)價(jià)粒子,即計(jì)算適應(yīng)值;(3)尋找個(gè)體極值Pbest;(4)尋找全局最優(yōu)解Gbest;(5)修改粒子的速度和位置.

1.3 并行啟發(fā)式算法原理

并行啟發(fā)式算法的基本原理是基于現(xiàn)代并行計(jì)算的概念和原理, 同時(shí)融合現(xiàn)代啟發(fā)式算法的全局隨機(jī)搜索優(yōu)化能力, 使算法能夠更好的適用于大規(guī)模種群、動(dòng)態(tài)多樣性、更快的收斂速度和全局尋優(yōu)能力.目前, 并行啟發(fā)式算法已經(jīng)是大數(shù)據(jù)計(jì)算領(lǐng)域的熱點(diǎn)研究領(lǐng)域.其主要優(yōu)點(diǎn)包括:(1)并行啟發(fā)式算法染色體的并行編碼形式, 使初始種群具有很好的多樣性;(2)由單機(jī)全局搜索到多機(jī)局部搜索, 使算法實(shí)時(shí)性得以提高;(3)并行啟發(fā)式算法通過(guò)海量數(shù)據(jù)的預(yù)處理,能夠得到K個(gè)局部?jī)?yōu)化方案集, 提高了算法的求解質(zhì)量.

2 基于Hadoop的并行啟發(fā)式車輛調(diào)度算法

2.1 算法流程設(shè)計(jì)

基于Hadoop的車輛調(diào)度并行啟發(fā)式算法優(yōu)化主要分兩個(gè)階段:(1)利用并行遺傳算法算法對(duì)海量的車輛調(diào)度相關(guān)數(shù)據(jù)(路況的實(shí)時(shí)監(jiān)控視頻、車輛基本運(yùn)行狀況等)進(jìn)行預(yù)處理, 得到K個(gè)局部?jī)?yōu)化的調(diào)度及路徑規(guī)劃方案集(對(duì)創(chuàng)建的方案集進(jìn)行源節(jié)點(diǎn)和方案集是否為空判斷), 為下一步啟發(fā)式算法實(shí)現(xiàn)高效全局優(yōu)化奠定基礎(chǔ).(2)利用并行的啟發(fā)式算法(遺傳算法、粒子群算法等)對(duì)局部?jī)?yōu)化的調(diào)度及路徑規(guī)劃方案集進(jìn)行全局優(yōu)化搜索, 得到最優(yōu)的方案.基于Hadoop的并行遺傳算法充分利用Hadoop的主從計(jì)算模式, 通過(guò)數(shù)據(jù)并行方式, 實(shí)現(xiàn)大規(guī)模、高實(shí)時(shí)的車輛調(diào)度優(yōu)化.對(duì)某一區(qū)域內(nèi)的車輛調(diào)度數(shù)據(jù)進(jìn)行最短路徑分析, 得到局部的最短路徑方案集, 根據(jù)方案集生成向量列表,此時(shí)啟動(dòng)并行啟發(fā)式算法, 對(duì)車輛調(diào)度及路徑規(guī)劃方案集進(jìn)行全局優(yōu)化.主要的Map Reduce編程模型包括了Map、Combine和Reduce 3個(gè)階段.

在執(zhí)行此算法前, 集群主節(jié)點(diǎn)首先將已得到的簇類中心向量列表和簇中心數(shù)目廣播到各個(gè)子節(jié)點(diǎn)上.Map函數(shù)的輸入依然是各個(gè)數(shù)據(jù)塊集合, Map的輸入格式為形式, key1為對(duì)象 id, valuel為數(shù)據(jù)對(duì)象向量, Map函數(shù)的邏輯就是將本節(jié)點(diǎn)上的數(shù)據(jù)對(duì)象劃到離其最近的簇向量中去, 輸出格式也是, key2為簇向量標(biāo)識(shí)符, value2為數(shù)據(jù)對(duì)象向量.Map過(guò)程就將集群中的所有點(diǎn)都劃入到離其最近的簇中心向量中去, 這樣可能會(huì)使簇中心向量發(fā)生變化, 因此需要再次計(jì)算簇中心向量.

Combine函數(shù)的輸入是Map的輸出, 而此函數(shù)的輸出依然是鍵值對(duì)可以表示為, key3依然還是簇類向量標(biāo)識(shí)符,value3為相同key3的所有向量組合和這些向量的數(shù)目.

Reduce函數(shù)處理屬于同一簇的所有數(shù)據(jù)對(duì)象向量, 并重新生成新的簇類中心向量, 其輸入輸出均是鍵值對(duì)形式.此時(shí)調(diào)用傳統(tǒng)啟發(fā)式算法, 實(shí)現(xiàn)輸入數(shù)據(jù)對(duì)象的隨機(jī)快速搜索.

輸入信息是各個(gè)子節(jié)點(diǎn)的combine結(jié)果, 輸出信息是簇類標(biāo)識(shí)符和新的簇類中, 在每一次Reduce執(zhí)行完成后, 都需要將新的簇類中心向量與前一次的簇類中心向量進(jìn)行比較如果滿足上文給出的聚類準(zhǔn)則函數(shù)就可結(jié)束迭代, 即認(rèn)可聚類結(jié)果已收斂.具體流程如圖1所示.

圖1 基于 Hadoop的并行啟發(fā)式算法流程

2.2 遺傳算法的MapReduce并行過(guò)程

(1) Map函數(shù)

種群適應(yīng)值函數(shù)的計(jì)算(步驟(3)和(7))匹配Map函數(shù), 它必須獨(dú)立于其他實(shí)例來(lái)計(jì)算.利用Map函數(shù)基本定義, 計(jì)算給定個(gè)體的適應(yīng)值.并且將最好的個(gè)體的路徑保存下來(lái)最終寫(xiě)到分布式文件系統(tǒng)HDFS的全局文件中.初始化任務(wù)的客戶端, 在MapReduce結(jié)束時(shí)從mapper中讀取這些值并檢查收斂條件是否滿足.GA每次迭代的Map過(guò)程偽代碼:

(2) C.Partitioner

若GA的選擇算子(步驟(4))在每個(gè)節(jié)點(diǎn)本地執(zhí)行, 空間約束將會(huì)人為引入并降低選擇壓力, 并可能導(dǎo)致收斂時(shí)間增加.因此, 去中心化的、分布式的選擇算法成為首選.MapReduce模型唯一的全局通信點(diǎn)是Map和Reduce之間的Shuffle.在Map階段的最后,MapReduce框架使用分區(qū)將key/value對(duì)輸出給Reduce過(guò)程.分區(qū)會(huì)將中間的key/value對(duì)在各個(gè)Reduce之間進(jìn)行拆分.函數(shù)GetPartition()返回給定的(key, value)應(yīng)該發(fā)送給的 Reducer.在默認(rèn)應(yīng)用中, 它使用Hash(key)%numReducers, 以便具有相同key的值分配給同一個(gè)reducer, 從而可以應(yīng)用Reduce函數(shù).通過(guò)構(gòu)建適宜的分區(qū)工具, 隨機(jī)地把個(gè)體分配給不同的Reducer.GA的隨機(jī)分割過(guò)程偽代碼:

(3) Reduce過(guò)程

采用無(wú)替換競(jìng)爭(zhēng)選擇算子.一場(chǎng)競(jìng)爭(zhēng)在S個(gè)隨機(jī)選擇的個(gè)體直接進(jìn)行, 選出其中的贏家.重復(fù)這個(gè)過(guò)程,重復(fù)次數(shù)為種群大小.由于隨機(jī)選擇個(gè)體相當(dāng)于隨機(jī)對(duì)所有個(gè)體洗牌并按順序處理它們, Reduce函數(shù)也按順序處理每個(gè)個(gè)體.最初的個(gè)體為最后一輪競(jìng)賽而緩存, 當(dāng)比賽窗口滿了, 執(zhí)行 SelectionAndCrossover算法.當(dāng)交叉窗口滿了, 我們使用隨機(jī)交叉算子.在實(shí)際應(yīng)用中, 可將S設(shè)為5, 交叉算子采用選出的兩個(gè)連續(xù)的父代個(gè)體進(jìn)行.GA每次迭代的Reduce過(guò)程偽代碼:

3 實(shí)驗(yàn)及結(jié)果分析

3.1 Hadoop環(huán)境構(gòu)建

環(huán)境構(gòu)建分為硬件環(huán)境和軟件環(huán)境, 其中Hadoop計(jì)算節(jié)點(diǎn) 4個(gè), 操作系統(tǒng)為 Cent OS, 具體參數(shù)如下:

硬件環(huán)境:4臺(tái)PC機(jī);

軟件環(huán)境:操作系統(tǒng):Cent OS 6.5版本;JDK:1.8版本;Hadoop:3.0版本;Mahout:0.12.1版本.

3.2 計(jì)算實(shí)例及分析

本文通過(guò)Maple軟件實(shí)現(xiàn)配送網(wǎng)絡(luò)和驗(yàn)證數(shù)據(jù)的隨機(jī)產(chǎn)生, 采用少量數(shù)據(jù)就能夠發(fā)現(xiàn)基于Hadoop的并行啟發(fā)式遺傳算法的高效性, 而Hadoop本身具有處理大數(shù)據(jù)的能力.為在論文中體現(xiàn)數(shù)據(jù)真實(shí)性, 采用隨機(jī)產(chǎn)生的方式以少量數(shù)據(jù)進(jìn)行示例性說(shuō)明(大量數(shù)據(jù)無(wú)法在文中展示, 也不利于論文結(jié)果重現(xiàn)).假設(shè)配送區(qū)域限定為 100×100 km2的正方形區(qū)域, 利用 rand 函數(shù)隨機(jī)獲得20個(gè)靜態(tài)需求位置數(shù)據(jù)和10個(gè)動(dòng)態(tài)需求位置數(shù)據(jù), 配送車輛最大配送體積為9 m3, 單個(gè)需求的體積最大為 3 m3, 車輛最大配送距離為 100 km, 配送中心的位置設(shè)定為 O(50 km, 50 km).隨機(jī)產(chǎn)生的靜態(tài)需求位置數(shù)據(jù)如表1所示, 動(dòng)態(tài)需求位置數(shù)據(jù)如表2所示.

表1 靜態(tài)需求位置數(shù)據(jù)

表2 動(dòng)態(tài)需求位置數(shù)據(jù)

為了驗(yàn)證基于Hadoop的車輛調(diào)度算法改進(jìn)性能,對(duì)上述車輛調(diào)度問(wèn)題進(jìn)行求解, 得到基于遺傳算法、基于粒子群算法以及基于Hadoop的車輛調(diào)度算法的基本收斂性能, 如圖2所示.

由圖2可知, 三種算法中基于Hadoop的車輛調(diào)度算法能夠在 2 0代后實(shí)現(xiàn)快速收斂, 這得益于Hadoop并行遺傳算法的局部可行解集的提前獲取和全局并行計(jì)算的收斂性.

其次對(duì)比分析三者的搜索成功率、優(yōu)化調(diào)度時(shí)間等基本性能, 如表3所示, 可以看出三種算法中基于Hadoop的車輛調(diào)度改進(jìn)算法能夠?qū)崿F(xiàn)全方位的性能提升, 特別是在收斂時(shí)間和平均迭代次數(shù)上.在車輛調(diào)度節(jié)點(diǎn)數(shù)量為靜態(tài)20, 動(dòng)態(tài)數(shù)量為10的情況下, 利用4臺(tái)PC機(jī), 計(jì)算時(shí)間由傳統(tǒng)啟發(fā)式算法大約17.5 s左右降低到3.1 s.對(duì)于更大規(guī)模的多約束高實(shí)時(shí)車輛動(dòng)態(tài)調(diào)度問(wèn)題而言, 基于Hadoop的并行遺傳算法能夠更快響應(yīng)需求.

圖2 算法收斂性能

表3 算法計(jì)算結(jié)果

4 結(jié)論

本文針對(duì)傳統(tǒng)車輛調(diào)度算法在處理動(dòng)態(tài)、實(shí)時(shí)、大規(guī)模車輛調(diào)度存在的不足, 特別是啟發(fā)式算法對(duì)初始種群敏感, 充分利用Hadoop在處理海量數(shù)據(jù)的快速性、計(jì)算效率等特性, 提出了一種基于Hadoop的車輛調(diào)度并行優(yōu)化算法, 快速獲取可行的區(qū)域最短路徑規(guī)劃方案集, 并通過(guò)Map Reduce并行編程框架實(shí)現(xiàn)該算法來(lái)適應(yīng)大規(guī)模車輛調(diào)度問(wèn)題, 有效提高車輛調(diào)度算法的計(jì)算實(shí)時(shí)性及優(yōu)化性能.仿真結(jié)果驗(yàn)證了該算法在處理大規(guī)模車輛調(diào)度問(wèn)題時(shí)具有良好的全局優(yōu)化能力、計(jì)算加速比以及模型擴(kuò)展能力.