城市生活垃圾收運(yùn)路線優(yōu)化模型及算法研究

王亞潔，賈順平，蔣金亮

(北京交通大學(xué)交通運(yùn)輸學(xué)院，北京100044)

城市的高速發(fā)展使得人們對于生活環(huán)境質(zhì)量的要求越來越高，生活垃圾問題就成為了人們關(guān)注的焦點(diǎn)。合理的收運(yùn)路線可以使車輛的調(diào)度更加高效，減少行駛的距離，也可以有效地降低時(shí)間和燃料成本等，增加人力和物力資源利用的有效性。因此垃圾收運(yùn)工作的重點(diǎn)就是合理地選擇車輛收運(yùn)路線。

車輛路徑問題，郵政員問題和旅行商問題是國外車輛路線優(yōu)化研究的主要內(nèi)容。1995年，Chang［1］在分析環(huán)境與經(jīng)濟(jì)之間存在的關(guān)系后提出很多不確定因素影響著垃圾收運(yùn)問題，灰色多目標(biāo)混合整數(shù)規(guī)劃模型(FIMOMIP)可以用來求解，量化不確定參數(shù)可以通過多目標(biāo)分析結(jié)構(gòu)中的間隔數(shù)據(jù)來解決。Cordeau，et al(2002)，Simone和 Borenstein(2007)對優(yōu)化垃圾收運(yùn)路線進(jìn)行了計(jì)算機(jī)工具的模擬，結(jié)果證明其研究方法是可行的。2006年，El-Haggar和Badran運(yùn)用了運(yùn)籌學(xué)的方法研究出一種基于定量組合的計(jì)算機(jī)技術(shù)，使得分配車輛的啟發(fā)式算法可以得到實(shí)現(xiàn)。

近年來，在國外研究成果的基礎(chǔ)上，我國學(xué)者結(jié)合中國的基本情況對路線優(yōu)化問題進(jìn)行了大量的研究，從最初單一的目標(biāo)到多個(gè)目標(biāo)，從簡單函數(shù)到不確定性多目標(biāo)的路線模型，優(yōu)化方法的研究也是不斷改進(jìn)和成熟。盛金良［2］進(jìn)行了城市生活垃圾收運(yùn)模式的研究，主要內(nèi)容是關(guān)于收運(yùn)系統(tǒng)設(shè)置中轉(zhuǎn)與否是與哪些因素有關(guān)，最終得出影響因素包括垃圾量，車輛載貨能力以及垃圾產(chǎn)生源與處理地之間的距離。臺(tái)灣學(xué)者張乃斌［3］研究的是收集車輛路線和調(diào)度的問題，他建立了一個(gè)多目標(biāo)混合整數(shù)模型，結(jié)合先進(jìn)的GIS技術(shù)成功的解決了這個(gè)問題。

1 城市生活垃圾收運(yùn)系統(tǒng)概況

1.1 城市生活垃圾概念及特點(diǎn)

生活垃圾包括兩個(gè)部分，一部分是在平時(shí)生活中產(chǎn)生的或者是為了生活服務(wù)所產(chǎn)生的固體廢棄物;第二部分是國家法律法規(guī)中規(guī)定的“固體廢棄物視為生活垃圾”。我國城市生活垃圾具有以下特點(diǎn):

第1，垃圾的成分比較復(fù)雜，性質(zhì)不穩(wěn)定。

由于人們生活的差異性，產(chǎn)生的垃圾也種類繁多。而且隨著科學(xué)技術(shù)的發(fā)展，新產(chǎn)品和材料的產(chǎn)生使得垃圾成分變得復(fù)雜。

第2，生活垃圾的產(chǎn)生量、性質(zhì)與成分與多種因素息息相關(guān)。

第3，城市生活垃圾具有很高的經(jīng)濟(jì)價(jià)值。生活中的很多當(dāng)垃圾扔掉的物品經(jīng)過回收后是可以再循環(huán)使用的，比如說廢舊電池、廢紙等。因此生活垃圾存在不可忽視的經(jīng)濟(jì)價(jià)值。

