# Optimal Design of Signal Controlled Road Networks Using Differential Evolution Optimization Algorithm

Authors: Huseyin Ceylan
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This study proposes a traffic congestion minimization model in which the traffic signal setting optimization is performed through a combined simulation-optimization model. In this model, the TRANSYT traffic simulation software is combined with Differential Evolution (DE) optimization algorithm, which is based on the natural selection paradigm. In this context, the EQuilibrium Network Design (EQND) problem is formulated as a bilevel programming problem in which the upper level is the minimization of the total network performance index. In the lower level, the traffic assignment problem, which represents the route choice behavior of the road users, is solved using the Path Flow Estimator (PFE) as a stochastic user equilibrium assessment. The solution of the bilevel EQND problem is carried out by the proposed Differential Evolution and TRANSYT with PFE, the so-called DETRANSPFE model, on a well-known signal controlled test network. Performance of the proposed model is compared to that of two previous works where the EQND problem has been solved by Genetic-Algorithms- (GAs-) and Harmony-Search- (HS-) based models. Results show that the DETRANSPFE model outperforms the GA- and HS-based models in terms of the network performance index and the computational time required.


---

## Body

## 1. Introduction

Configuring the traffic signal timings is a challenging problem in transportation engineering as it is important to minimize delays and total travel time in the road networks. Since the drivers’ route choice behavior is taken into account in the User Equilibrium (UE) manner, this problem is called the EQuilibrium Network Design (EQND) problem. Two common solution methods have been discussed for solving the EQND problem: Mutually Consistent (MC) and bilevel approaches. In those approaches, some procedures have been developed for determining the optimal signal timings. Allsop and Charlesworth [1] presented an MC calculation for the EQND problem. In their study, the equilibrium link flows and resulting signal settings are calculated, respectively, by solving each problem until the convergence criterion has been satisfied. However, the resulting MC signal settings and equilibrium link flows are nonoptimal in many cases [2, 3].Due to the multiobjective structure of the EQND problem, it is usually modeled as a bilevel programming problem, where certain design parameters are optimized at the upper level, while the lower level represents a UE problem [4–10]. Heydecker and Khoo [4] presented a Linear Constraint Approximation (LCA) to the UE constraint and solved the EQND problem. On the other hand, effectiveness of the Sensitivity Analysis (SA) of UE flows in particular design issues has been investigated in several studies [6, 11, 12]. The basic principle of the SA-based methods is searching for the optimal solution using the simplex method by formulating a linearized subproblem at the current signal settings. Because of the nonconvex solution space of the EQND problem, LCA- and SA-based algorithms may only produce locally optimal solutions [13]. Thus, these optimization techniques are not guaranteed to obtain the global optimum solutions. Over the past several decades, some heuristics based on natural phenomena such as Genetic Algorithms (GAs) [14], Simulated Annealing (SA) [15], and Differential Evolution (DE) [16] have been developed to overcome this problem. These methods can be applied to both continuous (differentiable) and discontinuous (nondifferentiable) objective functions without requiring an extensive formulation. Moreover, they do not require specialized starting points and they are rarely trapped into a local optimum solution [17]. These advantages enhance their application in the field of the EQND.Friesz et al. [18, 19] presented a metaheuristic SA-based optimization approach under variational inequality constraints. Ceylan and Bell [7] presented a simulation-optimization model combining GAs with the logit traffic assignment tool Path Flow Estimator (PFE), which has been developed and improved by Bell and Shield [20], Bell et al. [21–23], Bell and Iida [24], Bell and Grosso [25], and TRANSYT traffic simulation software [26, 27]. In the study, the upper level problem was considered to be the optimization of the green times, common cycle time, and offsets to minimize the network Performance Index (PI) which may be defined as the sum of a weighted combination of the delays and stops on all the links in a network. Furthermore, Teklu et al. [28] presented a GA-based signal timing optimization method that considers drivers rerouting. Ceylan [29] combined GAs with the TRANSYT Hill-Climbing optimization routine and proposed a hybrid global/local optimization method for determining optimal signal timings. In the related study, drivers rerouting was ignored. Ceylan and Ceylan [30] developed a hybrid solution approach, where the metaheuristic Harmony Search (HS) and TRANSYT Hill-Climbing optimization methods were combined, considering drivers’ route choice behavior. The performance of their model was compared with that of the pure HS- and GA-based solution models. Although a number of solution methods were developed and improved for the solution of the EQND problem, it may be useful to develop new models based on different optimization algorithms. Among them, DE is an important optimization algorithm due to its powerful solution ability in finding the global optimum solution.The DE algorithm, which is an improved version of GAs, is a quite simple evolutionary approach that is quite faster and robust at numerical optimization, and it is more likely to find the global optimum of an objective function [31]. However, to create new solution vectors, the DE uses nonuniform crossover and tournament selection operators, while the bitwise flipping approach is used in GAs. Thus, it can be used for optimizing functions, including many local optima with real variables [17]. The DE algorithm has recently been applied to several engineering design problems, including the optimization of the airfoil cross section of a vertical-axis wind turbine [32], the designing of the aperture of pyramidal horns [33], the optimizing of reservoir systems [34], shape design of variable capacitance micromotor  [35], various constrained engineering design problems [36, 37], the vehicle routing problem with time windows [38], the optimal design of water distribution networks [39, 40], and river suspended sediment concentration modeling [41], but no studies of DE have been reported on the solution of the EQND problem.In this study, the Differential Evolution and TRANSYT with PFE (DETRANSPFE) model are developed for the solution of the EQND problem. For this purpose, the Stochastic User Equilibrium (SUE) traffic assignment and traffic signal optimization problems are combined using the DE solution framework to minimize the network PI value. It should be noted that this is the first time that the DE optimization algorithm is implemented for the EQND problem. The proposed model is applied to Allsop and Charlesworth’s [1] test road network and a comparison with GA- and HS-based models is given to examine the solution ability of the DETRANSPFE model. The DETRANSPFE model further extends the GA- and HS-based models [7, 30] in terms of mathematical formulation and the computational time.The remainder of the paper is organized as follows: fundamentals of the SUE assignment and traffic signal optimization problems are given in Section2. Basics of the DE algorithm and DETRANSPFE model are provided in Section 3. Performance of DETRANSPFE model is proved with a numerical example in Section 4. Last, the study is ended with some conclusions and future recommendations in Section 5.


