考慮道路坡度影響的多約束冷鏈配送問題研究

閔德權，孫曉娜，李宇航，江可鑒

綠色包裝與循環經濟

考慮道路坡度影響的多約束冷鏈配送問題研究

閔德權，孫曉娜，李宇航，江可鑒

（大連海事大學 交通運輸工程學院，遼寧 大連 116026）

為改進傳統冷鏈VRP將配送區域默認為二維平面，使得實際調度與理想狀態產生差異而造成配送成本增加的問題，本文對相關問題進行深入研究，旨在合理規劃資源配置，提升企業經濟效益。通過引入坡度函數對油耗成本和碳排放成本進行計算，綜合考慮三維空間位置、多車型、載質量變化、客戶取送貨需求和時間窗要求等多種現實約束，并提出一種基于K–means多維時空聚類的改進遺傳算法進行求解。求解結果表明，若最初將道路坡度考慮在成本計算內，可有效降低9.58%的配送成本。同時，應避免大型車輛在重載時突然發生海拔變化。當發生海拔變化時，大型車輛可在卸載一部分貨物后改變至更高的高度。本文研究的模型更加貼近實際路網，具有更高的適用性，特別是對有明顯道路坡度城市的冷鏈品的配送具有現實的借鑒意義。

道路坡度；多約束；冷鏈配送；K–means多維時空聚類；改進的遺傳算法

隨著生鮮電商崛起、人工智能、大數據、物聯網等技術的爆發，冷鏈物流產業得以迅速發展，其中“最后一公里”的配送已成為冷鏈物流市場普遍反映的最大問題[1]。“最后一公里”是指通過一輛冷鏈車將貨物從配送中心運送至客戶點的過程，研究發現，“最后一公里”配送成本已成為供應鏈網絡中最昂貴的部分，可占到總運輸過程的28%[2]。因此如何建立符合實際和適合城市特點的數學模型，以更高效運輸和降低成本是冷鏈中心必須解決的問題。

為解決制約生鮮電商“最后一公里”發展的瓶頸，眾多學者已將如何最小化配送成本作為優化目標，其中油耗成本作為主要的成本因素，其不僅與車輛的速度、距離、載值量和燃料類型有關，道路坡度也會對成本造成較大的影響[3]。現階段，學者們對車輛油耗成本和碳排放成本的研究仍專注于速度、距離、載質量的變化。Zhang等[4]考慮了載質量的變化對燃油消耗的影響，利用改進的禁忌搜索算法求解了最小化成本的數學模型；康凱等[5]認為距離和載質量會影響成本，并采用改進的蟻群算法進行求解；狄衛民等[6]考慮車速、距離和載質量對油耗成本的影響，并設計頭腦風暴優化算法進行求解；劉長石等[7]在時變路網考慮了車速、載質量和行駛距離對成本的影響，并設計了一種改進的蟻群算法進行求解。

以上文獻都是將配送區域假設在二維平面上，忽視了節點間不對稱這一事實，使得最優求解方案在實際調度中與理想化狀態產生差異，造成因車輛路徑規劃錯誤而導致配送過程中額外成本的增加。Joubert等[8]為證實道路坡度在燃油消耗過程中起著重要作用，模擬了一個道路坡度在[?8°, 8°]內變化的場景，為重型車輛選擇路徑提供了必要的依據；Lajevardi等[9]提出將路面坡度剖面與給定速度和時間相匹配的方法，并在加拿大的大不列顛哥倫比亞省進行了驗證；Ritter等[10]提出了一種基于道路坡度和車輛質量的估計理論分析，并在實驗驗證方面證實了其模型的實用性；Brunner等[11]構建了考慮道路等級信息和車載質量對油耗成本影響的模型，稱其為陡峭道路VRP(VRP–SR)模型，并通過啟發式算法求解。

通過對以往文獻的整理與分析發現，現階段文獻仍有如下不足。

