陳齊玲，溫潔嫦，林志逢

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

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

陳齊玲，溫潔嫦，林志逢

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

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

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

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

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

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

1 廢棄物處理站的選址問題

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

總成本

(1)

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

(2)

z=ω1z1+ω2z2.

(3)

s.t

(4)

(5)

(6)

(7)

(8)

(9)

2 進化算法

(1) 編碼.

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

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

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

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

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

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

(3) 算法的具體步驟.

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

步驟2：通過計算各個染色體的適值，對它們進行評估；

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

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

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

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

3 仿真實例

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

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

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

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

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

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

表3 備選處理站的位置坐標

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

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

Tab.4 The location of transfer stations

選擇的中轉(zhuǎn)站運往此中轉(zhuǎn)站的產(chǎn)生點容量/t建設(shè)費/萬元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é)論

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

[1] 何波，楊超，任鳴鳴.廢棄物處理站選址問題及多目標演化算法求解[J].系統(tǒng)工程理論與實踐，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] 韓毅，蔡建湖，周根貴,等.廢棄物處理站選址問題的和諧搜索算法[J].計算機科學，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].中國管理科學，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].運籌與管理，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)運站和處理站建立的選址及相關(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è)計的多目標優(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] 呂新福 , 蔡臨寧 , 曲志偉 . 廢棄物回收物流中的選址-路徑問題 [J]. 系統(tǒng)工程理論與實踐,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ū)域多目標進化算法協(xié)同車輛路徑問題中的應(yīng)用[J].廣東工業(yè)大學學報，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] 張金鳳, 陳蔚麗.多目標進化算法在物流配送中心選址中的應(yīng)用[J].廣東工業(yè)大學學報，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] 張金鳳.多目標進化算法在垃圾收運系統(tǒng)中的運用[J].廣東工業(yè)大學學報，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] 康忠健，訾淑偉.基于差分進化算法的油田區(qū)域配電網(wǎng)無功優(yōu)化技術(shù)的研究[J].電工技術(shù)學報,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ōu)化方法及應(yīng)用。

10.3969/j.issn.1007- 7162.2015.03.011

X

A

1007-7162(2015)03- 0056- 05