多中心半開放式城市物流異構電動車輛路徑優化

摘 要：

隨著國家政策的推動及新能源技術的發展，電動物流車在財政補貼、限行、節能環保和運營成本方面相較傳統燃油車具有優勢，越來越多的物流企業在城市配送中采用電動物流車。根據異構車型電動車輛配送隊伍較單一車型電動車輛配送隊伍具有降低物流配送費用優勢的研究，在多中心半開放式情況下，考慮客戶時間窗要求及電動車輛續航里程和充電約束，構建了配送總成本最小的電動車輛物流配送路徑優化模型。針對該模型特點，利用遺傳算法與模擬退火相結合的混合算法進行求解。分析表明，所構建的優化模型及求解算法可以有效解決多中心半開放式的異構電動物流配送車輛路徑優化問題。

關鍵詞：車輛路徑問題；異構車型；電動物流；遺傳-模擬退火算法

中圖分類號：TP301"" 文獻標志碼：A""" 文章編號：1001-3695（2024）12-008-3587-08

doi： 10.19734/j.issn.1001-3695.2024.06.0149

Vehicle route optimization of heterogeneous fleet electric for multicenter semi-open urban logistics

Chu Liangyong1，2， Wang Jianing1，2， Ding Jingru1

（1.School of Navigation， Jimei University， Xiamen Fujian 361021， China; 2.Fujian Shipping Research Institute， Xiamen Fujian 361021， China）

Abstract：

With the promotion of national policies and the development of new energy technologies， this paper aimed to explore the application of electric logistics vehicles in urban distribution to optimize their routing and reduce total distribution costs. It constructed a logistics distribution path optimization model for electric vehicles that minimized total distribution costs， considering customer time window requirements， low electric vehicle range， and charging constraints. It used a hybrid algorithm combining genetic algorithm and simulated annealing to solve the model. The analysis shows that the constructed optimization model and the solution algorithm can effectively solve the path optimization problem for heterogeneous electric logistics distribution vehicles in a multi-center， semi-open environment. The proposed model and algorithm not only reduce total distribution costs but also enhance the efficiency of electric logistics vehicles in urban distribution， demonstrating practical application value.

Key words：vehicle path problem; heterogeneous vehicle model; electric logistics; improved genetic-simulated annealing algorithm

0 引言

隨著國家經濟的迅速發展和人們消費方式的升級，城市物流配送活動也隨之蓬勃增長。作為物流基本活動的關鍵環節，城市配送在物流行業中的地位愈發重要，對城市經濟發展產生深遠影響。電動汽車以其低污染、可再生的優點，迅速占據城市物流配送市場，并逐步取代燃油車，成為解決城市物流配送需求和環保問題的首選運輸工具。

為了在有限條件下對電動車輛進行合理調度，提高經濟效益，部分學者集中研究通過充電手段來提升車輛的續航能力。增加行駛過程中電池電量不僅可延長車輛的配送里程，還有助于削減配送成本。Conrad 等人［1］針對途中充電的車輛路徑問題，證明通過充電有效地減少了車輛的配送成本。Schneider等人［2］探究了車輛經過充電站的問題，建立了包括充電站在內的數學模型，并運用混合啟發式算法來解決，同樣證實途中充電策略有助于降低車輛的配送成本。Adler 等人［3］針對電動車輛的電量焦慮，研究了充電站數量相對應的EVRP。電動汽車的途中充電主要分為完全和部分兩種充電策略。車輛在途中充電站將電量充滿為完全充電策略。允許電動車輛充電至任一電量水平為部分充電策略。除了充電策略的考慮外，國內外學者在建立模型時，大多數以恒定的電量消耗單位里程以及線性的充電時間與電池充電水平的關系作為假設。例如，Goeke 等人［4］針對客戶時間窗約束，構建異質車隊EVRP模型時采用完全充電策略，且充電時間與電量成正比。Keskin等人［5］在其 EVRP 模型中設置了正常速率充電、快速充電和超快速率充電三種充電模式，均采用線性充電模型。程坦等人［6］研究了考慮多種因素下以多種車型進行配送的問題，設計了局部搜索增強的自適應大鄰域搜索算法進行求解，結果表明采用部分充電策略可以有效節約成本。此外考慮到客戶需求可能會隨時發生變動，部分學者對于不確定需求電動物流車輛路徑規劃也進行了研究。Ge等人［7］針對具有隨機需求和動態補救措施的電動汽車路徑的總成本最小化問題，建立了機會約束的EVRPSD模型和兩個插入成本模型，并設計了CW-TS啟發式算法和貪婪算法來求解它們。

隨著物流企業規模的發展，物流車輛配送問題也從單一車型發展到了異構車型。Subramanyam等人［8］將多車型與不確定需求相結合，對不確定需求建模為隨機變量的異構車輛路徑問題進行研究。張景玲等人［9］考慮了新增客戶需求和客戶需求量變化兩種不確定性，建立了多車型開放式車輛路徑問題兩階段模型，求得的配送方案能夠較好地處理新增客戶需求和新增客戶導致的需求量的變化。李嘯麟［10］通過對多車型電動物流車的物流配送現狀進行分析，建立了多車型配送路徑規劃模型，并設計遺傳算法運用 MATLAB求解模型，從而驗證了該模型的可行性。閆淼等人［11］針對同一車型與異構車型物流車隊進行比較，認為異構車型應用在城市物流配送可以有效降低整體配送成本，減少車輛資源的閑置與浪費，優化車輛路徑。

隨著特大城市和城市群的出現，傳統的單一車場配送模式難以滿足快速、高效、準時的要求，建立城市運營級多配送中心成為進一步發展目標。王長瓊等人［12］針對電商配送中的 VRP 問題，建立多配送中心車輛路徑優化模型，采用遺傳算法對該模型進行求解。于濱等人［13］通過啟發式算法預優化初始種群，提高蟻群算法的搜索效率，設計兩階段算法求解MDVRPTW。張鵬威等人［14］結合電動車輛在充電站或配送中心補充電量的行為，設計分散搜索算法求解MDVRP。王勇等人［15］考慮共同配送和資源共享策略，研究了多中心電動車輛路徑問題，建立了雙目標優化模型，設計了基于節約算法的多目標粒子群混合算法求解。范厚明等人［16］針對多車型多配送中心問題基于“先車輛后配送中心”的原則，先根據車輛容量約束重新為每個車輛分配客戶，再根據首尾客戶位置計算出最近的配送中心，從而獲得最終路徑。Wang等人［17］構建了帶時間窗和共享充電站的協同多車場電動車輛路徑優化模型，提出了一種嵌套禁忌搜索的改進多目標遺傳算法，以優化電動車路徑和充電位置。張穎鈺等人［18］研究了多中心半開放式送取需求可拆分的車輛路徑問題，構建了以車輛配送距離最短為目標的模型，設計大變異鄰域遺傳算法進行求解。

目前經典車輛路徑問題大多只考慮了速度恒定的情況，而忽略了實際配送過程中會出現交通擁堵等因素的影響，因此時變速度的車輛路徑問題近年來成為一個研究熱點。Gmira等人［19］考慮了時變條件下客戶間的行程時間和行駛路徑的變化，并采用禁忌搜索算法求解。周鮮成等人［20］同樣根據經驗設定早晚高峰與平常出行時間，以改變路網的速度。隨著物流行業的快速發展，許多企業擁有多個配送中心，因此多車場車輛路徑問題成為新的研究熱點。Hesam等人［21］針對多車場車輛路徑問題，設計了一種變量鄰域禁忌搜索算法求解，該算法在強化階段采用顆粒狀局部搜索機制，在變量鄰域搜索的多樣化階段采用禁忌振蕩機制。

綜合來看，已有研究在滿足客戶時間窗限制條件下將電動物流車輛應用到城市配送當中，但未充分考慮電動物流車輛在配送過程中與多中心多車型的發展實際。基于此，本文建立的電動物流車輛路徑優化模型，與現有研究主要區別在于設置時變速度以及加入多車型、多中心半開放式配送約束條件，利用改進的遺傳-模擬退火混合算法進行求解，讓車輛路徑規劃更加貼近現實，豐富研究成果。

1 問題描述

城市物流主要是城市區域內的企業為確保產品供應的正常運轉，從城市內的大型倉庫中獲取原材料或將產品分銷給下級供應商的物流活動。為了有效安排配送任務，企業需要提前一天向配送中心通報所需的貨物數量，而配送中心則會根據各客戶的需求量來組織當天的配送工作。

物流企業若采用單一配送中心模式，可能面臨配送距離過長和難以準時到達客戶所在地等問題。并且，單一配送中心的路徑優化模型更適用于需求點較少、客戶相對集中、為某一社區或小城市的配送任務。而為了滿足大城市的城市物流客戶需求，采用多企業協同配送的多配送中心模式更為合適。在實際的配送問題中，一個城市的貨物配送通常不僅限于單一中心，而是會建立多個配送中心，以滿足配送需求并節約成本。因此，本文采用多配送中心的半開放式配送模式，車輛可以從任意配送中心出發，在完成所有配送任務后返回任意配送中心。

本文構建的模型以車輛固定成本、運輸成本、充電成本以及客戶時間窗懲罰成本之和最小為目標函數，以確保配送方案總成本的最小化。在所設定的問題中，模型包括多個配送中心和多個客戶點，所有配送中心和客戶點的地理位置均為已知。多個配送中心共同擁有多型號的配送車輛，這些車輛可以從任一配送中心出發，滿足不同時間點的客戶需求，最終返回任意配送中心。每個配送中心的貨物量充足，車型數量已知，可靈活調配。為了簡化模型構建并確保配送的有序進行，每個客戶需求點只能由一輛車進行配送，每條配送路線也僅由一輛車完成。此外，鑒于城市道路在不同時間段存在擁堵情況，本文構建的多中心半開放式帶時間窗的車輛路徑問題模型也充分考慮了時變路網的影響。本文城市物流配送模式如圖1所示。

2 模型構建

2.1 模型假設

本章研究的是需求量確定背景下多中心半開放式多車型的EVRP-TW，因為在現實的配送中要考慮的實際因素過多，為了方便模型的構建，作出如下假設：

a）多配送中心同時配送，電動物流車從一配送中心出發，完成路徑上所有客戶點配送任務后，返回距離最近的配送中心。

b）每個客戶點的地理位置、客戶需求量、時間窗、服務時間已知且不會變化；每個客戶需求不可拆分，只能被一輛電動物流車服務，但每輛電動物流車可以服務多個客戶點。

c）不同類型電動物流車的最大載重、電池額定容量、充電速率等參數已知，且電動物流車在充電時充電速率保持不變。

d）當電動物流車剩余電量到達預設的電量焦慮值時，就近選擇充電站補充電量；充電站地理位置、收費標準已知，可容納多輛電動物流車同時充電。

e）電動物流車在行駛途中的耗電系數保持不變。

f）本文僅考慮不同時間的道路擁堵對車輛速度與車輛行駛時間的影響。

2.2 符號說明

本文模型構建所使用的符號如表1所示。

定義決策變量為：Xpijkr，若配送中心p的第k輛r型車從客戶點i行駛到客戶點j，則Xpijkr=1，否則Xpijkr=0；Ypikr，若配送中心p的第k輛r型車服務客戶點i，則Ypikr=1，否則Ypikr=0；Zpikr，若配送中心p的第k輛r型車在充電站i點充電，則Zpikr=1，否則Zpikr=0。

2.3 車輛行駛時間計算

在交通擁堵情況下，車輛的行駛速度為時變速度，車輛在不同時間段的行駛速度不同，為此采用路段劃分方法計算車輛在各路段的行駛時間。

將一天內的可配送時間劃分為H個不同時段，T0表示配送網絡最早出發時刻，{T0，T1，…，TH－1}為H個時段的時間節點。不同時段下有不同的平均車速vl（l=0，1，…，H－1），則車輛kr在子時間［Tl，Tl+1］（l=0，1，…，H－1）內的行駛時間為

tvikr，l=Tl+1－Tl""""" ""∑lh=0（Th+1－Th）vh≤lij

