# Joint Implementation of Signal Control and Congestion Pricing in Transportation Network

Authors: Wei Mao; Feifei Qin; Yihong Hu; Zhijia Tan
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The policy of jointly implementing signal control and congestion pricing in the transportation network is investigated. Bilevel programs are developed to model the simultaneous optimization of signal setting and congestion toll. The upper level aims to maximize the network reserve capacity or minimize the total travel time, subject to signal setting and toll constraints. The lower level is a deterministic user equilibrium problem given a plan of signal setting and congestion charge. Then the bilevel programs are transferred into the equivalent single level programs, and the solution methods are discussed. Finally, a numerical example is presented to illustrate the concepts and methods, and it is shown that the joint implementation policy can achieve promising results.


---

## Body

## 1. Introduction

As a result of urbanization and industrialization, almost all big cities in the world face serious problems of traffic congestion. Therefore, it becomes more and more important to mitigate traffic congestion and to enhance the potential reserve capacity of road networks. Over the past forty years, many researchers investigated various management methods, such as signal control [1–4], congestion pricing [5–13], route guidance [14], and credit management [15, 16] to improve the network performance.In the previous studies of traffic management, some researchers set their objective functions to be the minimization of the total travel time over the whole network [8, 15]. Furthermore, enhancing network capacity is also often used as an alternative objective function in traffic management [10, 17]. In those cases, network capacity is defined as the maximal demand that can be accommodated in the network, without violating capacity constraints of the links.In the analysis of traffic management, scholars often use single approach for traffic management, and the combined methods are seldom utilized. With the rapid development of intelligent computing and control technologies [18, 19], it becomes more feasible to jointly implement various traffic management approaches. Due to lack of analytical research on the joint implementation of signal control and congestion pricing, the purpose of this paper is to present a policy of simultaneously optimizing traffic signal setting and congestion toll. Furthermore, both reserve capacity maximization and travel time minimization are used as the objectives of the policy planner.The proposed problem is formulated as a Stackelberg game with the bilevel optimization structure. The upper level either minimizes total travel time or maximizes network reserve capacity with both signal setting parameters and congestion tolls as control variables. The lower level is a deterministic user equilibrium (DUE) problem given the signal setting and tolls assigned by the upper level. After replacing the lower level traffic assignment problem with its first order conditions, the proposed bilevel problem can be transferred into its equivalent single level formulation. By transferring the objective functions and link cost functions into piecewise linear functions, the whole problem becomes a linear program that can be solved by using commercial computing package, such as CPLEX.The remainder of the paper is organised as follows. The bilevel programs that combine traffic problems are formulated in Section2. In Section 3, the bilevel models are then transferred into single level models, and their linearized formulations are also discussed. Section 4 presents the numerical example and discussed results. Conclusions are provided in Section 5.


## 2. Bilevel Formulation of Improving Network Capacity with Simultaneous Implementation of Signal Control and Congestion Pricing

LetG=(N,A) be a directed transportation network defined by a set N of nodes and a set A of directed links. Each link (a∈A) has an associated flow-dependent travel time, ta(va), which presents the travel time per unit flow or average travel time on each link. The travel time function, ta(va), is assumed to be differentiable and monotonically increasing with the traffic flow, va. Let W denote the set of origin-destination (O-D) pairs and let Pw be the set of all paths between O-D pair. Each feasible path, p∈Pw, between O-D pair has a travel time tpw=∑a∈Ata(va)δapw. Herein δapw equals 1 if the path p between O-D pair uses link a, and 0 otherwise. The existing demand between O-D pair is denoted as qwsuch that q is the vector of qw.The set of signal-controlled intersections is denoted asI(I⊂N). Meanwhile, let Ai be the set of links entering the signalized intersection and let A¯ be the set of all signal-controlled links, A¯={Ai,i∈I}.The signal timing variables for links approaching a given signalized intersection should satisfy some linear constraints, which include cycle time, clearance time, and minimum and maximum green times. These constraints can be mathematically described in the following form:(1)Giλi≥bi,i∈I,
where λi is a vector of timing variables associated with signalized intersection. Both the matrix Gi and vector bi depend on the particular timing specification for intersection, whether it is stage based or group based. For more detailed descriptions, the reader may refer to Allsop [20].In this paper, we allow for link based tolls, which means a certain amount of toll (τa) is imposed on link a. Let τ be the vector of link-based toll, τa. After transferring the monetary cost τa into the equivalent cost in time unit according to the value of time (VOT), ρ, the generalized travel cost (GTC) (including both travel time and toll charge) of passing link a is ta(va,λ)+(τa/ρ). Here, we assume J(J⊆A) to be the set of toll links.