1）現有多數文獻都將配送區域理想在二維平面上，忽視了道路坡度對車輛油耗和碳排放的影響，導致研究成果與實際調度產生較大差距，停留在理論層面。

2）針對多車型的行駛路線和車型選擇的研究中，現有文獻忽視了道路坡度對車輛分配的影響，主要體現在大型車輛雖會提升滿載率，但過度爬坡會造成額外成本的增加，而小型車輛單位費用較高，如若考慮道路坡度只選擇小型車輛也不現實。

3）針對MDOVRP的求解方法上，通過聚類和啟發式2種算法結合已被廣泛證明并應用，但已有文獻的聚類方法大多采用二維空間上的任意2點間的歐式距離作為劃分聚類簇的依據，忽略了節點間的不對稱性問題，而導致聚類結果不全面。

綜上，針對上述現有文獻的不足，本文通過引入坡度函數對油耗成本和碳排放成本進行計算，綜合考慮三維空間位置、多車型、載質量變化、客戶取送貨需求和時間窗要求等多種現實約束研究冷鏈產品的配送問題，并設計一種基于K–means多維時空聚類的改進遺傳算法進行求解。這一研究旨在對有明顯道路不對稱性城市的生鮮品配送提供現實的借鑒意義，如我國的重慶、大連等地區。

1 問題描述與假設

1.1 問題描述

本文研究問題可描述如下：某一區域內有實行聯合配送的多家冷鏈中心，車輛自某一中心出發，在多約束下完成指定的取送貨任務，完成后車輛按就近原則返回任意配送中心。在此過程中，綜合考慮道路坡度的影響，主要體現在對油耗成本、碳排放成本的影響和車輛安排的選擇上，旨在為車輛規劃合理的路徑，使企業物流成本最低。

1.2 模型假設

針對本文研究問題，為方便建模，假設條件如下：

1）配送中心及客戶點位置已知，且中心擁有不同車型車輛。

2）不考慮配送車輛中途返回配送中心，配送車輛自出發直至返回配送中心即為一次服務完成。

3）客戶的時間窗和取送貨量信息均已知。

4）節點位于不同的高度，即車輛在節點間行駛時需考慮坡度影響。

5）客戶取送貨需求不可拆分，即每個客戶只允許一輛配送車為其進行配貨和取貨服務，且服務總量應在配送車輛的最大載質量以內。

1.3 參數說明

2 模型構建

2.1 道路坡度的影響

道路坡度定義為高程變化與水平距離的比值[12]，準確的道路坡度是現實路網中不可忽視的一個重要因素，在許多方面可以促進與交通相關的研究，但在研究分析中通常會被忽略，導致車輛在燃油經濟性和污染排放中的研究不夠全面。研究表明，車輛總質量和道路坡度是影響車輛動力系統的2個重要因素。隨著道路坡度的增加，燃油消耗和尾氣排放都在增加，就平均而言，與平坦路面相比，在坡度等級為1%的路面上油耗增加了15%，而在坡度等級為6%的路面上油耗大約增加了1倍。在觀察完整路線時，研究發現，與平坦路線相比，丘陵路線的消耗增加了15%～20%。同時車輛質量的改變，油耗成本也會改變10%左右。因此路線的選擇是車輛類型和道路坡度的共同作用[11]。本文通過引入坡度函數[13]以考慮高度變化對油耗成本的影響，公式見式（1）。

2.2 成本分析

1）油耗成本。在現實路網中，道路不可能總是處在同一高度上，因此導致了配送網絡具有不對稱的特征。本文在油耗模型中引入坡度函數，采用Brunner等[11]提出的改進的車輛油耗模型，具體如下：其認為單位時間的燃料消耗函數可近似表示為式（2）。

后者產生的碳排放量近似看作與時間呈正線性相關[14]，見式（7）。

式中：為制冷設備消耗每單位體積油耗時產生的碳排放量。為排放每單位體積二氧化碳需要支付的碳稅，則碳排放成本見式（8）。

