Header menu link for other important links
X
Algorithm for determining most reliable travel time path on network with normally distributed and correlated link travel times
Published in
2010
   
Issue: 2196
Pages: 83 - 92
Abstract
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.
About the journal
JournalTransportation Research Record
ISSN03611981
Open AccessNo
Concepts (39)
  •  related image
    Computational experiment
  •  related image
    CONGESTION MITIGATION
  •  related image
    CORRELATED LINK
  •  related image
    Efficient algorithm
  •  related image
    EFFICIENT PATH
  •  related image
    EMPIRICAL INVESTIGATION
  •  related image
    Empirical results
  •  related image
    EXPECTED TIME
  •  related image
    INDEPENDENCE ASSUMPTION
  •  related image
    Intelligent transportation systems
  •  related image
    MAXIMUM TRAVEL TIME
  •  related image
    Monte carlo
  •  related image
    NETWORK SIZE
  •  related image
    OPTIMAL RELIABILITY
  •  related image
    OPTIMALITY CONDITIONS
  •  related image
    OPTIMALITY CRITERIA
  •  related image
    PATH ENUMERATION
  •  related image
    RELIABILITY THRESHOLD
  •  related image
    RISK ATTITUDE
  •  related image
    Shortest path
  •  related image
    SHORTEST PATH PROBLEM
  •  related image
    SUBOPTIMALITY
  •  related image
    TEST NETWORK
  •  related image
    TRAFFIC INCIDENTS
  •  related image
    Transportation network
  •  related image
    Travel time
  •  related image
    TRAVEL TIME RELIABILITY
  •  related image
    TRAVEL TIME UNCERTAINTY
  •  related image
    Algorithms
  •  related image
    Behavioral research
  •  related image
    Graph theory
  •  related image
    Intelligent systems
  •  related image
    Normal distribution
  •  related image
    Optimization
  •  related image
    Reliability
  •  related image
    Traffic congestion
  •  related image
    Transportation
  •  related image
    Wireless sensor networks
  •  related image
    Computational efficiency