生活垃圾收集階段車輛路徑問(wèn)題研究

文/張燕紅

1.引言

隨著城市規(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)輸總路程。

2.掃描算法

將掃描算法應(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)站。

3.遺傳算法

將遺傳算法運(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)算停止。

4.結(jié)果分析

根據(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)化效果較好。

5.結(jié)論

綜上所述，采用遺傳算法能夠有效解決垃圾收運(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.