生鮮產品的共享雲物流資源優化調度演算法

摘要：為提高草原生鮮產品的物流水平，促進草原生鮮產品物流的轉型升級，提出了一種新的雲物流概念。在此基礎上，設計了一種面向草原生鮮產品的共享雲物流資源優化調度演算法。該演算法首先運用DFS、Mapreduce等大數據相關技術，實現並行計算並設計新的物流資源封裝與組織形式，分析當前雲物流資源調度演算法方面存在的問題並提出解決方案。面向草原生鮮產品的共享雲物流資源優化調度演算法採用動態NSGA-II（多目標遺傳演算法）資源規劃模型，尋找NSGA-II模型的快速求解方法，為雲物流突破發展瓶頸提供解決方案。實驗表明，該演算法調度高效、適用性強、穩定性好，能有效提高當前草原生鮮物流的水平，能夠促進當前物流企業的轉型升級。

引言

目前雲物流的研究主要停留在概念及架構方面，在雲物流資源封裝、建模、調度、監控與管理方面成果較少[1-3]。同時，內蒙古地區作為我國五大牧區之一，生鮮產品產量大、產能分散，傳統物流已經不能適應生鮮產品的配送需求[4-6]。針對這種現狀，豐富當前雲物流的內涵，並將其用於滿足草原生鮮產品的配送需求，將為面向草原生鮮產品的雲物流實現管理更高效、規劃更合理、運費更低廉、控制更精細、調整更及時的物流目標提供實現途徑[8-9]。

1

雲物流資源優化調度演算法概念描述

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

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

(3)服務資源匹配演算法：當用戶發出對物流的請求時，服務端根據動態NSGA—II演算法對伺服器端的物流資源進行分配，使得利益、配送及時率、滿意度等達到最優化。

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

(5)服務滿意度：當benefit最大，time_cost、caclu_cost最小時，利用動態NSGA—II演算法，使得用戶對於物流配送的滿意度達到最優。

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

2

物流資源的封裝與組織

2.1

物流資源的虛擬化與服務化封裝

利用物聯網技術，實時掌握道路、運載工具的運行情況以及位置信息，利用大數據技術，對這些數據進行挖掘，用一個數據結構來表示，就能夠完成物流資源的虛擬化。將虛擬化的物流資源封裝成物流雲服務的形式，並將基礎的物流資源雲服務組合成更複雜的物流資源雲服務以便於在進行資源調度時加快匹配速度。由所有的物流資源雲服務構成了物流資源服務雲。在資源調度時只需將服務請求交給物流資源服務雲，就能以最快的速度搜索到與之匹配的物流服務。

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

2.2

物流服務特殊組織

