基于混合遺傳算法的城市固體廢棄物運輸路徑優化研究

劉 華，武 峰（西安建筑科技大學 管理學院，陜西 西安 710055）

0 引言

隨著城市化進程不斷推進，城市生活固體廢棄物產生量持續增長，同時居民的環保和健康意識也不斷加強，如何管理城市生活固體廢棄物已經成為居民和政府關注的重要問題，也受到了學術界的廣泛關注[1]。生活固體廢棄物的運輸環節作為城市生活固體廢棄物管理的重要組成部分，對其進行優化不僅可以提高廢棄物的回收處理速度以及降低處理成本，而且能有效地解決運輸過程中由于粗放運輸方式所導致的一系列環境問題，同時也可為有關部門相關決策提供理論指導。車輛路徑優化問題（Vehicle Routing Problem，VRP）正是固體廢棄物運輸路徑研究的核心問題，最早是由Dantzig 和Ramser 提出的，問題可描述為：有一個起點和若干個客戶點，在已知客戶需求以及客戶位置的條件下，規劃最優路徑，車輛從起點出發遍歷所有客戶點后回到起點，并使得總距離最短[2]。在城市生活固體廢棄物運輸系統中，廢棄物回收站可以看為起點，垃圾產生點為客戶點。在廢棄物運輸過程中，城市處理能力及其政策法規對運輸時間進行限制，即運輸必須在廢棄物收集點的時間窗（Time Windows）內進行。由此在傳統VRP 的問題上引出了帶時間窗的車輛路徑問題（Vehicle Routing Problem Time Windows，WRPTW）。

VRPTW 問題屬于NP-hard 問題，同時由于約束條件復雜，隨著客戶數目的增加，求解的難度較大。算法的優劣將直接影響求解的效率和質量，因此學者一直致力于尋找更高效的求解算法。針對于VRPTW 問題。Orivalde S.Silva Júnior 等利用多重蟻群系統（MACS）和隨機變量鄰域下降（RVND）提出了MACS-RVND 算法[3]。Raúl Ba?os 等提出了一種基于模擬退火的多目標優化算法——多溫度Pareto 模擬退火算法（MT-PSA）[4]。Konstantakopoulos Grigorios D 等提出了一多目標優化的大規模鄰域搜索算法（MOLNS）[5]。孫滬增等針對蟻群算法局部搜索能力不足以及容易陷入早熟的缺點，通過改進的狀態轉移規則并多種局部搜索算子來改進蟻群算法[6]。陳久梅等針對開放式帶時間窗問題，設計了變鄰域搜索算法，擁有較好的收斂性和穩定性[7]。李珺等利用貪婪插入法構建初始解，在細菌覓食算法中引入了大鄰域搜索方法Removal 算子，擴大了求解算法的搜索空間[8]。張建同等針對模擬退火算法求解VRPTW 問題時容易早熟的問題，在算法中引入了變鄰域搜索算法提出了SAVN，實踐證明添加后能夠顯著提升算法跳出局部最優解的能力[9]。張瑾等對客戶點按其所在位置進行聚類分析，在蝙蝠算法中引入了變步長搜索策略和兩元素優化方法進行局部搜索，提高算法的求解效率[10]。張曉楠等通過在運用簡化的變鄰域搜索進行局部開發，引入鄰域半徑減少策略提出了混合Memetic 算法用于求解VRPTW 問題，研究表明算法能夠搜索到更好的路徑[11]。黃震等在蟻群算法中將遺傳算法中的交叉、變異機制提出了混合遺傳算法，用于提高算法的求解效率[12]。何小鋒等通過定義人工螞蟻的轉移概率，增加量子比特啟發式因子，以及用量子旋轉門實現信息素更新提出了量子蟻群算法（QACA），研究表明能夠提高算法的全局搜索能力[13]。

總體來看，元啟發式算法當前擁有較為豐富的研究成果，相較于精確式算法和啟發式算法擁有更好的求解效率，而且更適合大規模求解。遺傳算法（GA）是模擬生物進化過程，通過選擇、交叉和變異機制來實現最優解的探索，同時遺傳算法也被廣泛應用于求解VRPTW 問題，然而遺傳算法同時存在局部搜索能力不足，過早陷入局部最優的缺點，當問題規模增大或約束增加時，往往不能得到好的結果。變鄰域搜索算法（VNS）則是采用多種鄰域變化，可以和其他元啟發式算法進行結合來提升算法的局部搜索能力，提高求解效率。因此本文將VNS 算法中鄰域搜索與GA 算法進行結合，提出混合遺傳算法用于求解VRPTW 問題。

1 城市固體廢棄物運輸路徑優化模型

本問題可描述為有1 個廢棄物回收站0，和n 個廢棄物產生點，可定義為一個無向連通圖G=（V,L），其中V=｛0,1 ,…,n ｝為節點，其中0 為中轉中心，V/0 為收集點。E 為連接節點的邊集合，E=｛（i,j）|i,j∈V,i≠j ｝。中轉中心有K 輛運輸車輛，車輛的最大裝載能力為Q，每個收集點有確定廢棄物處理量di，每個收集點只能由一輛運輸車完成收集，同時每輛車只能服務一條路徑，運輸車輛必須在廢棄物產生點的時間窗內進行配送。根據以上對VRPTW 問題的描述，可構建數學模型如下：

