面向城市交通的简化路网模型及路径规划问题的研究

随着城市中交通堵塞情况的越来越严重,出行者对简洁、高效的路径规划算法的要求日益迫切。如何根据现实的道路交通状况构建合理而有效的路网模型,并在路网模型的基础上设计出满足出行者需求的简捷有效的路径规划有着非常重要的意义。在实际应用中,比较常见的路网模型都考虑了比较复杂的交通限制信息(例如:路宽、车流量、由于施工、交通事故等对道路进行限行的规定),而路径规划的目标也会在路网模型的基础上根据出行者的要求进行多目标或单目标的规划。 目前,国内外研究提出的道路交通网络模型比较多,包括各种复杂的静态路网模型、动态路网模型、以及实时路网模型等。这些复杂路网模型虽然在一定程度上可以更好地描述现实交通路况,但这些模型考虑的因素普遍比较繁多,比如为了计算交叉口的时延就考虑排队等待的长度、环形道的长度、交叉口的车流量等,另外还有考虑动态交通流以及红绿和交叉口延时等,因此导致路径规划算法的设计过于繁琐,不仅计算效率显著下降,而且所需道路信息难以实时精确地采集,从而不能很好地响应城市内出行者的导航要求。针对这种情况,本文重点研究了如何在保证路径规划效果的前题下,尽可能考虑较少的因素来简化路网模型,更好地响应城市出行者的导航要求。论文研究主要贡献如下: ①首先,考虑城市交通的基本特点,研究提出了一种简洁实用的的简化静态路网模型。并在该模型的基础上设计了改进的Dijkstra算法,即S-Dijkstra算法,来解决城市路径规划问题。该模型仅要求采集很少的道路通行信息,却能简接地反映道路转弯延时、通行速度、红绿灯和斑马线等复杂因素对车辆通行时间的间接影响,具有简单实用的特点。 ②进而,通过按照城市交通动态变化的特殊规律,将一个工作日内道路通行时段划分为不同的时间段,对上述简化模型进行扩展,构建了一种基于时间段划分的简化动态路网模型。并给出了能在该模型上正常运行的改进Dijkstra算法,即D-Dijkstra算法,来解决适合城市内汽车导航的动态路径规划问题。 ③最后,本文通过将限定搜索的矩形区域法和分层方法结合运用到上述提出的路径规划算法中,设计出了缩小搜索空间的高效的Dijkstra算法,新方法通过对路径搜索空间的降维,能显著提高导航算法的运行效率。 本文提出的简化路网模型,所需数据采集简化,容易实施,算法简单高效,能够满足于城市路径导航的实际需要,对相关研究开发具有较好的参考价值。