## 2. Problem Formulation

Considering a network with sets of nodesN, links A, and paths P between the Origin-Destination (O-D) pairs W, bilevel formulation of the EQND problem may be expressed as a combination of the SUE traffic assignment and network performance optimization in the following way:(1a)minPI(v*(ψ),ψ)={∑a∈A[G·d·Da(v*(ψ),ψ)+K·k·La(v*(ψ),ψ)]∑a∈A[G·d·Da(v*(ψ),ψ)}+λ·E(ϕ)(1b)s.t.Cmin≤C≤Cmax(1c)s.t.ϕ≥ϕmin,ϕ∈φ(1d)s.t.E(ϕ)={|[∑mn(ϕ+I)]-C|if∑mn(ϕ+I)≠C,[∀n∈N]0if∑mn(ϕ+I)=C,[∀n∈N],where PI(v*(ψ),ψ) is the performance index of the road network (£/h), v*(ψ) is the vector of equilibrium link flows as a function of signal timings, ψ. G is the cost of delay, d is the weighting factor of delay, Da(v*(ψ),ψ) represents delay as a function of equilibrium link flows and signal timings, Kis the cost for 100 vehicle stops, k is the weighting factor of stops, and La(v*(ψ),ψ) is the number of vehicle stops per hour. Additionally, subscripts “a”, “n,” and “p” denote link a, node (or signalized intersection) n, and path p, respectively. Superscript “*” indicates that the variable is associated with its optimal and/or equilibrium state. E(ϕ) is the penalty term, and it takes a zero value if the total duration of the total green and intergreen times equals the network cycle time at every signalized intersection; otherwise, it varies linearly with the magnitude of constraint violation. The penalty approach is implemented by multiplying the penalty term with a weighting factor, λ, as shown in (1a). Note that a larger λ for a given constraint set means that a greater emphasis will be placed on resolving constraint violations. However, the selection of λ is mostly problem dependent. Furthermore, C represents the network cycle time while Cmin and Cmax are the lower and upper bounds of the network cycle time, respectively, ϕmin is the lowest acceptable stage green timing duration, φ is the vector of duration of stage green timings [ϕ;∀ϕ=1,…,mn,∀n∈N], mn is the number of stages for signalized intersection n, and I is the intergreen time between signal stages.In (1a), v*(ψ) may implicitly be derived from the solution of (2a), which leads to a logit path choice model [42](2a)MinimisevZ(v,ψ)Minimisev=-qTy(v,ψ)+vTt(v,ψ)Minimisev-∑a∈A∫0va(ψ)ta(ψ,x)dx(2b)s.t.q=Λh(2c)s.t.v=δh(2d)s.t.h≥0,where q represents the vector of the total O-D demands [qw;∀w∈W], y(v,ψ) is the vector of path travel times [yp;∀p∈P], t(v,ψ) is the vector of link travel times [ta;∀a∈A], and h is the vector of path flows [hp;∀p∈P]. In (2b) and (2c), Λ represents the O-D/path incidence matrix and δ represents the link/path incidence matrix, where δap=1 if link a is on path p, and δap=0; otherwise, [δap;∀a∈A;∀p∈P]. In this study, solution of the SUE assignment problem, which is given in (2a), is conducted by PFE with Pseudocode 1, where α is the dispersion parameter. When α is zero, path choice is not sensitive to cost that means that any path is likely to be chosen. On the other hand, while α tends to infinity, drivers become concentrated on the least cost paths to travel. The link cost function used by PFE is presented in
(3)ta(va(ψ),ψ)=ta0+dau+daro(t),
where ta0 is the free-flow travel time on link a, dau and daro are the uniform and random plus over saturation delays at the downstream intersection, respectively. The convergence measure is obtained by basing it on the flow in the last several iterations of PFE. At this point, let v-aj represent the average flow over the last r iterations; that is,
(4)v-aj=1r(vaj+vaj-1+⋯+vaj-r+1)=1r∑i=0r-1vaj-i,
where r is a priori fixed that may be accepted as “3” in applications [43]. Thus, a convergence criterion κ, that is based on flow similarity, is used as given in
(5)∑a(vaj+1-vaj)∑avaj≤κ.Pseudocode 1
Step 1  (initialization)
q
← user supplied, ∀w∈W
v
a
← 0, ∀a∈A
t
a
←
t
a
(
v
a
), ∀a∈A
j
← 1, iteration counter
Step 2 (update link costs by method of successive averages)
t
a
←
1
j
t
a
(
v
a
)
+
(
1
-
1
j
)
t
a
Step 3 (new path costs)
y
p
←
∑
a
∈
A
δ
a
p
t
a
(
v
a
)
Step 4 (new path flows - logit route choice model)
h
p
←
q
w
exp
(
-
α
y
p
)
∑
p
∈
P
w
exp
(
-
α
y
p
)
Step 5 (new link flows)
v
a
←
∑
p
∈
P
w
δ
a
p
h
p
if any new path and link flows converged then
j
←
j
+
1
return to Step 2
else stop.


## 3. Basics of the Differential Evolution Algorithm and DETRANSPFE Model

The DE algorithm is a comparatively simple, fast, powerful, and robust variant of an evolutionary algorithm for solving optimization problems. In this section, the solution of the EQND problem, which deals with the signal setting optimization based on the DETRANSPFE model, is presented. The solution procedure of the proposed model is presented in Figure1 and the main solution steps are explained hereafter.Figure 1
Flow chart of the DETRANSPFE model.Step 1 (initialization of the objective function, user-specified DE parameters, network characteristics, and termination criterion).
The objective function to be minimized has been given in (1a). The DE algorithm is controlled by three parameters. The first parameter, which is called the number of populations (Np), that represents the number of solution vectors used during the optimization process. The mutation factor (F), which is the second parameter and which is recommended to be set between 0.5 and 1 by Storn and Price [31], has an effect on the difference vector. The third one is the crossover rate (CR), which is the probability of mixing parameters of the mutation vector. The recommended range of the crossover rate is [0.8, 1.0] by Storn and Price [31]. Fixed sets of data related to the network topology are represented with the vector of free-flow link travel times, t0[ta0;∀a∈A], and the vector of saturation link flows, s[sa;∀a∈A]. In this study, results of the DETRANSPFE model will be compared with those obtained by the GA- and HS-based models, which have been developed by Ceylan and Bell [7] and Ceylan and Ceylan [30], respectively. Therefore, the maximum number of generations (ξmax) has been used as the termination criterion as in GA- and HS-based models. The numerical values of the DE parameters, the network characteristics, and the termination criterion are given in Section 4.Step 2 (generation of the initial population).
In this step, initial signal timing variables are generated between preset possible bounds and their corresponding network PI values which are calculated and stored as shown in(6)[C11ϕ21⋯θη-11θη1C12ϕ22⋯θη-12θη2⋯⋯⋯⋯⋯C1Np-1ϕ2Np-1⋯θη-1Np-1θηNp-1C1Npϕ2Np⋯θη-1NpθηNp]⟹[PI(v,ψ)1PI(v,ψ)2⋯PI(v,ψ)Np-1PI(v,ψ)Np],
where η is the number of decision variables and θ represents the vector of offset variables [θ;∀θ=1,…,N]. In order to calculate the network PI values according to (1a), the TRANSYT traffic simulation tool, which requires the SUE equilibrium link flows, is used at this step. As can be seen from Figure 1, TRANSYT requires both signal timing variables and corresponding SUE traffic link flows to calculate the network PI. Thus, before running the TRANSYT, the PFE traffic assignment tool is employed to calculate the SUE traffic link flows. Signal timing variables are transformed for the use of DETRANSPFE model as follows.(i)
Network cycle time is generated based on possible value bound[Cmin,Cmax].(ii)
Offsets are generated based on the following expression:(7)0≤θi≤C-1,
where θi represents the offset variable for signalized intersection i[θi∈θ;i=1,2,…,N]. However, stage change times are derived from offset variables in the following way:
(8)Si,1=θi,i=1,2,…,N,
where Si,1 is the change time for the first stage of the ith signalized intersection [44].(iii)
Stage green times are generated based on the possible value bound[ϕmin,ϕmax].
Note that, unlike the DE and HS in which the signal timing parameters governing the system performance index are represented as real numbers, these parameters in the GA are coded into binary strings, and the mapping from the binary string representation of variables into the real numbers is carried out to be used in the TRANSYT traffic model and PFE [7]. At this point, simplicity to code is important for researchers who are not familiar with programming and are looking for algorithms that can be simply implemented and tuned to solve the traffic signal timing optimization problem.Step 3 (mutation).
In particular, DE has the advantage of using a simple and efficient form of a self-adapting mutation process [45]. The mutation, which represents the basic strength of DE, is performed by adding the weighted difference vector between two population members to a third member. Combining three different, randomly chosen signal timing vectors to create a mutant vector, ρi,g, is given in
(9)ρi,G=ψr0,G+F·(ψr1,G-ψr2,G),
where r0 is a randomly chosen base vector index that is different from the target vector index, i. r1 and r2 are also randomly selected difference vector indices that are different from both base and target vector indices. Simple adaptation rule for F improves the performance of the DE algorithm to a large extent without imposing any serious computational burden [46]. However, the mutation is treated as a random change of some signal timing parameters in the GA, and this process may lead to an increase in computational load since the mutation is repeated if the mutated solution is infeasible.Step 4 (crossover).
The search process of the DE is completed with the uniform crossover. At this step, each member of the trial vector,μi,g, is chosen from the mutant vector with the probability of CR or from the target vector with the probability of 1-CR as given in
(10)μj,i,G={ρj,i,Gif(randj(0,1)≤CRorj=jrand)ψj,i,Gotherwise.
CR is compared with the output of a uniform random number generatorrandj(0,1) to determine whether the mutant vector or target vector will provide the member of the trial vector in (10). If the random number is less than or equal to CR, the trial parameter is chosen from the mutant vector, ρi,G; otherwise, the parameter is chosen from the target vector, ψi,G. Additionally, the condition of j=jrand ensures that at least one member of the trial vector is inherited from the mutant vector. Although both DE and GA contain the crossover process, their implementations are quite different. In DE, one of two feasible signal timing parameter values is chosen, whereas two solution vectors are recombined to produce two trial vectors often by crossover in GA. Considering the possible bounds of the signal timing parameters, the crossover operator of the GA used to manipulate the chromosomes often yields infeasible offspring. In such cases, crossover process is repeated and valuable CPU time is wasted.Step 5 (selection).
At this step, the objective function is evaluated using the parameters of the trial vector. For this purpose, DETRANSPFE employs PFE for calculating the SUE link flows using signal timing parameters stored in the trial vector. Then, both trial vector parameters and resulting SUE link flows are given to the TRANSYT to calculate the total network PI. If the trial vector,μi,g, has an equal or lower PI value than that of its target vector, ψi,G, it replaces the target vector in the next generation; otherwise, the target vector is retained in the population as given in
(11)ψi,G+1={μi,GifPI(v*(μi,G),μi,G)≤PI(v*(ψi,G),ψi,G)ψi,Gotherwise.
It should be noted that although the mutation, crossover, and selection steps are explained only for stage green timing parameters in (9)–(11), these steps are performed in the same manner for all decision parameters in the DETRANSPFE model.Step 6 (termination).
The mutation, crossover, and selection steps of the DETRANSPFE model are repeated until the maximum number of generations,ξmax, is reached.


## 4. Numerical Example and Computational Comparison

The performance of the proposed DETRANSPFE model is investigated on Allsop and Charlesworth’s [1] well-known test road network in this section. The results obtained by two previous works are presented to make a comparison to prove the effectiveness of the DETRANSPFE model.


### 4.1. Test Road Network

The basic layout of the test network and the allocations for signal groups for each intersection are provided in Figures2 and 3, respectively.Figure 2
Allsop and Charlesworth’s [1] test network.Figure 3
Configuration of signal groups.Fixed travel demands for eachO-D pair are given in Table 1. The input data including free-flow travel times and saturation flow rates is given in Table 2.Table 1
Fixed travel demands for eachO-D pair (vehicles/hour).
O-D pairs
F
E
D
B
A
Origin totals
A
200
30
700
250
—
1180
C
900
130
200
20
40
1290
D
100
50
—
250
400
800
E
20
—
30
130
300
480
G
20
60
170
450
550
1250
Destination totals
1240
270
1100
1100
1290
5000Table 2
Input data for test network.
Intersection
Link
t
a
0
s
a
1
1
1
2000
2
1
1600
16
10
2900
19
10
1500
2
3
10
3200
15
15
2600
23
15
3200
3
4
15
3200
14
20
3200
20
1
2800
4
5
20
1800
6
20
1850
10
10
2200
11
1
2000
12
1
1800
13
1
2200
5
8
15
1850
9
15
1700
17
10
1700
21
15
3200
6
7
10
1800
18
15
1700
22
1
3600Using typical values found in practice, the minimum green time,ϕmin, for each group is 7 seconds, and the intergreen times, I, are 5 seconds between incompatible signal groups. The possible range for the network cycle time is set at 36 and 120 seconds. Values of the mutation factor, F, the crossover rate, CR, which are the user-specified parameters of DE, and the weighting factor, λ, are set to 0.80, 0.80, and 10, respectively. The optimization process is terminated after 110 generations for Np=40 (i.e., 4400 function evaluations) in the same manner as Ceylan and Bell’s [7] GA-based modeling.


### 4.2. Computational Results

In order to prove the effectiveness of DETRANSPFE, the model was run 100 times with different random seeds and initial populations for the test network. The convergence behavior of the DETRANSPFE, GA-based, and HS-based models can be seen in Figure4.Figure 4
GA-based [7], HS-based [30], and DE-based model solutions of Allsop and Charlesworth’s network.Figure4 indicates that the best solution was obtained as 679.1 £/h at the 49th generation (i.e., about 1690 function evaluations) with the DETRANSPFE model. The improvement of the network PI is about 28% in comparison with the initial status of the network. It can also be seen from Figure 4 that the DETRANSPFE model performs slightly better than the GA- and HS-based models in terms of the final values of total network performance index. The comparison of GA-based, HS-based, and DETRANSPFE models in terms of the network PI value is given in Table 3.Table 3
Numerical results of three models.
Models
Best PI (£/h)
Mean PI (£/h)
Worst PI (£/h)
GA-based [7]
712.5
N/A
N/A
HS-based [30]
687.7
690.4
704.4
DETRANSPFE
679.1
684.7
690.6
N/A: not available.It can be seen from Table3 that the DETRANSPFE model minimizes the network PI value by about 4.69% and 1.25% better than the GA- and HS-based models, respectively. Furthermore, the highest PI value obtained after 100 runs of the DETRANSPFE model is 690.6 £/h, which may indicate the better solution ability of the DETRANSPFE model. In order to evaluate the average computation times required by three models, the algorithms have been recoded in Visual Basic and run in a PC with a 1.6 Ghz processor and 1 GB ram. Computation time required by the DETRANSPFE model is obtained as 36 minutes, while GA- and HS-based models require about 66 and 43 minutes, respectively. As it has been mentioned in the previous section, the crossover and mutation operators of the GA may lead to an increase in computation time due to the infeasible solutions. Ceylan and Ceylan [30] stated that if signal timing constraints are not satisfied for generated timings, the HS-based model automatically discards those generated signal timings and starts generating new ones. Considering this situation, it may be concluded that the DETRANSPFE completes 4400 function evaluations by about 45% and 16% faster than the GA- and HS-based models, respectively. The network cycle times obtained by the GA-based, HS-based, and DETRANSPFE models is 77, 71, and 79 seconds, respectively. Signal timings resulting from three models are given in Table 4.Table 4
Signal timing values resulting from three models.
Models
Performance Index, PI (£/h)
Cycle time,C(sec)
Junction number,n
Start of green in seconds
Stage 1
Stage 2
Stage 3
GA-based [7]
712.5
77
1
0
32
—
2
59
25
—
3
13
60
—
4
44
72
20
5
64
5
30
6
47
6
—
HS-based [30]
687.7
71
1
0
28
—
2
50
20
—
3
8
52
—
4
37
63
15
5
55
67
21
6
37
69
—
DETRANSPFE
679.1
79
1
0
18
—
2
36
11
—
3
77
47
—
4
38
67
15
5
57
70
19
6
22
52
—Resulting link flows and degree of saturation values resulting from three models are presented in Tables5(a) and 5(b), respectively.Table 5
(a) Equilibrium link flows resulting from three models, (b) degree of saturation values resulting from three  models.
(a)
Final values of SUE link flows (veh/h)
Links
GA-based [7]
HS-based [30]
DETRANSPFE
1
716
718
769
2
463
462
411
3
716
718
769
4
569
594
528
5
636
638
592
6
173
174
146
7
462
461
411
8
478
477
552
9
120
110
99
10
479
479
553
11
499
498
500
12
250
252
250
13
450
450
450
14
789
789
790
15
790
788
791
16
663
662
391
17
409
411
410
18
350
352
349
19
625
629
899
20
1290
1290
1290
21
1057
1069
1079
22
1250
1250
1250
23
837
847
460
(b)
Degree of saturation (%)
Links
GA-based [7]
HS-based [30]
DETRANSPFE
1
36
36
38
2
54
53
36
3
44
43
38
4
54
57
50
5
57
57
54
6
34
35
31
7
62
65
69
8
51
56
64
9
39
57
51
10
80
81
86
11
80
80
79
12
22
23
22
13
75
76
81
14
73
76
75
15
60
58
48
16
63
68
76
17
88
82
79
18
50
52
62
19
78
76
83
20
82
82
81
21
85
79
78
22
72
70
61
23
67
72
54Table5(b) indicates that since the highest degree of saturation, is obtained as 86%, which is less than 90%, the network works under reserve capacity, and traffic flow is uncongested after the application of the DETRANSPFE model.


## 4.1. Test Road Network

The basic layout of the test network and the allocations for signal groups for each intersection are provided in Figures2 and 3, respectively.Figure 2
Allsop and Charlesworth’s [1] test network.Figure 3
Configuration of signal groups.Fixed travel demands for eachO-D pair are given in Table 1. The input data including free-flow travel times and saturation flow rates is given in Table 2.Table 1
Fixed travel demands for eachO-D pair (vehicles/hour).
O-D pairs
F
E
D
B
A
Origin totals
A
200
30
700
250
—
1180
C
900
130
200
20
40
1290
D
100
50
—
250
400
800
E
20
—
30
130
300
480
G
20
60
170
450
550
1250
Destination totals
1240
270
1100
1100
1290
5000Table 2
Input data for test network.
Intersection
Link
t
a
0
s
a
1
1
1
2000
2
1
1600
16
10
2900
19
10
1500
2
3
10
3200
15
15
2600
23
15
3200
3
4
15
3200
14
20
3200
20
1
2800
4
5
20
1800
6
20
1850
10
10
2200
11
1
2000
12
1
1800
13
1
2200
5
8
15
1850
9
15
1700
17
10
1700
21
15
3200
6
7
10
1800
18
15
1700
22
1
3600Using typical values found in practice, the minimum green time,ϕmin, for each group is 7 seconds, and the intergreen times, I, are 5 seconds between incompatible signal groups. The possible range for the network cycle time is set at 36 and 120 seconds. Values of the mutation factor, F, the crossover rate, CR, which are the user-specified parameters of DE, and the weighting factor, λ, are set to 0.80, 0.80, and 10, respectively. The optimization process is terminated after 110 generations for Np=40 (i.e., 4400 function evaluations) in the same manner as Ceylan and Bell’s [7] GA-based modeling.


## 4.2. Computational Results

In order to prove the effectiveness of DETRANSPFE, the model was run 100 times with different random seeds and initial populations for the test network. The convergence behavior of the DETRANSPFE, GA-based, and HS-based models can be seen in Figure4.Figure 4
GA-based [7], HS-based [30], and DE-based model solutions of Allsop and Charlesworth’s network.Figure4 indicates that the best solution was obtained as 679.1 £/h at the 49th generation (i.e., about 1690 function evaluations) with the DETRANSPFE model. The improvement of the network PI is about 28% in comparison with the initial status of the network. It can also be seen from Figure 4 that the DETRANSPFE model performs slightly better than the GA- and HS-based models in terms of the final values of total network performance index. The comparison of GA-based, HS-based, and DETRANSPFE models in terms of the network PI value is given in Table 3.Table 3
Numerical results of three models.
Models
Best PI (£/h)
Mean PI (£/h)
Worst PI (£/h)
GA-based [7]
712.5
N/A
N/A
HS-based [30]
687.7
690.4
704.4
DETRANSPFE
679.1
684.7
690.6
N/A: not available.It can be seen from Table3 that the DETRANSPFE model minimizes the network PI value by about 4.69% and 1.25% better than the GA- and HS-based models, respectively. Furthermore, the highest PI value obtained after 100 runs of the DETRANSPFE model is 690.6 £/h, which may indicate the better solution ability of the DETRANSPFE model. In order to evaluate the average computation times required by three models, the algorithms have been recoded in Visual Basic and run in a PC with a 1.6 Ghz processor and 1 GB ram. Computation time required by the DETRANSPFE model is obtained as 36 minutes, while GA- and HS-based models require about 66 and 43 minutes, respectively. As it has been mentioned in the previous section, the crossover and mutation operators of the GA may lead to an increase in computation time due to the infeasible solutions. Ceylan and Ceylan [30] stated that if signal timing constraints are not satisfied for generated timings, the HS-based model automatically discards those generated signal timings and starts generating new ones. Considering this situation, it may be concluded that the DETRANSPFE completes 4400 function evaluations by about 45% and 16% faster than the GA- and HS-based models, respectively. The network cycle times obtained by the GA-based, HS-based, and DETRANSPFE models is 77, 71, and 79 seconds, respectively. Signal timings resulting from three models are given in Table 4.Table 4
Signal timing values resulting from three models.
Models
Performance Index, PI (£/h)
Cycle time,C(sec)
Junction number,n
Start of green in seconds
Stage 1
Stage 2
Stage 3
GA-based [7]
712.5
77
1
0
32
—
2
59
25
—
3
13
60
—
4
44
72
20
5
64
5
30
6
47
6
—
HS-based [30]
687.7
71
1
0
28
—
2
50
20
—
3
8
52
—
4
37
63
15
5
55
67
21
6
37
69
—
DETRANSPFE
679.1
79
1
0
18
—
2
36
11
—
3
77
47
—
4
38
67
15
5
57
70
19
6
22
52
—Resulting link flows and degree of saturation values resulting from three models are presented in Tables5(a) and 5(b), respectively.Table 5
(a) Equilibrium link flows resulting from three models, (b) degree of saturation values resulting from three  models.
(a)
Final values of SUE link flows (veh/h)
Links
GA-based [7]
HS-based [30]
DETRANSPFE
1
716
718
769
2
463
462
411
3
716
718
769
4
569
594
528
5
636
638
592
6
173
174
146
7
462
461
411
8
478
477
552
9
120
110
99
10
479
479
553
11
499
498
500
12
250
252
250
13
450
450
450
14
789
789
790
15
790
788
791
16
663
662
391
17
409
411
410
18
350
352
349
19
625
629
899
20
1290
1290
1290
21
1057
1069
1079
22
1250
1250
1250
23
837
847
460
(b)
Degree of saturation (%)
Links
GA-based [7]
HS-based [30]
DETRANSPFE
1
36
36
38
2
54
53
36
3
44
43
38
4
54
57
50
5
57
57
54
6
34
35
31
7
62
65
69
8
51
56
64
9
39
57
51
10
80
81
86
11
80
80
79
12
22
23
22
13
75
76
81
14
73
76
75
15
60
58
48
16
63
68
76
17
88
82
79
18
50
52
62
19
78
76
83
20
82
82
81
21
85
79
78
22
72
70
61
23
67
72
54Table5(b) indicates that since the highest degree of saturation, is obtained as 86%, which is less than 90%, the network works under reserve capacity, and traffic flow is uncongested after the application of the DETRANSPFE model.


## 5. Conclusions

A number of methods for the solution of EQND problems have been discussed and new methodologies have been created. In this context, a simulation-optimization based-model, so-called DETRANSPFE, has been developed by combining the DE optimization technique with the TRANSYT traffic simulation tool. The EQND problem, which has been formulated in the bilevel form, has been solved by searching for the optimal or near-optimal signal setting strategy on the upper level with the DE optimization technique. On the lower level, the SUE assignment problem has been solved using PFE. In order to prove the effectiveness of the DETRANSPFE model, it has been applied to a well-known test network. Results have shown that the DETRANSPFE model provides better results than those obtained by GA- and HS-based models in terms of the total network performance index. In order to evaluate the average computation times required by three models, GA- and HS-based algorithms have been recoded and run. Results indicated that the DETRANSPFE model requires about 45% and 16% less computational time in comparison with the GA- and HS-based models, respectively.Several directions, for future research in solving the EQND problem, are possible. For DE, encouraging results indicate that there is a potential for further improvement in its procedures, such as developing a hybrid search mechanism, in which a local search technique is integrated with DE algorithm. Besides, the design of different metaheuristics, which may improve the solution quality in terms of the system performance index and computational time required, may be explored. For practical application purposes, it would be useful to carry out a comparative study based on different metaheuristics within the scope of a case study including a real-sized signal controlled road network.



---

*Source: 696374-2013-08-07.xml*