# 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.

### Types of Network Design Problem

• Discrete Network Design Problem
• 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.

### Bi-Level Framework

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
${\displaystyle \min \limits _{x\in X}\;\;F(x,y(x))}$

subject to:

${\displaystyle G(x,y(x))\leq 0,\;\;}$

where ${\displaystyle y(x)}$ is a solution to the following optimization problem for any fixed ${\displaystyle x\in X}$

${\displaystyle \min \limits _{y\in Y}\;\;f(x,y)}$

subject to: ${\displaystyle g(x,y)\leq 0}$

#### 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)[4].

For example, under DUE when the link travel cost function (${\displaystyle t_{a}}$)is assumed to be separable( such as BPR function), the lower level optimization problem, i.e. solution to y(x)can be written as

${\displaystyle \min \limits _{v}\sum _{a\in A}{\int _{0}^{v_{a}}{t_{a}\left(w,x\right)}dw}}$

subject to

${\displaystyle v_{a}=\sum _{i\in I}\sum _{j\in J}\sum _{r\in P_{ij}}f_{r}^{ij}\delta _{ar}^{ij}}$
${\displaystyle \sum _{r\in P_{ij}}f_{r}^{ij}=q_{ij}(x),f_{r}^{ij}\geq 0,r\in P_{ij},i\in I,j\in J}$

where ${\displaystyle v_{a}}$ is the flow on link ${\displaystyle a}$, ${\displaystyle f_{r}^{ij}}$ is the path flow on route ${\displaystyle r}$ between ${\displaystyle i}$ and ${\displaystyle j}$ and ${\displaystyle \delta }$ is the link-path incidence matrix. SUE counterpart of the user equilibrium can be also found in the relevant literature[5],[6]. Since NDP generally involves long-term 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.

#### Upper-Level Optimization

Depending upon the objective different upper level objective functions can be formulated[7].

1. Minimize total network cost at equilibrium
${\displaystyle \max _{u}F\left(u,v(u)\right)=\sum _{a\in A}t_{a}(u).v_{a}(u)}$

subject to:

${\displaystyle \sum _{a\in A}g_{a}(u_{a})\leq B,\;\;\ 0\leq u_{a}\leq u_{a}^{max},\;\;\ a\in A}$
where ${\displaystyle u_{a}}$ is the continuous capacity increase of link ${\displaystyle a}$ and ${\displaystyle g_{a}(u_{a})}$ 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:

${\displaystyle \max _{\mu u}\;\mu }$

subject to

${\displaystyle v_{a}(\mu d,u)\leq C_{a}(u_{a}),\;\ a\in A}$

where ${\displaystyle v_{a}\left(\mu d,u\right)}$ represents equilibrium flow on link ${\displaystyle a\in A}$ when each O-D pair is increased by ${\displaystyle \mu }$ 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:

${\displaystyle \max _{u}\;\ F\left(u,d(u),v(u)\right)=\sum _{w\in W}{\int _{0}^{d_{w}}D_{w}^{-1}(x)dx-c_{w}d_{w}}}$

where ${\displaystyle D_{w}^{-1}}$ is the inverse of the monotonically decreasing demand function, ${\displaystyle D_{w}\left(c_{w}\right)}$ for O-D pair ${\displaystyle w}$.

## 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, ${\displaystyle f_{i}\left(x_{1},x_{2}\right)}$, where ${\displaystyle x_{i}}$ is the decision variable for ${\displaystyle i^{t}h}$ in the game. Then ${\displaystyle (x_{1}^{*},x_{2}^{*})}$ is the Nash equilibrium solution if

${\displaystyle f_{1}\left(x_{1},x_{2}^{*}\right)\geq f_{1}\left(x_{1}^{*},x_{2}^{*}\right)}$
${\displaystyle f_{1}\left(x_{1}^{*},x_{2}\right)\geq f_{1}\left(x_{1}^{*},x_{2}^{*}\right)}$

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), ${\displaystyle x_{2}=Y\left(x_{1}\right)}$,where ${\displaystyle x_{1}}$ is the decision made by leader(player 1). Stackelberg equilibrium solution can be obtained by solving following optimization problem:

${\displaystyle \min \limits _{x_{1}}f\left(x_{1},Y(x_{1})\right)}$, where
${\displaystyle Y\left(x_{1}\right)}$ is the solution to the lower level optimization problem for any given ${\displaystyle x_{1}}$ i.e.
${\displaystyle \min \limits _{x_{2}}f\left(x_{1},x_{2}\right)}$

Similar to Nash solution, Stackelberg equilibrium solution, ${\displaystyle \left(x_{1}^{*},x_{2}^{*}\right)}$ satisfies following inequalities

${\displaystyle f_{1}\left(x_{1},Y(x_{1})\right)\geq f_{1}\left(x_{1}^{*},Y(x_{1}^{*})\right)}$
${\displaystyle f_{2}\left(x_{1},Y(x_{1})\right)\leq f_{2}\left(x_{1},x_{2}\right)}$

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
Branch and Bound
• Continuous NDP
Iterative-Optimization-Assignment (IOA) algorithm[8][9]
The Sensitivity Analysis-based algorithm[10][11]
• Other approaches
Computational Intelligence
Genetic algorithm
Simulated annealing

## References

1. 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.
2. L. Leblanc. An algorithm for the discrete network design problem. Transportation Science, 9(3): 183, 1975
3. M. Abdulaal and L. LeBlanc. Continuous equilibrium network design models. "Transportation Research Part B: Methodological, 13(1):19-32, 1979
4. a b Sheffi,Y., 1984. Urban transportation networks: equilibrium analysis with mathematical programming methods, Prentice-Hall Englewod Cliffs, N.J.
5. Daganzo, C.F., Y. Sheffi. On Stochastic Models of Traffic Assignment. Transportation Science, Vol 11, No. 3, 1997, pp. 253-274.
6. Davis, G.A., Exact local solution of the continuous network design problem via stochastic user equilibrium assignment. Transportation Research, 28B, 1994, pp.61-75.
7. 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.
8. 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
9. Friesz,T.L., and Harker,P.T. properties of the iterative optimization-equilibrium algorithm,Civil Engineering Systems,2,1985,pp. 142-154.
10. Wong,S. C., and Yang, H. Reserved capacity for a signal controlled road network, Transportation Research 31B, 1997,397-402.
11. Yang, H., and Lam, W.H.K. Optimal road tolls under conditions of queuing and congestion. Transportation Research, 30A, 1996, 319-332.
12. Yang, H., and Yagar, S. Traffic assignment and traffic control in general freeway-arterial corridor systems, Transportation Research ,28B, 1994, 463-485
13. Yang, H., and Bell,M.G.H. Traffic restraint, road pricing and network equilibrium. Transportation Research, 31B, 1997, 303-314