利用基于云計算大數(shù)據(jù)的動態(tài)NSGA—II調(diào)度算法，加快了物流資源調(diào)度模型的求解速度

摘要：為提高草原生鮮產(chǎn)品的物流水平，促進草原生鮮產(chǎn)品物流的轉(zhuǎn)型升級，提出了一種新的云物流概念。在此基礎(chǔ)上，設(shè)計了一種面向草原生鮮產(chǎn)品的共享云物流資源優(yōu)化調(diào)度算法。該算法首先運用DFS、Mapreduce等大數(shù)據(jù)相關(guān)技術(shù)，實現(xiàn)并行計算并設(shè)計新的物流資源封裝與組織形式，分析當(dāng)前云物流資源調(diào)度算法方面存在的問題并提出解決方案。面向草原生鮮產(chǎn)品的共享云物流資源優(yōu)化調(diào)度算法采用動態(tài)NSGA-II（多目標(biāo)遺傳算法）資源規(guī)劃模型，尋找NSGA-II模型的快速求解方法，為云物流突破發(fā)展瓶頸提供解決方案。實驗表明，該算法調(diào)度高效、適用性強、穩(wěn)定性好，能有效提高當(dāng)前草原生鮮物流的水平，能夠促進當(dāng)前物流企業(yè)的轉(zhuǎn)型升級。

0引言

目前云物流的研究主要停留在概念及架構(gòu)方面，在云物流資源封裝、建模、調(diào)度、監(jiān)控與管理方面成果較少。同時，內(nèi)蒙古地區(qū)作為我國五大牧區(qū)之一，生鮮產(chǎn)品產(chǎn)量大、產(chǎn)能分散，傳統(tǒng)物流已經(jīng)不能適應(yīng)生鮮產(chǎn)品的配送需求[4-6]。針對這種現(xiàn)狀，豐富當(dāng)前云物流的內(nèi)涵，并將其用于滿足草原生鮮產(chǎn)品的配送需求，將為面向草原生鮮產(chǎn)品的云物流實現(xiàn)管理更高效、規(guī)劃更合理、運費更低廉、控制更精細、調(diào)整更及時的物流目標(biāo)提供實現(xiàn)途徑。

1云物流資源優(yōu)化調(diào)度算法概念描述

(1)服務(wù)請求：用戶發(fā)出的運送貨物請求，客戶端接收后，向服務(wù)端發(fā)出空間、時間、目的地等信息的請求，服務(wù)端對相應(yīng)請求作出響應(yīng)。

(2)虛擬化資源：將道路、運載工具、位置信息等用一個數(shù)據(jù)結(jié)構(gòu)表示。

(3)服務(wù)資源匹配算法：當(dāng)用戶發(fā)出對物流的請求時，服務(wù)端根據(jù)動態(tài)NSGA—II算法對服務(wù)器端的物流資源進行分配，使得利益、配送及時率、滿意度等達到最優(yōu)化。

(4)服務(wù)及時率：利用動態(tài)NSGA—II算法，當(dāng)benefit最大，time_cost、caclu_cost最小時，abs(由計算機算法得到的計算時間T+靈敏閾值Δt-實際運送時間t)/(T+Δt)。

(5)服務(wù)滿意度：當(dāng)benefit最大，time_cost、caclu_cost最小時，利用動態(tài)NSGA—II算法，使得用戶對于物流配送的滿意度達到最優(yōu)。

(6)物流服務(wù)請求屬性：物流服務(wù)請求用多個屬性進行描述。如果用D表示物流的空間區(qū)間，D1，D2分別表示源點與目的地；T表示時間區(qū)間，T1，T2分別表示最早出發(fā)時間與最晚到達時間；V表示體積；G表示重量；SP表示其他特殊要求集合如單價等，則一個基本的物流服務(wù)請求可以寫成SQ((D1，D2)，(T1，T2)，V，G，SP)。設(shè)服務(wù)請求具有n個屬性，可以表示成X={x1，x2，…，xn}，假定有m個類，分別用C1，C2，…，Cm表示。設(shè)兩個具有n個屬性的服務(wù)請求Xi，Xj，并表示成Xi={xi1，xi2，…，xin}，Xj={xj1，xj2，…，xjn}。

