Parameters of travel cost function.
Abstract
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.
Keywords
- 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
where
Link no. | |||
---|---|---|---|
1 | 3.5 | 1500 | – |
2 | 1.5 | 1200 | |
3 | 1.5 | 1500 | 1 − |
4 | 1.0 | 1500 | – |
It is supposed that the cycle time is 80 s for the signalized intersection numbered 3 in Figure 1. Let
where
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
3. Formulation of the problem
Let us assume that a road network has a set of links,
subject to
Eq. (6) represents the constraint of equity and Eq. (7) is related to the link capacity constraint in which
subject to
where
In order to represent travel costs of users on link
where
where
where the first term of Eq. (15) is the inverse of the function
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:
The flowchart of bilevel-heuristic solution algorithm based on the HS is given in Figure 2.
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.
The number of link | Free-flow travel time | Saturation capacity | Green-time ratio |
---|---|---|---|
1 | 270 | 5000 | |
2 | 270 | 3000 | 1 |
3 | 270 | 6000 | 1− |
4 | 450 | 6000 | 1− |
5 | 270 | 6000 | 1− |
6 | 270 | 6000 | |
7 | 270 | 3000 | 1 |
8 | 270 | 6000 | |
9 | 270 | 3000 | 1− |
10 | 270 | 5000 | |
11 | 270 | 3000 | 1 |
12 | 270 | 6000 | 1− |
13 | 405 | 4000 | 1 |
14 | 270 | 6000 | 1− |
15 | 270 | 2500 | 1 |
16 | 270 | 3000 | 1 |
17 | 270 | 3000 | |
18 | 540 | 4500 | |
19 | 270 | 4000 | 1 |
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
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
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.
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.
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
The number of link | Equilibrium flow | Saturation capacity | Green-time ratio | Capacity |
---|---|---|---|---|
1 | 1188 | 5000 | 0.61 | 2745 |
3 | 1969 | 6000 | 0.39 | 2106 |
4 | 1920 | 6000 | 0.39 | 2106 |
5 | 1338 | 6000 | 0.39 | 2106 |
6 | 1820 | 6000 | 0.61 | 3294 |
8 | 0 | 6000 | 0.61 | 3294 |
9 | 0 | 3000 | 0.39 | 1053 |
10 | 1704 | 5000 | 0.61 | 2745 |
12 | 768 | 6000 | 0.39 | 2106 |
14 | 768 | 6000 | 0.39 | 2106 |
17 | 367 | 3000 | 0.61 | 1647 |
18 | 2333 | 4500 | 0.61 | 2471 |
In order to test the effect of parameter
Objective function value | 0.672 | 0.643 | 0.640 | 0.640 |
Demand multiplier ( | 1.488 | 1.556 | 1.562 | 1.562 |
Green-time ratio ( | 0.607 | 0.610 | 0.590 | 0.590 |
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
References
- 1.
Webster FV, Cobbe BM. Traffic Signals. London: Ministry of Transport; 1966 - 2.
Allsop RE. Estimating the traffic capacity of a signalized road junction. Transport Research. 1972; 6 :245-255 - 3.
Yagar S. Capacity of a signalized road junction: critique and extensions. Transportation Research. 1974; 8 :137-147 - 4.
Yagar S. Addressing errors and omissions in papers on intersection capacity maximization. Transportation Research. 1985; 19B :81-84 - 5.
Wong SC. Group-based optimization of signal timings using the TRANSYT traffic model. Transportation Research. 1996; 30B :217-244 - 6.
Wong SC, Yang H. Reserve capacity of a signal-controlled road networks. Transportation Research. 1997; 31B :397-402 - 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.
Ge YE, Zhang HM, Lam WHK. Network reserve capacity under influence of traveller information. Journal of Transportation Engineering. 2003; 129 :262-270 - 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.
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.
Chiou SW. Reserve capacity of signal-controlled road network. Applied Mathematics and Computation. 2007; 190 :1602-1611 - 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.
Chiou SW. Optimal signal-setting for road network with maximum capacity. Information Sciences. 2014; 273 :287-303 - 14.
Wang J, Deng W, Zhao J. Road network reserve capacity with stochastic user equilibrium. Transport. 2015; 30 (1):103-116 - 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.
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.
Meng Q, Yang H. Benefit distribution and equity in road network design. Transportation Research Part B. 2002; 36 :19-35 - 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.
Frank M, Wolfe P. An algorithm for quadratic programming. Naval Research Logistics Quarterly. 1956; 3 :95-110 - 20.
Li ZC, Ge XY. Traffic signal timing problems with environmental and equity considerations. Journal of Advanced Transportation. 2014; 48 :1066-1086 - 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.
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.
Geem ZW, Kim JH, Loganathan GV. A new heuristic optimization algorithm: Harmony search. Simulation. 2001; 76 (2):60-68 - 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.
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.
Geem ZW. Optimal Design of Water Distribution Networks using Harmony Search [thesis]. Seoul, Korea: Korea University; 2000