货郎担问题的应用与求解开题报告

全文总字数：2434字

1. 研究目的与意义

货郎担问题,即tsp(traveling salesman problem)问题，又译为旅行推销员问题、旅行商问题，是图论中的著名的问题，其目标是寻找一条最小代价的哈密顿图，具有npc计算复杂性，tsp问题是典型的组合优化问题，广泛应用在现实生活和实际工程中，如计算机网络节点设置、电子地图、物流配送、交通路线规划、航班飞行计划、电路板钻孔、铁路/公路网建设等。

当旅行商人数增多，问题变得更复杂时，经典的tsp模型优势不在，因此引入了多旅行商问题（mtsp，multiple traveling salesman problem），它是tsp的扩展，也是一个np复杂的问题。

多旅行商问题可以描述为m个旅行商从一个城市（或多个城市）出发，遍历n个城市，且每个城市有且仅有一个旅行商拜访，要求总路线最短的路径。

2. 国内外研究现状分析

旅行商问题在数学上的制定是由爱尔兰数学家哈密顿(william rowan hamilton)和英国数学家托马斯柯克曼(thomas penyngton kirkman) 于19世纪完成的。

tsp的一般形式似乎是由20世纪30年代维也纳和哈佛的数学家首次研究的，特别是卡尔门格尔（carl menger）定义了问题，考虑明显的蛮力算法，并观察观察非最优性最近邻启发式算法。

20世纪30年代，哈斯勒惠特尼（hassler whitney）在普林斯顿大学推出一个名为旅行商问题的问题后不久，merrill m. flood在解决校车路线问题过程中首先从数学角度考虑tsp问题。

3. 研究的基本内容与计划

研究内容： 首先把实际问题抽象成数学问题便于处理和计算，研究聚类算法，找一个合适的算法对目标问题进行拆分，对于拆解出来的小规模问题，运用遗传算法进行求解，遗传算法有良好的鲁棒性，是优化路径问题中常用的启发式仿生算法之一。

对比不同染色体编码的遗传算法的解空间复杂度。

时间安排 2019.01.132019.03.18 搜集资料、文献，查阅国内外研究动态，完成开题报告。

4. 研究创新点

现存求解TSP问题的启发式算法有很多，但是对于大规模问题还是会出现计算复杂度过高的问题，对于解决此类问题，本方法提出分层次分部求解复杂的TSP问题，使计算得到简化。

先用聚类算法把MTSP问题拆解成小规模TSP问题，再运用启发式随机搜索算法求解TSP问题。