進(jìn)化算法在廢棄物選址問(wèn)題上的應(yīng)用

陳齊玲，溫潔嫦，林志逢

(廣東工業(yè)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，廣東 廣州 510520)

進(jìn)化算法在廢棄物選址問(wèn)題上的應(yīng)用

陳齊玲，溫潔嫦，林志逢

(廣東工業(yè)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，廣東 廣州 510520)

研究城市廢棄物中轉(zhuǎn)站和處理站的選址問(wèn)題，考慮總成本(建設(shè)費(fèi)、運(yùn)費(fèi))最低和環(huán)境負(fù)效應(yīng)最小，建立優(yōu)化模型.設(shè)計(jì)進(jìn)化算法求解，確定要建立的中轉(zhuǎn)站和處理站的位置、容量及建設(shè)費(fèi)用，并確定了中轉(zhuǎn)站服務(wù)的產(chǎn)生點(diǎn)和處理站服務(wù)的中轉(zhuǎn)站.最后算例仿真表明了算法的可行性和有效性.

廢棄物選址問(wèn)題； 優(yōu)化模型； 進(jìn)化算法

隨著城市生活垃圾、廢棄物排放量的大幅度增加，人們必須采用合適的方式來(lái)處理這些廢棄物.本文解決廢棄物中轉(zhuǎn)站和處理站的選址問(wèn)題，是一個(gè)厭惡型設(shè)施的選址問(wèn)題.如果中轉(zhuǎn)站和處理站距離居民區(qū)太近，容易給居民帶來(lái)難聞的氣味和引來(lái)蚊蟲；如果太遠(yuǎn)，運(yùn)輸費(fèi)用又太高.中轉(zhuǎn)站和處理站屬于城市環(huán)境衛(wèi)生基礎(chǔ)設(shè)施，由政府部門做決策，應(yīng)綜合考慮對(duì)環(huán)境的影響最小和總成本最低等方面因素來(lái)建立廢棄物中轉(zhuǎn)站和處理站.

近年來(lái)，國(guó)內(nèi)外很多學(xué)者對(duì)廢棄物處理站選址問(wèn)題進(jìn)行了研究.何波等[1]采用多目標(biāo)演化算法對(duì)廢棄物處理站選址問(wèn)題進(jìn)行求解，該文獻(xiàn)雖然考慮了成本(處理費(fèi)和運(yùn)費(fèi))和環(huán)境負(fù)效應(yīng)，但忽略了建站費(fèi).韓毅等[2]建立了廢棄物處理站選址多目標(biāo)模型，再將多目標(biāo)轉(zhuǎn)換為單目標(biāo)，應(yīng)用和諧搜索算法求解.何波等[3]研究了廢棄物逆向物流網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，并設(shè)計(jì)基于啟發(fā)式的兩階段分解算法求解.黃錚[4]針對(duì)有害廢棄物處理站選址建立了雙目標(biāo)優(yōu)化模型，并給出一個(gè)多項(xiàng)式時(shí)間算法求解.胡雙海等[5]分析了影響廢棄物處理站選址因素.何波等[6]建立了廢棄物逆向物流網(wǎng)絡(luò)設(shè)計(jì)的多目標(biāo)優(yōu)化模型，采用兩階段模糊算法求解.呂新福等[7]建立了PLRP-IF模型，應(yīng)用啟發(fā)式算法求解.Smith[8]建立了一個(gè)雙準(zhǔn)則選址模型,模型最終通過(guò)傅里葉消元法來(lái)完成.Alumur 和 Kara[9]建立了選址-路徑問(wèn)題多目標(biāo)模型，運(yùn)用了 GIS 技術(shù)和 CPLEX 軟件求解.Brimberg和ReVelle[10]建立了以總成本最小和未被服務(wù)的需求點(diǎn)最少為目標(biāo)的雙目標(biāo)模型，通過(guò)加權(quán)法求解.Giannikos[11]建立的多目標(biāo)模型，應(yīng)用目標(biāo)規(guī)劃求解.文獻(xiàn)[1-3,6-9,11]的模型中的總成本沒(méi)有考慮垃圾處理費(fèi)用，文獻(xiàn)[4-5]沒(méi)有具體的模型和算法，文獻(xiàn)[10]的模型雖然考慮了總成本，但沒(méi)有考慮環(huán)境負(fù)效應(yīng).本文從經(jīng)濟(jì)效益和環(huán)境效應(yīng)兩方面綜合考慮，研究廢棄物的中轉(zhuǎn)站和處理站的選址，以總成本最低和環(huán)境負(fù)效應(yīng)最小為目標(biāo)，用權(quán)重和(采用隨機(jī)權(quán)重方法，在選擇過(guò)程中的每一步都隨機(jī)給出權(quán)重，由此可以給所有可能的組合以平等的機(jī)會(huì))方法把雙目標(biāo)轉(zhuǎn)換為單目標(biāo)，建立優(yōu)化模型，模型中的總成本不僅考慮了建站成本和運(yùn)費(fèi)，還考慮了垃圾處理費(fèi)，使模型考慮的因素更全面，讓決策者根據(jù)企業(yè)戰(zhàn)略選擇適合的方案.

