Dynamic Continuous Network Design Problem

Abstract

A linear bilevel programming model and two analytical solution methods (the Kth-best algorithm and mixed integer programming reformulation) for the continuous network design problem are presented on the basis of the multiorigin, single-destination, user-optimal dynamic traffic assignment (UO DTA) problem. From the test problem, it is shown that the bilevel formulation is more desirable than the two known single-level models based respectively on system-optimal and UO DTA. For the multiorigin, multidestination, larger-size problem, three metaheuristics that can produce solutions beyond local optimality are employed: simulated annealing (SA), genetic algorithm (GA), and random search (RS). These metaheuristics share the same functional evaluation: a simulation-based UO DTA that propagates traffic according to Daganzo's cell transmission model. From computational results, GA outperforms the others for all three test problems in terms of solution quality, convergence speed, and processor time, whereas SA and RS appear nondominated. It is also shown that the appropriate set of algorithm parameters is network-specific and should be recalibrated for each network to achieve the best results.