陳 燕, 于 放, 田 月, 劉 璐

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

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

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

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

為此本文針對動態(tài)車輛調(diào)度過程中對算法實(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ī)模動態(tài)車輛實(shí)時調(diào)度問題.

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

1.1 遺傳算法基本原理

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

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

1.2 粒子群算法基本原理

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

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

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

并行啟發(fā)式算法的基本原理是基于現(xiàn)代并行計(jì)算的概念和原理, 同時融合現(xiàn)代啟發(fā)式算法的全局隨機(jī)搜索優(yōu)化能力, 使算法能夠更好的適用于大規(guī)模種群、動態(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í)時性得以提高;(3)并行啟發(fā)式算法通過海量數(shù)據(jù)的預(yù)處理,能夠得到K個局部優(yōu)化方案集, 提高了算法的求解質(zhì)量.

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

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

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

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

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

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

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

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

2.2 遺傳算法的MapReduce并行過程

(1) Map函數(shù)

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

(2) C.Partitioner

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

(3) Reduce過程

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

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個, 操作系統(tǒng)為 Cent OS, 具體參數(shù)如下:

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

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

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

本文通過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)行示例性說明(大量數(shù)據(jù)無法在文中展示, 也不利于論文結(jié)果重現(xiàn)).假設(shè)配送區(qū)域限定為 100×100 km2的正方形區(qū)域, 利用 rand 函數(shù)隨機(jī)獲得20個靜態(tài)需求位置數(shù)據(jù)和10個動態(tài)需求位置數(shù)據(jù), 配送車輛最大配送體積為9 m3, 單個需求的體積最大為 3 m3, 車輛最大配送距離為 100 km, 配送中心的位置設(shè)定為 O(50 km, 50 km).隨機(jī)產(chǎn)生的靜態(tài)需求位置數(shù)據(jù)如表1所示, 動態(tài)需求位置數(shù)據(jù)如表2所示.

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

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

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

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

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

圖2 算法收斂性能

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

4 結(jié)論

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