3）貨損成本。不論道路坡度如何變化，本文運輸的生鮮產品的貨損都是不可避免且不可逆的，且其只與時間相關，參考文獻[15]有：

前者為運輸過程中造成的貨損成本，后者為卸貨過程中造成的貨損成本。

2.3 數學模型

目標函數：

約束條件：

目標函數依次為車輛使用成本、油耗成本、碳排放成本、貨損成本及時間懲罰成本。式（11）表示車輛行駛距離不超過其自身最大行駛距離的限制；式（12）表示不允許車輛在各配送中心之間直接行駛；式（13）表示車輛最終停留在配送中心；式（14）表示節點處車輛進出平衡，即車輛到達客戶點服務完成后必須從客戶點處離開；式（15）表示客戶取送貨需求不可拆分，每個客戶點只能由類型的車輛進行服務；式（16）表示配送區域內的客戶都被訪問到且僅訪問一次；式（17）表示車輛在訪問后的裝載量仍不能超過車最大載質量限制；式（18）表示車輛必須在客戶最大限度接受服務時間窗內進行配送任務；式（19）表示消除子回路；式（20）—（22）表示決策變量取值范圍。

3 算法設計

本文研究的問題是VRP變種問題，文中所構建的模型是在傳統VRP模型的基礎上進行的擴展和延伸，因此其求解原理與方法是一致的，屬于NP–Hard問題。啟發式算法在求解這類問題時具有明顯的優越性，遺傳算法具有魯棒性強、并行性高和搜索能力強的特點，但收斂速度慢且容易陷入局部最優，不能保證整體最優[16]。為改進該缺陷，本文設計了一種改進的遺傳算法對模型進行求解，并在此基礎上采用時空相似測度對節點進行分組和聚類，從而提高初始種群的質量，更好地提升算法的求解效率。綜上，本文通過結合模型特點設計了一種基于K–means多維時空聚類的改進遺傳算法并對其進行求解。

3.1 K–means多維時空聚類算法

3.2 基于K–means多維時空聚類的改進遺傳算法

1）初始種群的產生。首先用式（24）對全客戶進行聚類簇劃分，每個聚類簇的初始路徑構造步驟如圖1所示。

2）適應度函數。本文是求解配送成本最小化的問題，因此將目標函數的倒數作為適應度函數。

3）交叉、變異操作。本文選擇改進的雙切點交叉方法作為交叉算子，兩點互換法作為變異算子。與傳統兩點交叉法不同的是將互換的基因序列放到對方個體的最前方，并依次刪除原個體中與互換后的交叉區域內相同的基因。

4）進化逆轉操作。為提高算法的局部搜索能力，在交叉、變異操作后引入連續多次的進化逆轉操作，但該操作只能朝著目標值更優的方向進行。

5）2–OPT順序擾動策略。為避免算法早熟而陷入局部最優解，本文引入順序擾動策略，對當前的不同線路的解進行拆分重構。若不符合多約束要求，則重新進行擾動操作，直至滿足約束要求，如圖2所示。

圖1 初始種群生成步驟

圖2 2–OPT順序擾動操作

4 算例驗證與結果分析

4.1 算例描述

本文采用文獻[17]的方法生成算例，共有3家冷鏈中心為52名客戶進行服務，有A1，A22種車型可指派，載質量分別為3 000、5 000 kg，發車費用分別為300、400元。其余各車輛配置均統一。此外，其余部分數據參考表1。

算法采用Matlab2022b進行實驗，并在操作系統為Windows10、電腦內存為8GB、CPU為Inter(R)Core (TM)i5–6200U、主頻率為2.30GHz的電腦上實現。經測試，算法參數設置如下：種群規模為100、最大迭代次數為300、交叉概率為0.5、變異概率為0.03。

4.2 結果分析

