王 瑞，單而芳

（上海大學(xué) 管理學(xué)院， 上海 200444）

基于油耗和低碳的垃圾收集路徑優(yōu)化研究

王 瑞，單而芳

（上海大學(xué) 管理學(xué)院， 上海 200444）

隨著我國(guó)城市垃圾產(chǎn)量的日漸增多，如何使垃圾收運(yùn)過(guò)程無(wú)害化、節(jié)能化，已成為綜合治理環(huán)境的新挑戰(zhàn).垃圾收運(yùn)費(fèi)用在整個(gè)垃圾處理系統(tǒng)中占很大比例，同時(shí)隨著人們生活水平的提高，人們對(duì)生活環(huán)境和身體健康更加關(guān)注.因此，本文將油耗和碳排放因素考慮到垃圾收集問(wèn)題中，建立了以運(yùn)輸距離、油耗和碳排放相結(jié)合的多目標(biāo)垃圾收集問(wèn)題模型，并采用基于插入算法的文化基因算法進(jìn)行求解，通過(guò)標(biāo)準(zhǔn)算例說(shuō)明了該算法的有效性和實(shí)用性.

WCVRP 問(wèn)題；油耗；低碳；文化基因算法；城市生活垃圾

對(duì)于 WCVRP問(wèn)題，目前國(guó)際上還沒(méi)有將油耗作為目標(biāo)函數(shù)進(jìn)行優(yōu)化，而 WCVRP問(wèn)題與 VRP問(wèn)題一樣：服務(wù)過(guò)程中會(huì)產(chǎn)生大量的油耗.因此，本文考慮總路程、能源和環(huán)境等多方面因素，建立了WCVRP問(wèn)題的數(shù)學(xué)模型，采用基于插入算法的文化基因算法進(jìn)行求解，通過(guò)實(shí)例求解驗(yàn)證了該算法解決實(shí)際問(wèn)題的可行性和有效性.

1 問(wèn)題描述和符號(hào)說(shuō)明

1.1 問(wèn)題描述

WCVRP問(wèn)題的收運(yùn)過(guò)程可以描述為：垃圾收運(yùn)車輛從車庫(kù)出發(fā)，在規(guī)定的時(shí)間內(nèi)到達(dá)垃圾點(diǎn)收集垃圾，直至車輛達(dá)到容量限制，就運(yùn)到處理廠卸空垃圾.車輛卸空后，再返回繼續(xù)收集，如此重復(fù)，直到服務(wù)完所有的垃圾收集點(diǎn)，車輛卸空后返回車庫(kù).

具體描述為：在滿足載重和時(shí)間約束的前題下，如何合理安排車輛路線，在滿足每個(gè)垃圾點(diǎn)被收集且只收集一次的同時(shí)，使運(yùn)輸距離、油耗、碳排放量最小.

1.2 符號(hào)說(shuō)明

