文/張燕紅

1.引言

隨著城市規(guī)模的不斷擴(kuò)大和經(jīng)濟(jì)水平的逐步提高，我國生活垃圾清運(yùn)量增長迅速[1]。在國內(nèi)外學(xué)者的研究中，有諸多算法[2-5]可用于解決垃圾收集階段的車輛路徑優(yōu)化問題。本文通過比較掃描算法和遺傳算法的計算效果，從兩者中選擇較優(yōu)的一方，作為將來在研究垃圾收集階段車輛路徑問題的求解算法。其中，本文的優(yōu)化區(qū)域共計10個轉(zhuǎn)運(yùn)站，它們負(fù)責(zé)服務(wù)多個收集點。求解時，采用兩階段算法，先使用整數(shù)規(guī)劃將收集點指派給轉(zhuǎn)運(yùn)站，再分別使用掃描算法和遺傳算法計算其車輛的運(yùn)輸總路程。

2.掃描算法

將掃描算法應(yīng)用于本文的城市生活垃圾收運(yùn)問題，根據(jù)調(diào)研得知，運(yùn)輸車輛通常從一次轉(zhuǎn)運(yùn)站出發(fā)訪問各收集點，則對應(yīng)的起始點為各一次轉(zhuǎn)運(yùn)站，約束條件是垃圾收集車車輛的限重，滿足約束條件的收集點則加入當(dāng)前組中，直到垃圾收集車輛載重達(dá)到限定值后，建立一個新組，只有當(dāng)所有的收集點都?xì)w入相應(yīng)組時算法停止。這樣，每一個組便形成了一條大致路徑，即垃圾收集車輛可以從一次轉(zhuǎn)運(yùn)站出發(fā)，按順序經(jīng)過每組中的各收集點，最后返回一次轉(zhuǎn)運(yùn)站。

3.遺傳算法

將遺傳算法運(yùn)用到本文所研究的垃圾收集階段的收運(yùn)路徑問題中，以200個收集點，10個轉(zhuǎn)運(yùn)站為例，進(jìn)行算法構(gòu)造的處理細(xì)節(jié)如下：（1）編碼方式的設(shè)計。本文采用實數(shù)編碼方法，垃圾收集點用序號1~200表示，垃圾一次轉(zhuǎn)運(yùn)站用序號201~210表示，且序號具有唯一性。（2）初始群體的確定。完成上述編碼及其他相關(guān)數(shù)據(jù)設(shè)置后，接著根據(jù)一次轉(zhuǎn)運(yùn)站和垃圾收集點的數(shù)量、地理位置以及垃圾收運(yùn)能力或垃圾產(chǎn)生量等因素，使用整數(shù)規(guī)劃理論求解出各個轉(zhuǎn)運(yùn)站服務(wù)的收集點。而后，將各轉(zhuǎn)運(yùn)站服務(wù)的收集點序號隨機(jī)排列生成個體，且每個個體不出現(xiàn)相同的自然數(shù)。本文的群體規(guī)模確定為20。（3）適應(yīng)度評估。個體的適應(yīng)度是用來評估其方案優(yōu)劣程度的，此處的目標(biāo)函數(shù)值是運(yùn)輸路程長度，當(dāng)目標(biāo)函數(shù)值越小時，它的適應(yīng)度反而越大。因此，本文的適應(yīng)度函數(shù)F（x）與目標(biāo)函數(shù)f（x）的關(guān)系為：maxF（x）=min（-f（w））。（4）選擇操作。將種群中的多個個體根據(jù)其從大到小的適應(yīng)度進(jìn)行排名，選出排名靠前的20名留下作為下一次迭代的父代，同時，將較劣的路徑方案舍去。其中排名第一的個體在性能上是最佳的。（5）交叉操作。對于之前已通過選擇操作才生成的新種群，此處采用0.8的交叉概率，使用類似OX法的一種交叉方法，隨機(jī)在父代個體中選擇交配區(qū)域[37]。（6）變異操作。自然界中，變異是后代基因根據(jù)小概率改動的變化。在遺傳算法中，為模擬自然界的變異故將種群突變的情況設(shè)置為小概率事件，可能會使群體中小部分個體發(fā)生改變。本文中取0.1的突變概率，即對于每一個父代（染色體），生成1個0~1之間的隨機(jī)數(shù)，若該數(shù)小于突變概率，則父代執(zhí)行變異操作，且每次改變其位值的基因數(shù)只有兩個，變異時基因換位次數(shù)取1。（7）終止判斷。本文選取的終止準(zhǔn)則為迭代次數(shù)限制，當(dāng)?shù)螖?shù)未達(dá)到設(shè)定代數(shù)時，運(yùn)算繼續(xù)循環(huán)；反之，則運(yùn)算停止。

4.結(jié)果分析

根據(jù)上述提到的掃描算法和遺傳算法運(yùn)用到垃圾收運(yùn)問題的具體步驟，使用專業(yè)求解軟件編程分別計算重慶市主城區(qū)10個一次轉(zhuǎn)運(yùn)站各自的垃圾收運(yùn)總路程，得到的結(jié)果見表1所示。

表1 掃描算法和遺傳算法計算結(jié)果比較

從表1可以看出，在掃描算法的計算結(jié)果中，最小的是13.71km，最大的是795.37km；在遺傳算法的計算結(jié)果中，最小的是11.1km，最大的是656.3km。其中第一個轉(zhuǎn)運(yùn)站服務(wù)的收集點較少，因而使用兩種算法計算得出的運(yùn)行總路程均較小；而第七個轉(zhuǎn)運(yùn)站服務(wù)的收集點較多且部分收集點位于面積較廣的風(fēng)景區(qū)，因此其運(yùn)行總路程對于其他幾個轉(zhuǎn)運(yùn)站而言最大。同時，可以發(fā)現(xiàn)對于一次轉(zhuǎn)運(yùn)站至收集點的垃圾收運(yùn)工作路徑安排，采用遺傳算法計算得出的運(yùn)輸總路程相較于掃描算法計算得出的運(yùn)輸總路程而言更少，且大多數(shù)轉(zhuǎn)運(yùn)站的優(yōu)化比例超過10%，其中有兩個轉(zhuǎn)運(yùn)站的優(yōu)化比例在20%左右，優(yōu)化效果較好。

5.結(jié)論

綜上所述，采用遺傳算法能夠有效解決垃圾收運(yùn)路徑問題，減少垃圾收運(yùn)車輛運(yùn)輸總路程，從而降低在途運(yùn)輸時間，從而為緩解道路交通壓力、助力“生態(tài)文明城市”建設(shè)貢獻(xiàn)力量。

引用出處

[1]中華人民共和國國家統(tǒng)計局.中國統(tǒng)計年鑒[M].北京:中國統(tǒng)計出版社,2015-2021.

[2]趙紅霞,劉高森,李愈.基于隨機(jī)游走的分類垃圾回收最優(yōu)路徑規(guī)劃[J].交通運(yùn)輸工程與信息學(xué)報,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)化的多回收站點垃圾收運(yùn)問題求解[J].中國科學(xué)技術(shù)大學(xué)學(xué)報,2020,50(5):695-704.

[5]朱明華,范秀敏,劉炳凱,等.上海浦東新區(qū)城市生活垃圾收運(yùn)路線優(yōu)化研究[J].資源科學(xué),2009,31(9):1612-1618.