用于最短路算法的公交网络模型构建

公共交通线路网络的复杂化使乘客难于选择最优的出行线路。用于最短路算法的公交网络模型,解决了有向图难以承载票价和换乘这两个出行要素的问题,有效地把公交出行要素包含在弧中,使得最短路算法可以直接根据这些要素搜索最优出行方案。     

重大灾害条件下基于GIS的最短路径改进算法

利用经典的Dijkstra算法,对重大灾害条件下Dijkstra算法进行了改进,构建了惩罚因子函数,结合GIS软件二次开发模块,通过Visual C++6.0实现了复杂网络的分析功能。分析了重大灾害条件下节点数量对于道路可靠性以及最优路径选取的影响,综合考虑距离、行程时间以及节点数量因素,证明了改进Dijkstra算法对于最优路径选择的优越性。分析结果表明:利用改进Dijkstra算法、经典Dijkstra算法计算出的路径节点数分别为31、59,行程时间基本相同。可见,改进算法能有效减少疏散路径中的节点数量,降低车辆在节点处的延误损失和风险。     

綠色節能最佳化運輸路徑之規劃

隨著經濟發展,自然環境惡化程度持續加深,肇因為小客車數量日益增加,於是近年來綠色交通概念被大力提倡,如能以最佳節能路徑為運輸進行改造,將能為綠色環保盡一份心力。以最短路徑演算法（Dijkastra＇s Algorithm）為基礎,撰寫出最佳節能路徑之演算法,即每台車皆能以最低油耗知目標行駛,並將其與最短距離和最少旅行之路徑進行結果比較,結果發現該最佳節能路徑相較另兩條目標路徑時最能節省燃油消耗,此成果可提供小客車車主進行最佳節能路徑之規劃。另外也以路網均衡之概念進行交通量指派,使用者均衡和系統均衡分別於時間成本和油耗成本目標下之比較。     

基于可视图和A~＊算法的连续模型路径搜索

针对交通枢纽仿真领域中行人最短路径搜索环境建模难的问题,提出一种基于可视图的连续拓扑模型最短路径搜索策略,通过在连续模型下建立可视图并使用A*算法搜索出一条适合行人通行的最短路径,将改进的可视图算法和A*算法结合,降低连续模型中自动选择路径复杂度和扩展结点数目.将该算法应用于城市综合客运枢纽功能与结构数值实验系统对行人对象进行路径搜索导航,实验结果证明此算法可行且具有更高的效率和通用性.     

Bicriterion shortest path problem with a general nonadditive cost

A bicriterion shortest path problem with a general nonadditive cost seeks to optimize a combination of two path costs, one of which is evaluated by a nonlinear function. This paper first identifies a number of emerging transportation applications for which such a shortest path problem might be considered a core subproblem. We propose to first approximate the general nonlinear cost function with a piecewise linear counterpart, and then solve each linear subproblem sequentially. A specialized algorithm is developed to solve the subproblems, which makes use of the efficient path set (or the convex hull) to update upper and lower bounds of the original problem. Conditions under which the solution to a subproblem must belong to the efficient path set are specified. Accordingly, we show that the optimal path must be efficient if the nonlinear cost function is concave. If the optimal path to a subproblem is not efficient, partial path enumeration, implemented using a simple K-shortest path ranking procedure, is conducted to close the gap. The proposed algorithm includes strategies aiming to expedite path enumeration by using upper bounds derived from the efficient path set. Numerical experiments are conducted to demonstrate correctness and effectiveness of the proposed algorithm.     

An eco-routing model considering microscopic vehicle operating conditions

The eco-routing problem concerned in this paper addresses the optimal route choice of eco-drivers who aim to meet an emission standard imposed by regulators, while trying to find the path with the minimum total operating cost, which consists of both travel time and fuel costs. The paper first develops fuel consumption and greenhouse gas emissions estimation models that link emission rates to a vehicle’s physical and operational properties. Unlike most studies in the literature, the emission model developed in this paper retains as many microscopic characteristics as feasible in the context of route planning. Specifically, it is able to approximate the impacts of major acceleration events associated with link changes and intersection idling, and yet does not require detailed acceleration data as inputs. The proposed eco-routing model also explicitly captures delays at intersections and the emissions associated with them. Using a simple probabilistic model, the impacts of different turning movements on eco-routing are incorporated. The proposed model is formulated as a constrained shortest path problem and solved by off-the-shelf solvers. Numerical experiments confirm that vehicle characteristics, especially weight and engine displacement, may influence eco-routing. The results also suggest that ignoring the effects of turning movements and acceleration may lead to sub-optimal routes for eco-drivers.     

城市道路网最短路径启发算法研究

从城市道路网络的实际特点出发,对城市电子地图的道路网进行网络分析,将最佳路径搜索问题转化为图论中的最短路径搜索问题,通过对最短路径搜索算法的分析,提出了一种求解城市道路网两点间最短路径的算法。该算法主要对Dijkistra算法的搜索方法进行改进,根据两点间直线距离最短这一原理,运用待扩展节点与终止节点间的直线距离这一启发信息,使搜索沿着某个最有希望的路径进行下去,大大减少了搜索范围,提高了路径搜索的速度,具有重要的实践意义。     

基于混沌蚁群算法的最短路径选择研究

如何解决最短路径选择问题一直是城市交通流诱导系统的关键之一.基于群体仿生理论的蚁群算法是解决此问题的一种方法,针对采用蚁群算法进行最短路径选择时易出现的陷入局部最优解问题,引入混沌理论,采用混沌蚁群算法利用混沌初始化进行改善个体质量和利用混沌扰动避免在蚁群算法搜索过程中陷入局部极值,同时降低了蚁群算法的时间复杂度,从而更好的解决了最短路径选择问题.     

Application of Auction Algorithm for Shortest Paths to Traffic Assignment

Auction algorithm is a new and simple algorithm for finding shortest paths in a directed graph proposed by Prof. Bertsekas, whose application has been extended to solve a variety of linear network flow problems. In this paper, auction algorithm for shortest paths is introduced and its characteristics are analyzed. The paper compares the auction algorithm with other algorithms widely used such as label-setting algorithm and label-correcting algorithm. The auction algorithm is particularly applicable to parallel computation and to the solution of a large-scale sparse network, which precisely meets the requirements of the traffic assignment. The algorithm is easy to program. Through a variety of measures the basic algorithm can be improved and speeded up and the computation speed can be increased by several times. The auction algorithm can be adopted in various traffic assignment methods. It can be used efficiently in the case of multiple origins and a single destination, and a single origin and multiple destinations. Different origin sets and destination sets are determined in accordance with the requirement of the traffic assignment. It is not required any more to find the shortest paths connecting any node pairs, so a lot of computation can be avoided and the computing time can be reduced by the use of the auction algorithm in the traffic assignment. Auction algorithms can thus be broadly applied in the transportation fields.     

路线控制点距公路中线最短距离自动求解算法研究

讨论了公路选线时与平面线形设计有关的路线控制点距公路中线最短距离的计算机自动求解算法问题，提出了求解的新算法——步长压缩摆动趋近法。该算法在各种平曲线类型情况下均是可行的。