Combinatorial Approach for Multiple-Destination User Optimal Dynamic Traffic Assignment

An algorithm that can be used to solve the user optimal dynamic traffic assignment problem for multiple destinations is proposed. The algorithm uses the cell transmission model, which can account for traffic realities, such as dynamic queuing and spillover. The approach selects a destination for equilibration, fixes the paths of the vehicles assigned to the other destinations, and finds an optimal dynamic traffic assignment for the destination of interest via an extension to a previously introduced combinatorial algorithm. The spatial path set obtained for this destination is then fixed, and another destination is relaxed. The process is repeated iteratively among the destinations. The approach is guaranteed to find the user optimal solution for a single destination given any number of other fixed-path vehicles, but the approach is a heuristic for finding the multiple-destination user optimal path set. The algorithm is implemented and computationally tested for an example network, and solution properties are explored.