基于路徑靈活性的兩階段開放式低碳選址-路徑問題

劉成清，胡大偉，黃 榕

(長安大學(xué)汽車學(xué)院，西安710064)

隨著經(jīng)濟(jì)發(fā)展與城鎮(zhèn)化進(jìn)程的加快，城市人口與汽車保有量快速增長，導(dǎo)致城市物流配送需求快速上升，交通擁堵問題日益嚴(yán)重。城市交通擁堵導(dǎo)致運(yùn)輸車輛配送效率降低，CO2排放增加，這與巨大的城市物流配送需求及節(jié)能減排的物流產(chǎn)業(yè)發(fā)展理念相矛盾。在短時(shí)間內(nèi)，城市交通擁堵問題無法徹底解決，因此，節(jié)能、環(huán)保、高效的城市配送規(guī)劃方案成為緩解當(dāng)前矛盾的有效措施。近年來，如何減少運(yùn)輸過程中的CO2排放和燃油消耗成為眾多學(xué)者研究的熱點(diǎn)。Bektas等[1]在傳統(tǒng)車輛路徑問題中考慮CO2排放，基于綜合排放模型，提出了燃油車的污染-路徑問題(polluted routing problem,PRP)，并針對該問題的特點(diǎn)，建立準(zhǔn)確的模型；Demir等[2]基于總成本與時(shí)間的背反原理，構(gòu)建雙目標(biāo)的PRP模型，并提出了算法解決100個(gè)節(jié)點(diǎn)內(nèi)的PRP問題；Koc等[3]以最小化排放為目標(biāo)，建立異質(zhì)車隊(duì)的選址-路徑問題模型，并提出一種自適應(yīng)大鄰域搜索的元啟發(fā)式算法求解該問題。Ehmke等[4]考慮不同時(shí)段路網(wǎng)的交通情況，提出基于時(shí)間的最小化燃油消耗的車輛路徑問題，以決策在城市配送區(qū)域進(jìn)行配送活動(dòng)時(shí)的車輛路徑和出發(fā)時(shí)間?？紤]城市交通存在路徑可替代性強(qiáng)、擁堵空間分布不均等特點(diǎn)，Huang等[5]基于PRP問題，明確提出“路徑靈活性”概念，建立確定和隨機(jī)交通情形下，基于路徑靈活性和時(shí)間依賴性的車輛路徑問題模型，并以北京為例，測試模型和算法的有效性和實(shí)用性。Fabian等[6]在經(jīng)典車輛路徑問題(vehicle routing problem,VRP)中考慮路徑靈活性，分別以最小化總成本、燃油消耗/排放量、距離和旅行時(shí)間為目標(biāo)建立模型，并對比分析其差異。大量研究表明，在運(yùn)輸配送規(guī)劃中，考慮城市路網(wǎng)的路徑靈活性有助于減少能量消耗及CO2排放。

與PRP問題相比，選址-路徑問題(location routing problem,LRP)的研究起步較早，目前已取得豐富的成果，但仍存在許多有待發(fā)掘的領(lǐng)域[7-11]。胡大偉[12]運(yùn)用系統(tǒng)分析的思想和方法研究了物流系統(tǒng)中的LRP問題，并提出了多種啟發(fā)式算法，對LRP數(shù)學(xué)模型進(jìn)行優(yōu)化求解；Contardo等[13]建立了帶容量限制的兩階段選址-路徑問題(2E-LRP)模型，并提出一種分支切割精確算法和自適應(yīng)大鄰域搜索元啟發(fā)式算法；Vidovic等[14]建立了非危險(xiǎn)、可回收物品的2E-LRP數(shù)學(xué)模型，并提出一種兩階段貪婪啟發(fā)式算法；Pichka等[15]基于2E-LRP問題，分析城市中開放式路徑的可能性，提出兩階段開放式選址-路徑問題(2E-OLRP)，針對該問題建立了3種數(shù)學(xué)模型，并提出一種改進(jìn)的模擬退火算法。

