云計(jì)算下物流配送調(diào)度的算法研究

包瓊雪

（溫州職業(yè)技術(shù)學(xué)院，浙江 溫州 325035）

云計(jì)算下物流配送調(diào)度的算法研究

包瓊雪

（溫州職業(yè)技術(shù)學(xué)院，浙江 溫州 325035）

在分析影響資源調(diào)度因素的基礎(chǔ)上，建立了云計(jì)算環(huán)境下的物流資源調(diào)度模型，在云計(jì)算框架下完成訂單信息和物流配送車(chē)輛的信息處理，從而得出最合理的物流配送方案。針對(duì)物流配送中的車(chē)輛調(diào)配問(wèn)題，建立了配送路徑算法模型和最小配送成本算法模型，為物流配送方案提供最佳的策略。通過(guò)仿真實(shí)驗(yàn)表明，該算法具備可行性和優(yōu)越性。

云計(jì)算；物流配送；優(yōu)化算法；資源調(diào)度

一、引言

目前物流企業(yè)的貨物配送以及訂單的分類處理都是通過(guò)相關(guān)人員的隨意的分配。該方式簡(jiǎn)單易行，然而隨著物流業(yè)的極速的發(fā)展，大量訂單的增加使得該種方式效率變得十分低下。云技術(shù)是一種虛擬化的技術(shù)，用該技術(shù)可以實(shí)現(xiàn)優(yōu)勢(shì)資源的共享，利用優(yōu)勢(shì)的資源就可以較好的完成物流業(yè)資源分配以及調(diào)度的問(wèn)題。物流企業(yè)中的物流配送以及業(yè)務(wù)調(diào)度算法運(yùn)算過(guò)程中不僅要顧及到及時(shí)響應(yīng)的問(wèn)題，還要對(duì)該算法實(shí)現(xiàn)的成本進(jìn)行估計(jì)，如果成本耗費(fèi)過(guò)高或者對(duì)于客戶的響應(yīng)不及時(shí)該方式都是沒(méi)有意義的。在研究的過(guò)程中采取了多約束條件以及遺傳學(xué)算法方面的知識(shí)來(lái)解決這些實(shí)際的問(wèn)題[1]。

二、物流資源調(diào)度

（一）影響物流調(diào)度的因素

物流企業(yè)的配送是分段式的,配送過(guò)程中有很多不同配送單位協(xié)同來(lái)完成貨物的配送，一般來(lái)說(shuō),物流企業(yè)接到訂單之后會(huì)對(duì)訂單進(jìn)行簡(jiǎn)單分割，然后由配送車(chē)輛將訂單中的物品按照事先設(shè)定好的路線對(duì)貨物進(jìn)行配送。這個(gè)過(guò)程也就是物流配送的過(guò)程占據(jù)物流業(yè)成本的絕大部分。如何對(duì)訂單進(jìn)行合理的分割，確定配送車(chē)輛的數(shù)量以及配送路線的指定都直接影響了物流配送成本。具體來(lái)講影響物流企業(yè)配送成本的主要方面有車(chē)輛數(shù)量的確定，配送人員的分配，訂單的分割，配送路線的合理規(guī)劃，對(duì)于客戶需求響應(yīng)的時(shí)間等。物流業(yè)的物流配送首先應(yīng)該優(yōu)先考慮的是企業(yè)的大訂單，然后采集零散的較小的訂單[2]。接著劃分責(zé)任配送區(qū)域，確定相應(yīng)的配送時(shí)間，在配送的過(guò)程中同時(shí)要考慮到物流配送的遠(yuǎn)近以及車(chē)輛路線安排的事宜針對(duì)配送距離比較遠(yuǎn)的訂單可以采取專門(mén)的車(chē)輛配送。

圖1 配送路線以及配送方案示意圖