lij－∑lz=1（Tz－Tz－1）vz－1vz ∑lh=0（Th+1－Th）vhgt;lij≥∑lz=1（Tz－Tz－1）vz－1

0 ∑lz=1（Tz－Tz－1）vz－1gt;lij（1）

2.4 數學模型

本文設計了以總配送成本為最小的目標函數，考慮電動車輛配送時的電量消耗，構建了異構電動車輛的城市物流配送路徑優化模型。

目標函數式（2）表示構建總成本最小為優化目標的異構電動車輛路徑優化模型，其中第一部分為固定成本、第二部分為運輸成本、第三部分為懲罰成本、第四部分為充電成本。約束式（3）表示車輛完成配送任務后不必返回初始配送中心。約束式（4）表示到達節點與離開節點的車輛相同。約束式（5）表示不存在從配送中心出發到配送中心的車輛。約束式（6）表示子回路消除約束。約束式（7）表示所有客戶均得到服務且僅被一輛車服務。約束式（8）表示車輛從配送中心出發，且最多出發1次。約束式（9）表示保證客戶點被車輛服務時一定有其路徑與其連接。約束式（10）表示從配送中心承載的貨物量等于配送過程中所有客戶點的需求量，且該初始承載貨物量不超過r型車的最大裝載貨物量。約束式（11）表示車輛離開節點i的時間。若節點i為客戶點，則為到達客戶點的時間和客戶點的最早服務時間相比的最大值，與客戶點服務時間的和；若節點i為充電站點，則為到達充電站點時間與充電時間的總和。約束式（12）表示車輛從節點i到j的行駛時間。約束式（13）表示車輛到達節點的時間。約束式（14）表示車輛電量與行駛里程關系。車輛電量在行駛過程中，僅與消耗速率、行駛時間有關，與載重等無關。約束式（15）表示車輛離開節點i時的電量。服務客戶點時車輛進行卸載操作，無須耗電；充電站充電時看作完全充電。約束式（16）表示車輛電量焦慮約束。考慮到電動物流車電池特性及駕駛員的里程焦慮，車輛的剩余電量一般不低于該車輛最大電池容量的20%～25%。約束式（17）表示電池充電量約束。約束式（18）表示所有車輛從倉庫出發時均為滿電狀態。

