道路转向延迟的动态对偶图模型

传统的道路转向延迟对偶图表达法缺乏对交通网络时间依赖特性的考虑,不适合动态路径规划问题的求解。本文将时间因素引入到对偶图中,发展了一种动态对偶图模型,将交通路网表达为动态对偶网络,并为之定义了FIFO(先进先出）条件,推导了满足FIFO条件的动态行程计算方法,设计了时间依赖的标号设定最短路径算法。实验结果表明,利用该对偶图模型和动态对偶网络,能有效表达路网转向延迟,在以出行时间为标准的动态路径规划中,基于动态对偶网络的路径规划结果可节省约16%的出行时间。     

Dynamic algorithms for the shortest path routing problem: learning automata-based solutions.

This paper presents the first Learning Automaton-based solution to the dynamic single source shortest path problem. It involves finding the shortest path in a single-source stochastic graph topology where there are continuous probabilistic updates in the edge-weights. The algorithm is significantly more efficient than the existing solutions, and can be used to find the "statistical" shortest path tree in the "average" graph topology. It converges to this solution irrespective of whether there are new changes in edge-weights taking place or not. In such random settings, the proposed learning automata solution converges to the set of shortest paths. On the other hand, the existing algorithms will fail to exhibit such a behavior, and would recalculate the affected shortest paths after each weight-change. The important contribution of the proposed algorithm is that all the edges in a stochastic graph are not probed, and even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the shortest path graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. All the algorithms were tested in environments where edge-weights change stochastically, and where the graph topologies undergo multiple simultaneous edge-weight updates. Its superiority in terms of the average number of processed nodes, scanned edges and the time per update operation, when compared with the existing algorithms, was experimentally established. The algorithm can be applicable in domains ranging from ground transportation to aerospace, from civilian applications to military, from spatial database applications to telecommunications networking.     

Efficient Path Generation with Reduced Coordinates

Path generation is an important problem in many fields, especially robotics. One way to create a path between a source point z and a target point y inside a complex planar domain Ω is to define a non‐negative distance function d(y, z), such that following the negative gradient of d (by z) traces out such a path. This presents two challenges: (1) The mathematical challenge of defining d, such that d(y, z) has a single minimum at z = y for any fixed y, because the gradient‐descent path may otherwise terminate at a local minimum before reaching y; (2) The computational challenge of defining d, such that it can be computed efficiently. Using the concepts of harmonic measure and f‐divergence, we show how to assign a set of reduced coordinates to each point in Ω and to define a family of distance functions based on these coordinates, such that both the mathematical and the computational challenge are met. Since in practice, especially in robotics applications, the path is often restricted to follow the edges of a discrete network defined on a finite set of sites sampled from Ω, any method that works well in the continuous setting must be discretized appropriately to preserve the important properties of the continuous case. We show how to define a network connecting a finite set of sites, such that a greedy routing algorithm, which is the discrete equivalent of continuous gradient descent, based on our reduced coordinates is guaranteed to generate a path in the network between any two sites. In many cases, this network is close to a planar graph, especially if the set of sites is dense. Guaranteeing the existence of a greedy route between any two points in the graph is a significant advantage in practical applications, avoiding the complexity of other path‐planning methods, such as the shortest‐path and A* algorithms. While the paths generated by our algorithm are not the shortest possible, in practice we found that they are close to that.     

A fast path planning by path graph optimization

A fast path planning method by optimization of a path graph for both efficiency and accuracy is proposed. A conventional quadtree-based path planning approach is simple, robust, and efficient. However, it has two limitations. We propose a path graph optimization technique employing a compact mesh representation. A world space is triangulated into a base mesh and the base mesh is simplified to a compact mesh. The compact mesh representation is object-dependent; the positions of vertexes of the mesh are optimized according to the curvatures of the obstacles. The compact mesh represents the obstacles as accurately as the quadtree even though using much fewer vertexes than the quadtree. The compact mesh distributes vertexes in a free space in a balanced way by ensuring that the lengths of edges are below an edge length threshold. An optimized path graph is extracted from the compact mesh. An iterative vertex pushing method is proposed to include important obstacle boundary edges in the path graph. Dijkstra's shortest path searching algorithm is used to search the shortest path in the path graph. Experimental results show that the path planning using the optimized path graph is an order of magnitude faster than the quadtree approach while the length of the path generated by the proposed method is almost the same as that of the path generated by the quadtree.     

动态最短路径算法及其仿真

最短路径算法广泛应用在GIS(地理信息系统)、机器人探路、计算机网络等领域,经过几十年发展,有了很大进展.现在流行的最短路径算法有Dijkstra算法、A*算法,它们都建立在信息完全准确、静态路网的前提下.但现实中信息常常不准确、不完整,路途环境不断变化.当环境变化时,需要重新修改整个路径,因而速度较慢.介绍一种动态最短路径算法,初始时建立好最短路径,当环境变化时,可以只计算变化处附近局部节点,减少计算量,从而较迅速做出新的最短路径选择.最后经过仿真看出,路网中节点越多,动态最短路径算法优势越大.     

Minimal functional routes in directed graphs with dependent edges

Graphs are mathematical structures used to model a set of objects and the relations between them. One of the basic concepts of graph theory, the path, has wide real‐world applications. In classic graph models, edges ending at a node are assumed to be independent. However, many real graphs/networks can only be correctly described by considering a dependency among nodes or edges. Paths in such graphs may not be functional if the conditional dependency is ignored. In this study, we investigate the routing problem in directed graphs with dependent edges represented by general graph models as alternatives to hypergraphs. We define a minimal functional route (MFR) as a minimal set of nodes and edges that can independently perform information transfer between two given nodes, and formulate the determination of MFRs as a graph search problem. A depth‐first‐search (DFS) top‐down algorithm, an iterative integer linear programming (ILP) bottom‐up algorithm, and a subgraph‐growing bottom‐up algorithm are devised subsequently to solve this problem. Numerical experiments verify the effectiveness of the algorithms. The defined MFR problem and the proposed algorithms are expected to find many practical applications.     

Dynamic Shortest Path Monitoring in Spatial Networks

With the increasing availability of real-time traffic information, dynamic spatial networks are pervasive nowadays and path planning in dynamic spatial networks becomes an important issue. In this light, we propose and investigate a novel problem of dynamically monitoring shortest paths in spatial networks (DSPM query). When a traveler aims to a destination, his/her shortest path to the destination may change due to two reasons: 1) the travel costs of some edges have been updated and 2) the traveler deviates from the pre-planned path. Our target is to accelerate the shortest path computing in dynamic spatial networks, and we believe that this study may be useful in many mobile applications, such as route planning and recommendation, car navigation and tracking, and location-based services in general. This problem is challenging due to two reasons: 1) how to maintain and reuse the existing computation results to accelerate the following computations, and 2) how to prune the search space effectively. To overcome these challenges, filter-and-refinement paradigm is adopted. We maintain an expansion tree and define a pair of upper and lower bounds to prune the search space. A series of optimization techniques are developed to accelerate the shortest path computing. The performance of the developed methods is studied in extensive experiments based on real spatial data.     

