（机械制造及其自动化专业论文）基于模拟退火的粒子群优化算法在拆卸序列规划中的应用.pdf

基于模拟退火的粒子群优化算法 在拆卸序列规划中的应用 摘要 拆卸序列规划是废旧产品回收阶段的最初步骤，也是绿色再制造工程的重 要组成部分。拆卸序列规划的目的就是在最短的时间内，投入较少的人力，使 用尽可能少以及简单的工具来完成对目标产品符合预定要求的拆卸。但是拆卸 过程涉及到大量的因素，如何充分考虑这些因素，适当调整顺序，得到效率最 大化的拆卸序列是十分复杂的问题。 本文将基于模拟退火的粒子群优化算法这一混合优化算法应用于拆卸序列 规划求解问题。基于拆卸约束图理论，引入了无向边的权重以及拆卸工具信息， 提出了拆卸赋权约束图模型。分析了粒子群优化算法与模拟退火算法的优缺点， 优化了基于模拟退火的粒子群优化算法流程。重新定义了粒子的位置与速度的 更新规则以及模拟退火过程的模型扰动规则，定义了判断拆卸序列优劣的适应 度函数，提出了不可行序列的判定及其修正方法。最后以某款料理机主机体为 例，运用该算法求解其拆卸序列，并与单一粒子群优化算法相比较，验证了该 算法的可行性与有效性。 关键词：拆卸序列规划粒子群优化算法模拟退火算法拆卸赋权约束图 a p p l i c a t i o no fp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m b a s e do ns i m u l a t e da n n e a l i n g o nd i s a s s e m b l ys e q u e n c ep l a n n i n g a b s t r a c t d i s a s s e m b l ys e q u e n c ep l a n n i n gi st h ef i r s ts t e po ft h er e c y c l i n go ft h ew a s t e p r o d u c t s ，a n di sa l s ot h ei m p o r t a n tp a r to ft h er e m a n u f a c t u r i n ge n g i n e e r i n g t h e p u r p o s eo fd s p i st od i s a s s e m b l et h ea i mp r o d u c ti na c c o r d a n c ew i t ht h ed e m a n d a n dw i t h i nt h es h o r t e s tt i m e ，w o r k e r sa n dt o o l s t h e r ea r es om a n ye l e m e n t s r e l a t i v et ot h ed i s a s s e m b l yp r o c e s s ，s oi ti sac o m p l i c a t e di s s u et h a th o wt oc o n s i d e r t h ef a c t o r s ，a d j u s tt h es e q u e n c ep r o p e r l ya n dg i v e nt h eb e s td i s a s s e m b l ys e q u e n c e i tb e u s e di nd i s a s s e m b l ys e q u e n c ep l a n n i n gp r o c e s sw h i c hi sah y b r i d o p t i m i z a t i o na l g o r i t h m ，t h ep a r t i c l e s w a r m - s i m u l a t e da n n e a l i n go p t i m i z a t i o n a l g o r i t h m ( p s o s a ) t h ed i s a s s e m b l yw e i g h t e d c o n s t r a i n tg r a p h ( d w c g ) i s p r e s e n t e db a s e do nd i s a s s e m b l yc o n s t r a i n tg r a p h t h eu n d i r e c t e de d g ew e i g h ta n d t h ed i s a s s e m b l yt o o l si n f o r m a t i o na r eb r o u g h ti nt oc o m p l e t et h ed w c gt h e a d v a n t a g e sa n dd i s a d v a n t a g e so ft h ep s oa n ds a a r ea n a l y z e d ，a n df l o wo ft h e p s o - s ai so p t i m i z e d r e d e f i n et h eu p d a t er u l e so ft h ep a r t i c l e sp o s i t i o na n ds p e e d a n dt h em o d e ld i s t u r b a n c er u l e so ft h es i m u l a t e da n n e a l i n gp r o c e s s g i v i n gt h e d e f i n i t i o no fp a r t i c l ef i t n e s sf u n c t i o n ，a n da l s ot h ea l g o r i t h md e t a i l st of i tt h em o d e l t h em e t h o du s e dt oj u d g et h ed i s a s s e m b l ys e q u e n c ef e a s i b i l i t ya n df i xi ti sg i v e ni n t h i sp a p e r t h e nap a r to fak i n do fb l e n d e ri sa n a l y z e du s i n gt h ep a r t i c l e s w a r m s i m u l a t e da n n e a l i n go p t i m i z a t i o na l g o r i t h ma sa ni l l u s t r a t i o nt ov e r i f y i t s e l f ，a n da l s oc o m p a r e dw i t ht h ep a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mt os h o w i t sf e a s i b i l i t ya n de f f i c i e n c y k e yw o r d s ：d i s a s s e m b l ys e q u e n c ep l a n n i n g ；p a r t i c l e s w a r mo p t i m i z a t i o n ； si m u l a t e da n n e a l i n g ；d i s a s s e m b l yw e i g h t e dc o n s t r a i n tg r a p h 插图清单 图i - i 传统制造过程及其废弃物4 图l 一2 广义的绿色再制造过程与环境的关系5 图3 - 1 拆卸约束图的简单实例2 0 图3 - 2 运用d c g 搜寻拆卸序列流程图2 3 图3 3 目标零件6 的拆卸示意图2 4 图3 4 零件连接关系示意图2 7 图3 5 零件拆卸赋权约束图2 7 图4 - ip s o 优化算法流程图3 1 图4 - 2 基本s a 算法流程图3 4 图4 3p s o s a 优化算法求解拆卸序列流程图3 6 图5 1 某料理机外观图3 9 图5 - 2 主机体模块爆炸图4 0 图5 - 3 主机体拆卸约束赋权图4 2 表格清单 表卜l 欧盟环保规范发展概况。2 表卜2 国内世界产量第一的规模产品制造能力3 表2 - 1 零件间约束关系分类图一j 1 4 表3 - i 目标零件6 的选择性拆卸过程2 5 表3 2 三类工程属性内容及分值2 6 表3 - 3 拆卸工具转换分值表2 6 表5 - i 主机体各零件连接信息及其权重值4 2 表5 - 2 主机体各零件拆卸工具对照表4 3 表5 3 两种算法运行结果比较4 3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 佥目墨些太堂 或其他教育机构的学位或 证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均己在论文中作了 明确的说明并表示谢意。 学位论文作者签名：匆铬争 签字日期m 口年归 学位论文版权使用授权书 本学位论文作者完全了解金8 巴些厶堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金a 巴王些态堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：嘭络箩 签字日期：洳胗年尹月) 口日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字口期圆。r d 年彳月2 艏 电话： 邮编： 致谢 本论文是在导师刘志峰教授的悉心指导下完成的，从入学以来研究方向的 确定到论文的撰写、修改、定稿整个过程都凝聚了导师大量的心血。导师个人 渊博的知识、开拓的视野、以及在学术上严谨的态度、科研上无私奉献的精神 和工作上勤奋务实的作风一直是我学习的榜样。导师的谆谆教导和生活上对我 的关心与帮助我将永远铭记，在此谨向导师致以崇高的敬意与诚挚的感谢! 衷心地感谢绿色设计与制造研究所的刘光复教授、宋守许副教授、朱家诚 教授、王玉琳副教授以及黄海鸿副教授，几年来各位老师在学习与生活上给了 我很大的帮助；特别感谢张雷老师，张老师在我就读硕士期间给予了莫大的帮 助，无论是学习上、工作上还是生活上，每处细节都为我考虑，让我全身心的 投入到学习与科研，同时对本文的选题及撰写进行了深入细致的指导，在此表 示衷心的谢意。 感谢高洋、胡迪、柯庆镝、鲍宏等博士，孙博、杨明、郭卫、顾国刚、湛 阳、张磊、施英莹、蒋云、刘琳、凌波等硕士在生活和学业上给予我的支持与 帮助，感谢他们在本人科研和完成本文的过程中所提供的帮助和宝贵意见。 感谢已毕业的莫兴波、李冰冰、张福龙、陈清、陈志军、仲榕南等硕士在 生活和学习上给予我的支持和帮助。 感谢父母对我的养育之恩，感谢我的爷爷、奶奶和姥姥多年来对我学习、 生活上的关怀与呵护，感谢我的家人一直以来对我默默的付出与全力的支持， 没有他们所做的一切，我不就可能顺利完成学业。我将用毕生的努力来回报所 有关爱我的亲人。 最后，向所有给予我关心和帮助的老师、同学和亲友致以深深的谢意和美 好的祝福。 杨德军 2 0 1 0 年4 月 第一章绪论 1 1课题研究背景及意义 1 1 1 研究背景 2 0 世纪世界经济飞速发展，社会各领域新思想、新理论、新技术层出不穷。 经济的空前繁荣，政治的相对稳定，使人类文明步入了一个新的时代，这是人 类社会以往各个历史时期都望尘莫及的，也是无法比拟的。但这种以高投入、 高消耗为代价的高速增长给地球生态环境造成了巨大的破坏，这种破坏甚至是 无法挽回的。环境、资源、人口三大问题也就随之而来，目前全球均深受其困 扰，这三大问题是当今社会面临的主要问题【1 1 。 随着产品更新换代的速度越来越快，尤其以电子类消费产品居首，全球每 年淘汰数以亿计的电脑、手机等数码产品以及电视、冰箱等家电产品。随着汽 车逐渐进入家用领域，私家汽车的保有量也呈逐年上升趋势。每年报废的汽车 数量也相当可观。由于制造以及回收工艺等问题，或者很多产品是直接当作垃 圾扔掉而不会被回收，所以这些产品废弃后很多有毒有害物质进入了生态系统， 对环境造成了严重的污染。调查表明，制造业中机电产品是最大的环境污染源。 随着资源的日益匮乏，以及不能进行合理回收的废弃产品数量的不断增长，人 类社会面临的压力越来越大。为了有效缓解资源短缺与资源浪费的矛盾，减少 大量的废旧产品对环境的危害，将废旧产品再资源化，重新加以利用，绿色再 制造工程逐步形成，并成为发展最快的一种新的研究领域和新兴产业。 传统模式的制造业一味追求经济效益，而忽略了环境的平衡发展以及自然 资源的可持续利用，是目前地球居住环境日益恶化的罪魁祸首。国际社会已普 遍关注这一问题，并积极寻求解决方法。世界各国都在制定自己的发展战略， 相应环保法令法规也相继出台。如表1 1 【2 】所示，影响力最大的是欧盟颁布的多 条法规，分别从产品的回收、材料的使用、化工产品的监控以及能源的消耗几 方面着手，较全面的实现了环境的保护、资源利用的最大化并保障了消费者的 人身安全。继欧盟之后，美国、日本等也纷纷颁布相应的环保法规，建立了绿 色环保的制造规范。我国也于2 0 0 6 年2 月2 8 日颁布了电子信息产品污染控 制管理办法1 3 j ，对进口的电子信息产品进行了有毒有害物质( p b 、c d h g 、c r 6 + 、 p b b s 、p b d e s ) 的管控。各环保法规的相继颁布，必然会引导传统的制造业向 生态、环保的方向转变，建立绿色采购体系，推行清洁生产，降低能耗。虽然 短期内会增加生产成本，但是从长远角度考虑，这是制造业转变的必由之路。 自改革开放以来，我国逐步发展成为世界制造大国，据不完全统计，有1 0 0 多 种制造业产品形成了大批量生产能力，其中一些更是居于国际首位，如表1 2 1 4 j 所示。欧盟与美国等制定的环保法规构筑了“绿色贸易壁垒”，这对于我国绝大 多数依靠出口的企业是一次挑战，同时也是极佳的机遇。必须积极应对，调整 生产模式，由高能耗、低产出的传统制造业向生态环保的新型制造业转变，是 应对当前形势的唯一途径。 表1 - 1 欧盟环保规范发展概况心1 指令规范名称 主要管控内容管控时间 包装及包装废弃物指令 管控包装材料危害物质( c d 、p b 、h g 、c r 6 + ) 2 0 0 1 0 7 0 l (9 4 6 2 e c、 含量总和不得超过1 0 0 0 p p m 。 废弃物回收能源回收率 6 0 ； 2 0 0 4 12 e c、 再使用率5 5 8 5 ； 2 0 0 8 1 2 - 3l 2 0 0 6 34 0 e c ) 各材料回收目标1 6 6 0 电子电气设备禁限用危 管控电子电气设备( 钨丝灯泡、家用灯具与医疗 害物质指令( r o l l s ， 设备及监控设备除外) 危害物质含量。 p b 、h g 、c r “、p b b s 、p b d e s 1 0 0 0 p p m ； 2 0 0 6 0 7 0l 2 0 0 2 9 5 e c ) c d l0 0 p p m 。 应建立废弃电子电气设备回收体系 2 0 0 5 0 8 1 3 废弃电子电气设备回收处理目标： 废弃电子电气设备指令 平均回收量达到4 k g 人年； 2 0 0 6 1 2 31 ( w e e e ，2 0 0 2 9 6 e c ) 各类别产品回收率5 0 7 5 ： 再生利用率7 0 8 0 。 电子电气产品回收处理信息披露。上市1 年内 能耗产品生态化设计指 应评估产品生命周期各阶段的环境冲击，改进环 境绩效，并编制生态说明书( e c o l o g i c a lp r o f i l e ) 。 2 0 0 7 0 8 1 l 令( e u p ，2 0 0 5 3 2 e c ) 产品结合c e 标志的市场机制。 关于限制全氟辛烷磺酸 规定各欧盟成员国须于2 0 0 7 年1 2 月2 7 日依据 销售及使用的指令 指令实施有关法例，主要影响：地毯、皮革、纺 织品、服装、纸张、包装品、灭火器等禁用全氟 2 0 0 8 0 6 2 7 ( p f o s ，2 0 0 6 1 2 2 e c ) 辛烷磺酸盐( p e r f l u o r o o c t a n es u l f o n a t e s ，p f o s ) 。 如果填充油含有p a h s 超过以下标准，不得投入 多环芳香烃浓度限制指市场或用来生产轮胎与相关物件： 2 0 1 0 0 1 0 1 令( p a h s ，2 0 0 6 6 9 e c ) b a p 不得超过1 m g k g ； 所列出只p a h s 总含量不得超过1 0 m g k g 。 化学品注册、评估、授 r e a c h ( r e g i s t r a t i o n ，e v a l u a t i o na n d 权和限制指令 a u t h o r i z a t i o no f c h e m i c a l s ) ，是一个化学品注册、 评估及授权机制，在法规系统中，欧盟生产或进 2 0 0 7 0 6 - 01 ( r e a c h ， e c n 0 1 9 0 7 2 0 0 6 ) 口化学物质1 吨年以上的企业都将收到法规的 管控，并须进行物质登记或注册。 2 传统的生产方式早已不适应当前经济的发展与环境的要求，生产厂商也意 识到了这一问题，纷纷寻求突破，取得了一些成效。绿色再制造通过对废弃产 品的重新评估，制定零件替换、零件再制造或材料回收等相应生产计划，不仅 降低了重新生产的成本，同时也大大减少了环境的污染以及资源的过度消耗， 是一种行之有效的方法。如何有效地利用资源和最大限度地减少废弃物，已成 为解决环境和资源问题的根本方法。随着人们环境意识的觉醒，绿色再制造工 程应运而生并迅速发展，它是解决资源浪费、环境污染和废旧设备翻新改造的 最佳方法和有效途径，是符合国家可持续发展战略的一项绿色系统工程。 表1 - 2 国内世界产量第一的规模产品制造能力n 1 产品名称 生产规模百分比产品名称生产规模百分比 彩色电视机3 9 3 6 万台 2 9 摩托车 l1 5 3 万辆4 4 洗衣机1 4 4 3 万台2 4 拖拉机2 1 0 万台8 3 电冰箱1 2 7 9 万台1 6 电话机9 5 9 8 万台大于5 0 空调 18 2 7 万台3 0 显示器4 5 0 0 万台 4 2 电风扇7 6 6 l 万台5 0 以上钟表 1 5 亿只 7 5 照相机5 5 1 4 万台5 0 以上微特电机3 0 亿台 6 0 微波炉1 2 5 7 万台3 0 一次性电池 1 7 0 亿只4 0 电饭锅13 5 5 万台 数字程控交换机3 0 0 0 万线 吸尘器1 0 10 万台 抽油烟机3 6 6 万台 自行车4 2 7 0 万辆9 9 年4 0 人造金刚石 1 0 亿克拉 6 0 以上 太阳能热水器6 0 0 万平方米 集装箱 1 5 3 万t e u8 3 在产品报废时，经过以优质、高效、节能、环保为目标的绿色再制造，不 仅能够恢复产品原有功能特性，而且能够及时通过引进新技术、新工艺和新材 料，改进并提高产品的技术性能和可靠性，实现性能升级。 绿色再制造工程可以大量恢复报废设备及部件的性能，延长使用寿命，降 低产品的全生命周期费用，节约原材料，减少环境污染，促进新产业的形成， 培养大批专业技术人员并增加就业率，形成新的经济增长点。我国的一些企业 已瞄准了电冰箱、空调、汽车等的绿色再制造。现阶段我国投入装备研制、生 产、购置的费用不可能太多，但很多的装备已经废旧，处于更新换代的阶段。 如何科学的对现有设备进行改造，使之适应现阶段的需要以及作为未来的储备， 以最低的资金，达到最优的效果，这些都需要绿色再制造工程的支持。 绿色再制造工程运用了多种高新技术，采用了产业化的生产方式、严格的 产品质量管理和市场管理模式，最大限度的再生和利用废旧产品。绿色再制造 技术是对先进制造技术的完善和补充。废旧产品的绿色再制造是其产品全生命 周期管理的延伸和创新，可以对废旧产品中可利用的价值充分加以利用，减少 了资源的消耗，延长了产品的使用寿命。简单的说，绿色再制造是产品废弃后 对其重新加工，使其成为可再次使用产品的过程，包括加工处理后的原材料与 对既有零件的再制造，使其达到性能要求。绿色再制造的目的就是尽可能多的 进行零件再制造，将材料回收降低到最小程度。广义的绿色再制造包括产品设 计、制造并投入使用后，为其保持、恢复可用状态或加以重新利用，所采取的 一系列技术措施或工程活动，主要包括如下几个方面【5 】： ( 1 ) 修复：通过测试、拆修、换件、局部加工等，恢复产品的规定状态 或完成规定功能的能力。 ( 2 ) 改装：通过局部修改产品设计或连接、局部制造等，令产品使用技 术性能得到提高，适应使用或技术发展的需要，延长使用寿命。 ( 3 ) 改进或改型：通过局部修改和制造，特别是引进新技术等，使产品 使用与技术性能得到提高，适应使用或技术发展的需要，延长使用寿命。 ( 4 ) 回收利用：通过对废旧产品进行测试、分类、拆卸、加工等，使产 品或其零部件、原材料得到再利用。 废岩堆 回 收 的 材 料 图1 - 1 传统制造过程及其废弃物旧1 不 鹭 收 嫠 弃 缝 置 点 绿色再制造的优势可以通过与传统制造业各过程的环境排放对比图得出。 图1 1 f 6 】是传统制造业的制造过程及其废弃物，图1 2 展示了广义的绿色再制造 过程与环境的关系。绿色再制造所使用的原材料是环保无毒害的；制造过程也 4 不会产生对环境和人体有害的废物；产品使用过程中，在满足性能要求的同时， 消耗能源最少，对环境的污染降到最低程度；产品废弃回收过程，最大限度的 将零件以及材料重用，减少了对资源的过度消耗。与传统制造过程相比，对于 保护生态环境，坚持可持续发展战略，建设和谐社会有重要意义。 材 料 的 同 收 对生产及同收 过程产生的有 毒有害物质进 行无害化处理 图卜2 广义的绿色再制造过程与环境的关系 绿色再制造是目前学术界以及企业积极努力的目标，但是限于现阶段的科 学技术水平，很多研究只是停留在理论阶段，进入实际操作阶段尚需新理论、 新技术、新材料等的支持。拆卸序列规划是绿色再制造重要的组成部分，也是 目前广泛研究且较为深入，并具有很强的可操作性的课题之一。产品废弃后的 维修以及回收过程是从产品的拆卸开始的，而长期的实践经验表明，产品的拆 卸阶段往往耗费了大量的人力、物力与时间。因此合理高效的拆卸序列，可以 有效的提高生产效率，节约资源。进行拆卸理论研究显得尤为重要，不仅可以 促进绿色再制造理论的发展，而且可以最直接的实现企业的经济效益。 新事物的诞生以及发展会遇到很多的障碍和问题，绿色再制造工程的研究 与推广同样面临着来自各方的阻力。主要面临的问题和须做好的工作有以下几 点【5 j ： 1 研究再制造关键技术，保障再制造产品质量。再制造这一新兴产业的发 展离不开相关理论技术的支持，组建绿色再制造技术研究中心并加大关键技术 的研发投入与核心难题的攻关力度，及时将研究成果转化为经济效益，形成良 性循环，以利于产业的健康发展。对于再制造企业的回收与再制造流程进行严 格监督，确保再制造产品的质量符合相关标准，使再制造产品性能不差于，甚 至优于原产品，消除消费者心中对于再制造产品的种种顾虑，树立再制造企业 以及再制造产品良好的正面形象。 2 建立专业化再制造企业。针对我国再制造产业发展现状，在初期阶段， 应由国家相关部门利用现有优势资源，引导并建立一批骨干再制造企业，形成 产业规模，提高竞争力，逐步形成再制造社会化生产体系，发挥其带头作用， 引导再制造产业良性发展。同时，具有一定规模的大型制造企业，应加大自身 产品再制造的投入，通过再制造使一部分产品达到新品的性能，另一部分产品 则改造为其他产品，提高再制造产品的市场份额，同时不断为用户提供完善的 维修服务，并在设计新品时就考虑到再制造问题。 3 制定与再制造相关的政策、法律、法规。政府相关部门需针对技术标准、 加工工艺、产品类别、废旧产品回收、再制造产品销售和售后服务等再制造过 程的各个方面，尽快制定并出台可以促进再制造工程健康发展的政策、法律和 法规。对一些报废量大的产品，如家电产品、电子产品、汽车等，通过立法延 伸其制造者的责任，由企业出资建立回收网络，并对回收产品进行再制造，尤 其是可能对环境产生严重污染的产品，从而避免对环境的破坏。企业经过再制 造的产品进入市场，在保证其质量与性能的同时，必须做明确标记，与新产品 严格区分，确保消费者的知情权。 4 唤起公众的再制造意识。再制造业发展进度快慢以及成功与否，广大消 费者对其认知的程度是不可忽视的一个要因素。因此，政府、企业及有关部门 需要加大宣传力度，积极引导，再制造过程透明化，让消费者了解再制造的流 程，明确再制造产品不等同于劣质产品，且质量性能完全不亚于新产品。 1 1 2 课题提出 拆卸序列规划属于n p 完全问题，若不加入一些限制因素，随着产品零件 数目的增加，拆卸序列的数目将呈爆炸式的增长，即使加入了相关的约束，包 括成本、时间以及零件间干涉等，可行的拆卸序列还是会非常之多。如果不经 过任何计划，直接进行盲目拆卸，将会有更多的人力与时间浪费在拆卸过程中， 更有可能导致拆卸最终无法完成。因此，国内外很多学者均投入了大量时间对 其进行研究，旨在寻求一个最佳的拆卸序列。 拆卸序列规划的目的，即在最短的时间内，投入较少的人力，使用尽可能 少以及简单的工具，搜寻目标产品合理的拆卸顺序，以满足既定要求。目前求 解拆卸序列规划问题，运用较多的思路为：首先将产品的结构以及拆卸信息用 图模型进行表达，然后通过一些约束条件，生成一组可行解，最后利用优化算 法对其进行优化，得到最终结果。人类社会的很多创意与灵感都来自于自然界， 受到启发，很多优秀的算法也应运而生。比如蚁群算法( a n tc o l o n y 6 o p t i m i z a t i o n ，a c o ) 【7 j 、遗传算法( g e n e t i ca l g o r i t h m ，g a ) 【8 j 、粒子群优 化算法( p a r t i c a ls w a r mo p t i m i z a t i o n ，p s o ) 【9 】等。这些算法的提出使我们 对复杂问题的求解有了新的思路及方法，但是也有一些不足的地方，因此研究 人员也不断对这些算法进行改进与优化。本文研究的问题就是将粒子群优化算 法与模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 【l o 】相结合，运用于拆卸序列规 划求解中。基本流程是：利用零件间的结构关系、拆卸工具等因素，首先删除 某些不可行的拆卸序列，运用拆卸时间、成本等优选条件初步得出备选解空间， 再通过人工智能算法求出最佳拆卸序列。 1 2国内外相关领域研究现状 产品的绿色再制造是传统制造模式自身转变，适应时代发展要求的必经之 路，可以有效缓解目前给环境带来的压力。装配拆卸序列规划是绿色再制造过 程的重要组成部分，国外较早就开始了相关研究。拆卸过程可以看作是装配过 程的逆过程，后者是随着零件数目的增加而不断增加约束，前者相反，每拆卸 一个零件就解除一个或几个约束。装配序列规划的研究可以为拆卸序列提供参 考的基础，而研究拆卸序列规划又可以反过来指导产品设计，优化装配序列。 因此，两者具有很强的关联性。 装配拆卸序列规划早期的研究主要围绕图论技术展开，同时近年在计算机 仿真模拟方面也有了飞速的发展。b o u r j a u l t 】尝试用装配顺序的优先关系来描 述装配体中各零件间的装配顺序几何干涉关系，并提出了产品装配结构的联系 图模型表达方法，并以该图为输入信息，结合分析处理与人机交互，搜索出所 有可行几何装配顺序。l a m b e r t 1 2 】提出了一种拆卸图方法，通过一种有向网络 图来描述产品的拆卸结构，图中节点表示可拆的子装配体，并遵循自左至右的 顺序拆卸，不过由于建模难度较大，须集成计算机辅助设计工具。该方法与 a n d o r 图类似，通过线性规划方法搜寻目标产品的最大收益指标，进而确定 最佳的拆卸序列。s r i n i v a s a n 和g a d h 1 3 1 4 】提出了层次化图和虚拟拆卸度量，同 时也提出了基于去除影响关系图和可达关系图的波传播方法，并应用于选择性 拆卸序列的优化求解。基于去除影响关系图是有向图，以定点表示零件，弧表 示拆卸约束关系。可达关系图同样也是有向图，定点表示零件这一点与前者相 同，不同的是这里的弧表示的是零件间的邻接关系。拆卸序列的搜索过程为， 从指定拆卸零件和边界零件分别向另一方产生一个传播，当两个波在途中相遇 时，拆卸序列搜索完成。m o o r e 1 5j 利用p e t r i 网对复杂产品的拆卸序列规划进行 了研究。g u n g o r 和g u p t a 1 6 】等提出了一种生成拆卸优先矩阵和拆卸序列的方法 来解决有限零件的完全拆卸问题。w o o 和d u t t a r 7 】通过一种结构化的拆卸树寻 找选择性拆卸序列，不过该方法有一定的局限性，仅适用于零件间无依赖拆卸 的情况。无依赖拆卸是指仅拆除目标零件，而无需考虑与之有接触关系的零部 7 件，这种情况是非常极端的，不具有实际意义。j o h n s o n 1 8 】对产品拆卸树进行了 相关研究，为了减化拆卸过程而提出了材料相容、易归类、并行拆卸操作等技 术，评估和优化了产品回收的拆卸工艺，并开发了拆卸成本评估和拆卸序列优 化软件。t a l e b l l 吼2 0 】提出了一种对复杂产品进行拆卸序列规划的算法，并对其 进行了改进。z a h e d 2 l 】等将虚拟原型的方法应用于产品的拆卸序列分析中，可 以在没有实际产品的情况下进行拆卸序列规划。o n o s a t o 、1 w a t a 2 2j 等为了评估 装配拆卸的难易性，提出了基于运动学的仿真系统的评估方法，通过产品三维 仿真图形计算零件的可能运动，从而得出零件从产品中拆下的可能性。 f e l d m a n 2 3 提出了基于知识的拆卸规则。s i d d i q u e ( 2 4 】从拆卸能量及拆卸熵角度对 拆卸难度进行了定量评估。v u j o s e v i e t 2 5 】提出了产品维护过程分析的仿真方法， 对可行拆卸序列进行优化，实现最少拆卸时间、拆卸成本以及劳动力的消耗。 r a j i t 2 6 等开发了虚拟拆卸软件用于产品的拆卸及维护，对产品原型进行拆卸分 析并评估其复杂性及拆卸费用。z h a n g 2 7 】等利用无向图模型描述产品结构，并 建立拆卸模型，最终将拆卸回收问题转化为图论搜索问题。z u s s m a n 【2 8 】赋予每 个零件不同的优先权，优先权高的零件优先拆卸。江吉彬f 2 9 】等提出了一种基于 层次网络图的拆卸序列生成方法，通过将复杂的网络图分解成单元网络图，避 免因节点数过多而引起的组合爆炸问题。高建刚 3 0 】等定义了机电产品拆卸与或 图拆卸回收模型，提出了计算产品所有可能的分解方案及所有可能的拆卸序列 的算法。刘继红p i j 等也在虚拟环境下对人工装配拆卸进行了研究。 但是基于图论的求解过程，随着产品零部件的增多，都不可避免的会遇到 爆炸组合问题，使问题的求解变得异常复杂。随着人工智能算法的不断发展， 越来越多的研究学者将人工智能算法应用到拆卸序列规划求解中，以解决这一 问题。应用较广泛的人工智能算法主要有蚁群算法、遗传算法、粒子群算法以 及模拟退火算法。 h o n g b os h a n 3 2 】等基于组件数量、拆卸工具以及拆卸方向的考虑建立了拆 卸优化模型，然后运用蚁群算法得到了有效的产品拆卸序列。k o n g a r 3 3 j 等采用 遗传算法对拆卸序列进行规划，得到了最佳的拆卸序列。王辉【3 4 5 】等构建了产 品拆卸可行性信息图，并分别用蚁群算法以及遗传算法进行了最优拆卸序列的 搜寻。张秀芬【36 j 等将赋权混合图模型映射到粒子群模型，应用粒子群算法实现 了复杂产品的最优拆卸序列规划。h o n g 3 7 】等将模拟退火算法引入机器人装配序 列规划，通过装配序列能量函数来表示成本，经过多次迭代最后得到成本最小 的装配序列。 由以上文献可以看出，国外对拆卸回收的研究起步较早，涉及范围较为广 泛，研究内容相对深入。而国内由于研究起步较晚，加之受各方面条件制约， 所以理论以及实践水平与国外相比还有一些差距。目前，国内外对拆卸回收的 研究还是较多的停留在理论探索阶段，研究工作的重点主要是倾向于拆卸序列、 拆卸路径的规划及评价工具的开发，对于虚拟产品拆卸模型也进行了有益的探 索，但是缺乏突破性的进展，距离实际应用还有很大距离，这将是下一步研究 的重点。现阶段，针对拆卸序列规划的研究虽然很多，但也存在不少问题，还 无法实现自动化程度较高的机器拆卸，遇到零件数目较多的复杂产品，通常效 果不是很理想。 粒子群算法来源于对一个简化社会模型的模拟，通过追随当前搜索到的最 优值来寻找全局最优，与遗传算法和蚁群算法相比，简单易实现且没有许多参 数需要调整。可是单一p s o 算法易陷入局部极值，导致无法得到最优结果，为 了弥补这一缺陷，本文将模拟退火算法与粒子群算法相结合，运用基于模拟退 火的粒子群算法求解拆卸序列问题。该方法在保留p s o 快速简单的全局寻优特 点下，利用s a 跳出局部最优的能力，实现了全局最优解的搜寻。 1 3论文研究内容及章节安排 满足产品的功能需求一直是传统设计的目标，从而导致企业忽略了产品的 可拆卸性与可回收性等其他绿色属性。传统制造方式给人类以及环境带来的危 害已经引起了社会广泛的关注。废弃产品的拆卸与回收重用，可以降低资源的 消耗，减少对环境的污染。拆卸阶段是回收废弃产品，对其进行零件重用、材 料回收等后续工作的基础，也是非常重要的步骤。因此，有必要对其进行深入 研究，以节省时间、人力、物力等各种资源。同时，拆卸序列规划的研究也可 以反过来反馈到产品设计阶段，设计人员通过参考研究结果，在设计的过程中 针对装配以及拆卸过程加以改进，使其更加人性化、方便快捷、省时省力。 在此基础上，本文主要讨论了拆卸阶段产品的拆卸序列规划问题。首先基 于拆卸赋权约束图，通过人机交互构建了产品结构表达模型，然后将拆卸过程 相关信息赋予拆卸约束图的节点与边，定义了判断拆卸序列优劣的适应度函数， 将算法与模型进行了映射。通过分析拆卸赋权约束图，利用适应度函数的筛选， 得到初始种群，判断是否满足最优，若不满足则运用粒子群优化算法进行迭代 操作得到退火算法的初始种群，最后由模拟退火算法进行退火降温操作得到下 次迭代的初始种群，循环求解直至粒子的适应值达到预定目标或完成预定的 迭代次数为止。 本文的组织结构如下： 第一章系统阐述了课题研究的背景、意义，分析了国内外学者在拆卸序 列规划方面的研究现状。 第二章对拆卸序列规划相关问题进行了表述，包括拆卸的定义与分类以 及与拆卸序列有关的一些技术要点。 第三章在详细分析了拆卸约束图的基础上，引入无向边的权重以及拆卸 工具信息，将其扩展为五元组的拆卸赋权约束图，并说明了其应用方法。 9 第四章从基本原理到算法流程对粒子群优化算法及模拟退火算法进行了 阐述，分析了各自的优缺点，并将两种算法的思想结合起来，提出基于模拟退 火的粒子群优化算法，最后给出了在拆卸序列中的应用。 第五章以某款料理机主机体组件为例，验证了本文提出的算法，并与单 一的粒子群算法进行了比较，取得了较满意的结果。 第六章总结全文，指出下一步的工作方向。 1 0 第二章拆卸序列规划问题 2 1 引言 拆卸序列规划是研究如果调整产品拆卸过程中的各步骤先后顺序以及合 理分配各种资源，使之达到效益最大化，即在最短的时间内，利用最少的人力 资源，使用尽可能少以及简单的工具，通过合理的工序来完成对目标产品符合 预定要求的拆卸。这一系列过程涉及到拆卸过程中大量的信息，因此有必要对 拆卸问题以及拆卸过程中相关的信息进行研究归类。 2 2 拆卸的定义与分类 2 2 1 拆卸的定义及目的 拆卸是通过人工手动或机器自动化的方式，采用一定的工具和方法，解除 零件间的相互约束，将产品零部件顺序分离的过程。拆卸的目的及应用领域为： 零部件的重用和再制造、产品维修、材料回收。 拆卸的目的有三个： 产品零部件的重复利用。重复利用包括直接重复利用和间接重复利用两 种方式。一般对于制造成本高，革新周期长或使用寿命长的零部件，可以考虑 采用直接重复利用的方式，如啤酒瓶等，可直接用于盛其它液体；间接重复利 用即再制造后重用，主要是针对产品中的有些零部件，由于回收后无法直接用 于同类型产品，此时可对其进行再加工，用于其他类型或规格的产品，如汽车 零部件经过再加工后用于拖拉机的相关部位、淘汰计算机主板可用于游戏机等。 元器件回收。这主要是针对电子产品，由于其组成材料多种多样，更新 换代周期短，因此，往往需要采用特殊工艺方法回收其中的某些特殊元器件。 材料的回收。当产品的材料成本高，单个零件的生产成本低，且生产规 模大，产品生命周期短，此时往往用简单的材料回收方式。拆卸可以在产品层 次上进行，也可以在部件层次上进行。 拆卸是产品废弃后回收处理阶段的第一道工序，其过程可分为两步，一是 解除待拆零件( 或组件) 与装配体间的约束，二是将其沿无空间约束的方向取 出。实现以上两部分工作必须了解目标零件在整个装配体中的连接关系、以及 目标零件在拆卸方向上是否有空间约束等。即需要零部件在装配体中的位置关 系信息，以及与拆卸难易程度及经济性相关的信息，如拆卸工具、拆卸时间等。 零件间的约束包括可拆卸与不可拆卸，其中可拆卸约束主要包括螺纹、扣、轻 压入、间隙连接等，不可拆卸约束主要包括铆接、焊接、注塑等。针对不同的 约束类型，需要不同的工具进行拆卸，所需时间也不尽相同，拆卸过程的相关 信息对最终拆卸序列的优化结果以及后续分析都相当重要。 2 2 2 拆卸的分类 通常按照拆卸零件的方法以及产品拆卸的程度两种方法进行分类p 引。 1 按照拆卸零件的方法，可将拆卸分为： 1 - m 维可拆。根据拆卸时零件所需线性移动的方向次数，可以分为l 维 可拆和m 维可拆。前者指拆卸某零件时仅需1 次线性移动即可，后者 指拆卸某零件时需m 次连续的线性移动。 直接或间接拆卸。根据拆卸目标零件时是否需要先拆去其他零件，可分 为直接拆卸和间接拆卸。若拆卸目标零件时，必须移走其他零件，称 之为间接拆卸，否则称为直接拆卸。 顺序或并行拆卸。根据同时拆卸零件数目的多少，分为顺序拆卸和并行 拆卸。顺序拆卸指每次只能拆下一个零件，并行拆卸允许同时拆下几 个零件。如果零件a 对零件b 有空间约束，只能先拆零件a 再拆零件 b ，这种拆卸称为顺序拆卸。若零件a 和零件b 作为单个零件可同时 拆下，这种拆卸称为并行拆卸。 单纯或非单纯拆卸。根据拆卸目标零件时对其他零件的操作情况，可分 为单纯拆卸和非单纯拆卸。若拆卸目标零件时需改变其他零件的位置， 这种操作即为非单纯拆卸，否则为单纯拆卸。 破坏或非破坏拆卸。根据拆卸时是否要对目标零件进行破坏式的拆解， 可分为破坏拆卸和非破坏拆卸。拆卸过程中，所有零件均不被破坏叫 做非破坏拆卸。若有一个或多个零件被破坏则称为破坏拆卸。非破坏 拆卸后，零部件大多可以重用或再制造后重用，破坏拆卸后只能做材 料回收或废弃处理。 2 根据产品拆卸的程度，可将拆卸分为完全拆卸、部分拆卸、目标零部件 拆卸等几种方式： 完全拆卸。指将一个产品完全拆卸至单个零件。这种拆卸方式主要应用 于理论研究，实际中应用很少。 部分拆卸。指将一个产品中的部分零部件进行拆卸。一般进行部分拆卸 主要是出于经济因素的考虑，当拆卸进行到某一阶段时，剩余的零件 已没有利用价值或价值低于对其进行拆卸的费用，此时拆卸工作就不 再进行下去；或者剩余零件由同种材料构成，不满足进行再制造的要 求，可以统一进行材料回收。 目标零部件拆卸。指对产品中指定的零部件进行拆卸的方式。进行目标 零部件拆卸的原因主要是出于维修、重用或保护环境等因素的考虑。 例如，在产品使用阶段，产品中的某个零件失效而需要将其拆下进行 维修；或当产品寿命终结而被废弃时，其中的某个零部件具有较大的 价值并仍然可以重用或可以修整翻新；或者废弃产品中的某个零部件 1 2 对环境具有较大的破坏性，此时应考虑将这样的零部件作为目标零部 件进行拆卸，这种拆卸方式在实际中应用也很广泛。 2 3 拆卸过程相关信息及拆卸设计原则 2 3 1 产品的拆卸信息 产品在拆卸过程中所需要的相关信息主要是产品设计信息、零件基本信 息、装配信息、拆卸过程信息等【3 9 1 。 1 产品设计信息。产品设计初期，随着产品功能的确定，产品相关的设计 信息便可大致确定，包括设计寿命、材料种类、结构、尺寸、体积、重量以及 注意事项等，这些信息描述了产品的初步轮廓，决定了零部件的工程性能和理 化特性。其中，尺寸和体积信息在拆卸路径规划时可以用来确定零部件移动的 步长和终点；根据设计寿命和产品使用的时间，可以知道产品中主要零部件的 工作状态以及日常保养情况。 2 零件基本信息。零件的基本信息包括零件的类型、几何尺寸、形状、重 量和材料等信息。进行产品拆卸序列规划时，主要关注零件的类型与