混合遗传算法求解退役工程机械回收及再制造系统中的碳排放问题

邓乾旺 徐博文 廖浩岚 刘霞辉

(湖南大学汽车车身先进设计制造国家重点实验室 湖南 长沙 410082)

混合遗传算法求解退役工程机械回收及再制造系统中的碳排放问题

邓乾旺 徐博文*廖浩岚 刘霞辉

(湖南大学汽车车身先进设计制造国家重点实验室 湖南 长沙 410082)

对退役产品进行回收及再制造能够降低二氧化碳的排放量，但尚没有一个定量模型对退役产品的整个回收及再制造过程的碳排放进行评估。针对这种现状，以工程机械退役产品为对象，对回收及再制造过程中的“碳足迹”进行深入研究，建立了工程机械产品回收及再制造过程的碳排放评估模型；并采用改进的混合遗传算法对模型进行了求解，该算法将遗传算法和模拟退火算法相结合以克服它们各自在局部搜索和全局搜索方面的缺陷，引入了竞争机制和自适应机制来进一步抑制算法的早熟，实现了对复杂回收及再制造网络系统的高效处理。实例结果表明，该模型能够有效地解决退役产品回收及再制造系统的碳排放计算问题。

工程机械产品 回收及再制造系统 碳排放 混合遗传算法(HGA)

0 引 言

由全球气候变暖引发的一系列连锁反应对人类的生存造成了极大的威胁，环境问题受到了人们的广泛关注，这在很大程度上促进了整个退役产品再制造行业的发展。退役产品的回收及再制造过程对环境带来的影响，主要包括：(1) 运输过程导致的二氧化碳排放；(2) 退役产品的再制造过程，从回收入厂、清洗、检测、拆解、修复到最终处理等，造成的额外资源消耗和废弃物排放。另一方面，随着低碳经济和绿色经济等经济模式的提出，碳排放作为衡量环境状况的一个关键指标，被越来越多的学者引用和研究。同时，伴随着再制造过程的一系列不确定性因素，如回收产品的质量、顾客的需求、回收产品的价格、数量等，增加了对退役产品回收及再制造过程的环境效益评估的难度。因此，如何在一系列不确定性的因素下，有效地衡量和评估工程机械退役产品的回收与再制造过程对环境带来的影响，是一个亟待解决的问题。

关于制造过程碳排放的研究基本上侧重于传统制造业或运输业的碳排放，而关于退役产品的回收和再制造过程碳排放的研究非常少。Alsaffar等[1]。研究了产品从设计到整个制造过程的碳足迹。刘明达等[2]对现有的一些碳排放的核算方法进行了研究和对比。Yu[3]和史春阳[4]研究了运输过程中的碳排放问题。Kim等[5]以发电机作为案例，评估了汽车再制造的经济性和环境性。Goldey等[6]建立了废旧电子通信产品回收链上的环境效益评价模型。Appleby等[7]对比了不同的废旧产品再制造方法对应的“碳足迹”。关于再制造的效益评估方面，Golinska等[8]从经济、环境、社会维度评价再制造企业的可持续性和成熟度。也有很多学者通过不同的模型，探讨了再制造对资源和环境的影响[6,9-11]。关于再制造绿色绩效评估过程中的不确定因素分析主要集中在退役产品的再制造活动对经济效益的评估上[12-13]，而不是生态效益方面(如资源和环境效益)的评估。

通过以上的文献分析可知，目前尚缺乏一个量化的模型，对工程机械退役产品的整个回收及再制造全过程的碳排放进行估算。且由于整合了退役产品的再制造过程，使得回收网络各节点之间回收数量的决策由回收运输过程扩展到了退役产品的回收及再制造全过程，增加了模型求解的难度，用单纯的运输问题很难找到模型的最优解。针对以上情况，本文以工程机械退役产品为对象，对回收及再制造过程中的“碳足迹”进行深入研究。以“碳排放的减少量”作为衡量回收及再制造的环境效益的指标，建立了工程机械退役产品回收及再制造的碳排放评估模型，并结合遗传算法和模拟退火算法的优缺点，引入自适应机制，设计了自适应的混合遗传算法HGA(Hybrid Genetic Algorithm)对模型进行求解。并通过实例对比验证了算法的有效性。

1 退役产品回收及再制造过程中的“碳足迹”

