基于模擬退火算法的雙目標(biāo)優(yōu)化模型在垃圾收集路徑規(guī)劃中的應(yīng)用研究

摘要：文章針對(duì)城市垃圾車的“距離-時(shí)間”雙目標(biāo)優(yōu)化問(wèn)題，提出了一種基于模擬退火算法和線性加權(quán)法的優(yōu)化模型，旨在同時(shí)優(yōu)化最短行駛距離和最短運(yùn)輸時(shí)間。首先，該研究綜合考慮了站點(diǎn)間的距離、運(yùn)輸時(shí)間、裝載時(shí)間、傾倒時(shí)間和排隊(duì)時(shí)間等多種因素，構(gòu)建了雙目標(biāo)優(yōu)化規(guī)劃模型。其次，選擇模擬退火算法進(jìn)行求解，采用Metropolis準(zhǔn)則和退火過(guò)程，以有效突破局部最優(yōu)解。最終，通過(guò)調(diào)控退火溫度等參數(shù)，確保了算法的有效性與效率。結(jié)果顯示，該模型能夠顯著優(yōu)化垃圾車的總行程和運(yùn)輸時(shí)間，為城市垃圾處理系統(tǒng)的規(guī)劃與調(diào)度提供了堅(jiān)實(shí)的理論基礎(chǔ)。

關(guān)鍵詞：模擬退火算法；線性加權(quán)法；雙目標(biāo)優(yōu)化

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2025）02-0023-03 開(kāi)放科學(xué)（資源服務(wù)） 標(biāo)識(shí)碼（OSID） ：

0 引言

隨著城市化進(jìn)程的加快，垃圾處理已成為城市管理的關(guān)鍵環(huán)節(jié)。垃圾車收集路徑規(guī)劃問(wèn)題引起了大量中外學(xué)者的關(guān)注。明勇等人[1]提出了一種基于改進(jìn)混合蛙跳和GIS的路徑規(guī)劃設(shè)計(jì)，其收斂速度和尋優(yōu)能力非常突出。閆芳等人[2]則將動(dòng)態(tài)模型分解為一系列靜態(tài)模型，通過(guò)粒子群規(guī)劃來(lái)進(jìn)行路徑規(guī)劃設(shè)計(jì)，考慮的因素包括碳排放、車輛裝載能力及二次污染等，較為全面。Nuortio等人[3]的主要貢獻(xiàn)在于提出了GVNT元啟發(fā)式的概念解模型及其成功的實(shí)際應(yīng)用，包括為大型實(shí)際路由問(wèn)題設(shè)計(jì)高效求解方法的若干實(shí)現(xiàn)指南。

在垃圾收集和運(yùn)輸過(guò)程中，提高車輛運(yùn)行效率、降低運(yùn)行成本已成為亟待解決的問(wèn)題。垃圾車的運(yùn)行不僅與站點(diǎn)之間的距離有關(guān)，還受到轉(zhuǎn)運(yùn)時(shí)間、裝載時(shí)間、傾倒時(shí)間和排隊(duì)時(shí)間等多種因素的影響。模擬退火法[4-7]作為一種啟發(fā)式搜索方法，其跳出局部最優(yōu)解的能力在解決復(fù)雜模擬問(wèn)題時(shí)表現(xiàn)出了顯著的性能。基于此，本文討論了在停車場(chǎng)與處理站唯一的情況下，垃圾車“距離-時(shí)間”雙目標(biāo)優(yōu)化的數(shù)學(xué)模型，旨在通過(guò)模擬退火算法找到同時(shí)滿足時(shí)間最短和距離最短的解。

為了建立一個(gè)全面、準(zhǔn)確的數(shù)學(xué)模型，本文首先明確了站間距離和轉(zhuǎn)運(yùn)時(shí)間等基本變量，并在此基礎(chǔ)上構(gòu)建了車輛總運(yùn)行距離和總時(shí)間的計(jì)算公式。與以往研究不同，本文采用線性加權(quán)法[8]將雙目標(biāo)問(wèn)題轉(zhuǎn)化為單一目標(biāo)進(jìn)行優(yōu)化，并通過(guò)數(shù)據(jù)標(biāo)準(zhǔn)化方法，使不同的距離和時(shí)間度量得以在同一尺度上進(jìn)行比較。此外，通過(guò)參數(shù)控制，確保算法在有限時(shí)間內(nèi)收斂至最優(yōu)解。研究成果不僅有助于優(yōu)化垃圾收集和運(yùn)輸過(guò)程，還為其他類似的雙目標(biāo)優(yōu)化問(wèn)題提供了有效的解決思路。