圖1為配送路線方案示意圖，圖中1-6為配送的地點(diǎn)，中間為配送中心。將1-3點(diǎn)劃分為一個(gè)配送區(qū)域，將4-6點(diǎn)作為另一個(gè)配送區(qū)域。根據(jù)兩個(gè)區(qū)域的訂單情況分別設(shè)定一定數(shù)量的車(chē)輛，然后對(duì)每次配送的時(shí)間進(jìn)行規(guī)定以滿足客戶對(duì)于配送時(shí)間的需求。

（二）云計(jì)算下的物流調(diào)度

由于云計(jì)算具有海量數(shù)據(jù)處理的能力，響應(yīng)速度比較快，價(jià)格低廉而被很多的行業(yè)所廣泛的使用。由于物流業(yè)中物流配送的過(guò)程涉及到的車(chē)輛數(shù)量問(wèn)題，配送時(shí)間問(wèn)題，配送路線問(wèn)題都要涉及比較復(fù)雜的算法，復(fù)雜的算法就對(duì)計(jì)算機(jī)的硬件及運(yùn)算方式提出了更高要求。傳統(tǒng)的計(jì)算方式由于時(shí)間響應(yīng)慢，往往達(dá)不到物流企業(yè)對(duì)于實(shí)時(shí)性的要求，采取云計(jì)算的方式來(lái)對(duì)物流配送的過(guò)程中海量的數(shù)據(jù)進(jìn)行處理，然后得到物流配送實(shí)時(shí)性的最小成本同時(shí)又滿足客戶需求的配送方式[3]。

圖2 云計(jì)算方式下模型的計(jì)算方式

三、改進(jìn)遺傳算法下的配送車(chē)輛調(diào)度

（一）問(wèn)題提出

一般的物流企業(yè)來(lái)講物流配送的環(huán)節(jié)可以簡(jiǎn)單的劃分為：客戶下單，物品分配，配送過(guò)程，物品簽收，交易完成。影響配送主要成本的還是車(chē)輛數(shù)據(jù)的確定以及配送路線的確定，如果二者設(shè)置合理則能夠在最小成本下來(lái)滿足客戶的需求[4]。由于在配送的過(guò)程中需要滿足客戶以及最小成本的原則，所以該模型要滿足以下的幾條規(guī)則。

（1）路線劃分完成之后，車(chē)輛的行走必須要嚴(yán)格按照該路線進(jìn)行行駛，不得更改。

（2）路徑的分支是由多個(gè)配送節(jié)點(diǎn)之間的相互連接組成的。

（3）規(guī)劃路徑時(shí)，不同的路徑不能夠出現(xiàn)重復(fù)的節(jié)點(diǎn)。

（4）分支路徑的選取要滿足上述約束條件。

（5）配送車(chē)輛不能出現(xiàn)超載，如果一次配送不能夠完全配送完畢，可以考慮多次或多個(gè)車(chē)輛，但是要在滿足客戶的基本時(shí)間響應(yīng)需求下，以最小的成本來(lái)實(shí)現(xiàn)該配送。

（6）每條配送路線都有一個(gè)規(guī)定的時(shí)間閾值，一般來(lái)講配送的時(shí)間應(yīng)該小于該閾值以滿足客戶對(duì)于配送時(shí)間的要求。

（二）車(chē)輛調(diào)度模型

車(chē)輛調(diào)度模型的建立要遵循上述約定的條件，本文中假設(shè)配送點(diǎn)的個(gè)數(shù)為N個(gè)，可以承接配送任務(wù)的車(chē)輛的數(shù)目為M。d（x，y）為點(diǎn)x與點(diǎn)y之間的距離一般來(lái)說(shuō)就是配送距離，R（x）為配送到某個(gè)地點(diǎn)x所有的配送物品的數(shù)量，Q為配送車(chē)輛的最大的載重。D為配送車(chē)輛行駛的距離。配送路徑的選擇以滿足盡量多的訂單為原則，但是配送路徑的選擇應(yīng)該在車(chē)輛能夠行駛的最大的距離限度之內(nèi)。則配送方案模型如公式（1）所示。

