Open access peer-reviewed chapter

Reserve Capacity Model for Optimizing Traffic Signal Timings with an Equity Constraint

Written By

Ozgur Baskan and Cenk Ozan

Submitted: March 21st, 2017 Reviewed: September 8th, 2017 Published: December 6th, 2017

DOI: 10.5772/intechopen.70883

Chapter metrics overview

1,470 Chapter Downloads

View Full Metrics


This paper represents a solution algorithm for optimizing traffic signal timings in urban road networks by considering reserve capacity with an equity constraint. It is well known that the variation of signal timings in a road network may cause an inequity issue with regard to the travel costs of road users travelling between origin-destination (O-D) pairs. That is, the users may be influenced differently by changing traffic signal timings. In this context, the bilevel programming model is proposed for finding reserve capacity for signalized road networks by taking into account the equity issue. In the upper level, the reserve capacity is maximized with an equity constraint, whereas deterministic user equilibrium problem is dealt in the lower level. In order to solve the proposed model, a heuristic solution algorithm based on harmony search combined with a penalty function approach is developed. The application of the proposed model is illustrated for an example road network taken from a literature.


  • reserve capacity
  • equity constraint
  • penalty function
  • bilevel programming
  • harmony search

1. Introduction

For decades, the term reserve capacity has been utilized for optimizing traffic signal timings as an objective. As known, it has been usually applied to signalized intersections and is defined as demand multiplier for existing origin-destination (O-D) demand matrix by considering cycle time, saturation capacity, green timings, and other corresponding constraints. Up to now, many researchers have carried out several works on this concept. The concept of reserve capacity was firstly applied by Webster and Cobbe [1]. They used the explicit formulation and calculated the reserve capacity of a signalized junction. Afterward, Allsop [2] formulated a linear program to calculate it for more complex signalized intersections. This approach proposed by Allsop [2] has been improved by using different saturation flows between stages by Yagar [3, 4]. Wong [5] used the reserve capacity model to investigate the priority junctions and roundabouts. Wong and Yang [6] enhanced the reserve capacity model to a signalized road network with user equilibrium assignment. In their study, it was investigated that how the existing O-D demand matrix may be enlarged by providing that the link flows are operated under their capacities. Ziyou and Yifan [7] used two different objectives such as the reserve capacity and the link capacity expansion. For this purpose, they developed multiobjective solution algorithm, which aims to maximize the reserve capacity and to minimize the investment costs of link capacity expansions by considering signal timings. Ge et al. [8] provided a new approach to investigate how the reserve capacity is influenced by information of the road users. Results emphasized that the increase on the reserve capacity is not affected subsequently with the increase in information of the road users. Ceylan and Bell [9] developed a novel approach to calculate reserve capacity of a signalized network. In their study, optimum values of offsets, common cycle time, and the green times are investigated using genetic algorithm by taking into account stochastic user equilibrium link flows. Chen et al. [10] defined a new index related to capacity and reliability to determine demand multiplier for a signalized road network. The reserve capacity model is improved by considering the new developed index using a bilevel programming (BP) model. Chiou [11] proposed a new approach to find the demand multiplier in the context of reserve capacity with equilibrium constraints. Miandoabchi and Farahani [12] proposed an integrated model, which combined the problem of arrangement of lane directions and lane additions in urban road networks in terms of the reserve capacity. Chiou [13] developed a bilevel programming model to maximize the network’s capacity. A hybrid-search heuristic method has been used to obtain maximum capacity of the road network by minimizing the total delay in terms of signal timings. The method has been applied to signalized road test networks. The results show that the developed algorithm outperforms the classical methods in terms of minimizing the delay. Wang et al. [14] proposed two bilevel programming models: one aims to maximize the reserve capacity in the network by using stochastic user equilibrium link flows, whereas the other one deals with maximizing reserve capacity by considering continuous network design problem. The significant result of their work is that the reserve capacity cannot always be increased by informing of the road users in the network. Xiao et al. [15] developed a reserve capacity model based on zone level to obtain maximum increase in travel demand and to investigate how the use of maximum capacity in the network influences the land-use development. For this purpose, the genetic algorithm has been used to solve the bilevel programming model and the proposed model is applied to a small numerical test network. The results reveal that the proposed reserve capacity model can be used for land-use planning in urban road networks. Recently, Han and Cheng [16] aimed to maximize the reserve capacity with a tradable credit scheme in the context of the stochastic user equilibrium. Numerical examples showed the advantage of the use of tradable credit scheme in maximizing reserve capacity in a given road network.

