# Solving a Signalized Traffic Intersection Problem with NLP Solvers

Authors: Teófilo Miguel M. Melo; João Luís H. Matias; M. Teresa T. Monteiro
Journal: Conference Papers in Mathematics
 (2013)

---

## Abstract

Mathematical Programs with Complementarity Constraints (MPCC) finds many applications in areas such as engineering design, economic equilibrium, and mathematical theory itself. In this work, we
consider a queuing system model resulting from a single signalized traffic intersection regulated by pretimed control in an urban traffic network. The model is formulated as an MPCC problem and may be used to ascertain the optimal cycle and the green split allocation. This MPCC problem is also formulated as its NLP equivalent reformulation. The goal of this work is to solve the problem, using both MPCC and NLP formulations, minimizing two objective functions: the average queue length over all queues and the average waiting time over the worst queue. The problem was codified in AMPL and solved using some optimization software packages.


---

## Body

## 1. Introduction

Mathematical Programs with Complementarity Constraints (MPCC) is a subclass of more general Mathematical Programs with Equilibrium Constraints (MPEC). These kind of constraints may come as a game, a variational inequality, or as stationary conditions of an optimization problem. The main applications areas are engineering and economics [1–3]. They are so widespread in these areas because the concept of complementarity is synonymous with the notion of system equilibrium. They are very difficult to solve as the usual constraint qualifications necessary to guarantee the algorithms convergence fail in all feasible points [4]. This complexity is caused by the disjunctive nature of the complementarity constraints.Some nonlinear approaches to solve MPCC have been proposed, starting with the smoothing scheme [5, 6], the regularization scheme [7, 8], the interior point methods [9], the penalty approaches [10–12], and the “elastic mode” for nonlinear programming in conjunction with a sequential quadratic programming (SQP) algorithm [13]. In Fletcher et al.’s study [14], the quadratic convergence of SQP is guaranteed, near a stationary point, under relatively mild conditions.As the number of vehicles and the need for transportation grow, traffic light control can be used to control the flow of the traffic in urban environments. De Schutter and De Moor [15] study the optimal traffic control problem of a two two-way streets intersection. These authors derive an approximate model that describes the evolution of the queues lengths as a continuous function of time.Starting from this model it is possible to compute the traffic light switching scheme that minimizes a criterion such as average queue length over all queues, the average waiting time over the worst queue, or average waiting time.A single signalized intersection regulated by pretimed control problem with four traffic streams is considered. This problem is formulated as an MPCC and also as its NLP equivalent reformulation. Some computational experiments using the FilterMPEC, the KNITRO, and the MATLAB optimization toolbox are performed.This paper is organized as follows. Next section defines the MPCC problem and its NLP reformulation. Some optimal issues are presented in Section3. The traffic model formulation using two objective functions is described in Section 4. In Section 5, the optimization solvers main characteristics are presented. Numerical experiments using the solvers are reported in Section 6. Some conclusions and future work are carried out in Section 7.


## 2. Problem Definition

We consider Mathematical Program with Complementarity Constraints(MPCC):
(MPCC)minf(x)s.t.ci(x)=0,i∈E,ci(x)≥0,i∈I,0≤x1⊥x2≥0,
where f and c are the nonlinear objective function and the constraint functions, respectively, assumed to be twice continuously differentiable. E and I are two disjoined finite index sets with cardinalities p and m, respectively. A decomposition x=(x0,x1,x2) of the variables is used where x0∈ℝn (control variables) and (x1,x2)∈ℝ2q (state variables). The expressions 0≤x1⊥x2≥0:ℝ2q→ℝq are the q complementarity constraints. Q is a finite index set with cardinality q.One attractive way of solving(MPCC) is to replace the complementarity constraints by a set of nonlinear inequalities, such as x1jx2j≤0,  j∈Q, and then solve the equivalent nonlinear program (NLP):
(MPCC-NLP)minf(x)s.t.ci(x)=0,i∈E,ci(x)≥0,i∈I,x1jx2j≤0,j∈Q,x1≥0,x2≥0.


## 3. Optimal Issues

