王紹凡+陳荔

摘 要：研究了電子商務(wù)環(huán)境下有時間窗的車輛路徑問題，考慮了時間窗限制的約束，并構(gòu)建以最小成本為目標的模型，包括固定成本、運輸成本和懲罰成本。為求解所建模型，提出了基于改進智能水滴算法的車輛路徑優(yōu)化方案，并進行了程序設(shè)計。運用算法實例進行驗證，并將算法結(jié)果進行對比分析，表明改進的算法收斂性更好，能求出問題的最優(yōu)解。

關(guān)鍵詞：電子商務(wù)；時間窗；物流配送；車輛路徑問題；智能水滴算法

DOIDOI：10.11907/rjdk.171130

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：1672-7800（2017）008-0032-04

0 引言

電子商務(wù)模式受到越來越多的關(guān)注。在電子商務(wù)環(huán)境下，如何合理設(shè)計配送路線、提高效率、減少物流成本是急需解決的問題。

隨著信息技術(shù)和云計算的發(fā)展，形成了新的物流配送模式，學者對其形式及現(xiàn)狀進行了探索。郎茂祥[1-3]分別用遺傳、模擬退火和禁忌搜索等算法對一般VRP和有時間窗的VRP問題進行求解。何云等[4]以成本最低為目標并加入客戶時間滿意度構(gòu)建模型，運用遺傳算法求解獲得最優(yōu)配送路徑。TC Du等[5]針對電子商務(wù)B2C環(huán)境下的動態(tài)車輛路徑問題設(shè)計了模型算法求解。侯玉梅等[6]構(gòu)建了有時間窗的模型并求解。與傳統(tǒng)算法相比，智能水滴算法是根據(jù)自然界中水滴與所處環(huán)境之間相互作用產(chǎn)生河道過程的一種智能算法，最先被Hamed Shah-Hosseini[7]用于解決旅行商問題，最終收斂得到最優(yōu)解。隨后智能水滴算法用于解決旅行商問題、多維背包問題和灰度閾值問題等[8-10]。馬竹根[11]介紹了IWD的產(chǎn)生原因，闡述了多種領(lǐng)域應(yīng)用并進行總結(jié)。Iman Kamkar等[12]運用智能水滴算法求解一般車輛問題。徐佳敏等[13]將智能水滴算法運用到求解應(yīng)急物流問題中并得到優(yōu)化結(jié)果。周虹[14]和李珍萍[15]針對有時間窗問題運用智能水滴算法求解。

本文研究了電子商務(wù)環(huán)境下的VRP問題，基于改進智能水滴算法建立總成本最小模型，利用該算法求解最優(yōu)路線，并結(jié)合算例進行了驗證與分析。

1 配送路徑問題描述及模型

電子商務(wù)環(huán)境下的帶時間窗車輛路徑優(yōu)化問題可描述為：從一個配送中心出發(fā)為多個顧客進行服務(wù)，且車輛在配送任務(wù)結(jié)束后需返回出發(fā)點。假設(shè)配送車輛的型號一致并且最大承載量一定，顧客所需求的數(shù)量以及配送中心和顧客位置已知，并且顧客對于服務(wù)時間有限制。因此，本文就是在滿足一系列約束條件下，設(shè)計合理的配送路線的目標優(yōu)化問題。

令G=（N，S）為客戶點和配送中心及客戶之間連線所組成的無向路線圖，N表示需要配送的客戶集合，其中N={1，2，…，n}，0表示配送中心，S表示連線所組成的邊集合，K表示配送中心車輛總數(shù)，ri表示顧客需求量，ωk表示車輛的最大承載量，F(xiàn)k表示運輸車輛的固定成本，cij表示車輛k在顧客i與j之間的運輸成本，dij表示顧客與顧客之間及配送中心與顧客之間的距離，Tij表示車輛從顧客i到j(luò)的行駛時間，Tik表示車輛k到達顧客i的時間，ti表示為顧客i開始服務(wù)的時間，m1為提前到達等待的懲罰系數(shù)，m2為延遲到達的懲罰系數(shù)；vk表示車輛的平均行駛速度，[ATi，BTi]表示顧客i所期望的服務(wù)時間，[ETi，LTi]表示顧客i可接受的服務(wù)時間（ETi

定義模型的決策變量：

xkij=1車輛k從顧客i駛向顧客j；i，j=1，2，…，n；0否則；k=1，2，…k；（1） yki=1車輛k對顧客i服務(wù)；i，j=1，2，…，n；0否則；k=1，2，…k； （2）

