进化算法在废弃物选址问题上的应用

陈齐玲，温洁嫦，林志逢

(广东工业大学 应用数学学院，广东 广州 510520)

进化算法在废弃物选址问题上的应用

陈齐玲，温洁嫦，林志逢

(广东工业大学 应用数学学院，广东 广州 510520)

研究城市废弃物中转站和处理站的选址问题，考虑总成本(建设费、运费)最低和环境负效应最小，建立优化模型.设计进化算法求解，确定要建立的中转站和处理站的位置、容量及建设费用，并确定了中转站服务的产生点和处理站服务的中转站.最后算例仿真表明了算法的可行性和有效性.

废弃物选址问题； 优化模型； 进化算法

随着城市生活垃圾、废弃物排放量的大幅度增加，人们必须采用合适的方式来处理这些废弃物.本文解决废弃物中转站和处理站的选址问题，是一个厌恶型设施的选址问题.如果中转站和处理站距离居民区太近，容易给居民带来难闻的气味和引来蚊虫；如果太远，运输费用又太高.中转站和处理站属于城市环境卫生基础设施，由政府部门做决策，应综合考虑对环境的影响最小和总成本最低等方面因素来建立废弃物中转站和处理站.

近年来，国内外很多学者对废弃物处理站选址问题进行了研究.何波等[1]采用多目标演化算法对废弃物处理站选址问题进行求解，该文献虽然考虑了成本(处理费和运费)和环境负效应，但忽略了建站费.韩毅等[2]建立了废弃物处理站选址多目标模型，再将多目标转换为单目标，应用和谐搜索算法求解.何波等[3]研究了废弃物逆向物流网络设计问题，并设计基于启发式的两阶段分解算法求解.黄铮[4]针对有害废弃物处理站选址建立了双目标优化模型，并给出一个多项式时间算法求解.胡双海等[5]分析了影响废弃物处理站选址因素.何波等[6]建立了废弃物逆向物流网络设计的多目标优化模型，采用两阶段模糊算法求解.吕新福等[7]建立了PLRP-IF模型，应用启发式算法求解.Smith[8]建立了一个双准则选址模型,模型最终通过傅里叶消元法来完成.Alumur 和 Kara[9]建立了选址-路径问题多目标模型，运用了 GIS 技术和 CPLEX 软件求解.Brimberg和ReVelle[10]建立了以总成本最小和未被服务的需求点最少为目标的双目标模型，通过加权法求解.Giannikos[11]建立的多目标模型，应用目标规划求解.文献[1-3,6-9,11]的模型中的总成本没有考虑垃圾处理费用，文献[4-5]没有具体的模型和算法，文献[10]的模型虽然考虑了总成本，但没有考虑环境负效应.本文从经济效益和环境效应两方面综合考虑，研究废弃物的中转站和处理站的选址，以总成本最低和环境负效应最小为目标，用权重和(采用随机权重方法，在选择过程中的每一步都随机给出权重，由此可以给所有可能的组合以平等的机会)方法把双目标转换为单目标，建立优化模型，模型中的总成本不仅考虑了建站成本和运费，还考虑了垃圾处理费，使模型考虑的因素更全面，让决策者根据企业战略选择适合的方案.

进化算法可以应用于不同的领域，如协同车辆路径问题[12]、物流配送中心选址问题[13]、垃圾收运系统问题[14]、油田区域配电网问题[15]中. 由于本文的模型需要通过算法找到全局最优解，而进化算法具有内在的隐并行性和良好的全局寻优能力，这样可以使算法在搜索过程中不容易陷入局部最优.

1 废弃物处理站的选址问题

针对废弃物选址问题，本文是以总成本(包括运输费、中转站的建设费和处理站的建设费)最少和环境效应(与中转站和处理站到产生点的距离成反比，与它们的容量成正比)最小为目标函数，再应用权重和方法将双目标转换为单目标，以限制每个中转站和处理站的容量、每个产生点的废弃物只能运往一个中转站、每个中转站中的废弃物只能运往一个处理站、运往每个中转站的废弃物的总量不能超过其容量以及运往每个处理站的废弃物的总量不能超过其容量为约束条件，建立数学模型.该数学模型如下：