公式1的含義為采取某種配送方案下物流配送總的路徑的長(zhǎng)度，也就是第一個(gè)配送點(diǎn)x0與第二個(gè)配送點(diǎn)x1之間的距離加上第二個(gè)配送點(diǎn) x1與第三個(gè)配送點(diǎn)x2之間的距離……加上 xN+M-2與xN+M-1之間的距離最后再加上最后一個(gè)點(diǎn)到第一個(gè)出發(fā)點(diǎn)之間的距離就得到了公式1也就是采取某種配送方案時(shí)配送車(chē)輛所走過(guò)的總的路徑。通過(guò)約束條件，建立目標(biāo)函數(shù)為滿足該約束的成本最低的模型：

在公式2中cij為運(yùn)輸車(chē)輛從需求點(diǎn)i運(yùn)輸?shù)叫枨簏c(diǎn)j所需要的運(yùn)輸成本，yijK為運(yùn)輸車(chē)輛K是否會(huì)由i點(diǎn)到達(dá)j點(diǎn)，如果運(yùn)輸車(chē)輛會(huì)經(jīng)過(guò)i到j(luò)點(diǎn)之間的路徑那么該值就為1否則該值就為0，Pi為在節(jié)點(diǎn)i處停留單位時(shí)間的成本消耗，Ti為車(chē)輛在節(jié)點(diǎn)i停留的時(shí)間。令F為配送這些點(diǎn)所需的最小的成本。上式就是配送成本最小化模型。根據(jù)可支配車(chē)輛的出發(fā)滿足下列條件：

根據(jù)載重量的最大載重量的約束要求要滿足下列條件：

在公式4中，k為運(yùn)輸車(chē)輛，當(dāng)車(chē)輛k經(jīng)過(guò)節(jié)點(diǎn)i時(shí)xik的值為1，當(dāng)車(chē)輛k不經(jīng)過(guò)節(jié)點(diǎn)i時(shí)，xik值為0，Qi為應(yīng)該為節(jié)點(diǎn)i所應(yīng)該配送貨物的重量，公式4的含義就是運(yùn)輸車(chē)輛k為所有其配送節(jié)點(diǎn)配送貨物的總重量不應(yīng)該超過(guò)車(chē)輛k的最大的載重Qk。配送車(chē)輛k在配送節(jié)點(diǎn)i與配送節(jié)點(diǎn)j之間的配送節(jié)點(diǎn)關(guān)系滿足下列式子：

在公式5與公式6中描述的意義為假設(shè)運(yùn)輸車(chē)輛k經(jīng)過(guò)i點(diǎn)到達(dá)j，那么車(chē)輛k一定既經(jīng)過(guò)又經(jīng)過(guò)節(jié)點(diǎn)i又經(jīng)過(guò)節(jié)點(diǎn)j。根據(jù)配送模型對(duì)于配送時(shí)間的約束條件，要滿足下列式子：