WCVRP問(wèn)題意為圖 G=(V,A),V=VdYVfYVc，其中：車庫(kù) Vd={0}，為了方便，車庫(kù)節(jié)分為開(kāi)始和結(jié)束{0,0'}，m個(gè)垃圾處理站 Vf={1,…m}，n個(gè)垃圾收集點(diǎn)Vc=(m+1,…,m+n)弧 A={(i,j)|i,j∈V,i≠j}.一共 K種車型（k=1,2,…k），k車型的數(shù)目為 gk，車容量為 qk，tij、為車型 k在弧(i,j)相應(yīng)的運(yùn)輸時(shí)、運(yùn)輸距離，sij、[ai, bi]是垃圾點(diǎn) i∈V相應(yīng)的服務(wù)時(shí)間和時(shí)間窗，qi為垃圾點(diǎn) i∈Vc的垃圾收集量，變量}當(dāng)且僅當(dāng)車型 k的第 g輛車從 i到 j時(shí)當(dāng)且僅當(dāng)任務(wù) i由 k車型的第 g輛車服務(wù)∈{0,1}當(dāng)且僅當(dāng)車型 k能收集 i點(diǎn)時(shí)，表示型 k的第 g輛車收集到垃圾點(diǎn) i時(shí)，已累計(jì)收集的垃圾量表示車型 k的第 g輛車開(kāi)始收集垃圾點(diǎn) i的時(shí)間，hk表示第 k型車的碳 -排放因子.

1.3 建立模型

一般在給定車型的情況下，油耗與載重有關(guān)，本文假設(shè)二者成正比關(guān)系表示 k型車空載時(shí)的單位油耗，Qk表示 k型車滿載時(shí)的單位油耗，ri表示服務(wù)完 i后車輛實(shí)載率，則 k型車服務(wù)弧(i,j)的單位油耗量為：

WCVRP問(wèn)題的數(shù)學(xué)模型可建為：

（1）目標(biāo)函數(shù)

（2）約束條件

目標(biāo)函數(shù)為運(yùn)輸距離、油耗量、CO2排放量最小，公式（1）、（2）保證所有車輛必須從車庫(kù)出發(fā)，完成任務(wù)后回到車庫(kù)，公式（3）所有垃圾收集點(diǎn)必須且僅收集一次，公式（4）、（5）是對(duì)車輛的服務(wù)時(shí)間和時(shí)間窗的限定，公式（6）車輛從車庫(kù)出發(fā)和回到車庫(kù)要保持車是空載，公式（7）保證每個(gè)垃圾點(diǎn)只有一種相容車型的一輛車收集，公式（8）、（9）表示兩個(gè)變量間的約束關(guān)系，公式（10）是對(duì)多類型車輛車容的限制，公式（11）、（12）非負(fù)二元變量.

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

WCVRP問(wèn)題是大規(guī)模車輛路徑問(wèn)題，需要處理的垃圾點(diǎn)往往很多.文獻(xiàn)[11]中提到的文化基因算法是一種基于種群的全局搜索和基于個(gè)體的局部啟發(fā)式搜索的結(jié)合體，通過(guò)局部搜索提高個(gè)體適應(yīng)度，使以后的操作種群變小，進(jìn)而提高算法的效率.本文局部搜索采用爬山法，全局搜索采用遺傳算法.文化基因算法首先通過(guò)插入算法得到一個(gè)初始種群，然后通過(guò)選擇、交叉、突變和適應(yīng)來(lái)一代一代淘汰不良個(gè)體，選出最優(yōu)解.

2.1 初始種群

為了得到初始種群，我們采用所羅門(mén)的插入算法.該算法路線選擇基于兩個(gè)標(biāo)準(zhǔn)：距離當(dāng)前點(diǎn)最近和時(shí)間窗最早.如：從車庫(kù)開(kāi)始選擇距離車庫(kù)最近且時(shí)間窗允許的的垃圾點(diǎn)收集，收集完后，選擇距離當(dāng)前垃圾點(diǎn)最近的垃圾點(diǎn)收集，當(dāng)車達(dá)到額定容量的時(shí)候，到最近的垃圾處理廠卸空垃圾.再返回收集，直至服務(wù)完所有的垃圾收集點(diǎn).車輛到垃圾處理站卸空后，回到車庫(kù).路線順序?yàn)閇車庫(kù)、垃圾點(diǎn)、垃圾處理廠、車庫(kù)].因此，所有的垃圾收集點(diǎn)都被服務(wù)完，就得到了初始種群.

2.2 適應(yīng)度函數(shù)

基于目標(biāo)函數(shù)，適應(yīng)度函數(shù)可以表示為：

θ1，θ2，θ3：為權(quán)重表示每個(gè)目標(biāo)的重要程度.根據(jù)每個(gè)目標(biāo)的重要性，給予權(quán)重相應(yīng)的值.

2.3 交叉和突變

用染色體表示的頂點(diǎn)序列代表每個(gè)個(gè)體，由于車庫(kù)和垃圾處理廠不需要被服務(wù)，所以，進(jìn)行交叉和突變時(shí)，要將車庫(kù)和垃圾處理廠在頂點(diǎn)序列中刪除.交叉是繁殖下一代的主要部分，它的操作對(duì)象是兩個(gè)個(gè)體.隨機(jī)選擇兩個(gè)個(gè)體作為父代，兩個(gè)染色體之間部分基因先互換，然后選擇一個(gè)或多個(gè)基因（頂點(diǎn)序列）進(jìn)行交叉.圖 1闡述了兩個(gè)個(gè)體 P1，P2位置 1、2以及位置 6-9的基因互換，然后，P1的位置 4、7和第 P2的位置 7、10上的基因交叉.兩個(gè)新的個(gè)體 O1,O2就產(chǎn)生了.

圖1 交叉程序步驟

突變操作的對(duì)象是一個(gè)個(gè)體，它交換一個(gè)染色體的兩個(gè)或多個(gè)基因.圖2闡述了孩子這一代O1的染色體位置3與位置7的基因，位置9和位置10的基因交換，形成新的突變后的個(gè)體.

圖2 突變操作隨機(jī)交換例子

由于進(jìn)行交叉和突變時(shí)，把車庫(kù)和垃圾處理廠刪除了，為了保持路線的完整性，要把車庫(kù)和垃圾處理廠插入.當(dāng)染色體的下一步違反約束時(shí)，就將合適的垃圾處理廠插入解中.違反的約束被刪除，繼續(xù)進(jìn)行下一步.如：車輛收集了垃圾點(diǎn) 7-9-11后，達(dá)到了車輛的額定車容，則在垃圾點(diǎn) 11后插入一個(gè)距離垃圾點(diǎn)11最近的垃圾處理廠，卸完垃圾后，再繼續(xù)收集垃圾.最后，把車庫(kù)加在染色體的頭和尾，形成一個(gè)車輛完整的路線.如：路線 0-7-9 -11-1-8-5-3-6-4-2-10-13-12-0，其中 0為車庫(kù)，1、2為垃圾處理廠，其余為垃圾點(diǎn).

