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

劉成清，胡大偉，黃 榕

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

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

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

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

1 模型建立

1.1 問題描述

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

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

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

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

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

1.2 參數定義與模型假設

假設1：在1 d的時間段內進行配送規劃。

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

1.3 運輸成本計算

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

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

(1)

式(1)中：ξ為空燃比；s為發動機的摩擦系數，kJ/(rad·L)；N為發動機轉速，rad/s；V為發動機排量，L；η和κ為常數；P為發動機輸出的功率，kW，可由式(2)計算。

P=Ptract/ηtf

(2)

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

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

(3)

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

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

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

(4)

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

1.4 CO2排放量計算

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

(5)

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

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

1.5 建立模型

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

(6)

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

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

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

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

(30)

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

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

(31)

2 案例計算

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

圖3 城市交通網絡圖Fig.3 The city traffic network in case

表1 實例參數Table 1 The case parameters

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

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

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

3 結果分析

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

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

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

表2 車輛相關參數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求解時間Fig.4 The solving time of CPLEX

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

圖6 2E-OLCLRP模型最優路徑Fig.6 Optimal paths of 2E-OLCLRP model

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

4 結論

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

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