面向多旅行商问题的多目标模拟退火算法研究

Research on Multi-objective Simulated Annealing Algorithm for Multi-traveling Salesman Problem

多旅行商问题是经典旅行商问题的一种演化,考虑一些约束,可以转换为一些较现实的问题,具有较高的理论研究和应用价值.在多旅行商问题中,一个任务由多位旅行商共同完成,问题的求解难度较经典旅行商问题更大.现有的研究中指定旅行商个数,将问题转换为固定数量的多旅行商问题.本文构建了求解pareto解的多目标多旅行商问题模型,针对一定规模的城市数量和约束的问题,获得多旅行商问题中旅行商的合适数量.本文将旅行商的个数和多旅行商的最长访问路径作为优化目标,采用改进的多目标模拟退火(IMOSA)算法和传统的多目标遗传算法对问题进行了求解.采用30个城市的旅行商问题对两种算法进行了测试,发现改进的多目标模拟退火算法相较于多目标遗传算法计算复杂度低,且能发现较好的pareto解,算法性能更优.

Multi-traveling salesman problem is an evolution of the classic traveler problem. Considering some constraints, it can be converted into some more realistic problems, with high theoretical research and application value. In the multi-traveling salesman problem, a task is completed by a number of travel agents, the problem is more difficult than the classic traveler problem. In the existing study, they convert the problem into a fixed number of traveling salesmen problem. In this paper,we construct a multi-objective multi-traveling salesman problem model for seeking the pareto solu-tion. In view of the problem of the number of cities and the constraints of a certain scale, we obtain the number of trave-ling salesmen of the problem. In this paper,the number of traveler and the longest access path of multi-traveler are taken as the optimization target. The improved multi-objective simulated annealing （ IMOSA） algorithm and multi-objective genetic algorithm are used to solve the problem. The results show that the improved multi-objective simulated annealing algorithm is more complex than the multi-objective genetic algorithm and can find a better pareto solution and the algo-rithm performance is better than that of the multi-objective genetic algorithm.