基于模擬退火算法的雙目標優化模型在垃圾收集路徑規劃中的應用研究

摘要：文章針對城市垃圾車的“距離-時間”雙目標優化問題，提出了一種基于模擬退火算法和線性加權法的優化模型，旨在同時優化最短行駛距離和最短運輸時間。首先，該研究綜合考慮了站點間的距離、運輸時間、裝載時間、傾倒時間和排隊時間等多種因素，構建了雙目標優化規劃模型。其次，選擇模擬退火算法進行求解，采用Metropolis準則和退火過程，以有效突破局部最優解。最終，通過調控退火溫度等參數，確保了算法的有效性與效率。結果顯示，該模型能夠顯著優化垃圾車的總行程和運輸時間，為城市垃圾處理系統的規劃與調度提供了堅實的理論基礎。

關鍵詞：模擬退火算法；線性加權法；雙目標優化

中圖分類號：TP311 文獻標識碼：A

文章編號：1009-3044（2025）02-0023-03 開放科學（資源服務） 標識碼（OSID） ：

0 引言

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

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

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

2 雙目標優化模型建立與求解

2.1 基于路程與時間雙目標最優的規劃模型

在停車場與處理站唯一的情況下，構建了雙目標最優距離-時間數學模型。通過模擬分解等方法，將多個影響因素轉化為一個簡單因素，最終得到滿足時間和距離最優的解。

2.1.1 模型建立

車輛行駛的總距離：

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

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

垃圾車在每個收集點翻轉垃圾所需的時間：

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

式中：tf 代表翻桶所用時間，Ki 代表第i 個收集點的站點垃圾桶數量。

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

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

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

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

車輛站點運行此征收時間：

tp = ts + tf + tr （5）

式中：tp 代表站點花費的總時間；ts 代表站點花費的啟停時間；tr代表補償時間。

每輛車的總運行時間為：

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

式中：Ba 為汽車的編號；tdj 為停車調查到收集點的時間；tij 為第i 站到第j 站所需時間；tx 為垃圾車卸載時間；

車輛執行任務最長時間：

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

式中：T代表實際行駛總時長。

將總路程與時間的關系歸一化，將數據歸一化為：

時間-距離雙目標建模：

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

2.2 模型求解

2.2.1 模擬退火算法（SA）

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

基于當前狀態x （n）和某一指標（如梯度下降或能量） ，狀態更新為 x （n + 1），系統能量由 E （n）變為E（n + 1）。定義系統由x （n + 1）轉移至x （n + 1）的接受概率P如下：

如果系統的能量降低，則新狀態的接受概率為1；如果系統的能量增加，則根據設定的概率P 進行處理：生成一個在區間[0，1]內均勻分布的隨機數ε，若ε 大于P，接受這種狀態轉移；否則，拒絕該轉移。接著進行下一步，重復上述過程。概率P 的大小與能量變化量和溫度T之間的關系有關，如圖1所示。

2.2.2 模擬退火參數調整

模擬退火算法以Metropolis算法為基礎，但在不調整參數的情況下使用該算法可能會導致優化搜索速度過慢。為確保算法在合理的時間范圍內達到穩定狀態，必須謹慎設置控制其穩定的參數。在上述公式中，可調參數用T表示。若T設置過高，退火過程將過快，可能導致在局部最優解時過早終止；反之，如果T設置過低，計算時間將會增加。在實踐中，退火溫標被用來調節退火過程，最初T值較大，隨著退火過程的進行，T值逐漸降低。

1） 起始溫度越高，得到高效率的解決方案的概率就會越高，當然所需要的時間周期也就越長。因而起始溫度 T（0） 應該選得足夠高，以便接受所有的轉移狀態。

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

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

式中：λ 為一個介于0.8到0.99之間的正數。對于每個溫度，都需要進行符合條件的轉移嘗試。指數下降的穩定速率相對較慢，其他的下降方式如下：

3） 最終溫度。退火過程的完成可以定義為在若干次更新迭代中沒有新狀態可供更新，或未達到預先設定的條件閾值。

2.2.3 模擬退火的步驟

目標函數、解空間和初始解三個部分是模擬退火算法的基本組成部分，圖2詳細展示了其算法流程[10]。

初始化：設定起始溫度T，初始解狀態為S，以及每個溫度值對應的迭代次數L；

對k=1，…，L執行第（3）至第（6）步；

生成新解S'；

計算增量 ΔT = C （S'） - C （S），其中 C（S）為代價函數；

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

當滿足停止條件時，輸出當前解作為最優解，程序結束。停止條件通常是在連續若干個新解未被接受時，算法停止；當T 逐漸減小至0時，返回第2步。

模擬退火算法產生的新解和接受解的步驟如下：

首先，在現有解的基礎上，利用生成函數在解空間中構建一個新的解。為了簡化后續的計算和驗證過程，并縮短算法的執行時間，通常會采用一些簡單的變換方法來生成新的解決方案。需要強調的是，所采用的變換方法將決定當前方案的基本結構，從而影響收斂穩定方案的選擇。其次，計算新方案所帶來的目標函數差異。由于目標函數的差異僅受到調整部分的影響，因此在進行計算時，采用增量計算法的優先級最高。在絕大多數情況下，這種方法是計算目標函數差異的最有效方式。

再次是考慮新解的可接受性來進行判斷，接受的標準是其依據。其中，最常用的接受標準是Metropo?lis準則：當ΔT 小于0時，接受S'作為新的當前解S；如果ΔT≥0，則以概率exp （-Δ T／T"） 來決定是否接受S'作為新的當前解S。

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

2.2.4 算法求解流程

采用MATLAB語言編寫程序，對上述內容進行模擬退火算法優化，仿真過程中所需的控制參數設計如下：

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

2） 目標函數。目標函數（或稱代價函數）為車輛所有的路徑長度。要求：

進行一次迭代由三個步驟組成。

3） 新解的產生。假設上一步迭代的解為：

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

①2交換法。選擇任意兩個序號u和v，將它們之間的順序交換，使整體變為逆序，此時得到的新路徑為：

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

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

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

4） 代價函數差。根據第一步，此時路徑差可用下述公式表示：

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

5） 接受準則：

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

6） 結束條件：判斷整個退火過程是否完成，可以通過預先設定的停止溫度e = 0.01°來判斷。如果T 小于e，流程結束，輸出結果。

2.3 模型求解結果

利用雙目標規劃與模擬退火算法（SA） 的優化結果如表1所示。

所有車輛全部完成時間為6 805秒。

3 結論

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

參考文獻：

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

[2] 閆芳，鄧德萍，柴福良.基于智能垃圾桶的垃圾分類動態收運路徑優化問題研究[J].計算機應用研究，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].艦船科學技術，2020，42（16）：199-201.

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

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

[7] 任小強.基于遺傳和模擬退火算法的電動汽車充電調度策略研究[J].蘭州職業技術學院學報，2024，40（3）：73-77.

[8] 連燕.基于加權和的多目標優化法在小流域治理中的研究[J].云南水力發電，2022，38（8）：66-70.

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

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

[11] 羅渝東.基于改進模擬退火算法的臺北市路劃構建方法研究[J].時空信息學報，2024，31（2）：240-247.

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

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

【通聯編輯：張薇】