基于遗传算法的多旅行商问题的优化

发布时间：2020-10-14 22:51

　　 旅行商问题(Traveling Salesman Problem,TSP)是一个经典的NP-hard组合优化问题,多旅行商问题(Multiple Traveling Salesman Problem,MTSP)作为其扩展模型,具有更强的实际意义。而在理想情况下的旅行商问题及多旅行商问题几乎是不存在的,本文介绍了两种更符合实际意义的限容量多旅行商问题(Multiple Traveling Salesman Problem With Limited Capacity,LCMTSP)和不确定性多旅行商问题(Uncertain Multiple Traveling Salesman Problem,UMTSP)模型,并设计了遗传算法(Genetic Algorithm,GA)对这两种模型进行求解。本文首先对LCMTSP问题模型进行了研究,将容量限制条件加入到多旅行商问题模型中,以控制每个旅行商访问城市个数范围。鉴于问题的复杂性,本文在传统GA的种群初始化过程中,采用完全随机法和适用于多旅行商问题模型的次优选择法,并在交叉算子中加入最小路径交叉等规则,且引入DI算子和3-opt算子。实验结果证明了所设计IGA求解LCMTSP问题时的可行性和有效性以及较高的计算效率。考虑到理想化的多旅行商问题在现实环境中的不可靠性,本文将现实情况下的不确定性因素归纳为一种路况系数,从而构建了不确定性多旅行商问题(UMTSP)模型。针对该问题,设计了遗传算法对其进行了求解,并比较基本MTSP问题与UMTSP问题的实验结果。实验结果证明了UMTSP问题模型的实际意义以及所提遗传算法的可行性与实用性。
【学位单位】：安庆师范大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：C81
【部分图文】：

TSP问题的研究方法

种群初始化

种群初始化
【参考文献】

相关期刊论文 前10条

1 麻存瑞;马昌喜;;不确定旅行商问题的鲁棒模型与算法[J];计算机应用;2014年07期

2 柯良军;尚可;冯祖仁;;不确定旅行商问题的鲁棒模型及其算法研究[J];计算机科学;2012年S1期

3 崔瑾娟;;基于遗传算法的旅行商问题的研究[J];安阳师范学院学报;2012年02期

4 王越;许全文;黄丽丰;;基于改进遗传算法的连续函数优化[J];重庆理工大学学报(自然科学版);2011年02期

5 张建强;方卫国;;有时间窗约束车辆路径问题的改进遗传算法[J];计算机工程与应用;2010年32期

6 郭强;迟洪钦;;基于GA的MTSP问题的研究[J];计算机与数字工程;2010年10期

7 黄宝珠;肖菁;;改进的MIMIC算法求解旅行商问题[J];计算机工程与设计;2010年16期

8 高岳林;刘军民;;差分进化算法的参数研究[J];黑龙江大学自然科学学报;2009年01期

9 徐志伟;张耀坤;张勇;黄雷;;求解旅行商问题的一种改进遗传算法[J];四川兵工学报;2009年01期

10 杨尚达;李世平;;遗传算法研究[J];兵工自动化;2008年09期

相关硕士学位论文 前10条

1 王雪红;基于遗传算法的车辆路径优化问题的应用研究[D];天津科技大学;2016年

2 杨俊雷;基于改进遗传算法的结构可靠度计算[D];河北工程大学;2012年

3 张虎;遗传算法的改进研究及其在工程优化中的应用[D];三峡大学;2012年

4 王娜;求解TSP的改进遗传算法[D];西安电子科技大学;2010年

5 姜薇;遗传算法中交叉算法的改进[D];吉林大学;2009年

6 王进;蚁群算法在物流系统中的应用研究[D];南昌大学;2008年

7 王爽;改进的自适应遗传算法在知识库中的应用研究[D];大连交通大学;2008年

8 刘道军;向量编码遗传算法求解TSP问题的研究[D];中南民族大学;2008年

9 程娜;基于混合进化算法的车辆路径优化问题的研究[D];延边大学;2008年

10 支姝;基于遗传算法的配送路线优化研究[D];长安大学;2008年

本文编号：2841304