多旅行商问题的智能算法设计与仿真开题报告

全文总字数：3951字

1. 研究目的与意义（文献综述）

多旅行商问题(multipletraveling salesman problem, mtsp)是经典旅行商问题(travelingsalesman problem, tsp)的一种泛化和推广,加上某些特定的附加条件,则能够演化成一些较现实的问题,如快递员送货、车辆的路径规划、应急物资配送、多无人机协同侦察路径优化等，因而具有较高的理论研究和应用价值。在多旅行商问题中,一个任务由多位旅行商共同完成,其问题的求解难度较经典旅行商问题更大,用于经典旅行商问题求解的方法或策略不能简单地应用于多旅行商问题的求解,有关该问题的研究成果远比经典旅行商问题少。很多组合优化问题，比如背包问题、分配问题、车间调度问题都和tsp同属np完全问题，它们都是同等难度的，如果其中一个能用多项式确定性算法解决，那么其他所有的np完全问题也能用多项式算法解决。许多关于tsp的工作并不仅是由实际应用直接推动的，而是因为tsp为其它一般的各类算法提供了思想方法平台，而这些算法广泛地应用于各种离散优化问题。很多方法本来是从tsp发展起来的，后来推广到其他np完全问题上去，tsp大量的直接应用给研究领域带来了生机，并引领了未来的工作。

旅行商问题的与众不同之处在于，尽管世界各地的一流应用数学家已经研究了几十年，但人们如今依然不知道，对于一般性的旅行商问题，如何才能得出远远优于简单暴力枚举检验的通用解法。由于社会发展的需求变更以及经典tsp方面研究成果不断积累，mtsp研究逐渐成为了新的研究热点。一般来讲，泛化的mtsp定义如下：给定一个n个结点（城市）集合，让m个旅行商各自从一个城市出发，每位旅行商访问其中一定数量的城市，最后回到其出发城市，要求每个城市至少被一位旅行商访问一次并且只能一次，问题的目标是求得访问m条环路代价最小访问次序，其中代价可以是距离、时间、费用等。

对多旅行商问题的研究是从上个世纪七十年代开始，最初主要采用精确算法对问题求解，其中有线性规划方法、动态规划方法、分支定界方法，但由于问题规模的扩大，问题解空间膨胀速度与问题规模呈指数关系，成为限制精确算法求解mtsp性能的主要瓶颈，后续的研究工作逐渐倾向于采用启发式算法或元启发式算法，常用的算法有lin-kernighan 算法、神经网络算法、遗传算法、蚁群算法等。然而，该问题是否存在一个有效的通用的求解方法仍然是一个开放性的问题。旅行商问题吸引了越来越多的人对它进行研究。其中，有数学家，计算机科学家，运筹学家，还有一些其它领域的研究者。大部分研究的解决方案都是先将mtsp 转化为tsp，然后在转化得到的tsp 基础上利用tsp 的求解算法再进行求解。

2. 研究的基本内容与方案

基本内容：分析多旅行商问题的特征，主要针对一种典型的多旅行商问题进行智能算法的设计并进行计算仿真，例如物流配送中心选址问题，由于市场竞争激烈，客户可能会从快速、灵活和免费送货的公司购买产品；应急物资配送问题：无人机救援、无人机送货服务等，目标是削减成本，提供更便宜，更快捷，更高效的服务。

目标：通过matlab仿真分析算法的最优解、程序运行时间、求解规模大小、全局寻优性能等，不断改进算法程序，使算法的适用性更强，当问题复杂时也能有一个较好的效果。

方案1：采用遗传算法，遗传算法（geneticalgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。在tsp领域，遗传算法的思路大致如下。首先形成路线的初始种群，可以通过反复从随机城市出发使用最近邻算法获取路线；然后是一般的循环步骤，在种群中选取若干对路线，让它们交叉配对得到子代路线，再从父子两代路线中选出一个新的种群。反复多次进行这一步骤，最优秀的路线最终将脱颖而出，成为唯一的生存赢家。在遗传算法的基本原则框架下，路线种群进化的方法各式各样，为我们留有充足的选择空间。我们不但可以选择交叉配对过程，也可以选择适应度评价标准以确定如何选择下一代种群。

3. 研究计划与安排

第1～2周：翻译相关外文资料，初步确定方案，完成开题报告；

第3～4周：对拟采用智能算法的设计和程序实现等进行方案论证；

第5周：确定最终方案，并进行可行性分析；

4. 参考文献（12篇以上）

[1]william j c.迷茫的旅行商：一个无处不在的计算机算法问题[m].隋春宁，译.北京：人民邮电出版社，2013:200-207.

[2] 俞庆生，林冬梅，王东.多旅行商问题研究综述[j].价值工程，2012,31(2)：166-168.

[3] 徐小平，张东洁.基于猴群算法求解旅行商问题[j].计算机工程与应用，2018,54(2)：144-148.