Transportation network design is the problem of determining the optimal modification, such as the addition of new road segments, of an existing ground transportation network [1]}, [2]}. The modifications can be expanding the capacity of existing links, or adding new nodes and links to the network. The quality of the modifications is evaluated via the congestion of the travelers in the modified network and the cost of the modifications. The input of the problem includes 1) the existing transportation network topology, 2) the travel demand between each origin-destination pair for a specific time interval, 3) the characteristics of roads, such as flow capacity and free travel time, 4) the set of candidate options for modifications and their cost, and 5) the total budget for modifications. The outcome of the problem is a set of modifications that satisfies the budget constraint and minimizes the congestion of the travelers. See [3]} for a recent survey on transportation network design.
