A new algorithm for the dynamic simultaneous departure time and route choice problem with inflow and density constraints

The constraints on the link density and the link inflow must be included in modeling the dynamic user optimal simultaneous departure time and route choice problem (DUO-SDTRC) for it to be consistent with the reality. Recently, a relaxation with gradient projection algorithm was presented for this problem but it was very inefficient. A more efficient heuristic algorithm, the relaxation with match algorithm, is presented in the paper. First, a one-level variational inequality (VI) model is presented for the DUO-SDTRC with constraints on link inflow and link density. Second, a relaxation with match algorithm is presented for solving the model. The model and algorithm are applied to a network and the performance of the two algorithms is compared. The results indicate that the relaxation with match algorithm is far more efficient than the relaxation with gradient projection algorithm in solving the problem.