基于实时道路的路径优化算法设计与实现

论文摘要

随着对物流配送路径优化问题研究的不断深入,各种路径优化算法在物流领域已经有了广泛且成熟的应用。但是传统的路径优化算法都是基于静态信息的计算,现今城市路面交通状况每况愈下,传统的路径优化算法已经无法满足目前路径优化的需求。随着全球定位系统GPS的发展以及各种路况采集技术的成熟,以往无法收集到的实时交通数据现在已经完全可以作为路径优化的全新计算参数,为基于实时道路的路径优化提供了可能。今后随着3G网络和WiFi的普及,信息的传递将更加便捷,在这样的背景下如何利用城市实时道路信息来进一步规划合理的行驶路径已经成为目前物流领域急需解决的课题。本文提出了将传统的解决车辆路径问题(Vehicle Routing Problem,VRP)的蚁群算法与解决最短路径问题的A*算法结合成为两阶段算法,以求解“次优快速解”的思想对蚁群算法进行了高效实现,将蚁群算法的输出作为A*算法的输入,对A*算法进行了重点改进,将实时道路信息作为一个新的计算维度融入A*算法,提出了基于时间换算和基于路程换算的A*算法,同时也提出了A*算法结点的预处理方法。本文开发了一套基于实时道路信息的路径优化系统,能够适用于指定配送模型下的路径优化,使用真实的上海市道路交通实时路况数据对算法进行了验证并得到比较满意的优化结果。本文首先分析了相关的路径优化算法和城市实时路况采集技术;接着,本文提出了基于实时道路的路径优化解决框架,详细阐述了该模型的各个关键部分;然后,本文设计了高效的蚁群算法和改进的A*算法作为核心算法,同时在后台数据库存放了真实的道路路况数据作为计算参数;最后在系统的实现部分,本文使用J2EE相关技术和ORACLE 10g数据库完成了基于MVC架构的系统实现,并使用上海市电子地图与MapXtreme完成了基于GIS的结果显示。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 研究背景和意义
• 1.2 国内外研究现状
• 1.3 研究内容与取得成果
• 1.3.1 研究内容与所做的工作
• 1.3.2 本文的创新之处
• 1.4 论文结构
• 第二章 基于实时道路的路径优化技术分析
• 2.1 路径优化问题研究综述
• 2.1.1 VRP 问题及蚁群算法
• 2.1.2 最短路径算法
• 2.2 现有研究存在的问题
• 2.2.1 算法缺陷
• 2.2.2 模型缺陷
• 2.3 本文的研究思路
• 2.4 相关技术简介
• 2.4.1 全球定位系统GPS
• 2.4.2 道路信息采集技术
• 2.4.3 地理信息系统GIS
• 第三章 实时路况采集技术研究
• 3.1 城市高架道路路况采集
• 3.2 基于浮动车的实时路况采集技术研究
• 3.2.1 浮动车选型
• 3.2.2 GPS 经纬度坐标与GIS 电子地图坐标转换
• 3.2.3 采样点定位计算
• 3.3 实时路况的计算
• 3.4 本章小结
• 第四章 基于实时道路的路径优化算法设计
• 4.1 基于实时道路的路径优化解决框架
• 4.2 高效的蚁群算法实现
• 4.3 改进的A*算法解决实时道路的路径优化
• 4.3.1 经典A*算法的局限性
• 4.3.2 基于时间换算的A*算法
• 4.3.3 基于路程换算的A*算法
• 4.3.4 加入启发因子的改进A*算法
• 4.3.5 A*算法的预处理
• 4.3.6 改进的A*算法性能与测试比较
• 4.4 本章小结
• 第五章 系统设计与实现
• 5.1 系统功能模块介绍
• 5.2 系统架构设计
• 5.3 数据库设计
• 5.4 系统演示
• 第六章 总结与展望
• 6.1 本文总结
• 6.2 未来展望
• 参考文献
• 附录一 浮动车采集原始数据
• 附录二 线圈采集数据
• 附录三 电子地图路面数据
• 致谢
• 攻读硕士学位期间已发表或录用的论文