2.4 停止條件

定義每代種群的適應(yīng)度函數(shù)為：

zi(pop)：評(píng)估發(fā)展中的第 i代種群；

avgi(pop)：種群中第 i代所有個(gè)體的平均值；

maxi(pop)：種群中第 i代所有個(gè)體的最大值；

如果 zi(pop)的值在第 i+1代后不再發(fā)展，且發(fā)生了 n次，則算法結(jié)束.

3 數(shù)據(jù)分析

本文采用標(biāo)準(zhǔn)算例 1（數(shù)據(jù)來(lái)源于 http://www. hec.ca/chairedistributique/data/)，算法采用 matlab編程實(shí)現(xiàn).算例有 3種車型，2個(gè)垃圾處理廠，16個(gè)垃圾收集點(diǎn)，車輛信息：車型 1：數(shù)量 3、車容 10m3、載重 30Kg、碳排放因子 hk2.78Kg/L、空車油耗 Q0k0.09L/Km、滿載油耗 Qk0.15L/Km；車型 2：數(shù)量 5、車容 8m3、載重 60Kg、碳排放因子 hk2.54Kg/L、空車油耗 Q0k0.07/Km、滿載油耗 Qk0.13L/Km；車型 3：數(shù)量8、車容 5m3、載重 30Kg、碳排放因子 hk2.25Kg/L、空車油耗 Q0k0.05L/Km、滿載油耗 Qk0.10L/Km.

采用上述算法，設(shè)置基本參數(shù)為：最大迭代次數(shù) T=150，種群規(guī)模 G=50，θ1=0.5,θ2=0.3，θ3=0.2.在MATLAB平臺(tái)上運(yùn)行的結(jié)果為：

具體表述為詳細(xì)路徑即：路徑 1：車庫(kù) 0→垃圾點(diǎn) 9→垃圾點(diǎn) 12→垃圾點(diǎn) 17→垃圾點(diǎn) 15→垃圾處理廠 2→車庫(kù) 0，使用車型 1.路徑 2：車庫(kù) 0→垃圾點(diǎn) 3→垃圾點(diǎn) 6→垃圾點(diǎn) 11→垃圾點(diǎn) 10→垃圾點(diǎn)7→垃圾處理廠 2→車庫(kù) 0，使用車型 3.路徑 3：車庫(kù) 0→垃圾點(diǎn):4→垃圾點(diǎn) 14→垃圾點(diǎn) 16→垃圾點(diǎn)18→垃圾處理廠 1→垃圾點(diǎn) 5→垃圾點(diǎn) 13→垃圾點(diǎn) 8→垃圾處理廠 1→車庫(kù) 0，使用車型 2.得到滿意解 13512.00.

表1 結(jié)果比較

以車輛總路程為目標(biāo)和以車輛總路程、油耗量、co2排放量為目標(biāo)進(jìn)行優(yōu)化的結(jié)果進(jìn)行比較由表 1得出：以車輛總路程、油耗量、co2排放量為目標(biāo)與車輛總路程相比，雖然總路程有一些增加，但油耗量和 co2的排放量明顯減少.減少了能源消耗，減輕了環(huán)境污染，對(duì)城市可持續(xù)發(fā)展和人民身體健康有積極作用.

4 結(jié)論

為了保證市容、市貌，垃圾處理是市政當(dāng)局急需解決的問(wèn)題.垃圾收運(yùn)是垃圾處理的關(guān)鍵環(huán)節(jié)，因此，對(duì)垃圾收集路線進(jìn)行優(yōu)化，可以減少成本、節(jié)約能源、降低環(huán)境污染.本文針對(duì)垃圾車型號(hào)相同造成的車輛利用率低的現(xiàn)狀同時(shí)考慮油耗和環(huán)境污染等因素，提出了基于油耗和低碳的多車型垃圾收集路線優(yōu)化方案.采用文化基因算法對(duì)該問(wèn)題進(jìn)行求解，得到了問(wèn)題的滿意解.這開(kāi)辟了對(duì)垃圾收運(yùn)問(wèn)題研究的新思路，研究垃圾收運(yùn)路線時(shí)考慮節(jié)能和環(huán)境保護(hù)問(wèn)題具有理論價(jià)值和現(xiàn)實(shí)意義.

〔1〕路玉龍,趙扶搖,韓靖,張鴻雁.城市生活垃圾收運(yùn)路線優(yōu)化的數(shù)學(xué)模型與算法[J].環(huán)境科學(xué)與管理,2010,30(5):46-50.

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

O242；X799

A

1673-260X（2014）08-0026-03