Pareto Hybrid Ant Colony and Genetic Algorithm for Multi-Objective U-Shaped Disassembly Line Balancing Problem
-
摘要: 针对传统方法求解多目标U型拆卸线平衡问题的不足，提出了一种基于Pareto解集的多目标蚁群遗传算法.在构造初始解阶段，以协同考虑最大作业时间、最小拆卸成本差作为蚂蚁的启发式信息；通过蚁群算法搜索可行拆卸序列，并根据多目标之间的支配关系得到Pareto解集；将蚁群算法的Pareto非劣解作为遗传操作的个体，进而将遗传操作的结果正反馈于最优拆卸路径上信息素的积累，并采用拥挤距离作为蚂蚁全局信息素更新策略，可以平衡多目标对信息素的影响，使算法快速获得较优解.将所提算法应用于52项拆卸任务算例和某打印机拆卸线实例，在算例验证中，通过对比Pareto蚁群算法，所提算法求得的8个非劣解在3个评价指标上性能分别提高了50.43%、3.25%、14.10%，在实例应用中所提算法求得8种可选平衡方案，从而验证了所提算法的有效性、优越性和实用性.Abstract: Owing to the incapability of traditional methods in solving multi-objective U-shaped disassembly line balancing problem (UDLBP), a multi-objective ant colony genetic algorithm based on Pareto set is proposed to solve the UDLBP. In constructing the initial solution phase, the maximum operation time and the minimum disassembly cost difference were collaboratively considered as the heuristic information of the ants. The feasible disassembly sequence was searched using the ant colony algorithm, and the Pareto solution set was obtained based on the dominance relationship among the multiple objectives. Further, the Pareto non-inferior solutions of the ant colony algorithm were used as the chromosomes of the genetic operator. Moreover, the results of the genetic operator were fed back to the accumulation of pheromone on the optimal disassembly sequence. The crowding distance was regarded as the global pheromone update strategy to balance the effect of multi-objective function regarding the pheromone and thereby make the algorithm obtain better solutions readily. The proposed algorithm was applied to 52 disassembly task examples and a printer disassembly line instance. Compared with the Pareto ant colony algorithm, the performances of the three evaluation indicators of the 8 non-inferior solutions obtained using the proposed algorithm are improved by 50.43%, 3.25%, and 14.10%, respectively. In the example application, the proposed algorithm obtained eight balancing schemes, which verifies the effectiveness, superiority, and practicability of the proposed algorithm.
-
图 5 ACGA非劣解在f2、f3、f4上空间分布
注：●表示方案
Figure 5. Non-inferior solutions spatial distribution of f2, f3, f4
编号 Fidle Fsmooth Fcost 1 0.057 9 0.859 4 150.546 2 0.057 9 0.928 5 159.768 3 0.057 9 0.863 2 152.412 4 0.175 7 0.968 1 170.357 5 0.175 7 0.974 7 173.388 6 0.175 7 0.945 1 167.416 
下载: 导出CSV
表 2 所提Pareto ACGA求解平衡方案
Table 2. Balance schemes of proposed Pareto ACGA
编号 任务分配方案 Fidle Fsmooth Fcost 1 {-39, -5, -30, -20, -43}→{-9, -6, -26}→{-33, 36, 37, 21, 29, 18}→{32, -2, -52, -42, -19, -27, 28, 47, -17, 15}→{3, 1, 12, -10, 35}→24, 16, 14, -45, 4, 31, 25, 11, -41, 23}→{-44, 34, 46, 22, 49, 51, -48, -50, -38, 8, 7, 40, 13} 0.057 9 0.982 3 142.224 2 {4, 31, 25, -5}→{-26, -30, -9}→{-33, -20, 36, 21, 29}→{3, 1, 12, -6}→{-18, -43, -42, 47, 46, 34, 22, 35, 24}→{7, 37, 28, 32, -19, -27, -10, -41, -2, 49}→{51, 44, 8, 15, 40, 14, 52, -17, -39, -38, -23, -45, -16, 50, 48, 11, 13} 0.057 9 0.915 3 130.332 3 {-19, -27, -44, 37, 42, 21, 4, 31}→{25, 18, 29, -5}→{-9, -33, -26}→{-30, -6, -20, 36, 52, 45}→{3, 1, 12, 2, -16, -39, 35}→{24, 34, 22, -10, 49, 51, -48, -17, 28}→{-43, 47, 32, -13, -38, -23, 40, 8, 15, -11, -14, -7, -41, -50, -46} 0.057 9 0.923 4 135.648 4 {-9, -33, -26, 37}→{4, 31, 25, -5}→{-30, -20, -17, -2, -6, 29}→{36, 18, -10, -21, -13, -45, -39, -42, -44}→{3, 1, -43, 12, 35}→{24, -48, 32, -19, -52, -27, 34, 28, 8, 15, -41}→{22, 49, 51, -38, -23, -11, -46, -50, -47, -7, -16, -14, -40} 0.057 9 0.932 1 137.262 5 {-20, -52, -5, -9}→{-30, -26, -6, 37}→{-43, -21, -18, -42, -33, 36}→{3, 1, -10, 12, 35}→{4, 32, 28, 34, -17, 22, 24, 31, 8}→{25, 29, -19, -27, 15, -38, -23}→{-2, 49, 51, 16, 47, -48, -50, -44, -41, -45, -11, 7, 13, 40, 46, 14, 39} 0.057 9 0.964 6 140.766 6 {-20, -43, -52, -9, -6}→{-5, -26, -30}→{-33, 36, 37, 21, 29, 18}→{42, -19, -27, 4, 3, 1}→{31, 25, 12, 47, -17, -48}→{32, 35, 24, -44, 14, 28, 15, 34, 22, -10}→{49, 51, 8, -38, -45, -23, -50, -13, -2, -7, -11, -41, -40, -39, -46, -16} 0.057 9 0.941 3 140.304 7 {-44, -5, -21, -26}→{-9, -30, -6, 29}→{32, -20, -10, -33, 36, 42}→{18, -2, 3, 1, 12}→{34, 22, 35, -52, 24, 7, 4, -13, -17, 28}→{31, 25, -43, -8, -48, -19, -45, -27}→{37, 49, -38, 51, 40, -23, -39, -46, -50, -47, -11, -15, -14, -41, -16} 0.057 9 0.976 1 141.924 8 {-45, -5, -9, -19, -52, -41}→{-20, -33, 36, 26}→{-30, -6, -21, -18, 3}→{1, 12, 35, 24, 28}→{34, -27, 22, -43, -48, -50, -2, 7, 47, 8, -40, 46}→{42, 37, -10, -16, 29, -17, -32, 4, 15, -51}→{31, 25, 49, 44, 13, -38, -23, -11, -14, -39}55, 0] 0.057 9 0.990 0 146.994
下载: 导出CSV
表 3 拆卸任务相关信息表
Table 3. Related data information of printer disassembly tasks
编号 零件名称 t/s U/(元·s-1) r P 1 电源线 3 0.002 9 -x 0 2 硒鼓 3 0.002 9 +z 0 3 搓纸轮 2 0.002 7 +z 0 4 分页器螺钉 16 0.005 5 -z 0 5 分页器 5 0.003 3 -z 4 6 进纸盘 40 0.010 3 +x 0 7 前面板 18 0.005 9 +x 9, 11 8 左侧板螺钉 8 0.003 9 -x 0 9 左侧板 33 0.008 9 -y 8 10 右侧板螺钉 8 0.003 9 -x 0 11 右侧板 13 0.004 9 -y 10 12 拉杆 5 0.003 3 +y 0 13 顶盖螺钉 16 0.005 5 +z 0 14 顶盖 10 0.004 3 -x 9, 11, 12 15 组排线 18 0.005 9 -y 9 16 加热组件螺钉 24 0.007 1 +z 14 17 加热组件 4 0.003 1 +z 16 18 后盖板螺钉 8 0.003 9 -x 0 19 后盖板 2 0.002 7 -x 18 20 电源板螺钉1 16 0.005 5 -x 9 21 电源板螺钉2 32 0.008 7 -y 9 22 电源板 15 0.005 3 -y 15, 20, 21, 24, 25, 28 23 塑料挡片 6 0.003 5 -y 15 24 带排线1 2 0.002 7 -y 9 25 地线 2 0.002 7 +z 9 26 拾纸组件螺钉1 16 0.005 5 -x 19 27 拾纸组件螺钉2 32 0.008 7 +y 0 28 拾纸组件排线 4 0.003 1 +y 9 29 拾纸组件 15 0.005 3 -x 25, 26, 27, 28 30 带排线2 2 0.002 7 +y 11 31 齿轮防尘罩螺钉 40 0.010 3 +y 11 32 齿轮防尘罩 3 0.002 9 +y 30, 31 33 继电器螺钉 8 0.003 9 +y 11 34 继电器 2 0.002 7 +y 33 35 格式化板螺钉 24 0.007 1 +y 11 36 格式化板 2 0.002 7 +y 35 37 传动齿轮组 15 0.005 3 +y 32 38 弹簧组 2 0.002 7 +y 32 39 ECU外罩螺钉 32 0.008 7 +z 7 40 ECU外罩 36 0.009 5 +z 39 41 基座螺钉 32 0.008 7 -z 0 42 基座 4 0.003 1 -z 27, 41 43 发动机螺钉 16 0.005 5 -y 40 44 发动机 3 0.002 9 -y 43, 48 45 右内侧板螺钉 8 0.003 9 +y 11 46 右内侧板 2 0.002 7 +y 43, 45 47 激光器电路板螺钉 8 0.003 9 +z 40 48 激光器电路板排线1 2 0.002 7 -y 40 49 激光器电路板排线2 2 0.002 7 +z 40 50 激光器电路板 10 0.004 3 +z 24, 30, 47, 48, 49 51 激光器螺钉 32 0.008 7 +z 50 52 激光器带排线 2 0.002 7 -y 40 53 激光器 2 0.002 7 +z 49, 51, 52 54 左内侧板螺钉 8 0.003 9 -y 22 55 左内侧板 2 0.002 7 -y 54
下载: 导出CSV
表 4 Pareto ACGA非劣解的平衡方案
Table 4. Non-inferior solution balance schemes of Pareto ACGA
编号 任务分配方案 f1 f2 f3 f4 1 {-55, -53, 27, 41, -51, -6}→{4, -29, -37, -26, -13, -52, -17, -16, -14, -38, -34, -46, -19, -3, -2, -44, -23}→{-43, -36, -35, -32, -31, 8, 1, 9}→{21, 15, 20, 24, 25, 28, 12, 22, 54, 10, 18, 11, 30}→{7, 39, 40, 49, 48, 42, 45, 33, 47, 5, 50} 5 594 6.655 5 32 2 {2, 27, 41, 4, 13, -29, -26, 8}→{6, 9, 15, 20, -37, 10}→{21, 11, 31, 35, 7, 33}→{39, 40, 1, 43, 45, 47, 18, 23, 12, 5, -17}→{-16, -14, -44, 52, 42, 28, 25, 3, 19, 24, 22, 54, 34, 30, 32, 38, 36, 46, 48, 49, 50, 51, 53, 55} 5 586 6.887 5 33 3 {-53, -1, 27, 6, 41, -51}→{4, -50, 8, 9, 21, 15, 20}→{-29, -23, -26, 10, 18, -47, -17, -16, -37, -13, 11, -14}→{45, 35, 33, 31, 7, 39}→{40, 43, 42, 28, 12, 5, -44, -2, 25, 3, 19, 24, 22, 54, 48, 30, 32, 38, 34, 36, 46, 49, 52, 55} 5 678 6.684 5 29 4 {1, 6, 27, 41, -37, -13}→{4, -29, -26, 10, 18, 12, 5, 42, 11, 31}→{35, 45, 33, -23, 8, 9, 21, 15}→{20, 7, 39, 40, 43, 47, 19, -44, 14}→{16, 17, 28, 2, 25, 3, 24, 22, 54, 48, 30, 32, 36, 34, 38, 46, 49, 50, 51, -53, -52, -55} 5 610 6.916 5 26 5 {-53, -1, -6, 27, 41, -51}→{-37, -23, -13, -50, -47, 10, -5, -29, -26, -4, 11, 45}→{31, 35, 33, 12, -44, 18, 8, 9}→{21, 15, 7, 20, 14, 39}→{40, 43, 16, 17, 42, 28, 2, 49, 3, 19, 24, 25, 22, 54, 48, 30, 32, 36, 34, 38, 46, 52, 55} 5 718 6.423 5 28 6 {-36, -13, 4, -29, -35, 41, 27}→{6, -26, 8, 9, 21, 28}→{-37, 20, 15, 23, 5, 12, 42, -17, -16, -14, 18, 10, -44, 11}→{31, 7, 33, 39, 40}→{43, 45, 47, 2, 1, 19, 3, 24, 25, 22, 54, 34, 30, 32, -53, -51, -50, -55, -38, -46, -48, -49, -52} 5 534 6.539 5 39 7 {-53, -51, 41, 27, 6}→{-37, -29, -26, -13, 4, -50, -23, -47, 18, 10, 8}→{9, 15, 11, 31, 21}→{35, 7, 45, 39, 40, 43}→{20, 33, 12, 5, -17, -16, -14, -42, -2, -44, -52, 28, 1, 34, 3, 19, 24, 25, 22, 54, 55, 30, 32, 48, 36, 38, 46, 49} 5 628 6.191 5 36 8 {10, 6, 27, 41, -37, 8}→{9, 21, 15, 20, 18, 23, 12, 13}→{-29, -26, 4, 11, 14, 31, 35}→{16, 33, 45, 5, 7, 42, 39, 40}→{43, 47, 17, -44, -2, 28, 36, 1, 49, 3, 19, 24, 25, 22, 52, 54, 55, 30, 32, 38, 34, 46, 48, 50, 51, 53} 5 506 6.916 5 32
下载: 导出CSV
-
国务院.国务院关于印发《中国制造2025》的通知[J].中华人民共和国国务院公报, 2015(16):10-26. http://www.cnki.com.cn/Article/CJFDTOTAL-ZQMP201503004.htm GUNGOR A, GUPTA S M. Disassembly line in product recovery[J]. International Journal of Production Research, 2002, 40(11):2569-2589. doi: 10.1080/00207540210135622 AVIKAL S, MISHRA P K, JAIN R. A Fuzzy AHP and PROMETHEE method-based heuristic for disassembly line balancing problems[J]. International Journal of Production Research, 2014, 52(5):1306-1317. doi: 10.1080/00207543.2013.831999 BENTAHA M L, BATTAIA O, DOLGUI A. Lagrangian relaxation for stochastic disassembly line balancing problem[J]. Procedia CIRP, 2014(17):56-60. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=CC0214534488 MCGOVERN S M, GUPTA S M. A balancing method and genetic algorithm for disassembly line balancing[J]. European Journal of Operational Research, 2007, 179(3):692-708. doi: 10.1016/j.ejor.2005.03.055 朱兴涛, 张则强, 朱勋梦, 等.求解多目标拆卸线平衡问题的一种蚁群算法[J].中国机械工程, 2014, 25(8):1075-1079. doi: 10.3969/j.issn.1004-132X.2014.08.016ZHU Xingtao, ZHANG Zeqaing, ZHU Xunmeng, et al. An ant colony optimization algorithm for multi-objective disassembly line balancing problem[J]. China Mechanical Engineering, 2014, 25(8):1075-1079. doi: 10.3969/j.issn.1004-132X.2014.08.016 MCGOVERN S M, GUPTA S M. Ant colony optimization for disassembly sequencing with multiple objectives[J]. The International Journal of Advanced Manufacturing Technology, 2006, 30(5):481-496. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=f857d98cf5114ed7c4cd3ae30371f41e KALAYCI C B, GUPTA S M. A particle swarm optimization algorithm for solving disassembly line balancing problem[C]//Proceedings for the Northeast Region Decision Sciences Institute. [S. l.]: Newport, 2012: 347-357. KALAYCI C B, GUPTA S M, NAKASHIMA K. Bees colony intelligence in solving disassembly line balancing problem[C]//Proceedings of the 2011 Asian Conference of Management Science and Applications. Sanya: [S. n.], 2011: 34-41. 张则强, 胡扬, 陈冲.求解拆卸线平衡问题的改进人工蜂群算法[J].西南交通大学学报, 2016, 51(5):910-917. doi: 10.3969/j.issn.0258-2724.2016.05.013ZHANG Zeqiang, HU Yang, CHEN Chong. An improved artificial bee colony algorithm for disassembly line balancing problem[J]. Journal of Southwest Jiaotong University, 2016, 51(5):910-917. doi: 10.3969/j.issn.0258-2724.2016.05.013 KALAYCI C B, POLAT O, GUPTA S M. A variable neighbourhood search algorithm for disassembly lines[J]. Journal of Manufacturing Technology Management, 2015, 26(2):182-194. doi: 10.1108/JMTM-11-2013-0168 TUNCEL E, ZEID A, KAMARTHI S. Solving large scale disassembly line balancing problem with uncertainty using reinforcement learning[J]. Journal of Intelligent Manufacturing, 2014, 25(4):647-659. doi: 10.1007/s10845-012-0711-0 KALAYCI C B, GUPTA S M. Tabu search for disassembly line balancing with multiple objectives[C]//Proceedings of the 41st International Conference on Computers & Industrial Engineering. Los Angeles: [S. n.], 2011: 477-482. KALAYCI C B, GUPTA S M, NAKASHIMA K. A simulated annealing algorithm for balancing a disassembly line[C]//Proceedings of the Seventh International Symposium on Environmentally Conscious Design and Inverse Manufacturing. Netherlands: [S. n.], 2011: 713-718. METE S, CIL Z A, AGPAK K, et al. A solution approach based on beam search algorithm for disassembly line balancing problem[J]. Journal of Manufacturing Systems, 2016, 41:188-200. doi: 10.1016/j.jmsy.2016.09.002 丁力平, 谭建荣, 冯毅雄, 等.基于Pareto蚁群算法的拆卸线平衡多目标优化[J].计算机集成制造系统, 2009, 15(7):1406-1413. http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200907022DING Liping, TAN Jianrong, FENG Yixiong, et al. Multiobjective optimization for disassembly line balancing based on Pareto ant colony algorithm[J]. Computer Integrated Manufacturing Systems, 2009, 15(7):1406-1413, 1429. http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200907022 ALAVIDOOST M, BABAZADEH H, SAYYARI S. An interactive fuzzy programming approach for bi-objective straight and U-shaped assembly line balancing problem[J]. Applied Soft Computing, 2016, 40:221-235. doi: 10.1016/j.asoc.2015.11.025 ALAVIDOOST M H, ZARANDI M H, TARIMORADI M, et al. Modified genetic algorithm for simple straight and U-shaped assembly line balancing with fuzzy processing times[J]. Journal of Intelligent Manufacturing, 2017, 28(2):313-336. doi: 10.1007/s10845-014-0978-4 AGRAWAL S, TIWARI M K. A collaborative ant colony algorithm to stochastic mixed-model U-shaped disassembly line balancing and sequencing problem[J]. International Journal of Production Research, 2008, 46(6):1405-1429. doi: 10.1080/00207540600943985 李明, 张则强, 胡扬. U型布局的拆卸线平衡问题及其求解算法研究[J].现代制造工程, 2015(7):7-12. doi: 10.3969/j.issn.1671-3133.2015.07.003LI Ming, ZHANG Zeqaing, HU Yang. Research on U-shaped disassembly line balancing problem and solving algorithm[J]. Modern Manufacturing Engineering, 2015(7):7-12. doi: 10.3969/j.issn.1671-3133.2015.07.003 张则强, 胡俊逸, 程文明.第Ⅰ类双边装配线平衡问题的改进蚁群算法[J].西南交通大学学报, 2013, 48(4):724-730. doi: 10.3969/j.issn.0258-2724.2013.04.020ZHANG Zeqiang, HU Junyi, CHENG Wenming. Improved ant colony algorithms for two-sided assembly line balancing problem of type Ⅰ[J]. Journal of Southwest Jiaotong University, 2013, 48(4):724-730. doi: 10.3969/j.issn.0258-2724.2013.04.020 KUCUKKOC I, ZHANG D Z. Integrating ant colony and genetic algorithms in the balancing and scheduling of complex assembly lines[J]. The International Journal of Advanced Manufacturing Technology, 2016, 82(1/2/3/4):265-285. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=c6d8fd8411099bdee157fb11d60a377b DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197. doi: 10.1109/4235.996017 -
下载:
点击查看大图
图(5) / 表(4)
计量
- 文章访问数: 446
- HTML全文浏览量: 237
- PDF下载量: 114
- 被引次数: 0