An efficient solution algorithm for solving multi-class reliability-based traffic assignment problem

The multi-class reliability-based user equilibrium (RUE) problem has been intensively studied in recent years, as it can capture the route choice behaviors of users with heterogeneous risk-aversion under demand and supply uncertainties. Few solution algorithms, however, are available for solving the RUE problems in large-scale road networks. This is mainly due to the non-additive property of the path finding sub-problem in the RUE model. An efficient traffic assignment solution algorithm for solving the multi-class RUE problems in large-scale road networks is proposed in this study. First, an effective shortest path algorithm is developed to explicitly overcome the non-additive difficulty. The algorithm is capable of finding optimal paths for all user classes in one search process and hence the repeated search process for each user class is avoided. This property can save not only computational time but also memory requirement. The proposed shortest path algorithm is then, further incorporated into a path-based traffic assignment algorithm using a column generation technique. Such traffic assignment algorithms can solve the multi-class RUE problem without the requirement of path enumeration. Experimental results show that the proposed solution algorithms can, even for large-scale networks with multi-user classes, efficiently achieve highly accurate RUE solutions within satisfactory computational time. (C) 2011 Elsevier Ltd. All rights reserved.