基于改進(jìn)多元宇宙算法的配送路徑優(yōu)化研究

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

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

中圖分類號(hào)：F 25" " " " " " 文獻(xiàn)標(biāo)志碼：A

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

1 問題描述與模型構(gòu)建

1.1 問題描述

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

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

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

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

1.2.1 固定成本

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

（2）

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

1.2.2 行駛成本

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

（3）

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

1.2.3 能耗成本

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

（4）

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

1.2.4 碳稅成本

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

（5）

1.2.5 懲罰成本

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

（6）

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

（7）

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

2 基于模擬退火的改進(jìn)多元宇宙算法

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

2.1 參數(shù)設(shè)定

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

（8）

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

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

（9）

（10）

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

2.2 編碼與解碼

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

2.3 黑白洞轉(zhuǎn)移

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

2.4 關(guān)于向最優(yōu)宇宙進(jìn)行探索

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

2.5 關(guān)于向較差宇宙進(jìn)行移動(dòng)

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

2.6 整體算法步驟

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

3 算例分析

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)

[1]李英，張鵬威，吳一帆.電動(dòng)汽車/傳統(tǒng)汽車混合車隊(duì)車輛配置及路徑優(yōu)化模型[J].系統(tǒng)管理學(xué)報(bào)，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]許菱，楊林超，朱文興，等.農(nóng)村電商物流下無人機(jī)與車輛協(xié)同配送路徑優(yōu)化研究[J].計(jì)算機(jī)工程與應(yīng)用，2024，60（1）：310-318.

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

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

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

[8]謝世鑫，王旭，杜建輝，等.考慮同城配送的多產(chǎn)品多中心兩級(jí)物流網(wǎng)絡(luò)設(shè)計(jì)及車輛路徑研究[J].管理工程學(xué)報(bào)，2023，37（3）：178-190.