研究發(fā)現(xiàn)，針對LRP或2E-LRP問題的相關(guān)研究中，未考慮實(shí)際路網(wǎng)情況，且僅根據(jù)距離計(jì)算運(yùn)輸成本，與實(shí)際運(yùn)輸過程存在較大差異；大部分PRP問題和考慮路徑靈活性問題的研究都僅針對單一路徑問題，而將選址與路徑問題進(jìn)行整體研究，比考慮其單一因素更能節(jié)約總成本，且2E-LRP模型有利于優(yōu)化整體運(yùn)輸配送網(wǎng)絡(luò)，進(jìn)一步降低總成本。此外，城市配送網(wǎng)絡(luò)中客戶點(diǎn)多、分布廣，且城市路網(wǎng)存在路徑可替代性強(qiáng)、交通擁堵空間分布不均等特點(diǎn)。因此，基于2E-OLRP模型，在總成本中考慮燃油消耗和CO2排放成本，在路徑規(guī)劃中考慮路徑靈活性，構(gòu)建2E-OLCLRP-WF模型，研究路徑靈活性對總成本和CO2排放的影響，為物流企業(yè)規(guī)劃節(jié)能、環(huán)保、高效的城市物流配送方案提供理論支撐和決策參考。

1 模型建立

1.1 問題描述

假設(shè)有一個(gè)倉庫V0，Ns個(gè)配送中心，Nc個(gè)客戶點(diǎn)，Nm個(gè)交叉口。所有的客戶點(diǎn)都必須被服務(wù)，且只能被訪問一次；交叉口可被多次訪問，也可不被訪問；每輛車的裝載量不超過最大車容量；任意配送中心服務(wù)的客戶總需求不超過該配送中心的最大容量；客戶點(diǎn)只能由配送中心服務(wù)；最后，以最小化總成本為目標(biāo)，在第一階段中，確定分配給每個(gè)配送中心的客戶以及第一層車輛的路徑，在第二階段中，確定第二層車輛的路徑。

圖1所示為2E-OLCLRP-WF模式的示意圖。第一層的車輛從倉庫出發(fā)，服務(wù)配送中心后，終止于該路徑上的最后一個(gè)配送中心，第一層車輛的路徑由實(shí)線箭頭表示，其中，第一層的車輛只能經(jīng)過倉庫、配送中心和交叉口，不能經(jīng)過客戶點(diǎn)；第二層的車輛從配送中心出發(fā)，服務(wù)客戶后，終止于該路徑上的最后一個(gè)客戶，第二層車輛的路徑由虛線箭頭表示，其中，第二層的車輛只能經(jīng)過配送中心、客戶點(diǎn)和交叉口，不能經(jīng)過倉庫。兩點(diǎn)之間能否直接到達(dá)取決于實(shí)際的路網(wǎng)情況。

路徑靈活性示意圖如圖2所示。圖中1和2分別表示兩個(gè)客戶點(diǎn)，從客戶點(diǎn)1到客戶點(diǎn)2存在3條不同的路徑。路徑靈活性是指兩點(diǎn)之間存在多條可供選擇的路徑，根據(jù)不同的車輛裝載量及各弧上的速度選擇的最優(yōu)路徑可能存在較大差異，因此，3條路徑均可能是客戶點(diǎn)1到客戶點(diǎn)2的最優(yōu)路徑。

圖1 2E-OLCLRP-WF問題示意圖Fig.1 The sketch of 2E-OLCLRP-WF problem

圖2 路徑靈活性示意圖Fig.2 The sketch of path flexibility

1.2 參數(shù)定義與模型假設(shè)

假設(shè)1：在1 d的時(shí)間段內(nèi)進(jìn)行配送規(guī)劃。

假設(shè)2：倉庫、配送中心處的車輛數(shù)無限制。

1.3 運(yùn)輸成本計(jì)算

2E-OLCLRP-WF問題中運(yùn)輸成本由燃油消耗成本和CO2排放成本組成，根據(jù)Barth等[16]、Scora等[17]所提出的綜合排放模型，燃油消耗率可由式(1)計(jì)算。

