考虑转向限制的路网中最短路径算法研究

《考虑转向限制的路网中最短路径算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、考虑转向限制的路网中最短路径算法研究第1章绪论1.1研究背景近几年，物流行业快速发展，以配送货品为主要业务的快递企业、物流公司不断兴起。为了应对激烈的市场竞争，如何更快更经济地将货物送到顾客手中，成为了各个企业的发展目标，拥有精确快速的路径规划算法成为各个企业的制胜法宝。精确的路径规划依赖于对最短路问题的深入研究。最短路问题是图论和网络优化理论研究中的经典问题，在交通运输科学、地理信息科学等领域都有广泛运用，并涉及运筹学、计算机科学等相关学科。道路网络中出行路线的选取是最短路问题的一个最基本应用。现代交通路网经过长时间的不断发展与

2、逐步完善，其规模越来越大，复杂度越来越高。相比起在一般简单拓扑中最短路的求解，实际交通网络中最短路径的求解与之颇为不同。这是因为，相较于理想的、简单的拓扑网络，现实生活中的交通路网中存在有各种各样的交通管制或限制。例如：在某些路口，尽管道路是连通的，但是禁止右转或者禁止左转，或者是只允许车辆单向行驶等；再如，有一些区分时段的交通管制措施，如在城市道路中常见到的禁止大型货车在白天时段通行、某些特大型城市中禁止外埠车辆在高峰时段驶入特定道路等。这些交通管制措施的存在，使得很多直观上连通的道路路径，在实际交通行为中是不可达的。这对最短路

3、径计算有着很大的影响，增加了求解实际路网最优路径的难度。普通的最短路径算法在寻找最短路径时，只考虑路段长度或在行驶时间，不对路段之间的转向限制加以考虑和处理，从而导致搜索到的最短路径并不符合实际情形。据研究，由于道路网络中交叉路口转向限制的存在，而导致的时间延迟可占全部车辆行驶时间的17%-35%[1]；而如果在进行路径规划时不考虑转向限制，就必然导致求出的最优路线要么不实用，要么与交通规则相冲突。要解决这些问题，就需要提出专门的算法求解带有转向限制的最短路径问题。现在，交通、计算机、运筹学等领域，已有不少人研究了带转向限制的最短

4、路径问题。考虑转向限制的最短路径算法，特别是单源点到多汇点的最短路径算法得到了突飞猛进的发展。在保持图的结构不变的情况下，Gutierrez等[2]提出的基于弧标号的改进Dijkstra算法得到了带转向限制的路网中单源点到多个汇点间最短路径的精确解。........1.2考虑转向限制的图的定义交通路网是由道路、交叉口及转向限制等信息组成的一个复杂系统。在大部分的交通路网研究中，人们只考虑了道路和交叉口信息，忽略了转向限制。但由于转向限制的存在，使得许多相连的道路变得不连通。在交通路网中，最常见的转向限制有四种，禁止左转、禁止右转、

5、禁止掉头和单向通行，本文将针对这几种转向限制进行研究。转向限制是路网的重要属性，在路网中进行最优路径计算时，如果忽略转向信息，那就丢掉了路网的重要特征，这样所求得的所谓最优路线在实际的交通路网中是行不通的。从而，本文的研究都建立在考虑路网转向限制的基础上。要在计算机上计算路网中的最优路线，就必须将交通路网的相关信息转换成相应的数据，以使计算机能够识别。路网的直观结构与图结构相似，用图可以很好的表示路网信息。图中的节点表示交叉口，弧段表示道路，路段的属性作为弧的权，道路转向限制用图的连通性表示。.........第2章基于弧标号的改

6、进Dijkstra算法最短路径算法在城市交通网络中有着广泛而重要的应用。不同于一般的抽象网络，城市交通网络有着更多的限制条件，以交叉口的转向限制最为主要。据研究，由于道路网络中交叉路口转向限制的存在，而导致的时间延迟可占全部车辆行驶时间的17%-35%。因此，在交通网络路径规划中不能忽视转向限制[45,46]。Dijkstra算法是一种使用广度优先搜索解决有向图最短路径问题的经典算法，适于求解交通网络中的最短路问题[47]，但是一般的Dijkstra算法只考虑道路长度或行驶时间，而不对道路间的转向限制进行考虑。显然，这样无法搜索到

7、符合实际情形的最短路径。为了求解带转向限制的实际交通网络中的最短路径问题，国内外学者进行了大量研究。考虑转向限制的最短路径求解方法主要有三种：扩展网络法、对偶图法和弧标号算法。Vanhove等[48]对三种求解方法进行了比较，发现在转向限制超过5%的路网中，弧标号算法的性能更佳。韩刚等提出了弧标号的思想，在此之后大量文献对弧标号算法的设计进行了讨论，Gutierrez等在前人研究的基础上提出了基于弧标号的改进Dijkstra算法，该算法对路径规划中可能出现回路的问题进行了解决[49]。对于考虑转向限制的路网中单源点最短路径问题的求

8、解，基于弧标号的改进Dijkstra算法是目前最成熟的算法。该算法能确保得到顾及转向限制的交通路网规划问题的最优解，是本文所提出的双向弧标号最短路径算法和多点到多点的最短路径算法的基础。本章将对基于弧标号的改进Dijkstra算法的理论进行介绍，并