A short review of the literature shows that the studies for optimizing traffic signal timings within the context of reserve capacity ignored a significant issue. As known, the equilibrium travel costs between O-D pairs are influenced positively or negatively after changing the traffic signal timings in a road network. This may lead to different results for the road users traveling between O-D pairs. Consequently, the inequity problem is generated for the different road users travelling among O-D pairs on a road network. Therefore, the equity issue should be considered to implement more equitable signal control by the local authorities in order to prevent its negative effects on some road users traveling between O-D pairs. For decades, equity issue is started taking into account by researchers for solving some transportation problems. For example, Meng and Yang [17] examined the benefit of distribution between the road users and the inequity problem related to the continuous network design problem with regard to travel costs of users before and after applying a project related to network design. Yang and Zhang [18] proposed a bilevel programming model for the toll-design problem in a given road network by considering the equity constraint.

In the light of overview of literature, this study aims to improve the literature by considering the equity issue and the term of reserve capacity in the signal control problem, in order to provide equitable traffic signal timings on a given road network. A bilevel programming model with an equity constraint on the upper level is developed for determining the highest demand multiplier by setting traffic signal timings on a road network. We use the penalty function method to transfer the equity constraint as a penalty term to upper level objective function and then use harmony search (HS) method to solve it. In the lower level, the user equilibrium (UE) assignment in which the road users follow the user equilibrium principles of Wardrop is carried out using Frank-Wolfe (FW) algorithm proposed by Frank and Wolfe [19]. The rest of the paper is organized as follows: in the next section, an example is given to show the inequity problem occurred after changing the traffic signal timings. Section 3 presents the bilevel-heuristic solution algorithm with an equity constraint. In addition, the penalty function approach is given by incorporating HS approach. In Section 4, the numerical application of proposed model is presented. Conclusions and future studies are remarked in Section 5.


2. Inequity issue in the signal control problem

Consider a simple road network to show the inequity issue arises by changing the traffic signal timings. The road network has two O-D pairs (1→4, 2→4) as can be seen in Figure 1. The travel demands between the given O-D pairs are q14 = 450 and q24 = 350 vehicles per hour, respectively. It is assumed that dashed intersection is signalized as shown in Figure 1. The travel cost function used in the example road network is


Figure 1.

A simple road network.

where xa is the flow on link a, ta0 is free-flow travel time, Ca is the capacity of link a, Ψ is the cycle time, σa is the green-time ratio, and ta(xa) is travel time for link a. The parameters for the example road network are presented in Table 1.

Link no.ta0Caσa
31.515001 − σ

Table 1.

Parameters of travel cost function.

It is supposed that the cycle time is 80 s for the signalized intersection numbered 3 in Figure 1. Let σ be the ratio of effective green time to cycle time on link 2, and it is taken as 0.5 for current situation. In this case, the green-time ratio on link 3 is 0.5. It is assumed that the behavior of the road users’ route choice follows the UE conditions. In this case, the equilibrium travel costs between O-D pairs can be easily obtained using the FW algorithm as follows:


where Z indicates the equilibrium travel cost for O-D pair w in W on the example road network. Suppose the local authority of road network has decided to decrease the green-time ratio on link 2 to 0.30. After applying of this arrangement, equilibrium travel costs between O-D pairs will be


Eq. (3) implies that after decreasing the green-time ratio on link 2, the equilibrium travel cost from origin 1 to destination 4 is decreased and the travel cost from origin 2 to destination 4 is increased. This result means that the road users travelling between O-D pair (2-4) cannot get any benefit from this implementation. Consequently, the inequity problem exists among the road users travelling between O-D pairs. To minimize such negative effects of signal timing setting on a given road network, equity issue should be taken into account. For this purpose, Eq. (4) is proposed to show the level of changing equilibrium travel cost of each O-D pair before and after adjusting the signal timing.


