Models and algorithms for road network design: a review and some new developments

The Network Design Problem (NDP) has long been recognized to be one of the most difficult and challenging problems in transport. In the past two decades, we have witnessed the development of a vast, growing body of research focused on formulations and solution procedures for the NDPs, which deal with the selection of either link improvements or link additions to an existing road network, with given demand from each origin to each destination. The objective is to make an optimal investment decision in order to minimize the total travel cost in the network, while accounting for the route choice behaviour of network users. In this paper, we present a general survey of existing literature in this area, and present some new developments in model formulations. We incorporate the elasticity of travel demand into the NDP and seek the economic-based objective function for optimization. We also pose the mixed network design problem involving simultaneous choice of link addition and capacity improvement which is considered more sensible for road networks. In addition, we introduce the network reserve capacity concept for a capacity improvement plan, and raise and clarify some interesting issues relating to NDP and Braess's paradoxes. Finally, from the survey and the new proposal made herein, we offer some perspectives on future research.