摘 要：隨著城鎮(zhèn)化速度加快，城鄉(xiāng)結合區(qū)域配送問題受到廣泛關注。由于城鄉(xiāng)間交通條件存在差距，因此配送車隊構成和路徑安排成為制約物流運輸?shù)闹饕堋１疚尼槍θ绾谓档统青l(xiāng)混合區(qū)域條件下的配送成本，構建了模糊時間窗混合車隊的城鄉(xiāng)混合區(qū)域配送的車輛路徑數(shù)學模型（The vehicle routing problem in mixed urban and rural and regional distribution of mixed fleet，VRP-MURMF）數(shù)學模型，并提出一種基于模擬退火算法改進的多元宇宙算法，采用逆序輪盤賭策略，使其在一定概率下向較差宇宙方向移動，避免陷入局部最優(yōu)，在對比試驗中，在探索后期比其他算法仍然具有較強的尋優(yōu)能力，證明了本文算法的有效性。

關鍵詞：多元宇宙算法；配送成本；城鄉(xiāng)混合區(qū)域；車輛路徑優(yōu)化

中圖分類號：F 25" " " " " " 文獻標志碼：A

目前，我國城鎮(zhèn)化率不斷加快和鄉(xiāng)村交通條件進一步提升，城市和鄉(xiāng)村不同地區(qū)物流配送問題受到持續(xù)關注[1]。隨著社會發(fā)展和技術創(chuàng)新，物流配送方式日益多樣化。特別是在混合車隊的路徑優(yōu)化中，不同類型的配送工具需要協(xié)同運作，使路徑規(guī)劃更復雜并具有挑戰(zhàn)性[2-3]。因此本文研究了在模糊時間窗下混合車隊的城鄉(xiāng)混合區(qū)域配送的車輛路徑優(yōu)化問題（VRP-MURMF）。對于配送區(qū)域包括城市和鄉(xiāng)村2類區(qū)域且由一個配送中心的2類配送工具（油車、電車）配送的情況，提出了基于模擬退火的多元宇宙算法，提高了算法跳出局部最優(yōu)的能力和勘探能力。

1 問題描述與模型構建

1.1 問題描述

本文研究的混合車隊城鄉(xiāng)混合區(qū)域配送問題可以描述為在軟時間窗約束條件下，單一配送中心由混合車隊對城、鄉(xiāng)2類區(qū)域進行配送，具體包括以下7個假設。1）一個配送中心。2）每個配送節(jié)點只被一輛車服務。3）配送中心有2種車型，即油車和電車。4）載重不允許超過最大載質量，客戶位于城市和鄉(xiāng)村。5）車輛在鄉(xiāng)村和城市能耗速度不同。6）車輛的電量和燃油量充足，每個車型的最大載質量已知。7）每條配送線路的客戶總需求量小于等于車輛最大載質量，配送車輛從配送中心出發(fā)，最終返回配送中心。

1.2 數(shù)學模型

VRP-MURMF針對配送的總成本Fmin構建函數(shù)?？偝杀綟min包括C1（固定成本）、C2（行駛成本）、C3（能耗成本）、C4（碳排放成本）和C5（懲罰成本）。綜上所述，VRP-MURMF的具體數(shù)學模型如公式（1）所示。

Fmin=C1+C2+C3+C4+C5 （1）

1.2.1 固定成本

單次配送的固定成本不會隨距離等因素變化而變化，通常是配送的汽車數(shù)量和單位固定成本的乘積。

（2）

式中：i、j為配送節(jié)點；{1，...，N}為客戶集合；AKE為電車固定成本；AKC為燃油汽車固定成本；xij為{0，1}決策變量，油車或電車從節(jié)點i配送至節(jié)點j時xij=1，否則為0。

1.2.2 行駛成本

配送過程中車輛的行駛成本會因行駛里程的變化而變化，如公式（3）所示。

（3）

式中：BKE為電車單位距離成本；BKC燃油汽車單位距離成本；dij為節(jié)點i、j間的距離。

1.2.3 能耗成本

在配送過程中，車輛由燃油或電能消耗產生的成本會因車輛行駛距離變化而變化，同時城鄉(xiāng)間的道路條件不同，當2個配送節(jié)點都是鄉(xiāng)村節(jié)點時，其單位成本也會不同，公式（4）所示。

（4）

式中：DKE為電車單位距離能耗；DKC為燃油汽車單位距離能耗；gKE為電車單位能耗成本；gKC燃油汽車單位能耗成本；p為農村能耗差異系數(shù)。

1.2.4 碳稅成本

碳稅是一種促進節(jié)能減排的重要手段。碳排放成本=碳排放量×單位碳稅系數(shù)α[4]。鄉(xiāng)村區(qū)域交通設施不完善，與城市相比，路況有一定不足，因此鄉(xiāng)村的碳排放量更高，如公式（5）所示。

（5）

1.2.5 懲罰成本

