Transportation Geography and Network Science/Network design problem
Network design: Graph Theory Perspective
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 NP-hard in nature. Typically evolutionary algorithms, exact techniques such as branch-and-cut or combination of the both are used to solve these problems.
Network Design for Roads
Transportation planning and management tasks typically involves determining a set of optimal values for certain pre-specified 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. Structurally there are two different forms of the problem: a) discrete form such as addition of new links to existing road way system. b) continuous form such as capacity expansion of the existing road way .
Types of Network Design Problem
- 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, cordon-based pricing.
Bilevel programming is one of the well known techniques used in solving Network Design Problem(NDP). Following are the general characteristics associated with bi-level 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
where is a solution to the following optimization problem for any fixed
Lower Level User Equilibrium Assignment
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).
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
where is the flow on link , is the path flow on route between and and is the link-path incidence matrix. SUE counterpart of the user equilibrium can be also found in the relevant literature,. Since NDP generally involves long-term investment, elasticity in transportation demand is warranted to obtain a consistent result. Sheffi gave modified solution to the user equilibrium assignment, considering the elastic demand.
Depending upon the objective different upper level objective functions can be formulated.
- Minimize total network cost at equilibrium
- where is the continuous capacity increase of link and is the construction cost(usually assumed to be non-negative, increasing and differentiable)
- 2. Maximize Reserved Capacity
This upper-level 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 Origin-Destination(O-D) matrix subject to flow conservation and capacity constraint.The corresponding NDP formulation can be expressed as:
where represents equilibrium flow on link when each O-D 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 O-D pair .
Game Theoretic Concept
Bi-level 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 non-cooperative and Stackelberg games reflect the NDP formulation. Nash non-cooperative 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 bi-level NDP in road network is a Stackelberg game, while at the lower level, the users exhibit non-cooperative behavior in choosing their individual route, which satisfies conditions for Nash non-cooperative game.
Enumeration of Algorithms
- Discrete NDP
- Continuous NDP
- Iterative-Optimization-Assignment (IOA) algorithm
- The Sensitivity Analysis-based algorithm
- Other approaches
- Computational Intelligence
- Link Usage Proportion-Based algorithm
- Friesz, T. L., 1981, The Multi-objective 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:Springer-Verlag), pp, 116-127.
- 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):19-32, 1979
- Sheffi,Y., 1984. Urban transportation networks: equilibrium analysis with mathematical programming methods, Prentice-Hall Englewod Cliffs, N.J.
- Daganzo, C.F., Y. Sheffi. On Stochastic Models of Traffic Assignment. Transportation Science, Vol 11, No. 3, 1997, pp. 253-274.
- Davis, G.A., Exact local solution of the continuous network design problem via stochastic user equilibrium assignment. Transportation Research, 28B, 1994, pp.61-75.
- 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. 257-278, 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. 351-365
- Friesz,T.L., and Harker,P.T. properties of the iterative optimization-equilibrium algorithm,Civil Engineering Systems,2,1985,pp. 142-154.
- Wong,S. C., and Yang, H. Reserved capacity for a signal controlled road network, Transportation Research 31B, 1997,397-402.
- Yang, H., and Lam, W.H.K. Optimal road tolls under conditions of queuing and congestion. Transportation Research, 30A, 1996, 319-332.
- Yang, H., and Yagar, S. Traffic assignment and traffic control in general freeway-arterial corridor systems, Transportation Research ,28B, 1994, 463-485
- Yang, H., and Bell,M.G.H. Traffic restraint, road pricing and network equilibrium. Transportation Research, 31B, 1997, 303-314