式（1）為目標函數，其中第一部分為車輛固定成本，主要取決于車輛的使用數目，第二部分為可變成本，與車輛的行駛距離有關，兩者之和為車輛的總成本費用。式（2）、式（3）表示車輛從廢棄物回收點出發最終返回回收點。式（4）表示廢棄物產生點i 只接受一輛車的配送服務。式（5）表示車輛運輸服務必須在廢棄物產生點的時間窗內進行。式（6）是用于確保運輸服務的連續性，其中M 為一個大的正值。式（7）為車輛載重約束，式（8）為0～1 約束。變量具體含義如表1 所示。

表1 變量符號說明

2 算法設計

考慮到遺傳算法的缺陷，本文對遺傳算法做出以下改進。一是引入自適應交叉變異和最優個體保留策略來提升算法的求解效率。二是在變異算子中，引入變鄰域搜索增強算法的局部搜索能力。算法流程如圖1 所示。

圖1 算法流程圖

2.1 初始化種群

初始解能夠直接影響算法的求解效率，隨機生成解能夠豐富解集空間，是較為常用的初始化種群方法，然而本文研究的VRPTW 問題會受到車輛載重約束和服務時間窗約束，如果選擇隨機初始化種群則會不可避免地產生大量的無效解。因此，本文采用遍歷廢棄物產生點的方法，首先隨機生成廢棄物產生點序列C，以載重約束為主約束，將產生點c1,c2,…,cn依次添加到車輛ki行駛的路徑節點中，當超過車輛k 的最大載重時，此時新派一輛車，直到將所有收集點都添加到路徑中，與此同時將每條路徑內的收集點的順序進行調整，通過計算車輛到達的收集點時間，并與廢棄物產生點的時間窗進行對比從而完成路線內調整，當難以滿足條件時，則新增車輛。這樣既能夠保證初始解的有效性，提高算法的效率，同時采用隨機序列又能夠兼顧種群多樣性，提高搜索空間。本文的染色體編碼采用整數編碼的方式，以8 個垃圾收集點節點為例，如圖2 所示。

圖2 編碼方式

其中節點9 和節點10 為虛擬的廢棄物回收站，作為不同車輛路徑的分界，故車輛1 的行駛路徑為：0→2→4→1→3→0；車輛2 的行駛路徑為：0→5→7→0；車輛3 的行駛路徑為：0→6→8→0。

2.2 適應度函數

適應度作為個體質量的衡量標準，與個體被選擇的概率成正相關關系。由于在求解過程中難以確保滿足時間窗約束和載重量約束，因此采用懲罰函數的方法用來解決違反約束的問題。分別建立時間窗約束懲罰函數T（s）和載重約束懲罰函數Q（s）并與目標函數中的總成本進行加和。將其倒數作為求解過程中的適應度函數。

時間窗約束懲罰函數：

其中：ti為到達收集點i 的時間，ei和li分別為廢棄物產生點i 的左右時間窗，w1和w2為早到和晚到的懲罰參數。

載重約束懲罰函數：

其中：di為收集點i 的廢棄物產生量，Q 為車輛的最大載重量，w3為超載懲罰參數。

2.3 選擇算子

選擇操作是從種群中選擇適應度高的個體產生新群體的過程，選擇出良好的個體形成新的種群能夠提高收斂速度。輪盤賭法、錦標賽法是較為常見的選擇算子，已有研究表明錦標賽選擇策略比輪盤賭選擇策略具有更好的通用性，且性能更優[14]。因此本文采用二元錦標賽法，具體操作為從種群中隨機選擇一對個體，通過對比兩者的適應度，選擇適應度高的個體進入下一代，剔除重復個體形成新的種群。

2.4 交叉算子

交叉算子能夠提高遺傳算法的全局搜索能力，是指將兩個個體中的部分結構進行替換完成重組，生成兩個新的個體。本文采用部分匹配交叉（PMX），具體操作為隨機生成兩個交叉點，交換兩條染色體的交叉片段，同時刪除染色體中的重復遍歷點。將重復遍歷點重新插入染色體，如圖3 所示。

圖3 交叉算子

2.5 變異算子

遺傳算法中變異算子能夠提高算法的局部搜索能力，避免算法陷入局部最優。本文采用變鄰域搜索（VNS）來完成遺傳算法中的變異操作，采用Insert、Swap 和Reverse 三個搜索算子進行變鄰域搜索。Insert 算子是隨機選擇兩個節點，將第一個節點插入到第二節點。Swap 算子是隨機選擇兩個不同的節點，將其交換位置。Reverse 算子是逆轉兩個位置之間所有城市的順序。具體如圖4、圖5、圖6 所示。

圖4 Insert 算子

圖5 Swap 算子

圖6 Reverse 算子

