遠距離物流配送調(diào)度指在物流配送中心給定配送任務(wù)的情況下，如何派車、組織運輸可以確保配送路程最短且運輸成本最低[1,2]?，F(xiàn)階段，我國大部分的物流企業(yè)在資源運輸過程中存在分配不均勻和配送線路安排不合理等問題，導(dǎo)致運力資源嚴重浪費，而缺乏完整的遠距離物流配送調(diào)度方案是造成上述現(xiàn)象出現(xiàn)的重要因素，所以研究遠距離物流配送調(diào)度具有十分重要的研究意義。

 

基于上述背景，為了減少成本、提高效率，國內(nèi)相關(guān)專家針對遠距離物流配送調(diào)度方面的問題展開了大量研究，例如：杜子超等人[3]構(gòu)建眾包配送車輛調(diào)度模型，引入蟻群—量子粒子群混合優(yōu)化算法對模型求解，確定車輛調(diào)度方案；黃逸文等人[4]分析物流系統(tǒng)的運行特性，構(gòu)建物流協(xié)同調(diào)度模型，對模型協(xié)同優(yōu)化處理，進而獲取最佳調(diào)度方案；曹志鵬等人[5]提出一種全新的動態(tài)調(diào)度方法，通過局部搜索算法確定最終車輛動態(tài)調(diào)度方案。

 

在以上幾種研究算法的基礎(chǔ)上，提出了一種響應(yīng)用戶隨機需求的遠距離物流配送調(diào)度算法。仿真分析表明，所提算法可以大幅度提升用戶滿意度以及調(diào)度效率，更好地解決遠距離物流配送調(diào)度問題。

 

2 算法

2.1 構(gòu)建遠距離物流配送調(diào)度模型

由于在實際物流配送過程中，受到訂單量的波動、用戶臨時需求的變化等影響，用戶的需求往往是隨機而變的[6,7]。為了更真實地模擬現(xiàn)實物流運輸環(huán)境，需要考慮響應(yīng)用戶隨機需求，設(shè)置真實用戶與虛擬用戶，以此構(gòu)建遠距離物流配送調(diào)度模型，從而制定調(diào)度方案，優(yōu)化配送調(diào)度。

 

通常物流配送系統(tǒng)包含一個配送中心和多個用戶，主要通過專業(yè)的物流配送車輛進行服務(wù)。將遠距離起始時間設(shè)定為t0,配送結(jié)束時間為t1。在t0時刻之前出現(xiàn)的用戶被稱為真實用戶，為了降低配送成本并更好地服務(wù)于在t0時間后隨機出現(xiàn)的用戶，中間某個時間段設(shè)定為tn。根據(jù)用戶以往的需求信息，預(yù)測在(t0,tn)時間段內(nèi)配送區(qū)域內(nèi)可能出現(xiàn)需求的用戶，并將這些用戶稱為虛擬用戶。結(jié)合虛擬用戶和真實用戶，制定遠距離物流配送調(diào)度方案。假設(shè)沒有出現(xiàn)虛擬客戶需求，則繼續(xù)按照原始配送方案配送；反之，則需要將車輛朝著下一個虛擬需求用戶出現(xiàn)的方向行駛，如果后續(xù)并沒有虛擬用戶出現(xiàn)，則直接返回至物流配送中心。對于在tn之后出現(xiàn)的客戶需求，由于無法及時滿足用戶的配送時間需求，所以可以將其作為設(shè)定為下一配送計劃的真實用戶需求。

 

在實際遠距離物流配送調(diào)度過程中，考慮響應(yīng)用戶隨機需求的情況下，需要作出以下假設(shè)：

 

1)物流配送車輛的數(shù)量有限。

 

2)物流配送車輛的容量和承載能力是完全相同的。

 

3)車輛從配送中心出發(fā)，完成物流配送服務(wù)后直接返回至配送中心。

 

4)每個用戶只可以由1輛車展開遠距離物流配送服務(wù)。

 

5)在(t0,tn)期間隨機出現(xiàn)需求的用戶可以利用匯集以及預(yù)測獲取。

 

6)不同用戶的需求發(fā)生是相互獨立的。

 

