Toll pricing and heterogeneous users: Approximation algorithms for finding bicriterion time-dependent efficient paths in large-scale traffic networks

Hani S. Mahmassani*, Xuesong Zhou, Chung Cheng Lu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

Abstract

This paper presents both exact and approximation algorithms for finding extreme efficient time-dependent shortest paths for use with dynamic traffic assignment applications to networks with variable toll pricing and heterogeneous users (with different value of tune preferences). A parametric least-generalized cost path algorithm is presented to determine a complete set of extreme efficient time-dependent paths that simultaneously consider travel time and cost criteria. However, exact procedures may not be practical for large networks. For this reason, approximation schemes are devised and tested. Based on the concept of ε-efficiency in multiobjective shortest path problems, a binary search framework is developed to find a set of extreme efficient paths that minimize expected approximation error, with the use of the underlying value of time distribution. Both exact and approximation schemes (along with variants) are tested on three actual traffic networks. The experimental results indicate that the computation time and the size of the solution set are jointly determined by several key parameters such as the number of time intervals and the number of nodes in the network. The results also suggest that the proposed approximation scheme is computationally efficient for large-scale bi-objective time-dependent shortest path applications while maintaining satisfactory solution quality.

Original languageEnglish (US)
Pages (from-to)28-36
Number of pages9
JournalTransportation Research Record
Issue number1923
DOIs
StatePublished - 2005

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Mechanical Engineering

Fingerprint

Dive into the research topics of 'Toll pricing and heterogeneous users: Approximation algorithms for finding bicriterion time-dependent efficient paths in large-scale traffic networks'. Together they form a unique fingerprint.

Cite this