where Z¯w and Zw are defined equilibrium travel costs between O-D pair w in W before and after adjusting the traffic signal timing, and the parameter β is used to characterize the level of equity. This equation ensures that the variation of equilibrium travel cost of each O-D pair after adjusting traffic signal timing does not exceed a predetermined value.


3. Formulation of the problem

Let us assume that a road network has a set of links, A and a set of intersections, N. Its existing O-D demand matrix is represented as q. Assume that a factor ξ is used to increase the existing O-D matrix, and thus the increased O-D matrix can be represented as ξq. Link flow x can be determined by considering the demand multiplier ξ and the green-time ratio σ for signalized intersections on a given road network. Thus, the objective function can be written as given:


subject to


Eq. (6) represents the constraint of equity and Eq. (7) is related to the link capacity constraint in which pa represents degree of saturation for link a and sa is the saturation capacity on link a. In Eq. (8), σi is a vector of green-time ratio for intersection i ∈ I , and matrix Gi and vector bi are variables, which depend on the stage configuration of a given signalized intersection (see for details [20]). The equilibrium link flows, xa(ξ, σa), and corresponding travel costs for O-D pairs, Z¯wxξσ, are obtained by solving user equilibrium traffic assignment problem given below:


subject to


where ta is the travel cost of all users on link a ∈ A. Eq. (10) represents that the sum of the route flows between O-D pair, r-s, has to be demand between same O-D pair. Eq. (11) shows that the flow on a link is to be the sum of the route flows which use this link. Eq. (12) is related to the non-negativity. Since the UE traffic assignment problem is convex, there are different methods, which are able to solve this problem efficiently. One of them is the Frank-Wolfe (FW) method. Indeed, this method is developed for quadratic optimization problems but it is also suitable for obtaining equilibrium link flows on transportation road networks [21, 22]. Therefore, the equilibrium link flows depended on the travel costs between O-D pairs and demand multiplier are calculated by using the FW method in this study.

In order to represent travel costs of users on link a, we suppose that it consists of two components such as flow-dependent running time and a stop delay arises from signal control at any intersection. This definition can be written as


where ta is the travel time on link a ∈ A, α1 and α2 are the values of travel time and stop delay, respectively. The right side of the Eq. (13) represents the stop delay occurred due to signalized intersection. If the considered intersection is not signalized, this term will be zero. It means that travel cost of all users on link a equals to its travel time. The link travel time ta(xa) can be determined by using Bureau of Public Roads function as given below:


where ta0 is the free-flow travel time on link a ∈ A. Considering the reserve capacity maximization problem, the objective function given in Eq. (5) should be evaluated as minimization problem in keeping with the principles of the HS algorithm. Moreover, the constraints of Eq. (5) should be incorporated into the objective function by using the penalty function approach.


subject to Eqs. (9)(12)

where the first term of Eq. (15) is the inverse of the function u, which is the maximization problem, its second term is the penalty function in which θ is used as constant of the penalty, and so u¯ is the minimization problem which will be solved by using the HS algorithm.

3.1. Bilevel programming model

As known, the bilevel programming (BP) model used for the solution of complex engineering problems is NP-hard. Even if the BP model has some disadvantages due to its non-convexity, it would be beneficial for taking into consideration the connection between interrelated problems. It is obvious that the BP model has two levels such as upper and lower levels. Even though both upper and lower levels are convex separately, the convexity of the both levels together cannot be ensured. This can be evaluated as a major disadvantage of the BP model. So, the exact algorithms such as Branch-Bound method can be incapable for the solution of the problem. In the context of reserve capacity, the upper levels deals with finding the maximum value of capacity by considering traffic signal timings while user’s reactions to this changing are determined in the lower level with regard to equilibrium link flows. This mutual interaction can be evaluated by using the BP model effectively. On the other side, there has been increasing trend for the use of meta-heuristic algorithms in solving the BP model in recent years. Therefore, we used the harmony search (HS) algorithm for the solution of the BP model in this study. The HS algorithm is developed by Geem et al. [23]. As known, the musical process performed in an orchestra in order to reach the best harmony is the source of inspiration of this algorithm. The members of an orchestra try to reach the best harmony by making practices, just as searching of the global solution of a given problem can be controlled by some procedures in the HS. The HS algorithm uses four parameters for the solution. The first one is the harmony memory size (HMS), which represents number of population in the harmony memory (HM). The second one is the harmony memory considering rate (HMCR), which is the probability of the use of the HM to diversify the population. The third one is the pitch adjusting rate (PAR), which represents whether the pitch adjustment is required or not; and lastly the number of improvisations (NI), which represent the number of iterations (see for details [24, 25]). The procedure of the HS algorithm is summarized within the context of the reserve capacity maximization in order to brevity of the chapter as following:

Step 0: Set the HS parameters (HMS, HMCR, PAR, and NI) and network related parameters. The values of parameters HMCR, PAR, and HMS vary between 0.70–0.95, 0.20–0.50, and 10–50, respectively, which are proposed in order to obtain satisfying performance by Geem [26]. Therefore, HMS, PAR, and HMCR are used as 10, 0.45, and 0.85 in this study, respectively.

Step 1: Populate the HM with green-time ratio σa for each link a ∈ A (i.e., link connected with signalized intersections) and demand multiplier (ξ).

Step 1.1: Solve the lower level problem (i.e., UE traffic assignment problem) by considering the variables (σ , ξ) generated in Step 1. After obtaining UE link flows, the objective function value of each harmony vector is calculated by using Eq. (15).

Step 2: Considering memory consideration, a new vector is calculated. The first member of the new vector is selected by using the HMCR parameter from the HM with probability of HMCR. The rest members of the vector are selected in similar way. On the other hand, the probability of the (1-HMCR) is used in order to decide whether the member of the new vector is selected from the feasible solution space.

Step 3: This step is related to decide whether the adjustment of the pitch is required or not. For this purpose, the PAR parameter is used and it varies between 0 and 1. After memory consideration step, the members of the new vector are increased or decreased with the probability of PAR by considering bw which is an arbitrary bandwidth (see for details [23]). The use of the probability of (1-PAR) provides that the corresponding value of the member of the new vector remains unchanged.

Step 4: Solve the lower level problem for the new vector. Then the corresponding objective function value is calculated by using Eq. (15).

Step 5: All objective function values stored in the HM are sorted from the best to the worst, and if the objective function value of the new vector is better than the worst one in the HM, the new vector is included into the HM instead of the worst one.

Step 6: Termination criterion. The algorithm is ended, if the number of iterations reached its maximum value. Otherwise go to Step 2.

The flowchart of bilevel-heuristic solution algorithm based on the HS is given in Figure 2.

Figure 2.

Flowchart of the bilevel-heuristic solution algorithm based on the HS.


4. Numerical application

The proposed bilevel-heuristic solution algorithm has been applied to example test network, which consists of 19 links, 13 nodes, and 4 O-D pairs as shown in Figure 3. The corresponding link parameters, such as free-flow travel time and saturation capacity, are given in Table 2.

Figure 3.

Example test network.

The number of linkFree-flow travel time ta0 (s)Saturation capacity sa (vehicle per hour)Green-time ratio σ

Table 2.

Link parameters used in the test network.

The gray filled nodes are considered as signalized intersections as shown in Figure 3. Each of all signal-controlled intersections has two stages and their cycle time is assumed as 90 s. On the other hand, maximum and minimum values of the green-time ratio for each signalized intersection are 0.8 and 0.2, respectively. The O-D demands between nodes 1 and 2, nodes 1 and 3, nodes 4 and 2, and nodes 4 and 3 are 1500, 1000, 1000, and 1500 vehicle per hour, respectively. The maximum degree of saturation flow pa is assumed as 0.9. Further assumptions are made on the values of travel time and stop delay and they are considered as α1 = 20 and α2 = 40 $/hour [20].

The convergence graph of the bilevel-heuristic solution algorithm can be seen in Figure 4. It is assumed that the algorithm is terminated, when it reached the considered maximum number of iterations, namely 300. Taking into account of minimum and maximum values of green-time ratio, the proposed algorithm increases gradually the demand multiplier especially after 25 iterations. While the value of demand multiplier was about 1.1 at the first iteration, it reached the value of 1.55 with increasing of about 36% at the final iteration. It is obvious that this result has been achieved with taking into account the constraints of the link capacities, equity parameter, and signal timings. The equity parameter of β was fixed as 0.1 for this solution.

