考慮需求可拆分的多車型電動車路徑優(yōu)化研究

摘" 要：為降低J公司的物流配送成本，提高運(yùn)輸效率，提出考慮需求可拆分的多車型電動車路徑優(yōu)化方案，以車輛固定成本、能耗成本、時間窗懲罰成本和碳交易成本之和最小化為目標(biāo)建立優(yōu)化模型，并采用改進(jìn)的自適應(yīng)遺傳算法進(jìn)行求解，得到優(yōu)化后的配送方案。與優(yōu)化前同車型配送方案相比，總成本降低了8.4%，配送時長縮短了11.5%，有效地降低了企業(yè)的成本，提高了物流配送效率和客戶滿意度。

" 關(guān)鍵詞：物流配送；需求可拆分；多車型；電動車；改進(jìn)的自適應(yīng)遺傳算法

" 中圖分類號：U116.2" " 文獻(xiàn)標(biāo)志碼：A

DOI：10.13714/j.cnki.1002-3100.2025.05.005

Abstract： In order to reduce the logistics and distribution cost of company J and improve the transportation efficiency， an optimization scheme for multi-vehicle electric vehicle path considering the demand can be split is proposed， and the optimization model is established with the goal of minimizing the sum of vehicle fixed cost， energy consumption cost， time window penalty cost and carbon transaction cost， and the improved adaptive genetic algorithm is used to solve the optimized distribution scheme. Compared with the distribution scheme of the same model before optimization， the total cost has been reduced by 8.4%， and the delivery time has been shortened by 11.5%， which effectively reduces the cost of the enterprise and improves the logistics and distribution efficiency and customer satisfaction.

Key words： logistics and distribution; split demand; multi-vehicle; electric vehicle; improved adaptive genetic algorithm

0" 引" 言

" J公司為一家物流運(yùn)輸公司，業(yè)務(wù)主要聚焦于快消、服裝、家電家具、生鮮等產(chǎn)品的運(yùn)輸。目前，該公司所使用的配送方案為使用同一型號的電動車進(jìn)行配送，隨著公司業(yè)務(wù)的不斷擴(kuò)張，各個配送點(diǎn)的需求差異性較大且需求量也在增加，進(jìn)而導(dǎo)致該公司的運(yùn)營成本不斷增加，如何降低物流成本是J公司面臨的主要問題。

" 多車型車輛路徑問題是指使用多種不同類型的車輛進(jìn)行配送，不同類型車輛的固定成本、額定裝載量和續(xù)航里程等有所不同，它的目標(biāo)是根據(jù)任務(wù)要求對不同類型的車輛行駛路徑進(jìn)行優(yōu)化，使配送成本最小化或客戶滿意度最高等。目前已有諸多學(xué)者對該問題進(jìn)行了研究，初梁勇等[1]研究了異構(gòu)電動車隊在應(yīng)對客戶需求不確定性和時間窗要求時的路徑優(yōu)化問題，并針對電動車輛續(xù)航里程有限和配送途中充電等實際約束，構(gòu)建了一個以最小化配送總成本為目標(biāo)的優(yōu)化模型。夏揚(yáng)坤等[2]研究了一種帶客戶分級和需求可拆分的生鮮車輛路徑問題，需求可拆分為需求依背包拆分，是一種需求離散拆分的新類型，即每個客戶的生鮮需求量可由多個背包離散組合而成。王南星等[3]構(gòu)建以總運(yùn)輸成本最小為優(yōu)化目標(biāo)的時變綠色車輛路徑模型，根據(jù)模型特點(diǎn)改進(jìn)遺傳算法，并運(yùn)用大中小3種規(guī)模的算例對其進(jìn)行仿真實驗，驗證了模型和算法可以有效地降低物流配送成本。王偉權(quán)等[4]研究了線性可變充電策略下的多車型電動車輛路徑問題，提出了基于路徑的混合整數(shù)線性模型。

" 本文以車輛固定成本、能耗成本、時間窗懲罰成本和碳交易成本之和最小化為目標(biāo)建立考慮需求可拆分的多車型電動車路徑優(yōu)化模型，并采用改進(jìn)后的自適應(yīng)遺傳算法進(jìn)行求解，為企業(yè)提供物流配送方案參考。

1" 問題描述與模型建立

1.1" 問題描述

