## Network Design

Site still under construction ...

### Budget Design Problem

The budget design problem inverts the minimum cost problem by taking an exogenous upper bound on investment costs into consideration. As an example we refer to a government which designates a fixed amount of tax income to road infrastructure investments. The instructed network designer is then asked to assign these resources to network improvements in the "most desirable" way.

### Discrete Network Design

Discrete network design problems are concerned with the topology of the network. The basic ingredients are a set of potential nodes and a set of potential edges. Typical tasks are explained best by giving some examples.

• Establish a new transport network from the scratch (greenfield approach). For instance, think of a newcomer in the telecommunications industry. Another case is concerned with the reconstruction of networks floods (scorched earth approaches). A less drastic example is that of snow removal to put a network back into service as quick as possible.
• Extend a given network by the construction of new nodes or links. Additional nodes may refer to new warehouses, industrial parks, airports, ports, etc. The connection of nodes to a network requires the construction of new roads or bridges, rail links, tunnels, bypasses, shipping canals etc. Recall that parts of a network are related to each other as complements, other elements are substitutes. In this sense, certain links are necessary to reach a particular node; other interconnections just improve its accessibility.
• Growing networks naturally reach a state where improvements not only incur costs of construction but also demolition costs, which have deep impact, for example, on urban growth; see Hochman, Pines (1980). The problem is here to weigh up strategies of pure network extensions and strategies of reconstruction.
• Of course, there are mixed cases which need elements of discrete and continuous network design. An example is the provision of new transport services on an urban subway network which requires new tunnels (and stations) as well as an upgrade of old tracks.
• An advanced problem addresses the question of optimal location of points of interconnection for traffic exchange between autonomous networks. Awduche et al. (1998) analyze such a problem in the context of Internet Service Providers with the objective to minimize the cost of peering, which improves the efficiency of Internet-domain traffic. The same problem is valid for national and international telecommunications networks as well as for road traffic with respect to different travel modes or for commercial road systems.

### Continuous Network Design

Continuous network design problems have the task of improving the functionality of networks or of network elements so that the level of service (comfort, risk, travel time, etc.) delivered to the customers increases. These problems take the network topology as given. They are concerned with the parameterization of a network (link or node capacity, user charges, etc.).

### Traffic Diversion and Traffic Dimininution (or Creation)

Any measure that improves traffic conditions causes two modifications of the prevailing traffic pattern, in particular, when the demand for traffic is price sensitive. On the one hand, traffic diversion is concerned with rerouting a fixed volume of traffic. On the other hand, traffic diminution (or creation) takes into account that tolls reduce the demand for traffic but it essentially ignores the traffic assignment problem.

Recall the example of the City of London. The congestion charge has reduced traffic volumes by 20% within the eight-square-mile downtown zone (traffic diminution). The remaining traffic now can be reorganized under less restrictive traffic conditions (traffic diversion).

Literature: Beckmann, McGuire (1953)

### Hub-and-Spoke Networks

Airline passenger carriers and parcel delivery networks take care of routing by developing so-called hub-and-spoke networks. At first, all flows are collected via spokes at specialized nodes, say hubs. In doing so the bundling of flows on the interhub links makes more efficient transportation technologies available to the carrier. At least to some extend, hub-and-spoke networks have the disadvantage that when considerable traffic volumes are concentrated on a few links, failures of network components may cause severe losses. Literature: O'Kelly (1986) or Bryan, O'Kelly (1999)