An Algorithm for the Discrete Network Design Problem.

This article addresses the "link-addition" or discrete network design problem in road travel. Given an existing urban road network, with projected increases in demands for road travel between various pairs of nodes, it is typically the case that severe congestion will exist if the capacity of the network is not expanded. Thus, the decision maker must consider building new links into the network, or increasing the capacity of some existing links. He must consider the various types of possible improvements to the network, as well as several locations in the network as candidates for improvement. When using a network to model a road transportation system, the travel time experienced by each driver along any link is given by the average travel time function for the link. Because of congestion, it is taken to be a nonlinear function of the total flow along the link. The sum of all drivers' travel times along a link is called the total travel time function. This is of considerable importance in solving large network design problems, since shortest route problems can be easily solved even for very large networks.