详情

原文传递分层路径诱导算法与策略研究

论文题名：	分层路径诱导算法与策略研究
关键词：	智能交通系统;道路网;路径诱导;分层算法;数据结构
摘要：	在智能交通系统中的路径诱导子系统中，查询最优路径是其中的一项基本的功能。许多研究者已经从理论上和实验上对该问题进行了广泛的研究。目前为止，道路网中的路径诱导算法主要有平面算法和分层算法两大类。平面算法是指如Dijkstra算法、A算法和A<'>算法等的图搜索算法，而分层算法由平面算法和一组在层次数据结构上进行推理的规则组成。在分层算法的每一层可使用某种平面算法，而推理规则将规定如何运用层次数据结构。与平面算法相比，分层算法通常在搜索一条满意的路径时具有较好的性能，这是因为分层数据结构使得某个搜索过程在子网中进行，子网的小数据规模可使得搜索过程高效执行。而随着问题规模的变大，平面算法却会较快地产生“组合爆炸”问题。已有的最近E节点分层算法在提升低层节点时不够准确，而最佳E节点分层算法又效率太低。为此，本文提出了一种分层A枣算法。其实质是在低层向高层过渡时采用启发式定向搜索的方法确定E节点，而在高层路网中搜索时采用A<'>算法。目的是在求解速度较快的前提下，搜索出相对可靠的E节点。西安市道路网的测试数据表明，分层A<'>算法的平均求解效率是Diikstra算法的75.48倍，平均路径长度与平均最短路径长度的偏差仅为0.865km，平均高层路径比重达到69.7％。通过比较分层A<'>算法、最近E节点分层算法和Diikstra算法的性能，笔者认为分层A<'*>算法具有较好的实用性。另外，在中心式路径诱导系统中，计算中心需要传送必要的地图数据给车辆。为了缩短计算中心与车辆之间的数据传送时间，本文提出并实现了一种TMSCR数据准备模型，即在包含起止点的一个网格集合的外接矩形区域中，提取起点网格内的低层路段、终点网格内的低层路段和所有高层路段的并集，发送给车辆。实验表明，实现该模型的时间代价很小，TMSCR模型与传统的方法相比，可以大大节省通信时间，从而为车辆提供优质的服务。最后，笔者基于MapXtreme2005 6.6和.net 2005设计并实现了西安市路径查询原型系统。该系统由三部分组成，即空间数据库、核心算法层和用户界面。路径求解模块是一个DLL文件，是通过建立VC++类库项目而生成的。由于MapXtreme2005 6.6只提供了VB和VC＃两种模板，所以本文采用VB应用程序来调用C++编写的：DLL模块完成了系统的实现。
作者：	李建元
专业：	计算机软件与理论
导师：	师军
授予学位：	硕士
授予学位单位：	陕西师范大学
学位年度：	2007
正文语种：	中文