本文研究可描述為：物流企業(yè)擁有一個配送中心，且建有一支具有固定車輛數(shù)但載重、續(xù)航能力等不相同的多車型電動車隊，為N個帶有時間窗的客戶提供配送服務(wù)，車輛完成任務(wù)后要返回配送中心。配送過程中客戶的需求允許被拆分，可以由至少一輛車為其提供服務(wù)，拆分原則為將客戶點(diǎn)對單類產(chǎn)品的需求量視為一個不可拆分的“背包”，客戶的需求視為由多個背包離散組合而成。本文的研究目標(biāo)是在滿足約束條件的前提下，通過優(yōu)化車輛行駛路徑，實現(xiàn)車輛固定成本、能耗成本、時間窗懲罰成本和碳交易成本構(gòu)成的總成本最小化。

" 為了盡可能保障問題描述的合理性，現(xiàn)提出如下假設(shè)：（1）配送中心及客戶點(diǎn)位置已知，且客戶需求、時間窗已知；（2）電動車為異構(gòu)車型，車輛電池容量、裝載能力已知且不同；（3）車輛從配送中心出發(fā)，完成配送任務(wù)后返回配送中心；（4）電動車從配送中心出發(fā)時為滿電，續(xù)航里程可滿足配送要求，在途中不再充電；（5）每個客戶點(diǎn)的配送需求由至少一輛車滿足，每輛車最多為同一客戶點(diǎn)配送一次，客戶點(diǎn)處商品需求只能按照“背包”進(jìn)行拆分，某一類商品不能再按個數(shù)進(jìn)行拆分；（6）每輛車的載重量不能超過其最大載重量；（7）車輛需在時間窗內(nèi)到達(dá)客戶點(diǎn)，早到或晚到都會產(chǎn)生相應(yīng)的時間窗懲罰成本；（8）車輛行駛速度恒定，不考慮堵車等突發(fā)情況影響；（9）車輛產(chǎn)生的能耗成本與車輛載重和路徑長度成線性相關(guān)，車輛載重僅考慮商品卸載前后的重量變化；（10）車輛在客戶點(diǎn)服務(wù)期間，發(fā)動機(jī)關(guān)閉，不產(chǎn)生能耗。

1.2" 模型建立

式（1）為目標(biāo)函數(shù)，表示車輛固定成本、能耗成本、時間窗懲罰成本和碳交易成本組成的總配送成本最低；式（2）表示車輛從配送中心出發(fā)最后返回配送中心；式（3）表示客戶點(diǎn)車輛進(jìn)出平衡約束；式（4）表示每個客戶點(diǎn)至少被訪問一次；式（5）至式（8）表示客戶點(diǎn)的需求可拆分，但單個背包量不可再拆；式（9）表示所有客戶點(diǎn)的需求必須被滿足；式（10）表示車輛的裝載能力約束；式（11）表示車輛數(shù)量約束；式（12）表示車輛離開配送中心載重約束；式（13）表示車輛離開中間節(jié)點(diǎn)載重約束；式（14）表示車輛離開節(jié)點(diǎn)時間約束；式（15）表示車輛到達(dá)節(jié)點(diǎn)時間約束；式（16）表示車輛離開配送中心為滿電狀態(tài)；式（17）表示耗電量與車輛載重關(guān)系約束；式（18）表示車輛電池容量約束；式（19）至式（20）表示剩余電量約束；式（21）表示消除子循環(huán)約束；式（22）至式（24）表示變量取值約束。

2" 算法設(shè)計

本文所研究的問題為車輛路徑問題的延伸問題，屬于NP-hard問題，求解較為復(fù)雜，現(xiàn)有研究多采用啟發(fā)式算法進(jìn)行求解。遺傳算法是受自然進(jìn)化過程中“優(yōu)勝劣汰”的自然選擇機(jī)制和遺傳信息傳遞規(guī)律的啟發(fā)所提出的一種智能優(yōu)化算法，該算法可以應(yīng)用于多種問題的優(yōu)化，具有全局搜索能力強(qiáng)等優(yōu)點(diǎn)。本文對傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)，提出改進(jìn)的自適應(yīng)遺傳算法，改進(jìn)后算法的設(shè)計如下。

" （1）編碼與解碼

染色體采用實數(shù)編碼的方式。以一個具有N個客戶點(diǎn)，1個配送中心，且配送中心最多可派遣K輛車的問題為例。N個客戶點(diǎn)分別標(biāo)記為1、2、3、…、N-1、N，配送中心派遣的車輛使用同一編號，記為N+1，因此一個染色體所具有的基因個數(shù)為N+K，編號小于或等于N的基因代表的是客戶點(diǎn)，剩余的則代表配送中心派遣的車輛，染色體編碼如圖1所示。以一個代表車輛的基因為起點(diǎn)，下一個“車輛基因”為終點(diǎn)，取中間基因即為車輛路徑。

