基于遺傳算法的物流云服務(wù)平臺(tái)任務(wù)調(diào)度研究

（重慶郵電大學(xué) 經(jīng)濟(jì)管理學(xué)院，重慶 400065）

0 引言

隨著“大數(shù)據(jù)（Big data）”時(shí)代的到來，各行各業(yè)的業(yè)務(wù)數(shù)據(jù)如海量洪流般的產(chǎn)生，數(shù)據(jù)以及數(shù)據(jù)處理對(duì)企業(yè)的發(fā)展和創(chuàng)新有著至關(guān)重要的作用。物流業(yè)作為我國的戰(zhàn)略性基礎(chǔ)性產(chǎn)業(yè)，必然也會(huì)受“大數(shù)據(jù)”時(shí)代的影響，人們對(duì)物流服務(wù)的需求更加多樣化和復(fù)雜化，物流運(yùn)單信息呈現(xiàn)海量增長趨勢（尤其是在“雙11”、“購物狂歡節(jié)”等節(jié)假日時(shí)期，各大電商平臺(tái)促銷活動(dòng)激烈，導(dǎo)致人們的消費(fèi)行為高度集中），更要求物流調(diào)度對(duì)市場變化具有更高的靈敏性和適應(yīng)性，而物流調(diào)度的主要難點(diǎn)在于如何用更少的時(shí)間對(duì)需求不同、運(yùn)單量極大的物流服務(wù)進(jìn)行快速合理的分配。

近年來，在云計(jì)算、物聯(lián)網(wǎng)和供應(yīng)鏈管理的綜合模式下，產(chǎn)生了一種新型物流服務(wù)模式，即物流云服務(wù)（Logistics Cloud Service，LCS）。物流云服務(wù)是一種在網(wǎng)絡(luò)技術(shù)支持下，通過物流云服務(wù)平臺(tái)整合物流資源和客戶資源從而形成對(duì)應(yīng)的物流資源云，并根據(jù)客戶需求智能管理和調(diào)配物流資源，為客戶提供便捷、優(yōu)質(zhì)的個(gè)性化物流服務(wù)。與以往的物流服務(wù)模式相比，物流云服務(wù)更加注重服務(wù)的專業(yè)化和個(gè)性化，通過構(gòu)建按需供應(yīng)、資源高度共享的物流云服務(wù)平臺(tái)來實(shí)現(xiàn)對(duì)全社會(huì)物流資源的分配和調(diào)度?；谶@種模式，客戶可以快捷地享受到最適合的物流服務(wù)，而作為物流服務(wù)提供方也能以最少的時(shí)間對(duì)物流資源進(jìn)行調(diào)度分配來滿足客戶的個(gè)性化需求。但是，由于我國物流行業(yè)起步較晚，物流云服務(wù)模式尚在發(fā)展初期，針對(duì)如何快速地實(shí)現(xiàn)物流資源與需求任務(wù)的動(dòng)態(tài)組合、智能匹配和優(yōu)化調(diào)度的相關(guān)研究就尤為重要。

關(guān)于物流云服務(wù)以及物流云服務(wù)模式下的任務(wù)調(diào)度研究，國內(nèi)外學(xué)者取得了一定的成果。林云等人認(rèn)為物流服務(wù)具有云計(jì)算的技術(shù)特征，提出了面向供應(yīng)鏈的物流云服務(wù)模式；陳典斌探討了物流云服務(wù)的設(shè)計(jì)與運(yùn)行措施；徐驍勇等人以任務(wù)執(zhí)行時(shí)間與能耗作為優(yōu)化目標(biāo)，建立了一個(gè)節(jié)能調(diào)度模型，并將非支配排序遺傳算法（NSGA-II）應(yīng)用于云計(jì)算的節(jié)能調(diào)度問題；鄭小強(qiáng)等人提出了一種云遺傳算法來解決復(fù)雜維修物流任務(wù)的組織和調(diào)度；李振汕等人針對(duì)系統(tǒng)處理大規(guī)模物流調(diào)度信息能力不足的情況，提出了一種基于云計(jì)算環(huán)境下的物流資源調(diào)度優(yōu)化模型對(duì)問題進(jìn)行求解；孫大為等從理論上對(duì)云資源調(diào)度模型進(jìn)行了系統(tǒng)的建模分析，提出了一種基于免疫克隆的偏好多維QoS的云資源調(diào)度優(yōu)化算法；張衛(wèi)等人結(jié)合云模型和蟻群算法對(duì)制造服務(wù)調(diào)度問題制定了一種求解策略，以實(shí)現(xiàn)制造服務(wù)資源的優(yōu)化配置。