進(jìn)化算法可以應(yīng)用于不同的領(lǐng)域，如協(xié)同車輛路徑問(wèn)題[12]、物流配送中心選址問(wèn)題[13]、垃圾收運(yùn)系統(tǒng)問(wèn)題[14]、油田區(qū)域配電網(wǎng)問(wèn)題[15]中. 由于本文的模型需要通過(guò)算法找到全局最優(yōu)解，而進(jìn)化算法具有內(nèi)在的隱并行性和良好的全局尋優(yōu)能力，這樣可以使算法在搜索過(guò)程中不容易陷入局部最優(yōu).

1 廢棄物處理站的選址問(wèn)題

針對(duì)廢棄物選址問(wèn)題，本文是以總成本(包括運(yùn)輸費(fèi)、中轉(zhuǎn)站的建設(shè)費(fèi)和處理站的建設(shè)費(fèi))最少和環(huán)境效應(yīng)(與中轉(zhuǎn)站和處理站到產(chǎn)生點(diǎn)的距離成反比，與它們的容量成正比)最小為目標(biāo)函數(shù)，再應(yīng)用權(quán)重和方法將雙目標(biāo)轉(zhuǎn)換為單目標(biāo)，以限制每個(gè)中轉(zhuǎn)站和處理站的容量、每個(gè)產(chǎn)生點(diǎn)的廢棄物只能運(yùn)往一個(gè)中轉(zhuǎn)站、每個(gè)中轉(zhuǎn)站中的廢棄物只能運(yùn)往一個(gè)處理站、運(yùn)往每個(gè)中轉(zhuǎn)站的廢棄物的總量不能超過(guò)其容量以及運(yùn)往每個(gè)處理站的廢棄物的總量不能超過(guò)其容量為約束條件，建立數(shù)學(xué)模型.該數(shù)學(xué)模型如下：

總成本

(1)

環(huán)境負(fù)效應(yīng)

(2)

z=ω1z1+ω2z2.

(3)

s.t

(4)

(5)

(6)

(7)

(8)

(9)

2 進(jìn)化算法

(1) 編碼.

采用二進(jìn)制編碼，染色體的基因位數(shù)是備選中轉(zhuǎn)站的個(gè)數(shù)與備選處理站的個(gè)數(shù)的和，即m+l，前m位對(duì)應(yīng)的是備選中轉(zhuǎn)站，后l位對(duì)應(yīng)的是備選處理站.如果前m位上有基因?yàn)?，表示對(duì)應(yīng)的中轉(zhuǎn)站被選中，建立中轉(zhuǎn)站，否則不建立中轉(zhuǎn)站；如果后l位上有基因?yàn)?，表示對(duì)應(yīng)的處理站被選中，建立處理站，否則不建立處理站.例如表示有10個(gè)備選中轉(zhuǎn)站和5個(gè)備選處理站，第3、4、6、10個(gè)備選中轉(zhuǎn)站被選建立中轉(zhuǎn)站，第2、5個(gè)處理站被選來(lái)建立處理站,則編碼為

0 0 1 1 0 1 0 0 0 1 0 1 0 0 1

(2) 適應(yīng)值函數(shù).

適值函數(shù)定為模型的目標(biāo)函數(shù)，為

F=z=ω1z1+ω2z2，

其中ω1,ω2的值隨機(jī)產(chǎn)生.

(3) 算法的具體步驟.

步驟1：對(duì)種群的個(gè)體，利用二進(jìn)制進(jìn)行編碼，隨機(jī)生成初始化種群P(0)，設(shè)置最大的迭代代數(shù)Gen_max，種群規(guī)模K、交叉率pc和變異率pm；

步驟2：通過(guò)計(jì)算各個(gè)染色體的適值，對(duì)它們進(jìn)行評(píng)估；