為了提高物流服務的搜索、匹配與調度的速度，避免因為物流服務的組織形式降低物流服務的搜索、匹配與調度的效率，需要改進物流服務的組織形式。本項目通過研究，擬將物流服務組織成物流服務雲的形式。假定有一個物流服務S1，將其表示成S1((D1，D2)，(T1，T2)，TC，CC，SP，State)，假定D1到D2需要經過D3，D4。由於D1到D3，D3到D4，D4到D2都需要時間，因此對時間區間(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中相鄰的服務可以兩兩求並，又能生成兩個新的物流服務S14((D1，D4)，(T1，T4)，TC14，CC14，SP14，State14)與S15((D3，D2)，(T3，T2)，TC15，CC15，SP15，State15）。圖1對上述服務的組織形式進行了具體描述。

3

基於聚類與分類的服務請求的分解與合成

3.1

服務請求的分類

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

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

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

3.2

服務請求的聚類

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

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

根據服務請求之間的相似度，採用k-means 演算法對服務請求進行聚類。

3.3

服務請求的分解與合成

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

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

4

物流方案的搜索與NSGA-II動態模型的建立

4.1

基於雲計算的物流方案搜索方法

由於物流資源服務雲是按照記錄的方式分散存放在雲計算系統的各個節點上，在雲計算的管理節點上存儲了各節點存儲記錄的元數據或者索引。利用雲計算方式進行分散式搜索包括如下步驟：數據分片；分片數據搜索；分片數據匯總。

4.2

模型目標選擇與NSGA-II模型的建立

4.2.1 模型目標選擇

由於本項目針對的是草原生鮮產品的雲物流資源調度問題，設定如下調度目標：

(1)物流請求者承擔的運費低於傳統物流；

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

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

(4)物流平台收益不低於傳統物流企業；

(5)第四、五方關聯物流企業或資源提供方收益不低於預期；

(6)物流造成的環境污染低於政府部門規定；

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

4.2.2 NSGA-II規劃模型的建立

(1)運費目標

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

運費目標應該是物流請求方、物流服務提供方、物流平台運營方等多個方面協商的結果。

(2)時間目標

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

(3)收益目標

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

(4)滿意度目標

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

4.3

物流資源狀態的動態更新

為了達到對物流狀態盡量精確掌控的目的，就必須一方面通過物聯網技術對當前交通與運載工具等物流資源運行情況進行准實時監控，並根據交通狀況的統計特性、天氣等外在因素可能對交通狀況造成的影響等等，通過大數據手段對這些統計量進行挖掘與更新。將更新後的數據代入靜態NSGA-II規劃模型，方便在T+Δt時間後更新模型參數，從而將靜態NSGA-II規劃模型變成動態NSGA-II規劃模型。

5

生鮮產品雲物流資源優化調度演算法描述

生鮮產品雲物流資源優化調度演算法如下：

Main（）

{

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

將物流資源按高級到基礎的順序放到資源服務雲，高級用spark處理；

按級別創建block塊；

Request服務按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 按照動態NSGA—II模型和cost、time_cost、caclu_cost函數值最小，s(x)接近於5進行執行匹配，在執行中benefit保證最大且靈敏度控制在Δt閾值中；

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

End

}

6

模擬試驗

6.1

試驗數據分析

運費目標模擬結果如表1和圖2所示。

圖2中，z軸運費單價為cij，y軸運量為xij，z軸為運費目標。

時間目標模擬試驗結果如表2和圖3、圖4所示。

6.2

實驗對比數據

傳統的NSGA規劃模型的求解方法計算效率低，計算複雜度高，共享參數需要預先確定。為了提高模型求解的並行計算程度，從而有效地減少模型求解時間，本項目擬根據物流服務雲的構成，將高級的物流雲服務按照基礎的物流雲服務進行分解，同時將NSGA-II模型中與該高級物流雲服務關聯的約束與目標分解到基礎的雲服務上。

將所有單個規劃模型組成任務池，每個雲計算節點按照自己的運算速度在任務池中摘取需要計算的任務，並對單個規劃模型進行求解。在整體上來說，多個單個規劃模型同時在多個雲計算節點上並行計算，其總的並行程度比求解傳統NSGA模型要高得多。

至於空間複雜度，由於測試數據有限所以未能準確估計，有待進一步改善觀察。

7

結論

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

其中在現實環境下擁有各種影響下及時率的提高充分體現了物流資源調度的高效性、穩定性，滿意度的提高充分體現了演算法的適用性。而這些提高將在某種程度上改變生鮮產品雲物流的水平，促進物流企業的轉型升級。

所有實驗結果均是依賴於部分內蒙古草原生鮮數據資料，也就是說此結果和結論均具有局限性，所以後期的實踐與應用將需要部分改善，已完成市場需求。

參考文獻

[1] DIXIT V S，CHHABRA S.Logistics business under the cloud computing framework[C].Computational Science and Its Applications(ICCSA)，2015 15th International Conference on Year.2015：96-99.

[2] 王琦峰，呂紅波，江瑜.雲物流體系結構與應用模式研究[J].電信科學，2012(3)：126-132.

[3] 張水旺，胡小建.雲物流概念模型及其運作機理研究[J].科技管理研究，2015(19)：186-190.

[4] 張向陽，袁澤沛.網購時代我國「智慧雲物流」平台體系與協同運營模式研究[J].中國科技論壇，2013(7)：99-104.

[5] 孫振興.農產品的雲物流平台構建研究綜述[J].生產力研究，2015(4)：157-160.

[6] 丁麗芳.雲物流環境下的農物商一體化農產品物流模式[J].中國流通經濟，2014(6)：41-45.

[7] 孟魁.我國農產品雲物流模式的整合路徑研究[J].湖北農業科學，2015，54(4)：1010-1013.

[8] Kyung-Hyun Choi，Dong-Soo Kim，Yang-Hoi Doh.Multi-agent-based task assignment system for virtual enterprises[J].Management Science，2012(7)：1634-1646.

[9] Normanr Lofts.Multiple allocation of resources in a Network-an optimal scheduling algorithm[J].Future Generation Computer Systems，2010，14(6)：213-218.

作者信息:

史寶珠，李美安，左玉暉

（內蒙古農業大學 計算機與信息工程學院，內蒙古 呼和浩特010018）

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！