遺傳算法（Genetic Algorithms，GA）是一種模擬自然進(jìn)化的仿真算法，它將問題表示成“染色體”的適者生存過程，通過“染色體”群的一代代不斷進(jìn)化，經(jīng)過復(fù)制、交叉和變異等操作，最終收斂到“最適應(yīng)環(huán)境”的個(gè)體，從而求得問題的最優(yōu)解或者近似最優(yōu)解。因?yàn)檫z傳算法直接以目標(biāo)函數(shù)作為搜索信息，不需要梯度等高等價(jià)值信息，并且采用自適應(yīng)隨機(jī)搜索技術(shù)，使用多個(gè)搜索點(diǎn)的搜索信息，因而它具有高度的靈活性、并行性和很強(qiáng)的通用性。本文基于物流云服務(wù)平臺(tái)強(qiáng)大的信息整合能力，采用遺傳算法對(duì)物流云服務(wù)平臺(tái)中的物流任務(wù)進(jìn)行調(diào)度優(yōu)化，最后進(jìn)行仿真實(shí)驗(yàn)，證明了遺傳算法對(duì)實(shí)現(xiàn)物流云服務(wù)平臺(tái)任務(wù)調(diào)度的有效性和可行性，實(shí)現(xiàn)了兼顧最大化資源利用率、最小化調(diào)度時(shí)間以及最低運(yùn)營成本三方面目標(biāo)的物流云服務(wù)平臺(tái)任務(wù)調(diào)度優(yōu)化。

1 物流云服務(wù)平臺(tái)概述

1.1 內(nèi)涵作用

物流云服務(wù)平臺(tái)（Cloud Service Platform,CSP）是面向各類物流企業(yè)、物流樞紐中心及各類綜合型企業(yè)的物流部門等的完整解決方案，依靠大規(guī)模的云計(jì)算處理能力、標(biāo)準(zhǔn)的作業(yè)流程、靈活的業(yè)務(wù)覆蓋、精確的環(huán)節(jié)控制、智能的決策支持及深入的信息共享來完成物流行業(yè)各個(gè)環(huán)節(jié)所需要的信息化要求。它是傳統(tǒng)物流信息服務(wù)平臺(tái)的完善與升級(jí)，為解決當(dāng)前物流資源共享困難、資源利用率不高、信息不對(duì)稱等問題提供了新的解決思路。

1.2 體系架構(gòu)

物流云服務(wù)模式主要由三個(gè)部分構(gòu)成，即：物流服務(wù)需求方（Logistics Cloud Service Demander,LCSD）即用戶層、物流服務(wù)提供方（Logistics Cloud Service Provider,LCSP）即資源層、云服務(wù)平臺(tái)（CSP）即云端服務(wù)層。CSP主要由個(gè)性化物流服務(wù)推薦中心、物流云調(diào)度中心和服務(wù)質(zhì)量監(jiān)控管理中心三個(gè)部分構(gòu)成，它是連接LCSD和CSP的橋梁和樞紐，負(fù)責(zé)建立完整的供需服務(wù)鏈。LCSD通過CSP發(fā)布自己的個(gè)性化物流需求，LCSP通過CSP發(fā)布自己已有的物流資源和服務(wù)，CSP通過對(duì)LCSD的物流需求進(jìn)行分析，然后對(duì)LCSP所提供的物流資源和服務(wù)進(jìn)行整合、檢索和匹配，建立起滿足LCSD個(gè)性化需求的物流服務(wù)解決方案并進(jìn)行相應(yīng)的資源調(diào)度。物流云服務(wù)平臺(tái)體系架構(gòu)如圖1所示。

