Application of Paths Information in Network Design Problem

Abstract

In a discrete network design problem, an optimal subset is chosen from a set of proposed link additions to an existing road network in order to minimize the total cost of users. The problem has been called as a complex issue in the transportation planning literature. The main source of complexity is that the problem is a bilevel program in which the lower-level program is a traffic assignment problem. In this paper, a path-based traffic assignment problem is used as the lower-level problem. The path-based algorithms not only provide the link-flow solution, but also the useful path-flow solution (path information) that may be required or used in certain applications, such as network design problem. To solve a network design problem, the traffic assignment problem will need to be solved many times. The main objective of this paper is to expedite the solution of the network design problem by initializing traffic assignment problems with path sets already found in previously performed traffic assignments. The rationale behind this idea is that the addition of a number of proposed links to a network will not change the used paths for the majority of origin-destination (OD) pairs. In this paper, the network design problem is solved by a branch and bound algorithm for a small network and a relatively large network. It is shown that the proposed method is capable of reducing the computation time to one-fifth in real-size networks.