2 雙目標(biāo)優(yōu)化模型建立與求解

2.1 基于路程與時(shí)間雙目標(biāo)最優(yōu)的規(guī)劃模型

在停車場(chǎng)與處理站唯一的情況下，構(gòu)建了雙目標(biāo)最優(yōu)距離-時(shí)間數(shù)學(xué)模型。通過(guò)模擬分解等方法，將多個(gè)影響因素轉(zhuǎn)化為一個(gè)簡(jiǎn)單因素，最終得到滿足時(shí)間和距離最優(yōu)的解。

2.1.1 模型建立

車輛行駛的總距離：

D = Σdij，i = 1，...，13 （1）

式中：D 代表總距離，dij 代表站點(diǎn)i到站點(diǎn)j 之間的距離，包括停車場(chǎng)、收集站和處置站之間的距離，以及其他站點(diǎn)之間的連接距離。

垃圾車在每個(gè)收集點(diǎn)翻轉(zhuǎn)垃圾所需的時(shí)間：

tf = 120 × [ K ] i ＼2 （2）

式中：tf 代表翻桶所用時(shí)間，Ki 代表第i 個(gè)收集點(diǎn)的站點(diǎn)垃圾桶數(shù)量。

處理站最多同時(shí)容納 4 輛車傾倒，故存在以下約束方程：

tf = 90 + Qi，Sci gt; 4 （3）

式中： Sci 為垃圾處理站此時(shí)汽車總數(shù)， Q 為車輛等待前面汽車的時(shí)間。

Q = 900 - Sc （i - 4），i ≥ 5 （4）

車輛站點(diǎn)運(yùn)行此征收時(shí)間：

tp = ts + tf + tr （5）

式中：tp 代表站點(diǎn)花費(fèi)的總時(shí)間；ts 代表站點(diǎn)花費(fèi)的啟停時(shí)間；tr代表補(bǔ)償時(shí)間。

每輛車的總運(yùn)行時(shí)間為：

tBa = tdj +Σln （t ） p + tij + tis + tx + tsd （6）

式中：Ba 為汽車的編號(hào)；tdj 為停車調(diào)查到收集點(diǎn)的時(shí)間；tij 為第i 站到第j 站所需時(shí)間；tx 為垃圾車卸載時(shí)間；

車輛執(zhí)行任務(wù)最長(zhǎng)時(shí)間：

T = max{t } Ba ，a = 1，2，...，13 （7）

式中：T代表實(shí)際行駛總時(shí)長(zhǎng)。

將總路程與時(shí)間的關(guān)系歸一化，將數(shù)據(jù)歸一化為：

時(shí)間-距離雙目標(biāo)建模：

min（0.8L* + 0.2T*） （10）

2.2 模型求解

2.2.1 模擬退火算法（SA）

Metropolis算法是退火過(guò)程的核心，旨在避免陷入局部最優(yōu)解。1953年，Metropolis提出了重要性采樣法。具體而言，Metropolis準(zhǔn)則中，新解是否被接受取決于其優(yōu)劣關(guān)系：若新解優(yōu)于當(dāng)前解，則直接接受；若新解劣于當(dāng)前解，則以由溫度決定的概率接受當(dāng)前解。溫度越高，接受概率越大；溫度越低，接受概率越小[9]。

基于當(dāng)前狀態(tài)x （n）和某一指標(biāo)（如梯度下降或能量） ，狀態(tài)更新為 x （n + 1），系統(tǒng)能量由 E （n）變?yōu)镋（n + 1）。定義系統(tǒng)由x （n + 1）轉(zhuǎn)移至x （n + 1）的接受概率P如下：

如果系統(tǒng)的能量降低，則新?tīng)顟B(tài)的接受概率為1；如果系統(tǒng)的能量增加，則根據(jù)設(shè)定的概率P 進(jìn)行處理：生成一個(gè)在區(qū)間[0，1]內(nèi)均勻分布的隨機(jī)數(shù)ε，若ε 大于P，接受這種狀態(tài)轉(zhuǎn)移；否則，拒絕該轉(zhuǎn)移。接著進(jìn)行下一步，重復(fù)上述過(guò)程。概率P 的大小與能量變化量和溫度T之間的關(guān)系有關(guān)，如圖1所示。

