Transportation Geography and Network Science/Network design problem
Contents
Network design: Graph Theory Perspective[edit]
For a given graph, G=(V,E,W), where V represents set of vertices, E denotes the set of edges between each connecting nodes or vertices and W indicates the weights associated with edges in graph. More than often, a Network Design problem involves identifying a subset set of graph's edges satisfying a set of constraints with minimum total weights ( or costs). Some examples of network design problem include;
1. Constrained Minimum Spanning Tree Problems:
The objective of this problem is to find the minimum spanning tree with constrained degree, diameter (see w:Distance (graph theory)), cost of transmitting a given set of communication requirements between nodes.
2. Generalized Network Design Problems:
Graph is partitioned into clusters or communities and the objective is to identify a subgraph connecting exactly or at least one node from each cluster sunder certain constraints such as cost, length, etc. One of the famous problems under this category is generalized traveling salesman problem (see w:Traveling salesman problem).
Such problems are combinatorial and NPhard in nature. Typically evolutionary algorithms, exact techniques such as branchandcut or combination of the both are used to solve these problems.
Network Design for Roads[edit]
Introduction[edit]
Transportation planning and management tasks typically involves determining a set of optimal values for certain prespecified decision variables by optimizing different system performance measures such as safety, congestion, accessibility, etc. based on user's route choice behavior. With growing demand for travel on roads, the network design problem has emerged to be one of the most critical tasks for transportation planners, particularly considering the limited availability of resources to expand system capacity. Typical decisions in network design problem include road pricing and optimal signal control. A large amount of work has already been done on network Design in transportation area^{[1]}. Structurally there are two different forms of the problem: a) discrete form such as addition of new links to existing road way system^{[2]}. b) continuous form such as capacity expansion of the existing road way ^{[3]}.
Types of Network Design Problem[edit]
 Discrete Network Design Problem

 Related to topology of the network. E.g., adding new links or close links.
 Continuous Network Design Problem

 Related to parametrization of the network. E.g. capacity expansion, road pricing, signal timings.
 Mixed Network Design Problem

 Related to both topology and parametrization. E.g. adding new infrastructure and capacity expansion, cordonbased pricing.