圖1 物流云服務(wù)平臺(tái)體系架構(gòu)

1.3 任務(wù)調(diào)度

物流云服務(wù)平臺(tái)下的任務(wù)調(diào)度主要包括以下兩個(gè)方面：

（1）物流硬件資源調(diào)度。主要是為了解決當(dāng)企業(yè)拿到一批物流任務(wù)之后，應(yīng)當(dāng)如何調(diào)度現(xiàn)有的車輛、人工資源以及車輛的路徑優(yōu)化等問題；這個(gè)方面是傳統(tǒng)物流企業(yè)最為關(guān)心的問題，隨著物流行業(yè)的發(fā)展，此類問題的解決方案已經(jīng)較為成熟，故本文不再具體討論此類資源調(diào)度問題。

（2）物流管理服務(wù)資源調(diào)度。主要是解決當(dāng)物流云平臺(tái)面臨多批次的任務(wù)申請(qǐng)時(shí)，應(yīng)當(dāng)如何合理地分配云端的服務(wù)器、存儲(chǔ)資源以及任務(wù)實(shí)施者，以達(dá)到高效的平臺(tái)運(yùn)行效率和較低的運(yùn)營成本。這也是當(dāng)下物流云服務(wù)平臺(tái)最為關(guān)心的問題，也是本文的研究重點(diǎn)。

2 物流云服務(wù)平臺(tái)下的任務(wù)調(diào)度模型

2.1 問題描述

本文要解決的問題是同一類物流服務(wù)需求方（LCSD）向云服務(wù)平臺(tái)（CSP）提出物流需求，CSP對(duì)提交上來的物流任務(wù)進(jìn)行批處理，然后整合物流云服務(wù)提供方（LCSP）已有的物流資源和服務(wù)，將物流任務(wù)和物流資源和服務(wù)進(jìn)行檢索匹配，并進(jìn)行相應(yīng)的物流云調(diào)度。為了提高云平臺(tái)的服務(wù)質(zhì)量，本文建立了一個(gè)兼顧資源利用率、調(diào)度時(shí)間與運(yùn)營成本的多目標(biāo)優(yōu)化模型，來指導(dǎo)物流云服務(wù)平臺(tái)下的物流任務(wù)調(diào)度分配。

2.2 假設(shè)條件

由于物流云服務(wù)環(huán)境下的任務(wù)調(diào)度非常復(fù)雜，包含了各種不確定因素，因此，為使物流云服務(wù)平臺(tái)下的任務(wù)調(diào)度模型化，需假設(shè)以下前提條件：

（1）LCSD的性質(zhì)相同或相近，需要接受服務(wù)的時(shí)間差別較??；

（2）各個(gè)LCSD都是互相獨(dú)立的，且互不干擾；

（3）LCSD的數(shù)量遠(yuǎn)遠(yuǎn)大于LCSP的數(shù)量；

（4）CSP對(duì)批量物流任務(wù)的處理具有順序性，本批任務(wù)完成以后才可以進(jìn)行下一批物流任務(wù)的分配和調(diào)度；

（5）每個(gè)LCSP工作能力相同，即對(duì)于同一個(gè)物流任務(wù)的完成時(shí)間相同；

（6）不考慮LCSP具體如何處理任務(wù)，當(dāng)一個(gè)任務(wù)分配給某個(gè)LCSP，本模型只關(guān)心其完成該任務(wù)的時(shí)長，不考慮LCSP如何調(diào)配人員和車輛等具體問題；

（7）物流云服務(wù)任務(wù)調(diào)度成本僅考慮物流云服務(wù)平臺(tái)的運(yùn)營成本。

2.3 模型建立

基于以上前提，可以對(duì)物流云服務(wù)平臺(tái)下的任務(wù)調(diào)度做出如下描述：用Q表示LCSD的數(shù)量，P表示LCSP的數(shù)量，調(diào)度工作是將Q個(gè)需求通過CSP分配給P個(gè)LCSP完成。設(shè)第i個(gè)LCSP分配到Ki個(gè)任務(wù)，Ci為每次使用云平臺(tái)的開銷（包括帶寬、存儲(chǔ)容量等費(fèi)用），Bi為每個(gè)LCSP單位時(shí)間內(nèi)最大任務(wù)承載量，Ki/Bi則為每個(gè)LCSP的使用率，本文將其定義為該LCSP的資源利用率，這樣，物流云服務(wù)平臺(tái)下的任務(wù)調(diào)度的多目標(biāo)優(yōu)化模型表示如下：

其需要滿足以下約束條件：

其中：tij為第j個(gè)任務(wù)使用第i個(gè)資源的時(shí)間；Ti為第i個(gè)LCSP完成所分配到的任務(wù)所需要的時(shí)間；）表示完成該批任務(wù)所需要的時(shí)間；表示完成該批任務(wù)LCSP的平均資源使用率；表示完成該批任務(wù)的成本。本模型是一個(gè)多目標(biāo)的優(yōu)化問題，其優(yōu)化目標(biāo)綜合考慮了調(diào)度時(shí)間，資源利用率以及調(diào)度成本，即使得完成任務(wù)的所用的時(shí)間最少，資源利用率最高，同時(shí)相應(yīng)的調(diào)度運(yùn)營成本最低。

2.4 模型分析

本模型是一個(gè)多目標(biāo)整數(shù)規(guī)劃問題，為了簡化求解，引入偏好向量λ=（x,y,）z將問題轉(zhuǎn)化成單目標(biāo)整數(shù)規(guī)劃問題：

這樣，只要定義好偏好向量λ=（x,y,）z，問題便可以通過遺傳算法等啟發(fā)式算法進(jìn)行求解了。

3 物流云服務(wù)平臺(tái)下的任務(wù)調(diào)度遺傳算法設(shè)計(jì)

3.1 編碼與種群初始化

編碼機(jī)制是遺傳算法的必要步驟，對(duì)于應(yīng)用于不同問題的編碼，目前還沒有統(tǒng)一的方法。DeJong提出了兩條操作性強(qiáng)的實(shí)用編碼原則：（1）有意義的積木塊編碼原則：應(yīng)使用能夠易于產(chǎn)生與所求問題相關(guān)的且具有低階、短定義長度模式的編碼方案；（2）最小字符串編碼原則：應(yīng)使用能使問題得到自然表示或者描述的具有最小編碼字符集的編碼方案。

常用的編碼方案有二進(jìn)制編碼、Gray編碼等。從本質(zhì)上看Gray編碼是二進(jìn)制編碼的一種轉(zhuǎn)換，本文采取Gray編碼的方式來對(duì)上文中提出模型中的自變量進(jìn)行編碼。Gray碼是依靠二進(jìn)制碼進(jìn)行轉(zhuǎn)換的，轉(zhuǎn)換規(guī)則如下：

（1）對(duì)n位二進(jìn)制的碼字，從右到左，以0到n-1編號(hào)；

（2）如果二進(jìn)制碼字的第i位和i+1位相同，則對(duì)應(yīng)的格雷碼的第i位為0，否則為1（當(dāng)i+1=n時(shí)，二進(jìn)制碼字的第n位被認(rèn)為是0，即第n-1位不變）。

3.2 適應(yīng)度函數(shù)與選擇

在遺傳算法中，適應(yīng)度函數(shù)即為本文的目標(biāo)函數(shù)，且具有非負(fù)性，任何情況下都大于等于0，其值越大越好。

物流云服務(wù)平臺(tái)面向不同的企業(yè)和用戶，不同的物流服務(wù)需求者對(duì)于目標(biāo)函數(shù)的追求也存在較大差異，比如：快消或季節(jié)性產(chǎn)品（例如時(shí)裝），物流速度也就是物流任務(wù)的完成時(shí)間是其核心指標(biāo)，則相對(duì)的偏好向量λ=（x,y,）z中的y值就會(huì)大一些。企業(yè)用戶可以根據(jù)自身的物流需求定位以及訂單的特性，參考物流云服務(wù)平臺(tái)的相關(guān)調(diào)度參數(shù)的歷史數(shù)據(jù)，進(jìn)行偏好向量的設(shè)置。