第4，垃圾量大，產(chǎn)生源分散，范圍廣。生活垃圾急劇增加的原因一方面是我國人口基數(shù)大，另一方面是城市的高速發(fā)展。生活垃圾的主要來源是家庭，因此所有的居住區(qū)域都是垃圾產(chǎn)生源，分布范圍很廣而且很分散。

1.2 城市垃圾收運(yùn)系統(tǒng)

城市垃圾收運(yùn)是指將垃圾從產(chǎn)生源運(yùn)到垃圾處理場的整個(gè)過程，其中包含了3個(gè)階段:收集、運(yùn)輸和轉(zhuǎn)運(yùn)［4］。人們將垃圾從產(chǎn)生源放至垃圾桶的過程即為收集階段;運(yùn)輸階段指的是車輛從車庫出發(fā)以后，遵循一定的路線收集區(qū)域內(nèi)的所有收集點(diǎn)的垃圾，然后運(yùn)往垃圾轉(zhuǎn)運(yùn)站(有的情況下垃圾車直接運(yùn)往處理場，不經(jīng)過轉(zhuǎn)運(yùn)站);轉(zhuǎn)運(yùn)站發(fā)出較大容量的車輛將壓縮后的垃圾運(yùn)往處理場則是轉(zhuǎn)運(yùn)過程所包含的內(nèi)容。

在收運(yùn)過程中，第一個(gè)收集階段需要調(diào)查區(qū)域現(xiàn)在的垃圾量及組成成分、垃圾產(chǎn)生源的分布情況等和預(yù)測其未來發(fā)展規(guī)模;清運(yùn)階段需要對垃圾車輛的收集路線進(jìn)行優(yōu)化設(shè)計(jì)，最后一個(gè)轉(zhuǎn)運(yùn)階段需要對垃圾量運(yùn)輸進(jìn)行優(yōu)化分配。

圖1 城市生活垃圾收運(yùn)模式?jīng)芎犹卮髽騇IDAS/Civil計(jì)算模型Fig.1 Municipal Solid Waste collection and transportation mode

城市的快速發(fā)展對于現(xiàn)有的環(huán)衛(wèi)設(shè)施是一個(gè)巨大的挑戰(zhàn)。按常住人口配置的環(huán)衛(wèi)設(shè)施已經(jīng)不能滿足城市正常運(yùn)轉(zhuǎn)的需求，主要是由于外來人口的大幅增加，導(dǎo)致了城市垃圾量急劇上升;同時(shí)因?yàn)槔者\(yùn)設(shè)施場地要求嚴(yán)格，所以城市能提供給它的場地有限，越來越遠(yuǎn)離垃圾處理場地。環(huán)保和廢物資源化的高要求使得收運(yùn)系統(tǒng)更加的信息化、規(guī)?；鸵?guī)范化。

2 垃圾路線優(yōu)化模型的建立

2.1 問題描述和符號說明

垃圾收運(yùn)問題可以表達(dá)為在垃圾收集區(qū)域內(nèi)，垃圾管理部門擁有多輛垃圾收集車輛，每天從車庫出發(fā)后經(jīng)過收集點(diǎn)進(jìn)行垃圾收集，在垃圾量達(dá)到車輛的最大運(yùn)輸能力后開往中轉(zhuǎn)站，將垃圾清空后再繼續(xù)去收集點(diǎn)重復(fù)上述的工作，當(dāng)所有的垃圾都被運(yùn)往處理場后返回到車庫。

一般情況下，垃圾收運(yùn)路線問題的3個(gè)條件為已知，分別是車庫、收集點(diǎn)和中轉(zhuǎn)站之間的距離、各個(gè)收集點(diǎn)的垃圾量以及每輛垃圾運(yùn)輸車輛的最大載荷，根據(jù)這些條件可以求得最佳的車輛運(yùn)輸路線。

