考慮需求可拆分的多車型電動車路徑優化研究

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

" 關鍵詞：物流配送；需求可拆分；多車型；電動車；改進的自適應遺傳算法

" 中圖分類號：U116.2" " 文獻標志碼：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公司為一家物流運輸公司，業務主要聚焦于快消、服裝、家電家具、生鮮等產品的運輸。目前，該公司所使用的配送方案為使用同一型號的電動車進行配送，隨著公司業務的不斷擴張，各個配送點的需求差異性較大且需求量也在增加，進而導致該公司的運營成本不斷增加，如何降低物流成本是J公司面臨的主要問題。

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

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

1" 問題描述與模型建立

1.1" 問題描述

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

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

1.2" 模型建立

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

2" 算法設計

本文所研究的問題為車輛路徑問題的延伸問題，屬于NP-hard問題，求解較為復雜，現有研究多采用啟發式算法進行求解。遺傳算法是受自然進化過程中“優勝劣汰”的自然選擇機制和遺傳信息傳遞規律的啟發所提出的一種智能優化算法，該算法可以應用于多種問題的優化，具有全局搜索能力強等優點。本文對傳統的遺傳算法進行改進，提出改進的自適應遺傳算法，改進后算法的設計如下。

" （1）編碼與解碼

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

（2）計算種群適應度

（3）選擇操作

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

" Step1：假設有n個個體，從中隨機選擇2個個體；

" Step2：比較2個個體的適應度值，并保留適應度值較高的個體；

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

" （4）交叉及變異操作

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

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

3" 優化效果評價

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

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

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

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

4" 結" 論

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

參考文獻：

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

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

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

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

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