基于GA的最小旅行时间的多旅行商问题研究

Study on minimum completion time multiple traveling salesman problem based on genetic algorithm

以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准,而对最小完成时间的多旅行商一类问题研究得相对较少。针对所有旅行商最小完成时间的多旅行商一类问题,用遗传算法进行优化,且提出了矩阵解码方法。以距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较,适于距离对称和非对称的多旅行商问题求解。

Previous research on multiple traveling salesman problems is 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-time-shortest as the evaluating rule. In order to solve this problem, used genetic algorithm to optimize it and proposed decoding method with matrix. This paper simulated symmetric and asymmetric multiple traveling salesman problems and compared different crossover operators. It is fit for solving symmetric and asymmetric multiple traveling salesman problems.