本文采用基于K–means多維時空聚類的改進遺傳算法對4.1節中的算例進行求解。為使結果穩定，算法運行10次，平均運行時間為73.63 s。從表2可知，其最優配送方案總花費為20 228.3元，使用配送車輛6輛；最差配送方案總花費21 539.7元，使用配送車輛7輛；10次運行結果平均值為20 885.3元，最優解偏差為2.99%，最差解偏差為3.04%。圖3是最優配送方案的迭代趨勢，可以看出，本研究中使用的方法能夠穩定地收斂到最優解，且求解運行時間可接受。

表1 參數設置

Tab.1 Parameter setting

表2 算例求解結果

Tab.2 Solution result of numerical example

圖3 最優配送結果迭代

圖4a是表1中最優配送方案的車輛行駛路徑圖，其俯視圖如圖4b所示。表3列舉了圖4b對應的車輛行駛最優路徑。

4.3 對比分析

為驗證道路坡度對配送路徑和車型選擇的影響，本研究將道路坡度前期考慮在成本計算中和后期加入成本計算中進行對比分析，并引入新型冷藏車A3。A3的載質量為8 000 kg，發車費用為500元，其余配置與前文統一。前者計算方法與前文一致，后者計算方法如下：首先采用上述算法求解出該算例在同一高度即對稱下的配送方案并記錄，然后將該方案不變，通過計算得出其在不同高度下即非對稱下的成本。為使結果穩定，算法運行10次，結果如表4所示。

圖4 車輛行駛最優路徑

表3 最優配送方案路線

Tab.3 Route of optimal distribution scheme

由表4可知，前期將道路坡度考慮在成本計算中（即非對稱下），最佳配送方案總成本為21 603.1元，最優配送方案如表5所示，其平均配送成本為22 109.7元；而在后期將道路坡度加到成本計算中（即對稱下），最優配送方案總成本為23 761.4元，最優配送方案如表5所示，其平均配送成本為24 583.2元。對比可知，配送成本平均降低了9.58%。

綜合表4、表5可以得出，非對稱情況下配送方案更傾向于安排A1、A2車型的選擇，而較少安排A3車型的派發，其目的是減少大型車輛因頻繁爬坡而造成的額外成本增加。但對稱情況下不存在此目的，因此更傾向于將大型車輛參與到派送中。成本的增加在一定程度上說明了模型的不適用性，特別是針對一些山地城市，若長期采用此類模型，不僅會造成短期的效益低下，而且不利于企業的長期發展。綜上，將道路坡度直接考慮在模型內的求解調度方案，對企業在現實路網中的配送路線和車輛類型的選擇有更大的幫助，其可有效降低配送成本，是物流中心降低營運成本的重要改進措施。

表4 運行10次的算例結果

Tab.4 Results of numerical examples running for 10 times

表5 非對稱與對稱下的最優配送方案路線

Tab.5 Route of optimal distribution scheme under asymmetry and symmetry

5 結語

針對目前冷鏈物流研究所存在因缺少考慮實際路網的道路坡度而造成配送方案在城市實際調度中增加成本和車輛安排不合理等問題，本文在考慮道路坡度對油耗、碳排放和車輛行駛路徑影響的基礎上，綜合考慮了多中心開放、多車型、客戶具備取送貨需求及軟時間窗等多種現實約束。建立了以配送總成本最小為目標的優化模型，并設計了一種基于K–means多維時空聚類的改進遺傳算法對模型進行研究和求解。結果表明，若冷鏈中心將道路坡度作為一個影響成本的因素考慮在車輛路徑安排和車型選擇時，其能夠采用更加符合現實路網和城市特點的模型，從而有效降低冷鏈中心的配送成本，也可有效避免大型車輛安排不合理的現象即減少大型車輛在過度爬坡中造成的油耗浪費和對環境的污染。同時，在配送路線的選擇上，也對大型車輛在重載時的行駛路線給出建議，即應減少其在行駛過程中海拔的突然變化，可選擇在卸載一部分貨物后改變至更高的高度。

