Parameters of travel cost function.
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
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 . They used the explicit formulation and calculated the reserve capacity of a signalized junction. Afterward, Allsop  formulated a linear program to calculate it for more complex signalized intersections. This approach proposed by Allsop  has been improved by using different saturation flows between stages by Yagar [3, 4]. Wong  used the reserve capacity model to investigate the priority junctions and roundabouts. Wong and Yang  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  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.  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  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.  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  proposed a new approach to find the demand multiplier in the context of reserve capacity with equilibrium constraints. Miandoabchi and Farahani  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  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.  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.  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  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  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  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 . 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
where xa is the flow on link a, 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.
|3||1.5||1500||1 − σ|
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 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:
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 ). The equilibrium link flows, xa(ξ, σa), and corresponding travel costs for O-D pairs, , are obtained by solving user equilibrium traffic assignment problem given below:
where 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 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.
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 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. . 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 . 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 ). 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.
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 (s)||Saturation capacity sa (vehicle per hour)||Green-time ratio σ|
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 .
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.
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 β 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 link||Equilibrium flow xa (vehicles per hour)||Saturation capacity sa (vehicles per hour)||Green-time ratio σ||Capacity paCa(σa, sa) (vehicles per hour)|
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||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|
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.