路線問題中定義 V={0，1，2，…，n，n+1}，編號0代表車庫，收集點(diǎn)的編號則為1，2，3…，n。編號n+1代表轉(zhuǎn)運(yùn)站。可行解是滿足運(yùn)載能力等約束條件的解的集合。最優(yōu)解是可行解集合中路線最短的解。

2.2 模型建立

筆者建立的收運(yùn)路線優(yōu)化模型是以收運(yùn)總路線最短為目標(biāo)函數(shù)［5］。建立數(shù)學(xué)模型中目標(biāo)函數(shù)為:

約束條件的設(shè)置如下:

式中:qi為i點(diǎn)的垃圾量;dij為i點(diǎn)到j(luò)點(diǎn)的距離;W為垃圾車的最大容量;K為車庫的車輛總數(shù);nk為垃圾車k的收集點(diǎn)數(shù)(0表示沒有使用垃圾車k);Lik為垃圾車k離開i點(diǎn)時(shí)車中的垃圾量;M代表無窮大∞。

式中:約束(2)表示車輛從車庫出發(fā);約束(3)表示垃圾收集點(diǎn)不會(huì)重復(fù)收集;約束(4)表示垃圾車k經(jīng)過的收集點(diǎn)數(shù)比總的收集點(diǎn)數(shù)少;約束(5)表示不會(huì)遺漏垃圾收集點(diǎn);約束(6)表示車輛的垃圾量不會(huì)超載;約束(7)表示車在離開車庫和中轉(zhuǎn)站時(shí)垃圾量為0;約束(8)表示上一個(gè)點(diǎn)離開時(shí)的垃圾量加上在該點(diǎn)的垃圾量等于車在下一個(gè)收集點(diǎn)離開時(shí)的垃圾量。

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

3.1 遺傳算法簡介

隨著收集點(diǎn)數(shù)的增加，模型的解以指數(shù)型的速度增長，傳統(tǒng)的計(jì)算方法已經(jīng)無法滿足其求解要求，因此人工智能方法成為人們關(guān)注的焦點(diǎn)。

遺傳算法(Genetic Algorithm，簡稱GA)作為一種啟發(fā)式算法最初是由美國密歇根大學(xué)的John Holland教授在20世紀(jì)60年代提出的［6］，是由自然界生物進(jìn)化規(guī)律衍生出來的一種全局尋優(yōu)算法。染色體代表可行解，按照“適者生存”的原則，通過交叉和變異兩種遺傳操作產(chǎn)生出新一代環(huán)境適應(yīng)性更強(qiáng)的染色體，這一過程反復(fù)進(jìn)行直到達(dá)到某一收斂標(biāo)準(zhǔn)為止。最后得出環(huán)境適應(yīng)性最強(qiáng)的個(gè)體，即最優(yōu)解。

開始的時(shí)候有必要保留在最初最好的染色體。因?yàn)樽顑?yōu)的染色體不一定是出現(xiàn)在最后，如果在進(jìn)化后的種群發(fā)現(xiàn)更好的染色體的話，則用其來代替之前的最好的染色體，這樣就產(chǎn)生了新的染色體。不斷重復(fù)過程后，得出適應(yīng)能力最強(qiáng)的染色體，即是最優(yōu)解。

人工智能算法除了遺傳算法之外還包括模擬退火算法(Simulated Annealing，簡稱SA)、禁忌搜索算法(Tabu Search，簡稱TS)等。TS算法的優(yōu)勢是所求得的解精確度最高，但是其運(yùn)算耗費(fèi)時(shí)間最長;SA算法相較于其他兩種算法的優(yōu)勢是求解速度非?？?，但精確度不高，所以通常用于求解較小規(guī)模的問題;而GA算法集合了上述兩種方的優(yōu)點(diǎn)，不僅解的精確度高，而且運(yùn)算時(shí)間也相對較短，所以GA算法能夠同時(shí)兼顧到精確度和運(yùn)算時(shí)間兩個(gè)方面，在解決路線優(yōu)化問題上具有廣闊的應(yīng)用前景，所以本文選用遺傳算法進(jìn)行求解。