Figure 4.

Convergence graph of the bilevel-heuristic solution algorithm.

In this context, we have shown the equilibrium link flows after increasing total demand with multiplier of 1.55 as seen in the network given in Figure 5. While the total demand between four O-D pairs was 5000 before applying the demand multiplier to the network, it reached to 7777 vehicles per hour as shown in Figure 5. It should also be emphasized that there is no flow on the links numbered 8 and 9, which arises from the fundamental principle of the UE assignment. Another significant issue is that the links that carry lowest and highest flows are 17, 13, and 19.

Figure 5.

Equilibrium link flows after applying demand multiplier.

It is pointed out that even then the links approaching to the signalized intersections in the network are operated under their capacities. This can be seen in Figure 6. In Figure 6, the gray bars represent capacities of the links approaching to signalized intersections, whereas the black bars show the equilibrium link flows. As can be seen in Figure 6, even though the equilibrium flows on the links numbered 3, 4, and 18 are quite high, they continue to serve under their capacities.

Figure 6.

Comparison of equilibrium link flows and their capacities on signalized intersections.

The significant parameters of the links approaching to the signalized intersections are given in Table 3. The green-time ratios are also obtained after running the bilevel-heuristic solution algorithm under fixed value of parameter β as shown in Table 3. When we consider the signalized intersection numbered 5, which has two approaching links, namely 1 and 3, the green-time ratio has found 0.61 for the link 1 and 0.39 for the link 3. Since each of the signalized intersections has two stages, the sum of green-time ratios of two links is equal to one. In addition to this, we have shown also the capacities of links which are calculated taking into account degree of saturation, saturation capacity, and green-time ratio. Again, it can be seen that the flows of the considered links are operated under their capacities.

The number of linkEquilibrium flow xa (vehicles per hour)Saturation capacity sa (vehicles per hour)Green-time ratio σCapacity paCa(σa, sa) (vehicles per hour)

Table 3.

The parameters of the links approaching to signalized intersections for β = 0.1.

In order to test the effect of parameter β on the solution algorithm, it has been run for different values for β and the corresponding results are given in Table 4. While parameter β is increased from 0.05 to 0.20, the objective function values decrease in similar ratios. On the other hand, the demand multiplier increases since its value is inversely proportional to the objective function value. The reason for this is that the local authority pays less attention to the equity, so this leads to an increased travel demand in the network. Another significant result of this test is the objective function value and demand multiplier remain stable after a value of 0.15 of equity parameter β.

β = 0.05β = 0.10β = 0.15β = 0.20
Objective function value u¯0.6720.6430.6400.640
Demand multiplier (ξ)1.4881.5561.5621.562
Green-time ratio (σ)0.6070.6100.5900.590

Table 4.

Obtained results using different values of equity parameter β.


5. Conclusions

