Object modeling and path computation for multimodal travel systems

This paper describes a multimodal travel system (MTS) designed to address the needs of a variety of demand-responsive transport. An origin–destination (O–D) trip in transportation network can be accomplished by using multiple modes. In urban network passengers may boarding buses or metros to go from one place to another, and modes as autobus or trains are used by passengers to travel between cities. The work focuses on the network object modeling and multimodal shortest path algorithm. A solution to the problem of long-run planning of transit on multimodal network has been implemented and tested. The work presents the general results found, and the proposed algorithm recognizes the set of constraints related to the time schedule and the sequence of used modes in a O–D trip. The aim is to provide a tool for detecting the facilities of using different travel modes through a transportation network. Routings may include distinct combination of rail, and route. Geographic Information Systems (GIS) were invaluable in the cost-effective construction and maintenance of this work and the subsequent validation of mode sequences and paths selections. Attention is devoted to the multimodal path operator as well as to the use of GIS-transit planning.     

Fuzzy graphs modelling for HazMat telegeomonitoring

Telegeomonitoring system development combines two heterogeneous technologies: the geographical information systems technology (GIS) and telecommunications technology. In this paper, we give the system components for telegeomonitoring transportation of hazardous materials. The telegeomonitoring system uses GIS to capture civil infrastructure (urban network, land use, industries, etc.) and decision support systems technology to allow risks analysis and evaluate routing strategies that minimize transportation risk. Routing algorithms are to this effect adapted to graphs of the fuzzy risk. A new algebraic structure is proposed to solve a path-finding problem in a fuzzy graph. This algebraic structure is adapted precisely to solve the problem of the K-best fuzzy shortest paths. The approach that we proposed, consists of defining generic structures of operator’s traversal problem in fuzzy graphs. The principal contribution of our approach is to build adequate structures of path algebra to solve the problem of graph traversal in a fuzzy graph without negative circuits. Foundations of the system studied in this work will be able to be transposed to other fields of transportation.     

灾后运输网络中的最短路修复合作博弈

在最短路修复合作博弈中,当灾后运输网络规模较大时,最优成本分摊问题难以直接求解。基于拉格朗日松弛理论,提出了一种最短路修复合作博弈成本分摊算法。该算法将最短路修复合作博弈分解为两个具有特殊结构的子博弈,进而利用两个子博弈的结构特性,可以{高效地}求解出二者的最优成本分摊,将这两个成本分摊相加,可以获得原博弈的一个近乎最优的稳定成本分摊。结果部分既包含运输网络的随机仿真,也包含玉树地震灾区的现实模拟,无论数据来源于仿真还是现实,该算法都能在短时间内为最短路修复合作博弈提供稳定的成本分摊方案。     

The first <Emphasis Type="Italic">K</Emphasis> minimum cost paths in a time-schedule network

The time-constrained shortest path problem is an important generalisation of the classical shortest path problem and in recent years has attracted much research interest. We consider a time-schedule network, where every node in the network has a list of pre-specified departure times and departure from a node may take place only at one of these departure times. The objective of this paper is to find the first K minimum cost simple paths subject to a total time constraint. An efficient polynomial time algorithm is developed. It is also demonstrated that the algorithm can be modified for finding the first K paths for all possible values of total time.     

The shortest path problem with forbidden paths

We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints.     

模糊最短路的一种算法

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

Finding K shortest looping paths with waiting time in a time–window network

A time-constrained shortest path problem is a shortest path problem including time constraints that are commonly modeled by the form of time windows. Finding K shortest paths are suitable for the problem associated with constraints that are difficult to define or optimize simultaneously. Depending on the types of constraints, these K paths are generally classified into either simple paths or looping paths. In the presence of time–window constraints, waiting time occurs but is largely ignored. Given a network with such constraints, the contribution of this paper is to develop a polynomial time algorithm that finds the first K shortest looping paths including waiting time. The time complexity of the algorithm is O(rK²|V₁|³), where r is the number of different windows of a node and |V₁| is the number of nodes in the original network.     

Development of the tree-based link labeling algorithm for optimal path-finding in urban transportation networks

The optimal path-finding algorithm which is an important module in developing route guidance systems and traffic control systems has to provide correct paths to consider U-turns, P-turns, and no-left-turns in urban transportation networks.Traditional methods which have been used to consider those regulations on urban transportation networks can be categorized into network representation and algorithmic methods like the vine-building algorithm. First, network representation methods use traditional optimal path-finding algorithms with modifications to the network structure: for example, just adding dummy nodes and links to the existing network allows constraint-search in the network. This method which creates large networks is hard to implement and introduces considerable difficulties in network coding. With the increased number of nodes and links, the memory requirement tremendously increases, which causes the processing speed to slow down. For these reasons, the method has not been widely accepted for incorporating turning regulations in optimal path-finding problems in transportation networks. Second, algorithmic methods, as they are mainly based on the vine-building algorithm, have been suggested for determining optimal path for networks with turn penalties and prohibitions. However, the algorithms, although they nicely reflect the characteristics of urban transportation networks, frequently provide infeasible or suboptimal solutions.The algorithm to be suggested in this research is a method which is basically based on Dijkstra's algorithm [1] and the tree-building algorithm used to construct optimal paths. Unlike the traditional node labeling algorithms which label each node with minimum estimated cost, this algorithm labels each link with minimum estimated cost.Comparison with the vine-building algorithm shows that the solution of the link-labeling algorithm is better than that of the vine-building algorithm which very frequently provides suboptimal solutions. As a result, the algorithm allows turning regulations, while providing an optimal solution within a reasonable time limit.     