3.2 遺傳算法設(shè)計(jì)步驟

3.2.1 初始化

初始化可行解，一般以隨機(jī)方式產(chǎn)生一個(gè)初始可行解向量，記為 x=(bi)，i=1，2，…，n，其中 bi是數(shù)據(jù)或稱為個(gè)體，遺傳算法的思路是按照一點(diǎn)的規(guī)則不斷更新個(gè)體，盡可能從中選出最優(yōu)個(gè)體，直到找出全局可行解為止。n的取值范圍在30～160。

3.2.2 選擇操作

以適應(yīng)度函數(shù)的函數(shù)值作為“優(yōu)勝劣汰”的指標(biāo)來選出更優(yōu)的可行解，通過不斷迭代使得解能夠逐漸向全局最優(yōu)點(diǎn)靠近，式(9)是一個(gè)適應(yīng)度函數(shù)，其中bi表示適應(yīng)度，適應(yīng)度小的個(gè)體，被選擇的概率就相應(yīng)小，還可能是0，也就是個(gè)體被淘汰。適應(yīng)度高的個(gè)體被選擇的概率大，其繁殖的下一代數(shù)量比較大。通過這樣的選擇方式就可以產(chǎn)生適應(yīng)能力強(qiáng)的后代。

3.2.3 交叉操作

基因的交叉操作是指可行解域內(nèi)的任意兩個(gè)個(gè)體將以一定的概率Pc被選擇，并交換相同位置上的數(shù)據(jù)，即進(jìn)行基因交換重組，得到新的個(gè)體，根據(jù)經(jīng)驗(yàn)，交叉概率Pc的一般取值范圍為0.4～0.99。

3.2.4 變異操作

基因的變異操作指的是對可行解本身進(jìn)行操作，可行解域內(nèi)的任意個(gè)體將以一定的變異概率Pm發(fā)生某些數(shù)據(jù)位的變化，從而得到新解。這樣的變異過程可以增加種群的多樣性，染色體之間差異性的提高可以避免種群規(guī)模有限而導(dǎo)致的進(jìn)化終止。根據(jù)經(jīng)驗(yàn)，變異概率 Pm取值在0.001～0.1。

3.2.5 算法停止準(zhǔn)則的設(shè)計(jì)

算法必須是收斂的，不能一直無休止的進(jìn)行下去，即在經(jīng)過可數(shù)步長之后算法應(yīng)該能夠自動(dòng)停止。根據(jù)不同的需要可以選取不同的收斂標(biāo)準(zhǔn)，設(shè)計(jì)不同的停止準(zhǔn)則，一般常用的是選取指定步長的方法，但是步長的大小對結(jié)果有較大的影響，所以需要反復(fù)試驗(yàn)以確定合理的步長大小。一般建議的終止代數(shù)范圍為100～1000。

4 案例分析

4.1 背景設(shè)計(jì)

先說明本案例的垃圾收集方式，在此垃圾收集區(qū)域，居民將垃圾裝入垃圾袋后送往收集容器內(nèi)，車輛將垃圾收集后運(yùn)至中轉(zhuǎn)站，再由轉(zhuǎn)運(yùn)站的壓縮垃圾運(yùn)輸車將壓縮過的垃圾運(yùn)往填埋場。

在本區(qū)域里，只有一個(gè)車庫，它的編號為0，車庫有一輛垃圾收集車，垃圾收集車的載重量為5 t，垃圾收集點(diǎn)為 i，i={1，2，…，8}，垃圾中轉(zhuǎn)站的編號為9。車庫、收集點(diǎn)和中轉(zhuǎn)站之間的距離(km)以及各個(gè)垃圾收集點(diǎn)的垃圾量(t)如表1。

表1 垃圾收集點(diǎn)信息Table 1 information of waste collection point

4.2 優(yōu)化結(jié)果分析