在配送過程中，客戶滿意度和配送到達時間的隸屬關系函數(shù)式如公式（6）所示。

（6）

根據(jù)客戶滿意度可以計算出配送過程中產生的懲罰成本，如公式（7）所示。

（7）

式中：客戶最大滿意度以時間窗[ETi，LTi]長度的一半為標準，設定客戶可接受最早時間為EETi=ETi-（LTi-ETi）/2，可接受最晚時間為 ELTi=LTi-（LTi-ETi）/2；Si為車輛到達節(jié)點i的時間；μ（Si）為節(jié)點i的客戶滿意度；n為配送客戶數(shù)量；Q為單位滿意度懲罰成本。

2 基于模擬退火的改進多元宇宙算法

標準的多元宇宙算法針對的是連續(xù)性問題，而車輛路徑優(yōu)化問題是典型的離散問題，因此需要對算法進行離散化處理[5]。由于搜索策略以相對最優(yōu)宇宙作為搜索區(qū)域，因此在迭代后期，種群越來越趨于同質化，所選出的最優(yōu)宇宙趨于相似，搜索效率降低，不易跳出局部最優(yōu)。針對以上問題，本文提出了基于模擬退火的改進多元宇宙算法（multi-verse optimizer variation，SAMVO）。

2.1 參數(shù)設定

SAMVO算法迭代采用輪盤賭機制，對排序后的宇宙膨脹率進行選取，并通過黑洞和白洞進行宇宙間的物質交換，如公式（8）所示。

（8）

式中：r1、r2和r3分別為[0，1]間的隨機數(shù)，用于后續(xù)的隨機操作；xkj為通過輪盤賭策略選擇出來的第k個宇宙的第j個分量；NI（Ui）為第i個宇宙的歸一化膨脹率。

設定WEP（Wormhole Existence Probability）為蟲洞存在可能性系數(shù)，定義了宇宙空間內蟲洞存在的可能。TDR（Travelling Distance Rate）代表物體在最優(yōu)宇宙附近蟲洞轉換的距離。二者分別如公式（9）、公式（10）所示。

（9）

（10）

式中：WEPmin與WEPmax分別為0.2與1；l為當前迭代次數(shù)；L為最大迭代次數(shù)；p為隨迭代次數(shù)改變的探測速度，該值越高，算法在局部區(qū)域探測速度越快，為了開發(fā)準確性，設定p=6。

2.2 編碼與解碼

進行編碼時，每個宇宙的編碼代表一條配送路徑的方案。假設有1個配送中心，kc輛燃油汽車，ke輛電車，v個充電樁，m個城市客戶，n個農村客戶，各客戶節(jié)點和配送車輛采用自然數(shù)進行編號且編號固定，離散且唯一。進行編碼時，先對車輛節(jié)點進行隨機排序，再將客戶節(jié)點和充電樁節(jié)點隨機插入，形成初始隨機編碼。例如當kc與ke分別為2，l為1，m與n分別為4時，形成的編碼如圖1所示。

2.3 黑白洞轉移

采用隨機原子操作（交換、插入和轉移操作）[6]，具體操作如下。如果r1≤NI（Ui），就通過輪盤賭策略所選出的較優(yōu)宇宙Uk進行轉移，比較每個Uk和Ui，將第一個不同分量作為操作的起始分量Uia，在該分量后隨機選擇一個分量Uib，對這2個分量進行隨機操作，生成U'i。比較Ui和U'i的適應度膨脹率NI（Ui）與NI（U'i），選取較大者更新為新的Ui。

2.4 關于向最優(yōu)宇宙進行探索

在最優(yōu)解的鄰域進行開發(fā)，結合上述編碼方式制定最優(yōu)宇宙鄰域搜索機制。在最優(yōu)宇宙中隨機選擇一個車輛節(jié)點，對該車輛節(jié)點下的2個客戶節(jié)點進行隨機原子操作，生成新的解。如果更新后解的膨脹率比原解的膨脹率大，就將其替換為新的Ui。以插入操作為例，操作過程如圖2所示。

2.5 關于向較差宇宙進行移動

為避免在探索后期陷入局部最優(yōu)，在搜索機制上結合模擬退火算法的思想和在一定概率下向負面解進行探索，增加了算法的靈活性。如果隨機數(shù)r3≤0.5，就向通過逆序輪盤賭策略所選出的較差宇宙NK進行移動。比較每個MK和Ui，將第一個不同分量作為操作的起始分量Uip，在該分量后隨機選擇一個分量Uiq，對這2個分量進行隨機的原子操作，生成U'i。比較Ui和U'i的適應度膨脹率NI（U），選取較大者作為新的Ui。以反轉操作為例，如圖3所示。

2.6 整體算法步驟