通過上述分析，由于需要全面考慮用戶分布情況，可以將設(shè)定的物流配送區(qū)域劃分為多個柵格，每個柵格代表用戶區(qū)域，根據(jù)配送區(qū)域人口密度大小確定柵格單元規(guī)模，其中在一個柵格內(nèi)的用戶即為同一個配送區(qū)域。遠距離物流配送區(qū)域柵格圖和集群示意圖如圖1所示。除了歷史沒有出現(xiàn)用戶的柵格和物流配送服務(wù)開始前期已經(jīng)出現(xiàn)的真實用戶所在柵格，剩余的柵格ai可能隨機出現(xiàn)的用戶需求。

 

圖1 遠距離物流配送柵格圖和集群示意圖   下載原圖

 

為了解不同時間段的需求強度和波動性，計算歷史時間段內(nèi)的用戶需求概率，確定合適的車輛調(diào)度策略。統(tǒng)計檢驗各個柵格ai在設(shè)定單位時間出現(xiàn)用戶需求的概率β(zs),則集群c在歷史時間段內(nèi)的用戶需求概率β(zc)可以表示為式(1)的形式：

 

 

式中，n表示單位時間內(nèi)出現(xiàn)用戶需求的次數(shù)。如果β(zc)的取值大于等于給定的經(jīng)驗概率數(shù)值C(minβ),則代表集群中存在隨機需求的虛擬用戶；反之，不存在虛擬用戶。對剩下的全部柵格遍歷處理，刪除無法形成虛擬用戶的柵格和集群。

 

為確保每個柵格只屬于一個集群，需要將柵格群內(nèi)重疊的集群刪除，根據(jù)β(zc)計算結(jié)果，獲取虛擬用戶，全部虛擬用戶的集合為：

 

Btemp={c|β(zc)≥C(minβ)|∪c|β(zc)≥C(minβ)|}   (2)

 

式中，σ(i)表示集群Btemp含柵格總需求量的標(biāo)準(zhǔn)差；ha,b代表集群Btemp含柵格總需求量的平均值；θi,j代表置信水平系數(shù)。

 

考慮到物流企業(yè)在物流配送過程中不同類型用戶對時間窗的需求，如果物流配送時間到達配送點的時間早于設(shè)定的時間窗，則需要在原地等待直至?xí)r間窗開啟，將耗費時間成本。為此，將懲罰系數(shù)ψa,b,c引入到遠距離物流配送調(diào)度中，分析配送延遲對用戶滿意度產(chǎn)生的影響。將遠距離物流配送調(diào)度時間最短和用戶滿意度為目標(biāo)，根據(jù)虛擬用戶的需求量，構(gòu)建目標(biāo)函數(shù)。遠距離物流配送調(diào)度時間Zij和用戶滿意度top對應(yīng)的計算式如下：

 

 

上式中，zf代表客戶的懲罰成本；pk代表廣義用戶滿意度系數(shù)；ωa代表車輛到達客戶a的時間窗；tup代表隨機兩個用戶之間的時間窗；tcx代表遠距離物流配送延遲。

 

為了優(yōu)化配送方案，提高用戶滿意度和效益，根據(jù)遠距離物流配送調(diào)度時間最小minZij和用戶滿意度最大maxtop為依據(jù)，按照車輛先真實后虛擬用戶配送的原則，構(gòu)建響應(yīng)用戶隨機需求的遠距離物流配送調(diào)度模型?,如式(6)所示：

 

 

2.2 遠距離物流配送調(diào)度模型求解

為了得到最優(yōu)的配送方案，通過求解遠距離物流配送調(diào)度模型，以確定最佳的車輛配送路線、出發(fā)時間和資源分配，最大程度地滿足用戶需求并降低運營成本。PSO算法[8,9]8-9]是基于全局最優(yōu)以及個體最優(yōu)的目的不斷變換速度以及位置更新，整體的操作過程十分簡單，并且還具有比較高的搜索效率，在尋優(yōu)過程中具有比較好的尋優(yōu)能力。種群中所有粒子的飛行方向都是通過全局最優(yōu)極值來確定的，由于迭代到設(shè)定次數(shù)后，種群中所有粒子都會被限制在一個比較小的范圍內(nèi)，詳細的飛行狀態(tài)如圖2所示：

 

