電子商務(wù)環(huán)境下路徑優(yōu)化模型及算法研究

王紹凡+陳荔

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

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

DOIDOI：10.11907/rjdk.171130

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：1672-7800（2017）008-0032-04

0 引言

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

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

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

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

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

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

定義模型的決策變量：

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

基于以上描述及假設(shè)，針對(duì)時(shí)間約束條件，增加懲罰函數(shù)，建立總成本最小的目標(biāo)優(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

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

2 算法求解

2.1 智能水滴算法

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)（i，j）兩點(diǎn)之間泥土量越少時(shí)，則位置j被i位置處的智能水滴選取為下一運(yùn)行位置的可能性增大。計(jì)算下一位置j的概率表達(dá)式如下：

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

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

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

2.2 算法改進(jìn)

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

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

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

水滴移動(dòng)路徑中的泥土含量不斷變化，算法進(jìn)行搜索時(shí)易陷入局部最優(yōu)狀態(tài)。針對(duì)這一缺陷，借助最大最小概念，對(duì)從位置i到位置j在路徑上的水滴流動(dòng)泥土量設(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個(gè)顧客進(jìn)行配送，配送中心及顧客坐標(biāo)數(shù)據(jù)如表1所示。

假設(shè)配送中心為同一規(guī)格的配送車輛，且車輛的最大載重為30kg，平均行駛速度為30km/h，每輛車啟動(dòng)所需的固定費(fèi)用為10元/輛，每輛車單位行駛距離費(fèi)用為0.7元/km，配送中心工作時(shí)間為[6：30-19：00]；配送車輛比客戶要求的時(shí)間早到的懲罰系數(shù)為15/時(shí)，配送車輛比客戶要求的時(shí)間晚到則懲罰系數(shù)為20/時(shí)；智能水滴算法參數(shù)為：水滴個(gè)數(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。

編號(hào)坐標(biāo)需求量/kg服務(wù)時(shí)間/min可接受時(shí)間期望時(shí)間[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可從看出，改進(jìn)前后的算法具有對(duì)比性，改進(jìn)后的算法更具收斂性，所求目標(biāo)函數(shù)成本更低。當(dāng)?shù)?0次時(shí)，可求得最優(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