### 2.1. Bilevel Model of Minimizing Total Travel Time

The travel time minimization problem over the whole network can be modelled by a bilevel program, or a Stackelberg game. In such a leader-follower game, the leader cannot directly control the decision of the follower, but it can affect the behaviour of the follower by making its own decisions and anticipating the results. However, the follower can only react according to the decisions of the leader. In this study, the transport system planner is viewed as the leader, and its decision variables are signal setting and congestion tolls. The followers are travellers, and their route choice behaviours can be characterized by a deterministic traffic assignment, given the decisions made by the leader.The behaviour of the leader, namely, the upper level problem, is given below(2)minv,τ,λ∑a∈Ata(va,λ)va(λ,τ)s.t.Giλi≥bi,i∈Iτju≥τj≥τjl,j∈J,
where v(λ,τ) is the vector of link traffic volume. va(λ,τ) represents an equilibrium traffic flow which obtains from the following lower-level program [5]:
(3)minv∑a∈A∫0vata(ω,λ)dω+∑j∈Jvjτjρ(4)s.t.∑p∈Pwfpw=qw,w∈Wva=∑w∈W∑p∈Pwfpwδapw,a∈Afpw≥0,p∈Pw,w∈W.


### 2.2. Bilevel Model of Maximizing Network Reserve Capacity

In this subsection, we introduce the bilevel program of network reserve capacity maximization, which is jointly implementing signal control and congestion pricing. If the current OD matrix is multiplied by a factorμ, then it becomes μq. Given the new demand matrix μq, link flow v can be obtained by solving a traffic assignment based on the vector of the signal timing variables λ for all signalized intersections and the vector τ of congestion tolls. If the degree of saturation on any link does not exceed a prescribed benchmark value of that link at the equilibrium condition, the congestion and emission in the network are acceptable. Namely, the following condition has to be satisfied:
(5)va(μ,λ,τ)≤paCa(λ),a∈A,
where Ca(λ) is the capacity of link which is dependent on the signal timings (λ). Furthermore, va(μ,λ,τ) is the equilibrium traffic flow of link a that depends on the demand multiplier, signal settings, and congestion tolls. Parameter pa is the maximum acceptable degree of saturation for link a. The above constraint should be fulfilled for links at closely spaced intersections, since queues block neighbour intersections and congestion would spread over the whole network.The largest multiplier of the O-D matrix that can be accommodated without violating the capacity constraints can be obtained by maximizingμ within the feasible region defined by the constraints for all links. Let the maximum acceptable value of OD multiplier  μ be μ*. Therefore, if μ*>1 the network has reserve capacity of 100(μ*-1)q, and if μ*<1 the network is overloaded by 100(1-μ*)q.The combined signal control and congestion pricing optimization problem is formulated as a bilevel model or a Stackelberg game. The leader, namely, the system planner aims to maximize the network reserve capacity, by setting appropriate signals and tolls, whereas the follower, namely, travellers follow deterministic user equilibrium in terms of the generalized travel cost (GTC), which describes the minimum-cost path finding behavior of drivers in the transportation networks. Consequently, the upper level program is given by(6)Maximiseμ,λ,τμ(7)subjecttova(μ,λ,τ)≤paCa(λ),a∈AGiλi≥bi,i∈Iτju≥τj≥τjl,j∈J,
where the equilibrium flow va(μ,λ,τ) is obtained by solving the following lower-level network equilibrium problem:
(8)minv∑a∈A∫0vata(ω,λ)dω+∑j∈Jvjτjρ(9)subjectto∑pϵPwμqw,wϵWva=∑wϵW∑pϵPwfpwδap,aϵAfpw≥0,pϵPw,wϵW.