工程机械退役产品的回收及再制造过程包括以下过程：对消费点的退役产品进行回收确认、将退役产品运输至回收中心、回收中心中转、回收中心运至再制造中心、整机清洗、整机初步鉴定、整机拆解、关键零部件鉴定、关键零部件修复、报废、直接再使用入库、修复入库等。回收及再制造的各个过程均伴随着不同程度的能源消耗，从而导致了二氧化碳排放量的增加。具体如图1所示。

图1 工程机械退役产品回收及再制造全过程的流程图

退役产品回收过程中的碳排放量主要产生于运输过程和中转存储过程，其中，运输过程中的碳排放量是回收过程碳排放的主要来源，且该过程中碳排放量的大小直接与运输车的油耗相关(可视为运输距离和运输数量的函数，见下文)。因此，在退役整机的回收过程中，运输距离和运输数量是影响碳排放的主要因素。另一方面，对于单台整机或零部件的再制造而言，无论是整机鉴定、整机拆解还是关键零部件的鉴定和修复过程，各阶段的能源或材料的消耗在很大程度上视退役整机的回收质量而定，即单台退役整机再制造过程中的碳排放量受回收整机质量的变动而变动。基于以上对回收及再制造过程“碳足迹”的分析，本文以工程机械退役产品的回收网络选址和回收质量的不确定性为出发点，建立了工程机械退役产品回收及再制造的碳排放评估模型。

2 模型建立

2.1 模型假设

(1) 假设各消费点位置是已知的，而回收网点和再制造中心需要从各自的备选地点选取，且各备选设施的位置及设施之间的距离已知。

(2) 各消费点的废旧产品的期望回收量是已知的；各回收网点的回收数量受其回收能力约束；各再制造中心的再制造数量也受到其再制造能力的约束。

(3) 单位产品的再制造过程中，可以回收x种关键零部件和y种材料。

(4) 工程机械退役产品可直接再使用的比率为λ(0≤λ≤1)；关键零部件可直接再使用的比率为γ(0≤γ≤1)。退役产品的关键零部件的报废率为θ。

(5) 质量不确定造成额外碳排放的函数ξ=c(τ1,τ2)。令产品及其关键零部件的质量系数分别为τ1和τ2，τ1和τ2在一定程度上可以反映退役产品的回收质量，即τ1和τ2值越大表示产品及其关键零部件的回收质量越高。

2.2 模型参数

1) 消费点的集合为k∈K={1,2,…,p}，再制造中心的备选地i∈I={1,2,…,m}，回收网点的备选地j∈J={1,2,…,n}。

2)RBi、SBj均为0-1变量，分别表示是否选择i和j地作为再制造中心和回收网点，当在i地建立再制造中心时，RBi=1，否则RBi=0。

3)RCi为在备选地建立再制造工厂的最大再制造能力(台)，HCj为在备选地建立回收网点的最大回收能力(台)。HRk为的消费点k的期望可回收量(台)。

7) 运输车每公里油耗(L)与运输距离l(kg)及重量g(t)的关系为:f(g,l)=ε0gl+φ0，其中ε0为油耗系数，φ0为常数[3]。每单位(L)汽油的二氧化碳排放量(kg)为μ1(根据中华人民共和国国家发改委制定的《省级温室气体清单编制指南》(发改办气候[2011]1041号)关于汽油和标准煤的二氧化碳排放系数的估算表，可取μ1=2.925 1)。

8) 再制造过程的额外碳排放量ξ视退役产品及其关键零部件的质量状况τ1和τ2取值如下：

其中，α1、α2、α3均小于0，对式(1)-式(4)的解释如下所示：

(2) 当退役产品不能直接再使用，其关键零部件可以直接再使用时，关键零部件直接进行简单处理后入库、待装配或再销售，该过程的额外消耗导致的碳排放与关键零部件的质量系数τ2相关。

(3) 当退役产品及其关键零部件均不能直接再使用，且关键零部件不报废时，关键零部件需要进行修复，直到满足要求的质量状态。该过程的额外消耗导致的碳排放与关键零部件的质量系数τ2也有密切关系。

(4) 当退役产品不能直接再使用，且关键零部件报废时，关键零部件需要进行报废处理，该过程的额外消耗导致的碳排放量为c1+c2+c4。

2.3 模型建立

目标函数:

目标函数中，各表达式的解释如下所示：

表示当退役产品不能直接再使用，且关键零部件报废时，再制造的碳排放减少量；

表示当退役产品及其关键零部件均不能直接再使用，且关键零部件不报废时，再制造碳排放的减少量；

表示当退役产品不能直接再使用，其关键零部件可以直接再使用时，再制造碳排放的减少量；

表示当退役产品可以直接再使用时，再制造碳排放的减少量。

