約束條件遺傳算法的餐廚廢棄物收運路線研究

肖艷兵，芮小平

（1.山東正元地球物理信息技術有限公司，山東 濟南 250000；2.山東明嘉勘察測繪有限公司，山東 淄博255000；3.中國科學院大學資源與環境學院，北京 100049）

約束條件遺傳算法的餐廚廢棄物收運路線研究

肖艷兵1,2，芮小平3

（1.山東正元地球物理信息技術有限公司，山東 濟南 250000；2.山東明嘉勘察測繪有限公司，山東 淄博255000；3.中國科學院大學資源與環境學院，北京 100049）

以西寧市交通網絡數據庫為基礎，結合GIS技術，分析西寧市餐廚廢棄物的時空分布規律，并在此基礎上，根據收運車輛、餐廚廢棄物產生點以及產生量之間的關系，采用遺傳算法研究最佳派送路線，并通過系統進行實現。

車輛路徑問題；遺傳算法；西寧市

傳統餐廚廢棄物的收運調控過程主要憑借主觀經驗確定，忽略了動態變化，從而造成收運過程運能配置不合理。根據動態變化的餐廚廢棄物產生量以及廢棄物的分布位置，結合空間數據庫建立餐廚廢棄物收運車輛和收運路線動態分配模型，保證用最少的餐廚收運車輛和最佳的收運路線進行收運，具有重要的現實意義。

車輛收運路線的分配屬于車輛路徑問題（Vehicle Route Problem, VRP）?，F有對車輛路徑問題的求解方法主要有精確優化算法和啟發式算法。精確優化算法主要有分支定界法[1]、Dijkstra[2-3]、A*算法和線性規劃算法等方法在內的線性規劃方法和非線性規劃方法來求最優解[4-5]。啟發式算法主要有模擬退火算法[6]、禁忌搜索算法[7-8]、蟻群算法以及遺傳算法等[9-14]。精確求解主要應用于路網規模較小的情況。當城市路網規模很大時，使用精確優化算法進行最優路徑求解需要較長的運行時間。一般在為收運車輛分配收運路線時，并不需要絕對的最短路徑，只要大致較短即可，因此可以使用啟發式算法求解。

目前人們使用遺傳算法研究的大都基于城市點或配送點，主要以點之間的坐標作為運算依據，并沒有結合實際道路網絡應用到具體某個區域中。本文以西寧市交通網絡數據庫為基礎結合GIS技術，分析西寧市餐廚廢棄物的時空分布規律，并在此基礎上，根據收運車輛、餐廚廢棄物產生點以及產生量之間的關系，采用遺傳算法研究最佳派送路線。

1 問題描述

餐廚廢棄物收運要求對有飯店存在的每條街，都至少通過一次，再集中到餐廚廢棄物收購中心。每輛車裝運的廢棄物是有限的，而且廢棄物的量又是隨時變化的，如何用最少的車輛最大限度地收取所有廢棄物是多目標調配算法要解決的主要問題。由于城市內路網規模相對較小，餐廚廢棄物收運車輛相對靈活，對餐廚廢棄物波動比較敏感。所以應更強調于滿足以下原則：

1）嚴格遵循城市道路運輸方案的有關法規政策。

2）盡可能用最少的車輛最大限度地收運餐廚廢棄物。

3）盡可能提高收運效率，如在一定區域選取最優路徑，每車每次重復路線最少，收運所有該地區的餐廚廢棄物。

4）盡可能使空車行駛的總里程少，空車行駛的時間少等。

5）由于餐廚垃圾收運過程中產生異味，因此收運線路要盡量繞開居民區。

2 基于遺傳算法的多目標路徑規劃

2.1 基本思路

根據西寧市餐廚廢棄物產生的時空規律，可以根據青海潔神現有的收運車輛噸位確定分配收運車輛的最少數量，最少車輛可用如下方法判斷計算：

首先判斷最大噸位車輛能夠裝運的總量是否大于餐廚廢棄物總量，如果大于餐廚廢棄物總量，則車輛數為餐廚廢棄物總量/最大噸位上取整。如果小于餐廚廢棄物總量，則進一步判斷第二噸位的車輛能夠裝運的總量是否大于餐廚廢棄物總量-最大噸位裝運總量，如果大于該數，則車輛數為最大噸位車輛數+（（餐廚廢棄物總量-最大噸位裝運總量）/第二噸位）上取整。如果小于則進一步根據上面的方法判斷第三噸位需要的車倆。