## 2.1. Bilevel Model of Minimizing Total Travel Time

The travel time minimization problem over the whole network can be modelled by a bilevel program, or a Stackelberg game. In such a leader-follower game, the leader cannot directly control the decision of the follower, but it can affect the behaviour of the follower by making its own decisions and anticipating the results. However, the follower can only react according to the decisions of the leader. In this study, the transport system planner is viewed as the leader, and its decision variables are signal setting and congestion tolls. The followers are travellers, and their route choice behaviours can be characterized by a deterministic traffic assignment, given the decisions made by the leader.The behaviour of the leader, namely, the upper level problem, is given below(2)minv,τ,λ∑a∈Ata(va,λ)va(λ,τ)s.t.Giλi≥bi,i∈Iτju≥τj≥τjl,j∈J,
where v(λ,τ) is the vector of link traffic volume. va(λ,τ) represents an equilibrium traffic flow which obtains from the following lower-level program [5]:
(3)minv∑a∈A∫0vata(ω,λ)dω+∑j∈Jvjτjρ(4)s.t.∑p∈Pwfpw=qw,w∈Wva=∑w∈W∑p∈Pwfpwδapw,a∈Afpw≥0,p∈Pw,w∈W.


## 2.2. Bilevel Model of Maximizing Network Reserve Capacity

In this subsection, we introduce the bilevel program of network reserve capacity maximization, which is jointly implementing signal control and congestion pricing. If the current OD matrix is multiplied by a factorμ, then it becomes μq. Given the new demand matrix μq, link flow v can be obtained by solving a traffic assignment based on the vector of the signal timing variables λ for all signalized intersections and the vector τ of congestion tolls. If the degree of saturation on any link does not exceed a prescribed benchmark value of that link at the equilibrium condition, the congestion and emission in the network are acceptable. Namely, the following condition has to be satisfied:
(5)va(μ,λ,τ)≤paCa(λ),a∈A,
where Ca(λ) is the capacity of link which is dependent on the signal timings (λ). Furthermore, va(μ,λ,τ) is the equilibrium traffic flow of link a that depends on the demand multiplier, signal settings, and congestion tolls. Parameter pa is the maximum acceptable degree of saturation for link a. The above constraint should be fulfilled for links at closely spaced intersections, since queues block neighbour intersections and congestion would spread over the whole network.The largest multiplier of the O-D matrix that can be accommodated without violating the capacity constraints can be obtained by maximizingμ within the feasible region defined by the constraints for all links. Let the maximum acceptable value of OD multiplier  μ be μ*. Therefore, if μ*>1 the network has reserve capacity of 100(μ*-1)q, and if μ*<1 the network is overloaded by 100(1-μ*)q.The combined signal control and congestion pricing optimization problem is formulated as a bilevel model or a Stackelberg game. The leader, namely, the system planner aims to maximize the network reserve capacity, by setting appropriate signals and tolls, whereas the follower, namely, travellers follow deterministic user equilibrium in terms of the generalized travel cost (GTC), which describes the minimum-cost path finding behavior of drivers in the transportation networks. Consequently, the upper level program is given by(6)Maximiseμ,λ,τμ(7)subjecttova(μ,λ,τ)≤paCa(λ),a∈AGiλi≥bi,i∈Iτju≥τj≥τjl,j∈J,
where the equilibrium flow va(μ,λ,τ) is obtained by solving the following lower-level network equilibrium problem:
(8)minv∑a∈A∫0vata(ω,λ)dω+∑j∈Jvjτjρ(9)subjectto∑pϵPwμqw,wϵWva=∑wϵW∑pϵPwfpwδap,aϵAfpw≥0,pϵPw,wϵW.


## 3. Transformation to an Equivalent Single Level Formulation