2.2.2 模擬退火參數(shù)調(diào)整

模擬退火算法以Metropolis算法為基礎(chǔ)，但在不調(diào)整參數(shù)的情況下使用該算法可能會(huì)導(dǎo)致優(yōu)化搜索速度過(guò)慢。為確保算法在合理的時(shí)間范圍內(nèi)達(dá)到穩(wěn)定狀態(tài)，必須謹(jǐn)慎設(shè)置控制其穩(wěn)定的參數(shù)。在上述公式中，可調(diào)參數(shù)用T表示。若T設(shè)置過(guò)高，退火過(guò)程將過(guò)快，可能導(dǎo)致在局部最優(yōu)解時(shí)過(guò)早終止；反之，如果T設(shè)置過(guò)低，計(jì)算時(shí)間將會(huì)增加。在實(shí)踐中，退火溫標(biāo)被用來(lái)調(diào)節(jié)退火過(guò)程，最初T值較大，隨著退火過(guò)程的進(jìn)行，T值逐漸降低。

1） 起始溫度越高，得到高效率的解決方案的概率就會(huì)越高，當(dāng)然所需要的時(shí)間周期也就越長(zhǎng)。因而起始溫度 T（0） 應(yīng)該選得足夠高，以便接受所有的轉(zhuǎn)移狀態(tài)。

2） 指數(shù)式下降是退火速率中最便捷的下降方式：

T （n） = λT （n），n = 1，2，3，... （12）

式中：λ 為一個(gè)介于0.8到0.99之間的正數(shù)。對(duì)于每個(gè)溫度，都需要進(jìn)行符合條件的轉(zhuǎn)移嘗試。指數(shù)下降的穩(wěn)定速率相對(duì)較慢，其他的下降方式如下：

3） 最終溫度。退火過(guò)程的完成可以定義為在若干次更新迭代中沒(méi)有新?tīng)顟B(tài)可供更新，或未達(dá)到預(yù)先設(shè)定的條件閾值。

2.2.3 模擬退火的步驟

目標(biāo)函數(shù)、解空間和初始解三個(gè)部分是模擬退火算法的基本組成部分，圖2詳細(xì)展示了其算法流程[10]。

初始化：設(shè)定起始溫度T，初始解狀態(tài)為S，以及每個(gè)溫度值對(duì)應(yīng)的迭代次數(shù)L；

對(duì)k=1，…，L執(zhí)行第（3）至第（6）步；

生成新解S'；

計(jì)算增量 ΔT = C （S'） - C （S），其中 C（S）為代價(jià)函數(shù)；

如果ΔT lt; 0，則接受S'作為新的當(dāng)前解；否則，以概率exp （-Δ T／T"） 接受S'作為新的當(dāng)前解；

當(dāng)滿足停止條件時(shí)，輸出當(dāng)前解作為最優(yōu)解，程序結(jié)束。停止條件通常是在連續(xù)若干個(gè)新解未被接受時(shí)，算法停止；當(dāng)T 逐漸減小至0時(shí)，返回第2步。

模擬退火算法產(chǎn)生的新解和接受解的步驟如下：

首先，在現(xiàn)有解的基礎(chǔ)上，利用生成函數(shù)在解空間中構(gòu)建一個(gè)新的解。為了簡(jiǎn)化后續(xù)的計(jì)算和驗(yàn)證過(guò)程，并縮短算法的執(zhí)行時(shí)間，通常會(huì)采用一些簡(jiǎn)單的變換方法來(lái)生成新的解決方案。需要強(qiáng)調(diào)的是，所采用的變換方法將決定當(dāng)前方案的基本結(jié)構(gòu)，從而影響收斂穩(wěn)定方案的選擇。其次，計(jì)算新方案所帶來(lái)的目標(biāo)函數(shù)差異。由于目標(biāo)函數(shù)的差異僅受到調(diào)整部分的影響，因此在進(jìn)行計(jì)算時(shí)，采用增量計(jì)算法的優(yōu)先級(jí)最高。在絕大多數(shù)情況下，這種方法是計(jì)算目標(biāo)函數(shù)差異的最有效方式。

