Price of anarchy for reliability-based traffic assignment and network design

Abstract

This paper proposes reliability-based system-optimal traffic assignment under supply uncertainty based on the concept of the total system travel time budget, and defines the price of anarchy (PoA) for the corresponding user equilibrium (UE) traffic assignment. An analytical formula for a set of the upper bounds of the PoA for the equilibrium assignment to the networks with polynomial link travel time functions is derived. These bounds are proved to be independent of the network topology and demands. The formula for the minimum upper bound is also derived and can be reduced to the upper bound formula for traditional UE traffic assignment as a special case. The PoA for the traditional UE network design problem (NDP) with polynomial link travel time functions is defined, and proved to be bounded by the upper bound of that for traditional UE traffic assignment of the same instance, before any link expansion. The PoA for the reliability-based UE (RUE) NDP with polynomial link travel time functions is also proved to be bounded by the set of upper bounds of that for RUE traffic assignment of the same instance, before any link expansion.

Keywords:

• reliability-based traffic assignment
• network design problem
• price of anarchy

Acknowledgements

The authors are grateful to the four reviewers for their useful comments.

ORCID

W.Y. Szeto http://orcid.org/0000-0001-7059-3532

Notes

1. A vector function is strictly monotone on a non-empty set C if for all vectors , .

Additional information

Funding

This research was jointly supported by grants (Nos. 201311159123 and 201411159063) from the University Research Committee of the University of Hong Kong and a grant from the National Natural Science Foundation of China (No. 71271183).