Obviously, the proposed models are very difficult to solve due to their bilevel structure. In this section, we transfer the bilevel models into the single-level program and approximate them into a set of mixed integer linear programs. Therefore, they can be solved by commercial software, such as CPLEX.


### 3.1. Equivalent Single-Level Model of Minimizing Total Travel Time

First, we replace the user equilibrium traffic assignment problem with its first order condition. Accordingly, the total travel time minimization problem becomes a single-level formulation:(10)minx,λ,τZ=∑a∈Ata(xa,λ)xa(11)s.t.Giλi≥bi,i∈I(12)τju≥τj≥τjl,j∈J(13)∑p∈Pwfpw=qw,w∈W,(14)va=∑w∈W∑p∈Pwfpwδapw,a∈A,(15)cpw=∑a∈Ata(va,λ)δapw+∑j∈Jτjδjpwρ,(16)fpw(cpw-πw)=0,p∈Pw,w∈W,(17)cpw-πw≥0,p∈Pw,w∈W,(18)fpw≥0,p∈Pw,
where πw represents the least travel cost, including both travel time and toll of OD pair w. The symbol cpw denotes the generalized travel cost in the path p.In the above proposed model, constraints (16)–(18) represent the deterministic route choice behaviour. Clearly this complementary condition is nonlinear and nonconvex, so it cannot be put into a linear program. Fortunately, Wang and Lo [21] formulated it into a set of mixed-integer constraints, as below
(19)Lφpw+ε≤fpw≤U(1-φpw),p∈Pw,w∈W,φpw∈{0,1},p∈Pw,w∈W,Lφpw≤cpw-πw≤Uφpw,p∈Pw,w∈W,cpw-πw≥0,p∈Pw,w∈W,
where L represents a negative constant with a very large absolute value, U is viewed as a very large positive constant, while ε is treated a very small positive value. And φpw is a binary variable. Specifically, if φpw=0, one has fpw>0 and cpw=πw. If φpw=1, one has fpw=0 and cpw>πw. These two cases of φpw are exactly equivalent to the above complementary condition. Therefore, conditions (16)–(18) can be replaced by conditions (19).If we letTa(xa,λ)=ta(xa,λ)xa, the objective function becomes ∑a∈ATa(xa,λ). If ta(xa,λ) and Ta(xa,λ) are transferred into linear functions, the above problem is a linear program. Fortunately, ta(xa,λ) and Ta(xa,λ) can be approximated by a piecewise linear function with multiple segments. Let λk be the kth variable in the vector λ, and K is the cardinality of λ. The feasible domain of va, [v_a,v¯a] is partitioned into N segments, and the feasible domain of λk, [λ_k,λ¯k] is partitioned into M segments, respectively. Theoretically, the accuracy of linearizing ta(xa,λ) can be guaranteed by setting sufficiently large N and M. In this study, for each link a, a series of values of Va,n are used to partition the feasible domain of va into many small segments, where v_a<Va,n<Va,n+1<v¯a,(n=1,…N-1). We denote [Va,n,Va,n+1] as the region n of va. Similarly a series of values of Zk,m are used to partition the feasible domain of λk into many small segments, where λ_k<Zk,m<Zk,m+1<λ¯k,(m=1,…,M-1). We denote [Zk,m,Vk,m+1] as region m of λk. For each region (n,m1,…,mk,…,mK), the following linear function is specified to approximate the nonlinear travel time function, ta(xa,λ)(20)ta(va,λ)=Enava+∑k=1KFmkλk+Gm1,…,mk,…,mKa,nifUa,n≤va≤Ua,n+1,Zk,m≤λk≤Zk,m+1,
where Ena and Fmk are coefficients. The first-order Taylor series is applied to approximate the travel time function ta(xa,λ). Therefore, the coefficients Ena and Fmk are determined by the derivatives of the travel time function with respect to va and λk that are evaluated at Va,n and Zk,m, namely,
(21)Ena=∂ta∂va|(Va,n,Z1,m1,…,Zk,mk,…ZK,mK).Fmk=∂ta∂λi|(Va,n,Z1,m1,…,Zk,mk,…ZK,mK).
And the coefficient Gm1,…,mk,…,mKa can be evaluated by equating the values of the original function and the piecewise linear approximated function at Ua,n and Vλk,mk, and thus given by
(22)Gm1,…,mk,…,mKa,n=ta(Va,n,Z1,m1,…,Zk,mk,…ZK,mK)-Va,n∂ta∂va|(Va,n,Z1,m1,…,Zk,mk,…ZK,mK)-∑k=1KZk,mk∂ta∂λk|(Va,n,Z1,m1,…,Zk,mk,…ZK,mK).
Subsequently, the piecewise linear travel time function of each link is transferred into the following equivalent mixed-integer linear constraints:
(23)L·ξa,n≤va-Va,n≤U·(1-ξa,n)-ε,θa,n=ξa,n+1-ξa,n,L·ςmk≤λi-Zk,mk≤U·(1-ςmk)-ε,ϑmk=ςmk+1-ξmk,ψn,m1,…,mk,…,mKa=θa,n+∑k=1Kϑmk,L·(K+1-ψm1,…,mk,…,mKa,n)≤ta-(Enava+∑k=1KFmkλk)≤U·(K+1-ψm1,…,mk,⋯,mKa,n),ξa,n∈{0,1},ςmk∈{0,1},n=1,2,…,N,mk=1,2,…,M,∀a∈A,
where L and U still represent very large negative and positive constants, respectively. And ε is still a very small positive constant. The binary variable ξa,n indicates the comparison between va and Va,n. Specifically, ξa,n=0 indicates va≥Va,n, ξa,n=1 indicates va<Ua,n. Thus θa,n indicates whether va falls in segment n or not. If θa,n=1, va is in segment n. Similarly, ϑmk=1 means λk falls in segment mk. If ψm1,…,mk,…,mKa,n=K+1, then the corresponding approximated linear function in the region (n,m1,…,mk,…,mK) is utilized, namely, ta=Enava+∑k=1KFmkλk+Gm1,…,mk,…,mKa,n. In this way, all the nonlinear constraints of the single-level formulation have been transferred into linear ones.Tracing the same way,Ta(xa,λ) can be approximated into linear functions. Thus the whole problem becomes a mixed integer linear program, which can be solved by commercial software, such as CPLEX.


