摘 要

近年来随着移动网络的飞速发展，物流配送产业的规模不断增长，人们的生活得到了极大的便利。而大量的运送过程中，多城市、多地区间的配送路径选择往往决定了配送过程中的主要成本。求解该问题的本质即是计算获得旅行商问题的最优解。因此研究不同算法求解TSP问题的性能有着十分重要的意义。

通过对文献及网络资料的学习研究，本文借助MATLAB软件针对多启发式算法求解TSP问题进行了建模求解，并推广到MTSP问题当中，将遗传算法、蚁群算法、模拟退火算法、离散狼群算法、基于遗传操作的离散粒子群算法求解若干规模逐渐增大的城市标准测试集的性能进行统计对比，引入TOPSIS方法为各个算法在最优解、收敛速度、运行时间以及参数需求等指标下求解单个城市集综合打分排序，利用Friedman检验为算法在所有城市集上的综合求解表现上进行排序，并分析了不同算法的优劣性。

所得结果表明在TSP不同城市规模的问题求解中，模拟退火综合表现最好，离散狼群算法整体性能最为稳定，基于遗传操作的离散粒子群方法在城市规模较小时在不同性能指标下具有显著的求解优势，遗传算法和蚁群算法在城市规模较大时各性能都相对小规模时有所提高；在MTSP问题不同城市规模的问题求解中，依然是模拟退火的综合表现最好，遗传算法与蚁群算法的优劣差异并不明显。

本文的研究对于在不同需求的旅行商问题下合适的启发式算法选取以及根据算法间的优劣进行创新型混合算法设计具有重要的指导意义。

关键词： TSP；MTSP；多启发式算法；TOPSIS；Friedman检验

Abstract

In recent years, with the rapid development of mobile network, the scale of logistics distribution industry has been growing. The choice of distribution routes between multi-cities and multi-regions often determines the main cost in the process of delivery. The essence of solving this problem is to calculate and obtain the optimal solution of the traveling salesman problem. Therefore, it is very important to study the performance of different algorithms solving TSP problems.

By accomplishing study and research of literature and network materials, with the help of MATLAB software modeling for multiple heuristic algorithm to solve TSP problem solving, and extend the model to MTSP problem in this paper, using the Genetic Algorithm, Ant Colony Algorithm, Simulated Annealing Algorithm, the Discrete Wolves Pack Algorithm, Discrete Particle Swarm Optimization based on genetic operations to solve a number of standard cities test set statistical, introducing TOPSIS method and Friedman test method for each algorithm in the optimal solution and convergence speed, running time and comprehensive grade sorting under parameter indexes of demand to draw comparisons of the performances.

The results showed that in different TSP city sizes of the problem solving, the comprehensive performance of BSA is the best, DWPA overall performance is the most stable, GPSO has significant advantages in dealing with the problem in small urban sizes while GA and ACO have relatively improvement and corresponding advantages in performance in the larger city sizes. In solving the MTSP problem with different city sizes, BSA still has the best comprehensive performance. However, the performance differences between GA and ACO are not obvious.

The research of this paper provides significant guiding in the suitable heuristic algorithm selection among different demands of traveling salesman problem and offering innovative hybrid algorithm design directions based on merits of different algorithms.

Key Words： TSP；MTSP；heuristic algorithms；TOPSIS；Friedman test

目 录

第1章 绪论 1

1.1 研究背景与意义 1

1.2 国内外研究现状 1

1.3 研究内容与结构 2

1.4 本文创新点 3

第2章 旅行商问题理论基础 4

2.1 旅行商问题 4

2.2 多重旅行商问题 4

2.2.1 车辆路径问题 4

2.2.2 多重旅行商问题 5

2.3 本章小结 6

第3章 求解旅行商问题算法设计 7

3.1 遗传算法 7

3.1.1 遗传算法的构成要素 7

3.1.2 遗传算法的算法步骤 8

3.2 蚁群算法 10

3.2.1 蚁群算法的构成要素 10

3.2.2 蚁群算法的算法步骤 11

3.3 模拟退火算法 12

3.3.1 模拟退火算法的构成要素 12

3.3.2 模拟退火算法的算法步骤 13

3.4 狼群算法 15

3.4.1 离散狼群算法的构成要素 15

3.4.2 离散狼群算法的算法步骤 16

3.5 粒子群算法 17

3.5.1 粒子群算法的构成要素 17

3.5.2 粒子群算法的算法步骤 18

3.6 本章小结 19

第4章 仿真实验及结果分析 20

4.1 实验环境 20

4.2 TSP问题实验过程及结果分析 20

4.2.1 TSP问题的求解结果 20

4.2.2 TSP问题的求解结果分析 32

4.3 MTSP问题实验过程及结果分析 36

4.3.1 MTSP问题的求解结果 36

4.3.2 MTSP问题的求解结果分析 40

4.4 本章小结 41

第5章 结论与展望 42

参考文献 43

致 谢 45

第1章 绪论

1.1 研究背景与意义

在事先确定的约束条件下，为了获得问题目标函数的极小值或极大值，探求特定变量间的最优组合问题，即利用数学或计算机算法去寻找离散事件的最优方案，被称作组合优化问题，这在运筹学中占据着十分重要的位置。

作为组合优化问题中最有代表性的典型难题，旅行商问题(Traveling Salesman Problem，简称TSP)是一个NP完全问题，也同样是运筹学里的重要内容^[1]。其具体内容为：若一个商人想到N个城市进行商品售卖，设任意两城市i和j之间的距离为，以何种方式选择一条连通路能让这名商人在每个城市仅访问一遍后回到起点的条件下所走路径最短。对一个N城市的TSP问题，一共存在条可能路径。

多重旅行商问题(Multiple Traveling Salesman Problem，简称MTSP)是TSP问题的一个变种，可以用来更有效地解释实际应用。在MTSP模型中，不是只有一个销售人员，而是几个销售人员必须访问这些城市，这样每个城市只有一个销售人员访问，目标是最小化所有销售人员路径长度的总和^[2]。

在实际应用中，TSP模型被广泛应用于农业、工业、商业、计算机等不同领域的实际问题，如路由问题、网络问题^[3]和调度问题^[4]。