The NLP formulation has no feasible point that strictly satisfies the inequalities. This fact implies that the Mangasarian-Fromovitz constraint qualification (MFCQ) is violated at every feasible point [16]. This failure has consequences: the multiplier set is unbounded, the central path fails to exist, the active constraints normals are linearly dependent, and linearizations of the NLP formulation can be inconsistent arbitrarily close to the solution. Recent developments show that there is a relationship between strong stationarity defined by Scheel and Scholtes and the Karush-Kuhn-Tucker (KKT) points. This relationship established convergence of SQP methods for MPCC formulated as NLP. Some optimality concepts used in this work are based on the study of Fletcher et al. [14].


## 4. Traffic Model Formulation

In this section, we briefly describe the traffic model and present the MPCC formulation—further details could be consulted in the work of Ribeiro and Simões [17]. The traffic model considers an intersection with four traffic streams: S1, S2, S3, and S4 which are controlled by a traffic signal: T1, T2, T3, and T4, respectively. A set S={1,2,3,4} is considered. The intersection presented in Figure 1 is controlled by two phases (A and B). During Phase A, the traffic signals T1 and T3 have green light and the same occurs in Phase B for T2 and T4. In both phases, the cycle has 3 stages: green, yellow, and red. The arrival rate of vehicles in traffic stream Si at instant time t is λi(t) for i∈S. When the traffic signal Ti is green, the departure rate in traffic stream Si at instant time t is μi(t), and in the case of the traffic being yellow, the departure rate in traffic stream Si at instant t is κi(t) for i∈S. Let t0, t1, …, be the time instants when a change in the traffic signal occurs.Figure 1
Intersection.The duration of the yellow time and clearance time is fixed and set equal todY and dC, respectively. The time instants when traffic signals T1 and T3 initiate a green period and T2 and T4 begin a red period are t0, t2, t4, …. The time instants when traffic signals T1 and T3 initiate a red period and T2 and T4 begin a green period are t1, t3, t5, …. Thus, t2k+1-t2k=yG+dY+dC and t2k+2-t2k+1=yR+dY+dC, k∈ℕ0.Therefore,yG represents the green time in traffic signals T1 and T3 and yR represents the red time at T1 and T3, and a cycle length is equal to yG+yR+2dy+2dC.The traffic problem has the following MPCC formulation:(TP1)min∑i=14‍(12N(x0)i+∑k=1N-1‍1N(xk)i+12N(xN)i)s.t.0≤xk≤xmax,ymin≤yR≤ymax,ymin≤yG≤ymax,x2k+1≥x2k+b1yG+b3⊥x2k+1≥b5,x2k+2≥x2k+1+b2yR+b4⊥x2k+2≥b6,
where the objective function represents the average queue length over all queues. Since short cycles imply more stops and long cycles causes long delays, maximum and minimum durations for the red and green time (yR and yG) are considered as simple bound constraints. The number of vehicles in traffic stream i at time instant k is represented by (xk)i. The maximum queue length in each traffic stream is xmax and N is the time periods considered.Another situation was considered and has the following formulation:(TP2)minmaxi(1λ-i(12N(x0)i+∑k=1N-1‍1N(xk)i+12N(xN)i))s.t.0≤xk≤xmax,ymin≤yR≤ymax,ymin≤yG≤ymax,x2k+1≥x2k+b1yG+b3⊥x2k+1≥b5,x2k+2≥x2k+1+b2yR+b4⊥x2k+2≥b6.
In this case, the goal is to minimize the average waiting time over the worst queue, and the constraints are the same as the traffic problem (TP1).In addition, the following vectors are defined:(1)xk=[L1(tk),L2(tk),L3(tk),L4(tk)]T,k∈ℕ0,b1=[λ-1-μ-1,λ-2,λ-3-μ-3,λ-4]T,b2=[λ-1,λ-2-μ-2,λ-3,λ-4-μ-4]T,b3=[(λ-1-κ-1)dY+λ-1dC,λ-2(dC+dY),(λ-3-κ-3)dY+λ-3dC,λ-4(dC+dY)]T,b4=[λ-1(dC+dY),(λ-2-κ-2)dY+λ-2dC,λ-3(dC+dY),(λ-4-κ-4)dY+λ-4dC]T,b5=[max{(λ-1-κ-1)dY+λ-1dC,λ-1dC},0,max{(λ-3-κ-3)dY+λ-3dC,λ-3dC},0]T,b6=[0,max{(λ-2-κ-2)dY+λ-2dC,λ-2dC},0,max{(λ-4-κ-4)dY+λ-4dC,λ-4dC}]T,
where for each traffic stream, that is, for i∈S:(i)
λ-i is the average arrival rate;(ii)
μ-i is the average departure rate when the traffic signal is green;(iii)
κ-i is the average departure rate when the traffic signal is yellow;(iv)
Li(tk) is the queue length at time instant k.These two MPCC problems,(TP1) and (TP2), are reformulated into their NLP equivalent formulation (MPCC-NLP). Next section presents three optimization codes used to solve these two traffic situations in both formulations: (MPCC) and (MPCC-NLP).


