基于改进遗传算法的废旧家电回收网络模型研究

基于改进遗传算法的废旧家电回收网络模型研究江前斌， 汤兵勇( 东华大学 旭日工商管理学院，上海 200051)摘 要: 废旧家电作为可再生资源的一种，其体积大、回收价值高等特点引起了人们广泛关注，合理规划废旧家电回收网络是目前许多专家学者关注的问题。以上海某家废品回收公司为背 景，深入研究废旧家电回收体系结构，建立居委会和交投站两层废旧家电回收网络结构模型，然后 提出了改进遗传算法的数学模型并进行实例计算，最后对模型进行灵敏度分析从而获取较优的算 法参数。关键词: 废旧家电; 回收网络选址; 优化模型; 遗传算法中图分类号:F252文献标志码:A文章编号:1001 7011( 2011) 01 0028 060引言随着我国社会经济的发展，人民生活水平不断提高，自 20 世纪 80 年代以来家用电器逐步普及，目前我国已经成为家用电器产品的生产和消费大国。废旧家电产品既具有环境污染的潜在性，又具有再生资源回 收价值的可用性1。废旧家电的回收属于逆向物流领域，目前大多数文献求解逆向物流回收网络的方法主要是整数规划算 法及优化算法。冯勤超，顾宁生2考虑新建和扩建逆向物流设施的残值、拆解中心、再使用中心以及与供应 链的集成等几个因素的基础上，进行了逆向物流网络设计，并在此基础上构建逆向物流的混合整数线性规划 模型和算例分析。薛雷，王志平3通过建立混合整数规划模型，构建了一个由第三方物流参与的逆向物流网络，模型将提供的回收、检测、分拣服务的第三方物流加入到逆向物流网络中，使传统的三层逆向物流网络 变成 4 层。何波，杨超，张华4等针对固体废弃物的回收问题，构建了一个两层的逆向物流网络系统，研究了 如何确定回收站和处理站的地址和数量，废弃物产生点的分配以及废弃物的存储和运输问题，建立了一个多 目标的整数规划模型。谭瑛，高慧敏，曾建潮5针对整数规划问题的特点，提出了一种在整数空间中进行进化计算的 PSO 算法，使微粒群的进化限于整数空间，仿真实验结果验证了方法的正确性与有效性。谢如鹤， 邱祝强6考虑到客户、初始回收点和回收中心 3 个层次的逆向物流网络，以最小化总的相关成本建立了一 个内嵌两个指派模型的非线性混合整数规划模型并用遗传算法进行求解。本文主要研究废旧家电回收过程中两个主要待解决的问题: 交投站数目及位置的确定、交投站及客户回收点之间的对应关系。建立目标规划模型，通过改进的遗传算法进行求解。1废旧家电回收网络结构废旧家电产生主要是来源于各个社区的居民家中，废品回收公司都会在各个主要区域设置交投站，专门回收居民产生的废旧品。随着人们生活水平的提高，每年废旧家电产生量呈现不断上升的趋势。为了能够让废品充分利用，政府部门也在不断制定相关的回收政策，从而让回收工作更加顺利。许多居委会担任起对小区内的废旧家电的集中回收工作，废品回收公司定期到各区的家电集中点进行回收。目前大多数废旧家收稿日期: 2010 09 26基金项目: 国家自然科学基金重点资助项目( 70832005) ; 上海市第三期重点学科资助项目( S30504)作者简介: 江前斌( 1978 ) ，男，硕士研究生，主要研究方向: 电子商务与物流管理控制通讯作者: 汤兵勇( 1950 ) ，男，教授，博士生导师第 1 期江前斌等: 基于改进遗传算法的废旧家电回收网络模型研究29电回收网络的结构如图 1 所示。图 1 中虚线框代表选中的设施网点，废旧家电回收 的过程主要是: 居民把废旧家电统一运送到居委会指定 的收集点，废品回收公司派车把居委会收集点的家电回 收到对应的交投站，最后再将交投站的废旧家电统一运 到处理中心。交投站主要是对废旧家电进行简单的分类 拆分处理，可以认为是初级处理中心。假设处理中心的位置及选择运营的数目已经固定， 本文建立居委会和交投站的两层废旧家电回收网络结 构，考虑并解决以下两个问题: 如何从备选交投站中选择 运营的交投站; 各个居委会收集点的废旧家电应该由哪个交投站回收。本文仅考虑静止的回收网络选址，不考虑各个交投站以及处理中心的存储周期。2 废旧家电回收网络选址数学模型2. 1模型假设1 本文废旧家电回收网络模型中处理站数量固定且唯一，模型仅对交投站和居委会收集点进行网络规 划定位;234567各个交投站允许的废旧家电最大容量、回收点的位置以及产生的家电回收量已知;交投站的固定成本和单位距离成本通过详细调研可知; 假设回收点到交投站之间的距离为直线距离，通过经纬度可计算获得; 在指定区域内，必然存在一个交投站，其最大容量大于任何一个居委会收集点产生的废旧家电量; 指定区域内备选交投站总的容量大于所有回收点产生的总家电量; 该模型目标总成本仅由交投站的固定成本和距离运输成本构成，不考虑其他成本因素。2. 2模型参数xij : 第 i 个交投站对应回收第 j 个回收点; xi : 第 i 个备选交投站;Z2 : 第二个目标函数，表示选中的交投站数目; n: 备选交投站的数目;m: 回收点的数目; Dij : 从第 i 个交投站到第 j 个回收点的直线距离; Kij : 第 i 个交投站对应回收第 j 个回收点的关系集合;D: 选中交投站和所有对应的回收点之间总运输距离;Cd : 单位距离的运输成本; Ci : 第 i 个交投站的固定成本;Bj : 第 j 个回收点产生的废旧家电量; Ui : 第 i 个交投站的最大容量。其中决策变量定义如下:0，0，否则1，选择备选交投站 i1，第 i 个交投站回收第 j 个居委会收集点xi =， k =ij否则2. 3数学建模 Dij + xi *i = xi j KijminZ1 = Cd *Ci约束条件:任何一个交投站回收的废旧家电总量不能超过其最大的容量约束 Bj1 = Ui ;xij xi = n;2 选中的交投站最小为 1，最大不能超过备选交投站数目 03 每个居委会收集点只能由一个交投站回收 kij = 1，i xi 。j33. 1改进遗传算法设计染色体编码本模型将所有的回收点编号，即 1，2，m，并对交投站编号 1，2，n，即。在染色体编码过程中，以各30第 28 卷黑 龙 江 大 学 自 然 科 学 学 报个回收点为研究对象，染色体的长度等于回收点的数量 m。基因座上的值是回收点对应的的交投站的编号，该编号初始化是从 n 个交投站中随机产生一个数。例如，有 5 个交投站，编号分别为 1，2，5。10 个回收点分别为 1，2，10。在编码过程中，该染色体的长度为 10，假设初始化的染色体为 2 1 3 4 5 2 1 2 4 3，代表 1 号回收点废旧家电应该送到 2 号交投站，以此类推。3. 2染色体初始化根据编码方式，染色体的长度为 m。根据模型约束可以看出，并不是所有的染色体都是有效的。需要对初始化产生的每个个体进行约束判断，只有满足约 束条件的染色体才能够作为有效染色体，否则重新生 成。根据 2. 3 节第一个约束条件，初始产生的染色体需要计算各个选中的交投站需要回收的废旧家电是否超出其容量限制。假设交投站的数量为 10，回收点的 数量为 14，初始化如图 2 所示的染色体:可以看出，该染色体选择的交投站有 1、2、3、7、8 五个交投站。其中 1 号交投站对应的回收点是 1、7、9、10、13、14 号回收点; 2 号交投站对应的回收点是 6、12 号回收点; 3 号回收点对应的回收站是 2、3、4、5 号回收点; 7 号交投站对应的回收点是 9、10 号回收点; 8 号交投站对应的回收点是 8、11 号回收点;根据上述的对应关系，计算出各个交投站最大容量与其对应回收点废旧家电总产生量之间的关系。倘若前者小于后者，染色体需要重新生成。若前者大于后者，该染色体则为有效地染色体。3. 3 选择、交叉、变异操作选择操作采用轮盘选择，交叉操作采用多点交叉，先随机产生两个交叉点设为 Pot1 和 Pot2 ，这两个交叉点必须小于染色体的长度，且大于 0。同时前一个交叉点 Pot1 要小于后一个交叉点 Pot2 。即 0 Pot1 m，0 Pot2 m，且 Pot1 Pot2 。将匹配的两个染色体 Pot1 和 Pot2 之间的部分进行相互交换，从而得到新的两个 染色体。变异操作具体过程是: 将种群中各个个体的各个基因座作为变异对象，初始化产生一个 0 到 1 之间 的小数，和初始化的变异概率 Pm 比较，若其小于变异概率，则该点为突变的点，随机产生与突变点原始值不 同的点，从而得到新的变异个体。需要说明的是，该突变方式可以让选择的交投站数目发生变化，同时交投 站和回收点总距离也会发生变化，从而程序在另一个解集区域内进行搜索，跳出局部最优的情况。3. 4改进的遗传算法结合前面介绍的遗传算法操作步骤，本文通过算例发现: 除非迭代次数和种群规模设置很大，否则程序给出的结果都是次优解。原因是遗传算法容易在迭代过程中破坏种群优良个体，使得这些优良个体无法保留到下一代种群。为了解决以上问题，通过阅读大量相关的改进算法文献和程序测试，采用了文献7介绍的自适应度交叉和变异概率的方法来优化原来的模型。1 自适应交叉率由于交叉操作是为了产生新的个体，实现全局搜索的能力。因此，从种群整体进化过程来看，交叉概率 应该能随进化过程逐渐变小，到最后趋于某一稳定值，以避免对算法后期的稳定性造成冲击而导致算法不能 收敛，或收敛过程加长; 而从产生新个体的角度来看，种群中的所有个体在交叉操作上应该具有同等地位，即 相同的概率，从而使 GA 在搜索空间具有各个方向的均匀性7。本文改进的交叉概率与迭代次数有关，而与 种群内的个体无关，具体交叉概率的计算公式为:( t / maxGen)Pc，t = Pc ，max * 2如果 Pc，t Pc，min ，Pc ( t) = Pc，t ; 否则 Pc ( t)= Pc，min上述公式参数 t 为当前迭代数，maxGen 为最大种群数，Pc，t 为第 t 代临时交叉变量，Pc ，max 为最大交叉率，Pc，min 为最小交叉率，Pc ( t) 为第 t 代的交叉率。通过上述改进，当迭代次数越大的时候，临时交叉变量 Pc，t 越 小，交叉个体也逐渐减少，最后趋近于某个值，即最小交叉概率 Pc，min 。然而自适应交叉率是对种群所有个体 进行优化，但是并未能够处理种群中存在的较劣个体，下面介绍的自适应变异率能够很好地解决这个问题。2 自适应变异率变异算子主要作用是防止迭代出现早熟情况，传统的方法将所有迭代种群设置相同的变异率存在如下 的弊端: 首先，从种群整体上来看，随着迭代次数的增加，种群朝较优群体靠拢，因此迭代越多，变异概率应该 适当减少，从而能够维持较优个体。其次，每代中优良的个体和较差的个体都具备相同的变异概率，这样可第 1 期江前斌等: 基于改进遗传算法的废旧家电回收网络模型研究31能破坏了优良的个体，较差的个体并不能够得到变异改善。因此在变异率上需要集合考虑迭代次数以及个体适应度值。结合文献7，改进的自适应变异率的公式如下所示:fmax f( Xi)Pm，t = exp ( ) * 1 *Pm，maxfmax1 + t / maxGen如果 Pm，t Pm，min ，Pm ( t) = Pm，t 。否则 Pm ( t)= Pm，min上述公式参数 t 为当前迭代数，maxGen 为最大种群数，Pm，t 为第 t 代临时变异变量，Pm ，max 为最大变异率，Pm，min 为最小变异率，Pm ( t) 为第 t 代的变异率。通过上述自适应变异率，每个个体的变异率由其适应值和当 前种群迭代次数决定，从而使得变异操作更加合理。4实例分析4. 1实例描述本文采用 C# net 对回收网络选址模型进行编程，根据测试本文选取初始化的基本数据为: 单位运输距 离为 20 元 / 公里，种群规模 200，迭代次数 400，最大交叉率为 0. 85，最小交叉率为 0. 45，最大变异率为 0. 09， 最小变异率为 0. 05。本算例中共有 7 个交投站，11 个回收点。交投站的数据信息如表 1 所示:表 1 交投站数据表Talbe 1Deliever center data交投站名称经度纬度固定费用( 元)最大容量( kg)长宁 1 号站长宁 2 号站 长宁流动站 电子回收中心 杨安交投站 强发交投站121. 418 831. 201 860 0004 000121. 414 631. 220 8140 00014 000121. 416 731. 200 9840 00012 000121. 377 431. 218 0930 00010 000121. 472 931. 230 7120 0005 000121. 350 9121. 433 131. 223 3531. 202 6260 00050 0006 0008 000杨华交投站回收点数据如表 2 所示:表 2 回收点数据表Talbe 2 Collection points data回收点名称经度纬度产生量( kg)华阳路街道办事处新华街道办事处江苏路街道办事处121. 423 531. 210 2820121. 426 131. 204 51200121. 447 6121. 407 3121. 409 1121. 407 3121. 394 831. 225 3731. 217 5531. 197 2531. 209 231. 2044003001305002 100周桥街道办事处虹桥街道办事处天山街道办事处仙霞街道办事处本文将改进的遗传算法融入到选址模型中，通过 Google 地图 API 调用获取居委会及交投站的经纬度信息，然后根据经纬度计算出交投站和回收点之间的距离矩阵。该模型初始化数据除了距离矩阵外，还需要获取回收点废旧家电产生量和交投站回收的最大容量、交投站固定费用以及单位运输费用等信息。程序通过迭代计算 10 次结果如表 3 所示。由此可以看出 10 次程序给出了同一个方案: 选择交投站 3 个、总距离为 17 483 米、总成本为 459 666 元。但是由于遗传算法的局限性，容易陷入局部最优获得次优解。虽说自适应变异操作能够使迭代跳出局 部最优，但是不能保证每次代码运行都能够得到最优解。这里之所以得到确定的方案是因为种群规模和迭 代次数都设置的较大，因此搜索的空间也相对较大，容易搜到最优解。32第 28 卷黑 龙江 大学 自 然 科 学学报表 3Talbe 3程序运行 10 次结果表Ten times program results序号交投站数目总距离( 米)总成本( 元)计算时间13 个3 个3 个3 个3 个3 个3 个3 个3 个3 个17 483459 6662 秒 0 毫秒2 秒 31 毫秒2 秒 0 毫秒1 秒 984 毫秒1 秒 968 毫秒2 秒 0 毫秒2 秒 15 毫秒2 秒 0 毫秒2 秒 0 毫秒2 秒 15 毫秒217 483459 666317 483459 666417 483459 666517 483459 66667891017 48317 48317 48317 48317 483459 666459 666459 666459 666459 6664. 2算法灵敏度分析为了了解废旧家电网络规划遗传算法中各个参数对程序结果以及运行时间的影响，本节主要对迭代次数、种群规模、交叉概率、变异概率这三个主要的因素进行灵敏度分析。最后确定最佳的算法参数值，从而让该模型结果更加精确。1 迭代次数灵敏度分析在遗传算法中，迭代次数设置不宜过小，否则遗传算法可能搜索不到最优解。若设置为较大的值，算法 时间开销较大。本节选取初始化的基本数据为: 单位运输距离为 20 元 / 公里，种群规模 200，最大交叉率为0. 85，最小交叉率为 0. 45，最大变异率为 0. 09，最小变异率为 0. 05。先设置初始的迭代次数为 400 来分析，通过 10 次程序的运算结果表明，当得到取得最优解时，需要迭代的最大次数为 268 次( 见图 3 ) ，程序迭代400 次共需的时间开销平均大概为 1 秒 340 毫秒。在设置迭代次数的时候，最好设置大于 268 的值。当然为 了节约时间开销，设置的迭代次数不能过大，根据测试，建议迭代次数位于 400 450 之间，有 90% 以上的概 率保证每次获取得到最优解。2 种群规模灵敏度分析种群规模越大，染色体数目越多，因此获取最优解 得可能性越大。本节选取初始化的基本数据为: 单位运 输距离 为 20 元 / 公 里，迭 代 次 数 400，最 大 交 叉 率 为0. 85，最小交叉率为 0. 45，最大变异率为 0. 09，最小变 异率为 0. 05。设置当种群规模为 100 时，程序运行 10 次，有 6 次能够获取到最优解，换句话说只有 60% 概率 获取最优解。随着种群规模的扩大，取得最优解的概率 也逐渐上升。经测试，当种群规模至少取 250 时，程序 有 90% 以上的概率取得最优解。3 交叉概率灵敏度分析 采用自适应的交叉概率，随着迭代次数的增加，交叉概率逐渐降低到一个稳定的值。 该模型需要指定最大交叉概率和最小交叉概率。本节选取初始化的基本数据为: 单位运输距离为 20元 / 公里，迭代次数 400，种群规模为 100，最大变异率为 0. 09，最小变异率为 0. 05。经过测试，只要最大交叉概率不设置过小，基本上变异操作的两个参数对程序结果没有什么太大的影 响。4 变异概率灵敏度分析采用自适应的变异率，该变异率和个体适应度值和迭代次数相关。本节选取初始化的基本数据为: 单位 运输距离为 20 元 / 公里，迭代次数 400，种群规模为 100，最大交叉率为 0. 85，最小交叉率为 0. 45。通过测 试，该模型最大变异率不能过大，当值 0. 15 时，得到最优解的概率为 60% ，随着最大变异率值的增大，获得 最优解的概率逐渐降低。最小变异率一定要比最大变异率小一定的数值，否则产生不了最优解，自适应变异第 1 期江前斌等: 基于改进遗传算法的废旧家电回收网络模型研究33率也会失去意义。根据以上分析的结果，本文采用的参数为: 单位运输距离为 20 元 / 公里，种群规模 200，迭代次数 400，最 大交叉率为 0. 85，最小交叉率为 0. 45，最大变异率为 0. 09，最小变异率为 0. 05。5结论针对废旧家电网络规划问题，大多数文献以回收中心为对象采用整数 0 1 规划模型求解，本文采用以回收点为对象、染色体基因座的值为交投站的序号的编码方式，通过该编码方式，一方面能够从备选的交投 站中选择进行回收的交投站，另一方面能够得出回收点和交投站之间的对应关系。改进的遗传算法较好地 保留种群的优良个体，能够较稳定地获取全局最优值。通过对算法各参数的敏感度分析，得出该算法相对较 理想的设置参数。不同城市地区废旧家电回收网络结构不一定相同，本文主要考虑的是交投站和居委会两层结构，但是许 多地区可能还需要考虑多层回收网络结构。此外，本文的模型求解空间会随着问题规模的扩大而迅速上升， 当居委会数目较大的时候，求解最优解的时间会比较长，因此可以考虑先聚类后规划的方法，这也是今后需 要进一步研究的方向。参考文献1234567韩钢 我国废旧家电逆向物流的市场化运作模式研究D 大连: 大连海事大学，2007冯勤超，顾宁生 逆向物流网络优化设计模型J 东南大学学报( 自然科学版) ，2007，11: 322 326 薛雷，王志平 基于第三方物流的逆向物流优化模型J 大连海事大学学报，2007，12: 164 166 何波，杨超，张华，等 固体废弃物逆向物流网络优化设计J 系统工程，2006( 8) : 38 41 谭瑛，高慧敏，曾建潮 求解整数规划问题的微粒群算法J 系统工程理论与实践，2004( 5) : 126 129 谢如鹤，邱祝强 遗传算法在逆向物流网络规划设计中的应用J 武汉理工大学学报，2007( 10) : 902 905 欧阳森，王建华 一种新的改进遗传算法及其应用J 系统仿真学报，2003，15( 8) : 1066 1073Analysis on recycling network model of obsolete household appliancesbased on Improved Genetic AlgorithmJIANG Qian-bin， TANG Bing-yong( School of Glor