多旅行商问题的解空间分析及其车辆路由优化的应用研究

发布时间：2020-06-16 21:05

【摘要】：我们的社会丰富多彩,包罗万象,生活在大数据时代,车辆运输连接着我们生活的方方面面。车辆路由问题是一个在物流运输和资源分配等方面都有着非常广泛的应用的组合优化问题,是旅行商问题的进一步扩展,主要研究的问题是如何对车辆运输的路径进行优化以及如何合理的调配车辆。随着工业设计以及科学研究领域的各类复杂优化问题的不断深入,使用传统的优化算法在解决复杂优化问题时遇到了很多的困难,在这种背景下,群体智能优化算法的产生为解决复杂优化问题提供了新的思路。在众多群体智能算法中,遗传算法因其强大的全局搜索功能、鲁棒性高、适应性强、计算过程简单、便于与其他算法结合等特征,已广泛应用于工程优化、系统识别、自动控制等领域,是解决NP难问题的更有效的全局方法。本文使用遗传算法,旨在从理论和实验两方面多角度的分析和验证染色体编码方案的设计对于遗传算法解决多旅行商问题的至关重要的地位,综合全局搜索和局部搜索的平衡机制解决问题。基于相对解空间概念,首先分析三种染色体编码方案对应的解空间在极限意义下的相对大小关系,接下来分析旅行商数与城市数在不同情形下解空间的近似相对大小关系。本文对搜索空间定量分析的理论结果对工程问题的求解可以提供科学的指导意义。从而将其应用于目前较为流行的车辆路由优化问题中,创造性地提出了一种基于两段式编码方案的遗传算法。同时,本文在研究过程中重点关注遗传算法中染色体编码方式对解空间大小的影响,以及这种影响对群体寻求最优位置的指导。提出了一种基于两段式编码的遗传算法,采用先路由后集群的方法改进初始解的构造过程,并使用C-W-saving算法优化车辆的路线,优化选择操作中的选择策略,优化解的选择方法,并调整插入算子,对所选父代染色体进行特定的交叉变异操作,使用最大重叠交叉对子代进行交叉操作。最后在小数据集上进行仿真测试算法的收敛速度,并在大数据集上,通过与原始算法作对比来表明该算法的有效性。
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：U116.2;TP18
【图文】：

图２＿１解２间编码解码逡逑编码是实际问题和遗传算法之间的桥梁，遗传算法中的遗传算法不能直接实际问题的实际解空间，所以需要将要处理的实际优化问题的解空间转化为空间。使用遗传算法解决实际的优化问题时，首先要处理的问题就是染色体方式的选取。好的染色体编码策略可以大大提高算法效率，避免算法做一些功，不好的编码方法会带来算法的不适应，带来大量冗余解，而使算法无法。编码方法不断发展，常用的编码主要有以下几种：逡逑（１）二进制编码：二进制编码方式是遗传算法中最常用的一种编码方法。二编码是由０、１构成的，首先将实际优化问题的解空间变为由０、１构成的编间，然后在编码空间上进行下续的选择、交叉、变异等操作，在问题得到最后再将后代解码成实际优化问题适应的解空间。它的简单易行是它成为最案的重要原因，但在一些优化问题中，二进制编码因为只能表示几种状态不太适用。逡逑（２）实数编码：对于染色体ＸＭｘｐ邋ｘ２，…，ｘｆ，…，ｘｎ），Ｋ／分，ｘｔ．ｅＲ

逦Ｖ逦．／逡逑图２＿１解２间编码解码逡逑编码是实际问题和遗传算法之间的桥梁，遗传算法中的遗传算法不能直接处逡逑理实际问题的实际解空间，所以需要将要处理的实际优化问题的解空间转化为编逡逑码空间。使用遗传算法解决实际的优化问题时，首先要处理的问题就是染色体编逡逑码方式的选取。好的染色体编码策略可以大大提高算法效率，避免算法做一些无逡逑用功，不好的编码方法会带来算法的不适应，带来大量冗余解，而使算法无法进逡逑行。编码方法不断发展，常用的编码主要有以下几种：逡逑（１）

【相似文献】

相关期刊论文 前10条

1 俞庆生;林冬梅;王东;;多旅行商问题研究综述[J];价值工程;2012年02期

2 吴云;姜麟;刘强;;基于并行遗传算法多旅行商问题的求解[J];微型电脑应用;2011年07期

3 牟廉明;;子旅行商问题及其蚁群求解算法[J];计算机应用与软件;2011年11期