## 5. NLP Solvers

In this section, we present three solvers, two of them are available on the NEOS Server platform [18, 19], and the third one is available on MATLAB software. The NEOS Server is a free internet-based service for solving optimization problems with several solvers representing the state of the art in optimization software.


### 5.1. FilterMPEC

FilterMPEC arises from the work of Fletcher and Leyffer [20] to solve Mathematical Programs with Equilibrium Constraints (MPECs) in AMPL format [21]. FilterMPEC is an extension of filterSQP, implementing a SQP solver which is suitable for solving medium-scale nonlinearly constrained problems.


### 5.2. KNITRO

KNITRO was developed for the solution of general nonconvex, nonlinearly constrained optimization problems in AMPL format [22]. It is also effective for problems with complementarity constraints. KNITRO provides three algorithms, two of them use the interior point methods, and the other is based on an active set method.


### 5.3. MATLAB

The fmincon routine from MATLAB optimization toolbox [23] is a gradient-based method to solve problems with objective and constraint functions twice continuously differentiable. It uses one of four algorithms: active-set, interior point method, SQP, or trust-region-reflective. From these algorithms, we use the SQP algorithm to solve (MPCC-NLP). To connect the modelling language AMPL [24] to the fmnicon routine, a MATLAB mex function was used.


## 5.1. FilterMPEC

FilterMPEC arises from the work of Fletcher and Leyffer [20] to solve Mathematical Programs with Equilibrium Constraints (MPECs) in AMPL format [21]. FilterMPEC is an extension of filterSQP, implementing a SQP solver which is suitable for solving medium-scale nonlinearly constrained problems.


## 5.2. KNITRO

KNITRO was developed for the solution of general nonconvex, nonlinearly constrained optimization problems in AMPL format [22]. It is also effective for problems with complementarity constraints. KNITRO provides three algorithms, two of them use the interior point methods, and the other is based on an active set method.


## 5.3. MATLAB

The fmincon routine from MATLAB optimization toolbox [23] is a gradient-based method to solve problems with objective and constraint functions twice continuously differentiable. It uses one of four algorithms: active-set, interior point method, SQP, or trust-region-reflective. From these algorithms, we use the SQP algorithm to solve (MPCC-NLP). To connect the modelling language AMPL [24] to the fmnicon routine, a MATLAB mex function was used.


## 6. Numerical Experiments