本文豐富了現有的冷鏈產品配送模型，為建立更加貼合實際調度的路徑規劃提供了理論基礎和實踐指導，并對有明顯道路坡度的城市，如我國的重慶、大連等地區的冷鏈產品配送提供了現實的借鑒意義。未來在研究道路坡度影響冷鏈配送問題中，在模型方面，可將建立更加準確的坡度函數模型、更加細致地劃分節點間路徑狀況作為研究內容，以便模型能更貼合實際調度應用。

[1] 宋寒業. 冷鏈物流成行業新風口[N]. 中華工商時報, 2021, 15(004).

SONG Han-ye. Cold Chain Logistics Has Become a New Wind in the Industry[N]. China Business Times, 2021, 15(004).

[2] HOCHFELDER B. What Retailers can do to Make the Last Mile More Efficient[N/OL]. Supply Chain News And Analysis, 2017-05-22.https://www.supplychaindive. com

[3] PSYCHAS I D, MARINAKI M, MARINAKIS Y, et al. Non-Dominated Sorting Differential Evolution Algorithm for the Minimization of Route Based Fuel Consumption Multi-Objective Vehicle Routing Problems[J]. Energy Systems, 2017, 8: 785-814.

[4] ZHANG Jiang-hua, ZHAO Ying-xue, XUE Wei-li, et al. Vehicle Routing Problem with Fuel Consumption and Carbon Emission[J]. International Journal of Production Economics, 2015, 170: 234-242.

[5] 康凱, 韓杰, 普瑋, 等. 生鮮農產品冷鏈物流低碳配送路徑優化研究[J]. 計算機工程與應用, 2019, 55(2): 259-265.

KANG Kai, HAN Jie, PU Wei, et al. Optimization Research on ColdChain Distribution RoutesConsideringCarbonEmissionsfor Fresh Agricultural Products[J]. Computer Engineering and Applications, 2019, 55(2): 259-265.

[6] 狄衛民, 杜慧莉, 張鵬閣. 考慮動態擁堵的多車型綠色車輛路徑問題優化[J]. 計算機工程與設計, 2021, 42(9): 2614-2620.

DI Wei-min, DU Hui-li, ZHANG Peng-ge. Optimization of MultiVehicle Green Vehicle Routing Problem Considering Dynamic Congestion[J].Computer Engineering and Design, 2021, 42(9): 2614-2620.

[7] 劉長石, 王松, 羅亮, 鄧勝前. 時變路網條件下聯合配送的開放式車輛路徑問題[J]. 運籌與管理, 2021, 30(11): 26-33.

LIU Chang-shi, WANG Song, LUO Liang, et al. Open Vehicle Routing Problem for Joint Distribution under Time-VaryingRoad Network[J]. Operations Research and Management, 2021, 30(11): 26-33.

[8] JOUBERT J W. Multi-Agent Model of Route Choice When Vehicles are Sensitive to Road Grade[J]. Procedia Computer Science, 2017, 109: 869-874.

[9] LAJEVARDI S M, AXSEN J, CRAWFORD C. Examining the Role of Natural Gas and Advanced Vehicle Technologies in Mitigating CO2Emissions of Heavy- Duty Trucks: Modeling Prototypical British Columbia Routes with Road Grades[J]. Transportation Research Part D: Transport and Environment, 2018, 62: 186-211.

[10] RITTER A, WIDMER F, VETTERLI B, et al. Optimization-Based Online Estimation of Vehicle Mass and Road Grade: Theoretical Analysis and Experimental Validation[J]. Mechatronics, 2021, 80: 1-10.

[11] BRUNNER C, GIESEN R, KLAPP M A, et al. Vehicle Routing Problem with Steep Roads[J]. Transportation Research Part A: Policy and Practice, 2021, 151(6): 1-17.

