電子商務環境下路徑優化模型及算法研究

王紹凡+陳荔

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

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

DOIDOI：10.11907/rjdk.171130

中圖分類號：TP312

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

0 引言

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

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

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

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

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

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

定義模型的決策變量：

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

基于以上描述及假設，針對時間約束條件，增加懲罰函數，建立總成本最小的目標優化模型如下：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

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

2 算法求解

2.1 智能水滴算法

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

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

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

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

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

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

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

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

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

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

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

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

在式（7）中，ρ0和ρn通常都會選擇0-1之間的正數，并且兩者之間滿足關系式ρ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是一個很小的正數，用以確保f（·）的分母不為零。g（soil（i，j））可將兩點間路徑上的泥土量轉換為正值，計算公式表述如下：

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

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

2.2 算法改進

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

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

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

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

Δ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）

根據上述變化規律，能夠避免原來算法過早產生全局最優解問題，有效避免在局部搜索過程中所發生的停滯現象，算法收斂性得到提升。

3 算例分析

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

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

編號坐標需求量/kg服務時間/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可從看出，改進前后的算法具有對比性，改進后的算法更具收斂性，所求目標函數成本更低。當迭代到30次時，可求得最優解Z=975.12元，且完成任務需使用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