步驟3：采用輪轉(zhuǎn)法進(jìn)行選擇，從P(n)中選擇K個(gè)染色體到下一代P(n+1)；

步驟4：對(duì)P(n+1)進(jìn)行交叉(采用單斷點(diǎn)交叉法)和變異(采用基因位變異法)，產(chǎn)生新的P(n+1)；

步驟5：P(n)：=P(n+1)；

步驟6：如果滿足算法的終止條件，則停止，否則轉(zhuǎn)步驟2.

3 仿真實(shí)例

以我國(guó)某城市的數(shù)據(jù)為例仿真,如表1～3所示.我國(guó)每人每天產(chǎn)生1.1kg廢棄物，即α=1.1 kg/(人·d)，令γ=1元/(單位距離·t).

表1 備選中轉(zhuǎn)站的位置坐標(biāo)

用Matlab作出中轉(zhuǎn)站、產(chǎn)生點(diǎn)和處理站的散點(diǎn)圖,如圖1所示.

依照上面設(shè)計(jì)的遺傳多目標(biāo)優(yōu)化算法，用Matlab編寫出相應(yīng)的程序，求得結(jié)果如表4和表5所示.

由表4和表5所示的結(jié)果知道，在10個(gè)備選中轉(zhuǎn)站中，需要在第1、2、4、5、6、7、10個(gè)建站，在5個(gè)備選處理站中的第1和4個(gè)建立處理站.用Matlab程序得出在該方案下，所需要的總成本(建設(shè)費(fèi)、處理費(fèi)和運(yùn)費(fèi))為z1=1 593.7(萬(wàn)元)，產(chǎn)生的環(huán)境負(fù)效應(yīng)為z2=1 334.4.

表2 產(chǎn)生點(diǎn)的位置及人口

表3 備選處理站的位置坐標(biāo)

圖1 產(chǎn)生點(diǎn)、中轉(zhuǎn)站和處理站的散點(diǎn)圖

表4 中轉(zhuǎn)站的選址情況

Tab.4 The location of transfer stations

選擇的中轉(zhuǎn)站運(yùn)往此中轉(zhuǎn)站的產(chǎn)生點(diǎn)容量/t建設(shè)費(fèi)/萬(wàn)元18、13、16502529、10、11804047、21、22、23、2412060515、17、18、19、2012060614、28、29、3010050712、25、26、2710050101、2、3、4、5、69045

表5 處理站的選址情況

4 結(jié)論

隨著社會(huì)經(jīng)濟(jì)的發(fā)展，人們生活水平日益提高，產(chǎn)生的城市生活垃圾、廢棄物也大幅增加.政府面臨的一個(gè)重要問(wèn)題是如何處理這些廢棄物.本文主要研究了城市廢棄物中轉(zhuǎn)站和處理站的選址問(wèn)題，既考慮了經(jīng)濟(jì)因素又考慮了居民的意愿，建立多目標(biāo)模型.然后設(shè)計(jì)遺傳多目標(biāo)優(yōu)化算法，對(duì)數(shù)學(xué)模型求解，最終得到一組滿意的解.

[1] 何波，楊超，任鳴鳴.廢棄物處理站選址問(wèn)題及多目標(biāo)演化算法求解[J].系統(tǒng)工程理論與實(shí)踐，2007，26(11):72-79.

He B,Yang C,Ren M M.Waste treatment station location problem and multi-objective evolutionary algorithm[J].Systems Engineering Theory & Practice,2007,26(11):72-79.

[2] 韓毅，蔡建湖，周根貴,等.廢棄物處理站選址問(wèn)題的和諧搜索算法[J].計(jì)算機(jī)科學(xué)，2011，38(6)：255-258.

Han Y,Cai J H,Zhou G G,et al.Waste disposal harmony search algorithm location station[J].Computer Science,2011，38(6)：255-258.

[3] 何波，楊超，張華.廢棄物回收的多層逆向物流網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)問(wèn)題研究[J].中國(guó)管理科學(xué)，2007,15(3)：61-67.

He B,Yang C,Zhang H. Optimal design problem study of reverse logistics network of waste recycling of multilayer [J]. Chinese Journal of Management Science, 2007,15(3):61-66.

[4] 黃錚.有害廢棄物處理站選址近似帕累托集合的有效產(chǎn)生[J].運(yùn)籌與管理，2009,18(6)：70-74.

Huang Z.The treatment of hazardous waste generated approximate effective Pareto collection station siting[J].Operations Research and Management Science,2009,18(6)：70-74.