3 算法設計

本文所構建的模型是典型的NP-hard問題，傳統精確算法難以對該類問題進行快速求解，故應用元啟發式算法求解。遺傳算法在應對約束、執行全局搜索及保持穩定性能方面展現出優越性，且編程實現相對簡單，已廣泛應用于各種環境下的車輛路徑優化。因此，本文選用遺傳算法作為解題策略。為改進遺傳算法局部探索能力不足的缺點，本文提出將模擬退火算法融入其中。這一創新點旨在全面提升算法性能，加快運算與收斂速度，防止陷入局部最優，縮短求解時間，從而極大地提高混合算法的效率。

3.1 改進遺傳算法階段

3.1.1 初始種群生成

構建初始解決方案的策略對算法的優化質量和速度具有顯著影響。隨機創建初始種群可能導致大量無效個體，從而延長收斂時間。為了提升有效解的生成概率，本文提出一種“先客戶后配送中心”的兩階段生成方法，確保初始種群的可行性，并增強其多樣性和有效性，防止過早陷入局部最優。具體步驟如下：

階段1：客戶點分組和服務順序設定

a）根據問題需求，隨機選取車輛類型和起始配送中心（虛擬配送中心0）。按客戶時間窗起始時間由早到晚排列所有未服務的客戶，選取最早的客戶點作為當前路徑的第一個客戶點。