基于以上描述及假設(shè)，針對時間約束條件，增加懲罰函數(shù)，建立總成本最小的目標優(yōu)化模型如下：minZ1=∑Kk=1∑Ni=1∑Nj=1cijdijxkij+∑Kk=1∑Nj=1Fkxk0j+m1∑Ni=1max（ATi-ti，0）+m2∑Ni=1maxti-BTi，0（3）s.t.

∑Ni=1riyki≤ωk

∑Ni=1∑Nj=1dijxkij≤D

∑Kk=1yki=1i=1，2，…，n

∑Nj=1xk0j=1；∑Ni=1xki1=1

∑Ni=1xkij=ykjj=1，2，…，n；k=1，2，….k

∑Nj=1xkij=ykii=1，2，…，n；k=1，2，…k

假定：①任何車輛所運送的客戶總需求量不能超過車輛的最大載重量；②每臺車的行駛運輸距離不大于車輛的最長運輸距離；③每位顧客只能由一輛車輛進行配送；④每臺配送車輛都由配送中心出發(fā)；⑤每臺車輛任務(wù)完成后都需要回到配送中心；⑥配送車輛完成當前配送任務(wù)后，為下一位顧客繼續(xù)提供服務(wù)約束。

2 算法求解

2.1 智能水滴算法

G=（N，S）為客戶點和配送中心及客戶點之間連線所組成的無向路線圖，表示電子商務(wù)環(huán)境下的車輛路徑問題。其中，N表示需要配送的客戶集合，其中N={1，2，…，n}，0表示配送中心；S表示連線所組成的邊集合，即客戶點之間的距離。

將水滴運動時所攜帶的泥土量設(shè)為soil（IWD），水滴向前行駛時的速度設(shè)為velocity（IWD）。在水滴運動時這兩項都在不斷變化，算法就是在其中找到一條最優(yōu)路徑，相當于解決實際優(yōu)化問題。

每個水滴從起始點出發(fā)相當于配送車輛從配送中心出發(fā)，并從滿足所有約束條件的顧客集合中，按照概率公式選擇出服務(wù)的下一位顧客，所有服務(wù)完成后必須回到配送中心。這個運行過程可形成多個閉合的配送回路。算法運行過程中所得的最優(yōu)解，需要用構(gòu)造的目標函數(shù)來確定。每次迭代結(jié)束后都可在完整的訪問路線中找到最優(yōu)解，定義為TIB，并用這個最優(yōu)解來替換每個節(jié)點之間的泥土量以及全局最優(yōu)解TTB。重復(fù)運行這一過程，直到期望的最優(yōu)解TTB產(chǎn)生或算法運行到最大迭代次數(shù)Itermax。

水滴從所處位置i流動到下一位置j，它的速度增加值設(shè)定為Δvelocity（IWD），它與兩者之間路徑上的泥土量相關(guān)，表示為：

Δvelocity（IWD）=ΔvelIWD（t）=avbv+cv·soil（i，j）（4）

av、bv、cv分別為水滴速度的更新參數(shù)。

水滴中泥土的增加量Δsoil（IWD）與水滴在相鄰兩點間運動所耗費的時間相關(guān)，這一時間是以水滴的流速表示的，即time（i，j；velIWD）。因此，泥土的增加量表示為：

Δsoil（IWD）=Δsoil（i，j）=asbs+cs·time（i，j；velIWD）（5）

as、bs、cs分別為大于0的參數(shù)。智能水滴相鄰兩點間的時間可根據(jù)物理學中的勻速直線運動公式計算，即由兩節(jié)點間的距離與行駛速度計算：

time（i，j；velIWD）=D（i，j）velIWD（6）

智能水滴從位置i運動到位置j的過程中，會帶走一定數(shù)量的泥土，可由智能水滴所帶走的泥土數(shù)量（Δsoil（i，j））來更新，其表達式為：

soil（i，j）=ρ0·soil（i，j）-ρn·Δsoil（i，j）（7）

在式（7）中，ρ0和ρn通常都會選擇0-1之間的正數(shù)，并且兩者之間滿足關(guān)系式ρ0=1-ρn。

當（i，j）兩點之間泥土量越少時，則位置j被i位置處的智能水滴選取為下一運行位置的可能性增大。計算下一位置j的概率表達式如下：

