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

王 瑞，單而芳

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

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

王 瑞，單而芳

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

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

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

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

1 問題描述和符號說明

1.1 問題描述

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

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

1.2 符號說明

WCVRP問題意為圖 G=(V,A),V=VdYVfYVc，其中：車庫 Vd={0}，為了方便，車庫節(jié)分為開始和結(jié)束{0,0'}，m個垃圾處理站 Vf={1,…m}，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)輸時、運(yùn)輸距離，sij、[ai, bi]是垃圾點 i∈V相應(yīng)的服務(wù)時間和時間窗，qi為垃圾點 i∈Vc的垃圾收集量，變量}當(dāng)且僅當(dāng)車型 k的第 g輛車從 i到 j時當(dāng)且僅當(dāng)任務(wù) i由 k車型的第 g輛車服務(wù)∈{0,1}當(dāng)且僅當(dāng)車型 k能收集 i點時，表示型 k的第 g輛車收集到垃圾點 i時，已累計收集的垃圾量表示車型 k的第 g輛車開始收集垃圾點 i的時間，hk表示第 k型車的碳 -排放因子.

1.3 建立模型

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

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

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

（2）約束條件

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

2 算法設(shè)計

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

2.1 初始種群

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

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

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

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

2.3 交叉和突變

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

圖1 交叉程序步驟

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

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

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

2.4 停止條件

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

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

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

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

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

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

本文采用標(biāo)準(zhǔn)算例 1（數(shù)據(jù)來源于 http://www. hec.ca/chairedistributique/data/)，算法采用 matlab編程實現(xiàn).算例有 3種車型，2個垃圾處理廠，16個垃圾收集點，車輛信息：車型 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平臺上運(yùn)行的結(jié)果為：

具體表述為詳細(xì)路徑即：路徑 1：車庫 0→垃圾點 9→垃圾點 12→垃圾點 17→垃圾點 15→垃圾處理廠 2→車庫 0，使用車型 1.路徑 2：車庫 0→垃圾點 3→垃圾點 6→垃圾點 11→垃圾點 10→垃圾點7→垃圾處理廠 2→車庫 0，使用車型 3.路徑 3：車庫 0→垃圾點:4→垃圾點 14→垃圾點 16→垃圾點18→垃圾處理廠 1→垃圾點 5→垃圾點 13→垃圾點 8→垃圾處理廠 1→車庫 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)境污染，對城市可持續(xù)發(fā)展和人民身體健康有積極作用.

4 結(jié)論

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

〔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