1.1  课题研究内容

我的毕业设计课题是出租车动态路径规划。该系统采用了Dijkstra算法挑选最短路径，利用数据库访问技术实现道路信息的实时更新。实现了动态实时刷新数据库中存储的道路信息，挑选出从出发地和目的地之间的最短路径，并且能够根据动态更新的道路信息实时更新行车路线。

    静态最短路径规划算法在现代的城市交通道路中显现出很多的问题，在实践中，道路网络特征可能会随时发生变化，静态路径规划基于其自身特点根本无法满足道路网络中实时性这一特征。动态路径规划则可以对传统的静态路径不能解决的问题有所作为，它不仅可以类似于传统的出租车的手台或者广播，为司机提供较为准确实时的交通路况信息，让司机及时了解路况信息，同时还可以根据交通道路拥堵情况规划出最合理的行车路线，从而为那些对于城市交通道路不熟悉的司机提供便捷的行车路线，从而避免了大量的出行者盲目的选择道路而浪费时间。同时，在出租车行车过程中，也在不断根据前进的方向查询动态更新的数据实时选择最佳行车路线，避免遇到车流量较多拥挤的情况。源:自~优尔-·论`文'网·www.youerw.com/

1.2  课题研发的意义

研究出租车动态路径规划问题，可以解决交通趋势预测问题，建立可以高效行驶的行车路线模型，能够为出租车载客时提供道路状况最为通畅，行车时间最短的行车路线，最大限度的增加收益。

这次的毕业设计，是我在大学本科阶段完成的最后一个课程设计，这是对我大学四年学习成果的一个综合考察。在导师的指导下，经过这几个月的学习和钻研，将这些年来所学到的知识都融入其中，并对未接触过的知识有了新的了解，关键是学到了方法。这个课题主要涉及的开发工具是SQL Server 2008和Visual Studio 2010，充分利用数据库强大的数据存储、处理功能，对道路信息进行实时刷新，并利用动态最短路径算法挑选合理路径。

这次毕业设计让我对算法设计有了更深层次的了解，对我以后的工作也有很大的帮助。算法的研究最初可以追溯到上世纪60年代初期，在当时，计算机的可用资源十分有限，这也促进了有效算法的设计，自此以后算法研究在计算机领域广泛开展，出现了大量的有效算法，一个好的算法可以在很大程度上提高程序的运行效率。例如本课题所用到的Dijkstra算法提高了带权值的有向图的最短路径，极大的减少了路径搜索所需的时间，提高了程序的运行效率。

本系统基本能够实现所需完成的基本功能，并且具有较好的交互性，操作较为简单，具有一定的实用性，可以运用到现有的GPS导航系统中，完善其功能。

2  路径规划算法文献综述

2.1  路径规划算法

传统的最短路径规划算法实现的是缩短行程，如早期的基于限制条件的深度优先搜索算法到后来的Dijkstra算法等，在这些算法的设计过程中仅考虑了路径长度这一静态信息，以力求得到最短路径来达到节约时间的目的。

Dijkstra算法是典型的最短路径算法，这个算法是1959年幼荷兰计算机科学教授Dijkstra发现的，它可用于计算从一个起始节点到其他任意节点的最短路径，可适用于带权重的有向图或无向图，是现代智能交通系统使用最普遍的一种规划算法。算法的主要思想是广度优先搜索，以起始点为中心向外层层扩展，直至找到最终的目标节点，能够遍历到图中（有向图或无向图）的所有节点，正因如此，由于其要遍历途中所有节点，所以其运行效率会比较低。但是由于该算法能够保证得到最优解，所以其应用性还是十分广泛的