基于混合遺傳算法的城市固體廢棄物運(yùn)輸路徑優(yōu)化研究

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

0 引言

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

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

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

1 城市固體廢棄物運(yùn)輸路徑優(yōu)化模型

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

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

表1 變量符號說明

2 算法設(shè)計(jì)

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

圖1 算法流程圖

2.1 初始化種群

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

圖2 編碼方式

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

2.2 適應(yīng)度函數(shù)

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

時(shí)間窗約束懲罰函數(shù)：

其中：ti為到達(dá)收集點(diǎn)i 的時(shí)間，ei和li分別為廢棄物產(chǎn)生點(diǎn)i 的左右時(shí)間窗，w1和w2為早到和晚到的懲罰參數(shù)。

載重約束懲罰函數(shù)：

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

2.3 選擇算子

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

2.4 交叉算子

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

圖3 交叉算子

2.5 變異算子

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

圖4 Insert 算子

圖5 Swap 算子

圖6 Reverse 算子

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

其中：f（Scurr）為當(dāng)前解的目標(biāo)值，f（Snew）為新解的目標(biāo)值，k 為當(dāng)前鄰域的迭代次數(shù)，Kmax為最大鄰域最大迭代次數(shù)，P 為接受新解的概率。

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

圖7 局部搜索流程圖

2.6 自適應(yīng)交叉和變異概率

標(biāo)準(zhǔn)遺傳算法中，交叉概率和變異概率一般被設(shè)為定值。為了提高求解速率，在迭代前期，通?？梢栽O(shè)置較大的交叉概率來增強(qiáng)算法的全局搜索能力，提高搜索速度，而迭代后期，較低的交叉概率和較高的變異概率能夠減少對最優(yōu)解的破壞，同時(shí)增加算法的局部搜索能力。相比于常規(guī)的交叉變異概率，自適應(yīng)交叉、變異可以算法的進(jìn)程動態(tài)的調(diào)整其概率。基于以上分析，本文參考文獻(xiàn)[15]，設(shè)置了自適應(yīng)交叉和變異概率，計(jì)算公式如下所示。

其中：Pc_max和Pc_min分別是交叉概率區(qū)間的最大值和最小值，Pm_max和Pm_min分別為變異概率區(qū)間的最大值和最小值，f 為個體適應(yīng)度值，f'為進(jìn)行交叉父本中最優(yōu)個體的適應(yīng)度值，fmax前種群中最優(yōu)個體的適應(yīng)度，favg為當(dāng)前種群中的平均適應(yīng)度。

2.7 最優(yōu)個體保留策略

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

3 算例設(shè)計(jì)

3.1 算法驗(yàn)證

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

表2 算例求解結(jié)果

分析結(jié)果表明，相較于標(biāo)準(zhǔn)遺傳算法，本文所提出的GA_VNS 能夠得到更優(yōu)的求解結(jié)果，在求解R101-25 例題時(shí)具有顯著的效果，R101-25 迭代過程如圖8 所示，R101-25 最優(yōu)路線圖如圖9 所示。由于算法中的參數(shù)設(shè)置是由多次實(shí)驗(yàn)得出，因此求解大規(guī)模算例仍存在一定的改進(jìn)空間。

圖8 R101-25 迭代過程圖

圖9 R101-25 最優(yōu)路線圖

3.2 算例設(shè)計(jì)

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

表3 廢棄物回收站及產(chǎn)生點(diǎn)信息表

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

圖10 迭代過程圖

表4 算例求解結(jié)果

4 總結(jié)與展望

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

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