1 引言
遠(yuǎn)距離物流配送調(diào)度指在物流配送中心給定配送任務(wù)的情況下，如何派車、組織運(yùn)輸可以確保配送路程最短且運(yùn)輸成本最低[1,2]?，F(xiàn)階段，我國(guó)大部分的物流企業(yè)在資源運(yùn)輸過程中存在分配不均勻和配送線路安排不合理等問題，導(dǎo)致運(yùn)力資源嚴(yán)重浪費(fèi)，而缺乏完整的遠(yuǎn)距離物流配送調(diào)度方案是造成上述現(xiàn)象出現(xiàn)的重要因素，所以研究遠(yuǎn)距離
物流配送調(diào)度具有十分重要的研究意義。
基于上述背景，為了減少成本、提高效率，國(guó)內(nèi)相關(guān)專家針對(duì)遠(yuǎn)距離物流配送調(diào)度方面的問題展開了大量研究，例如：杜子超等人[3]構(gòu)建眾包配送車輛調(diào)度模型，引入蟻群—量子粒子群混合優(yōu)化算法對(duì)模型求解，確定車輛調(diào)度方案；黃逸文等人[4]分析物流系統(tǒng)的運(yùn)行特性，構(gòu)建物流協(xié)同調(diào)度模型，對(duì)模型協(xié)同優(yōu)化處理，進(jìn)而獲取最佳調(diào)度方案；曹志鵬等人[5]提出一種全新的動(dòng)態(tài)調(diào)度方法，通過局部搜索算法確定最終車輛動(dòng)態(tài)調(diào)度方案。
在以上幾種研究算法的基礎(chǔ)上，提出了一種響應(yīng)用戶隨機(jī)需求的遠(yuǎn)距離物流配送調(diào)度算法。仿真分析表明，所提算法可以大幅度提升用戶滿意度以及調(diào)度效率，更好地解決遠(yuǎn)距離物流配送調(diào)度問題。
2 算法
2.1 構(gòu)建遠(yuǎn)距離
物流配送調(diào)度模型
由于在實(shí)際物流配送過程中，受到訂單量的波動(dòng)、用戶臨時(shí)需求的變化等影響，用戶的需求往往是隨機(jī)而變的[6,7]。為了更真實(shí)地模擬現(xiàn)實(shí)物流運(yùn)輸環(huán)境，需要考慮響應(yīng)用戶隨機(jī)需求，設(shè)置真實(shí)用戶與虛擬用戶，以此構(gòu)建遠(yuǎn)距離物流配送調(diào)度模型，從而制定調(diào)度方案，優(yōu)化配送調(diào)度。
通常物流配送系統(tǒng)包含一個(gè)配送中心和多個(gè)用戶，主要通過專業(yè)的物流配送車輛進(jìn)行服務(wù)。將遠(yuǎn)距離起始時(shí)間設(shè)定為t0,配送結(jié)束時(shí)間為t1。在t0時(shí)刻之前出現(xiàn)的用戶被稱為真實(shí)用戶，為了降低配送成本并更好地服務(wù)于在t0時(shí)間后隨機(jī)出現(xiàn)的用戶，中間某個(gè)時(shí)間段設(shè)定為tn。根據(jù)用戶以往的需求信息，預(yù)測(cè)在(t0,tn)時(shí)間段內(nèi)配送區(qū)域內(nèi)可能出現(xiàn)需求的用戶，并將這些用戶稱為虛擬用戶。結(jié)合虛擬用戶和真實(shí)用戶，制定遠(yuǎn)距離物流配送調(diào)度方案。假設(shè)沒有出現(xiàn)虛擬客戶需求，則繼續(xù)按照原始配送方案配送；反之，則需要將車輛朝著下一個(gè)虛擬需求用戶出現(xiàn)的方向行駛，如果后續(xù)并沒有虛擬用戶出現(xiàn)，則直接返回至物流配送中心。對(duì)于在tn之后出現(xiàn)的客戶需求，由于無(wú)法及時(shí)滿足用戶的配送時(shí)間需求，所以可以將其作為設(shè)定為下一配送計(jì)劃的真實(shí)用戶需求。
在實(shí)際遠(yuǎn)距離物流配送調(diào)度過程中，考慮響應(yīng)用戶隨機(jī)需求的情況下，需要作出以下假設(shè)：
1)物流配送車輛的數(shù)量有限。
2)物流配送車輛的容量和承載能力是完全相同的。
3)車輛從配送中心出發(fā)，完成物流配送服務(wù)后直接返回至配送中心。
4)每個(gè)用戶只可以由1輛車展開遠(yuǎn)距離物流配送服務(wù)。
5)在(t0,tn)期間隨機(jī)出現(xiàn)需求的用戶可以利用匯集以及預(yù)測(cè)獲取。
6)不同用戶的需求發(fā)生是相互獨(dú)立的。
通過上述分析，由于需要全面考慮用戶分布情況，可以將設(shè)定的物流配送區(qū)域劃分為多個(gè)柵格，每個(gè)柵格代表用戶區(qū)域，根據(jù)配送區(qū)域人口密度大小確定柵格單元規(guī)模，其中在一個(gè)柵格內(nèi)的用戶即為同一個(gè)配送區(qū)域。遠(yuǎn)距離物流配送區(qū)域柵格圖和集群示意圖如圖1所示。除了歷史沒有出現(xiàn)用戶的柵格和物流配送服務(wù)開始前期已經(jīng)出現(xiàn)的真實(shí)用戶所在柵格，剩余的柵格ai可能隨機(jī)出現(xiàn)的用戶需求。
圖1 遠(yuǎn)距離物流配送柵格圖和集群示意圖 下載原圖
為了解不同時(shí)間段的需求強(qiáng)度和波動(dòng)性，計(jì)算歷史時(shí)間段內(nèi)的用戶需求概率，確定合適的車輛調(diào)度策略。統(tǒng)計(jì)檢驗(yàn)各個(gè)柵格ai在設(shè)定單位時(shí)間出現(xiàn)用戶需求的概率β(zs),則集群c在歷史時(shí)間段內(nèi)的用戶需求概率β(zc)可以表示為式(1)的形式：
式中，n表示單位時(shí)間內(nèi)出現(xiàn)用戶需求的次數(shù)。如果β(zc)的取值大于等于給定的經(jīng)驗(yàn)概率數(shù)值C(minβ),則代表集群中存在隨機(jī)需求的虛擬用戶；反之，不存在虛擬用戶。對(duì)剩下的全部柵格遍歷處理，刪除無(wú)法形成虛擬用戶的柵格和集群。
為確保每個(gè)柵格只屬于一個(gè)集群，需要將柵格群內(nèi)重疊的集群刪除，根據(jù)β(zc)計(jì)算結(jié)果，獲取虛擬用戶，全部虛擬用戶的集合為：
Btemp={c|β(zc)≥C(minβ)|∪c|β(zc)≥C(minβ)|} (2)
式中，σ(i)表示集群Btemp含柵格總需求量的標(biāo)準(zhǔn)差；ha,b代表集群Btemp含柵格總需求量的平均值；θi,j代表置信水平系數(shù)。
考慮到物流企業(yè)在物流配送過程中不同類型用戶對(duì)時(shí)間窗的需求，如果物流配送時(shí)間到達(dá)配送點(diǎn)的時(shí)間早于設(shè)定的時(shí)間窗，則需要在原地等待直至?xí)r間窗開啟，將耗費(fèi)時(shí)間成本。為此，將懲罰系數(shù)ψa,b,c引入到遠(yuǎn)距離物流配送調(diào)度中，分析配送延遲對(duì)用戶滿意度產(chǎn)生的影響。將遠(yuǎn)距離物流配送調(diào)度時(shí)間最短和用戶滿意度為目標(biāo)，根據(jù)虛擬用戶的需求量，構(gòu)建目標(biāo)函數(shù)。遠(yuǎn)距離物流配送調(diào)度時(shí)間Zij和用戶滿意度top對(duì)應(yīng)的計(jì)算式如下：
上式中，zf代表客戶的懲罰成本；pk代表廣義用戶滿意度系數(shù)；ωa代表車輛到達(dá)客戶a的時(shí)間窗；tup代表隨機(jī)兩個(gè)用戶之間的時(shí)間窗；tcx代表遠(yuǎn)距離物流配送延遲。
為了優(yōu)化配送方案，提高用戶滿意度和效益，根據(jù)遠(yuǎn)距離物流配送調(diào)度時(shí)間最小minZij和用戶滿意度最大maxtop為依據(jù)，按照車輛先真實(shí)后虛擬用戶配送的原則，構(gòu)建響應(yīng)用戶隨機(jī)需求的遠(yuǎn)距離物流配送調(diào)度模型?,如式(6)所示：
2.2 遠(yuǎn)距離物流配送調(diào)度模型求解
為了得到最優(yōu)的配送方案，通過求解遠(yuǎn)距離物流配送調(diào)度模型，以確定最佳的車輛配送路線、出發(fā)時(shí)間和資源分配，最大程度地滿足用戶需求并降低運(yùn)營(yíng)成本。PSO算法[8,9]8-9]是基于全局最優(yōu)以及個(gè)體最優(yōu)的目的不斷變換速度以及位置更新，整體的操作過程十分簡(jiǎn)單，并且還具有比較高的搜索效率，在尋優(yōu)過程中具有比較好的尋優(yōu)能力。種群中所有粒子的飛行方向都是通過全局最優(yōu)極值來(lái)確定的，由于迭代到設(shè)定次數(shù)后，種群中所有粒子都會(huì)被限制在一個(gè)比較小的范圍內(nèi)，詳細(xì)的飛行狀態(tài)如圖2所示：
圖2 PSO算法迭代前后粒子狀態(tài)圖 下載原圖
在迭代前后粒子狀態(tài)中，假定搜索對(duì)象是由m個(gè)粒子構(gòu)成的群體，從而得到最佳定位。在一個(gè)群體中，單個(gè)粒子的狀態(tài)可以用其位置和速度來(lái)描述。粒子在每次迭代后更新的位置和速度計(jì)算式如下：
{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)的隨機(jī)系數(shù)；ptij
i
j
t
代表個(gè)體最優(yōu)；gtij
i
j
t
代表全局最優(yōu)。
細(xì)菌搜索(Bacterial Foraging Optimization,BFO)算法[10,11]10-11]基于大腸桿菌趨利避害的搜索行為，得到一種基于群體智能的新算法。結(jié)合對(duì)大腸桿菌的研究，可以獲取整個(gè)優(yōu)化算法的詳細(xì)操作步驟：
1)大腸桿菌在自然界中隨意游蕩，尋找潛在的食源；
2)確定是否進(jìn)入了一個(gè)食物源地帶，若為營(yíng)養(yǎng)豐富，則繼續(xù)進(jìn)行，并進(jìn)入這個(gè)地帶；否則，就必須改變運(yùn)動(dòng)的方向。
3)在捕食的過程中，適當(dāng)?shù)卣{(diào)整自己的移動(dòng)方向，向更多的食物來(lái)源地遷移。
在細(xì)菌覓食過程中，將細(xì)菌的趨化覓食過程中狀態(tài)更新公式表示如下形式：
xt+1i=xt+1i+s(i)N(φt+1i) (8)
代表在t+1時(shí)段通過隨機(jī)函數(shù)形成的任意角度；xt+1i
i
t
+
1
代表細(xì)菌個(gè)體i在t+1時(shí)段內(nèi)完成一次趨化行為后的位置；s(i)代表角度對(duì)應(yīng)的標(biāo)準(zhǔn)化函數(shù)；N(·)代表細(xì)菌個(gè)體的移動(dòng)步長(zhǎng)。
由于PSO算法相對(duì)而言更容易陷入局部最優(yōu)值，而BFO算法具有較強(qiáng)的全局搜索能力，能夠通過模擬細(xì)菌覓食的行為，更好地探索整個(gè)搜索空間，從而找到更優(yōu)的解。因此，將BFO算法加入到PSO算法中，改進(jìn)PSO算法[12,13]12-13]。結(jié)合上述分析，采用改進(jìn)PSO算法對(duì)基于響應(yīng)用戶隨機(jī)需求的遠(yuǎn)距離物流配送調(diào)度模型求解，詳細(xì)的操作步驟如下：
1)初始化：
設(shè)定改進(jìn)PSO算法[14,15]14-15]中的參數(shù)，將群體中的粒子數(shù)量設(shè)定為m, 最大迭代次數(shù)設(shè)定為umax,根據(jù)實(shí)際調(diào)度需求設(shè)定粒子的速度變化范圍為[vmin,vmax],對(duì)群體中各個(gè)粒子的位置以及速度初始化處理，同時(shí)經(jīng)過搜索確定全局和個(gè)體最優(yōu)。
2)計(jì)算不同個(gè)體的適應(yīng)度取值：
計(jì)算群體中不同個(gè)體的適應(yīng)度取值，選取最短遠(yuǎn)距離物流配送調(diào)度時(shí)間和最高用戶滿意度作為適應(yīng)度函數(shù)；對(duì)比個(gè)體適應(yīng)度函數(shù)與歷史適應(yīng)度函數(shù)最優(yōu)值，假定適應(yīng)度取值高于歷史適應(yīng)度，由此更新粒子最優(yōu)值和全局最優(yōu)值；相反，對(duì)優(yōu)化結(jié)果無(wú)需進(jìn)行擴(kuò)展更新。
3)通過迭代處理，假設(shè)單一粒子的速度大于粒子最大速度，則需要對(duì)當(dāng)前速度展開更新，將其表示為vmax;反之，如果vi
滬公網(wǎng)安備 31011202008041號(hào)