問題模型所涉及的目標(biāo)函數(shù)包含三個(gè)部分：資源利用率、調(diào)度時(shí)間以及運(yùn)營成本?？紤]到本文給定的物流云服務(wù)模式下資源服務(wù)的分布性，在建模過程中考慮了物流云的相關(guān)信息。通過對(duì)服務(wù)選擇鏈進(jìn)行解碼，就可以得到服務(wù)質(zhì)量參數(shù)和服務(wù)的執(zhí)行成本。而物流成本和交貨期，需要結(jié)合兩條鏈進(jìn)行解碼。本文選用主動(dòng)調(diào)度的解碼方式來實(shí)現(xiàn)編碼串到參數(shù)的映射，根據(jù)子任務(wù)順序鏈中各子任務(wù)的排列順序，結(jié)合服務(wù)選擇鏈，確定每個(gè)子任務(wù)所選服務(wù)的執(zhí)行開始和結(jié)束時(shí)間，通過該子任務(wù)所選的服務(wù)，所屬企業(yè)以及子任務(wù)的所屬企業(yè)等相關(guān)信息，確定物流時(shí)間和物流成本。

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

4.1 實(shí)驗(yàn)仿真

為了驗(yàn)證本文提出的基于遺傳算法的物流云任務(wù)調(diào)度模型的合理性和算法的有效性，進(jìn)行了仿真實(shí)驗(yàn)。其中為了仿真的可實(shí)施性，本文對(duì)模型進(jìn)行了簡化，將復(fù)雜的多目標(biāo)優(yōu)化問題通過偏好向量轉(zhuǎn)化成單一目標(biāo)的優(yōu)化問題。遺傳算法的適應(yīng)度函數(shù)值（Fitness）即為上一章所闡述的目標(biāo)函數(shù)。利用MATLAB上謝菲爾德大學(xué)開發(fā)的遺傳算法工具箱以及Python上的遺傳算法開源算法對(duì)本文提出的模型進(jìn)行仿真。

本文算例是根據(jù)參考文獻(xiàn)[11]給出的問題修改而得。假設(shè)現(xiàn)有10個(gè)LCSP，其服務(wù)申請(qǐng)的響應(yīng)時(shí)間如表1所示。

表1 LCSP服務(wù)申請(qǐng)響應(yīng)時(shí)間 單位：m

與此同時(shí)，有100個(gè)LCSD，其業(yè)務(wù)完成時(shí)間如表2所示。

表2 LCSD業(yè)務(wù)完成時(shí)間 單位：m

每個(gè)服務(wù)器的使用成本如表3所示：

4.2 仿真結(jié)果

表3 每臺(tái)服務(wù)器的使用成本 單位：元

設(shè)置每個(gè)LSCP每天最大提供服務(wù)時(shí)間為12小時(shí)。通過MATLAB仿真得到最優(yōu)調(diào)度方案如表4、圖2至圖4所示：

表4

圖2 目標(biāo)函數(shù)值變化曲線

圖3 調(diào)度成本變化曲線

圖4 適應(yīng)度函數(shù)變化趨勢圖

4.3 結(jié)果分析

從上一節(jié)中可以看出，利用文中所闡述的遺傳算法，經(jīng)過100代迭代計(jì)算，適應(yīng)度函數(shù)可以收斂。算法完成了將100個(gè)LCSD任務(wù)分配給10個(gè)LCSP的任務(wù)，并且當(dāng)偏好向量λ=（0.4,0.4,0.2）的情況下，其中的一個(gè)最優(yōu)解為176.3，在此情況下服務(wù)成本為80.0元，服務(wù)所需時(shí)間為507.3分鐘。

5 結(jié)束語