### 3.2. Equivalent Single-Level Model of Maximizing Network Reserve Capacity

If the lower level problem is replaced with its first order condition, the combined signal control and pricing problem with the objective of maximizing reserve capacity can be transferred into a single-level formulation, as below(24)Maximiseμ,λ,τμ(25)s.t.va(μ,λ,τ)≤paCa(λ),a∈A¯Giλi≥bi,i∈I,τju≥τj≥τjl,j∈J,∑p∈Pwfpw=μqw,w∈W,va=∑w∈W∑p∈Pwfpwδapw,a∈A,cpw=∑a∈Ata(va,λ)δapw+∑j∈Jτjδjpwρ,Lφpw+ε≤fpw≤U(1-φpw),p∈Pw,w∈W,φpw∈{0,1},p∈Pw,w∈W,Lφpw≤cpw-πw≤Uφpw,p∈Pw,w∈W,cpw-πw≥0,p∈Pw,w∈W,fpw≥0,p∈Pw,
where πw represents the minimum generalized travel cost of OD pair w. Notation cpw denotes the generalized travel cost of path p. Furthermore, f, c, and π are vectors of fpw, cpw, and πw, respectively.In this program, the objective function is obviously a linear function. Andta(xa,λ) can also be linearized as done in Section 3.1.


## 3.1. Equivalent Single-Level Model of Minimizing Total Travel Time