4 李天龙;吕勇哉;;基于自组织优化算法的一类多旅行商问题[J];计算机应用;2010年02期

5 崔鹏;;多源点的旅行商问题的一种求解方法[J];科协论坛(下半月);2010年09期

6 王海龙;周辉仁;魏颖辉;;基于遗传算法的一类多旅行商问题研究[J];计算机应用;2009年01期

7 李锋;魏莹;;基于仿真的遗传算法求解动态旅行商问题[J];系统管理学报;2009年05期

8 李飞;白艳萍;;用遗传算法求解旅行商问题[J];中北大学学报(自然科学版);2007年01期

9 赵曦;;广义旅行商问题与旅行商问题的转化[J];电脑知识与技术(学术交流);2007年05期

10 江贺;张宪超;陈国良;;有向黑白旅行商问题[J];计算机学报;2007年03期

相关会议论文 前10条

1 冯纯伯;;旅行商问题的一种解法[A];1991年控制理论及其应用年会论文集（下）[C];1991年

2 李大卫;王梦光;;热轧调度与多旅行商问题[A];1996年中国控制会议论文集[C];1996年

3 张雷;郑维敏;;广义旅行商问题、放映员问题和一类调度模型[A];1996年中国控制会议论文集[C];1996年

4 熊翠;吴慧萍;李波;;多旅行商问题遗传算法求解及其改进[A];第四届中国智能计算大会论文集[C];2010年

5 刘春波;潘丰;杨丹;;基于改进的蚁群算法在中国旅行商问题中的求解[A];2007中国控制与决策学术年会论文集[C];2007年

6 贾亚军;丛爽;;粒子群与模拟退火的混合算法求解旅行商问题[A];'2010系统仿真技术及其应用学术会议论文集[C];2010年

7 李丽;程玉荣;牛奔;;离散人工蜂群算法求解旅行商问题[A];第十三届中国管理科学学术年会论文集[C];2011年

8 韩爱丽;朱大铭;;旅行商问题的一种新DNA编码方案[A];2006年全国理论计算机科学学术年会论文集[C];2006年

9 张炜;李勇刚;周晓君;;一种求解有城市访问顺序约束旅行商问题的状态转移算法[A];2018中国自动化大会(CAC2018)论文集[C];2018年

10 董亚非;谭刚军;张社民;;基于粘贴系统求解TSP问题[A];提高全民科学素质、建设创新型国家——2006中国科协年会论文集（下册）[C];2006年

相关博士学位论文 前10条

1 孟祥虎;着色旅行商问题及其动态化研究[D];东南大学;2017年

2 谭阳;求解广义旅行商问题的若干进化算法研究[D];华南理工大学;2013年

3 张梦颖;不确定因素下路径规划问题研究[D];中国科学技术大学;2016年

4 魏航;基于邻接实数矩阵编码的路径优化进化算法的研究[D];华南理工大学;2017年

5 王刚;两类圈问题的算法研究[D];国防科学技术大学;2013年

6 包晓光;一些路线问题的算法设计与分析[D];华东理工大学;2012年

7 李茂军;单亲遗传算法理论及应用[D];湖南大学;2002年

8 曾华;随机顾客和需求的配送优化[D];山东大学;2012年

9 李娜娜;仿生算法及其在专家分配问题中的应用[D];天津大学;2008年

10 费威;最小调整法的改进及其在经济优化中的应用[D];东北财经大学;2010年

相关硕士学位论文 前10条

1 郭赛;多旅行商问题的解空间分析及其车辆路由优化的应用研究[D];北京邮电大学;2019年

2 束东来;基于遗传算法的多旅行商问题的优化[D];安庆师范大学;2018年

3 谢曾慧;求解多目标旅行商问题的改进蚁群优化算法研究[D];东北大学;2017年

4 师喜婷;狼群算法的改进及其在复杂函数优化问题中的应用[D];西安理工大学;2018年

5 邓昶博;改进蚁群算法解决电商快递场景下的多目标多旅行商问题[D];华南理工大学;2018年

6 郑硕;新型启发式算法求解旅行商问题及其衍生问题[D];天津大学;2017年

7 赵丽娜;带油耗的单商品取送货旅行商问题研究[D];沈阳师范大学;2016年

8 徐东镇;蚁群算法及其在广义旅行商问题求解中的应用[D];合肥工业大学;2007年

9 胡平;群集智能算法在不确定旅行商问题中的应用研究[D];吉林大学;2007年

10 袁豪;旅行商问题的研究与应用[D];南京邮电大学;2017年

本文编号：2716585