This study aims to optimize traffic signal timings in terms of reserve capacity by taking the equity constraint into account. In order to create more equitable networks, this phenomenon should be taken into consideration in optimizing traffic signal timings. Thus, the road users in the network are similarly taken advantage by changing traffic signal timings. For this purpose, we developed a bilevel-heuristic solution algorithm based on the HS. While the demand multiplier and green-time ratio are found in the upper level by considering the equity issue, capacity, and signal timings constraints, the UE link flows are determined in the lower level by using the FW algorithm. First, we showed the inequity problem for the users by changing traffic signal timings in a small test network. Results of this small test emphasized that the equity issue should be taken into account to benefit equally for all road users between O-D pairs by changing traffic signal timings. On the other hand, the middle-sized test network has been used in order to show the usability of the proposed solution algorithm for optimizing traffic signal timings with regard to the reserve capacity. It has been found that the proposed algorithm is able to maximize the reserve capacity for optimizing traffic signal timings by considering the equity issue. Results also show that the links in the test network are operated under their capacities, even the demand is increased about 1.5 times for fixed value of equity parameter. Another significant result of this study is that the proposed reserve capacity model is sensitive to the different values of equity parameter β. As the value of β is increased, the value of demand multiplier also increases. This arises from that the authority pays less attention to the equity in high values of β so this leads to an increased travel demand in the network.


  1. 1. Webster FV, Cobbe BM. Traffic Signals. London: Ministry of Transport; 1966
  2. 2. Allsop RE. Estimating the traffic capacity of a signalized road junction. Transport Research. 1972;6:245-255
  3. 3. Yagar S. Capacity of a signalized road junction: critique and extensions. Transportation Research. 1974;8:137-147
  4. 4. Yagar S. Addressing errors and omissions in papers on intersection capacity maximization. Transportation Research. 1985;19B:81-84
  5. 5. Wong SC. Group-based optimization of signal timings using the TRANSYT traffic model. Transportation Research. 1996;30B:217-244
  6. 6. Wong SC, Yang H. Reserve capacity of a signal-controlled road networks. Transportation Research. 1997;31B:397-402
  7. 7. Ziyou G, Yifan S. A reserve capacity model of optimal signal control with user-equilibrium route choice. Transportation Research. 2002;36B:313-323
  8. 8. Ge YE, Zhang HM, Lam WHK. Network reserve capacity under influence of traveller information. Journal of Transportation Engineering. 2003;129:262-270
  9. 9. Ceylan H, Bell MGH. Reserve capacity for a road network under optimized fixed time traffic signal control. Journal of Intelligent Transportation Systems. 2004;8:87-99
  10. 10. Chen A, Chootinan P, Wong SC. New reserve capacity model of signal-controlled road network. Transportation Research Record: Journal of the Transportation Research Board. 2006;1964:35-41
  11. 11. Chiou SW. Reserve capacity of signal-controlled road network. Applied Mathematics and Computation. 2007;190:1602-1611
  12. 12. Miandoabchi E, Farahani RZ. Optimizing reserve capacity of urban road networks in a discrete network design problem. Advances in Engineering Software. 2011;42:1041-1050
  13. 13. Chiou SW. Optimal signal-setting for road network with maximum capacity. Information Sciences. 2014;273:287-303
  14. 14. Wang J, Deng W, Zhao J. Road network reserve capacity with stochastic user equilibrium. Transport. 2015;30(1):103-116
  15. 15. Xiao H, Gao J, Zou Z. Reserve capacity model based on variable demand for land-use development control. Transportation Planning and Technology. 2017;40(2):199-212
  16. 16. Han F, Cheng L. Stochastic user equilibrium model with a tradable credit scheme and application in maximizing network reserve capacity. Engineering Optimization. 2017;49(4):549-564
  17. 17. Meng Q, Yang H. Benefit distribution and equity in road network design. Transportation Research Part B. 2002;36:19-35
  18. 18. Yang H, Zhang X. Multiclass network tool design problem with social and spatial equity constraints. Journal of Transportation Engineering. 2002;128:420-428
  19. 19. Frank M, Wolfe P. An algorithm for quadratic programming. Naval Research Logistics Quarterly. 1956;3:95-110
  20. 20. Li ZC, Ge XY. Traffic signal timing problems with environmental and equity considerations. Journal of Advanced Transportation. 2014;48:1066-1086
  21. 21. Baskan O. Determining optimal link capacity expansions in road networks using Cuckoo search algorithm with Lévy flights. Journal of Applied Mathematics. 2013;2013:718015, 11 pages
  22. 22. Baskan O. Harmony search algorithm for continuous network design problem with link capacity expansions. KSCE Journal of Civil Engineering. 2014;18(1):273-283
  23. 23. Geem ZW, Kim JH, Loganathan GV. A new heuristic optimization algorithm: Harmony search. Simulation. 2001;76(2):60-68
  24. 24. Dell’Orco M, Baskan O, Marinelli M. A Harmony Search algorithm approach for optimizing traffic signal timings. PROMET Traffic & Transportation. 2013;25(4):349-358
  25. 25. Baskan O. An evaluation of heuristic methods for determining optimal link capacity expansions on road networks. International Journal of Transportation. 2014;2(1):77-94
  26. 26. Geem ZW. Optimal Design of Water Distribution Networks using Harmony Search [thesis]. Seoul, Korea: Korea University; 2000

Written By

Ozgur Baskan and Cenk Ozan

Submitted: March 21st, 2017 Reviewed: September 8th, 2017 Published: December 6th, 2017