TY - JOUR

T1 - Tolerance-based strategies for extending the column generation algorithm to the bounded rational dynamic user equilibrium problem

AU - Wang, D.

AU - Liao, F.

AU - Gao, Ziyou

AU - Timmermans, H.J.P.

PY - 2019/1

Y1 - 2019/1

N2 - The column generation (CG) algorithm has been widely applied to traffic assignment problems due to its capability of circumventing path enumeration. Incorporating bounded rationality (BR) and dynamics, this paper proposes four tolerance-based strategies for extending the CG algorithm to the bounded rational dynamic user equilibrium model (BR-DUE): (i) a tolerance-based minimum disutility path search strategy is developed to allow travelers seeking satisfactory paths; (ii) a self-adjusted convergence threshold strat- egy is applied for fast convergence at the intermediate iterations; (iii) a varied temporal resolution scheme, combining exploration and exploitation, is suggested to assign flows to narrow time regions rather than to the whole time horizon; and (iv) a path search skipping strategy is introduced by comparing the lower bound of travel disutility and the minimum disutility between the OD pairs. With these strategies, an efficient tolerance- based column generation (TBCG) algorithm for BR-DUE is developed. Numerical examples are provided to demonstrate that the TBCG algorithm leads to significant computation time reductions without the expense of solution quality, of which the speedup factors are around two compared with using the original CG algorithm.

AB - The column generation (CG) algorithm has been widely applied to traffic assignment problems due to its capability of circumventing path enumeration. Incorporating bounded rationality (BR) and dynamics, this paper proposes four tolerance-based strategies for extending the CG algorithm to the bounded rational dynamic user equilibrium model (BR-DUE): (i) a tolerance-based minimum disutility path search strategy is developed to allow travelers seeking satisfactory paths; (ii) a self-adjusted convergence threshold strat- egy is applied for fast convergence at the intermediate iterations; (iii) a varied temporal resolution scheme, combining exploration and exploitation, is suggested to assign flows to narrow time regions rather than to the whole time horizon; and (iv) a path search skipping strategy is introduced by comparing the lower bound of travel disutility and the minimum disutility between the OD pairs. With these strategies, an efficient tolerance- based column generation (TBCG) algorithm for BR-DUE is developed. Numerical examples are provided to demonstrate that the TBCG algorithm leads to significant computation time reductions without the expense of solution quality, of which the speedup factors are around two compared with using the original CG algorithm.

KW - Column generation

KW - Dynamic user equilibrium

KW - Bounded rationality

KW - Temporal resolution

UR - http://www.scopus.com/inward/record.url?scp=85057345348&partnerID=8YFLogxK

U2 - 10.1016/j.trb.2018.11.008

DO - 10.1016/j.trb.2018.11.008

M3 - Article

VL - 119

SP - 102

EP - 121

JO - Transportation Research. Part B: Methodological

JF - Transportation Research. Part B: Methodological

SN - 0191-2615

ER -