B-Dynamic: An Efficient Algorithm for Dynamic User Equilibrium Assignment in Activity-Travel Networks¹

Abstract: Multi-dimensional choice in dynamic traffic assignment (DTA)—for example, a combined model of activity location, time of participation, duration, and route choice decisions—results in exponentially increasing choice alternatives. Any efficient algorithm for solving the multi-dimensional DTA problem must avoid enumeration of alternatives. In this article an algorithm that does not enumerate paths is presented. The algorithm is a novel extension of Algorithm B (Dial, 2006) to dynamic networks and hence referred to as Algorithm B-Dynamic. The DTA model proposed here uses a point queue model for traffic propagation that reduces computational complexity. The activity participation decision dimensions are incorporated through utility functions, which are a linear function of duration and schedule delay (early or late arrival penalty). Numerical examples are then presented to illustrate both the steps of the algorithm and its capabilities. Overall, the algorithm performed well for up to medium-sized networks. Further, the algorithm scales fairly well with increasing demand levels.