[12] FAN Peng-fei, SONG Guo-hua, ZHU Zi-jun, et al. Road Grade Estimation Based on Large-Scale Fuel Consumption Data of Connected Vehicles[J]. Transportation Research Part D: Transport and Environment, 2022, 106: 103262.

[13] 饒衛振, 金淳, 王新華, 等. 考慮道路坡度因素的低碳VRP問題模型與求解策略[J]. 系統工程理論與實踐, 2014, 34(8): 2092-2105.

RAO Wei-zhen, JIN Chun, WANG Xin-hua, et al. A Model of Low-Carbon Vehicle Routing Problem Considering Road Gradient and Its Solving Strategy[J]. SystemsEngineering-Theory & Practice, 2014, 34(8): 2092-2105.

[14] 肖智豪, 胡志華, 朱琳. 求解冷鏈物流時間依賴型車輛路徑問題的混合自適應大鄰域搜索算法[J]. 計算機應用, 2022, 42(9): 2926-2935.

XIAO Zhi-hao, HU Zhi-hua, ZHU Lin. A Hybrid Adaptive Large Neighborhood Search Algorithm for TimeDependent Vehicle Routing Problem in Cold Chain Logistics[J]. Computer Application, 2022, 42(9): 2926-2935.

[15] WANG X, WANG M, RUAN J, et al. The Multi-Objective Optimization for Perishable Food Distribution Route Considering Temporal-Spatial Distance[J]. Procedia Computer Science, 2016, 96: 1211-1220.

[16] 范厚明, 田攀俊, 呂迎春, 等. 時變路網下考慮時空距離的同時配集貨車輛路徑優化[J]. 系統管理學報, 2022, 31(1): 16-26.

FAN Hou-ming, TIAN Pan-jun, LYU Ying-chun, et al. Vehicle Routing Problem with Simultaneous Delivery and Pickup Considering Temporal-Spatial Distance in Time- Dependent Road Network[J]. Journal of Systems & Management, 2022, 31(1): 16-26.

[17] ZHOU J, LEE M. A Lagrangian Relaxation-Based Solution Method for a Green Vehicle Routing Problem to Minimize Greenhouse Gas Emissions[J]. Sustainability, 2017, 9: 776.

Research on Multi Constraint Cold Chain Distribution Problem Considering the Effect of Road Slope

MIN De-quan, SUN Xiao-na, LI Yu-hang, JIANG Ke-jian

(College of Transportation Engineering, Dalian Maritime University, Liaoning Dalian 116026, China)

In order to solve the problem that the traditional cold chain VRP defaults the distribution area to a two-dimensional plane, which makes the actual scheduling different from the ideal state and causes the distribution cost to increase, the work aims to make an in-depth research on related problems, aiming at rationally planning the allocation of resources and improving the economic benefits of enterprises. The fuel consumption cost and carbon emission cost were calculated by introducing the slope function, and various realistic constraints such as three-dimensional space location, multiple models, load changes, customer's pickup and delivery requirements, and time window requirements were comprehensively considered. The improved genetic algorithm of K-means multi-dimensional spatiotemporal clustering was solved. The solution results indicated that if the road slope was initially considered in the cost calculation, the distribution cost could be effectively reduced by 9.58%. At the same time, large vehicles should avoid sudden altitude changes when heavily loaded. When the altitude changed, large vehicles could change to a higher altitude after some goods were unloaded. The model studied is closer to the actual road network and has higher applicability, especially for the distribution of cold chain products in cities with obvious road slopes, which has practical reference significance.

road slope; multi constraint; cold chain distribution; K-means multi-dimensional spatiotemporal clustering; improved genetic algorithm

TB485.3；U492.2+2

A

1001-3563(2023)13-0236-09

10.19554/j.cnki.1001-3563.2023.13.028

2022?11?25

國家社科基金（18VHQ005）

閔德權（1963—），男，碩士，教授，主要研究方向為旅游管理、交通運輸規劃與管理。

責任編輯：曾鈺嬋