2物流資源的封裝與組織

2.1物流資源的虛擬化與服務(wù)化封裝

利用物聯(lián)網(wǎng)技術(shù)，實時掌握道路、運載工具的運行情況以及位置信息，利用大數(shù)據(jù)技術(shù)，對這些數(shù)據(jù)進行挖掘，用一個數(shù)據(jù)結(jié)構(gòu)來表示，就能夠完成物流資源的虛擬化。將虛擬化的物流資源封裝成物流云服務(wù)的形式，并將基礎(chǔ)的物流資源云服務(wù)組合成更復(fù)雜的物流資源云服務(wù)以便于在進行資源調(diào)度時加快匹配速度。由所有的物流資源云服務(wù)構(gòu)成了物流資源服務(wù)云。在資源調(diào)度時只需將服務(wù)請求交給物流資源服務(wù)云，就能以最快的速度搜索到與之匹配的物流服務(wù)。

如果物流服務(wù)用S表示，S應(yīng)該具備端點D1，D2，通行能力TC，運載能力CC，可用時間端點T1，T2，特殊屬性SP，資源狀態(tài)State（表示占用與否，位置信息，速度信息及其它信息的集合）。物流服務(wù)S可以寫成S((D1，D2)，(T1，T2)，TC，CC，SP，State)，表示在T1到T2時間段內(nèi)，在D1到D2區(qū)間，可以運送CC單位的貨物，同時道路通行能力為TC，狀態(tài)為State。因為TC大于CC，在CC不能滿足需要時，可以增加TC-CC的運力。

2.2物流服務(wù)特殊組織

