Lindo Systems
! Find either user equilibrium, or system/social optimum for traffic
flow problem in a congested network. The time to transit
a link in the network is an increasing function of the
traffic on the link. At a user equilibrium, each user
chooses the shortest path from his origin to his destination.
The total travel time under the user equilibrium is
typically greater than the system optimum. Under a system
optimum, total delay time is minimized;
! Because of complementarity constraints, we should
turn on the Global Solver option by clicking on:
LINGO | Options | Global Solver | Use Global Solver
;
! Keywords: Braess Paradox, Complementarity constraint, Congestion,
Consumer Choice, Equilibrium, Network, System optimum,
Traffic Equilibrium, User Equilibrium;
sets:
Node; ! Nodes of the network;
Link( Node, Node): Bcost, Cap, TotFlo, ! Links of network;
ArcTime;
Trip( Node, Node): Dem; ! Trips to be routed in network;
Dest( Node) | @sum( Node(n): @IN( Trip, n, &1)); !Destination nodes;
Link4Dest( Link, Dest): X, Slk; ! (from, to, by destination) flow;
NXD( Node, Dest): R; ! Intermediate nodes to terminal nodes;
SYS /1..1/; ! Utility set, size 1, convenieht for conditional constraints;
endsets
! Parameters:
Dem(j,t) = flow that starts at j and wants to go to t,
Bcost(i,j) = travel cost(or delay, or travel time) from i to j when there is
no congestion,
Cap(i,j) = flow level from i to j at which congestion or
delay doubles, (and gets larger really fast).
UserOpt = 1 if we want User optimum/equilibrium, i.e., each
user chooses shortest path available, or
= 0 if we want System/social optimum, i.e., we direct
traffic so total delay is minimized.
Power = exponent for the flow which determines how travel
time increases with flow. 4 is a typical value used;
! Variables:
X(i,j,t) = flow from node i to j destined for t,
TotFlow(i,j) = total flow from i to j,
ArcTime(i,j) = congestion cost/delay from i to j,
R(i,t) = Remaining delay at i to get to destination t
by cheapest/fastest route,
Slk(i,j,t) = Difference in cost of going from i to j
to get to t, vs. going by the cheapest
route from i to destination t,
= ArcTime(i,j)+R(j,t) - R(i,t),
;
Data:
! Braess data set. The network is
C
/ ^ \
/ | \
A | D
\ | /
\ | /
B
!CBraess; UserOpt = 1; ! 0 => Social optimum, 1 => User equilibrium;
!CBraess; Scale = 1; ! Scale factor;
!CBraess; Power = 1; ! Exponent for congestion increase with flow;
!CBraess; Style = 1; ! ArcTime(i,j)= Bcost(i,j) + ( Cap(i,j)*TotFlo(i,j))^ Power;
!CBraess; Node = A B C D;
! From_node, To_node, Base/no_traffic cost, Capacity;
!CBraess; Link BCost Cap =
A B 0 10
A C 50 1
B C 10 1
B D 50 1
C D 0 10
;
! Trip data: origin, destination, trips;
!CBraess; Trip Dem =
A D 6
;
! Data set 2;
! Choose either User optimum (1), or system/social optimum(0);
!Ctraflo2 UserOpt = 1;
!Ctraflo2 Scale = 1; ! Scale factor;
!Ctraflo2 Node = A B C D E; ! Nodes of network;
!Ctraflo2 Power = 4; ! Exponent for congestion increase with flow;
!Ctraflo2 Style = 0; ! ArcTime(i,j)=
Bcost(i,j)*(1 + Scale*( TotFlo(i,j)/Cap(i,j))^ Power);
! Trips people want to make and number
per minute wishing to make the trips;
! Ctraflo2
Trip Dem =
A D 60
E C 5;
! Links of network and congestion parameters;
!Ctraflo2
Link BCost Cap =
A B 25.3714 45.9034
A C 51.7539 76.1578
B C 11.7538 52.5742
B D 51.7539 76.1578
C D 25.3714 45.9034
E A 11.7539 52.5743
E B 51.7539 76.1577;
! This data set can illustrate the Braess Paradox if
we set the demand from E to C = 0.
First, solve for the resulting user equilibrium(Useropt=1),
Next, make link B to C really unattractive by
setting BCost for B to C = 9999999.
Finally, solve again and notice that this removal of an
arc from the network made everyone's travel
time or cost lower;
! Case Sious Falls. This is a subset of the Sioux Falls data set;
! Network structure:
1--------------------2
| |
3------4------5------6
| | | |
| | 9------8------7
| | | | |
12-----11-----10-----16-----18
| | | \ | |
| | | \ | |
| | | 17 /
| | | | /
| 14-----15-----19 /
| | | | /
| 23-----22 | /
| | | \ | /
| | | \ |/
13-----24-----21-----20
;
!CSioux UserOpt = 0; ! 0 => Social optimum, 1 => User equilibrium;
!CSioux Scale = .03; ! Scale factor;
!CSioux Power = 4; ! Exponent for congestion increase with flow;
!CSioux Style = 0; ! ArcTime(i,j)=
Bcost(i,j)*(1 + Scale*( TotFlo(i,j)/Cap(i,j))^ Power);
!CSioux Node = 1..10;
! From_node, To_node, Base/no_traffic cost, Capacity;
!CSioux Link BCost Cap =
1 2 6.0008 25900.20
2 1 6.0008 25900.20 ! Add node 2 to network;
!CSioux 3 1 1.0000 23403.47 ! Add node 3 to network;
!CSioux 1 3 1.0000 23403.47
3 4 4.0000 17110.52 ! Add 4;
!CSioux 4 3 4.0000 17110.52
4 5 2.0000 17782.79 ! Add 5;
!CSioux 5 4 2.0000 17782.79
2 6 5.0000 4958.18 ! 6;
!CSioux 6 2 5.0000 4958.18
5 6 4.0000 4948.00
6 5 4.0000 4948.00
6 8 2.0000 4898.59 ! 8;
!CSioux 8 6 2.0000 4898.59
8 7 3.0000 7841.81 ! 7;
!CSioux 7 8 3.0000 7841.81
9 8 10.0000 5050.19 ! 9;
!CSioux 8 9 10.0000 5050.19
5 9 5.0000 10000.00
9 5 5.0000 10000.00
9 10 3.0000 13915.79 ! 10;
!CSioux 10 9 3.0000 13915.79;
! Trip data: origin, destination, trips;
!CSioux Trip Dem =
1 2 100 ! Add node 2;
!CSioux 2 1 100
1 3 100 ! Add node 3;
!CSioux 3 1 100
2 3 100
3 2 100
1 4 500 ! Add node 4;
!CSioux 4 1 500
2 4 200
4 2 200
3 4 200
4 3 200
1 5 200 ! Node 5;
!CSioux 5 1 200
2 5 100
5 2 100
3 5 100
5 3 100
4 5 500
5 4 500
1 6 300 ! Node 6;
!CSioux 6 1 300
2 6 400
6 2 400
3 6 300
6 3 300
4 6 400
6 4 400
5 6 200
6 5 200
1 8 800 ! 8;
!CSioux 8 1 800
2 8 400
8 2 400
3 8 200
8 3 200
4 8 700
8 4 700
5 8 500
8 5 500
6 8 800
8 6 800
1 7 500 ! 7;
!CSioux 7 1 500
2 7 200
7 2 200
3 7 100
7 3 100
4 7 400
7 4 400
5 7 200
7 5 200
6 7 400
7 6 400
8 7 1000
7 8 1000
1 9 500 ! 9;
!CSioux 9 1 500
2 9 200
9 2 200
3 9 100
9 3 100
4 9 700
5 9 800
6 9 400
9 6 400
7 9 600
9 7 600
8 9 800
9 8 800
1 10 1300 !10;
!CSioux 10 1 1300
2 10 600
10 2 600
3 10 300
10 3 300
4 10 1200
10 4 1200
5 10 1000
10 5 1000
6 10 800
10 6 800
7 10 1900
10 7 1900
8 10 1600
10 8 1600
9 10 2800
10 9 2800
;
Enddata
!Compute total flow on each arc;
@for(Link(i,j): [Def]
TotFlo(i,j)=@sum(Link4Dest(i,j,t): X(i,j,t))
);
!Conservation of flow,
for each origin j and destination t:
flow into j destined for t + flow originating
at j destined for t
= flow out of j destined for t;
@for( trip(j,t): [Origin]
@sum(Link4Dest(i,j,t): X(i,j,t)) + Dem(j,t) =
@sum(Link4Dest(j,k,t): X(j,k,t))
);
!Conservation of flow,
for each node j and destination t
for which j is not an origin for flow to t and j #NE# t:
flow into j destined for t = flow out of j destined for t;
@for( NXD(j,t) | (#NOT# @in( Trip,j,t)) #AND# (j #NE# t) :
[Inter] @sum( Link4Dest(i,j,t): X(i,j,t))=
@sum( Link4Dest(j,k,t): X(j,k,t))
);
! Compute travel time on Link i,j;
@for( SYS | Style #EQ# 0:
@for( Link(i,j): [CCon0]
ArcTime(i,j) =
Bcost(i,j)*(1 + Scale*( TotFlo(i,j)/Cap(i,j))^ Power)
);
);
@for( SYS | Style #EQ# 1:
@for( Link(i,j): [CCon1]
ArcTime(i,j) =
Bcost(i,j) + ( TotFlo(i,j)* Cap( i, j))^ Power
);
);
! Enforce user equilibrium ( if UserOpt = 1);
! For destination node t, the remaining time/cost
to get there is 0;
@for( Dest(t)| UserOpt: R(t,t) = 0);
! For the other nodes i;
@for( Dest(t)| UserOpt:
@for( Link(i,j) | i #NE# t:
[sdf] Slk(i,j,t) = ArcTime(i,j) + R(j,t) - R(i,t);
! Complementarity constraints. If Slk(i,j,t) > 0,then
we cannot use link i,j to get to t;
Slk(i,j,t)*X(i,j,t) = 0;
);
);
! Compute system cost;
SysCost = @sum(Link(i,j): TotFlo( i, j)*ArcTime( i, j));
! To minimize System cost or find Social optimum,
turn on the following, and turn off complemenarity constraints;
! Min = (1-UserOpt)*SysCost;
Min = SysCost;