再次是考慮新解的可接受性來(lái)進(jìn)行判斷，接受的標(biāo)準(zhǔn)是其依據(jù)。其中，最常用的接受標(biāo)準(zhǔn)是Metropo?lis準(zhǔn)則：當(dāng)ΔT 小于0時(shí)，接受S'作為新的當(dāng)前解S；如果ΔT≥0，則以概率exp （-Δ T／T"） 來(lái)決定是否接受S'作為新的當(dāng)前解S。

最后，如果新方案被接受，則用新方案替代當(dāng)前方案。接著，執(zhí)行當(dāng)前方案中與新方案生成時(shí)間相對(duì)應(yīng)的轉(zhuǎn)換部分，并調(diào)整目標(biāo)函數(shù)值，從而完成一次迭代，進(jìn)入下一輪試驗(yàn)。如果新方案被拒絕，則繼續(xù)基于原有的當(dāng)前方案進(jìn)行下一輪求解。模擬退火算法不受初始值的影響，所得到的解與起始狀態(tài)S（即算法迭代的起始點(diǎn)） 無(wú)關(guān)。該算法具有漸進(jìn)回收性，理論上證明其以1的概率回收到整體最優(yōu)解。此外，模擬退火算法還具備并行處理的能力[11-13]。

2.2.4 算法求解流程

采用MATLAB語(yǔ)言編寫(xiě)程序，對(duì)上述內(nèi)容進(jìn)行模擬退火算法優(yōu)化，仿真過(guò)程中所需的控制參數(shù)設(shè)計(jì)如下：

1） 解空間。在解空間中所有固定的起始點(diǎn)及最終點(diǎn)的循環(huán)排列集合可用S 表示，得到D = {（π1，π2，...，π72）|π1 = 1，（π2，π3，...，π70 ）{1，2，...，70}} 的 循環(huán)排列，π71 = 71，π72 = 72。 其中，每一個(gè)循環(huán)排列表示70個(gè)收集點(diǎn)的回收路徑。

2） 目標(biāo)函數(shù)。目標(biāo)函數(shù)（或稱代價(jià)函數(shù)）為車輛所有的路徑長(zhǎng)度。要求：

進(jìn)行一次迭代由三個(gè)步驟組成。

3） 新解的產(chǎn)生。假設(shè)上一步迭代的解為：

π1... πu - 1πuπu + 1... πv - 1πvπv + 1... πu - 1πuπu + 1... π72

①2交換法。選擇任意兩個(gè)序號(hào)u和v，將它們之間的順序交換，使整體變?yōu)槟嫘颍藭r(shí)得到的新路徑為：

π1... πu - 1πvπv - 1... πu + 1πuπv + 1... π102

②3變換法。選擇任意的序號(hào)u、v 和w，將u 與v之間的路徑插入到w 之后，得到的新路徑為：

π1... πu - 1πv + 1... πwπu... πvπw + 1... π102

4） 代價(jià)函數(shù)差。根據(jù)第一步，此時(shí)路徑差可用下述公式表示：

Δf = （dπu - 1，πv ） + dπu，πv + 1 - （dπu - 1，πu ） + dv，πv + 1 （16）

5） 接受準(zhǔn)則：

如果f lt; 0，則接受新的路徑；否則，以概率exp （-Δf ／T） 來(lái)決定是否接受新的路徑。具體操作是生成一個(gè)在[0，1]區(qū)間內(nèi)均勻分布的隨機(jī)數(shù)rand，如果rand小于exp （-Δf ／T），則進(jìn)行降溫。降溫時(shí)使用選定的降溫系數(shù)α，新的溫度T將被設(shè)定為αT（其中T為上一步迭代的溫度） ，這里選擇α = 0.997。

6） 結(jié)束條件：判斷整個(gè)退火過(guò)程是否完成，可以通過(guò)預(yù)先設(shè)定的停止溫度e = 0.01°來(lái)判斷。如果T 小于e，流程結(jié)束，輸出結(jié)果。

2.3 模型求解結(jié)果

利用雙目標(biāo)規(guī)劃與模擬退火算法（SA） 的優(yōu)化結(jié)果如表1所示。

所有車輛全部完成時(shí)間為6 805秒。

3 結(jié)論