動態收運路線設計的核心在于確定每條線路的收運路線，所有的收運車輛都是從收運中心出發，收運完后又回到收運中心，因此該問題屬于典型車輛配送問題（VRP）。

2.2 遺傳算法收運路線數學模型

首先對每個餐飲店進行編碼，隨機生成N個個體，生成初始化種群，然后根據適應度函數計算每個個體的適應度，通過選擇算子選擇適應度高的一個或者多個個體直接傳入下一代種群中，再通過復制、交叉、變異對個體進行篩選，組成新的種群，反復循環計算，種群中的個體適應度會不斷的提高，達到設置的條件時終止進化。多目標車輛路徑問題進行求解時的約束條件有：

式中，i為收運點；m為滿足條件時最大收運點；Q為車輛最大運量；D為車輛最大行駛距離；T為車輛最大行駛時間；L為收運點數量；nk為每輛車包含的收運點的數量；dm,0為滿足條件時的站點到回收中心距離。

式（1）保證每條收運線路上的收運點的垃圾量之和不會超過此條路徑上的配送車輛的最大載重量；式（2）保證每輛車輛在收運路線上的行駛距離不會超過該車輛的最大行駛距離；式（3）保證每輛車輛行駛的時間不會超過該車輛最大行駛時間，式（4）保證了每個收運點都能被車輛收運到。當Q(x)＞Q或D(x)＞D或T(x)＞T時，調用下一輛車輛進行路線計算。

2.3 遺傳算法的參數及優化

遺傳算法主要包括種群規模及種群初始化、選擇算子、交叉算子和變異算子等幾個參數。

2.3.1 種群規模

種群規模的大小將直接影響算法執行的效率和最終的優化結果。一般情況下，種群規模太小，不能提供足夠的采樣點，當計算結束時，可能得不到問題的可行解；當種群規模太大時，盡管可以防止早熟收斂現象的發生，但是計算量會非常大，影響算法的執行效率。

為方便起見，本文的染色體編碼將使用餐館的編號，每個餐館有單獨的編號，將所有餐館編號采用隨機組合的方式生成N個染色體組成初始種群。

2.3.2 選擇算子

常見的選擇算子包括最佳個體保存法、期望值方法、適應度比例法、聯賽選擇法、排序選擇法、排擠方法等。本文使用的是最佳個體保存法，即通過選擇適應度最高的個體進入下一代。適應度函數為：

使用最佳個體保存法，可以使適應度最高的個體直接進入到下一代中，而不必進行交叉復制，保證在進化的過程中保留該代的最優解，在個體交叉和變異的時候，不會被交叉和變異破壞該最優解。

2.3.3 交叉算子

常見的交叉算子包括一點交叉法、二點交叉法、多點交叉法、一致交叉法等。根據研究問題的特點，本文使用的是兩點交叉法，即隨機在父代染色體中生成兩個交叉點，然后交換兩個交叉點之間的部分染色體，生成兩個新的個體。如A和B兩條收運路線：

子代A從父代A中取交叉點前267，然后取父代B中兩個交叉點之間的8 697基因插入父代A4 513之前，然后去掉重復基因得到2、6、7、8、9、4、5、1、3。

2.3.4 變異算子

常見的變異算子包括基本變異法、自適應變異法、逆轉算子法等。本文使用的算子是基本變異法，即對個體隨機挑選一個基因，通過變異概率Pm進行基因變動。方法如下[15]：隨機產生一個1～n之間的數k，決定對回路中的第k個城市代碼Wk作變異操作，又產生一個1～n之間的數w替代Wk，將Wk加到尾部，得到此串有n+1個數碼，因為數w在串中重復了，必須刪除與數w相重復的數以得到合法的染色體。

3 算法實例應用

通過餐廚廢棄物的空間分布規律可知，居民較聚集、道路通達的地方以及老城區都是餐廚垃圾收運量較大的地區，因此本文選取西寧市市區262家餐館作為研究對象，暫時不考慮偏遠郊區；通過時間分布規律可知，平均每天的餐廚廢棄物的產生量約為100 t，假設每家餐館每天產出餐廚垃圾均0．381 7 t，初步配置20輛車輛進行收運，車輛載重及最大行駛距離如表1。其中序號表示收運車輛的車輛編號；載重代表每輛車最大載重；運距代表每輛車最大行駛距離。

表1 車輛參數表

