Dynamic pricing with heterogeneous users: Gap-driven solution approach for bicriterion dynamic user equilibrium problem

The bicriterion dynamic user equilibrium (BDUE) model characterizes the dynamic user equilibrium (DUE) in a network resulting from the path choice interactions of a population of heterogeneous trip makers with different values of time (VOT). The BDUE model represents an attempt to accommodate greater behavioral and policy realism in applying DUE models to designing and evaluating dynamic pricing strategies. It also represents an advance in generalizing heterogeneous user equilibrium models from the static regime to the dynamic traffic-assignment context. To effectively obtain time-varying path-flow patterns satisfying the BDUE conditions, a study was done to adapt the gap-driven and simulation-based algorithmic framework to solve the DUE problem (with a constant VOT). Especially, the proposed BDUE algorithm is a column generation-based approach that integrates the following components: (a) a simulation-based dynamic network loading model that captures traffic dynamics and determines experienced path travel times for a given time-varying path-flow pattern, (b) a path generation scheme that partitions the entire range of VOT into many subintervals and accordingly determines the corresponding multiple user classes and the least-generalized cost (i.e., extreme nondominated) paths for each user class, and (c) a multiclass path flow equilibrating method for updating the current path assignment. The results of the experiments conducted on several real networks show that the convergence pattern of the proposed algorithm is not affected by different VOT assumptions, and it is able to find close-to-BDUE solutions.