总成本

(1)

环境负效应

(2)

z=ω1z1+ω2z2.

(3)

s.t

(4)

(5)

(6)

(7)

(8)

(9)

2 进化算法

(1) 编码.

采用二进制编码，染色体的基因位数是备选中转站的个数与备选处理站的个数的和，即m+l，前m位对应的是备选中转站，后l位对应的是备选处理站.如果前m位上有基因为1，表示对应的中转站被选中，建立中转站，否则不建立中转站；如果后l位上有基因为1，表示对应的处理站被选中，建立处理站，否则不建立处理站.例如表示有10个备选中转站和5个备选处理站，第3、4、6、10个备选中转站被选建立中转站，第2、5个处理站被选来建立处理站,则编码为

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

(2) 适应值函数.

适值函数定为模型的目标函数，为

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

其中ω1,ω2的值随机产生.

(3) 算法的具体步骤.

步骤1：对种群的个体，利用二进制进行编码，随机生成初始化种群P(0)，设置最大的迭代代数Gen_max，种群规模K、交叉率pc和变异率pm；

步骤2：通过计算各个染色体的适值，对它们进行评估；

步骤3：采用轮转法进行选择，从P(n)中选择K个染色体到下一代P(n+1)；

步骤4：对P(n+1)进行交叉(采用单断点交叉法)和变异(采用基因位变异法)，产生新的P(n+1)；

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

步骤6：如果满足算法的终止条件，则停止，否则转步骤2.

3 仿真实例

以我国某城市的数据为例仿真,如表1～3所示.我国每人每天产生1.1kg废弃物，即α=1.1 kg/(人·d)，令γ=1元/(单位距离·t).

表1 备选中转站的位置坐标

用Matlab作出中转站、产生点和处理站的散点图,如图1所示.

依照上面设计的遗传多目标优化算法，用Matlab编写出相应的程序，求得结果如表4和表5所示.

由表4和表5所示的结果知道，在10个备选中转站中，需要在第1、2、4、5、6、7、10个建站，在5个备选处理站中的第1和4个建立处理站.用Matlab程序得出在该方案下，所需要的总成本(建设费、处理费和运费)为z1=1 593.7(万元)，产生的环境负效应为z2=1 334.4.

表2 产生点的位置及人口

表3 备选处理站的位置坐标

图1 产生点、中转站和处理站的散点图

表4 中转站的选址情况

Tab.4 The location of transfer stations

选择的中转站运往此中转站的产生点容量/t建设费/万元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 结论

随着社会经济的发展，人们生活水平日益提高，产生的城市生活垃圾、废弃物也大幅增加.政府面临的一个重要问题是如何处理这些废弃物.本文主要研究了城市废弃物中转站和处理站的选址问题，既考虑了经济因素又考虑了居民的意愿，建立多目标模型.然后设计遗传多目标优化算法，对数学模型求解，最终得到一组满意的解.

[1] 何波，杨超，任鸣鸣.废弃物处理站选址问题及多目标演化算法求解[J].系统工程理论与实践，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] 何波，杨超，张华.废弃物回收的多层逆向物流网络优化设计问题研究[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] 黄铮.有害废弃物处理站选址近似帕累托集合的有效产生[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] 胡双海，何波.论固体废弃物转运站和处理站建立的选址及相关研究 [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] 何波，杨超，杨珺.废弃物逆向物流网络设计的多目标优化模型[J].工业工程与管理，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]. 系统工程理论与实践,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] 谢桂芩，涂井先.分区域多目标进化算法协同车辆路径问题中的应用[J].广东工业大学学报，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] 张金凤, 陈蔚丽.多目标进化算法在物流配送中心选址中的应用[J].广东工业大学学报，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] 张金凤.多目标进化算法在垃圾收运系统中的运用[J].广东工业大学学报，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].电工技术学报,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-)，女，硕士研究生，主要研究方向为最优化方法及应用。

10.3969/j.issn.1007- 7162.2015.03.011

X

A

1007-7162(2015)03- 0056- 05