Evaluation and optimization of urban public transportation networks

So far, not much attention has been given to the problem of improving public transportation networks. In many cities these networks have been built sequentially and do not fit to the needs of the users any more. The results are long travel times and an unnecessarily high number of people who have to transfer. Compared to other investments for improving the service level of public transportation systems, the costs of rerouting the public vehicles are low and can, yet, highly improve the performance of the system.To evaluate a public transportation network, the shortest distance and the shortest route from node x to node y, taking the waiting times for a vehicle into account, must be known.It is shown in this paper, how to compute distances and routes efficiently for large networks. Using this algorithm it is described how to evaluate the average transportation cost of the passengers in a public transportation network.In the second part of the paper a heuristic algorithm is stated that improves a public transportation network using the average transportation cost as the objective.Finally, some experiences with real world problems are reported.     

Multimodal K-shortest viable path problem in Tehran public transportation network and its solution applying ant colony and simulated annealing algorithms

This paper treats with K-shortest viable path problem in a transportation network including multiple modes. The considered modes are metro, rapid-bus, private and walking. In this network, a viable path is one that the number of mode changes is limited and the traverse time and also the walking, metro and private usage are restricted subjected to some constraints. The traverse time is defined dependent on congestion level. Because constrained shortest path is NP-hard, we extend two metaheuristic algorithms namely GASA and BACS for the given problem. GASA is a Greedy Algorithm Simulated Annealing and BACS is a bi-direction searching Ant Colony System made by two colonies of ants. We evaluate the validation of these algorithms applying several multimodal random networks. In addition, their results are compared with CPLEX 12.1. We find that GASA is appropriate for small networks and BACS has better performance in median and large-scale networks. Our results on Tehran network also demonstrate that BACS provides better objective values than BACS ones because Tehran public transportation is sparse.     

基于道路堵塞及顾客时间要求的快件配送最优路径选择

针对道路堵塞如节假日导致的临时最短配送路径失效的问题,提出配送网络最优路径选择模型,并设计了求解快递配送网络关键边和最优路径的算法。首先,计算出整个网络的关键边,掌握配送网络特征;其次,考虑顾客时间要求,研究不完全信息(中断无法提前预知,只有到达中断边的起点处才可知)下的最优路径,根据最短路径上各边新的特点,计算出每条边中断后对应的一组备用路径,再选择运输时间小于或等于顾客可等待时间的路径为有效路径,考虑道路堵塞情况,从有效路径中选择最优路径;最后,结合配送网络的实际情况对最优路径进行了算例分析。     

Optimal egress time calculation and path generation for large evacuation networks

Finding the optimal clearance time and deciding the path and schedule of evacuation for large networks have traditionally been computationally intensive. In this paper, we propose a new method for finding the solution for this dynamic network flow problem with considerably lower computation time. Using a three phase solution method, we provide solutions for required clearance time for complete evacuation, minimum number of evacuation paths required for evacuation in least possible time and the starting schedules on those paths. First, a lower bound on the clearance time is calculated using minimum cost dynamic network flow model on a modified network graph representing the transportation network. Next, a solution pool of feasible paths between all O-D pairs is generated. Using the input from the first two models, a flow assignment model is developed to select the best paths from the pool and assign flow and decide schedule for evacuation with lowest clearance time possible. All the proposed models are mixed integer linear programing models and formulation is done for System Optimum (SO) scenario where the emphasis is on complete network evacuation in minimum possible clearance time without any preset priority. We demonstrate that the model can handle large size networks with low computation time. A numerical example illustrates the applicability and effectiveness of the proposed approach for evacuation.     

An Algorithm for Solving the Shortest Path Improvement Problem on Rooted Trees Under Unit Hamming Distance

Shortest path problems play important roles in computer science, communication networks, and transportation networks. In a shortest path improvement problem under unit Hamming distance, an edge-weighted graph with a set of source–terminal pairs is given. The objective is to modify the weights of the edges at a minimum cost under unit Hamming distance such that the modified distances of the shortest paths between some given sources and terminals are upper bounded by the given values. As the shortest path improvement problem is NP-hard, it is meaningful to analyze the complexity of the shortest path improvement problem defined on rooted trees with one common source. We first present a preprocessing algorithm to normalize the problem. We then present the proofs of some properties of the optimal solutions to the problem. A dynamic programming algorithm is proposed for the problem, and its time complexity is analyzed. A comparison of the computational experiments of the dynamic programming algorithm and MATLAB functions shows that the algorithm is efficient although its worst-case complexity is exponential time.     