First, we replace the user equilibrium traffic assignment problem with its first order condition. Accordingly, the total travel time minimization problem becomes a single-level formulation:(10)minx,λ,τZ=∑a∈Ata(xa,λ)xa(11)s.t.Giλi≥bi,i∈I(12)τju≥τj≥τjl,j∈J(13)∑p∈Pwfpw=qw,w∈W,(14)va=∑w∈W∑p∈Pwfpwδapw,a∈A,(15)cpw=∑a∈Ata(va,λ)δapw+∑j∈Jτjδjpwρ,(16)fpw(cpw-πw)=0,p∈Pw,w∈W,(17)cpw-πw≥0,p∈Pw,w∈W,(18)fpw≥0,p∈Pw,
where πw represents the least travel cost, including both travel time and toll of OD pair w. The symbol cpw denotes the generalized travel cost in the path p.In the above proposed model, constraints (16)–(18) represent the deterministic route choice behaviour. Clearly this complementary condition is nonlinear and nonconvex, so it cannot be put into a linear program. Fortunately, Wang and Lo [21] formulated it into a set of mixed-integer constraints, as below
(19)Lφpw+ε≤fpw≤U(1-φpw),p∈Pw,w∈W,φpw∈{0,1},p∈Pw,w∈W,Lφpw≤cpw-πw≤Uφpw,p∈Pw,w∈W,cpw-πw≥0,p∈Pw,w∈W,
where L represents a negative constant with a very large absolute value, U is viewed as a very large positive constant, while ε is treated a very small positive value. And φpw is a binary variable. Specifically, if φpw=0, one has fpw>0 and cpw=πw. If φpw=1, one has fpw=0 and cpw>πw. These two cases of φpw are exactly equivalent to the above complementary condition. Therefore, conditions (16)–(18) can be replaced by conditions (19).If we letTa(xa,λ)=ta(xa,λ)xa, the objective function becomes ∑a∈ATa(xa,λ). If ta(xa,λ) and Ta(xa,λ) are transferred into linear functions, the above problem is a linear program. Fortunately, ta(xa,λ) and Ta(xa,λ) can be approximated by a piecewise linear function with multiple segments. Let λk be the kth variable in the vector λ, and K is the cardinality of λ. The feasible domain of va, [v_a,v¯a] is partitioned into N segments, and the feasible domain of λk, [λ_k,λ¯k] is partitioned into M segments, respectively. Theoretically, the accuracy of linearizing ta(xa,λ) can be guaranteed by setting sufficiently large N and M. In this study, for each link a, a series of values of Va,n are used to partition the feasible domain of va into many small segments, where v_a<Va,n<Va,n+1<v¯a,(n=1,…N-1). We denote [Va,n,Va,n+1] as the region n of va. Similarly a series of values of Zk,m are used to partition the feasible domain of λk into many small segments, where λ_k<Zk,m<Zk,m+1<λ¯k,(m=1,…,M-1). We denote [Zk,m,Vk,m+1] as region m of λk. For each region (n,m1,…,mk,…,mK), the following linear function is specified to approximate the nonlinear travel time function, ta(xa,λ)(20)ta(va,λ)=Enava+∑k=1KFmkλk+Gm1,…,mk,…,mKa,nifUa,n≤va≤Ua,n+1,Zk,m≤λk≤Zk,m+1,
where Ena and Fmk are coefficients. The first-order Taylor series is applied to approximate the travel time function ta(xa,λ). Therefore, the coefficients Ena and Fmk are determined by the derivatives of the travel time function with respect to va and λk that are evaluated at Va,n and Zk,m, namely,
(21)Ena=∂ta∂va|(Va,n,Z1,m1,…,Zk,mk,…ZK,mK).Fmk=∂ta∂λi|(Va,n,Z1,m1,…,Zk,mk,…ZK,mK).
And the coefficient Gm1,…,mk,…,mKa can be evaluated by equating the values of the original function and the piecewise linear approximated function at Ua,n and Vλk,mk, and thus given by
(22)Gm1,…,mk,…,mKa,n=ta(Va,n,Z1,m1,…,Zk,mk,…ZK,mK)-Va,n∂ta∂va|(Va,n,Z1,m1,…,Zk,mk,…ZK,mK)-∑k=1KZk,mk∂ta∂λk|(Va,n,Z1,m1,…,Zk,mk,…ZK,mK).
Subsequently, the piecewise linear travel time function of each link is transferred into the following equivalent mixed-integer linear constraints:
(23)L·ξa,n≤va-Va,n≤U·(1-ξa,n)-ε,θa,n=ξa,n+1-ξa,n,L·ςmk≤λi-Zk,mk≤U·(1-ςmk)-ε,ϑmk=ςmk+1-ξmk,ψn,m1,…,mk,…,mKa=θa,n+∑k=1Kϑmk,L·(K+1-ψm1,…,mk,…,mKa,n)≤ta-(Enava+∑k=1KFmkλk)≤U·(K+1-ψm1,…,mk,⋯,mKa,n),ξa,n∈{0,1},ςmk∈{0,1},n=1,2,…,N,mk=1,2,…,M,∀a∈A,
where L and U still represent very large negative and positive constants, respectively. And ε is still a very small positive constant. The binary variable ξa,n indicates the comparison between va and Va,n. Specifically, ξa,n=0 indicates va≥Va,n, ξa,n=1 indicates va<Ua,n. Thus θa,n indicates whether va falls in segment n or not. If θa,n=1, va is in segment n. Similarly, ϑmk=1 means λk falls in segment mk. If ψm1,…,mk,…,mKa,n=K+1, then the corresponding approximated linear function in the region (n,m1,…,mk,…,mK) is utilized, namely, ta=Enava+∑k=1KFmkλk+Gm1,…,mk,…,mKa,n. In this way, all the nonlinear constraints of the single-level formulation have been transferred into linear ones.Tracing the same way,Ta(xa,λ) can be approximated into linear functions. Thus the whole problem becomes a mixed integer linear program, which can be solved by commercial software, such as CPLEX.