约束条件：

(5)

(6)

(7)

(8)

0≤Qjk≤HRk0≤Qjk≤HCj

(9)

0≤Qji≤HCj0≤Qji≤RCI

(10)

0≤λ≤1 0≤γ≤1

(11)

0≤τ1≤1 0≤τ2≤1

(12)

RBi、SBj为0-1变量

(13)

α1、α2、α3均小于0

(14)

其中，式(5)表示从消费地到回收中心回收量的最大回收能力约束；式(6)表示从回收中心到再制造中心的再制造能力约束；式(7)表示从消费低到回收中心的消费点期望报废量约束；式(8)表示从回收中心到再制造中心的最大回收能力约束；式(9)、式(10)表示非负约束；式(11)、式(12)表示参数约束。

3 模型求解

模型在评估碳排放时，不仅涉及到了传统回收网络选址和运输问题，也整合了退役产品的再制造过程，使得回收网络各节点之间回收数量的决策由回收运输过程扩展到了退役产品的回收及再制造全过程，用单纯的运输问题很难对模型进行求解。因此，引入遗传算法进行求解，并结合模拟退火算法，竞争机制及自适应机制的思想对经典遗传算法进行改进，建立了更适宜解决此类问题的自适应混合遗传算法。

3.1 基本思路

遗传算法是一种基于达尔文进化论思想的全局优化搜索算法，在人工智能、优化组合、自动控制等领域有广泛的应用。但该算法在局部搜索方面性能较差，并且存在早熟现象，即当群体进化到算法的中后期，由于群体的多样性遭到破坏，算法由于陷入局部最优，导致搜索停滞不前。模拟退化算法将优化组合问题和统计学中的热平衡问题类比，可用于有效解决组合优化问题。与遗传算法不同的是，该算法具有较强的局部搜索的能力，但在全空间搜索方面有不足之处。因此，通过将遗传算法和模拟退火算法相结合，可以扬长避短，将模拟退火算法嵌入到遗传算法的变异循环中，改善其局部搜索不足的缺点。在此基础上，引入自适应机制，又能有效地解决早熟现象，大大提高收敛速度，减少算法运行的时间。

3.2 求解过程

利用自适应的混合遗传算法对该模型进行求解，算法求解过程如下：

1) 编码方法

采用二进制字符串对离散0-1变量RBi、SBj进行编码，每条染色体编码串可表示为：

例如，对于具有三个再制造中心备选地和四个回收网点备选地的模型，如某个体的染色体为[1,0,1|0,0,1,1]，该染色体表示的回收网络为：在再制造中心备选地1和3建立再制造中心，选择回收网点备选地3和4建立回收网点，不选用再制造中心备选地2和回收网点备选地1、2。

2) 选择算子

3) 交叉算子和竞争机制

个体之间的交叉策略采用单点交叉策略，父代以交叉概率Pc随机设定交叉点，将两个体交叉点之后的基因互换产生子代。同时为了保证交叉操作对解的有效性，在交叉操作上引入了竞争机制，即对每一次交叉产生的两个子代和父代的适应度进行逐一评价，筛选出适应度最高的两个个体，进入下一代种群。交叉操作过程如图2所示。

图2 有竞争机制的交叉操作过程

4) 变异算子和模拟退火机制

子代以变异概率Pm改变其染色体某基因位上的基因，变异策略为单点变异。为了提高变异的效率，加快解的收敛速度，在此引入模拟退火算法，个体i经过变异得到个体j，它们对应的能量分别为Ei=106/fi和Ej=106/fj。若Ei>Ej，则接受个体j为新的个体；若Ei

图3 模拟退火流程图

5) 自适应机制

交叉算子Pc和变异算子Pm作为遗传算法的核心，为算法不断地引入新的个体，开辟新的解空间。Pc的值越大，新个体产生的速度越快，但是Pc的值过大，则可能会破坏遗传的模式，导致高适应度的个体的基因结构受到破坏，交叉遗传也失去其本身的意义。如果Pc的值过小，则会降低算法遗传的效率。同样的，Pm的大小反映了变异的强弱，过小不易产生新的个体，过大遗传算法就会失去其本身的意思，编程纯粹的随机搜索算法。如果Pc和Pm能够根据适应值的变化自动调整自身取值，算法的搜索效率将会大大地优化。

本文在此引入自适应参数[9]设置方程使Pc和Pm能够处于自适应的状态。当种群适应度较集中时，Pc和Pm增大。同时，对于适应度较高的个体，采取较低的Pc和Pm值。反之采取较高的Pc和Pm，使其以高概率被淘汰。自适应参数的设置如式(13)、式(14)所示。

