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

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

0引言

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

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

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

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

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

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

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

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

2物流資源的封裝與組織

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

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

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

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

為了提高物流服務(wù)的搜索、匹配與調(diào)度的速度，避免因?yàn)槲锪鞣?wù)的組織形式降低物流服務(wù)的搜索、匹配與調(diào)度的效率，需要改進(jìn)物流服務(wù)的組織形式。本項(xiàng)目通過研究，擬將物流服務(wù)組織成物流服務(wù)云的形式。假定有一個(gè)物流服務(wù)S1，將其表示成S1((D1，D2)，(T1，T2)，TC，CC，SP，State)，假定D1到D2需要經(jīng)過D3，D4。由于D1到D3，D3到D4，D4到D2都需要時(shí)間，因此對(duì)時(shí)間區(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)。同時(shí)由于S11與S12，S12與S13中相鄰的服務(wù)可以兩兩求并，又能生成兩個(gè)新的物流服務(wù)S14((D1，D4)，(T1，T4)，TC14，CC14，SP14，State14)與S15((D3，D2)，(T3，T2)，TC15，CC15，SP15，State15）。圖1對(duì)上述服務(wù)的組織形式進(jìn)行了具體描述。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)物流請(qǐng)求者承擔(dān)的運(yùn)費(fèi)低于傳統(tǒng)物流；

(2)運(yùn)送時(shí)間滿足客戶需求；

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

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

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

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

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

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

(1)運(yùn)費(fèi)目標(biāo)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

If requesti、requestj相似則進(jìn)行合并request

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

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

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

End

}

6仿真試驗(yàn)

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

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

圖2中，z軸運(yùn)費(fèi)單價(jià)為cij，y軸運(yùn)量為xij，z軸為運(yùn)費(fèi)目標(biāo)。

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

6.2實(shí)驗(yàn)對(duì)比數(shù)據(jù)

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

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

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

7結(jié)論

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

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

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