運(yùn)用MATLAB軟件進(jìn)行遺傳算法編程，經(jīng)過10次計(jì)算，結(jié)果如表2:在10次的優(yōu)化結(jié)果中，有兩條路徑為最短路徑，長度為26 km，路徑1為車庫0→收集點(diǎn)7→收集點(diǎn)8→收集點(diǎn)6→收集點(diǎn)1→中轉(zhuǎn)站9→收集點(diǎn)5→收集點(diǎn)4→收集點(diǎn)2→收集點(diǎn)3→中轉(zhuǎn)站9→車庫0;路徑2為車庫0→收集點(diǎn)2→收集點(diǎn)7→收集點(diǎn)6→收集點(diǎn)1→收集點(diǎn)3—中轉(zhuǎn)站9→收集點(diǎn)5→收集點(diǎn)4→收集點(diǎn)8→中轉(zhuǎn)站9→車庫0。10次的優(yōu)化結(jié)果平均值為29.6 km，標(biāo)準(zhǔn)偏差為2%，說明運(yùn)算結(jié)果具有良好的穩(wěn)定性，運(yùn)算時(shí)間在4～5 s，說明遺傳算法收斂速度較快。所以遺傳算法能兼顧時(shí)間和效率兩個(gè)方面，由此可以看出遺傳算法在路線優(yōu)化方面具有很強(qiáng)的可行性，具有很好的研究和發(fā)展前景。

表2 遺傳算法計(jì)算結(jié)果Table 2 results of genetic algorithms

5 結(jié)論

筆者介紹了一種人工智能啟發(fā)式算法——遺傳算法，并通過MATLAB程序進(jìn)行了遺傳算法編程實(shí)現(xiàn)了模型的求解。最后通過實(shí)例進(jìn)行了驗(yàn)證，遺傳算法在車輛路線優(yōu)化的計(jì)算中較為簡便，通過計(jì)算機(jī)程序?qū)崿F(xiàn)較為容易，具有很強(qiáng)的可行性。

但是文中還存在著很多的不足之處，在實(shí)際的收運(yùn)路線問題中面臨更多更為復(fù)雜的基于現(xiàn)實(shí)的細(xì)節(jié)性要求，而且遺傳算法對參數(shù)設(shè)置和遺傳算子表現(xiàn)出較強(qiáng)的依賴性，不恰當(dāng)?shù)膮?shù)及算子設(shè)計(jì)往往導(dǎo)致算法的早熟或不收斂，依據(jù)遺傳算法的缺點(diǎn)，結(jié)合其他人工智能算法的特點(diǎn)，構(gòu)造出混合算法來進(jìn)行求解是算法未來的發(fā)展方向。

［1］Nibin Chang.Managerial fuzzy optimal planning for solid waste management systems［J］.Journal of the Environmental Engineering，ASCE，1996，122(7):649-657.

［2］盛金良，曹春華.城市生活垃圾收運(yùn)模式設(shè)計(jì)［J］.環(huán)境衛(wèi)生工程，2000，8(2):85-87.Sheng Jinliang，Cao Chunhua.Design of municipal solid waste collection and transport system［J］.Environmental Sanitation Engineering，2000，8(2):85-87.

［3］王芳芳.基于改進(jìn)蟻群算法的城市生活垃圾收運(yùn)路線優(yōu)化研究［D］.北京:北京工業(yè)大學(xué)，2011.

［4］王康樂.垃圾收運(yùn)車輛路線的優(yōu)化及其應(yīng)用［D］.南京:東南大學(xué)，2005.

［5］路玉龍，趙扶搖，韓靖，等.城市生活垃圾收運(yùn)路線優(yōu)化的數(shù)學(xué)模型與算法［J］.環(huán)境科學(xué)與管理，2010(6):46-50.Lu Yulong，Zhao Fuyao，Han Jing，et al.Mathematical model and algorithm for route optimization of municipal domestic waste collection and transportation［J］.Environment Science and Management，2010(6):46-50.

［6］王文梅.基于單親遺傳算法的城市垃圾收運(yùn)路線優(yōu)化研究［D］.成都:西南交通大學(xué)，2005.