基于 GPS 跟踪的大数据出租车智能行车方向服务课题
Proposal presentation (due within 8-10 weeks)
In a form of presentation
Includes:
Your understanding of the project
What have you done to prepare for the project
Your roadmap
understanding of the project：（课题的目的意义）
What have you done to prepare for the project（目前所了解的算法）
Your roadmap（研究路线图）
课题：基于 GPS 跟踪的大数据出租车智能行车方向服务
目的：根据用户查询找出实际速度最快的行车路线
变量：出发点，终点，时间
考虑的因素：物理可达路线，车流拥堵状况，司机本身因素
每段路径设置一个权值反映当前路径动态交通状况，若交通状况良好（行车平均时间少、不拥堵）则设定权值大。用数据实时更新权值。自动选择当前从出发点到目的地的最优路径（平均最大权值路径）。
要求根据提供的实时数据计算出各个路段中的通行平均时间，并且判断出交通状况。（红色代表拥堵、黄色代表较为阻塞、绿色代表畅通）。
图3
图2
图一
我们对于这个项目的理解如下：从天安门到清华大学有很多条路径，用传统Dijkstra算法可以算出基于距离权值的最短路径。
但是当路况发生变化时例如某一路段发生拥堵时，是的该条路径的平均总权值发生变化，，则需要改变行车路径选取一条当前最短路径。(如图1、2、3)
我们做了哪些工作：
Dijkstra 算法是解决关于加权图（权为非负数）的单源最短路径问题的一种贪心算法，它按照路径长度增加的顺序找出从某一源结点到所有其他结点的最短路径。Dijkstra 算法将网络结点分为未标记结点、临时标记结点和永久标记结点 3 种类型。网络中所有结点首先初始化为未标记结点，在搜索过程中和最短路径结点相连通的结点为临时标记结点，每一次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，直至找到目标结点或者所有结点都成为永久标记结点才结束算法。Dijkstra算法的时间复杂度为O（n2）（动画演示）
传统 Dijkstra 算法比较简单，容易实现，但是在应用中其存在的不足非常
明显，表现在以下几个方面：（图上分析）
- 不适合大规模网络的最短路径计算。在路网模型大，结点数目多的系统（如车辆导航系统）中，若采用传统 Dijkstra 算法计算最短路径无论从存储空间上还是从计算时间上都会相当庞大，这将直接影响系统的性能；
(2)算法采用邻接矩阵描述网络结点和弧的特征，存在大量空间冗余，增加路径计算判断次数，不适合存储结点较多的道路网络。而且邻接矩阵难以全面地描述真实路网信息，如结点属性信息及弧的属性信息等；
(3)设 dist 数组记录临时标记结点的最短路径长度，搜索过程应选择最小的 dist[i]加入到 S 中，这个选择没有考虑终点的位置和方向，是贪心策略的体现，即在每个阶段都保持局部最优，而把各个阶段结果综合起来，总的结果可能不是最优。
我们将要做的内容：
最短路径的实时性研究需要解决两个关键性问题：一是采用哪种最短路径算法以及怎样优化算法使其更符合实际的路网计算；二是实时交通信息的采集、传输、发布，以及在算法中的应用。
(1)详细分析和讨论最短路径搜索策略和常见的最短路径算法；
(2)对 Dijkstra 算法进行深入分析，针对该算法在应用中存在的不足，设计一种基于 Dijkstra 算法的最优路径搜索方法：提出了新的区域限定模型，并在此限定区域内实现存储结构的优化和含有启发式信息的搜索策略。其中，区域限定是路径搜索的前提，它避免了众多无用结点参与计算带来的时间和空间的浪费；在限定区域的基础上对存储结构进行优化可以有效的减少存储空间（例如利用二叉堆优化）；启发式搜索策略使算法快速趋于目标结点，提高了执行效率。这三方面的优化是紧密联系，缺一不可的；（传统 Dijkstra 算法采用了盲目搜索策略，不考虑方向位置等任何启发信息。使用带有启发信息的权值计算函数进行计算（趋向方向对权值影响大），可使算法快速地趋于终点，以提高算法的运行效率。）
区域限定
(3)研究路网权值确定方法，设计了新的路网权值计算模型（将实时数据变化加入到权值计算模型中去）；
编号 日期 时间 经纬度
(4)这种优化算法的实现与分析
(5)综合三方面的优化于一体进行交通路网试验；