為了提高物流服務(wù)的搜索、匹配與調(diào)度的速度，避免因為物流服務(wù)的組織形式降低物流服務(wù)的搜索、匹配與調(diào)度的效率，需要改進物流服務(wù)的組織形式。本項目通過研究，擬將物流服務(wù)組織成物流服務(wù)云的形式。假定有一個物流服務(wù)S1，將其表示成S1((D1，D2)，(T1，T2)，TC，CC，SP，State)，假定D1到D2需要經(jīng)過D3，D4。由于D1到D3，D3到D4，D4到D2都需要時間，因此對時間區(qū)間(T1，T2)，將其改寫成(T1，T2)=(T1，T3)U(T3，T4)U(T4，T2)的形式。S1可以寫成S1((D1，D2)，(T1，T2)，TC，CC，SP，State)=S11((D1，D3)，(T1，T3)，TC11，CC11，SP11，State11）US11((D3，D4)，(T3，T4)，TC12，CC12，SP12，State12)US13((D4，D2)，(T4，T2)，TC13，CC13，SP13，State13)。同時由于S11與S12，S12與S13中相鄰的服務(wù)可以兩兩求并，又能生成兩個新的物流服務(wù)S14((D1，D4)，(T1，T4)，TC14，CC14，SP14，State14)與S15((D3，D2)，(T3，T2)，TC15，CC15，SP15，State15）。圖1對上述服務(wù)的組織形式進行了具體描述。

3基于聚類與分類的服務(wù)請求的分解與合成

3.1服務(wù)請求的分類

給定一個未知的物流請求數(shù)據(jù)樣本X(即沒有類標(biāo)號)，若樸素貝葉斯分類法將未知的請求樣本X分配給類Ci，則一定是：

P(Ci|X)>P(Cj|X) 1≤j≤m，j≠i

因此，給定概率閾值，可以用樸素貝葉斯方法對服務(wù)請求進行分類。

3.2服務(wù)請求的聚類

兩個服務(wù)請求的相似度可以表示成：

SAME=(Xi∩Xj)/(Xi∪Xj)

根據(jù)服務(wù)請求之間的相似度，采用k-means 算法對服務(wù)請求進行聚類。

3.3服務(wù)請求的分解與合成

服務(wù)請求所需的運載能力、運輸時間要求等如果不能直接跟物流服務(wù)相匹配，都可以將其分解成多個服務(wù)請求。

具有相同目的、或者相近目的；或者是具有是類似屬性的服務(wù)請求，可以按照聚類與分類算法將其合并成一個或多個相同或相近類型的服務(wù)請求，并搜索相應(yīng)的物流服務(wù)與其匹配。

4物流方案的搜索與NSGA-II動態(tài)模型的建立4.1基于云計算的物流方案搜索方法

由于物流資源服務(wù)云是按照記錄的方式分散存放在云計算系統(tǒng)的各個節(jié)點上，在云計算的管理節(jié)點上存儲了各節(jié)點存儲記錄的元數(shù)據(jù)或者索引。利用云計算方式進行分布式搜索包括如下步驟：數(shù)據(jù)分片；分片數(shù)據(jù)搜索；分片數(shù)據(jù)匯總。

4.2模型目標(biāo)選擇與NSGA-II模型的建立

4.2.1 模型目標(biāo)選擇

由于本項目針對的是草原生鮮產(chǎn)品的云物流資源調(diào)度問題，設(shè)定如下調(diào)度目標(biāo)：

(1)物流請求者承擔(dān)的運費低于傳統(tǒng)物流；

(2)運送時間滿足客戶需求；

(3)算法運行時間與調(diào)度時間滿足資源調(diào)度效率與及時性要求；

(4)物流平臺收益不低于傳統(tǒng)物流企業(yè)；

(5)第四、五方關(guān)聯(lián)物流企業(yè)或資源提供方收益不低于預(yù)期；

(6)物流造成的環(huán)境污染低于政府部門規(guī)定；

(7)投訴的比例低于各方接受的閾值。

4.2.2NSGA-II規(guī)劃模型的建立

(1)運費目標(biāo)

針對單個任務(wù)請求，需要確定運費最低的方案。單個請求的第i個子任務(wù)的第j個運送方案的運費單價為cij，運量為xij，則該請求的運費目標(biāo)如式(1)所示：

運費目標(biāo)應(yīng)該是物流請求方、物流服務(wù)提供方、物流平臺運營方等多個方面協(xié)商的結(jié)果。

(2)時間目標(biāo)

針對一個單純的子任務(wù)而言，對于選定的物流路線，需要經(jīng)過一個或多個物流階段，每個階段都有一定的時間消耗。同時，在求解模型的過程中也需要一定的時間消耗。時間目標(biāo)如式(2)、式(3)所示，其中cttij，cctij，xij，分別為第i個子任務(wù)的第j個運送方案的單位運輸時間、單位計算時間與運量。

(3)收益目標(biāo)

針對一段時間而言，物流平臺企業(yè)的收益目標(biāo)即使不能最大化，但也需要不低于傳統(tǒng)物流企業(yè)。而傳統(tǒng)物流企業(yè)而言，作為物流平臺的第四方、第五方物流的收益不應(yīng)該低于以前做傳統(tǒng)物流的收益或者其他期望收益。物流平臺與物流企業(yè)的收益目標(biāo)如式(4)所示，其中ci、xi分別表示第i個物流任務(wù)的單價以及運量。

(4)滿意度目標(biāo)

對發(fā)貨方，要求將貨品按時、按質(zhì)送到收貨方；而對收貨方，也要求按時按質(zhì)收到貨品。雙方的滿意度指標(biāo)是物流方產(chǎn)生投訴因素越少，滿意度越高。因此，需要根據(jù)投訴的產(chǎn)生因素建立投訴目標(biāo)函數(shù)式(5)，且最小化。

4.3物流資源狀態(tài)的動態(tài)更新

為了達到對物流狀態(tài)盡量精確掌控的目的，就必須一方面通過物聯(lián)網(wǎng)技術(shù)對當(dāng)前交通與運載工具等物流資源運行情況進行準(zhǔn)實時監(jiān)控，并根據(jù)交通狀況的統(tǒng)計特性、天氣等外在因素可能對交通狀況造成的影響等等，通過大數(shù)據(jù)手段對這些統(tǒng)計量進行挖掘與更新。將更新后的數(shù)據(jù)代入靜態(tài)NSGA-II規(guī)劃模型，方便在T+Δt時間后更新模型參數(shù)，從而將靜態(tài)NSGA-II規(guī)劃模型變成動態(tài)NSGA-II規(guī)劃模型。

5生鮮產(chǎn)品云物流資源優(yōu)化調(diào)度算法描述

生鮮產(chǎn)品云物流資源優(yōu)化調(diào)度算法如下：

Main（）

{

Input(物流資源D1、D2、D3、D4…Di)

將物流資源按高級到基礎(chǔ)的順序放到資源服務(wù)云，高級用spark處理；

按級別創(chuàng)建block塊；

Request服務(wù)按P(Ci|X)>P(Cj|X) 1≤j≤m，j≠i進行分類；

If request〉2＆＆requesti與requestj不相似則分解request；

If requesti、requestj相似則進行合并request

相似度：SAME=(Xi∩Xj)/(Xi∪Xj)

Receive request 按照動態(tài)NSGA—II模型和cost、time_cost、caclu_cost函數(shù)值最小，s(x)接近于5進行執(zhí)行匹配，在執(zhí)行中benefit保證最大且靈敏度控制在Δt閾值中；

Output(cost、time_cost、caclu_cost、s(x)、benefit)；

End

}

6仿真試驗

6.1試驗數(shù)據(jù)分析

運費目標(biāo)仿真結(jié)果如表1和圖2所示。

圖2中，z軸運費單價為cij，y軸運量為xij，z軸為運費目標(biāo)。

時間目標(biāo)仿真試驗結(jié)果如表2和圖3、圖4所示。

6.2實驗對比數(shù)據(jù)

傳統(tǒng)的NSGA規(guī)劃模型的求解方法計算效率低，計算復(fù)雜度高，共享參數(shù)需要預(yù)先確定。為了提高模型求解的并行計算程度，從而有效地減少模型求解時間，本項目擬根據(jù)物流服務(wù)云的構(gòu)成，將高級的物流云服務(wù)按照基礎(chǔ)的物流云服務(wù)進行分解，同時將NSGA-II模型中與該高級物流云服務(wù)關(guān)聯(lián)的約束與目標(biāo)分解到基礎(chǔ)的云服務(wù)上。

將所有單個規(guī)劃模型組成任務(wù)池，每個云計算節(jié)點按照自己的運算速度在任務(wù)池中摘取需要計算的任務(wù)，并對單個規(guī)劃模型進行求解。在整體上來說，多個單個規(guī)劃模型同時在多個云計算節(jié)點上并行計算，其總的并行程度比求解傳統(tǒng)NSGA模型要高得多。

至于空間復(fù)雜度，由于測試數(shù)據(jù)有限所以未能準(zhǔn)確估計，有待進一步改善觀察。

7結(jié)論

根據(jù)實驗結(jié)果數(shù)據(jù)依據(jù)可得，該算法充分利用了第四方、第五方閑置資源，使得物流資源的規(guī)劃更合理；利用基于云計算的服務(wù)請求的分解與合成使得管理更高效；利用基于云計算大數(shù)據(jù)的動態(tài)NSGA—II調(diào)度算法，加快了物流資源調(diào)度模型的求解速度，使得模型的求解時間不再對物流資源的調(diào)度速度、精度以及對物流資源的控制效率造成明顯影響最終達到運費更低廉，控制更精細、調(diào)整更及時的目標(biāo)。該算法使得配送及時率達到89.60%，滿意度在3.75-4.7之間，相比傳統(tǒng)物流而言及時率提高了近12%，滿意度提高了近0.62。

其中在現(xiàn)實環(huán)境下?lián)碛懈鞣N影響下及時率的提高充分體現(xiàn)了物流資源調(diào)度的高效性、穩(wěn)定性，滿意度的提高充分體現(xiàn)了算法的適用性。而這些提高將在某種程度上改變生鮮產(chǎn)品云物流的水平，促進物流企業(yè)的轉(zhuǎn)型升級。

所有實驗結(jié)果均是依賴于部分內(nèi)蒙古草原生鮮數(shù)據(jù)資料，也就是說此結(jié)果和結(jié)論均具有局限性，所以后期的實踐與應(yīng)用將需要部分改善，已完成市場需求。