公式8的含義為到達(dá)節(jié)點(diǎn)j所花費(fèi)的時(shí)間與在節(jié)點(diǎn)i停留的時(shí)間之和再加上運(yùn)輸車(chē)輛由節(jié)點(diǎn)i到節(jié)點(diǎn)j所花費(fèi)的時(shí)間減去M，如果運(yùn)輸車(chē)輛經(jīng)過(guò)i到達(dá)j那么取值為0否則取值為M，最后要小于或者等于到達(dá)j點(diǎn)所花費(fèi)的時(shí)間。在上述模型中物流配送可支配的車(chē)輛的集合為（K={1，2，…，m}）。配送過(guò)程中節(jié)點(diǎn)的集合為（G={1，2，…，n}）。配送中心表示為{0}。Gk為車(chē)輛k所配送的所有節(jié)點(diǎn)的集合。Ti為貨物配送到相應(yīng)的地點(diǎn)i所耗費(fèi)的時(shí)間。Cij為物流配送到節(jié)點(diǎn)i所耗費(fèi)的成本。Tij為從節(jié)點(diǎn)i配送到節(jié)點(diǎn)j所耗費(fèi)的時(shí)間。Qi為節(jié)點(diǎn)i的配送貨物的總量。Qk為配送車(chē)輛最大的貨運(yùn)量。Si為在節(jié)點(diǎn)i所裝卸貨物所耗費(fèi)的時(shí)間。為配送車(chē)輛出發(fā)的時(shí)刻。為系統(tǒng)要求的最長(zhǎng)配送時(shí)間。Xik為物流配送車(chē)輛的劃分。如果配送車(chē)輛經(jīng)過(guò)節(jié)點(diǎn)i那么該值為1否則該值為0。Yijk為配送路線規(guī)劃，如果車(chē)輛經(jīng)由i到j(luò)那么該值為1否則為0。

（三）模型算法分析

建立車(chē)輛調(diào)度模型的目的就是為了以最小的成本F來(lái)得到相應(yīng)的配送方案以及確定配送路線。如果沒(méi)有上述約束規(guī)定那么存在（Pn1+Pn2+…+Pnn）中配送的方式。相應(yīng)的計(jì)算量為（Pn1+Pn2+…+Pnn）m。如果加上上述條件，可支配車(chē)輛要滿足 ΣQi·xik≤Qk極大值為 IK，符合 Tj+Si+Tij-M（1-yijk）≤Tj極大值節(jié)點(diǎn)為Jk，符合T0k+ΣΣyijk（Tij+Si）極大值節(jié)點(diǎn)為 Hk，令 Lk=min（Ik，Jk，Hk），那么車(chē)輛K的配送選擇有ΣPLku種，相應(yīng)的信息處理量為mk=1（Lku=1ΣPLku），從上述方案可以推出隨著N與M的變大，計(jì)算量也會(huì)隨著極速變大。

（四）云計(jì)算環(huán)境下的算法流程

首先通過(guò)模型得出物流配送的車(chē)輛調(diào)度信息之后就要確定配送調(diào)度的優(yōu)先級(jí)次序，并在云計(jì)算方式下完成相應(yīng)配送方案以及配送路線的確定，其算法實(shí)現(xiàn)的流程如圖3所示。

圖3 云計(jì)算方式算法流程圖

四、仿真實(shí)驗(yàn)

仿真試驗(yàn)中采用CloudSim軟件來(lái)計(jì)算得到物流配送的方案，設(shè)定相應(yīng)的仿真情景，相應(yīng)的配送業(yè)務(wù)與車(chē)輛以及配送地點(diǎn)信息來(lái)對(duì)該算法進(jìn)行評(píng)估。假設(shè)可支配車(chē)輛為24，工作人員數(shù)量為48，配送車(chē)輛最大載貨數(shù)量為110，配送時(shí)間為每個(gè)工作日8小時(shí)，單件物品的每小時(shí)成本為0.6元，一共有5個(gè)配送中心，每個(gè)配送中心到配送節(jié)點(diǎn)之間的成本可以認(rèn)為是和兩點(diǎn)之間的距離成正比，采用不同的運(yùn)輸方案的時(shí)候可以確定車(chē)輛是否會(huì)經(jīng)歷兩個(gè)點(diǎn)之間的路徑，在某個(gè)點(diǎn)停留的單位時(shí)間成本為5，在每個(gè)點(diǎn)停留的時(shí)間假設(shè)都為5min。仿真的模型為多點(diǎn)的配送模型也就是在某個(gè)城市中有多個(gè)配送的中心，每個(gè)客戶端都可能是通過(guò)不同的配送中心來(lái)送貨的，配送中心的位置、數(shù)量以及配送點(diǎn)的位置和數(shù)量分布如圖4所示：

