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

摘要

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