TRANSPORTATION-NETWORK DESIGN PROBLEM: APPLICATION OF A HIERARCHICAL SEARCH ALGORITHM

Abstract

Two variants of a network design problem are solved by application of the tree search method. The first formulation aims to reduce a specified vehicle-minutes of traffic congestion at the least possible budget expenditure, and the second minimizes traffic congestion for a given budget. Both involve system-optimizing traffic assignment models with multipath flows. The solution method consists of network abstraction, tree search, and network disaggregation--collectively referred to as the hierarchical search algorithm. It is shown that such an algorithm reduces the search space by reducing the number of nodes and links and providing a tighter bound during the tree search. It also groups detailed links according to the function they perform--whether it be access/egress, line-haul, bypass, or internal circulation. However, the algorithm yields only a suboptimal solution, the quality of which is measured by an error function. The metropolitan network of Taipei, Taiwan, Republic of China, is used as a case study to verify some of the algorithmic properties, confirming its role in real-world applications. Finally, the performance of the algorithm, which is based on network abstraction, is favorably compared with a network-extraction network-design model.