混合伊藤算法求解多尺度着色旅行商问题

Hybrid IT? algorithm for multi-scale colored traveling salesman problem

着色旅行商问题(CTSP)是多旅行商问题(MTSP)与旅行商问题(TSP)的一种扩展,主要应用于含重复区域的多机工程系统(MES)等工程问题。CTSP是NP完全问题,尽管相关研究尝试采用遗传算法(GA)、模拟退火(SA)等方法求解该问题,但它们求解的问题尺度有限,且速度和求解质量上不尽人意。基于此,尝试采用一种基于均匀设计(UD)融合蚁群(ACO)算法和伊藤算法(IT?)的混合伊藤算法(UDHIT?)来求解该问题。UDHIT?采用UD来选择合适的参数组合,借助ACO的概率图模型来产生可行解,并利用伊藤算法的漂移和波动算子进行优化。实验的结果表明,UDHIT?求解多尺度CTSP的最优解和平均解比传统GA、ACO和IT?有所改善。

Colored Traveling Salesman Problem(CTSP)is a variant of Multiple Traveling Salesmen Problem(MTSP)and Traveling Salesman Problem(TSP),which can be applied to the engineering problems such as Multi-machine Engineering System(MES)with overlapping workspace.CTSP is an NP complete problem,although related studies have attempted to solve the problem by Genetic Algorithm(SA),Simulated Annealing(SA)algorithm and some other methods,but they solve the problem at a limited scale and with unsatisfactory speed and solution quality.Therefore,a hybrid IT?algorithm combined with Uniform Design(UD),Ant Colony Optimization(ACO)and IT? algorithm was proposed to solve this problem,namely UDHIT?.UD was applied to choose the appropriate combination of parameters of the UDHIT?algorithm,the probabilistic graphic model of ACO was used to generate feasible solutions,and the drift operator and volatility operator of IT? were used to optimize the solutions.Experimental results show that the UDHIT? algorithm can demonstrate improvement over the traditional GA,ACO and IT? algorithm for the multi-scale CTSP problems in terms of best solution and average solution.