整體算法步驟如下所示。1）初始化種群、WEPmin、WEPmax以及最大迭代次數(shù)等相關參數(shù)。2）計算每個小宇宙的NI（U），用輪盤賭機制（逆輪盤賭機制）選擇較優(yōu)的宇宙?zhèn)€體UK和較差的宇宙NK。3）通過每個個體Ui計算WEP和TDR值，生成隨機數(shù)r1、r2和r3。4）如果r1lt;NI（Ui），就根據(jù)白洞/黑洞轉移規(guī)則生成U'i。比較Ui和U'i的膨脹率，取較大者替代Ui。如果r1≥NI（Ui），就執(zhí)行下一步。如果r2=WEP，就向最優(yōu)宇宙移動原則生成U'i。如果r3≤0.5，向所選出的較差宇宙移動，生成U'i。比較Ui和U'i的膨脹率，取較大者替代Ui。5）如果r2=WEP，則執(zhí)行下一步。6）比較Ui和當前最優(yōu)宇宙Ubest的膨脹率，取較大者替代Ubest。7）如果達到最大迭代次數(shù)，輸出最優(yōu)解，算法結束；否則返回步驟2。

3 算例分析

為驗證模型效果和算法有效性，將Solomon數(shù)據(jù)集進行擴展更新，其中客戶位置信息來自https：//github.com/ShixinXIE/MD-2E-R-VRP[7]，并隨機選取為客戶。假定同一區(qū)域存在40個城市客戶和40個鄉(xiāng)村客戶，算法迭代最大次數(shù)為2000，種群數(shù)為300，其余參數(shù)值參考宋麗英等人的研究設定[8]。利用Python編寫SAMVO算法所構建的模型并進行求解，得到配送路徑和各項成本，配送路徑如圖4所示，配送方案見表1。

為比較改進算法的優(yōu)越性，本文對所構架的模型進行粒子群算法（PSO）、鯨魚算法（WOA）、灰狼算法（GWO）、離散多元宇宙算法（DMVO）以及本文改進算法（SAMVO）的對比試驗。數(shù)據(jù)來自所羅門數(shù)據(jù)集，結果見表2、表3。在不同算例下，SAMVO算法可以較好地求解出總成本，求解能力比MVO等上述算法有明顯提高，平均提升率超過20%。

為了直觀展示迭代過程中成本的變化情況和SAMVO算法的優(yōu)越性，下面以Solomon數(shù)據(jù)集中的new_c201為例，迭代過程如圖5所示。

根據(jù)圖5可知，本文提出改進多元宇宙算法（SAMVO）由于結合了模擬退火算法的思想，迭代前期存在向負面宇宙移動的可能性，因此搜尋速度比其他算法收斂速度慢，但在后期，該機制使搜索過程跳出了局部最優(yōu)的情況，向負面移動的機制優(yōu)勢顯現(xiàn)，隨著迭代次數(shù)增加，結果達到穩(wěn)定，整體損失趨于收斂。

4 結語

本文針對如何降低城鄉(xiāng)混合區(qū)域條件下混合車隊配送成本的問題，以總成本最低為目標函數(shù)，構建了模糊時間窗約束單中心車輛路徑成本模型。并將離散的多元宇宙算法進行了改進，參考模擬退火算法的思想，引入逆序輪盤賭機制，減少陷入局部最優(yōu)的情況。通過本文改進的多元宇宙算法來求解Solomon數(shù)據(jù)集和擴展數(shù)據(jù)集中部分算例，證明了本文算法解決該情況下車輛路徑問題的有效性和優(yōu)越性。

參考文獻

[1]李英，張鵬威，吳一帆.電動汽車/傳統(tǒng)汽車混合車隊車輛配置及路徑優(yōu)化模型[J].系統(tǒng)管理學報，2020，29（3）：522-531.

[2]LI Y，ZHANG P W，WU Y F.Vehicle routing problem with mixed fleet of conventional and electric vehicle[J].Journal of systems amp; management，2020，29（3）：522-531.

[3]ISLAM M A，GAJPAL Y，ELMEKKAWY T Y.Mixed fleet based"green clustered logistics problem under carbonemission cap[J].Sustainable"cities and society，2021，72：103074.

[4]許菱，楊林超，朱文興，等.農村電商物流下無人機與車輛協(xié)同配送路徑優(yōu)化研究[J].計算機工程與應用，2024，60（1）：310-318.

[5]唐慧玲，唐恒書，朱興亮.基于改進蟻群算法的低碳車輛路徑問題研究[J].中國管理科學，2021，29（7）：118-127.

[6]方恒，朱建鴻.基于離散多元宇宙算法的柔性作業(yè)車間調度[J].組合機床與自動化加工技術，2023（10）：174-178.

[7]張強，姜慧清，王穎等.基于離散多元宇宙算法求解車輛路徑問題[J].電子科技大學學報，2021，50（6）：890-898.

[8]謝世鑫，王旭，杜建輝，等.考慮同城配送的多產品多中心兩級物流網絡設計及車輛路徑研究[J].管理工程學報，2023，37（3）：178-190.