肖艷兵，芮小平

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

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

肖艷兵1,2，芮小平3

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

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

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

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

車輛收運(yù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ī)模很大時(shí)，使用精確優(yōu)化算法進(jìn)行最優(yōu)路徑求解需要較長的運(yùn)行時(shí)間。一般在為收運(yùn)車輛分配收運(yùn)路線時(shí)，并不需要絕對的最短路徑，只要大致較短即可，因此可以使用啟發(fā)式算法求解。

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

1 問題描述

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

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

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

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

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

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

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

2.1 基本思路

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

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

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

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

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

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

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

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

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

2.3.1 種群規(guī)模

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

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

2.3.2 選擇算子

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

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

2.3.3 交叉算子

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

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

2.3.4 變異算子

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

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

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

表1 車輛參數(shù)表

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

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

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

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

4 結(jié) 語

本文對于經(jīng)典車輛路徑問題采用標(biāo)準(zhǔn)遺傳算法，并基于西寧市餐廚廢棄物時(shí)空分布規(guī)律將遺傳算法應(yīng)用于實(shí)際的道路網(wǎng)絡(luò)中，而不僅僅只是以點(diǎn)對點(diǎn)之間的坐標(biāo)作為計(jì)算依據(jù)，并通過系統(tǒng)設(shè)計(jì)實(shí)現(xiàn)了路線分配。本文雖然將遺傳算法應(yīng)用到實(shí)際的道路網(wǎng)絡(luò)中，但標(biāo)準(zhǔn)遺傳算法本身具有容易早熟收斂，陷入局部最優(yōu)解，因此還需要對標(biāo)準(zhǔn)遺傳算法進(jìn)行改進(jì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] 李志建,鄭新奇,王淑晴,等．改進(jìn)A*算法及其在GIS路徑搜索中的應(yīng)用[J]．系統(tǒng)仿真學(xué)報(bào), 2009(10)： 3 116-3 119

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

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

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

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

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

[11] 張麗萍,柴躍廷．遺傳算法的現(xiàn)狀及發(fā)展動(dòng)向[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é)報(bào),2014(12)：51-56

[14] 蔡菲,崔健,丁寧,等． 基于GIS和改進(jìn)遺傳算法的最優(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

肖艷兵，工程師，研究方向?yàn)榈乩硇畔⑾到y(tǒng)開發(fā)與應(yīng)用。

2016-03-25。

項(xiàng)目來源：國家科技支撐計(jì)劃資助項(xiàng)目（2012BAC25B01）。