FR=ξ(sNV+P/η)/κ

(1)

式(1)中：ξ為空燃比；s為發(fā)動(dòng)機(jī)的摩擦系數(shù)，kJ/(rad·L)；N為發(fā)動(dòng)機(jī)轉(zhuǎn)速，rad/s；V為發(fā)動(dòng)機(jī)排量，L；η和κ為常數(shù)；P為發(fā)動(dòng)機(jī)輸出的功率，kW，可由式(2)計(jì)算。

P=Ptract/ηtf

(2)

式(2)中：ηtf為車輛傳動(dòng)系統(tǒng)的傳動(dòng)效率；Ptract為作用在車輪上的總驅(qū)動(dòng)力，N。

Ptract=(Mτ+Mgsinθ+0.5CdρAv2+MgCrcosθ)v/1 000

(3)

式(3)中：M為車輛的總質(zhì)量，kg；M=w+f，w為車輛整備質(zhì)量，kg；f為車輛負(fù)載，kg；v為車速，m/s；τ為加速度，m/s2；θ為道路坡度，(°)；g為重力常數(shù)，m/s2；Cd為空氣阻力系數(shù)；Cr為滾動(dòng)阻力系數(shù)；ρ為空氣密度，kg/m3；A為車輛迎風(fēng)面積，m2。

令弧(i,j)的長度為d，車輛在該弧上的速度為v，λ=ξ/κφ，γ=(1/1 000)ηtfη。其中，φ為燃油消耗率單位轉(zhuǎn)換系數(shù)；α=τ+gsinθ+gCrcosθ為車輛-路徑的固定常數(shù)；β=0.5CdρA為車輛的固定常數(shù)。則弧(i,j)上，車輛的燃油消耗量可表示為車速v和負(fù)載f的函數(shù)，如式(4)所示。

F(v,M)=λ(sNV+wγαv+γαfv+βγv3)d/v

(4)

車輛的運(yùn)輸成本與燃油消耗量成正比，比例系數(shù)為單位燃油與CO2排放量的成本。

1.4 CO2排放量計(jì)算

根據(jù)聯(lián)合國政府間氣候變化專門委員會(huì)(Intergovernmental Panel on Climate Change,IPCC)碳排放計(jì)算指南[18]推薦的燃油碳排放因子及參數(shù)值，采用式(5)計(jì)算每升柴油、汽油的CO2排放量V(CO2)，kg/L。

(5)

式(5)中：ψ為柴油/汽油的碳排放因子，由IPCC指南查得分別為20.2 kg/GJ、18.9 kg/GJ；H為柴油/汽油的熱值，kJ/g；ρ為柴油/汽油的密度，g/mL；M為CO2的摩爾質(zhì)量，取44；m為CO2中碳元素的摩爾質(zhì)量，取12。

經(jīng)計(jì)算，每升柴油、汽油的CO2排放量分別為2.74 kg/L、2.47 kg/L。

1.5 建立模型

建立2E-OLCLRP-WF模型如下：

(6)

式(6)表示最小化第一層和第二層的運(yùn)輸成本、第一層和第二層車輛固定成本以及配送中心開放成本之和。

(7)

(8)

(9)

(10)

(11)

(12)

Uijk≤Q1Xijk, ?i∈Vp,j∈Vp,k∈K1,i≠j

(13)

(14)

(15)

(16)

(17)

(18)

Xijk≤Rij, ?i,j∈Vp,k∈K1

(19)

約束(7)～約束(19)與第一階段相關(guān)。約束(7)表示開放的配送中心由一輛第一層的車輛服務(wù)，未開放的配送中心無車輛服務(wù)。約束(8)表示每個(gè)客戶均只由一個(gè)配送中心服務(wù)。約束(9)表示分配給開放的配送中心的客戶總需求不超過該配送中心的最大容量。約束(10)表示從倉庫出發(fā)的第一層車輛全部終止于配送中心，而不回到倉庫。約束(11)表示開放的配送中心至多是一輛第一層車輛的終點(diǎn)配送中心，未開放的配送中心不能作為終點(diǎn)配送中心。約束(12)表示開放的配送中心至少服務(wù)一個(gè)客戶點(diǎn)。約束(13)為第一層的車容量約束。約束(14)表示從倉庫運(yùn)出的總貨物量等于客戶的總需求。約束(15)和約束(16)為第一層的車流量平衡約束。約束(17)和約束(18)為第一層的貨流量平衡約束。約束(19)表示兩點(diǎn)間存在直達(dá)道路，車輛才能直接到達(dá)；若不存在直達(dá)道路，則需要經(jīng)過交叉口。