This section summarizes the results of the numerical tests, solving the traffic intersection problem with two different approaches: the first approach, used by FilterMPEC and KNITRO, the traffic problem is solved using the(MPCC) formulation; the second approach employed by fmincon routine uses (MPCC-NLP) reformulation. The MATLAB version was 7.11.0 (R2010b), and the computational experiments were made on a 2.26 GHz Intel Core 2 Duo with 8 GB of RAM, MAC OS 10.6.8 operating system. For all the solvers, the default options were used.Both traffic situations(TP1) and (TP2) were tested using ten instances of λ-i,i∈S, corresponding to problems P1–P10 reported in Table 1. Furthermore, N=61 was considered, which corresponds to a period of time over thirty cycles. The other parameters used are
(2)μ-i=1800veh/h,κ-i=720veh/h,i∈S,x0k=2%λ-kx0j=1%λ-kfork=1,3,j=2,4,xmaxi=25i∈S,dY=3s,dC=2s,ymin=7s,ymax=60s.Table 1
10 instances.
Problem
λ
-
1 (veh/h)
λ
-
2 (veh/h)
λ
-
3 (veh/h)
λ
-
4(veh/h)
P1
150
850
250
750
P2
150
800
250
700
P3
500
900
600
800
P4
500
850
600
750
P5
550
900
650
800
P6
650
800
750
700
P7
300
750
400
650
P8
450
600
550
500
P9
700
750
800
650
P10
850
600
850
500Tables2 and 3 report the optimization results of traffic problem (TP1) and traffic problem (TP2), respectively: the red split time (yR), the green split time (yG), and objective function value (obj) for the three solvers.Table 2
(
TP
1
) results.
Problem
FilterMPEC
KNITRO
fmincon
y
R  (s)
y
G  (s)
obj
y
R  (s)
y
G  (s)
obj
y
R  (s)
y
G  (s)
obj
P1
26.5
7.0
7.1
11.6
7.0
11.7
26.5
7.0
6.9
P2
23.6
7.0
6.6
13.7
7.0
7.1
23.6
7.0
6.4
P3
31.1
18.7
17.5
20.7
13.8
24.8
31.1
18.7
17.2
P4
28.8
17.7
15.2
17.2
12.2
17.9
28.8
17.7
14.9
P5
37.3
24.8
21.2
34.5
23.2
21.1
37.3
24.8
20.9
P6
32.0
27.9
21.0
20.4
18.0
23.0
32.0
27.9
20.7
P7
16.8
7.1
7.8
13.16
7.0
7.6
16.8
7.1
7.6
P8
13.5
10.6
8.32
10.9
9.8
8.0
13.5
10.6
8.0
P9
29.8
29.7
20.8
25.9
26.8
22.1
29.8
29.7
20.4
P10
21.3
27.9
16.6
21.3
27.9
16.2
21.3
27.9
16.2Table 3
(
TP
2
) results.
Problem
FilterMPEC
KNITRO
fmincon
y
R  (s)
y
G  (s)
obj
y
R  (s)
y
G  (s)
obj
y
R  (s)
y
G  (s)
obj
P1
18.8
7.0
14.5
13.3
7.0
17.2
18.8
7.0
14.5
P2
17.4
7.0
13.8
17.4
7.0
13.8
17.4
7.0
13.8
P3
28.2
16.4
26.5
19.9
12.4
39.7
39.0
22.7
24.5
P4
30.4
18.4
21.6
15.2
10.1
35.1
32.9
19.6
21.6
P5
36.4
24.0
40.2
20.8
14.0
75.9
41.4
27.0
29.9
P6
31.2
26.7
33.3
25.6
22.5
45.2
39.0
32.6
31.6
P7
15.0
7.2
14.3
14.1
7.0
15.1
16.2
7.9
14.2
P8
11.6
9.5
15.4
11.9
9.6
15.2
15.3
11.6
14.6
P9
31.0
30.0
32.9
20.1
20.3
65.8
35.9
34.0
32.3
P10
22.0
26.7
25.4
20.6
27.4
29.1
24.2
28.5
25.4Table4 presents the number of iterations (it) achieved by the solvers for both traffic situations (TP1) and (TP2). Among the analysed solvers, FilterMPEC is the one that presents the best performance solving the traffic situation (TP1). For traffic situation (TP2), KNITRO needs more iterations than the others solvers.Table 4
Number of iterations.
Problem
FilterMPEC
KNITRO
fmincon
it
it
it
(
TP
1
)
(
TP
2
)
(
TP
1
)
(
TP
2
)
(
TP
1
)
(
TP
2
)
P1
5
68
58
159
21
30
P2
5
68
18
204
24
25
P3
2
32
26
21
10
47
P4
8
54
41
106
43
58
P5
2
81
53
171
20
77
P6
3
84
34
118
15
61
P7
2
34
19
48
37
38
P8
4
49
15
70
25
59
P9
2
53
29
174
6
41
P10
3
66
45
81
24
99


## 7. Conclusions and Future Work

A traffic model was studied and codified in AMPL language which could be easily connected to nonlinear programming solvers. Two approaches were used to solve the traffic problem: the(MPCC) formulation, solved by FilterMPEC and KNITRO on NEOS Server and the reformulation (MPCC-NLP) solved by fmincon routine from MATLAB. The model for traffic situations (TP1) and (TP2) was efficiently solved by these solvers using both approaches (MPCC) and (MPCC-NLP).As a first stage of future work, we intend to introduce a probabilistic distribution in arrival rate instead of considering it as a constant value. Another idea is to allow that vehicles to turn (right or left) and not follow just ahead. With minor changes, other objective functions can be easily tested: average queue length over the worst queue, worst case queue length and average waiting time over all queues. Another goal of this work is to collect real data from a signalized traffic intersection in a city in order to test the model in a real situation.



---

*Source: 216898-2013-08-05.xml*