(13)

(14)

其中，Pc1=0.8，Pc2=0.6，Pm1=0.2，Pm2=0.02，fi为待评价个体的适应度，favg为当前种群的平均适应度，fmax为当前种群的最大适应值。

6) 终止准则

模型通过循环迭代寻找最优的决策，当种群个体的最优适值保持稳定或迭代达到了规定的进化代数时，循环终止。此时种群中的最优适值就是实际问题的满意值，最优适值对应的染色体即为实际问题的最优解。

4 算例分析

某工程机械再制造企业在全国设立了“再制造中心-回收网点”模式的回收及再制造网络，其总部位于武汉，分设武汉、南宁、成都、西安及乌鲁木齐五个再制造中心，并在全国设立构建18个回收网点，具备完善的回收及再制造体系。以该公司的回收再制造网络为例，构建一个有22个消费点，18个回收网点和5个再制造中心的三层回收再制造网络模型，各消费地的期望可回收量HRk、各回收网点的最大回收能力HCj以及各再制造中心的最大再制造能力RCi如表1所示。

表1 各网点的可回收(可处理)的产品数量/台

表2 关键零部件x消耗的循环材料y的量

产品及其零部件可直接再使用的比率分别为λ=0.2，γ=0.7，子代发生交叉概率Pc=0.8，变异概率Pm=0.2，θ=30。退役产品及其零部件的回收质量系数分别取τ1=0.4，τ2=0.8。

用C#语言分别编写混合遗传算法、遗传算法对碳排放评估模型进行求解，在VisualStudio2010软件环境，双核处理器@2.66GHz，2GB内存的硬件环境下，运行以上算例。经反复测试，取种群规模为30，最大迭代次数50次，得到两种算法的运行时间、最大适应度值及其对应的最优染色体(目标函数值)如表3所示。

表3 混合遗传算法与遗传算法的求解结果对比

上述算例的计算结果表明，对于一个具有十八个回收网点备选地和五个再制造中心备选地的回收网络系统，通过遗传算法和改善的混合遗传算法经过50次迭代，二氧化碳排放减少量均能收敛于一个合适的值。但在时间消耗上，两种算法有很大的差别，利用改善后的混合遗传算法求解该模型，所耗时间是遗传算法的30%左右，大大地缩减了求解的时间，求解效率大大提高。这主要归因于竞争机制和自适应机制的引入，限定了遗传和变异的方向，大大提高了最优解的收敛速度。同时混合遗传算法所得的最大适应值(103 917.811 3)相对于传统遗传算法的最大适应值(99 860.374 3)而言，准确度提高了4.1%。回收系统的各网点之间退役产品的配送数量如表2和表3所示，最大可节省二氧化碳的排放量为103 917.811 3kg。

另一方面，对比两种算法在每一次迭代所得的最大适应值，可以发现遗传算法在求解该模型的过程中，多次陷入适应度为99 860.374 3的染色体循环中，这也是导致经过50代之后，最大适应值仍停留在99 860.374 3的原因。这充分说明了本文提出的改进混合遗传算法具有较强的对抗局部极值的能力和较好的计算稳定性，主要是由于本文引入了模拟退火和自适应机制，使得算法始终具备开辟新的解空间的能力，减少了其陷入局部解空间的概率，并提高了局部搜索的效率，增强了算法的鲁棒性。

5 结 语

退役产品再制造效益的定量评估是回收和再制造评估的重点和难点。本文从环境效益的角度出发，选取“二氧化碳排放的减少量”作为衡量退役产品再制造环境效益的一个重要指标，建立了退役产品回收及再制造系统的碳排放定量评估模型。并设计了一种自适应的混合遗传算法，利用退火算法具有较强局部搜索能力的特点，将模拟退火算法嵌入到传统遗传算法中，并引入竞争和自适应机制，不仅有效地克服了遗传算法的早熟现象，也大大缩短了运算时间，提高了算法寻优的效率。实例结果表明，该算法能够有效地解决退役产品回收及再制造过程中的碳排放计算问题。此外，该算法也可为运输领域的非线性规划问题的求解提供一定的参考。

[1] Alsaffar A J,Haapala K R,Kim K Y,et al.A Process-Based Approach for Cradle-to-Gate Energy and Carbon Footprint Reduction in Product Design[C]//ASME 2012 International Manufacturing Science and Engineering Conference collocated with the 40th North American Manufacturing Research Conference and in participation with the International Conference on Tribology Materials and Processing.American Society of Mechanical Engineers,2012:1141-1150.

