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

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

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

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.