(20)

(21)

(22)

(23)

(24)

Lijk≤Q2Yijk, ?i,j∈Vp,i≠j,k∈K2

(25)

(26)

(27)

(28)

Yijk≤Rij, ?i,j∈Vp,k∈K2

(29)

約束(20)～約束(29)與第二階段相關(guān)。約束(20)表示每個(gè)客戶點(diǎn)有且僅有一輛第二層的車輛到達(dá)。約束(21)表示第二層車輛的起點(diǎn)必須是配送中心。約束(22)表示被使用的第二層的車輛全部終止于客戶點(diǎn)。約束(23)和(24)為第二層的車流量平衡約束。約束(25)為第二層的車容量約束。約束(26)表示從某一配送中心配送的貨物總量等于該配送中心服務(wù)的客戶的總需求量。約束(27)和(28)是第二層的貨流量平衡約束。約束(29)表示兩點(diǎn)間存在直達(dá)道路，車輛才能直接到達(dá)；若不存在直達(dá)道路，則需要經(jīng)過交叉口。

vmax≤vij≤vmin, ?i,j∈Vp

(30)

約束(30)表示兩層車輛的速度均不超過最高速度，且不低于最低速度。

為進(jìn)行對比，以驗(yàn)證2E-OLCLRP-WF模型的優(yōu)越性，在文獻(xiàn)[15]中，2E-OLRP模型的總成本中考慮燃油消耗和CO2排放成本，建立2E-OLCLRP模型，其總成本(目標(biāo))函數(shù)見式(31)。式(31)表示最小化第一層、第二層的運(yùn)輸成本和車輛固定成本，以及配送中心開放成本之和。該模型的約束與文獻(xiàn)[15]中約束相同。

(31)

2 案例計(jì)算

采用某市部分路網(wǎng)作為案例，該路網(wǎng)及倉庫、配送中心、客戶點(diǎn)和交叉口位置如圖3所示。其中包括：一個(gè)倉庫(1)、3個(gè)配送中心(2～4)、6個(gè)客戶點(diǎn)(5～10)和29個(gè)交叉口(11～39)，各點(diǎn)的相關(guān)參數(shù)如表1所示。通過谷歌地圖獲得各點(diǎn)間距離及速度，其中速度為一天時(shí)間段內(nèi)的平均速度。

圖3 城市交通網(wǎng)絡(luò)圖Fig.3 The city traffic network in case

表1 實(shí)例參數(shù)Table 1 The case parameters

與燃油消耗和CO2排放相關(guān)的車輛參數(shù)取值如表2所示。參考城市實(shí)際物流配送車型，第一層車輛選用柴油車，第二層車輛選用汽油車。

為得到2E-OLCLRP模型中倉庫、配送中心和客戶各點(diǎn)間的最短路徑及其距離，根據(jù)表1數(shù)據(jù)與圖3，利用Dijkstra算法編程求解，所得最短路徑(距離)如表3所示。

表3中第一行(列)表示倉庫(1)、配送中心(2～4)和客戶點(diǎn)(5～10)。例如：第二行、第三列表示點(diǎn)1到點(diǎn)2的最短路徑為：1-23-24-5-25-19-20-2，括號(hào)內(nèi)的數(shù)值表示最短距離為66 600 m。倉庫、配送中心、客戶點(diǎn)各點(diǎn)間的速度為兩點(diǎn)間最短路徑上的平均速度。

3 結(jié)果分析

將2E-OLCLRP-WF模型利用精確求解器CPLEX對算例進(jìn)行求解，得到總成本為9 298.25元，其中運(yùn)輸成本298.25元；編程求得CO2排放量為63.04 kg。求解信息如表4和圖4所示。最優(yōu)路徑如圖5所示，第一層的車輛路徑由實(shí)線箭頭表示，由一輛第一層的車輛完成運(yùn)輸任務(wù)；第二層的車輛路徑由虛線箭頭表示，其運(yùn)輸任務(wù)由兩輛第二層的車輛完成。

為求解2E-OLCLRP模型，將本文案例當(dāng)作1個(gè)倉庫、3個(gè)配送中心和6個(gè)客戶點(diǎn)的配送網(wǎng)絡(luò)。根據(jù)表3中各點(diǎn)間的最短路徑，利用燃油消耗函數(shù)式(4)計(jì)算各點(diǎn)間的運(yùn)輸成本(燃油消耗量×單位燃油及其CO2排放成本)，并以式(31)為目標(biāo)函數(shù)求解2E-OLRP模型，所得2E-OLCLRP問題模型的最優(yōu)路徑如圖6所示。圖6配送方案的總成本為9 316.81元，其中運(yùn)輸成本為316.81元，CO2排放量為67.05 kg。

求解結(jié)果表明，與2E-OLCLRP問題模型相比，2E-OLCLRP-WF模型總成本節(jié)約0.20%，其中，節(jié)約運(yùn)輸成本5.86%，減少CO2排放5.98%。證明了本文所提出的模型在節(jié)能減排方面的優(yōu)越性。

表2 車輛相關(guān)參數(shù)Table 2 Parameters and values relating to vehicle

表3 最短路徑(距離)Table 3 The shortest path (distance)

表4 CPLEX求解信息Table 4 The solving information of CPLEX

圖4 CPLEX求解時(shí)間Fig.4 The solving time of CPLEX

圖5 2E-OLCLRP-WF模型的最優(yōu)路徑Fig.5 Optimal paths of 2E-OLCLRP-WF model

圖6 2E-OLCLRP模型最優(yōu)路徑Fig.6 Optimal paths of 2E-OLCLRP model

由圖6可知，與圖5中的最優(yōu)路徑相比，圖6中第二層車輛的路徑發(fā)生了較大變化，但選擇開放的配送中心未發(fā)生變化，這主要是由于本文案例中客戶點(diǎn)的規(guī)模較小，而配送中心的開放成本較大，各點(diǎn)間路徑的靈活選擇所導(dǎo)致的總成本的變化較小，不足以影響開放配送中心的決策。

4 結(jié)論

針對城市配送客戶多、范圍廣、路徑可替代性強(qiáng)等特點(diǎn)，考慮路徑靈活性，同時(shí)考慮燃油消耗和CO2排放成本，建立以最小化總成本為目標(biāo)的城市網(wǎng)絡(luò)配送模型。為驗(yàn)證模型的優(yōu)越性，基于城市路網(wǎng)圖，利用精確求解器CPLEX對所建立的2E-OLCLRP-WF模型和2E-OLCLRP模型進(jìn)行求解，并將兩種模型的最優(yōu)路徑進(jìn)行對比分析。結(jié)果表明：①城市交通網(wǎng)絡(luò)運(yùn)輸配送的路徑?jīng)Q策具有較高的靈活性；②與2E-OLCLRP模型相比，2E-OLCLRP-WF模型能節(jié)約運(yùn)輸成本并減少CO2排放；③在小規(guī)模數(shù)據(jù)下，考慮路徑靈活性對總成本影響較小，但在節(jié)能減排方面仍具有較大的優(yōu)越性。研究結(jié)果可為城市網(wǎng)絡(luò)中物流配送的路徑規(guī)劃提供理論支持。

未來的研究可以從以下幾個(gè)方面入手：①開發(fā)啟發(fā)式算法求解大規(guī)模的2E-OLCLRP-WF問題；②考慮更接近實(shí)際配送情形的因素，如時(shí)間窗約束等；③考慮顧客需求不確定性等因素。