基于遗传算法的多人旅行商问题求解

Genetic Algorithm Based Solution of Multiple Travelling Salesman Problem

旅行商问题是一个经典的NP完全问题,多人旅行商问题的求解则更具挑战性。以往对求解多人旅行商问题的研究局限于以所有成员路径总和最小为优化标准,而对以所有成员路径最大值最小为优化标准的另一类多人旅行商问题却未加注意。文章给出了这两类多人旅行商问题的形式化描述,探讨了利用遗传算法求解这两类多人旅行商问题的基本思想和具体方案,进行了仿真实验验证。仿真实验数据表明,这是一种高效而且适应性强的多入旅行商问题求解方法。

Previous researches on multiple travelling salesman problem are mostly limited to the kind that employed total-path-shortest as the evaluating rule, but little notice is paid on the kind that employed longest-path-shortest as the evaluating rule. The formalized models of the two kinds of multiple travelling salesman problem are presented in this paper, and the main idea and specific way of applying genetic algorithm in solving the two kinds of travelling salesman problem arc also discussed , the simulation is made at the end. As the simulation result shows, it is an effective and robust way of solving travelling salesman problem.