AN APPROACH TO TRIP- AND ROUTE-PLANNING PROBLEMS

Some practical planning problems can be interpreted as set-to-set shortest path problem ( spp ), i.e., as search of a shortest path between two sets of nodes, A and B , of a graph G . A straightforward reduction of such a problem to the search of solutions for point-to-point spp s is impractical because the computational complexity is too high for a huge G . This paper presents a new approach to set-to-set spp for the case of not arbitrary A and B , but those which are represented by some nodes of an additional graph T . The graph T simulates a "geographic system" on G . Under some assumptions natural for many applications, this approach leads to a competitive algorithm for this kind of set-to-set spp . As prospective areas for this technique, two applications are discussed - the problem of route planning for a visually guided robot in a static environment, and the problem of planning a fastest trip by means of all available timetables of all kinds of transport.     

改进的k度匿名图构造算法

在社交网络中, 为防范用户隐私泄漏, 在用户数据发布前需要做匿名化处理. 针对以节点度数为背景知识的隐私攻击, 将社交网络匿名化问题建模为图的k度匿名化问题; 其主要方法是对图添加尽可能少的边或点来满足度匿名化要求, 其中要求添加边或点较少是期望尽可能保持原图结构特性. 目前, 加边类算法并不能很好地保留平均路径长度等结构特性; 加边且可加点类算法尽管能更好地保留原图结构特性, 但添加的边或点较多. 本文融合两类算法的策略提出改进算法. 新算法利用贪心法生成匿名度序列, 然后基于社区结构加边, 并且优先满足其匿名代价高于平均匿名代价的节点的匿名化要求; 若加边不能完成匿名化, 则通过加点实现图匿名化. 真实数据集上的实验结果表明新算法能更好地保留图的几种典型的结构特性, 并且添加的边或点更少.     

一种计算因特网AS拓扑的最短路径的快速算法

最短路径是因特网AS(autonomous system)拓扑的一个重要特征,AS间的路由路径一般是AS之间的最短路径.因特网服务提供商之间复杂的商业关系导致AS之间存在复杂的路由关系,从而影响AS路由路径的选择,因此在计算AS拓扑中最短路径时需要考虑AS间的路由关系.提出了一种计算AS拓扑中最短路径的算法,算法基于无向图的宽度优先最短路径算法,时间复杂度为O(nm),这里n和m分别为拓扑图中节点和边的个数.通过实验发现,与现有的计算AS拓扑最短路径的时间复杂度为O(n3)的算法相比,该算法在实现同样精确度的前提下大幅缩短了计算时间.