本文聚焦于垃圾車在停車場(chǎng)與處理站唯一情境下的“距離-時(shí)間”雙目標(biāo)最優(yōu)規(guī)劃問(wèn)題。通過(guò)構(gòu)建數(shù)學(xué)模型，綜合考慮站間距離、運(yùn)輸時(shí)間、本征時(shí)間、傾倒時(shí)間及排隊(duì)時(shí)間等多個(gè)關(guān)鍵因素，采用模擬退火算法，將雙目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單一目標(biāo)，并經(jīng)過(guò)數(shù)據(jù)歸一化處理，實(shí)現(xiàn)時(shí)間與路程的綜合權(quán)衡。研究結(jié)果表明，合理規(guī)劃可使垃圾車實(shí)現(xiàn)“時(shí)間-距離”最優(yōu)解，顯著提升垃圾處理效率，對(duì)城市垃圾處理系統(tǒng)的優(yōu)化設(shè)計(jì)具有重要指導(dǎo)意義。該研究具有極強(qiáng)的實(shí)踐性，能夠應(yīng)用于實(shí)際的垃圾收集車輛路徑規(guī)劃中，提高效率，降低成本，減少污染，具有顯著的社會(huì)效益。在后續(xù)研究中，結(jié)合更多先進(jìn)學(xué)習(xí)算法，并考慮更多現(xiàn)實(shí)因素，例如車輛容量限制、交通流量等，有望進(jìn)一步完善模型，提高模型的實(shí)用性。

參考文獻(xiàn)：

[1] 明勇，王華軍.基于改進(jìn)混合蛙跳和GIS的城市垃圾車回收路徑優(yōu)化設(shè)計(jì)[J]. 計(jì)算機(jī)測(cè)量與控制，2014，22（12）：4054-4057.

[2] 閆芳，鄧德萍，柴福良.基于智能垃圾桶的垃圾分類動(dòng)態(tài)收運(yùn)路徑優(yōu)化問(wèn)題研究[J].計(jì)算機(jī)應(yīng)用研究，2022，39（12）：3620-3625.

[3] NUORTIO T，KYT?JOKI J，NISKA H，et al.Improved route plan?ning and scheduling of waste collection and transport[J].ExpertSystems with Applications，2006，30（2）：223-232.

[4] 劉婧.基于改進(jìn)模擬退火算法的船舶物流配送中心選址研究[J].艦船科學(xué)技術(shù)，2020，42（16）：199-201.

[5] 冉昊杰，王宏智.基于改進(jìn)模擬退火算法的生鮮農(nóng)產(chǎn)品配送中心選址[J].計(jì)算機(jī)與現(xiàn)代化，2022（10）：36-40.

[6] 于琪，張靜.融合模擬退火參數(shù)的自適應(yīng)遺傳算法求解柔性作業(yè)車間調(diào)度問(wèn)題[J].電腦與信息技術(shù)，2024，32（3）：12-16.

[7] 任小強(qiáng).基于遺傳和模擬退火算法的電動(dòng)汽車充電調(diào)度策略研究[J].蘭州職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2024，40（3）：73-77.

[8] 連燕.基于加權(quán)和的多目標(biāo)優(yōu)化法在小流域治理中的研究[J].云南水力發(fā)電，2022，38（8）：66-70.

[9] 張廣智，趙晨，涂奇催，等.基于量子退火Metropolis-Hastings 算法的疊前隨機(jī)反演[J].石油地球物理勘探，2018，53（1）：153-160.

[10] 陳科勝，鮮思東，郭鵬.求解旅行商問(wèn)題的自適應(yīng)升溫模擬退火算法[J].控制理論與應(yīng)用，2021，38（2）：245-254.

[11] 羅渝東.基于改進(jìn)模擬退火算法的臺(tái)北市路劃構(gòu)建方法研究[J].時(shí)空信息學(xué)報(bào)，2024，31（2）：240-247.

[12] 孟浩德，吳征天，吳聞笛，等.基于改進(jìn)模擬退火算法的滅火小車多目標(biāo)路徑規(guī)劃[J]. 計(jì)算機(jī)與數(shù)字工程，2024，52（2）：394-398.

[13] 朱昱穎，金秋.基于模擬退火算法的電動(dòng)汽車電池配送路徑優(yōu)化[J].科技與創(chuàng)新，2024（3）：31-33，37.

【通聯(lián)編輯：張薇】