文/張燕紅
隨著城市規(guī)模的不斷擴(kuò)大和經(jīng)濟(jì)水平的逐步提高,我國(guó)生活垃圾清運(yùn)量增長(zhǎng)迅速[1]。在國(guó)內(nèi)外學(xué)者的研究中,有諸多算法[2-5]可用于解決垃圾收集階段的車輛路徑優(yōu)化問(wèn)題。本文通過(guò)比較掃描算法和遺傳算法的計(jì)算效果,從兩者中選擇較優(yōu)的一方,作為將來(lái)在研究垃圾收集階段車輛路徑問(wèn)題的求解算法。其中,本文的優(yōu)化區(qū)域共計(jì)10個(gè)轉(zhuǎn)運(yùn)站,它們負(fù)責(zé)服務(wù)多個(gè)收集點(diǎn)。求解時(shí),采用兩階段算法,先使用整數(shù)規(guī)劃將收集點(diǎn)指派給轉(zhuǎn)運(yùn)站,再分別使用掃描算法和遺傳算法計(jì)算其車輛的運(yùn)輸總路程。
將掃描算法應(yīng)用于本文的城市生活垃圾收運(yùn)問(wèn)題,根據(jù)調(diào)研得知,運(yùn)輸車輛通常從一次轉(zhuǎn)運(yùn)站出發(fā)訪問(wèn)各收集點(diǎn),則對(duì)應(yīng)的起始點(diǎn)為各一次轉(zhuǎn)運(yùn)站,約束條件是垃圾收集車車輛的限重,滿足約束條件的收集點(diǎn)則加入當(dāng)前組中,直到垃圾收集車輛載重達(dá)到限定值后,建立一個(gè)新組,只有當(dāng)所有的收集點(diǎn)都?xì)w入相應(yīng)組時(shí)算法停止。這樣,每一個(gè)組便形成了一條大致路徑,即垃圾收集車輛可以從一次轉(zhuǎn)運(yùn)站出發(fā),按順序經(jīng)過(guò)每組中的各收集點(diǎn),最后返回一次轉(zhuǎn)運(yùn)站。
將遺傳算法運(yùn)用到本文所研究的垃圾收集階段的收運(yùn)路徑問(wèn)題中,以200個(gè)收集點(diǎn),10個(gè)轉(zhuǎn)運(yùn)站為例,進(jìn)行算法構(gòu)造的處理細(xì)節(jié)如下:(1)編碼方式的設(shè)計(jì)。本文采用實(shí)數(shù)編碼方法,垃圾收集點(diǎn)用序號(hào)1~200表示,垃圾一次轉(zhuǎn)運(yùn)站用序號(hào)201~210表示,且序號(hào)具有唯一性。(2)初始群體的確定。完成上述編碼及其他相關(guān)數(shù)據(jù)設(shè)置后,接著根據(jù)一次轉(zhuǎn)運(yùn)站和垃圾收集點(diǎn)的數(shù)量、地理位置以及垃圾收運(yùn)能力或垃圾產(chǎn)生量等因素,使用整數(shù)規(guī)劃理論求解出各個(gè)轉(zhuǎn)運(yùn)站服務(wù)的收集點(diǎn)。而后,將各轉(zhuǎn)運(yùn)站服務(wù)的收集點(diǎn)序號(hào)隨機(jī)排列生成個(gè)體,且每個(gè)個(gè)體不出現(xiàn)相同的自然數(shù)。本文的群體規(guī)模確定為20。(3)適應(yīng)度評(píng)估。個(gè)體的適應(yīng)度是用來(lái)評(píng)估其方案優(yōu)劣程度的,此處的目標(biāo)函數(shù)值是運(yùn)輸路程長(zhǎng)度,當(dāng)目標(biāo)函數(shù)值越小時(shí),它的適應(yīng)度反而越大。因此,本文的適應(yīng)度函數(shù)F(x)與目標(biāo)函數(shù)f(x)的關(guān)系為:maxF(x)=min(-f(w))。(4)選擇操作。將種群中的多個(gè)個(gè)體根據(jù)其從大到小的適應(yīng)度進(jìn)行排名,選出排名靠前的20名留下作為下一次迭代的父代,同時(shí),將較劣的路徑方案舍去。其中排名第一的個(gè)體在性能上是最佳的。(5)交叉操作。對(duì)于之前已通過(guò)選擇操作才生成的新種群,此處采用0.8的交叉概率,使用類似OX法的一種交叉方法,隨機(jī)在父代個(gè)體中選擇交配區(qū)域[37]。(6)變異操作。自然界中,變異是后代基因根據(jù)小概率改動(dòng)的變化。在遺傳算法中,為模擬自然界的變異故將種群突變的情況設(shè)置為小概率事件,可能會(huì)使群體中小部分個(gè)體發(fā)生改變。本文中取0.1的突變概率,即對(duì)于每一個(gè)父代(染色體),生成1個(gè)0~1之間的隨機(jī)數(shù),若該數(shù)小于突變概率,則父代執(zhí)行變異操作,且每次改變其位值的基因數(shù)只有兩個(gè),變異時(shí)基因換位次數(shù)取1。(7)終止判斷。本文選取的終止準(zhǔn)則為迭代次數(shù)限制,當(dāng)?shù)螖?shù)未達(dá)到設(shè)定代數(shù)時(shí),運(yùn)算繼續(xù)循環(huán);反之,則運(yùn)算停止。
根據(jù)上述提到的掃描算法和遺傳算法運(yùn)用到垃圾收運(yùn)問(wèn)題的具體步驟,使用專業(yè)求解軟件編程分別計(jì)算重慶市主城區(qū)10個(gè)一次轉(zhuǎn)運(yùn)站各自的垃圾收運(yùn)總路程,得到的結(jié)果見(jiàn)表1所示。
表1 掃描算法和遺傳算法計(jì)算結(jié)果比較
從表1可以看出,在掃描算法的計(jì)算結(jié)果中,最小的是13.71km,最大的是795.37km;在遺傳算法的計(jì)算結(jié)果中,最小的是11.1km,最大的是656.3km。其中第一個(gè)轉(zhuǎn)運(yùn)站服務(wù)的收集點(diǎn)較少,因而使用兩種算法計(jì)算得出的運(yùn)行總路程均較?。欢谄邆€(gè)轉(zhuǎn)運(yùn)站服務(wù)的收集點(diǎn)較多且部分收集點(diǎn)位于面積較廣的風(fēng)景區(qū),因此其運(yùn)行總路程對(duì)于其他幾個(gè)轉(zhuǎn)運(yùn)站而言最大。同時(shí),可以發(fā)現(xiàn)對(duì)于一次轉(zhuǎn)運(yùn)站至收集點(diǎn)的垃圾收運(yùn)工作路徑安排,采用遺傳算法計(jì)算得出的運(yùn)輸總路程相較于掃描算法計(jì)算得出的運(yùn)輸總路程而言更少,且大多數(shù)轉(zhuǎn)運(yùn)站的優(yōu)化比例超過(guò)10%,其中有兩個(gè)轉(zhuǎn)運(yùn)站的優(yōu)化比例在20%左右,優(yōu)化效果較好。
綜上所述,采用遺傳算法能夠有效解決垃圾收運(yùn)路徑問(wèn)題,減少垃圾收運(yùn)車輛運(yùn)輸總路程,從而降低在途運(yùn)輸時(shí)間,從而為緩解道路交通壓力、助力“生態(tài)文明城市”建設(shè)貢獻(xiàn)力量。
引用出處
[1]中華人民共和國(guó)國(guó)家統(tǒng)計(jì)局.中國(guó)統(tǒng)計(jì)年鑒[M].北京:中國(guó)統(tǒng)計(jì)出版社,2015-2021.
[2]趙紅霞,劉高森,李愈.基于隨機(jī)游走的分類垃圾回收最優(yōu)路徑規(guī)劃[J].交通運(yùn)輸工程與信息學(xué)報(bào),2018,16(3):103-108.
[3]Nowakowski P,Szwarc K,Boryczka U.Vehicle route planning in e-waste mobile collection on demand supported by artificial intelligence algorithms[J].Transportation Research Part D:Transport and Environment,2018,63:1-22.
[4]張玉州,張子為.基于合作協(xié)同進(jìn)化的多回收站點(diǎn)垃圾收運(yùn)問(wèn)題求解[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào),2020,50(5):695-704.
[5]朱明華,范秀敏,劉炳凱,等.上海浦東新區(qū)城市生活垃圾收運(yùn)路線優(yōu)化研究[J].資源科學(xué),2009,31(9):1612-1618.