b）計算所有未服務客戶點的載重量，并判斷其是否滿足載重量約束，從所有滿足條件的未服務客戶集合中選擇需求量最大的客戶插入到路徑，重復操作，直到電動物流車的載重量約束不滿足或車輛返回配送中心服務時間超時，則新派一輛車。

c）對上述步驟生成的路徑進行電量修復。計算車輛在該路徑上到達各客戶節點的距離，從而計算車輛抵達第i個客戶節點時的剩余電量。當剩余電量低于預設的電量焦慮值時，車輛返回上一個客戶節點后，尋找距離最近的充電站。計算充電站與該客戶節點的位置，計算抵達充電站的耗費電量，若剩余電量高于耗費電量，則將充電站插入第i－1與i個客戶節點之間。若耗費電量高于剩余電量，返回第i－2個客戶節點，重復此過程，直至插入充電站節點。充電站插入策略如圖2所示。

d）重復步驟a）～c），直至所有客戶均被服務。

階段2：設定車輛的起點和終點配送中心。

e）替換虛擬配送中心0。計算每條路徑上第一位和最后一位客戶至所有配送中心的距離，選擇與路徑第一位客戶最近的配送中心作為車輛起點配送中心；選取與路徑上最后一位客戶最近的配送中心作為車輛終點配送中心。

圖3為染色體編解碼過程示意圖，以15個客戶（編號為1～15）、2個充電站（編號為16、17）、3個配送中心（編號為18～20）以及車輛型號為A（編號1、2）、B（編號3、4）兩種為例，按照上述步驟生成初始解：步驟a）b）劃分后的路徑如圖3（a） 所示；步驟b）電量修復過程后劃分的路徑如圖3（b）所示；步驟e）得到初始解如圖3（c） 所示。

3.1.2 建立適應度函數

本文采用總成本的倒數表示染色體的適應度函數值，即目標函數值Z越小，染色體的適應度值越大，個體越優，被選擇的概率越大，反之被選中的概率則越小。染色體的適應度函數可以表示為

fit（i）=1Zi" i∈{1，2，3，…，N}（19）

其中：Zi為第 i 條染色體的目標函數值；N為種群數量。

3.1.3 選擇操作

本文選擇操作中采取精英保留與輪盤賭相結合的策略。假設種群規模為N，各染色體的適應度值為fit（i），被選擇的概率為P（i），基于適應度值，選擇與種群數量相同的染色體生成子代種群。精英保留與輪盤賭相結合的選擇算法具體步驟如下：

a）將染色體按照適應度值fit（i）進行降序排列，依據設定的精英保留比例x%，保留前x%的染色體成為子代種群染色體。

b）計算剩余染色體被選擇的概率P（i）：

P（i）=fit（i）∑N（1-x%）i=1fit（i）（20）

c）計算剩余染色體被選擇的累計概率q（i）：

q（i）=∑N（1-x%）i=1fit（i）（21）

d）隨機產生數α∈［0，1］，若α≤q（1），選擇 1 號染色體成為子代種群染色體；若q（i－1）lt;αlt;lt;q（i），則選擇i號染色體遺傳到下一代。

e）重復步驟d），生成（1－x%）N個染色體，與步驟a）中的個體組成子代種群。

3.1.4 交叉變異操作

交叉操作是指從父代中選擇兩個染色體進行交配，并按照某種規則相互交換染色體片段生成兩個新染色體的過程。本文通過兩點交叉的方式生成子代。兩點交叉在遺傳算法中常用于提高種群的多樣性，促使算法更好地探索解空間。具體操作步驟如下：首先在兩個染色體中隨機選擇兩個交叉點；然后交換這兩個交叉點之間的染色體片段，生成兩個新的染色體。

變異操作是指在染色體中隨機改變一個或多個基因值的過程，以提高種群多樣性，避免進化過程中陷入局部極值。本文采用的是互換變異法，即將兩個等位基因的位置互換。具體操作步驟如下：首先隨機選擇染色體中的兩個基因位置；然后交換這兩個基因的位置。

3.1.5 交叉和變異概率自適應

自適應遺傳算法通過實時調整系統的動態參數，以改進算法的運行。這種方法不僅有助于保持種群的多樣性，還能提高算法的搜索能力。具體而言，當種群適應度較為集中時，可以適度增加交叉率（pc）和變異率（pm），以促使生成更多的新個體，從而探索更廣泛的搜索空間；相反，當種群適應度較為分散時，可適度降低pc和pm，以防止過度搜索，保持種群的多樣性。因此，通過自適應調整，pc和pm能夠形成相對最佳的取值，使得算法在不同的問題情境中更為靈活和高效。

本文按式（22）和（23）分別對交叉率pc和變異率pm進行自適應的調整。

pc=k1fmax－f′fmax－favg" f′≥favg

k3 f′lt;favg（22）

pm=k2fmax－ffmax－favg" f≥favg

k4 flt;favg（23）

其中： fmax為群體中最大的適應度值； favg為每代群體的平均適應度值； f′為兩個要交叉的個體中較大的適應度值； f為要變異個體的適應度值；k1、k2、k3、k4為系數，其中，基于個體被完全打亂的原則，一般將k3和k4設置為0.5，k1和k2設置為1.0。