（2）計算種群適應(yīng)度

（3）選擇操作

" 為了保持解的多樣性，本文選擇操作采用二元錦標(biāo)賽選擇法，即在每一次錦標(biāo)賽中取出2個個體，并比較2個個體的適應(yīng)度值，保留適應(yīng)度值較高的個體。具體操作步驟如下：

" Step1：假設(shè)有n個個體，從中隨機(jī)選擇2個個體；

" Step2：比較2個個體的適應(yīng)度值，并保留適應(yīng)度值較高的個體；

" Step3：重復(fù)步驟1～2，直到選擇出有足夠個體數(shù)量的新種群。

" （4）交叉及變異操作

" 本文設(shè)計的交叉操作方式如圖2所示。

本文選擇的變異操作為逆轉(zhuǎn)變異操作，具體的變異方式如圖3所示。

3" 優(yōu)化效果評價

選取J公司某一天的配送數(shù)據(jù)作為評價對象，涉及客戶點(diǎn)數(shù)量為30個，客戶需求商品種類為39種，其余相關(guān)數(shù)據(jù)如表2所示。

將J公司配送數(shù)據(jù)代入，分別利用改進(jìn)后的遺傳算法和傳統(tǒng)的遺傳算法進(jìn)行求解，得到收斂圖如圖5所示，通過對比可以看出，改進(jìn)后的遺傳算法在種群進(jìn)化的前期尋優(yōu)能力較強(qiáng)，逐步收斂到最優(yōu)值，尋優(yōu)效果更好；跳出局部最優(yōu)陷阱的能力也更強(qiáng)。

利用改進(jìn)后的遺傳算法對本文模型進(jìn)行求解，得到路徑圖如圖6所示，得到優(yōu)化后的配送數(shù)據(jù)，將其與優(yōu)化前J公司的配送數(shù)據(jù)進(jìn)行對比，如表3所示。

對比配送結(jié)果可以看出，優(yōu)化前后配送總成本從1 561.56元降低到1 430.93元，總成本降低了8.4%，降低了企業(yè)的運(yùn)輸成本；配送時間從原來的804.33分鐘縮短到711.53分鐘，配送時長縮短了11.5%，提高了企業(yè)的物流配送效率。

4" 結(jié)" 論

多車型車輛路徑問題研究具有廣闊的應(yīng)用前景，采用多車型車輛進(jìn)行配送對企業(yè)降低運(yùn)輸成本有重要意義。本文建立了考慮需求可拆分的多車型電動車路徑優(yōu)化模型，并提出了改進(jìn)的自適應(yīng)遺傳算法對模型進(jìn)行求解。求解結(jié)果表明，本文提出的配送方案在配送總成本上降低了8.4%，配送總時長縮短了11.5%，實現(xiàn)了配送成本的降低和物流配送效率的提高。

參考文獻(xiàn)：

[1] 初良勇，王嘉寧，丁靜茹. 不確定需求下異構(gòu)電動物流車輛的路徑優(yōu)化研究[J/OL]. 計算機(jī)工程與應(yīng)用，1-18（2024-10-31）[2025-01-16]. http：//kns.cnki.net/kcms/detail/11.2127.TP.20241031.1400.004.html.

[2] 夏揚(yáng)坤，鄧永東，龐燕，等. 帶客戶分級和需求可拆分的生鮮車輛路徑問題[J]. 計算機(jī)集成制造系統(tǒng)，2021，27（4）：1238-1248.

[3] 王南星，韓宗睿，劉勇，等. 多車場多車型冷鏈物流時變綠色車輛路徑優(yōu)化[J]. 物流科技，2024，47（15）：141-146.

[4] 王偉權(quán)，丁鼎，顏林莎. 線性充電策略下多車型電動車輛路徑模型研究[J]. 系統(tǒng)仿真學(xué)報，2022，34（3）：614-623.

[5] 顧文斌，唐敦兵，鄭堃，等. 基于激素調(diào)節(jié)機(jī)制改進(jìn)型自適應(yīng)粒子群算法在置換流水車間調(diào)度中的應(yīng)用研究[J]. 機(jī)械工程學(xué)報，2012，48（14）：177-182.