本算法選定的全部參數如下：車輛數x=20（最大收運線路）；最大迭代次數T=30 000；交叉概率Pc=0.9；變異概率Pm=（1-Pc）*0.9=0.09，種群規模Scale=100。算法實現基于Visual Studio2010平臺，采用C#編程語言結合ArcGIS Engine組件庫以及MySQL數據庫進行系統實現，經過程序運算得出最優路徑如表2所示。其中，序號代表收運車輛的車輛編號；收運方案代表車輛收運的路線并顯示出收運的餐館的順序；收運方案中的編號“0”代表車輛配送中心和車輛回收中心；本文中車輛配送中心和車輛回收中心是同一個單位，因此都用編號“0”表示，收運方案中的其他編號分別代表一個餐館，載重和運距分別為車輛分配路線后車輛收運餐廚廢棄物的實際收運量和實際行駛距離。

由程序運算結果可知，最優路徑出現在25 023代，最優路線數為18條即使用前18輛車進行餐廚垃圾收運，所有車輛從派車中心出發，收運完餐廚垃圾返回回收中心，詳細路線如圖1所示。

圖1 收運線路結果圖

表2 最優收運方案

4 結 語

本文對于經典車輛路徑問題采用標準遺傳算法，并基于西寧市餐廚廢棄物時空分布規律將遺傳算法應用于實際的道路網絡中，而不僅僅只是以點對點之間的坐標作為計算依據，并通過系統設計實現了路線分配。本文雖然將遺傳算法應用到實際的道路網絡中，但標準遺傳算法本身具有容易早熟收斂，陷入局部最優解，因此還需要對標準遺傳算法進行改進或者結合其他算法以解決這方面問題。

[1] 李詩珍,曹平方,李詩珍．基于分枝界定的VRP模型精確算法研究及應用[J]．包裝工程,2014(17)： 97-101

[2] YANG MY,COILLIE F V,LUC H,et al． Nature Conservation Versus Scenic Quality：A GIS Approach Towards Optimized Tourist Tracks in a Protected Area of Northwest Yunnan,China[J]．Journal of Mountain Science, 2014(1)： 142-155

[3] 江成玉,楊林,劉勇．煤與瓦斯突出后最佳避災路線的研究[J]．煤炭技術,2014(12)： 213-215

[4] 李志建,鄭新奇,王淑晴,等．改進A*算法及其在GIS路徑搜索中的應用[J]．系統仿真學報, 2009(10)： 3 116-3 119

[5] 趙真明,孟正大．基于加權A*算法的服務型機器人路徑規劃[J]．華中科技大學學報（自然科學版）, 2008(S1)： 196-198[6] 胡大偉,朱志強,胡勇．車輛路徑問題的模擬退火算法[J]．中國公路學報,2006(4)：123-126

[7] 余麗,陸鋒,楊林．交通網絡旅行商路徑優化的遺傳禁忌搜索算法[J]．測繪學報,2014(11)：1 197-1 203

[8] 賀一,劉光遠．禁忌搜索算法求解旅行商問題研究[J]．西南師范大學學報（自然科學版）, 2002(3)： 341-345

[9] 段海濱,馬冠軍,王道波,等．一種求解連續空間優化問題的改進蟻群算法[J]．系統仿真學報, 2007(5)： 974-977

[10] 段海濱,王道波,朱家強,等．蟻群算法理論及應用研究的進展[J]．控制與決策,2004(12)：1 321-1 326

[11] 張麗萍,柴躍廷．遺傳算法的現狀及發展動向[J]．信息與控制,2001(6)：531-536

[12] YANG S,TIN?S R．A Hybrid Immigrants Scheme for Genetic Algorithms in Dynamic Environments[J]． International Journal of Automation and Computing,2007(3)：243-254

[13] 李曉娟,沈斐敏．城市供水管網抗震加固優化研究[J]．中國安全科學學報,2014(12)：51-56

[14] 蔡菲,崔健,丁寧,等． 基于GIS和改進遺傳算法的最優路徑規劃[J]．工程勘察, 2009(10)： 62-65

[15] 蔡自興,徐光祐．人工智能及其應用[M]．清華大學出版社, 1996

P208

B文章編號：1672-4623（2017）06-0064-03

10.3969/j.issn.1672-4623.2017.06.019

肖艷兵，工程師，研究方向為地理信息系統開發與應用。

2016-03-25。

項目來源：國家科技支撐計劃資助項目（2012BAC25B01）。