An algorithm for the discrete network design problem without traffic assignment iterations

Though the transportation network design problem (TNDP) has been studied widely due to its importance, the majority of past studies need to solve the traffic assignment problem many times in the solution process, which makes the methods inefficient. In this paper, an algorithm for the TNDP of adding a lane/lanes to a link on a one-to-one network without traffic assignment iterations is presented. First, for each link, the travel time drop (TTD) of the network when adding a lane to each link is estimated. The estimation of the TTD does not need solving the traffic assignment problem on the network. It just need to adjust flows on the used paths of the OD. Since it does not involve finding the shortest path, it is far more efficient than the methods that need traffic assignment iterations. Then the link with the maximal TTD is selected for capacity expansion by adding a lane or lanes to it. At the end of each step, the TTD of the network is estimated again and a link is selected again for expansion. The process proceeds until the budget is met. The method is applied to a network and the validity of it is shown. The algorithm has two pros: 1) It can find the exact optimal solution for a one-to-one network; 2) It avoids UE iterations. The con of the algorithm is that it can only find the approximate optimal solution for multiple-origin-multiple-destination network. It helps to develop the approximate algorithm for a multiple-origin-multiple-destination (many-to-many) network.