圖4 多配送中心實(shí)際仿真問(wèn)題

通過(guò)對(duì)不同配送方式的計(jì)算可以得到表2結(jié)果。通過(guò)公式2可以計(jì)算每種配送方式下物流成本，在本仿真實(shí)驗(yàn)中一共有48個(gè)配送點(diǎn)，每個(gè)配送點(diǎn)可以有5種配送的選擇方式，一共有5的48次方種配送方式，通過(guò)計(jì)算這些配送方式的最小的成本就可以得到如表1所示的配送結(jié)果。表1中的結(jié)果是通過(guò)人工的計(jì)算得到的。

表1 人工計(jì)算方式配送成本與配送時(shí)間

表2為所采取云計(jì)算方式下，計(jì)算配送方案與配送模型所花費(fèi)時(shí)間，仿真驗(yàn)證結(jié)果如下：

表2 云計(jì)算方式下配送成本與配送時(shí)間

衡量配送調(diào)度算法的本文所基于的一個(gè)很重要的標(biāo)準(zhǔn)就是公式2中所描述的成本指標(biāo)，通過(guò)云計(jì)算方式下和人工配送調(diào)度方式下配送成本之間的對(duì)比，在訂單數(shù)分別為 190，200，210，220，230，240，250，260的時(shí)候配送的成本原來(lái)為9 502，9 703，…，11 824；而采用云計(jì)算方式下物流配送方案配送的成本為8 231，8 403，…，9 206；也就是云計(jì)算方式下配送的成本都降低了。通過(guò)將人工求取的計(jì)算結(jié)果的時(shí)間與云計(jì)算方式下的計(jì)算的時(shí)間進(jìn)行對(duì)比分析可以發(fā)現(xiàn)云計(jì)算模式下的配送調(diào)度算法的實(shí)現(xiàn)的時(shí)間要比人工快速的多，也相對(duì)精確的多。通過(guò)云計(jì)算技術(shù)的運(yùn)用，能夠大大縮短配送方案確定的時(shí)間提高配送的效率。

五、結(jié)語(yǔ)

通過(guò)將云計(jì)算技術(shù)應(yīng)用于物流配送過(guò)程中物流配送方案的確定以及配送路線確定，在模型的建立過(guò)程中通過(guò)問(wèn)題的分解提高的模型的現(xiàn)實(shí)意義也加快了模型的運(yùn)算的速度。通過(guò)相應(yīng)的實(shí)驗(yàn)驗(yàn)證云計(jì)算模式下的計(jì)算相應(yīng)的配送方案與路線大大減少了相應(yīng)的求解的時(shí)間提高了求解的效率，為物流配送方案的實(shí)時(shí)性確定提供了理論與現(xiàn)實(shí)的可行性。

[1]鈕亮，張寶友，2015.基于云計(jì)算求解城市物流配送最短路徑研究[J].科技通報(bào)（5）：184-188，213.

[2]豐佳棟，2015.云計(jì)算視角下的第三方物流服務(wù)質(zhì)量創(chuàng)新模型[J].中國(guó)流通經(jīng)濟(jì)（2）：33-38.

[3]劉章逵，2016.云計(jì)算在海上運(yùn)輸物流電子管理系統(tǒng)中的應(yīng)用[J].艦船科學(xué)技術(shù)（18）：103-105.

[4]李翔，葉歐，張鵬偉，2016.基于云計(jì)算的印刷企業(yè)供應(yīng)物流信息系統(tǒng)[J].包裝工程（21）：211-216.

（責(zé)任編輯：C 校對(duì)：T）

F062.3；F252.5

A

1004-2768（2017）04-0114-04

2017-01-17

包瓊雪（1976-），女，浙江溫州人，經(jīng)濟(jì)師，溫州職業(yè)技術(shù)學(xué)院工商管理系講師，研究方向：企業(yè)管理、物流管理。