[2] 刘明达,蒙吉军,刘碧寒.国内外碳排放核算方法研究进展[J].热带地理,2014,34(2):248-258.

[3] Yu C H,Tseng C Y,Chuang S C.Evaluation of Fuel Economy and Emissions Reduction for a Motorcycle With Automatic Idling-Stop Device[J].Journal of Energy Resources Technology,2014,136(2):021206.

[4] 史春阳.同时取送货的车辆路径问题中的低碳研究[D].北京:清华大学,2011.

[5] Kim H J,Raichur V,Skerlos S J.Economic and Environmental Assessment of Automotive Remanufacturing:Alternator Case Study[C]//ASME 2008 International Manufacturing Science and Engineering Conference collocated with the 3rd JSME/ASME International Conference on Materials and Processing.American Society of Mechanical Engineers,2008:33-40.

[6] Goldey C L,Kuester E U,Mummert R,et al.Lifecycle assessment of the environmental benefits of remanufactured telecommunications product within a “green” supply chain[C]//Sustainable Systems and Technology (ISSST),2010 IEEE International Symposium on.IEEE,2010:1-6.

[7] Appleby M R,Buckley A B,Lambert C G,et al.A comparison of carbon footprint calculations for end of life product recovery methods using PAS 2050[C]//ASME 2010 10th Biennial Conference on Engineering Systems Design and Analysis.American Society of Mechanical Engineers,2010:705-713.

[8] Golinska P,Kuebler F.The Method for Assessment of the Sustainability Maturity in Remanufacturing Companies[J].Procedia CIRP,2014,15:201-206.

[9] Luglietti R,Taisch M,Magalini F,et al.Environmental and economic evaluation of end-of-life alternatives for automotive engine[C]//Engineering,Technology and Innovation (ICE),2014 International ICE Conference on.IEEE,2014:1-9.

[10] Du Y,Li C.Implementing energy-saving and environmental-benign paradigm: machine tool remanufacturing by OEMs in China[J].Journal of Cleaner Production,2014,66:272-279.

[11] Xiong Z K,Cao J,Liu K J.Study On the Quality Control Policy in the Closed-loop Supply Chain Based on the Dynamic Game Theory[J].Chinese Journal of Management Science,2007,15(4):42-50.

[12] Jin X,Hu S J,Ni J,et al.Assembly Strategies for Remanufacturing Systems With Variable Quality Returns[J].IEEE Transactions on Automation Science and Engineering,2013,10(1):76-85.

[13] Kizilboga G,Mandil G,Genevois M E,et al.Remanufacturing Network Design Modeling:A Case of Diesel Particulate Filter[J].Procedia CIRP,2013,11:163-168.

HYBRID GENETIC ALGORITHM FOR SOLVING CARBON EMISSION FROM RECYCLING AND REMANUFACTURING SYSTEM OF END-OF-LIFE MACHINERY PRODUCTS

Deng Qianwang Xu Bowen*Liao Haolan Liu Xiahui

(StateKeyLaboratoryofAdvancedDesignandManufacturingforVehicleBody,HunanUniversity,Changsha410082,Hunan,China)

Recycling and remanufacturing of end-of-life machinery products can reduce CO2emissions, but there is not yet a quantitative model to evaluate the overall carbon emission during the whole recycling and remanufacturing process. In view of this situation, with the end-of-life machinery products as the object, the “carbon footprint” in the process of recycling and remanufacturing is studied in depth, and a carbon emission evaluation model for the recycling and remanufacturing of machinery products is established. Then the improved hybrid genetic algorithm is used to solve the model, the genetic algorithm and simulated annealing algorithm are combined to overcome their shortcomings in local search and global search. The competitive mechanism and adaptive mechanism are introduced to further suppress the precocity of the algorithm and realize the efficient processing of the complex recycling and remanufacturing network system. The example results show that the model can effectively solve the problem of end-of-life machinery products carbon emission calculation in the recycling and remanufacturing system.

Machinery products Recycling and remanufacturing system Carbon emission Hybrid genetic algorithm

2016-03-14。国家自然科学基金项目(71473077)；国家高技术研究计划项目(2013AA040206)。邓乾旺，教授，主研领域：产品开发过程管理技术及应用，智能制造，制造系统虚拟仿真。徐博文，硕士生。廖浩岚，博士生。刘霞辉，硕士生。

TP3-05

A

10.3969/j.issn.1000-386x.2017.04.008