This study addresses various formulations of the optimal reliability path problem on stochastic networks. Robust-Cost is adopted as the measure of reliability, which is defined as a weighted combination of the mean and standard deviation of travel time. The principal problem solved is the Minimum Robust-Cost Path (MRCP) problem in the presence of Correlated link travel times. It is shown that the subpath optimality and subpath non-dominance principles, which are conventionally adopted in the literature, cannot be used to solve this problem. In this light, this study proposes an algorithm based on the subpath pruning approach, which eliminates nonoptimal subpaths by using a pruning criterion. We construct the novel pruning criterion, which depends on only two independent objectives, by transforming the network and using efficient shortest path algorithms. The correctness of the algorithm is established, and its good practical performance is demonstrated on real-world networks. Furthermore, the pruning procedure is generalized with suitable modifications to solve three related problems: (i) the MRCP problem with independent link travel times, (ii) the K-best Robust-Cost Paths problem, and (iii) the MRCP problem with stochastic nondominance constraints. These extensions demonstrate the potential wider applications of the proposed solution approach. © 2016 INFORMS.

Karthik K. Srinivasan

Department Of Civil Engineering

Costs

reliability

Stochastic systems

Traffic control

Travel time

COST PATH

MOST RELIABLE PATH

OPTIMAL RELIABLE PATH

TRAVEL TIME CORRELATIONS

TRAVEL TIME RELIABILITY

Problem solving

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Transportation Science

The traditional traffic assignment model has been extended in the literature to incorporate uncertainty and travelers who are sensitive to it. However, the proposed formulations that model risk-averse users lack (i) a consistent representation of the various stochastic quantities involved and (ii) a general solution approach. In this context, this study formulates a consistent, reliability-based user-equilibrium problem with risk-averse travelers. In the proposed formulation, various stochastic quantities are consistent with each other: the stochastic origin–destination demands result in stochastic path-flows and in turn stochastic link-flows, which result in stochastic link travel times, and travelers make decisions based on the stochasticity of travel times. The formulation also incorporates (i) endogenous link-flow variances and covariances and (ii) flow-dependent and endogenous link travel time correlations. At equilibrium – which is defined over the distributions of travel times and flows – no user can improve her travel time reliability by unilaterally changing route. The conditions for existence of a solution to the formulated problem are presented. A gradient projection based algorithm is proposed to solve the formulated problem, which is demonstrated to be correct and efficient through computational experiments. We also show that ignoring consistency in the formulation can lead to potentially erroneous conclusions. Experiments also demonstrate that the solution can be sensitive to the demand levels, stochasticity in demand, and users’ degree of risk-aversion. This work has the potential to make existing reliability-based user-equilibrium formulations more general and operational. It also has important applications in reliability-based traffic planning and management. © 2018 Elsevier Ltd

Transportation Research Part B: Methodological

A consistent reliability-based user-equilibrium problem with risk-averse users and endogenous travel time correlations: Formulation and solution algorithm

Pruning algorithms to determine reliable paths on networks with random and correlated link travel times

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%). © 2017, Springer Science+Business Media New York.

Networks and Spatial Economics

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

The deterministic traffic assignment problem based on Wardrop's first criterion of traffic network utilization has been widely studied in the literature. However, the assumption of deterministic travel times in these models is restrictive, given the large degree of uncertainty prevalent in urban transportation networks. In this context, this paper proposes a robust traffic assignment model that generalizes Wardrop's principle of traffic network equilibrium to networks with stochastic and correlated link travel times and incorporates the aversion of commuters to unreliable routes. The user response to travel time uncertainty is modeled using the robust cost (RC) measure (defined as a weighted combination of the mean and standard deviation of path travel time) and the corresponding robust user equilibrium (UE) conditions are defined. The robust traffic assignment problem (RTAP) is subsequently formulated as a Variational Inequality problem. To solve the RTAP, a Gradient Projection algorithm is proposed, which involves solving a series of minimum RC path sub-problems that are theoretically and practically harder than deterministic shortest path problems. In addition, an origin-based heuristic is proposed to enhance computational performance on large networks. Numerical experiments examine the computational performance and convergence characteristics of the exact algorithm and establish the accuracy and efficiency of the origin-based heuristic on various real-world networks. Finally, the proposed RTA model is applied to the Chennai road network using empirical data, and its benefits as a normative benchmark are quantified through comparisons against the standard UE and System Optimum (SO) models. © 2017 Taylor & Francis.

Journal of Intelligent Transportation Systems: Technology, Planning, and Operations

Robust traffic assignment model: Formulation, solution algorithms and empirical application

There is a growing interest in modeling travel time uncertainty in transportation networks in addition to optimizing the reliability of travel times at the path and network level. This paper focuses on the analysis and optimization of travel time (including stopped delays) Reliability on the Urban Road Network in Chennai. Specifically, two objectives are investigated. The first objective involves the quantification of travel time reliability at the link and path level. In particular, the distribution of link travel times is quantified for the Chennai Urban road network using empirical data. The results indicate that the shifted log-normal distribution (SLN) reasonably represents link travel time for all facility types and relevant facility wise distribution parameters are estimated. Further, the resulting path travel time distribution is approximated by a SLN distribution, which is computationally less expensive than traditional Monte-Carlo estimation techniques with an acceptable compromise on accuracy. The second objective addresses the optimal reliability path problem on a network with SLN link travel times with general correlation structure. For this problem, it is shown that the sub-path optimality property of shortest path problems does not hold making traditional label-setting/label correcting algorithms inapplicable. Consequently, a sufficient optimality condition based on reliability bounds is established and a new network optimization algorithm is proposed and proof of correctness is presented. The convergence rate of the algorithm was shown to increase at every iteration under some mild conditions. The computational performance of the proposed algorithm is investigated using synthetic and real-world networks and found to be reasonably accurate. © 2013 Elsevier Ltd.

Finding most reliable paths on networks with correlated and shifted log-normal travel times

Transportation networks are subject to significant travel time uncertainty as a result of traveler behavior, recurring congestion, capacity variability (construction zones, traffic incidents), variation in demand, and so on. Therefore, interest is growing in modeling and optimizing travel time reliability in such networks. This paper proposes an efficient algorithm to compute the path of maximum travel time reliability on a network with normally distributed and correlated link travel times. For this optimal reliability path (ORP) problem, it is shown that the subpath optimality condition for the deterministic shortest path problem does not hold, and consequently, a new bounds-based optimality criterion is proposed using the K shortest expected time paths and the minimum path variance on the network. An algorithm is developed to solve the ORP problem on the basis of the proposed optimality criterion and an efficient path generation procedure. Computational experiments on various test networks show the proposed algorithm to be efficient, requiring limited path enumeration. With as few as five shortest paths and 50 Monte Carlo draws, the proposed algorithm is able to find the most reliable path for realistic network sizes. Empirical investigations highlight the unreliability of the least expected time path and suboptimality of the independence assumption. The study also underscores the role of risk attitudes (reflected by reliability threshold) on the benefits of the ORP. The algorithm and empirical results have important applications for developing reliability-based routing applications for congestion mitigation and intelligent transportation systems.

Fulltext

Transportation Research Record

Algorithm for determining most reliable travel time path on network with normally distributed and correlated link travel times

Transportation Research Record: Journal of the Transportation Research Board

Impacts of Correlations on Reliable Shortest Path Finding

Transportation Research Part A: Policy and Practice

Value of travel time reliability: A review of current evidence

Journal	Transportation Science
Publisher	INFORMS Inst.for Operations Res.and the Management Sciences
ISSN	00411655
Open Access	No