[5] 胡雙海，何波.論固體廢棄物轉(zhuǎn)運(yùn)站和處理站建立的選址及相關(guān)研究 [J]. 分析與決策,2007,26(1):67-69.

Hu S H,He B. On solid waste transfer station and treatment facility location and related research [J]. Analysis and Decision, 2007,26(1):67-69.

[6] 何波，楊超，楊珺.廢棄物逆向物流網(wǎng)絡(luò)設(shè)計(jì)的多目標(biāo)優(yōu)化模型[J].工業(yè)工程與管理，2007，1(5)：41-46.

He B,Yang C,Yang J.Multi objective optimization model of waste reverse logistics Mnetwork design[J].Industrial Engineering and Management,2007，1(5)：41-46.

[7] 呂新福 , 蔡臨寧 , 曲志偉 . 廢棄物回收物流中的選址-路徑問(wèn)題 [J]. 系統(tǒng)工程理論與實(shí)踐,2005,1(5):89-94.

Lü X F,Cai L N,Qu Z W. Location routing problem in the waste recovery Logistics [J]. Systems Engineering Theory & Practice, 2005,1(5):89-94.

[8] Melachrinoudis E, Smith J M. AnΟ(mn2) algorithm for the maximin problem inE2[J]. Operations Research Letters, 1995, 18:25-30.

[9] Alumur S, Kara B Y. A new model for the hazardous waste location-routing problem[J]. Computers & Operations Research, 2007, 34 :1406-1423.

[10] Brimberg J,ReVelle C.A bi-objective plant location problem:Cost vs. Demand served[J].Location Science,1998,1(6):121-135.

[11] Giannikos I.A multiobjective programming model for locating treatment sites and routing hazardous wastes[J].European Journal of Operational Research,1998,104(1):333-342.

[12] 謝桂芩，涂井先.分區(qū)域多目標(biāo)進(jìn)化算法協(xié)同車輛路徑問(wèn)題中的應(yīng)用[J].廣東工業(yè)大學(xué)學(xué)報(bào)，2011,28(4)：38-44.

Xie G Q,Tu J X.Subregional multi-objective evolutionary algorithm for the vehicle routing problem in collaborative applications[J].Journal of Guangdong University of Technology,2011，28(4)：38-44.

[13] 張金鳳, 陳蔚麗.多目標(biāo)進(jìn)化算法在物流配送中心選址中的應(yīng)用[J].廣東工業(yè)大學(xué)學(xué)報(bào)，2010，27(4)：76-80. Zhang J F,Chen W L.Application of multi objective evolutionary algorithm in location of logistics distribution center[J].Journal of Guangdong university of Technology,2010，27(4)：76-80.

[14] 張金鳳.多目標(biāo)進(jìn)化算法在垃圾收運(yùn)系統(tǒng)中的運(yùn)用[J].廣東工業(yè)大學(xué)學(xué)報(bào)，2011,28(2)：76-80.

Zhang J F.Application of multi objective evolutionary algorithm in waste collection and transportation system[J].Journal of Guangdong University of Technology,2011，28(2)：76:-80.

[15] 康忠健，訾淑偉.基于差分進(jìn)化算法的油田區(qū)域配電網(wǎng)無(wú)功優(yōu)化技術(shù)的研究[J].電工技術(shù)學(xué)報(bào),2013,28(6)：226-231.

Kang Z J,Zi S W.Study on reactive power optimization techniques without difference oilfield distribution network is divided based on evolutionary algorithm[J].Journal of Electrician Technique,2013,28(6):226-231.

Application of Evolutionary Algorithm in Waste Location

Chen Qi-ling， Wen Jie-chang， Lin Zhi-feng

(School of Applied Mathematics, Guangdong University of Technology, Guangzhou 510520, China)

The thesis lays its stress on the site selection of transfer station and treatment station of city wastes. The construction cost and freight and negative effects on environment will be taken into consideration in total cost and be restricted to the lowest level. Moreover, optimized models will be established and evolutionary algorithm will be designed to confirm the location, capacity and construction cost of transfer station and treatment station that need to be built. It also determines the conjunction point of transfer station as well as the transfer station of treatment station. Last, algorithm simulation demonstrates the feasibility and effectiveness of the algorithm.

waste location; optimized model; evolutionary algorithm

2014- 01- 06

陳齊玲(1989-)，女，碩士研究生，主要研究方向?yàn)樽顑?yōu)化方法及應(yīng)用。

10.3969/j.issn.1007- 7162.2015.03.011

X

A

1007-7162(2015)03- 0056- 05