pIWDi（j）=f（soil（i，j））∑kvc（IWD）f（soil（i，k））（8）

f（soil（i，j））=1εs+g（soil（i，j））（9）

式中的εs是一個很小的正數(shù)，用以確保f（·）的分母不為零。g（soil（i，j））可將兩點間路徑上的泥土量轉(zhuǎn)換為正值，計算公式表述如下：

g（soil（i，j））=soil（i，j）ifmin（soil（i，l））≥0soil（i，j）-min（soil（i，l））else（10）

函數(shù)min（·）表示從當前位置到剩下所有可能位置的路徑中，所含有泥土量的最小值。

2.2 算法改進

在車輛配送路徑優(yōu)化問題中，顧客之間的相對距離是車輛選擇哪條路徑的重要因素。因此，上述的概率公式可根據(jù)其路徑中的泥土量以及兩節(jié)點之間的距離來計算，即：

pIWDi（j）=f（soil（i，j））·ηij∑kvc（IWD）f（soil（i，k））·ηij（11）

其中，ηij=1/dij，dij表示顧客i與顧客j兩者之間的距離。

水滴移動路徑中的泥土含量不斷變化，算法進行搜索時易陷入局部最優(yōu)狀態(tài)。針對這一缺陷，借助最大最小概念，對從位置i到位置j在路徑上的水滴流動泥土量設(shè)定上下限，即：

Δsoilmin≤Δsoil（i，j）≤Δsoilmax（12）

亦可表示為：

Δ1soil（i，j）=Δsoilmax；ifΔsoil（i，j）>ΔsoilmaxΔsoilmin；ifΔsoil（i，j）<ΔsoilminΔsoil（i，j）；ifotherwise（13）

可將水滴泥土量和路徑所含泥土量的變化公式表述為：

soil（i，j）=ρ0·soil（i，j）-ρn·Δ1soil（i，j）（14）

soilIWD=soilIWD+Δ1soil（i，j）（15）

根據(jù)上述變化規(guī)律，能夠避免原來算法過早產(chǎn)生全局最優(yōu)解問題，有效避免在局部搜索過程中所發(fā)生的停滯現(xiàn)象，算法收斂性得到提升。

3 算例分析

假定某一配送中心為12個顧客進行配送，配送中心及顧客坐標數(shù)據(jù)如表1所示。

假設(shè)配送中心為同一規(guī)格的配送車輛，且車輛的最大載重為30kg，平均行駛速度為30km/h，每輛車啟動所需的固定費用為10元/輛，每輛車單位行駛距離費用為0.7元/km，配送中心工作時間為[6：30-19：00]；配送車輛比客戶要求的時間早到的懲罰系數(shù)為15/時，配送車輛比客戶要求的時間晚到則懲罰系數(shù)為20/時；智能水滴算法參數(shù)為：水滴個數(shù)20，av，bv，cv分別為1 000，20，1，as，bs，cs分別為1 000，10，1，ρn=0.9，ρIWD=0.8；初始速度和泥土量分別為InitVel=100，InitSoil=1000；最大迭代次數(shù)設(shè)為100。

編號坐標需求量/kg服務(wù)時間/min可接受時間期望時間[ETi，LTi][ATi，BTi]0（60，140）————1（30，114）2.512.5[8：00-17：00][9：00-11：30]2（40，36）315[8：00-10：30][8：30-10：30]3（48，96）315[8：00-17：00][9：00-15：00]4（52，120）630[8：00-12：00][8：30-11：30]5（92，154）315[8：00-8：30][8：00-8：30]6（92，66）2.512.5[8：00-17：00][10：00-15：00]7（94，100）525[8：00-17：00][8：30-11：30]8（108，100）525[8：00-10：45][9：00-10：30]9（44，160）630[8：00-8：30][8：00-8：30]10（20，54）420[8：00-13：00][8：00-12：00]11（108，32）525[8：00-13：00][10：30-12：00]12（130，88）525[8：00-17：00][9：00-15：00]

從圖1可從看出，改進前后的算法具有對比性，改進后的算法更具收斂性，所求目標函數(shù)成本更低。當?shù)?0次時，可求得最優(yōu)解Z=975.12元，且完成任務(wù)需使用7輛配送車。配送方案為：路徑1：0-9-0；路徑2：0-5-0；路徑3：0-12-8-0；路徑4：0-11-0；路徑5：0-4-7-6；路徑6：0-2-0；路徑7：0-1-10-3-0，如圖2所示。endprint