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

肖艷兵，芮小平

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

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

肖艷兵1,2，芮小平3

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

以西寧市交通網(wǎng)絡(luò)數(shù)據(jù)庫為基礎(chǔ)，結(jié)合GIS技術(shù)，分析西寧市餐廚廢棄物的時空分布規(guī)律，并在此基礎(chǔ)上，根據(jù)收運車輛、餐廚廢棄物產(chǎn)生點以及產(chǎn)生量之間的關(guān)系，采用遺傳算法研究最佳派送路線，并通過系統(tǒng)進行實現(xiàn)。

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

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

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

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

1 問題描述

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

1）嚴(yán)格遵循城市道路運輸方案的有關(guān)法規(guī)政策。

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

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

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

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

2 基于遺傳算法的多目標(biāo)路徑規(guī)劃

2.1 基本思路

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

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

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

2.2 遺傳算法收運路線數(shù)學(xué)模型

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

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

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

2.3 遺傳算法的參數(shù)及優(yōu)化

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

2.3.1 種群規(guī)模

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

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

2.3.2 選擇算子

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

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

2.3.3 交叉算子

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

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

2.3.4 變異算子

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

3 算法實例應(yīng)用

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

表1 車輛參數(shù)表

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

由程序運算結(jié)果可知，最優(yōu)路徑出現(xiàn)在25 023代，最優(yōu)路線數(shù)為18條即使用前18輛車進行餐廚垃圾收運，所有車輛從派車中心出發(fā)，收運完餐廚垃圾返回回收中心，詳細(xì)路線如圖1所示。

圖1 收運線路結(jié)果圖

表2 最優(yōu)收運方案

4 結(jié) 語

本文對于經(jīng)典車輛路徑問題采用標(biāo)準(zhǔn)遺傳算法，并基于西寧市餐廚廢棄物時空分布規(guī)律將遺傳算法應(yīng)用于實際的道路網(wǎng)絡(luò)中，而不僅僅只是以點對點之間的坐標(biāo)作為計算依據(jù)，并通過系統(tǒng)設(shè)計實現(xiàn)了路線分配。本文雖然將遺傳算法應(yīng)用到實際的道路網(wǎng)絡(luò)中，但標(biāo)準(zhǔn)遺傳算法本身具有容易早熟收斂，陷入局部最優(yōu)解，因此還需要對標(biāo)準(zhǔn)遺傳算法進行改進或者結(jié)合其他算法以解決這方面問題。

[1] 李詩珍,曹平方,李詩珍．基于分枝界定的VRP模型精確算法研究及應(yīng)用[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] 江成玉,楊林,劉勇．煤與瓦斯突出后最佳避災(zāi)路線的研究[J]．煤炭技術(shù),2014(12)： 213-215

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

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

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

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

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

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

[11] 張麗萍,柴躍廷．遺傳算法的現(xiàn)狀及發(fā)展動向[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] 李曉娟,沈斐敏．城市供水管網(wǎng)抗震加固優(yōu)化研究[J]．中國安全科學(xué)學(xué)報,2014(12)：51-56

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

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

P208

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

10.3969/j.issn.1672-4623.2017.06.019

肖艷兵，工程師，研究方向為地理信息系統(tǒng)開發(fā)與應(yīng)用。

2016-03-25。

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