导航软件之公交系统导航和TSP问题的研究与实现

摘要

城市公共交通是城市交通的不可缺的一部分，它也是各个政府大力发展的对象。但是随着城市建设的飞速发展，人口的迅速增长，如何选择合理的理想的出行方式是公众都比较关心的问题。随着计算机技术的发展，公交查询系统以C/S或者B/S的方式呈现给出行的人。因此导航软件或者web公交查询系统成为了人们首要的选择。
　　在路径导航中旅行商问题又是一个非常经典的问题。一般在解决TSP（旅行商问题）问题时，我们应该先对其进行预处理，并且把详细的坐标道路图抽象成无向完全图，就是把旅行商问题抽象成一条回路(Hamilton)，接着利用神经网络算法和蚁群算法来求解此问题，最后通过实验证明了想法的可实现性和高效性。本文在详细的介绍BP神经网络及其算法和蚁群算法的特点、原理后，具体的讲解了目前比较经典的BP算法和蚁群算法和它们的主要成果，也用联系和比较的方式说明了这些方法的优点和缺点及其应用，最后提出了较好的BP网络和蚁群算法并应用于解决TSP问题。
　　主要工作如下：
　　①针对传统的Dijkstra算法应用于城市公交导航的很多不适合，本文提出了站点归并和基于此的公交线路段归并，并充分考虑了人们的出行方式，主要包括:时间最短，地铁优先，步行最短。
　　②实现了导航软件之公交导航该功能，并给出部分代码。
　　③提出了基于L-M算法的改进BP神经网络，然后根据实际对该算法的参数进行讨论。
　　④建立基于改进的BP网络的交通预测系统。
　　⑤把预测结果反映给改进的蚁群算法，并计算出结果。
　　所以根据城市交通问题，本文在城市公共交通和TSP这两方面进行了研究。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1研究背景

1.2国内外发展现状

1.3研究意义

1.4城市交通拥挤原因

1.5本文论文结构

第二章 神经网络

2.1神经网络基础知识

2.2 BP神经网络

2.3网络性能分析

2.4几种改进的BP算法

2.5本章小结

第三章 蚁群算法

3.1蚂蚁生物特征和种群行为

3.2蚁群算法基础知识

3.3蚁群算法特点

3.4算法的实现

3.5算法流程图

3.6本章小结

第四章 一种改进的TSP解决方案

4.1改进的BP算法

4.2改进的BP网络在道路拥堵预测系统中的应用

4.3结果

4.4改进的蚁群算法

4.5新的改进的蚁群算法

4.6本章小结

第五章 导航软件

5.1基础理论

5.2公交线路网模型

5.3公交数据分析

5.4公交网络建模

5.5公交路径算法的设计与实现

5.6算法流程图

5.7导航软件在VS2005中的实现

5.8本章小结

第六章 总结与展望

参考文献

致谢