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

閔德權(quán)，孫曉娜，李宇航，江可鑒

綠色包裝與循環(huán)經(jīng)濟(jì)

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

閔德權(quán)，孫曉娜，李宇航，江可鑒

（大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116026）

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

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

隨著生鮮電商崛起、人工智能、大數(shù)據(jù)、物聯(lián)網(wǎng)等技術(shù)的爆發(fā)，冷鏈物流產(chǎn)業(yè)得以迅速發(fā)展，其中“最后一公里”的配送已成為冷鏈物流市場普遍反映的最大問題[1]?！白詈笠还铩笔侵竿ㄟ^一輛冷鏈車將貨物從配送中心運(yùn)送至客戶點(diǎn)的過程，研究發(fā)現(xiàn)，“最后一公里”配送成本已成為供應(yīng)鏈網(wǎng)絡(luò)中最昂貴的部分，可占到總運(yùn)輸過程的28%[2]。因此如何建立符合實(shí)際和適合城市特點(diǎn)的數(shù)學(xué)模型，以更高效運(yùn)輸和降低成本是冷鏈中心必須解決的問題。

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

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

通過對以往文獻(xiàn)的整理與分析發(fā)現(xiàn)，現(xiàn)階段文獻(xiàn)仍有如下不足。

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

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

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

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

1 問題描述與假設(shè)

1.1 問題描述

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

1.2 模型假設(shè)

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

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

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

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

4）節(jié)點(diǎn)位于不同的高度，即車輛在節(jié)點(diǎn)間行駛時需考慮坡度影響。

5）客戶取送貨需求不可拆分，即每個客戶只允許一輛配送車為其進(jìn)行配貨和取貨服務(wù)，且服務(wù)總量應(yīng)在配送車輛的最大載質(zhì)量以內(nèi)。

1.3 參數(shù)說明

2 模型構(gòu)建

2.1 道路坡度的影響

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

2.2 成本分析

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

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

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

3）貨損成本。不論道路坡度如何變化，本文運(yùn)輸?shù)纳r產(chǎn)品的貨損都是不可避免且不可逆的，且其只與時間相關(guān)，參考文獻(xiàn)[15]有：

前者為運(yùn)輸過程中造成的貨損成本，后者為卸貨過程中造成的貨損成本。

2.3 數(shù)學(xué)模型

目標(biāo)函數(shù)：

約束條件：

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

3 算法設(shè)計

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

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

3.2 基于K–means多維時空聚類的改進(jìn)遺傳算法

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

2）適應(yīng)度函數(shù)。本文是求解配送成本最小化的問題，因此將目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)。

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

4）進(jìn)化逆轉(zhuǎn)操作。為提高算法的局部搜索能力，在交叉、變異操作后引入連續(xù)多次的進(jìn)化逆轉(zhuǎn)操作，但該操作只能朝著目標(biāo)值更優(yōu)的方向進(jìn)行。

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

圖1 初始種群生成步驟

圖2 2–OPT順序擾動操作

4 算例驗(yàn)證與結(jié)果分析

4.1 算例描述

本文采用文獻(xiàn)[17]的方法生成算例，共有3家冷鏈中心為52名客戶進(jìn)行服務(wù)，有A1，A22種車型可指派，載質(zhì)量分別為3 000、5 000 kg，發(fā)車費(fèi)用分別為300、400元。其余各車輛配置均統(tǒng)一。此外，其余部分?jǐn)?shù)據(jù)參考表1。

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

4.2 結(jié)果分析

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

表1 參數(shù)設(shè)置

Tab.1 Parameter setting

表2 算例求解結(jié)果

Tab.2 Solution result of numerical example

圖3 最優(yōu)配送結(jié)果迭代

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

4.3 對比分析

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

圖4 車輛行駛最優(yōu)路徑

表3 最優(yōu)配送方案路線

Tab.3 Route of optimal distribution scheme

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

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

表4 運(yùn)行10次的算例結(jié)果

Tab.4 Results of numerical examples running for 10 times

表5 非對稱與對稱下的最優(yōu)配送方案路線

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

5 結(jié)語

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

本文豐富了現(xiàn)有的冷鏈產(chǎn)品配送模型，為建立更加貼合實(shí)際調(diào)度的路徑規(guī)劃提供了理論基礎(chǔ)和實(shí)踐指導(dǎo)，并對有明顯道路坡度的城市，如我國的重慶、大連等地區(qū)的冷鏈產(chǎn)品配送提供了現(xiàn)實(shí)的借鑒意義。未來在研究道路坡度影響冷鏈配送問題中，在模型方面，可將建立更加準(zhǔn)確的坡度函數(shù)模型、更加細(xì)致地劃分節(jié)點(diǎn)間路徑狀況作為研究內(nèi)容，以便模型能更貼合實(shí)際調(diào)度應(yīng)用。

[1] 宋寒業(yè). 冷鏈物流成行業(yè)新風(fēng)口[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] 康凱, 韓杰, 普瑋, 等. 生鮮農(nóng)產(chǎn)品冷鏈物流低碳配送路徑優(yōu)化研究[J]. 計算機(jī)工程與應(yīng)用, 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] 狄衛(wèi)民, 杜慧莉, 張鵬閣. 考慮動態(tài)擁堵的多車型綠色車輛路徑問題優(yōu)化[J]. 計算機(jī)工程與設(shè)計, 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] 劉長石, 王松, 羅亮, 鄧勝前. 時變路網(wǎng)條件下聯(lián)合配送的開放式車輛路徑問題[J]. 運(yùn)籌與管理, 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] 饒衛(wèi)振, 金淳, 王新華, 等. 考慮道路坡度因素的低碳VRP問題模型與求解策略[J]. 系統(tǒng)工程理論與實(shí)踐, 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] 肖智豪, 胡志華, 朱琳. 求解冷鏈物流時間依賴型車輛路徑問題的混合自適應(yīng)大鄰域搜索算法[J]. 計算機(jī)應(yīng)用, 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] 范厚明, 田攀俊, 呂迎春, 等. 時變路網(wǎng)下考慮時空距離的同時配集貨車輛路徑優(yōu)化[J]. 系統(tǒng)管理學(xué)報, 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）

閔德權(quán)（1963—），男，碩士，教授，主要研究方向?yàn)槁糜喂芾?、交通運(yùn)輸規(guī)劃與管理。

責(zé)任編輯：曾鈺嬋