## 3.2. Equivalent Single-Level Model of Maximizing Network Reserve Capacity

If the lower level problem is replaced with its first order condition, the combined signal control and pricing problem with the objective of maximizing reserve capacity can be transferred into a single-level formulation, as below(24)Maximiseμ,λ,τμ(25)s.t.va(μ,λ,τ)≤paCa(λ),a∈A¯Giλi≥bi,i∈I,τju≥τj≥τjl,j∈J,∑p∈Pwfpw=μqw,w∈W,va=∑w∈W∑p∈Pwfpwδapw,a∈A,cpw=∑a∈Ata(va,λ)δapw+∑j∈Jτjδjpwρ,Lφpw+ε≤fpw≤U(1-φpw),p∈Pw,w∈W,φpw∈{0,1},p∈Pw,w∈W,Lφpw≤cpw-πw≤Uφpw,p∈Pw,w∈W,cpw-πw≥0,p∈Pw,w∈W,fpw≥0,p∈Pw,
where πw represents the minimum generalized travel cost of OD pair w. Notation cpw denotes the generalized travel cost of path p. Furthermore, f, c, and π are vectors of fpw, cpw, and πw, respectively.In this program, the objective function is obviously a linear function. Andta(xa,λ) can also be linearized as done in Section 3.1.


## 4. A Numerical Example

