随机时间依赖网络的K期望最短路径

首先给出了随机时间依赖网络模型，K期望是短路径问题的形式化描述，并针对公交网络推导出到达弧头结点的时刻所服从的概率密度函数，路径期望耗费的计算方法，然后，基于随机一致性假设和胡机优势的概念给出了K期望最短路径问题的理论基础和算法并证明了算法的正确性，最后，给出了公交网络的应用实例和实验结果。     

Finding Reliable Shortest Paths in Road Networks Under Uncertainty

The aim of this study is to investigate the solution algorithm for solving the problem of determining reliable shortest paths in road networks with stochastic travel times. The availability of reliable shortest paths enables travelers, in the face of travel time uncertainty, to plan their trips with a pre-specified on-time arrival probability. In this study, the reliable shortest path between origin and destination nodes is determined using a multiple-criteria shortest path approach when link travel times follow normal distributions. The dominance conditions involved in such problems are established, thereby reducing the number of generated non-dominated paths during the search processes. Two solution algorithms, multi-criteria label-setting and A* algorithms, are proposed and their complexities analyzed. Computational results using large scale networks are presented. Numerical examples using data from a real-world advanced traveller information system is also given to illustrate the applicability of the solution algorithms in practice.     

Õ(Congestion + Dilation) Hot-Potato Routing on Leveled Networks

We study packet routing problems, in which we are given a set of N packets which will be sent on preselected paths with congestion C and dilation D. For store-and-forward routing, in which nodes have buffers for packets in transit, there are routing algorithms with a performance that matches the lower bound Ω(C+D). Motivated from optical networks, we study hot-potato routing in which the nodes are bufferless. Due to the lack of buffers, in hot-potato routing the packets may be delayed more than in store-and-forward routing. An interesting question is how much is the performance of routing algorithms affected by the absence of buffers. Here, we answer this question for the class of leveled networks, in which the nodes are partitioned into L+1 distinct levels. We present a randomized hot-potato routing algorithm for leveled networks, which routes the packets in O((C + L) ln⁹ (LN)) time with high probability. For routing problems with dilation Ω(L), and where N is a polynonial in L, this bound is within polylogarithmic factors of the lower bound Ω(C+L). Our algorithm demonstrates that for such routing problems the benefit from using buffers is no more than polylogarithmic; thus, hot-potato routing is an efficient way to route packets in leveled networks. In hot-potato routing, due to the lack of buffers, the packets may not be able to remain on their preselected paths during the course of routing (while in store-and-forward routing the packets remain on their preselected paths). However, in our algorithm the actual path that each packet follows contains its original preselected path; thus the lower bound Ω(C+L) is also a lower bound for the new paths. Our algorithm is distributed, that is, routing decisions are taken locally at each node while packets are routed in the network. To our knowledge, this is the first hot-potato algorithm designed and analyzed, in terms of congestion and dilation, for leveled networks.     

Mesh网络路由算法容错性的概率分析

该文基于k-Mesh子网的概念提出了两个简单的基于局部信息和分布式的Mesh网络容错路由算法，并对其容错性进行概率分析；在每个结点具有独立的出错概率的假设条件下，推导出路由算法成功返回由正确结点组成的路径的概率．该文运用严格的数学推理，证明了Mesh网络结点出错概率只要控制在1．87％以内，则对于多达几十万个结点的Mesh网络，提出的路由算法具有99％的概率确保找到正确结点组成的路径．路由算法的时间复杂性是线性的．模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度．     

时间依赖的网络中最小时间路径算法

时间依赖的网络与传统网络模型相比更具有现实意义，具有广泛的应用领域，交通网络和通信网络可以抽象为时间依赖的网络模型，当模型中弧的工度是时间依赖的变量，最短路径问题的求解变得非常困难，早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的，因此给出限制性条件使得传统最短路径算法是有效的。该文从最短路径算法的理论基础入手，从理论上证明了传统最短路径算法，如Dijkstra算法和标号设置算法，在时间依赖的网络上不能有效地求解最短路径问题，并且，在没有任何限制性条件下，给出了时间依赖的网络模型，理论基础，求解最小时间路径的优化条件和SPTDN算法，从理论上证明了SPTDN算法的正确性，算法的实验结果是正确的，最后给出了时间依赖的网络应用实例。     

Hyperpath-based vehicle routing and scheduling method in time-varying networks for airport shuttle service

