隨機需求下集送一體化節(jié)能配送線路問題研究

魏珂悅

一、引言

在實際配送中，車輛在配送的同時也有回收需求，即集送一體化VRP。隨機需求VRP是指客戶位置確定但需求量不確定，僅知道其概率分布。隨著能源價格上升，節(jié)能物流得到發(fā)展，要求減少車輛在行駛過程中所產(chǎn)生的燃油消耗。綜合考慮節(jié)能車輛路徑問題和隨機取貨需求的研究還未引起廣泛關(guān)注。本文研究軟時間窗約束下，取貨需求服從泊松分布的集送一體化節(jié)能配送線路優(yōu)化問題，以期增加企業(yè)收益并降低能耗。

二、問題模型

以單配送中心與多個客戶點之間的物流配送網(wǎng)絡(luò)為研究對象。同類型的一組車輛裝載客戶所需的貨物從配送中心出發(fā)，采用巡回運輸方式按客戶點進行配送和集貨服務(wù)，最終返回配送中心。各節(jié)點位置、客戶點的配送需求量已知，車輛出發(fā)前固定攬收貨物量已知。在滿足約束條件下，以最低成本得出運輸線路決策，同時多攬收貨物。

（一）假設(shè)條件

使用的車輛數(shù)不超過配送中心限制；每個客戶僅被訪問一次；送貨與集貨同時進行，服務(wù)時間忽略；距離取歐氏距離。時間窗開放后，客戶回收貨物是一個隨機過程。參考Fleischmana[1]等人文獻，假設(shè)回收過程為服從泊松分布。攬收貨物為標(biāo)準(zhǔn)件，重量和數(shù)量成線性關(guān)系。

（二）符號與參數(shù)說明

C1為單位車輛固定啟用成本。C0為單位距離運輸費用。Cf為單位油價。sij為點i和j之間的距離。K={k=1，2，3，…，m}為車輛集合。A={（i，j），i∈N，j∈N，i≠j}代表車場、客戶點之間邊的集合。[Ei，Li]為客戶i的服務(wù)時間窗要求。pe、pl分別為配送車輛提前到達、延遲到達的單位時間懲罰成本。Capa為車輛最大載重量。Tj為配送車輛到達客戶j的時刻。Tij為車輛在弧（i，j）的行駛時間。Vij為?。╥，j）的行駛速度，取隨機整數(shù)。F為單位重量貨物的收件費用。g為單位件數(shù)貨物的重量。di為出發(fā)前i的配送需求重量。pi為出發(fā)前i已知的攬收貨物重量。αij為與?。╥，j）有關(guān)的常數(shù)。β與車型有關(guān)，ω為空車重量。Qij為弧i，j是車輛的載重量。tr為燃油轉(zhuǎn)油耗系數(shù)。

決策變量xijk==1第k輛車服務(wù)客戶i后連續(xù)服務(wù)客戶j=0否則

（三）模型建立

min f1=C1∑mk=1xijk+∑k∈K∑（i，j）∈Asij·xijk·C0（1）

min f2=∑i∈NPTi（2）

式（1）、（2）表示行車成本和時間懲罰成本。假設(shè)客戶i貨物收集件數(shù)服從參數(shù)為λi·△t的泊松分布，建立集貨載件數(shù)最大化目標(biāo)函數(shù)。

maxR=F·g·∑i∈N，i≠0（Ti-Ei）·λi

車輛在弧i，j上行駛產(chǎn)生的能量消耗采用如下公式[2]：

EGij=αijω+Qij+βv2ijsij

該公式計算得出車輛在弧i，j上產(chǎn)生的的能耗EGij，單位焦耳，轉(zhuǎn)化為kWh。1L0號柴油可提供約9.32kWh能量，柴油發(fā)動機平均燃油率約為39%，由此能量消耗轉(zhuǎn)化為燃油量，計算出油耗成本。

minf3=Cf∑k∈K∑i，j∈Atr·αijω+Qij+βν2ijsij·xijk

式（3）轉(zhuǎn)化為maxR=-minR，對4個優(yōu)化目標(biāo)進行線性加和轉(zhuǎn)化為新目標(biāo)函數(shù)Z。

minZ=f1+f2-R+f3

∑mk=1∑ni=0xijk=1j∈V＼{0}

∑mk=1∑nj=0xijk=1i∈V＼{0}

∑i∈NXi0k=∑j∈NX0jk≤mk∈K

∑i∈S∑j∈Sxij≤S-1，≤S≤n-2， SN

PTi=maxpeLi-Ti，0，pl（Ti-Ei）i∈N

Tij=dijvij

Tj=Ti+Tij