Consider an example network, shown in Figure1, with 7 links and 6 nodes, of which nodes E and F are signal-controlled intersections. The current O-D demand from node A to node D is 10 veh/min and that from C to D is 20 veh/min. There is only one path ABD for the O-D pair (A, B),while there are two paths CBD and CD for O-D pair (C, D). The delay formula of links takes the following form:
(26)ta(va,λa)=ta0+θa×(vaλasa),
where λa is the proportion of a cycle that is effectively green for link α, and λa=1.0 for any link that does not enter into a signal-controlled junction. The values of ta0, θa, and sa are given in Table 1.Table 1
Input data to the example network.
Link numbera
1
2
3
4
Free-flow timeta0 (min)
4.6
5.2
5.1
3.9
Saturation flowsa (veh/min)
52
50
20
80Figure 1
A signal-controlled road network.For the signalized intersectionsB, signal control is represented by two split parameters (proportions of green times) λ1 and λ2. The proportion of green time allocated to link 1 is λ1, and the proportion allocated to link 2 is λ2. Loss time of phase transition is ignored, namely, λ1+λ2=1. Therefore the capacity of link 1 is λ1s1, and the capacity of link 2 is λ2s2. The lower and upper bounds of the proportion of green time are 0.05≤λ1, λ2≤0.95.With only signal control, the total travel time in the network is minimized atλ1=1.00 and λ2=0, which means green time is fully assigned to link 1. The minimal total travel time is 271.21 min. The corresponding link volume, link travel time, and volume to capacity ratio are listed in Table 2.Table 2
Solution of total travel time minimization with signal control only.
Link numbera
1
2
3
4
Traffic volume (veh/min)
10
0
20
10
Travel time (min)
4.95
4.83
9.00
4.18
Volume to capacity ratio
0.19
NA
1.00
0.13Now we consider the policy of the joint implementation of signal control and congestion pricing, wherein a tollτ3 is charged on link 3. Assume that the value of time is 1.0 $/min for travellers. Using the model developed in Section 2.1, after piecewisely linearizing the objective function and the delay formula, the solution is obtained at λ1=0.66, λ2=0.34, and τ3=$2.0. At the optimum, total travel time is 265.36 min. By introducing congestion pricing, the total travel time decreases by 5.85 min. The corresponding link volume, link travel time, and volume to capacity ratio are listed in Table 3.Table 3
Solution of total travel time minimization with both signal and pricing.
Link numbera
1
2
3
4
Traffic volume (veh/min)
10
4.70
15.30
14.70
Travel time (min)
5.12
5.78
8.08
4.30
Volume to capacity ratio
0.29
0.28
0.77
0.18Assume that the maximum acceptable level of link volume is exactly its capacity, and then we investigate the reserve capacity maximization. If signal control is the only policy, the solution is given byλ1=1.00 and λ2=0, which is the same as the case of the total travel time minimization. The maximal demand multiplier is 1.0, and the network has no reserve capacity. The link volumes are also shown in Table 2. Clearly, link 3 is the critical link since its volume reaches the capacity.When signal control and congestion pricing are simultaneously implemented, the model developed in Section2.2 is used to maximize the reserve capacity. After piecewisely linearizing the delay formula, the solution is obtained at λ1=0.46, λ2=0.54, and τ3=$3.59. At the optimum, the reserve capacity is 2.34. By introducing congestion pricing, the network demand multiplier increases from 1.0 to 2.34. In other words, the network reserve capacity increases from 0 to 1.34. In this case, the link volume, link travel time, and volume to capacity ratio are listed in Table 4. Clearly links 1, 2, and 3 are critical links, because they will be operated at their full capacities when the network serves 2.34 times the existing demand levels.Table 4
Solution of reserve capacity maximization with both signal and pricing.
Link numbera
1
2
3
4
Traffic volume (veh/min)
23.92
27.0
20.0
50.28
Travel time (min)
6.36
7.29
8.98
5.28
Volume to capacity ratio
1.0
1.0
1.0
0.63This numerical example shows that the network performance (in terms of both reserve capacity maximization and system time minimization) can be significantly improved by further introducing congestion pricing, besides implementing signal control.


## 5. Conclusions

This paper proposed a joint implementation policy of signal control and congestion toll optimization in the transportation network. The objective of the system planner is either to minimize the total travel time of the whole network or to maximize the reserve capacity of the network. The reserve capacity of a network is defined as a multiplier that raises the demand of each OD pair by the same proportion without violating capacity constraints of all links. The policy is formulated as two bilevel models, depending on which objective is chosen. The objective in the upper level is to minimize system travel time or to maximize reserve capacity. The problem in the lower level is a traffic assignment problem, considering both signal setting and congestion pricing. By reformulating the lower level problem with its first order conditions, we then transfer the bilevel programs into the equivalent single level programs. After transferring the objective function of the system travel time and the link cost formula into the piecewise linear functions, the whole problem can be characterized as a mixed integer program. The numerical example indicates that the network performance can be significantly improved by further introducing congestion pricing, besides implementing signal control.



---

*Source: 315752-2013-08-20.xml*