计算机应用 ›› 2021, Vol. 41 ›› Issue (3): 881-886.DOI: 10.11772/j.issn.1001-9081.2020060868

所属专题: 前沿与综合应用

• 前沿与综合应用 • 上一篇    下一篇

基于旅行商问题转化和遗传算法求解汽配件喷涂顺序

王彬溶1, 谭代伦1,2, 郑伯川2   

  1. 1. 西华师范大学 数学与信息学院, 四川 南充 637009;
    2. 西华师范大学 计算方法及应用软件研究所, 四川 南充 637009
  • 收稿日期:2020-06-23 修回日期:2020-10-20 出版日期:2021-03-10 发布日期:2021-01-15
  • 通讯作者: 谭代伦
  • 作者简介:王彬溶(1995-),女,四川巴中人,硕士研究生,主要研究方向:运筹与优化应用;谭代伦(1971-),男,重庆人,教授,硕士,主要研究方向:优化理论与应用;郑伯川(1974-),男,四川自贡人,教授,博士,主要研究方向:机器学习、深度学习。
  • 基金资助:
    四川省教育厅自然科学基金重点项目(15ZA0152);四川省科技计划项目(2019YFG0299);四川省教育厅重点教改项目(JG2018-688);西华师范大学英才基金资助项目(17YC387);西华师范大学重点教改项目(JGXMZA1825)。

Solving auto part spraying sequence by transforming to traveling salesman problem and genetic algorithm

WANG Binrong1, TAN Dailun1,2, ZHENG Bochuan2   

  1. 1. School of Mathematics and Information, China West Normal University, Nanchong Sichuan 637009, China;
    2. Institute of Computing Method and Application Software, China West Normal University, Nanchong Sichuan 637009, China
  • Received:2020-06-23 Revised:2020-10-20 Online:2021-03-10 Published:2021-01-15
  • Supported by:
    This work is partially supported by the Key Project of the Natural Science Foundation of the Education Department of Sichuan Province (15ZA0152), the Science and Technology Program of Sichuan Province (2019YFG0299), the Key Teaching Reform Project of the Education Department of Sichuan Province (JG2018-688), the Talent Foundation of China West Normal University (17YC387), the Key Teaching Reform Project of China West Normal University (JGXMZA1825).

摘要: 对汽配件颜色喷涂顺序进行优化有助于企业进一步降低生产成本,而目前尚无研究对该类问题提出针对性的数学模型和解法。考虑到每一个汽配件必须喷涂且只喷涂一次,具有旅行商问题(TSP)的基本特征,为此提出了TSP转化的建模方法并选用并行性和鲁棒性强的遗传算法(GA)进行求解。首先,将汽配件定义为TSP顶点,根据汽配件的颜色和类别要求定义顶点之间的距离和生产约束条件,以此构建了使喷涂序列颜色切换次数最少的0-1规划模型。其次,将汽配件的颜色和类别约束转化为惩罚因子,从而构成遗传算法的适应度函数,并基于锦标赛选择策略综合设计了复制、交换、翻转、滑动的变异策略。最后,构造汽配件数为64、93、293个,颜色数为5、7、10种的三组数据进行仿真实验,所提算法对这三组数据均能求得精确最优解5,7,10,而重复运行算法,可以获得近似最优解的均值分别为5.63,7.30,11.49。实验结果表明所建立的数学模型对汽配件颜色喷涂顺序问题的刻画准确,设计的遗传算法高效实用,此二者可推广应用于其他类似的生产加工问题。

关键词: 汽配件喷涂顺序问题, 旅行商问题, 0-1规划模型, 遗传算法, 惩罚因子

Abstract: Optimizing the color spraying sequence of auto parts can help enterprises to further reduce the production costs. However, there is no research proposing specific mathematical models and solutions for this type of problems. Considering the fact that each auto part must be sprayed and sprayed only once, which has the basic characteristics of the Traveling Salesman Problem (TSP), a modeling method of TSP transformation was proposed and the Genetic Algorithm (GA) with strong parallelism and robustness was selected to solve it. Firstly, the auto parts were defined as the TSP vertices, and the distance between the vertices and production constraints were defined according to the color and category requirements of the auto parts, so as to construct a 0-1 planning model for minimizing the number of color switching of the spraying sequence. Secondly, the color and category constraints of the auto parts were transformed into penalty factors, so as to construct the fitness function of the genetic algorithm. And, based on the championship selection strategy, the mutation strategies of copying, swapping, flipping, and sliding were comprehensively designed. Finally, three sets of data with 64, 93, 293 auto parts and 5, 7, 10 colors were constructed for simulation experiments. The proposed algorithm can obtain the accurate optimal solutions 5, 7, 10 for all three sets of data. With repeatedly running the algorithm, the average values of the approximate optimal solution are 5.63, 7.37, 11.49. Experimental results show that the established mathematical model is accurate to describe the auto part spraying sequence problem, and the designed genetic algorithm is efficient and practical, both of them can be applied to other similar production and processing problems.

Key words: auto part spraying sequence problem, Traveling Salesman Problem (TSP), 0-1 programming model, Genetic Algorithm (GA), penalty factor

中图分类号: