Shortest Path Auction Algorithm Without Contractions Using Virtual Source Concept

In this paper, the problem of finding a shortest path tree rooted at a given source node on a directed graph (SPT) is considered. A new efficient algorithm based on a primal-dual approach is presented, which improves both the convergence and the complexity of the best known auction-like algorithm. It uses the virtual source (VS) concept based on the following consideration: when a node i is visited for the first time by any algorithm which preserves verified the dual admissibility conditions, then the shortest path (SP) from the source node to i is found. Therefore, the SP from the source to the remaining nodes may be computed by considering i as a virtual source.We propose a very efficient implementation of an auction-like algorithm that uses this concept and enables us to obtain a computational cost of O(n ²), where n is the number of nodes.Numerical experimentsare reported showing that the new method outdoes previously proposed auction-like algorithms and is highly competitive with other state-of-art SP approaches.     

最短路的灵敏度分析

最短路的灵敏度分析就是讨论当网络中边的权值发生波动时，对目前的最短路带来的影响，本讨论了网络中边的权值在何种范围的变化时，极小最短路子网络不发生变化。     

Polynomial auction algorithms for shortest paths

In this paper we consider strongly polynomial variations of the auction algorithm for the single origin/many destinations shortest path problem. These variations are based on the idea of graph reduction, that is, deleting unnecessary arcs of the graph by using certain bounds naturally obtained in the course of the algorithm. We study the structure of the reduced graph and we exploit this structure to obtain algorithms withO (n min{m, n logn}) andO(n ²) running time. Our computational experiments show that these algorithms outperform their closest competitors on randomly generated dense all destinations problems, and on a broad variety of few destination problems.Research supported by NSF under Grant No. DDM-8903385, by the ARO under Grant DAAL03-86-K-0171, by a CNR-GNIM grant, and by a Fullbright grant     

结点有约束的交通网络最短路径模型

结点有约束的网络是一类特殊的网络，如具有禁止通行限制信息的交通路网等，由于最短路径的求解是有后效性的，经典的Dijkstra算法等不能直接用来求解该问题，本文提出了一种结点有约束的交通网络最短路径建模方法，该方法所建模型为一般网络模型，可用任一传统高效的算法求其最短路径，从根本上降低了问题的复杂性，为很好地解决交通、通信等领域中的此类问题提供了有益的方法。     

Resource Constrained Shortest Path Problems in Path Planning for Fleet Management

In the management and control of a vehicle fleet on a road network, the problem arises of finding the best route in relation to the mission of the fleet and to the typology of freight or users. Sometimes the route has to be adapted not only to current traffic conditions, but also to the physical, geometric and functional attributes of the roads, related to their urban location and environmental characteristics. This problem is approached here through an extension of the classic Shortest Path problem, named Resource Constrained Shortest Path problem (RCSP), where the resources are related to the road link attributes, assumed as relevant to the specific planning problem. A classification scheme of these attributes is first proposed and RCSP is described and reviewed. Next, a General Resource Constrained Shortest Path problem (GRCSP) is defined, which can be found in all cases where it is necessary to plan, statically or dynamically, the path of a vehicle and to respect a set of constraints expressed in terms of parameters and indices associated with the roads on the network. For this general problem a model has been formulated and a Branch and Cut solution approach is proposed. Computational results obtained on test and real networks during the experimentation of a fleet with low emission vehicles are also given. This revised version was published online in August 2006 with corrections to the Cover Date.     

模糊最短路的一种算法

模糊最短路问题在许多领域有着广泛的应用,研究这一问题具有重要意义。根据多准则决策理论求非被支配路径集合,求最大效用模糊最短路以及利用模糊数排序方法求模糊最短路是常用的三种研究方法,本文利用OERI排序原理,使网络模糊边长具有线性可加性,对具有三角模糊数边权的网络给出了一种标号算法,该算法简单高效,且易于在计算机上实现,算法的时间复杂度为O(n^2)。     

具有最大能量的最短路

本文讨论一类新的赋权图 ,称为双权图 ,G=( V,E;w,c) ,w称为权函数 ,c为容量函数 .并给出了 G中两顶点 u与 v之间具有最大能量的最短路的算法 .     

Shortest Path Problem on a Network with Imprecise Edge Weight

A network with its arc lengths as imprecise number, instead of a real number, namely, interval number and triangular fuzzy number is considered here. Existing ideas on addition and comparison between two imprecise numbers of same type are introduced. To obtain a fuzzy shortest path from a source vertex to all other vertices, a common algorithm is developed which works well on both types of imprecise numbers under consideration. In the proposed algorithm, a decision-maker is to negotiate with the obtained fuzzy shortest paths according to his/her view only when the means are same but the widths are different of the obtained paths. Otherwise, a fuzzy optimal path is obtained to which the decision-maker always satisfies with different grades of satisfaction. All pairs fuzzy shortest paths can be found by repeated use of the proposed algorithm.     

一种最短路问题的遗传算法求解

针对最短路径问题,在分析传统遗传算法不足的基础上提出了变长染色体遗传算法(ClvGA),详细论叙了其编码、基因插入(删除、变异)算子的设计,最后通过两个网络对ClvGA进行了实验仿真,结果表明:该方法在最短路径问题上表现出较好的鲁棒性.     

Auction algorithms for network flow problems: A tutorial introduction

This paper surveys a new and comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and transhipment problems. The prototype method, from which the other algorithms can be derived, is the auction algorithm for the assignment problem. This is an intuitive method that operates like a rel auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from the cost improvement idea that underlies primal simplex and dual ascent methods; at any one iteration, they may deteriorate both the primal and the dual cost. Auction algorithms perform very well for several important types of problems, both in theory and in practice, and they are also well suited for parallel computation.     

拆边法求最短路径

本文利用局部比较法 ,在图中定义子图、无效路径、以及可去边 .利用推导的有关定理 ,拆去可去边 ,利用最短路径相同的等价性 ,达到化简图 ,从而求出最短路径     

On the Generalized Elementary Shortest Path Problem: A heuristic approach

We introduce the generalized elementary shortest path problem (GESPP) where in addition to the features of the shortest path problem, nodes belong to predefined non-disjoint clusters. Each cluster is associated to a profit to the cost function, obtained if at least one element in the cluster appears in the path. Several applications can be considered as school bus routing, pricing problems, or telecommunication network design. Thus, depending on the case, clusters could be interpreted as groups of nodes with linking features as, for example, being easily reachable from each other, or some kind of coverage guarantee. We compare the GESPP to similar problems in the literature and we propose a two-phase heuristic algorithm for graphs including negative cycles. Tests on random instances with up to 100 nodes show an average gap of 0.3% to the best known solutions computed in 2.8s in average.     

Soft Constraint Logic Programming and Generalized Shortest Path Problems

In this paper we study the relationship between Constraint Programming (CP) and Shortest Path (SP) problems. In particular, we show that classical, multicriteria, partially ordered, and modality-based SP problems can be naturally modeled and solved within the Soft Constraint Logic Programming (SCLP) framework, where logic programming is coupled with soft constraints. In this way we provide this large class of SP problems with a high-level and declarative linguistic support whose semantics takes care of both finding the cost of the shortest path(s) and also of actually finding the path(s). On the other hand, some efficient algorithms for certain classes of SP problems can be exploited to provide some classes of SCLP programs with an efficient way to compute their semantics.     

Efficient algorithms for the 2-Way Multi Modal Shortest Path Problem

We consider the 2-Way Multi Modal Shortest Path Problem (2WMMSPP). Its goal is to find two multi modal paths with total minimal cost, an outgoing path and a return path. The main difficulty lies in the fact that if a private car or bicycle is used during the outgoing path, it has to be picked up during the return path. The shortest return path is typically not equal to the shortest outgoing path as traffic conditions and timetables of public transportation vary throughout the day. In this paper we propose an efficient algorithm based on bi-directional search and provide experimental results on a realistic multi modal transportation network.     

基于五次Hermite插值的机械臂最短路径规划研究

为了保证机械臂高效率和平稳的运行,机械臂运动轨迹曲线一般需要具有C~2连续性,且运动路径具有最优性.采用五次Hermite插值函数方法,构造机械臂的运动轨迹.求解最优化问题得到连接点处二阶导数信息,构造满足上述条件的曲线轨迹,最后给出了两个实例来验证该方法的有效性.     

Nonadditive Shortest Paths: Subproblems in Multi-Agent Competitive Network Models

A variety of different multi-agent (competitive) network models have been described in the literature. Computational techniques for solving such models often involve the iterative solution of shortest path subproblems. Unfortunately, the most theoretically interesting models involve nonlinear cost or utility functions and they give rise to nonadditive shortest path subproblems. This paper both describes some basic existence and uniqueness results for these subproblems and develops a heuristic for solving them.     

Label Correcting Methods to Solve Multicriteria Shortest Path Problems

In this paper, we deal with the solution of the multicriteria shortest path problem. In particular, we present a class of labeling methods to generate the entire set of Pareto-optimal path-length vectors from an origin node s to all other nodes in a multicriteria network. The proposed methods are supported theoretically by the principle of optimality and they are defined on the basis of various innovative node and label selection strategies.Computational results comparing the proposed methods to state-of-the-art approaches to solve the problem considered are also reported. They indicate that our methods are competitive in general; in several cases, they outperform all the other codes.     

Algorithms for time-dependent bicriteria shortest path problems

In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature. After reviewing relevant literature we develop a new algorithm for the TdBiSP with non-negative data. Numerical tests show the superiority of our algorithm compared with an existing algorithm in the literature. Furthermore, we discuss algorithms for the TdBiSP with negative travel times and costs.     

用矩阵和积求最短路的一种新算法

先定义了矩阵和积的概念和运算,在求最短路中,这种方法和线性代数中的矩阵运算相似,通过这种方法,把求最短路转化为矩阵的运算,计算简便,有效.     

Some observations about the extreme points of the Generalized Cardinality-Constrained Shortest Path Problem polytope

The Generalized Cardinality-Constrained Shortest Path Problem (GCCSPP) consists in finding the minimum cost path in a digraph, using at most r arcs in a subset F of the arc set. We propose an algebraic characterization of the extreme points of the associated polytope, and then we show that it is equivalent to the geometric one, obtained extending to the GCCSPP some known results for the cardinality-constrained shortest path problem.