BiLevel Framework[edit]
Bilevel programming is one of the well known techniques use din solving Network Design Problem(NDP). Following are the general characteristics associated with bilevel framework in transportation road network.
 At upper level (i.e. system level)overall system performance function is optimized.
 At lower level (user's level) individual traveler's minimized his/her actual or perceived travel cost.
 Decision at upper level can only influence but can not dictate over user's behavior.
Mathematical formulation for Bilevel Programming[edit]
subject to:
where is a solution to the the following optimization problem for any fixed
subject to:
Lower Level User Equilibrium Assignment[edit]
In the above equation y(x) is the network equilibrium flow (lower level response) for any given x(vector of decision variables).The two most common form of equilibrium flow are deterministic user equilibrium (DUE) and stochastic user equilibrium (SUE)^{[4]}.
For example, under DUE when the link travel cost function ()is assumed to be separable( such as BPR function), the lower level optimization problem, i.e. solution to y(x)can be written as
subject to
where is the flow on link , is the path flow on route between and and is the linkpath incidence matrix. SUE counterpart of the user equilibrium can be also found in the relevant literature^{[5]},^{[6]}. Since NDP generally involves longterm investment, elasticity in transportation demand is warranted to obtain a consistent result. Sheffi^{[4]} gave modified solution to the user equilibrium assignment, considering the elastic demand.
UpperLevel Optimization[edit]
Depending upon the objective different upper level objective functions can be formulated^{[7]}.
 Minimize total network cost at equilibrium
subject to:

 where is the continuous capacity increase of link and is the construction cost(usually assumed to be nonnegative, increasing and differentiable)
 2. Maximize Reserved Capacity
This upperlevel formulation allows to predict how much additional demand can a network sustain after improvement. maximization of reserve capacity will favor links with higher marginal social cost (i.e. link with high critical volume/capacity ratio will be chosen for future investment).Reserve capacity is evaluated as a multiplier to OriginDestination(OD) matrix subject to flow conservation and capacity constraint.The corresponding NDP formulation can be expressed as:
subject to
where represents equilibrium flow on link when each OD pair is increased by μ times.
 3. Maximize consumer surplus with elastic demand
When the demand is elastic, then total travel cost may not be an appropriate upper level objective function , as it may lead to undesirable impact on travel demand. In such scenario consumer surplus or net social benefits can be treated as an effective objective function. the corresponding NDP can be formulated as:
where is the inverse of the monotonically decreasing demand function, for OD pair .
Game Theoretic Concept[edit]
Bilevel transportation problem can be treated from game theoretic point of view. w:Game theory models situation where two or more players participate and their individual decisions impact each other.Typically Nash noncooperative and Stackelberg games reflect the NDP formulation. Nash noncooperative equilibrium is reached when no players can improve his or her objective by unilaterally changing his or her decision. More formally, without loss of generality, if there are two players involved in a game, where each individual aims to minimize their objective function, , where is the decision variable for in the game. Then is the Nash equilibrium solution if
In contrast,Stackelberg game has one leader who has the knowledge of the other player's(followers) response to any decision he or she may take.For example, in a two player game if player 1 is the leader, then the response of the player 2 (i.e. follower), ,where is the decision made by leader(player 1). Stackelberg equilibrium solution can be obtained by solving following optimization problem:


 , where
 is the solution to the lower level optimization problem for any given i.e.

Similar to Nash solution, Stackelberg equilibrium solution, satisfies following inequalities
From the above formulation of the two games it can be observed that the bilevel NDP in road network is a Stackelberg game, while at the lower level, the users exhibit noncooperative behavior in choosing their individual route, which satisfies conditions for Nash noncooperative game.
Enumeration of Algorithms[edit]
 Discrete NDP
 Continuous NDP
 IterativeOptimizationAssignment (IOA) algorithm^{[8]}^{[9]}
 The Sensitivity Analysisbased algorithm^{[10]}^{[11]}
 Other approaches
 Computational Intelligence
 Link Usage ProportionBased algorithm^{[12]}^{[13]}
References[edit]
 ↑ Friesz, T. L., 1981, The Multiobjective optimization in transportation: The case of equilibrium network design. In Organizations: Multiple Agents with Multiple Criteria, edited by J. N. Morse. Lecture Notes in Economics and Mathematical Systems, Vol. 190 (new York:SpringerVerlag), pp, 116127.
 ↑ L. Leblanc. An algorithm for the discrete network design problem. Transportation Science, 9(3): 183, 1975
 ↑ M. Abdulaal and L. LeBlanc. Continuous equilibrium network design models. "Transportation Research Part B: Methodological, 13(1):1932, 1979
 ↑ ^{a} ^{b} Sheffi,Y., 1984. Urban transportation networks: equilibrium analysis with mathematical programming methods, PrenticeHall Englewod Cliffs, N.J.
 ↑ Daganzo, C.F., Y. Sheffi. On Stochastic Models of Traffic Assignment. Transportation Science, Vol 11, No. 3, 1997, pp. 253274.
 ↑ Davis, G.A., Exact local solution of the continuous network design problem via stochastic user equilibrium assignment. Transportation Research, 28B, 1994, pp.6175.
 ↑ Yang, H.,M.G. Bell. Models and algorithms for road network design: a review and some new developments. Transport Reviews. Vol. 18, No. 3,pp. 257278, 1998.
 ↑ Asakura, Y.,and Saski,T. Formulation and feasibility test of optimal road network design model with endogenously determined travel demand. Proceedings of the 5th World Conference on Transport Research ,Yokohama,Japan,July,1990,pp. 351365
 ↑ Friesz,T.L., and Harker,P.T. properties of the iterative optimizationequilibrium algorithm,Civil Engineering Systems,2,1985,pp. 142154.
 ↑ Wong,S. C., and Yang, H. Reserved capacity for a signal controlled road network, Transportation Research 31B, 1997,397402.
 ↑ Yang, H., and Lam, W.H.K. Optimal road tolls under conditions of queuing and congestion. Transportation Research, 30A, 1996, 319332.
 ↑ Yang, H., and Yagar, S. Traffic assignment and traffic control in general freewayarterial corridor systems, Transportation Research ,28B, 1994, 463485
 ↑ Yang, H., and Bell,M.G.H. Traffic restraint, road pricing and network equilibrium. Transportation Research, 31B, 1997, 303314