圖2 PSO算法迭代前后粒子狀態(tài)圖   下載原圖

 

在迭代前后粒子狀態(tài)中，假定搜索對象是由m個粒子構(gòu)成的群體，從而得到最佳定位。在一個群體中，單個粒子的狀態(tài)可以用其位置和速度來描述。粒子在每次迭代后更新的位置和速度計算式如下：

 

{vt+1ij=ω⋅vtij+c1r1⋅(ptij−xtij)+c2r2⋅(gtij−xtij)xt+1ij=xtij+vt+1ij   (7)

 

代表粒子在完成第t次迭代處理后得到粒子的速度；xtij

i

j

t

代表粒子在完成第t次迭代處理后得到粒子的位置；ω代表慣性權(quán)重；c1和c2代表學(xué)習(xí)因子；r1和r2代表在[0,1]內(nèi)的隨機系數(shù)；ptij

i

j

t

代表個體最優(yōu)；gtij

i

j

t

代表全局最優(yōu)。

 

細菌搜索(Bacterial Foraging Optimization,BFO)算法[10,11]10-11]基于大腸桿菌趨利避害的搜索行為，得到一種基于群體智能的新算法。結(jié)合對大腸桿菌的研究，可以獲取整個優(yōu)化算法的詳細操作步驟：

 

1)大腸桿菌在自然界中隨意游蕩，尋找潛在的食源；

 

2)確定是否進入了一個食物源地帶，若為營養(yǎng)豐富，則繼續(xù)進行，并進入這個地帶；否則，就必須改變運動的方向。

 

3)在捕食的過程中，適當(dāng)?shù)卣{(diào)整自己的移動方向，向更多的食物來源地遷移。

 

在細菌覓食過程中，將細菌的趨化覓食過程中狀態(tài)更新公式表示如下形式：

 

xt+1i=xt+1i+s(i)N(φt+1i)   (8)

 

代表在t+1時段通過隨機函數(shù)形成的任意角度；xt+1i

i

t

+

1

代表細菌個體i在t+1時段內(nèi)完成一次趨化行為后的位置；s(i)代表角度對應(yīng)的標(biāo)準(zhǔn)化函數(shù)；N(·)代表細菌個體的移動步長。

 

由于PSO算法相對而言更容易陷入局部最優(yōu)值，而BFO算法具有較強的全局搜索能力，能夠通過模擬細菌覓食的行為，更好地探索整個搜索空間，從而找到更優(yōu)的解。因此，將BFO算法加入到PSO算法中，改進PSO算法[12,13]12-13]。結(jié)合上述分析，采用改進PSO算法對基于響應(yīng)用戶隨機需求的遠距離物流配送調(diào)度模型求解，詳細的操作步驟如下：

 

1)初始化：

 

設(shè)定改進PSO算法[14,15]14-15]中的參數(shù)，將群體中的粒子數(shù)量設(shè)定為m, 最大迭代次數(shù)設(shè)定為umax,根據(jù)實際調(diào)度需求設(shè)定粒子的速度變化范圍為[vmin,vmax],對群體中各個粒子的位置以及速度初始化處理，同時經(jīng)過搜索確定全局和個體最優(yōu)。

 

2)計算不同個體的適應(yīng)度取值：

 

計算群體中不同個體的適應(yīng)度取值，選取最短遠距離物流配送調(diào)度時間和最高用戶滿意度作為適應(yīng)度函數(shù)；對比個體適應(yīng)度函數(shù)與歷史適應(yīng)度函數(shù)最優(yōu)值，假定適應(yīng)度取值高于歷史適應(yīng)度，由此更新粒子最優(yōu)值和全局最優(yōu)值；相反，對優(yōu)化結(jié)果無需進行擴展更新。

 

3)通過迭代處理，假設(shè)單一粒子的速度大于粒子最大速度，則需要對當(dāng)前速度展開更新，將其表示為vmax;反之，如果vi