基于遗传算法的一类多旅行商问题研究

旅行商问题是一个经典的NP完全问题，对多人旅行商问题的求解则更具有意义。以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准，而对所有旅行商路径最大值最小的多旅行商一类问题研究的相对较少。针对所有旅行商路径最大值最小的多旅行商一类问题，用遗传算法优化，并且提出了矩阵解码方法。该方法适于距离对称和非对称的多旅行商问题求解。以距离非对称的多旅行商问题的实例进行了仿真，并对不同交叉算子性能进行了比较。

Study on multiple traveling salesman problem based on genetic algorithm

Traveling salesman problem is a classical complete nondeterministic polynomial problem. It is significant to solve Multiple Traveling Salesman Problems (MTSP). Previous researches on multiple traveling salesman problem are mostly limited to the kind that employed total-path-shortest as the evaluating rule, but little notice is made on the kind that employed longest-path-shortest as the evaluating rule. In order to solve this problem, genetic algorithm was used to optimize it and decoding method with matrix was proposed. It is fit for solving symmetric and asymmetric MTSP. Symmetric and asymmetric multiple traveling salesman problems were simulated and different crossover operators were compared.