本文采用輪盤賭法來隨機選擇鄰域，每當完成一個鄰域搜索后再隨機選擇下一個鄰域進行搜索。每當完成一次鄰域搜索，將當前解與當前最優解進行對比。為了進一步提高算法的效率避免因陷入局部最優，導致算法將無法跳出當前最優解。因此本文借鑒模擬退火算法的Metropolis 準則，如果能夠以一定概率接受比局部最優解的稍差的解將有助于算法跳出局部最優解。計算公式如式（11）所示。

其中：f（Scurr）為當前解的目標值，f（Snew）為新解的目標值，k 為當前鄰域的迭代次數，Kmax為最大鄰域最大迭代次數，P 為接受新解的概率。

局部搜索流程如圖7 所示。

圖7 局部搜索流程圖

2.6 自適應交叉和變異概率

標準遺傳算法中，交叉概率和變異概率一般被設為定值。為了提高求解速率，在迭代前期，通常可以設置較大的交叉概率來增強算法的全局搜索能力，提高搜索速度，而迭代后期，較低的交叉概率和較高的變異概率能夠減少對最優解的破壞，同時增加算法的局部搜索能力。相比于常規的交叉變異概率，自適應交叉、變異可以算法的進程動態的調整其概率。基于以上分析，本文參考文獻[15]，設置了自適應交叉和變異概率，計算公式如下所示。

其中：Pc_max和Pc_min分別是交叉概率區間的最大值和最小值，Pm_max和Pm_min分別為變異概率區間的最大值和最小值，f 為個體適應度值，f'為進行交叉父本中最優個體的適應度值，fmax前種群中最優個體的適應度，favg為當前種群中的平均適應度。

2.7 最優個體保留策略

為了防止種群中的優秀個體在迭代過程中遭到破壞，本文采用最優個體保留策略，如式（14）所示。在迭代過程中將第n-1 代種群中最優個體I 進行復制保留，如果經過交叉、變異等操作后，此時生成新的個體I，如果此時f（I）＞f（I'），則用個體I 替換個體I'最優個體保留策略能夠在一定程度上保護有效基因，提高算法的計算效率，同時也盡可能避免了對遺傳法則的破壞。

3 算例設計

3.1 算法驗證

本文選擇Solomen 算例中7 個標準例題對本文提出GA_VNS 算法進行測試，本文設置種群為150，最大迭代次數為250。其中對混合遺傳算法設置Pc_max和Pc_min為0.9 和0.5，Pm_max和Pm_min為0.2 和0.02。算例求解結果如表2 所示。

表2 算例求解結果

分析結果表明，相較于標準遺傳算法，本文所提出的GA_VNS 能夠得到更優的求解結果，在求解R101-25 例題時具有顯著的效果，R101-25 迭代過程如圖8 所示，R101-25 最優路線圖如圖9 所示。由于算法中的參數設置是由多次實驗得出，因此求解大規模算例仍存在一定的改進空間。

圖8 R101-25 迭代過程圖

圖9 R101-25 最優路線圖

3.2 算例設計

某廢棄物回收站坐標為（30,30），共有4 輛廢棄物運輸車，每輛車最大載重為150。該處理點需要收運周圍20 個廢棄物產生點所產生的垃圾，假設單位用車成本為200，單位距離的成本為30。廢棄物回收站及各廢棄物產生點具體信息如表3 所示。為了方便計算，將兩個節點的直線距離作為兩點的路程。

表3 廢棄物回收站及產生點信息表

在本算例中設置最大迭代次數為250，設置種群為150，設置Pc_max為0.9，Pc_min為0.5，Pm_max為0.2，Pm_min為0.02。根據以上條件，求得結果如表4 所示。經過驗證，三條運輸路徑均滿足收集點的時間窗約束和車輛載重約束，因此驗證了本算法在城市生活固體廢棄物運輸系統問題中的有效性。本算例迭代過程和最優配送路線如圖10 和圖11 所示。

圖10 迭代過程圖

表4 算例求解結果

4 總結與展望

本文以總運輸費用最小為優化目標提出了城市生活固體廢棄物運輸路線優化模型，進而提出了一種混合遺傳算法（GA_VNS），將變鄰域搜索的思想和遺傳算法進行結合，并采用了Swap、Insertion 和Reverse 三種鄰域搜索算子對遺傳算法的變異算子進行改進，同時采用模擬退火算法中的Metropolis 判定規則用于更新鄰域搜索的最優解，并采用自適應的交叉變異概率和最優個體保留策略，用于提高遺傳算法的局部搜索能力，有助于算法跳出局部最優。

實驗結果表明，與標準遺傳算法相比，本文所提出的混合遺傳算法擁有更好的求解效率，能夠得到比遺傳算法得到更優的配送路徑。從實驗結果來看，該算法能夠快速找出小規模問題的最優解，對于大規模問題的求解由于實驗中算法參數是經過多次實驗得到，因此離最優解仍存在一定的差距。對于后續研究將繼續從鄰域搜索的角度入手，設置鄰域的搜索算子、動態調整鄰域搜索的最大搜索次數，以及自適應的Metropolis 判別準則將是以后研究的重要工作。