Computation of the Reverse Shortest-Path Problem

The shortest-path problem in a network is to find shortest paths between some specified sources and terminals when the lengths of edges are given. This paper studies a reverse problem: how to shorten the lengths of edges with as less cost as possible such that the distances between specified sources and terminals are reduced to the required bounds. This can be regarded as a routing speed-up model in transportation networks. In this paper, for the general problem, the NP-completeness is shown, and for the case of trees and the case of single source-terminal, polynomial-time algorithms are presented.     

On the analysis of optimization problems in arc-dependent networks

This paper is concerned with the design and analysis of algorithms for optimization problems in arc-dependent networks. A network is said to be arc-dependent if the cost of an arc $a$ depends upon the arc taken to enter $a$. These networks are fundamentally different from traditional networks in which the cost associated with an arc is a fixed constant and part of the input. We first study the arc-dependent shortest path (ADSP) problem, which is also known as the suffix-1 path-dependent shortest path problem in the literature. This problem has a polynomial time solution if the shortest paths are not required to be simple. The ADSP problem finds applications in a number of domains, including highway engineering, turn penalties and prohibitions, and fare rebates. In this paper, we are interested in the ADSP problem when restricted to simple paths. We call this restricted version the simple arc-dependent shortest path (SADSP) problem. We show that the SADSP problem is NP-complete. We present inapproximability results and an exact exponential algorithm for this problem. We also extend our results for the longest path problem in arc-dependent networks. Additionally, we explore the problem of detecting negative cycles in arc-dependent networks and discuss its computational complexity. Our results include variants of the negative cycle detection problem such as longest, shortest, heaviest, and lightest negative simple cycles.²     

An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems

In this paper an algorithm is presented for determining the K best paths that may contain cycles in a directed network.The basic idea behind the algorithm is quite simple. Once the best path has been determined it is excluded from the network in such a way that no new path is formed and no more paths are excluded. This step leads to an enlarged network where all the paths, but the best one, can be determined. The method is repeated until the desired paths have been computed.The proposed algorithm can be used not only for the classical K shortest paths problem but also for ranking paths under a nonlinear objective function, provided that an algorithm to determine the best path exists.Computational results are presented and comparisons with other approaches for the classical problem are made.     

The shortest path problem with two objective functions

We present methods to find the shortest path in a network where each path is associated with two objectives. We describe how to obtain the nondominated paths and the extreme nondominated paths, and compare the expected complexity of the methods. An improvement in efficiency can be obtained when quasiconcave or quasiconvex utility functions are assumed. In the first case, we describe how to find the optimal extreme nondominated path and bounds for the optimal path value. Then the optimal path can be located by calculating the k-th shortest path. In the second case we suggest a branch and bound method to solve the problem.     

基于鲁棒优化的随机时变网络最优路径研究

交通事故、恶劣天气以及偶发的交通拥堵等都会导致道路交通网络中行程时间的不确定性,极大地影响了道路交通系统的可靠性,同时给日常生活中出行计划的制定以及出行路径的选择带来了不便。因此,本次研究将综合考虑道路交通网络中由于交通流量的全天变化所导致的路径行程时间的时变特征,以及由于事故、天气等不确定因素所导致的路径行程时间的随机特征,并以此作为路网环境的假设条件,对出行路径选择问题进行研究。具体地,首先建立行程时间的动态随机变量,并在此基础上模拟构建了随机时变网络。随后,定义了该网络环境下路径选择过程中所考虑的成本费用,并通过鲁棒优化的方法,将成本费用鲁棒性最强的路径视为最优路径。随后,在随机一致性条件下,通过数学推导证明了该模型可以简化为解决一个确定性时变网络中的最短路径问题。最终,具有多项式时间计算复杂度的改进Dijkstra算法被应用到模型的求解中,并通过小型算例验证模型及算法的有效性。结果表明,本研究中所提出的方法可以被高效率算法所求解,并且不依赖于先验行程时间概率分布的获取,因此对后续的大规模实际城市道路网络应用提供了良好的理论基础。此外,由于具有行程时间随机时变特征的交通网络更接近实际道路情况,因此本次研究的研究成果具有较高的实际意义和应用价值。     

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.     

A parametric algorithm for convex cost network flow and related problems

The convex cost network flow problem is to determine the minimum cost flow in a network when cost of flow over each arc is given by a piecewise linear convex function. In this paper, we develop a parametric algorithm for the convex cost network flow problem. We define the concept of optimum basis structure for the convex cost network flow problem. The optimum basis structure is then used to parametrize v, the flow to be transsshipped from source to sink. The resulting algorithm successively augments the flow on the shortest paths from source to sink which are implicitly enumerated by the algorithm. The algorithm is shown to be polynomially bounded. Computational results are presented to demonstrate the efficiency of the algorithm in solving large size problems. We also show how this algorithm can be used to (i) obtain the project cost curve of a CPM network with convex time-cost tradeoff functions; (ii) determine maximum flow in a network with concave gain functions; (iii) determine optimum capacity expansion of a network having convex arc capacity expansion costs.