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

A. Arun Prakash () and Karthik K. Srinivasan ()
Additional contact information
A. Arun Prakash: Singapore-MIT Alliance for Research and Technology
Karthik K. Srinivasan: IIT Madras

Networks and Spatial Economics, 2017, vol. 17, issue 3, No 6, 809-840

Abstract: Abstract 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%).

Keywords: Reliability; Robust-cost; Stochastic and time-dependent networks; Hypergraphs; Network optimization (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s11067-017-9345-2 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kap:netspa:v:17:y:2017:i:3:d:10.1007_s11067-017-9345-2

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-017-9345-2

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().