∑ni=1∑nj=1dixijk≤Capak∈K

∑ni=1∑nj=1pi+gTi-Eiλixijk≤Capak∈K

djxijk+pi+gTi-Eiλixijk≤Qij≤Capa-dixijk

∑nj=1Q0j=∑nj=1dj

式（7）、（8）為客戶點的訪問唯一性約束；式（9）表示所有車輛從車場出發(fā)，配送完后返回配送中心；式（10）保證不產(chǎn)生任何子回路。式（11）表示車輛的時間懲罰成本；式（12）表示車輛從節(jié)點i到j(luò)的行駛時間；式（13）表示到達j的時間。式（15）表示出發(fā)時，正向配送需求重量約束；式（16）表示返回時，攬收貨物重量約束；式（17）表示車輛在i，j弧上的載重約束；式（18）保證出發(fā)時裝載貨物總和滿足客戶需求。

三、模型求解

PSO算法在解決車輛路徑問題上十分高效，貪心算法在處理約束條件時快速簡便，本文設(shè)計基于貪心算法的PSO算法優(yōu)化車輛行駛路線。首先生成車輛服務(wù)客戶序列，其次引入貪心算法對不滿足車約束的方案進行調(diào)整，最后返回優(yōu)化路徑。每個粒子位置的具體編碼由兩部分構(gòu)成：X為車輛使用情況的K維向量，位置編碼取0或1分別代表未選用和選用；Y為車輛行駛路線的K×N維矩陣，N為客戶數(shù)。對調(diào)整后的客戶序列計算粒子適應(yīng)度值，對不滿足約束條件的粒子適應(yīng)度值施加懲罰值M。運行結(jié)束所得全局最優(yōu)值gbest

四、實驗結(jié)果分析

選取測試算例[3]，節(jié)點坐標(biāo)、客戶需求量等來自經(jīng)典算例。αij=0.0981，β=2.1，v是取[40，80]上的隨機整數(shù)。車場坐標(biāo)（40，40），客戶數(shù)20，車輛數(shù)6，車輛自重2.7噸，最大載重量1.5噸。算法最大迭代次數(shù)200，種群規(guī)模100，加速系數(shù)c1=c2=2.05；粒子慣性權(quán)重w1=0.729。對算例重復(fù)仿真20次，統(tǒng)計最佳適應(yīng)度值，見表1。

最優(yōu)解對應(yīng)的車輛總行駛成本4882元，燃油消耗成本378元，不滿足軟時間窗的懲罰成本259元。6輛車均被選用，行車路徑為：車輛1：0-12-30-4-29-22-1-0；車輛2：0-7-18-3-0；車輛3：0-21-14-19-27-13-0；車輛4：0-28-8-11-0；車輛5：0-26-25-10-24-15-20-2-17-0；車輛6：0-16-5-23-9-6-0。

為驗證優(yōu)化效果，另設(shè)計不考慮動態(tài)集貨數(shù)量和油耗費用的配送行駛方案并進行求解。在相同運行環(huán)境下，重復(fù)運行5次所得最優(yōu)結(jié)果見表2。

根據(jù)上表可知，綜合考慮集貨需求和油耗兩個因素后，配送成本上升，但集貨收益增加，更好滿足客戶的集貨需求，且?guī)缀鯇崿F(xiàn)車輛滿載，油耗費用降低。

綜上所述，攬收貨物需求、降低能耗的差異性，在一定程度上對物流配送線路均存在影響。節(jié)省油耗成本又增加集貨收益的同時，往往又提升其他配送成本，而客戶的滿意率也受到影響。因此，物流企業(yè)根據(jù)實際情況制定決策方案時，需考慮如何在節(jié)約成本和提升服務(wù)中權(quán)衡利弊，實現(xiàn)多目標(biāo)共贏。

五、總結(jié)與展望

從研究視角、模型、求解算法三方面進行創(chuàng)新，建立帶軟時間窗的集送一體化低油耗配送線路模型，設(shè)計PSO算法得出車輛路徑，利用模擬數(shù)據(jù)進行仿真。多車型、多配送中心和裝箱約束是本文下一步研究的方向。（作者單位：福州大學(xué)經(jīng)濟與管理學(xué)院）

參考文獻：

[1] Moritz Fleischmann，RoelofKuik，Rommert Dekker.Controlling inventories with stochastic item returns：A basic model[J].European Journal of Operational Research，2002（138）：63-75.

[2] TolgaBektas， Gilbert Laporte. The Pollution-Routing Problem[J]. Transportation Research Part B，2011（45）：1232-1250.

[3] Iori M. Metaheuristic algorithms for combinatorial optimization problems[D]. Bologna： University of Bologna， 2004.