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

Introduction

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.

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

$\min \limits _{x\in X}\;\;F(x,y(x))$

subject to:

$G(x,y(x))\leq 0,\;\;$

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

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

subject to: $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).

For example, under DUE when the link travel cost function ($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

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

subject to

$v_{a}=\sum _{i\in I}\sum _{j\in J}\sum _{r\in P_{ij}}f_{r}^{ij}\delta _{ar}^{ij}$

$\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 $v_{a}$ is the flow on link $a$, $f_{r}^{ij}$ is the path flow on route $r$ between $i$ and $j$ and $\delta$ 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.

Upper-Level Optimization

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

1. Minimize total network cost at equilibrium

$\max _{u}F\left(u,v(u)\right)=\sum _{a\in A}t_{a}(u).v_{a}(u)$

subject to:

$\sum _{a\in A}g_{a}(u_{a})\leq B,\;\;\ 0\leq u_{a}\leq u_{a}^{max},\;\;\ a\in A$

where $u_{a}$ is the continuous capacity increase of link $a$ and $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:

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

subject to

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

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

$\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 $D_{w}^{-1}$ is the inverse of the monotonically decreasing demand function, $D_{w}\left(c_{w}\right)$ for O-D pair $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, $f_{i}\left(x_{1},x_{2}\right)$, where $x_{i}$ is the decision variable for $i^{t}h$ in the game. Then $(x_{1}^{*},x_{2}^{*})$ is the Nash equilibrium solution if

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

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

$\min \limits _{x_{1}}f\left(x_{1},Y(x_{1})\right)$, where

$Y\left(x_{1}\right)$ is the solution to the lower level optimization problem for any given $x_{1}$ i.e.

$\min \limits _{x_{2}}f\left(x_{1},x_{2}\right)$

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

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

$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

The Sensitivity Analysis-based algorithm

• Other approaches

Computational Intelligence

Genetic algorithm

Simulated annealing

Link Usage Proportion-Based algorithm