半平面集聚点群TSP几何方法及其在物流路径优化中的应用

发布时间：2017-03-28 02:12

  本文关键词：半平面集聚点群TSP几何方法及其在物流路径优化中的应用，由笔耕文化传播整理发布。

【摘要】：随着电子商务技术的蓬勃发展,物流配送已成为国民经济新兴产业,车辆优化调度是物流配送的重要内容,物流路径规划是车辆优化调度的基础。路径规划属于旅行商问题(Traveling Salesman Problem),从图论的角度看,是在加权图中寻找最优哈密尔顿回路问题,常用的方法有最邻近法、最小树生成法、最小权匹配法以及改良圈算法等,这些都是一种近似算法,在图论中还不能用理论证明某种算法所求取的哈密尔顿回路最优,被归属于组合优化领域中的NP难题(Non-deterministic Polynomial),当前主要集中于采用优化方法求解,如模拟退火、遗传算法、进化计算、粒子群、蚂蚁群等方法,研究对象均是任意的有向图,未能结合物流配送目标门店的空间分布。因此,研究适用于解决实际生产活动中的物流路径规划问题的方法具有重要意义。在实际物流配送实践中,发现物流配送具有受车辆装载容积限制、单次配送门店数量少、门店相对聚集的特点。依据图论生成哈密尔顿环的相关理论,简化物流配载数学模型,定义了半平面聚集点群概念,提出了半平面集聚点群TSP几何求解方法,方法基本出发点是:以顶点距离作为权的加权图,生成图的哈密尔顿环与顶点的空间分布有关,实际生产环境中约束图顶点的空间分布会简化TSP的求解。半平面集聚点群TSP几何方法具体做法是:做点群平分线,从点群中找到距离源顶点最远的顶点,距离为l,以l为长度在角平分线上作点v_f,选择离点v_f最近的顶点和源顶点形成初始线路,其他各点加入次序为:加入后使得初始线路的增长量最大,以加入后增加的距离最少最近确定加入回路或去路。从理论上证明了由该方法生成的回路是哈密尔顿环,分析了方法的合理性;给出了方法的程序实现,计算了算法的复杂度;讨论了方法应用于物流路径规划过程中,出现的不满足半平面聚集点群的各种情况,提出了分解点群由多个哈密尔顿环组合形成回路的解决方案。半平面集聚点群TSP几何方法通过理论分析以及与贪婪算法、遗传算法对比实验验证,有如下结论:(1)方法利用了顶点空间分布特征,算法复杂度较低;(2)对于半平面聚集点群,方法所生成的回路是较优的哈密尔顿环,方法具有较高的精度和稳定性,能适用于实际的物流路径规划。半平面集聚点群TSP几何方法针对物流路径规划特点,利用图的顶点空间分布特征,简化数学模型,较好地解决了物流路径规划问题。
【关键词】：半平面集聚点群 旅行商问题 几何方法 物流路径规划
【学位授予单位】：湖南科技大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：U116.2;F252
【目录】：

• 摘要5-6
• ABSTRACT6-10
• 第1章 绪论10-16
• 1.1 研究背景和意义10-11
• 1.1.1 研究背景10
• 1.1.2 研究意义10-11
• 1.2 国内外研究现状11-13
• 1.3 研究内容和论文结构13-16
• 1.3.1 研究内容13-14
• 1.3.2 论文结构14-16
• 第2章 物流路径规划理论基础16-28
• 2.1 图论基础16-21
• 2.1.1 基本概念16-18
• 2.1.2 哈密尔顿环18-21
• 2.2 TSP常用求解方法21-26
• 2.2.1 贪婪算法22-24
• 2.2.2 遗传算法24-26
• 2.3 本章小结26-28
• 第3章 半平面集聚点群TSP几何求解方法28-38
• 3.1 半平面集聚点群28-29
• 3.2 几何求解方法29-35
• 3.2.1 算法思想29-30
• 3.2.2 算法详细步骤30-35
• 3.2.3 算法理论依据35
• 3.3 算法时间复杂度35-36
• 3.4 本章小结36-38
• 第4章 TSP几何求解方法在物流路径规划中的应用38-64
• 4.1 物流路径规划实现38-43
• 4.1.1 数据组织39-42
• 4.1.2 地图渲染42
• 4.1.3 实现效果42-43
• 4.2 门店分布特征分类及处理方法43-52
• 4.2.1 门店集聚分布的区域43-44
• 4.2.2 门店分布在仓库两侧的区域44-47
• 4.2.3 初始途径点分布在派车区域集聚点群边界上47-52
• 4.3 实验对比与分析52-63
• 4.3.1 贪婪算法路径规划实验52-54
• 4.3.2 遗传算法路径规划实验54-56
• 4.3.3 实验结果对比与分析56-63
• 4.4 本章小结63-64
• 第5章 结论和展望64-66
• 5.1 主要研究成果及创新点64
• 5.2 后续工作64-66
• 参考文献66-70
• 致谢70-72
• 附录A：攻读硕士学位期间的研究成果72

【参考文献】

中国期刊全文数据库 前10条

1 张伟;;基于蚁群算法的物流配送中车辆路径优化问题研究[J];物流科技;2015年10期

2 董妍汝;;基于选择算子的遗传算法改进[J];办公自动化;2015年16期

3 李金旭;黄悦悦;;求解TSP的贪心模拟退火算法[J];河南工程学院学报(自然科学版);2015年01期

4 苏晓勤;孙鹤旭;潘旭华;;改进蜂群算法的旅行商问题仿真[J];计算机工程与设计;2013年04期

5 傅刚;;PSO-TSP问题综述[J];黑龙江科技信息;2012年31期

6 马冬青;王蔚;;基于改进粒子群算法的物流配送车辆调度[J];计算机工程与应用;2014年11期

7 赵吉东;;蚁群算法的改进策略研究[J];中国科技信息;2012年12期

8 刘红军;赵帅;赵雷;;一种基于GA-SA-TS算法的车间调度方法的研究[J];制造技术与机床;2012年03期

9 杜占玮;杨永健;孙永雄;张池军;;基于互信息的混合蚁群算法及其在旅行商问题上的应用[J];东南大学学报(自然科学版);2011年03期

10 赵宜鹏;孟磊;彭承靖;;遗传算法原理与发展方向综述[J];黑龙江科技信息;2010年13期

  本文关键词：半平面集聚点群TSP几何方法及其在物流路径优化中的应用，，由笔耕文化传播整理发布。

本文编号：271514