3.2 模擬退火操作階段

本文采用指數退火方法進行降溫，即

Tk+1=βTk（24）

其中：Tk為第k次迭代的系統溫度；β為冷卻因子，一般取值為0.5～0.99。

在基于遺傳算法交叉、變異處理后，到達指定模擬退火開始迭代代數，模擬退火操作如下：

a）設置參數。初始溫度Tmax，令當前溫度T0=Tmax，終止溫度為Te，開始迭代代數為L0，停止迭代代數為Le，冷卻因子為β。

b）隨機選定一個初始解x0，令當前解xa=x0。

c）生成一個擾動解xnew，由于本文車輛總配送成本目標函數是離散的，產生的擾動解為隨機偏移量。

d）計算并比較新生成擾動解和當前解的適應度函數fit（xnew）和fit（xold），根據Metropolis基本準則式（25）決定是否接受新解。

p=1""""""""""" fit（xnew）≤fit（xold）

exp（－fit（xnew）－fit（xold）T） fit（xnew）gt;fit（xold）（25）

其中：p為新個體取代當前個體的概率；xnew為當前解；xold為擾動后產生的新解；T為當前溫度。

e）判斷是否達到迭代次數，若沒有，計算當前種群染色體適應度值，并進行改進遺傳算法操作；若滿足，則循環結束，輸出最優解。

綜上，改進遺傳與模擬退火混合算法流程如圖4所示。

4 算例驗證與結果分析

4.1 實驗設置

為了計算方便、使實驗結果具有可比性，本文選自 Cordeau標準數據集算例進行驗證和分析。該算例集針對 MDVRPTW 問題給出 20 組算例，其中算例pr01～pr10的客戶時間窗口較窄，配送中心用于服務的車輛數較多；pr11～pr20的客戶時間窗口較寬，配送中心用于服務的車輛數目較少；每個算例中各配送中心的車輛是同質的，即具有相同的最大載重和最長運行時間。

本文適題修改算例pr13，該算例中包含 4 個配送中心、144 個客戶，包括各客戶的坐標、需求、服務時間及時間窗。本文在算例pr13的基礎上選取4個客戶點改編為充電站（最后4個客戶點），產生45客戶點（前45客戶點）算例、92客戶點（前92客戶點）算例、140客戶點（前140客戶點）算例。45客戶點算例中各節點分布如圖5所示。調整后的算例形成了一個物流配送網絡，對本算例作出如下說明。

a）本算例集形成的配送網絡包括4個配送中心，4個分布于車場外的社會充電站，45個待配送客戶，各客戶時間窗及服務時間各不相同。多車型異構車隊可靈活調配，滿足不同配送中心的服務要求。車輛應在客戶時間窗內配送，若未在時間窗內到達，則按照標準產生懲罰成本。

b）所有電動物流車出發時均為滿電狀態。

c）電動物流車的配送出發點和終點均為配送中心，不約束為同一配送中心。

d）不允許電動物流車從充電站出發去往充電站。

4.2 算法參數設置

針對求解模型的改進遺傳-模擬退火混合算法，根據多次測試，算法參數的具體信息如表2所示。

4.3 車輛參數設置

為符合城市物流配送要求，本文需要設置模型的參數。模型的參數主要包括不同車輛的載重、車輛的固定成本、車輛行駛單位距離的運輸成本等，模型參數的具體信息如表3所示。

另外，考慮到電動物流車電池特性及駕駛員的里程焦慮，車輛的剩余電量不低于該車輛最大電池容量的20%，即δ=0.2。設定配送車輛早到等待懲罰系數為0.5元/min，晚到懲罰系數為0.7元/min。

4.4 時變速度設置

在實際的城市路網中，路網的運行速度時刻都在變化，為便于研究，本文假定路網運行速度在同一時間段內為定值，即假設路網運行速度服從離散型函數。時變速度的設定參考了百度地圖交通出行大數據平臺（https：//jiaotong.baidu.com/congestion/city/urbanrealtime/）發布的城市實時平均速度。為了選取具有明顯每日速度變化的數據，本文選擇了ZB市12月某工作日的速度數據，從圖6能看到，在早高峰和晚高峰期間，路網速度有顯著性變化。

為了實現合理的時段劃分和降低算法運行的復雜度，本文采用二分K-means方法劃分時段的策略。這種方法可以有效地將數據集劃分為不同的類型和簇，確保同一類型或簇中的數據類型的差異較小，而不在同一類型或簇中的數據類型的差異較大。這種聚類算法的運用，是為了根據時間和平均速度這兩個變量，將不同時段進行劃分，以便更好地分析和優化電動車輛路徑問題。

圖7為采用二分K-means算法對時段進行劃分的結果，K選取15，即將一天時間分成15個聚類，ω選取5 000，τ選取1。圖中，星號表示該點所在聚類質心。

根據圖中數據，整理成為表格如表4所示。

4.5 運行結果分析

為驗證改進遺傳-模擬退火算法對于模型的可行性，測試小規模客戶點算例運行情況，及不同規模客戶點算例運行情況對比。

4.5.1 小規模客戶點算例運行結果分析

圖8與表5為程序運行10次后的最優車輛路徑結果，該結果下程序的運行時間為11.43 min，為完成配送所需配送總成本為3 343.06元，車輛懲罰成本為61.98元，充電成本為527.45元，使用8輛車完成配送，所有客戶點均被服務。通過對結果的綜合分析，表明本文算法在小規模客戶點的場景下表現良好，能夠在保證服務質量的前提下實現成本優化。

4.5.2 不同規模客戶點的結果對比分析

為驗證本文算法在求解不同規模客戶點的有效性，分別對45、92、140個客戶點進行10次獨立實驗，采用改進遺傳-模擬退火混合算法求解10次，由于客戶點數目不同，隨著客戶點數目適當增加初始種群規模，分別為50、70、100，所得結果如表6所示。

由表6分析可知，雖然配送成本與持續運行時間隨著數據規模的增長而加大，但依舊控制在合理的范圍內。當客戶規模為45、92、140時，所有客戶點均被服務，證明本文模型的有效性，表明改進GA-SA混合算法求解需求量確定模型的可行性。

4.6 算法對比分析

本文改進后的遺傳-模擬退火混合算法相對于改進遺傳算法，不僅體現在對模型的適應性，在算法迭代收斂次數和速度上同樣能夠判斷算法優化是否有效。除了改進遺傳算法外，增加改進遺傳算法與大規模鄰域算法相結合的混合算法作對比，體現改進遺傳-模擬退火算法的有效性。

本節改進遺傳-大規模鄰域算法（改進GA-SA）在自適應遺傳算法步驟不變的情況下，改變模擬退火操作，設置為鄰域退火操作。其中，主要涉及到破壞算子與修復算子的選擇。

相關性破壞算子是指通過移除相似的客戶節點來對當前解進行破壞，本文的相關性計算公式為

R（i， j）=1l′ij+σijl′ij=lijmax lij（26）

其中：l′ij是兩客戶點距離標準值，范圍為［0，1］；lij表示客戶點之間的直線距離；σij=1表示兩客戶點在同一條配送路徑上，否則為0。若R（i， j）的值越大，客戶點相關性就越大。隨機選擇客戶點i，計算與其他客戶點的相關性，從大到小移除N個相關客戶。

遺憾值修復算子是指將破壞算子移除的客戶，按照遺憾值計算的高低，重新插入到路徑中。本文的遺憾值修復算子計算為

argmaxi∈N′1n∑vj=1Δτ（i，rj）－Δτ（i，r*）（27）

其中：N′為被相關性破壞算子移除的客戶點集合；Δτ（i，r*）表示客戶點i插入的最低增加費用，且對應的最低費用路徑為r*；Δτ（i，rj）表示除r*外其他路徑的最低插入費用，n為客戶點i可插入路徑的個數。通過遍歷被移除客戶點集合，將其插入到各自最低費用路徑的最優位置。

以45個客戶點為例，針對本文需求量確定的多中心半開放式多車型配送模型，分別對本文改進GA算法、改進GA-SA混合算法和改進GA-LNS混合算法進行10次實驗，總配送成本最優值如表7所示。

由表7，從總成本看，三種算法得到的結果差異并不大，但是時間上，采取改進GA-SA算法相較其他兩種算法確實有效地減少了運算時間，提升了算法的運算效率。因此，采取改進GA-SA混合算法在算法的收斂性能和計算速度上能夠有效求解需求量確定的多中心半開放式多車型帶時間窗路徑問題，并具有較好適應性。

4.7 模型對比分析

4.7.1 不同配送模式結果對比分析

為明確多中心半開放式在城市物流配送路徑優化問題中的作用，將原模型配送中心約束式（3）修改為

∑j∈V0xppjkr=∑j∈Vxpjpkr p∈P，kr∈K（28）

從而約束配送車輛必須返回出發配送中心，轉為多中心閉合式城市物流配送模式，其他條件不變，選取客戶點數目為45的數據集，采用改進GA-SA混合算法運行10次，并與上述構建的多中心半開放式物流配送路徑優化問題結果進行對比，所得結果如表8所示，其中節約成本比例為多中心閉合式配送模式最優值相對于多中心半開放式配送模式總配送成本最優值的節約百分比。

由表8可知：

a）總配送成本對比：多中心半開放式策略下的總配送成本低于多中心閉合式策略下總配送成本，表明在物流企業擁有多個配送中心，采用多中心半開放式聯合配送模式可以合理調配車輛資源，降低整體運輸成本，為企業盈利帶來增長空間。

b）配送成本明細對比：在進一步分析多中心情況下兩種配送模式最優配送方案的各項成本構成后發現，半開放式具有較小的配送成本和充電成本，其運輸成本比閉合式配送模式的運輸成本低7.16%，其充電成本比閉合式配送模式的充電成本低2.10%。此外，半開放式配送模式充電次數相較于閉合式配送模式充電次數顯著降低。這可能是因為在多中心半開放式配送模式中，電動物流車顯著地減少因閉合模式所導致的不必要的運輸路線，降低了電動物流車電量的消耗，從而降低了配送成本與充電成本，大大提高運輸效率，證明了本文模型的經濟性。

4.7.2 不同結構物流車隊結果對比分析

為明確異構物流車輛在城市物流配送網絡中的作用，將原模型的決策變量xpijkr修改為xpijk，構建同質車型的電動汽車城市物流路徑優化問題。與上述構建的異質車隊問題結果進行對比。所得結果如表9所示，其中節約成本比例為同質車隊較異質車隊的總配送成本節約百分比。

由表9可知：

a）總配送成本對比：異質車隊策略下的總配送成本低于同質車隊策略下的總配送成本，這表明在多中心半開放配送模式下采用異質車型的車輛配送，能夠合理調配車輛資源，從而降低整體運輸成本，為物流企業節約成本和盈利增長提供了空間。盡管在具體成本對比時，異質車隊并非在每個成本方面都表現出最低值，但總體上，其降低總配送成本的能力更強，這可能歸因于其更靈活的車型組合和路線規劃方式，能夠更好地適應復雜的配送需求和環境。

b）車型選擇對比：在同質車隊策略下，不同車型的使用情況和充電次數存在差異。A和B兩種型號的車輛在使用頻率和充電行為上存在顯著差異。B車型展現出顯著的優勢，不僅在配送車輛需求上顯著降低，而且相較于A車型，B的充電次數更為經濟。這揭示了B車型對于長途和持續運輸任務的高效適應性。然而，深入剖析這兩種車型的成本構成時，A車型顯示出更低的配送費用與充電成本，這意味著在區域范圍較小且車輛充足的場景下，選擇小型載重的A車型進行配送比大型載重的B車型更具優勢；但在區域范圍較大且充電站較少的場景下，選擇B車型更為經濟。

4.8 充電站數量靈敏性分析

在采用異構車型的電動物流車輛進行配送的情況下，為分析充電站數量對配送網絡中車輛路徑規劃的影響，在其他條件不變的情況下僅調整充電站數量對模型進行求解，每個算例分別求解10次，將其最優值進行比較，實驗結果如表10所示。

由表10可知：

總配送成本會隨著充電站數量的增多而降低，而當總成本降低到一定程度后變化趨于平緩。在本文45客戶點數目隨機分布的條件下，當充電站數量超過3個時，總配送成本的變化不再明顯。具體分析而言，隨著充電站數量的增多，配送車輛逐步減少，其配送過程中充電成本也逐漸降低。這是因為在一定區域內，隨著充電站數量的增加，配送車輛行駛路徑選擇的余地更大，但該區域的充電站數量卻趨于飽和，足夠服務該地的客戶點數量；設置過多的充電站，不僅會加大充電站的建設和維護成本，還會降低該地充電站的平均利用率。該靈敏性分析也證明了本文模型的現實合理性。因此，在根據客戶點分布的位置和數量合理建造充電站，可以有效減少車輛投入，減少物流企業配送成本。

5 結束語

本文在分析目前城市物流電動車輛配送路徑優化的背景下，分析多配送中心半開放式配送模式與多車型聯合配送的現實需求，考慮客戶時間窗與時變路網條件下車輛平均行駛速度的變化，研究帶有時間窗的需求量確定的多中心半開放式多車型配送路徑優化問題。分別構建以固定成本、運輸成本、時間窗懲罰成本、充電成本之和為最小值的目標函數。根據模型特點，采用“先客戶后配送中心”兩階段法構建初始種群，采用改進GA-SA算法求解模型。最后通過結果對比分析，證明本文模型和算法具有可行性和有效性。

但本研究還存在多方面的不足，比如模型的構建是基于一定的假設，而現實情況下的環境更為復雜，需要繼續加強與研究。在考慮道路因素方面，本研究只考慮固定節點直線運輸的電動車輛路徑問題，然而現實配送中，各節點間可以選擇不同的通路；且考慮道路擁堵對于時間路網車輛運行速度時，采用二分K-means算法對路網速度進行依據時間節段的階段劃分，未來可考慮車輛速度的連續函數變化。本研究假定不同充電時間平均電價相同，未來可考慮時變電價下的車輛路徑優化。且采用線性充電模式以及采用完全充電策略，未來可以考慮非線性充電模式或部分充電策略進行研究。

參考文獻：

［1］Conrad R G， Figliozzi M A. The recharging vehicle routing problem ［C］. //Proc of Industrial Engineering Research Conference.2011，1-8.

［2］Schneider M， Stenger A， Goeke D. The electric vehicle routing problem with time windows and recharging stations ［J］. Transportation science， 2014， 48（4）： 500-520.

［3］Adler J D， Mirchandani P B， Xue G， et al. The electric vehicle shortest-walk problem with battery exchanges ［J］. Networks amp; Spatial Economics， 2016， 16（1）： 155-173.

［4］Goeke D， Schneider M. Routing a mixed feet of electric and conventional vehicles ［J］. European Journal of Operational Research， 2015 （245）： 81-99.

［5］Keskin M， Catay B. A matheuristic method for the electric vehicle routing problem with time windows and fast chargers ［J］. Compu-ters amp; Operations Research， 2018 （100）： 172-188.

［6］程坦， 陳鵬， 張國偉， 等. 部分充電策略下的多車型電動汽車車輛路徑優化問題研究 ［J］. 交通運輸工程與信息學報， 2022， 20（2）： 105-114. （Cheng Tan， Chen Peng， Zhang Guowei. et al. Heterogeneous electric vehicles routing problem under partial charging strategy ［J］. Journal of Transportation Engineering and Information， 2022， 20（2）： 105-114.）

［7］Ge Xianlong，Zhu Ziqiang，Jin Yuanzhi. Electric vehicle routing problems with stochastic demands and dynamic remedial measures ［J］. Mathematical Problems in Engineering， 2020， 2020： 1-15.

［8］Subramanyam A， Repoussis P P， Gounaris C E. Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty ［J］. INFORMS Journal on Computing， 2020， 32（3）： 661-681.

［9］張景玲， 趙燕偉， 王海燕， 等. 多車型動態需求車輛路徑問題建模及優化 ［J］. 計算機集成制造系統， 2010， 16（3）： 543-550. （Zhang Jingling， Zhao Yanwei， Wang Haiyan， et al. Modeling and algorithms for a dynamic multi-vehicle routing problem with Customers dynamic requests ［J］. Computer Integrated Manufacturing Systems， 2010， 16（3）： 543-550.）

［10］李嘯麟. G公司多車型電動物流車配送路徑規劃研究 ［D］. 北京：北京交通大學， 2019. （Li Xiaolin. Distribution path planning of multi-model electric logistics vehicles of G company ［D］.Beijing： Beijing Jiaotong University， 2019）

［11］閆淼， 初良勇. 不同車型新能源車在城市冷鏈物流配送中的路徑優化 ［J］. 上海海事大學學報， 2022， 43（4）： 51-59. （Yan Miao， Chu Liangyong. Route optimization of different types of new energy vehicles in urban cold chain logistics distribution ［J］. Journal of Shanghai Maritime University， 2022， 43（4）： 51-59.）

［12］王長瓊， 王艷麗， 邱杰， 等. 基于TLV三維約束的多配送中心VRP問題 ［J］. 物流技術， 2017 （12）： 95-99. （Wang Chang-qiong， Wang Yanli， Qiu Jie， et al. Study on multi-depot VRP based on TLV three-fold constraints ［J］. Logistics Technology， 2017 （12）： 95-99.）

［13］于濱， 靳鵬歡， 楊忠振. 兩階段啟發式算法求解帶時間窗的多中心車輛路徑問題 ［J］. 系統工程理論與實踐， 2012， 32（8）： 1793-1800. （Yu Bin， Jin Penghuan， Yang Zhongzhen， Two-stage heuristic algorithm for multi-depot vehicle routing problem with time windows ［J］. Systems Engineering-Theory amp; Practice， 2012， 32（8）： 1793-1800）

［14］張鵬威， 李英， 成琪. 有限充電設施下的多配送中心電動車輛路徑問題研究 ［J］. 工業工程與管理， 2019， 24（5）： 97-105. （Zhang Pengwei， Li Ying， Cheng Qi. Multi-depot electric vehicle routing problem under limited recharging infrastructures ［J］. Industrial Engineering and Management， 2019， 24（5）： 97-105.）

［15］王勇， 李慧星， 羅思妤， 等. 資源共享模式下多中心共同配送電動車輛路徑優化問題 ［J］. 系統管理學報， 2023， 32（6）： 1119-1141. （Wang Yong， Li Huixing， Luo Siyu， et al. Electric vehicle routing optimization of multi-center joint distribution based on resource sharing mode ［J］. Journal of Systems amp; Management， 2023， 32（6）： 1119-1141.）

［16］范厚明， 徐振林， 李陽， 等. 混合遺傳算法求解多中心聯合配送路徑問題 ［J］. 上海交通大學學報， 2019， 53（8）： 1000-1009. （Fan Houming， Xu Zhenlin， Li Yang， et al. Hybrid genetic algorithm for solving multi-depot joint distribution routing problem ［J］. Journal of Shanghai Jiao Tong University， 2019， 53（8）： 1000-1009.）

［17］Wang Yong，Zhou Jingxin，Sun Yaoyao， et al. Collaborative multidepot electric vehicle routing problem with time windows and shared charging stations ［J］. Expert Systems with Applications， 2023， 219： 119654.

［18］張穎鈺， 吳立云. 多中心半開放式送取需求可拆分的車輛路徑優化 ［J］. 計算機應用研究， 2022， 39（8）： 2316-2321. （Zhang Yingyu， Wu Liyun. Multi-depot half open vehicle routing problem with split deliveries and pickups ［J］. Application Research of Computers， 2022， 39（8）： 2316-2321.）

［19］Gmira M，Gendreau M，Lodi A，et al.Tabu search for the time-dependent vehicle routing problem with time windows on a road network［J］. European Journal of Operational Research，2021，288（1）：129-140.

［20］周鮮成， 呂陽， 賀彩虹， 等. 考慮時變速度的多車場綠色車輛路徑模型及優化算法 ［J］. 控制與決策， 2022， 37（2）： 473-482. （Zhou Xiancheng， Lyu Yang， He Caihong， et al. Multi-depot green vehicle routing model and its optimization algorithm with time-varying speed ［J］. Control and Decision， 2022， 37（2）： 473-482.）

［21］Hesam S M E， atay B， Aksen D. An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems ［J］. Computers amp; Operations Research， 2021， 133： 105269.