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

 

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

 

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

 

2 算法

2.1 構建遠距離物流配送調度模型

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

 

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

 

在實際遠距離物流配送調度過程中，考慮響應用戶隨機需求的情況下，需要作出以下假設：

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

 

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

 

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

 

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

 

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

 

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

 

 

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

 

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

 

 

2.2 遠距離物流配送調度模型求解

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

 

圖2 PSO算法迭代前后粒子狀態圖   下載原圖

 

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

 

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

 

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

i

j

t

代表粒子在完成第t次迭代處理后得到粒子的位置；ω代表慣性權重；c1和c2代表學習因子；r1和r2代表在[0,1]內的隨機系數；ptij

i

j

t

代表個體最優；gtij

i

j

t

代表全局最優。

 

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

 

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

 

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

 

3)在捕食的過程中，適當地調整自己的移動方向，向更多的食物來源地遷移。

 

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

 

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

 

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

i

t

+

1

代表細菌個體i在t+1時段內完成一次趨化行為后的位置；s(i)代表角度對應的標準化函數；N(·)代表細菌個體的移動步長。

 

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

 

1)初始化：

 

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

 

2)計算不同個體的適應度取值：

 

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

 

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