本文綜合考慮資源利用率、任務(wù)調(diào)度時(shí)間以及調(diào)度運(yùn)營成本三方面指標(biāo)，與以往研究相比考慮更加全面，建立的物流云服務(wù)平臺(tái)下的任務(wù)調(diào)度模型通過遺傳算法求解并通過仿真驗(yàn)證，仿真結(jié)果顯示，目標(biāo)函數(shù)值隨著迭代次數(shù)的增多逐漸呈現(xiàn)上升趨勢，適應(yīng)度函數(shù)逐漸減小，調(diào)度成本也逐漸減小，證明了本研究的實(shí)際有效性，為物流云服務(wù)模式下的任務(wù)調(diào)度問題提供了新的解決思路。

但本文的研究還有需要改進(jìn)的地方，比如本文考慮的物流云服務(wù)平臺(tái)的調(diào)度運(yùn)營成本，并未考慮物流云服務(wù)提供商的服務(wù)成本以及物流云服務(wù)需求者的消費(fèi)成本，這一點(diǎn)對(duì)于提高綜合服務(wù)質(zhì)量缺乏一定的說服力，需要在以后的研究中得到解決，從而為物流云服務(wù)模式的發(fā)展和推廣提供更有效的解決方案和理論技術(shù)支持。

參考文獻(xiàn)：

[1]陳典斌.物流云服務(wù)——供應(yīng)鏈下的物流服務(wù)新模式探析[J].農(nóng)村經(jīng)濟(jì)與科技，2017,28(14):65-66.

[2]占天異，丁一，姚錦元,等.物流云服務(wù)下動(dòng)態(tài)設(shè)施選址問題研究[J].河北工業(yè)科技，2014(3):193-198.

[3]許波，趙超，祝衍軍,等.云計(jì)算中虛擬機(jī)資源調(diào)度多目標(biāo)優(yōu)化[J].系統(tǒng)仿真學(xué)報(bào)，2014(3):592-595,620.

[4]邰英英.物流云服務(wù)的物流服務(wù)新模式[J].科技經(jīng)濟(jì)市場，2016(11):176-177.

[5]梁紅波.云物流和大數(shù)據(jù)對(duì)物流模式的變革[J].中國流通經(jīng)濟(jì)，2014(5):41-45.

[6]姜妍旭.基于雙邊資源整合的云物流服務(wù)平臺(tái)研究與開發(fā)[D].哈爾濱：哈爾濱工業(yè)大學(xué)（碩士學(xué)位論文），2015.

[7]林云，田帥輝.物流云服務(wù)——面向供應(yīng)鏈的物流服務(wù)新模式[J].計(jì)算機(jī)應(yīng)用研究，2012(1):224-228.

[8]崔濤.基于云服務(wù)優(yōu)選的最節(jié)能物流運(yùn)輸調(diào)度系統(tǒng)的設(shè)計(jì)[J].現(xiàn)代電子技術(shù)，2016,39(20):138-141,145.

[9]張曉磊，馬從安，申晨.物流云服務(wù)下基于改進(jìn)蝙蝠算法的任務(wù)調(diào)度[J].計(jì)算機(jī)應(yīng)用研究，2015(6):1676-1679,1697.

[10]李振汕.云計(jì)算環(huán)境下的物流資源調(diào)度算法研究[J].物流技術(shù)，2013(9):339-341,386.

[11]梁慶中.混合云平臺(tái)上多目標(biāo)任務(wù)調(diào)度算法研究[D].北京：中國地質(zhì)大學(xué)（博士學(xué)位論文），2015.

[12]熊永華，王靜，吳敏,等.面向多目標(biāo)優(yōu)化的云制造虛擬資源調(diào)度方法[J].計(jì)算機(jī)集成制造系統(tǒng)，2015(11):3079-3087.

[13]Mengke Yang,Movahedipour Mahmood,Xiaoguang Zhou,et al.Design and Implementation of Cloud Platform for Intelligent Logistics in the Trend of Intellectualization[J].中國通信，2017,14(10):180-191.