It is very significant for a reasonable vehicle routing and scheduling in city airport shuttle service to decrease operational costs and increase passenger satisfaction. Most of the existing reports for such problems assumed that the travel time was invariable. However, the ever-increasing traffic congestion often makes it variable. In this study, considering the time-varying networks, a vehicle routing and scheduling method is proposed, where the time-varying feature enables the traveler to select a direction among all the Pareto-optimal paths at each node in response to the knowledge of the time window demands. Such Pareto-optimal paths are referred to hyperpaths herein. To obtain the hyperpaths, an exact algorithm is designed in this study for addressing the bi-criteria shortest paths problem, where the travel time comes to be discontinuous time-varying. Given the techniques that generate all Pareto-optimal solutions exhibiting exponential worst-case computational complexity, embedded in the exact algorithm, a computationally efficient bound strategy is reported on the basis of passenger locations, pickup time windows and arrival time windows. As such, the vehicle routing and scheduling problem viewed as an arc selection model can be solved by a proposed heuristic algorithm combined with a dynamic programming method. A series of experiments by using the practical pickup data indicate that the proposed methods can obtain cost-saving schedules under the condition of time-varying travel times.

     

Finding the Most Reliable Strategy on Stochastic and Time-Dependent Transportation Networks: A Hypergraph Based Formulation

This study addresses the problem of determining the most reliable time-adaptive strategy on a stochastic and time-dependent transportation network. The reliability is measured as a conic combination of the mean and standard-deviation of travel time and is termed robust-cost. The stochastic time-dependent network is represented as a directed acyclic hypergraph, where the time-adaptive strategies correspond to the hyperpaths. This representation transforms the problem to that of determining the hyperpath with the least robust-cost on the constructed hypergraph. The minimum robust-cost strategy problem is difficult to solve because of the non-linear objective function. Consequently, the solution procedures commonly adopted in the literature —that are based on substrategy optimality and substrategy non-dominance —are not applicable to this problem. In this light, we propose a novel bounds-based iterative algorithm that determines the minimum robust-cost strategy on the stochastic and time-dependent networks. This algorithm needs to determine the least and K-best strategies in the second moment of travel time, for which an efficient procedure is also proposed. The algorithm is shown to be exact and exhibit parameterically polynomial behavior; computational tests were performed to demonstrate its efficiency. Further, tests showed that the minimum robust-cost strategy compromises little in terms of the mean travel time (0.2%–2.9%) —compared to least expected travel time strategy— with significant reduction in travel time variability (6.2%–29.8%).     

传感器网络定向扩散机制中梯度生成算法的研究

如何生成优化的梯度是传感器网络定向扩散中的一个关键问题,本文在分析一种基本梯度生成算法的问题基础之上,利用兴趣包的转发次数对其进行改进,设计了一种分布式的最短路径梯度生成算法.该算法极大的降低了邻居节点间建立"平行梯度"和"逆向梯度"的概率,可构建从源节点到sink节点的多条最短路径.仿真表明,改进的算法可建立更为有效的梯度,从而使得定向扩散中数据报文沿着更短的路径传输,无线传感器网络的能量利用率更高.     

Fast approximation of betweenness centrality through sampling

Betweenness centrality is a fundamental measure in social network analysis, expressing the importance or influence of individual vertices (or edges) in a network in terms of the fraction of shortest paths that pass through them. Since exact computation in large networks is prohibitively expensive, we present two efficient randomized algorithms for betweenness estimation. The algorithms are based on random sampling of shortest paths and offer probabilistic guarantees on the quality of the approximation. The first algorithm estimates the betweenness of all vertices (or edges): all approximate values are within an additive factor \(\varepsilon \in (0,1)\) from the real values, with probability at least \(1-\delta \). The second algorithm focuses on the top-K vertices (or edges) with highest betweenness and estimate their betweenness value to within a multiplicative factor \(\varepsilon \), with probability at least \(1-\delta \). This is the first algorithm that can compute such approximation for the top-K vertices (or edges). By proving upper and lower bounds to the VC-dimension of a range set associated with the problem at hand, we can bound the sample size needed to achieve the desired approximations. We obtain sample sizes that are independent from the number of vertices in the network and only depend on a characteristic quantity that we call the vertex-diameter, that is the maximum number of vertices in a shortest path. In some cases, the sample size is completely independent from any quantitative property of the graph. An extensive experimental evaluation on real and artificial networks shows that our algorithms are significantly faster and much more scalable as the number of vertices grows than other algorithms with similar approximation guarantees.     

Multicriteria Stochastic Shortest Path Problem for Electric Vehicles

This paper formulates the reliable routing of electric vehicles in stochastic networks as a multicriteria shortest path problem with travel time and charging cost components. The reliability term is defined as the probability of finishing the trip without running out of charge. The arc travel times are represented as stochastic variables, and arc energy consumption is modeled as a linear function of arc length and arc travel time. The traveler aims to minimize the generalized cost, formulated as a linear function of travel time and charging cost, subject to a minimum reliability threshold, representing the level of risk a traveler is willing to take in favor of routes with lower cost. We propose a solution algorithm based on generalized dynamic programming and show that the optimal solution may include cycles that visit at least one charging station. The properties of the proposed multicriteria shortest path problem are mathematically proved. The simulation results on randomly-generated networks show that cyclic paths are very rare, and that the generalized cost of travel is a monotone increasing function of minimum reliability threshold.