# Performance Analysis of Decentralized VS Centralized Control for the Traffic Signal Synchronization Problem

Authors: Ludovica Adacher; Marco Tiriolo
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

This paper suggests the adoption of a spatial decomposition method to solve the signal synchronization problem. A good signal setting maximizes the number of vehicles passing through intersections, while minimizing gas emissions and possible delays experienced by drivers. The signals synchronization issue can be defined as the problem of finding the offsets, the green timings, and the cycle length for a series of controlled intersections, minimizing the total delay of the network subject to admissibility constraints. In this paper, the authors optimized the signal setting through a new Surrogate Method calculating the objective function via theCTMUT model while performing a simulation. A spatial decomposition approach is here suggested with a simultaneous analysis of different levels of cooperation among subnetworks. This study tries to identify a subnetwork that might be representative of the entire network while taking into consideration two factors: efficiency and efficacy. A comparison between centralized and decentralized control is performed.


---

## Body

## 1. Introduction

Traffic congestion can be reduced through a traffic signal control. A traffic signal control gives an improvement both for the drivers (minimizing travel time and delay) and for the environment (reducing both the energy consumption and gas emission). Nevertheless, controlling the traffic signals of a transportation network is a significant challenge due to its large-scale and complexity. Traffic congestion on roads is a serious problem, especially for big cities in the world.The traffic signal synchronization is a nonconvex problem and sometimes finding a quick and optimal solution even for small networks can be difficult [1, 2]. It has been showed that the improvement in the traffic flow can reduce fuel consumption, gas emissions and accidents [3–6].The signal synchronization problem consists in the simultaneous optimization: the offsets, the green timings and the cycle length at each junction (computed by delay minimization) for a series of junctions see [7].According to the classification presented in [8], there are three different approaches to solve the problem:(i)
Centralized approach: The majority of signal timing optimization algorithms use a centralized formulation and architecture. At the same time, for all intersections, they optimize various signal timing parameters (i.e., cycle length, green times, and offsets). However, network signal timing optimization is an NP-hard problem and a central optimization technique will not be scalable and applicable to large transportation networks [1, 9–12].(ii)
Hierarchical or distributed approaches decompose the network optimization problem into a multilevel control problem with distinct objectives at each level. The underlying concept of most hierarchical approaches is to make network level decisions at the upper (or central) level and the real-time, small-area computations in the lower (or intersection) level. The exchange of information is a crucial aspect [13–17].(iii)
Decentralized approaches decompose the network into regions with varying number of intersections. As the result of the decentralization, these approaches are scalable and can be real-time; however, rather than global optimization, they mostly locally control signals and may find a suboptimal solution [8, 18–23].It is evident that a centralized system will theoretically be able to find optimal solutions, though with a higher amount of information on the system than its distributed counterpart. However, the computation time of a centralized control increases exponentially together with the size of the urban network thus preventing its processing. It is also expected that a centralized system may theoretically provide a more effective control policy than its decentralized counterparts with a better coordination among network components. As a result of the decentralization, these approaches are scalable and can be on real-time basis; however, they control local signals and often find suboptimal solutions. The first developed commercial software is based on a centralized control system, where one computing unit decides for all intersections (e.g., SCOOT and SCATES) or hierarchical architectures where one part of the decision is centralized whereas the other is local (e.g., MOTION and RHODES).Often the literature suggests a decentralized approach which optimizes each intersection separately and the information used is not sufficient to optimize the offset among intersections, finding suboptimal solutions. Several authors tend to suggest a decomposition based on a single intersection either without or a limited exchange of information. The adaptive traffic signal control systems are used to accommodate real-time traffic conditions. In fact recent development of artificial intelligence, especially the success of deep learning, gives the possibility to use information of individual vehicles to control traffic signals. However, those studies are limited to isolated intersections and their effectiveness was only evaluated in ideal simulated traffic conditions by hypothetical benchmarks (see [24–27]). On the other hand, in [28] the authors evaluating an algorithm through real-world coordinated actuated signals, in a simulated suburban traffic corridor, emulate the real-field traffic condition. However, a corridor (a main street) with eight signals is considered under control. In [29], the author divides the network into individual intersections and proposes a dynamic programming algorithm to minimize total queue length at each intersection. The authors of [30] propose a rolling horizon based on predictive microscopic simulation algorithms based on cumulative vehicle delay. The max-pressure control is of great theoretical significance in terms of the decentralized control, which is able to guarantee the global stability by implementing a localized control policy. The back-pressure controller is a distributed feedback system which does not require knowledge of the global network inflow. Also the back-pressure controller adjusts just local green splits based on both upstream and downstream local queue length measured at each intersection. In [31], the author proposes an a-cyclic distributed max-pressure signal controller based on measurements of queue lengths at adjacent intersections. In [21], the author extends Varaiya’s work to cycle-based control with the exertion of logic function for the network-wide coordination. Others authors propose a decomposition approach but their test cases are not detailed enough (often they are corridors instead networks) or introduce more simplification for the optimization process. In [32], the authors propose for the freeway ramp metering a distributed optimization algorithm based on the multi-agent A-ADMM formulation, applied to both shared control and shared state systems. In [22], the authors introduce a decomposition mechanism for the global anticipatory network traffic control problems, based on dynamic clustering of traffic controllers. Their technique gives the possibility to recognize when and which controllers should be grouped in clusters, and when they can be optimized separately.Despite the decentralized approaches presented in literature, there are only a few studies comparing the performance of the distributed system to its centralized version. The authors of [20] propose a decentralized approach based on max-pressure controller, to evaluate their performances; the control systems are applied to a two-dimensional three-by-three grid network. The decentralized approach reaches an optimal level of about 22%. In [19], they present an alternative decentralized solution approach based on the neighbourhood concept, analyzing a real urban network of 58 signal-controlled. The discrepancies between the centralized and decentralized controllers are about 20%–30% with a reduction to 8%–15% once the network traffic router is introduced. In [23], the authors propose a distributed traffic signal control based on Cell Transmission Model. For lager topology up to 72 intersections, the decentralized approach, which requires no communication, reaches an optimal level of about 30%, with two rounds of communication about 8%. In all these studies that examine the decentralized approaches they present different objectives functions (delay, total travel time, and queue) and they solve the signal setting problem fixing only the green time of the controlled intersections whilst the cycle and the offset are not taken into consideration, thus reducing both the complexity of the problem and computational time. The main contributions of this study are the following:(i)
The objective function is the delay minimization. The delay is considered as the number of vehicles obstructed in the road section. Consequentially, the time saving due to signals synchronization reduces pollution produced by traffic and fuel loss due to low running speed.(ii)
The decision variables for the delay minimization are: (i) the green time, (ii) the offset, and (iii) the cycle for each controlled intersection (rather than only the green time).(iii)
The network is decomposed in sub-networks (rather than in individual intersections); network, rather than the neighborhood concept.(iv)
The proposed clustering is based on the physical topology and on the features of the urban road network (rather than the neighborhood concept).(v)
The analysis is performed on a real-world network with 56 signalized intersections and 39 intersections under control (rather than on small networks or corridors).In our previous studies, we have demonstrated the effectiveness of the Surrogate Method to solve the traffic signal synchronization problem proposing a centralized approach. However, the computing time grows with the size of decision vector (i.e., the urban network that needs to be optimized). The Surrogate Method is applied to single sub networks, minimizing the total delay and optimizing the cycle, the offset, and the green time ratio. Different levels of exchange of information between subnetworks are considered. In this paper, a decentralized approach is presented, and a comparison with a centralized approach is reported. Generally, a decentralization approach is created as a way to improve efficiency and take advantage of potential economies of scale. In fact, decentralization looks to improve the speed and flexibility. Our aim is to find a decentralized approach with a good trade off between optimality and computational time.


### 1.1. Contribution of the Paper

As shown previously, signal timing optimization in an urban network is an NP problem and a central approach is not able to find the optimal solution in a reasonable amount of time. The hierarchical approaches can find solutions faster but require significant investment in infrastructure to provide communications between a central unit and each local optimizer. The existing decentralized approaches find suboptimal signal timing parameters. Given the interactions among travellers and between travellers and the network in the transportation system, it is difficult to formulate pure mathematical models to evaluate performances. Simulation has been more widely used as the tool to evaluate transportation system performance under different policies. When the system operates in a stochastic environment and no closed form expression for objective function is available, the problem is further complicated by the need to estimate the function. In this case, traditional optimization methods based on derivatives cannot be applied. Most known approaches are based on some form of random search, or ordinal optimization approach. In addition, also being the simulation computationally expensive, the extensive exploration of the entire solution domain would imply unacceptable calculation time [33]. To avoid these problems, the Surrogate Method is introduced, first for manufacturing problem and then also for transportation problem [1, 9, 34]. This method combines the advantages of stochastic approximation type of algorithm with the ability to obtain sensitivity estimates. The gradient information necessary to drive the stochastic approximation part of the Surrogate Method is simplified considering the estimation of the objective function for a selection set (it will be describe in Section 4). In previous studies, it is demonstrated the capacity of the Surrogate Method (SM) to find central optimal solution to problems concerning signal setting and combined signal setting, due to its ability to jump out of local minimum. Hence, it is showed the efficacy and the efficiency of the SM with respect to the Projected Gradient Algorithm (PGA), the Particle Swarm Optimization (PSO), and the Genetic Algorithm (GA) (see [9, 35]). Given the complexity of this problem, a spatial decomposition method is introduced. The methodology here suggested can efficiently find optimal solutions without the need of a central unit. Specific contributions of this paper are as follows:(i)
Different decomposition of the network is proposed(ii)
Different decentralized approaches based on different levels of cooperation are suggested(iii)
Some simplifications to reduce the calculation time ofSM are introduced(iv)
A comparison between centralized and decentralized approach is presentedGiven the characteristics of the signal setting problem, in this paper, some simplifications for theSM have been introduced, while suggesting to reduce the complexity of the problem thought the network decomposition. Given the subnetworks and considering different levels of cooperation, the new SM is applied. The decomposition approach wants to reduce the computational time in order to find a solution that might be compatible with the central optimal solution. It is important to notice that the SM complexity is strictly related to the dimension of the network. Given a reduction in the network dimension, it is possible to obtain a significant reduction of the computational time.The signal setting improves driver safety, but it also provokes delays. For this reason, many researches try to minimize total delay, being the sum of all vehicles delays. This objective function is often calculated through simulation approaches. TheCTMUT is assumed in order to calculate the total delay caused by the signalized intersections. A centralized solution will provide a better performance, but it is often unrealistic. Unfortunately, the traffic signal synchronization is a complex (NP-hard) problem, and it is usually hard to be managed, hence it is unfit for online decision making, especially when the problem involves several intersections and a large time horizon. The centralized solution also presents disadvantages because it requires global information concerning the status of the network, and it is not robust, if a failure occurs in the network the system must recalculate a new solution. On the other hand, distributed strategies can be more robust to failures, and distributed approaches can find good application in different fields [8, 18, 23].The approach is described in Figure1. In Urban Traffic Simulation, the value of the objective function is calculated via simulation utilizing the CTMUT; in Traffic Control, the values of signal settings are defined by the Surrogate Method and the Network Clustering Method identifies different subnetworks that are considered for the signal setting optimization. In other words, thanks to the Simulator the flow in the nodes of the network, and the value of the objective function is determined. Selecting the nodes Priority through the clustering method, the Surrogate Method finds the best signal settings for a sub network, optimizing the entire network.Figure 1
Scheme of our approach.The remainder of the paper is organized as follows: The problem description is given inSection 2. In Section 3, the suggested method for the spatial decomposition and the levels of cooperation are described. Surrogate Method and its improvements are reported in Section 4. Section 5 provides some simulation results, and Section 6 draws the conclusions. In APPENDIX, the CTMUT and the clustering methods are reported. These concepts are known in the literature and are reported to facilitate understanding of the proposed approach.


## 1.1. Contribution of the Paper

As shown previously, signal timing optimization in an urban network is an NP problem and a central approach is not able to find the optimal solution in a reasonable amount of time. The hierarchical approaches can find solutions faster but require significant investment in infrastructure to provide communications between a central unit and each local optimizer. The existing decentralized approaches find suboptimal signal timing parameters. Given the interactions among travellers and between travellers and the network in the transportation system, it is difficult to formulate pure mathematical models to evaluate performances. Simulation has been more widely used as the tool to evaluate transportation system performance under different policies. When the system operates in a stochastic environment and no closed form expression for objective function is available, the problem is further complicated by the need to estimate the function. In this case, traditional optimization methods based on derivatives cannot be applied. Most known approaches are based on some form of random search, or ordinal optimization approach. In addition, also being the simulation computationally expensive, the extensive exploration of the entire solution domain would imply unacceptable calculation time [33]. To avoid these problems, the Surrogate Method is introduced, first for manufacturing problem and then also for transportation problem [1, 9, 34]. This method combines the advantages of stochastic approximation type of algorithm with the ability to obtain sensitivity estimates. The gradient information necessary to drive the stochastic approximation part of the Surrogate Method is simplified considering the estimation of the objective function for a selection set (it will be describe in Section 4). In previous studies, it is demonstrated the capacity of the Surrogate Method (SM) to find central optimal solution to problems concerning signal setting and combined signal setting, due to its ability to jump out of local minimum. Hence, it is showed the efficacy and the efficiency of the SM with respect to the Projected Gradient Algorithm (PGA), the Particle Swarm Optimization (PSO), and the Genetic Algorithm (GA) (see [9, 35]). Given the complexity of this problem, a spatial decomposition method is introduced. The methodology here suggested can efficiently find optimal solutions without the need of a central unit. Specific contributions of this paper are as follows:(i)
Different decomposition of the network is proposed(ii)
Different decentralized approaches based on different levels of cooperation are suggested(iii)
Some simplifications to reduce the calculation time ofSM are introduced(iv)
A comparison between centralized and decentralized approach is presentedGiven the characteristics of the signal setting problem, in this paper, some simplifications for theSM have been introduced, while suggesting to reduce the complexity of the problem thought the network decomposition. Given the subnetworks and considering different levels of cooperation, the new SM is applied. The decomposition approach wants to reduce the computational time in order to find a solution that might be compatible with the central optimal solution. It is important to notice that the SM complexity is strictly related to the dimension of the network. Given a reduction in the network dimension, it is possible to obtain a significant reduction of the computational time.The signal setting improves driver safety, but it also provokes delays. For this reason, many researches try to minimize total delay, being the sum of all vehicles delays. This objective function is often calculated through simulation approaches. TheCTMUT is assumed in order to calculate the total delay caused by the signalized intersections. A centralized solution will provide a better performance, but it is often unrealistic. Unfortunately, the traffic signal synchronization is a complex (NP-hard) problem, and it is usually hard to be managed, hence it is unfit for online decision making, especially when the problem involves several intersections and a large time horizon. The centralized solution also presents disadvantages because it requires global information concerning the status of the network, and it is not robust, if a failure occurs in the network the system must recalculate a new solution. On the other hand, distributed strategies can be more robust to failures, and distributed approaches can find good application in different fields [8, 18, 23].The approach is described in Figure1. In Urban Traffic Simulation, the value of the objective function is calculated via simulation utilizing the CTMUT; in Traffic Control, the values of signal settings are defined by the Surrogate Method and the Network Clustering Method identifies different subnetworks that are considered for the signal setting optimization. In other words, thanks to the Simulator the flow in the nodes of the network, and the value of the objective function is determined. Selecting the nodes Priority through the clustering method, the Surrogate Method finds the best signal settings for a sub network, optimizing the entire network.Figure 1
Scheme of our approach.The remainder of the paper is organized as follows: The problem description is given inSection 2. In Section 3, the suggested method for the spatial decomposition and the levels of cooperation are described. Surrogate Method and its improvements are reported in Section 4. Section 5 provides some simulation results, and Section 6 draws the conclusions. In APPENDIX, the CTMUT and the clustering methods are reported. These concepts are known in the literature and are reported to facilitate understanding of the proposed approach.


## 2. Problem Description

Over the past years, the well-known Cell Transmission Model (CTM by Daganzo [36]) has been extended, modelling practical applications. Considering the queue formation, queue dissipation, and kinematic waves, the CTM can be used to represent the real traffic dynamic. Recently, many extensions of CTM have been used for signal setting problem [37–41]. The Cell Transmission Model for Urban Traffic (CTMUT) is a good compromise between accuracy and computational complexity.TheCTMUT represents for each node the connection between the demand upstream intersections and the supplies downstream intersection, and it is also takes into consideration the percentages of the demand of turns for every single lane.TheCTMUT considers also behaviors of urban drivers (i.e., the movements that model drivers that by mistake take the channelized lane for right-turn).Given the urban networkUNN,E, where N is the set of controlled intersection i (nodes), and E is the set of links ei,j (edges), for a fixed value of the cycle C, the green split ratio is represented by g1,…,gM and the offsets by θ1,…,θM and M are the controlled intersection links (i.e., the traffic lights). The CTMUT is used to evaluate the objective function: the global delay of the network JDC,g1,…,gM,θ1,…,θM.The delay is considered as the number of vehicles obstructed in the road section (as in the paper of Lo see [42]). For each cell, the delay is defined as the difference between the number of vehicles that could travel in the downstream cell less the vehicles travelling in the downstream cell. The total delay includes both the upstream and the downstream node delay (for more details see APPENDIX).The delay of celli at time k is equal to the number of its vehicles in it minus the number of vehicles flowing into the next cell i + 1. The delay of the whole network is obtained by aggregating all cells during the time horizon (T).(i)
T = the time horizon(ii)
M = are controlled intersection links(iii)
k = period time(iv)
Na = the total number of cells of the link a(v)
niak = the nominal flow in the cell i of the link a for the period k(vi)
yiak = flow into cell i of the link a for the period k(vii)
yNa+1ak = outflow from the next cell Na+1 of the link a for the period kThe problem is formulated as follows:(1)minC,g,θ∈AdJDC,g,θ,T=∑k=1T∑a=1M∑i=1Naniak−yi+1ak,with the capacity constraints(2)Ad=g≔g1,…,gM′,gmin≤gi≤gmax,∑∀j:ej,i∈Egi=C,gi∈ℤ+;i=1,…,Mθ≔θ1,…,θM′,0≤θi≤1;θi∈ℤ+,i=1,…,M,where(i)
C is the cycle, which is the same for all intersection links i(ii)
g is an M-dimensional decision vector with gi∈ℤ+ denoting the green time ratio for intersection link i(iii)
whereθ is an M-dimensional decision vector with θi∈ℤ+ denoting the offset for intersection link i(iv)
gmin = minimum green time ratio for signalized link a fulfilling capacity constraint(v)
gmax = maximum green time ratio for signalized link a fulfilling capacity constraintJDC,g,θ,T is the total delay on the network when the decision variables (green split vector, offsets, and cycle) are fixed.Thegmin and gmax guarantee a minimum of green and red for a traffic light. The decision variables concern only the links connected to the signalized intersection (i.e., intersection with the traffic light).The analysis of the objective function shows that this function is convex with respect to the cycle; instead it presents many local minimum with regard to the green split vector and offsets. Since the Surrogate Method calculation time is strictly dependent on the size of the problem, the cycle is not optimized by Surrogate Method. The Cycle is the same for all junctions and fixed by the binary search, and only after it has been found its optimum value the Surrogate Method is applied. The shape of the objective function looks convex with respect to the cycle variations and it is quasiconvexity respect when the green ratio changes and non convex with many peaks, with respect to the offset variations. From this analysis, it seems that the hardest task for signal synchronization problem is the offset setting. Figure2 shows an example of the shape related both to one component of the green split vector variation and one offset variation. To visualize the characteristics of the solution space, it is not necessary to perform the average system time for all possible combinations of cycle/green time ratio/offset. In order to show the characteristics of the solution space, the cycle, the offset, and all green time ratio are kept constant, except for one component at time for each decision vector (or cycle or offset or green time). It is done for different values of green/offset/cycle that are kept constants.Figure 2
Shape of the objective function.
(a)(b)


## 3. Decentralized Approach

Spatial problem decomposition is the process that divides in small areas the space used for the optimization. The optimization of the decomposition is to identify some subsets of traffic lights that can be representative for the entire network [18, 21, 23].Based on the physical topology model of the urban road traffic network, urban networkUNN,E is defined considering the functional properties of urban road network such as the length and traffic capacity of the road sections, and the following definitions can be taken into consideration:(i)
N=n1,n2,…,nn is the finite set of the nodes which means the controlled intersections, n is the number of controlled intersections.(ii)
E=eij:i,j∈N is the finite set of the edges that means the sections of the road through which the two intersections can be connected directly. E is the number of elements in set E and it represents the number of the controlled links (eij≠eji).(iii)
EL:E⟶ℝ is the mapping function from an edge to a positive real number, ELeij=lij is the length of the road section eij.(iv)
Pi,j∗:N⟶ℝ is the mapping function from a couple of nodes i,j∈N to a positive real number, Pi,j∗ is the length of shortest path from i to j.(v)
ETC:E⟶ℤ is the mapping function from an edge to a positive integer, ETCeij=tcij is the traffic capacity of the road section eij.


### 3.1. Hybrid Clustering

A classification for the nodes of the urban network is introduced to define a new clustering method. A Node Priority considering three different parameters is here introduced:Degree D(j) is the simplest measure of the node. The degree of the node is the number of incident edges. Given(3)Xi,j=1,eij∈E,0,Otherwise.The degree of the nodej is calculated as follows:(4)Dj=∑i∈NXi,j+Xj,i.BetweennessB(j): Betweenness is a measure of the importance of the node with respect to the network. It is based on the idea that a node is central if it lies between many other nodes, in the sense that it is traversed by many of the shortest paths connecting couples of nodes.Givendi,k is the number of shortest paths between i and k and di,kj is the number of shortest paths between i and k that contain node j. The betweenness of node j B(j) is(5)Bj=1n−1n−2∑i≠j≠k∈Ndi,kjdi,k.FlowF(j) is the amount of the flow directed into node. Obviously the flow incoming into the node must be equal to the one coming out. Given the Yei,j the flow in to link ei,jFj=∑∀i∈N:eij∈EYei,j.Definition 1 (Node PriorityPj).
The Node PriorityPj is a function assigning a weight to each node j that takes into consideration the importance of the node with respect to the network, based on its degree, betweenness, and flow. The values normalized are(6)Pj=DjD+Bj+FjF.D=∑i=1nDiF=∑i=1nFiDefinition 2 (Network PriorityPUN).
Given the networkUNN,E, the Network Priority is a function that assigns a weight to the network.(7)PUN=∑∀j∈NPj.
The node priority is calculated by the sum of three normalized elements, this implies that each element varies from 0 to 1. For a node, the normalized degree increases with the number of the incident edges on it, and the betweenness increases with the number of the shortest paths traversed it and the normalized flow increases with the flow directed into the node. It is evident that the first two terms can change only if the urban network changes. While considering these priorities it is possible to understand the importance of each node with respect to the network. The Node Priority is also used to determine the Priority of each subnetwork. The Priority of the sub-network is given by the sum of the Priority of each node in the subnetwork. Given the partition, for each node and for each subnetwork, the Priority is calculated.
Given the procedure to calculate the Priority, the proposed algorithm to clustering the network is introduced.
The Hybrid algorithm suggests a clustering of the network considering the Priority method. The Hybrid algorithm adds to the clustering one subnetworkSK+1 composed by the nodes with highest priority on the network. Probably, these nodes are the nodes with more traffic; in fact, highest priority means this node has big probability to be chosen by a driver, because it is traversed by many shortest paths and has many incident edges. The aim of the Hybrid algorithm is to compose a subnetwork representing the whole urban network. It is evident that these most important nodes for the network must be optimize and synchronize, minimizing the total delay of the network. When the green time and the offset of these nodes are optimized, it is possible to optimize the others nodes considering different levels of cooperation. Given a clustering S from well known cluster algorithms and K is the number of clusters, the Hybrid algorithm adds a cluster composed by a set of nodes (not more then K−1+N/K), while selecting the nodes with highest Priority, and at least one node for each cluster in S, deleting these selected nodes from their clusters. The dimension of this new cluster SK+1 is defined through a preprocessing analysis. If in S the cluster with the highest Priority contains few nodes, the Hybrid clustering will consist in K sub networks, otherwise in K+1. The new cluster is composed by the nodes with the highest Priority from each sub network in S. Algorithm 1 reports the steps of the Hybrid algorithm. In Step 1, the main sub network Sk+1 is formed by the sub network S∗ with the highest Network Priority; Step 2 adds to the main sub network Sk+1 the node with the highest Node Priority from the other subnetworks in S. Step 3 guarantees that the dimension of Sk+1 does not exceed K−1+N/K.Example 1.
In Figure3, it is reported on the left side the clustering given by Newman algorithm S=1,2,3,5,6,4,7,8,9 (in bold the nodes with the highest Priority) and on the right the Hybrid clustering SH=1,2,4,5,8,3,6,7,9. The red nodes are the nodes with the the highest Priority. Given the small dimension of the network, SK+1 is set to be equal to 5. The Hybrid cluster gives 4 subnetworks and the new cluster SK+1=1,2,4,5,8 is composed by 5 nodes with the highest Priority almost one for each of the three subnetowrks of Newman: {1,2,5} from the sub network with higher Priority, {4} from the second, and {8} from the third.
Given a clustering of the entire urban network, we proposed different decentralized approaches based on different levels of cooperation between the individuated subnetworks.Algorithm 1: Principal steps of Hybrid algorithm.
Step 0 Given:the networkUNN,E andS=S1,S2,…,SK S is a cluster of K sub-networks given by a clustering methodSk+1= is the new sub-networkSH is the Hybrid clustering set;i,m,j,a int;Pi,∀i∈NPSj,∀Sj∈SStep 1 CalculateS∗=argmaxPSj, ∀Sj∈SS=S−S∗Sk+1=S∗Step 2 WHILES≠ DOSK+1=SK+1+i=argmaxPi, i∈SFORm=1,≤k,m++IFi∈SmSm=Sm−iSH=SH∪SmS=S−SmStep 3 WHILESK+1≥K−1+N/K DOi=argminPi, ∀i∈SK+1S∗=S∗+iSk+1=Sk+1−iStep 4 RETURNSH=SH∪S∗∪Sk+1Figure 3
Example of Hybrid clustering based on Newman partition. (a) Newman clustering. (b) Hybrid clustering.
(a)(b)


### 3.2. The Different Levels of Cooperation

Before introducing the different approaches, the concept of Traffic Signal Control is introduced.Definition 3.
Traffic Signal ControlSM:UN⟶ℤ.
Given the networkUNN,E, the Traffic Signal Control applies the SM to UN fixing all the variables of the signals control in the network minimizing the global delay of the network UNN,E.(i)
Cj is the cycle for the controlled intersection link j(ii)
gj is the green time ratio for controlled intersection link j(iii)
θj is the offset for controlled intersection linkj(iv)
JDUNC1,…,CE,g1,…,gE,θ1,…,θE. is the global delay of the network when the parameters are fixed
TheCj is the same for all intersection links and it is fixed by binary search (C).(8)SMUN=C,gj∗,θj∗∀j∈E:minJD.
In practice, the Traffic Signal Control, based on theSM, fixes the control variables (C,g,θ) to minimize the total delay in a given network UN. How the SM optimizes the traffic signal setting is shown in the next section. Given the network UN and the clustering S, different levels of cooperation are considered and reported. In a decentralized system, there is a lack of cooperation every time the subsystems do not exchange information. In this case, one cluster gives information to other clusters about one or more of its decision variables.Definition 4.
CoopnetCP:UN,S⟶SCP.
The Coopnet is a function that, given the networkUNN,E and the clustering S=S1,…,SK, returns a subnetwork SCP composed by the subnetwork with the highest Priority in S and the nodes with highest Priority in UN, at least one for each subnetworks in S.(i)
S∗=Si:maxPSi,∀Si∈S(ii)
ni∗=j:maxPj,∀j∈Si(9)SCP=S∗∪j=1‖S‖nj∗.
This process utilizes the same criteria of Hybrid algorithm without limiting the dimension of the subnetwork.Definition 5.
COOP means thatSM optimized only SCP.
The level of cooperation is minimal, and the Surrogate Method is applied only onSCP. The optimization is applied only on the nodes of the subnetwork, minimizing (JDSCP), the total delay calculated on SCP. The clusters give information only related to the nodes with the highest Priority.(i)
ApplySMSCP,JDSCP(ii)
SM OptimizesC∗,gi∗,θi∗∀i∈SCP(iii)
Fix randomlyC,gi,θbi∀i∈N−SCP
COOP is the method that optimizes only the subnetworkSCP, taking into account the subnetwork SK+1 introduced by the Hybrid method and the nodes with highest Priority, one for each subnetwork of the clustering. The choice to take the most important node for each subnetwork guarantees the synchronization between subnetworks. Obviously, when the cooperation increases, the results improve.Definition 6.
COOP1 means thatSM at first optimized SCP, and then in a parallel way on the others subnetworks, considering fixed all the traffic parameters of the nodes in SCP. The clusters provide information related to the nodes with the highest Priority, and the SM fixes the control variables of these nodes (all nodes in SCP) and then SM optimizes all the others clusters but the control variables in SCP are kept constant.(i)
ApplySMSCP,JDSCP(ii)
SM OptimizesC∗,gi∗,θi∗∀i∈SCP(iii)
UpdateSi=Si−ni∗∀Si∈S(iv)
ApplySMS1,JDS1,…,SS,JDSSSM Optimizes C∗,gi∗,θi∗∀i∈S1,…,SSDefinition 7.
COOP2 means thatSM is at first applied on SSC and then in series on the other subnetworks. The SM is applied to other subnetworks in a descending order of Priority. The clusters provide information related to the nodes and those clusters with the highest Priority, and the SM fixes the control variables of nodes in SCP, minimizing JSCP, and then the SM optimizes the second cluster with the highest Priority (i.e., S∗) but the control variables in SCP are kept constant minimizing JS∗ and so on.(i)
ApplySMSCP,JDSSC(ii)
SM OptimizesC∗,gi∗,θi∗∀i∈SSC(iii)
UpdateSi=Si−ni∗∀Si∈S(iv)
UNTILS≠ DO(v)
{S∗=Si:maxPSi,∀Si∈S(vi)
SMS∗,JDS∗(vii)
S=S−S∗}(viii)
SM OptimizesC∗,gi∗,θi∗∀i∈S∗Definition 8.
COOP3 means that theSM is applied as in COOP2 but the objective function examined in the SM is calculated on the subnetwork considered together with all those nodes already optimized. The clusters give information related to the nodes and to the clusters with highest Priority, and the SM first fixes the control variables of nodes in SCP, minimizing JSCP; then the SM optimizes the second cluster with higher Priority (i.e. S∗) but the control variables in SCP are keep constant minimizing JSCP∪S∗ and so on.(i)
ApplySMSCP,JDSSC(ii)
SM OptimizeC∗,gi∗,θi∗∀i∈SSC(iii)
UpdateSi=Si−ni∗∀Si∈S(iv)
UNTILS≠ DO(v)
{S∗=Si:maxPSi,∀Si∈S(vi)
SMS∗,JDSCP∪S∗(vii)
S=S−S∗}(viii)
SM OptimizesC∗,gi∗,θi∗∀i∈S∗
A scheme of the Network Clustering method and the cooperation methods is reported in Figure4. The white boxes are the input, the grey boxes are the methods, and the green boxes are the outputs. Given the network UNN,E and the flow F, the Network clustering method calculates the clustering set S, the Priority Node for each node of the network, and the Priority Network for each subnetworks.
Considering the different levels of cooperation, the signal setting parameters for a subset nodes (just the node inSCP) is optimized, if the cooperation is limited and for all the nodes in UNN,E in the other cases. The different level of cooperation is based on different levels of knowledge of urban network. COOP optimizes the Priority subnetwork only. The other methods optimize the whole network applying the SM on clustering in series or parallel way. When the cooperation is limited, the optimization is obtained considering the delay separately for each subnetwork; instead through a ful cooperation, the delay is calculated considering the union of the subnetworks. Section 6 reports a numerical example of the different levels of cooperation.Figure 4
Procedure providing the clustering and the signal setting parameters of the urban network.


## 3.1. Hybrid Clustering

A classification for the nodes of the urban network is introduced to define a new clustering method. A Node Priority considering three different parameters is here introduced:Degree D(j) is the simplest measure of the node. The degree of the node is the number of incident edges. Given(3)Xi,j=1,eij∈E,0,Otherwise.The degree of the nodej is calculated as follows:(4)Dj=∑i∈NXi,j+Xj,i.BetweennessB(j): Betweenness is a measure of the importance of the node with respect to the network. It is based on the idea that a node is central if it lies between many other nodes, in the sense that it is traversed by many of the shortest paths connecting couples of nodes.Givendi,k is the number of shortest paths between i and k and di,kj is the number of shortest paths between i and k that contain node j. The betweenness of node j B(j) is(5)Bj=1n−1n−2∑i≠j≠k∈Ndi,kjdi,k.FlowF(j) is the amount of the flow directed into node. Obviously the flow incoming into the node must be equal to the one coming out. Given the Yei,j the flow in to link ei,jFj=∑∀i∈N:eij∈EYei,j.Definition 1 (Node PriorityPj).
The Node PriorityPj is a function assigning a weight to each node j that takes into consideration the importance of the node with respect to the network, based on its degree, betweenness, and flow. The values normalized are(6)Pj=DjD+Bj+FjF.D=∑i=1nDiF=∑i=1nFiDefinition 2 (Network PriorityPUN).
Given the networkUNN,E, the Network Priority is a function that assigns a weight to the network.(7)PUN=∑∀j∈NPj.
The node priority is calculated by the sum of three normalized elements, this implies that each element varies from 0 to 1. For a node, the normalized degree increases with the number of the incident edges on it, and the betweenness increases with the number of the shortest paths traversed it and the normalized flow increases with the flow directed into the node. It is evident that the first two terms can change only if the urban network changes. While considering these priorities it is possible to understand the importance of each node with respect to the network. The Node Priority is also used to determine the Priority of each subnetwork. The Priority of the sub-network is given by the sum of the Priority of each node in the subnetwork. Given the partition, for each node and for each subnetwork, the Priority is calculated.
Given the procedure to calculate the Priority, the proposed algorithm to clustering the network is introduced.
The Hybrid algorithm suggests a clustering of the network considering the Priority method. The Hybrid algorithm adds to the clustering one subnetworkSK+1 composed by the nodes with highest priority on the network. Probably, these nodes are the nodes with more traffic; in fact, highest priority means this node has big probability to be chosen by a driver, because it is traversed by many shortest paths and has many incident edges. The aim of the Hybrid algorithm is to compose a subnetwork representing the whole urban network. It is evident that these most important nodes for the network must be optimize and synchronize, minimizing the total delay of the network. When the green time and the offset of these nodes are optimized, it is possible to optimize the others nodes considering different levels of cooperation. Given a clustering S from well known cluster algorithms and K is the number of clusters, the Hybrid algorithm adds a cluster composed by a set of nodes (not more then K−1+N/K), while selecting the nodes with highest Priority, and at least one node for each cluster in S, deleting these selected nodes from their clusters. The dimension of this new cluster SK+1 is defined through a preprocessing analysis. If in S the cluster with the highest Priority contains few nodes, the Hybrid clustering will consist in K sub networks, otherwise in K+1. The new cluster is composed by the nodes with the highest Priority from each sub network in S. Algorithm 1 reports the steps of the Hybrid algorithm. In Step 1, the main sub network Sk+1 is formed by the sub network S∗ with the highest Network Priority; Step 2 adds to the main sub network Sk+1 the node with the highest Node Priority from the other subnetworks in S. Step 3 guarantees that the dimension of Sk+1 does not exceed K−1+N/K.Example 1.
In Figure3, it is reported on the left side the clustering given by Newman algorithm S=1,2,3,5,6,4,7,8,9 (in bold the nodes with the highest Priority) and on the right the Hybrid clustering SH=1,2,4,5,8,3,6,7,9. The red nodes are the nodes with the the highest Priority. Given the small dimension of the network, SK+1 is set to be equal to 5. The Hybrid cluster gives 4 subnetworks and the new cluster SK+1=1,2,4,5,8 is composed by 5 nodes with the highest Priority almost one for each of the three subnetowrks of Newman: {1,2,5} from the sub network with higher Priority, {4} from the second, and {8} from the third.
Given a clustering of the entire urban network, we proposed different decentralized approaches based on different levels of cooperation between the individuated subnetworks.Algorithm 1: Principal steps of Hybrid algorithm.
Step 0 Given:the networkUNN,E andS=S1,S2,…,SK S is a cluster of K sub-networks given by a clustering methodSk+1= is the new sub-networkSH is the Hybrid clustering set;i,m,j,a int;Pi,∀i∈NPSj,∀Sj∈SStep 1 CalculateS∗=argmaxPSj, ∀Sj∈SS=S−S∗Sk+1=S∗Step 2 WHILES≠ DOSK+1=SK+1+i=argmaxPi, i∈SFORm=1,≤k,m++IFi∈SmSm=Sm−iSH=SH∪SmS=S−SmStep 3 WHILESK+1≥K−1+N/K DOi=argminPi, ∀i∈SK+1S∗=S∗+iSk+1=Sk+1−iStep 4 RETURNSH=SH∪S∗∪Sk+1Figure 3
Example of Hybrid clustering based on Newman partition. (a) Newman clustering. (b) Hybrid clustering.
(a)(b)


## 3.2. The Different Levels of Cooperation

Before introducing the different approaches, the concept of Traffic Signal Control is introduced.Definition 3.
Traffic Signal ControlSM:UN⟶ℤ.
Given the networkUNN,E, the Traffic Signal Control applies the SM to UN fixing all the variables of the signals control in the network minimizing the global delay of the network UNN,E.(i)
Cj is the cycle for the controlled intersection link j(ii)
gj is the green time ratio for controlled intersection link j(iii)
θj is the offset for controlled intersection linkj(iv)
JDUNC1,…,CE,g1,…,gE,θ1,…,θE. is the global delay of the network when the parameters are fixed
TheCj is the same for all intersection links and it is fixed by binary search (C).(8)SMUN=C,gj∗,θj∗∀j∈E:minJD.
In practice, the Traffic Signal Control, based on theSM, fixes the control variables (C,g,θ) to minimize the total delay in a given network UN. How the SM optimizes the traffic signal setting is shown in the next section. Given the network UN and the clustering S, different levels of cooperation are considered and reported. In a decentralized system, there is a lack of cooperation every time the subsystems do not exchange information. In this case, one cluster gives information to other clusters about one or more of its decision variables.Definition 4.
CoopnetCP:UN,S⟶SCP.
The Coopnet is a function that, given the networkUNN,E and the clustering S=S1,…,SK, returns a subnetwork SCP composed by the subnetwork with the highest Priority in S and the nodes with highest Priority in UN, at least one for each subnetworks in S.(i)
S∗=Si:maxPSi,∀Si∈S(ii)
ni∗=j:maxPj,∀j∈Si(9)SCP=S∗∪j=1‖S‖nj∗.
This process utilizes the same criteria of Hybrid algorithm without limiting the dimension of the subnetwork.Definition 5.
COOP means thatSM optimized only SCP.
The level of cooperation is minimal, and the Surrogate Method is applied only onSCP. The optimization is applied only on the nodes of the subnetwork, minimizing (JDSCP), the total delay calculated on SCP. The clusters give information only related to the nodes with the highest Priority.(i)
ApplySMSCP,JDSCP(ii)
SM OptimizesC∗,gi∗,θi∗∀i∈SCP(iii)
Fix randomlyC,gi,θbi∀i∈N−SCP
COOP is the method that optimizes only the subnetworkSCP, taking into account the subnetwork SK+1 introduced by the Hybrid method and the nodes with highest Priority, one for each subnetwork of the clustering. The choice to take the most important node for each subnetwork guarantees the synchronization between subnetworks. Obviously, when the cooperation increases, the results improve.Definition 6.
COOP1 means thatSM at first optimized SCP, and then in a parallel way on the others subnetworks, considering fixed all the traffic parameters of the nodes in SCP. The clusters provide information related to the nodes with the highest Priority, and the SM fixes the control variables of these nodes (all nodes in SCP) and then SM optimizes all the others clusters but the control variables in SCP are kept constant.(i)
ApplySMSCP,JDSCP(ii)
SM OptimizesC∗,gi∗,θi∗∀i∈SCP(iii)
UpdateSi=Si−ni∗∀Si∈S(iv)
ApplySMS1,JDS1,…,SS,JDSSSM Optimizes C∗,gi∗,θi∗∀i∈S1,…,SSDefinition 7.
COOP2 means thatSM is at first applied on SSC and then in series on the other subnetworks. The SM is applied to other subnetworks in a descending order of Priority. The clusters provide information related to the nodes and those clusters with the highest Priority, and the SM fixes the control variables of nodes in SCP, minimizing JSCP, and then the SM optimizes the second cluster with the highest Priority (i.e., S∗) but the control variables in SCP are kept constant minimizing JS∗ and so on.(i)
ApplySMSCP,JDSSC(ii)
SM OptimizesC∗,gi∗,θi∗∀i∈SSC(iii)
UpdateSi=Si−ni∗∀Si∈S(iv)
UNTILS≠ DO(v)
{S∗=Si:maxPSi,∀Si∈S(vi)
SMS∗,JDS∗(vii)
S=S−S∗}(viii)
SM OptimizesC∗,gi∗,θi∗∀i∈S∗Definition 8.
COOP3 means that theSM is applied as in COOP2 but the objective function examined in the SM is calculated on the subnetwork considered together with all those nodes already optimized. The clusters give information related to the nodes and to the clusters with highest Priority, and the SM first fixes the control variables of nodes in SCP, minimizing JSCP; then the SM optimizes the second cluster with higher Priority (i.e. S∗) but the control variables in SCP are keep constant minimizing JSCP∪S∗ and so on.(i)
ApplySMSCP,JDSSC(ii)
SM OptimizeC∗,gi∗,θi∗∀i∈SSC(iii)
UpdateSi=Si−ni∗∀Si∈S(iv)
UNTILS≠ DO(v)
{S∗=Si:maxPSi,∀Si∈S(vi)
SMS∗,JDSCP∪S∗(vii)
S=S−S∗}(viii)
SM OptimizesC∗,gi∗,θi∗∀i∈S∗
A scheme of the Network Clustering method and the cooperation methods is reported in Figure4. The white boxes are the input, the grey boxes are the methods, and the green boxes are the outputs. Given the network UNN,E and the flow F, the Network clustering method calculates the clustering set S, the Priority Node for each node of the network, and the Priority Network for each subnetworks.
Considering the different levels of cooperation, the signal setting parameters for a subset nodes (just the node inSCP) is optimized, if the cooperation is limited and for all the nodes in UNN,E in the other cases. The different level of cooperation is based on different levels of knowledge of urban network. COOP optimizes the Priority subnetwork only. The other methods optimize the whole network applying the SM on clustering in series or parallel way. When the cooperation is limited, the optimization is obtained considering the delay separately for each subnetwork; instead through a ful cooperation, the delay is calculated considering the union of the subnetworks. Section 6 reports a numerical example of the different levels of cooperation.Figure 4
Procedure providing the clustering and the signal setting parameters of the urban network.


## 4. Traffic Control: The Surrogate Method (SM)

The Surrogate Method (SM) solves the optimization problem by using the gradient method. This procedure presents an iterative structure that, in each cycle, transforms the original problem with discrete decision variables, into an optimization problem with continuous decision variables. The latter problem is denoted as Surrogate. Subsequently, the gradient estimate, which allows to update the solution, is realized in the discrete field.The steps sequence of the algorithm is reported in Algorithm2.Algorithm 2: Steps of the surrogate method SM.
0 Initializeρ0=z0 and perturb ρ0 to have all components non-integer.For any iterationk=0,1,… repeat the following steps1 Determine the selection setSρk using these steps:InitializeI = 1,…,2Mv = ρ − ⌊ρ⌋Repeat the following steps UntilI≠∅i=argminj∈Ivjyi=vi∗Wi=∑j∈Iej∗v=v−yiWi∗I=I/i∗Sρk = Wi−⌊ρ⌋,i=0,…,2M2 Select atransformation functionfk such that(i)zk=fkρk=argminz∈Sρkz−ρk.3 Evaluate the gradient estimation(i)∇JDρk=∇1JDρk,…,∇NJDρkT,(ii) using the following relationship(iii)∇jJDρk=JDzj−JDzk, where k satisfies(iv)zj−zk=ej (versor with j-th component equal to 1).4 Update state:ρk+1=πk+1ρk−ηk∇JDρk.5 If some stopping condition is not satisfied, repeat steps fork+1. Else set ρ∗.VectorZ is an 2M-dimensional decision vector, subject to the capacity constraints Ad and JDZ is the delay incurred when the state is Z. The cycle is fixed a priori by the binary search, whereas the green time ratio and the offset are optimized for each controlled link. The integer capacity constraint is relaxed and a resulting surrogate problem is obtained.The basic idea of this method is to solve a continuous optimization problem by stochastic approximation methods and establish the fact that when (and if) a solution of the relaxed problemρ∗ is obtained it can be mapped into a discrete point z=fρ∗∈Ad which is in fact the solution to the problem.Note, however, that the sequenceρk, k=1,2,… generated by an iterative scheme to solve the relaxed problem consists of real-valued solutions which are unfeasible, since the actual system involves only discrete resources. Thus, a key feature of the Surrogate algorithm is that at every step k of the iteration scheme, the discrete state is updated through zk=fkρk as ρk is updated.This has two advantages:(i)
The cost of the original system is continuously adjusted (in contrast to an adjustment that would only be possible at the end of the Surrogate optimization process)(ii)
It allows us to make use of information typically employed to obtain cost sensitivities from theactual operating system at every step of the processNote that there is an additional operation: thezk corresponds to feasible states based on which one can evaluate estimates ∇Jcρk, calculated on actual system zk (not the surrogate state ρk, see Step 3). We can therefore see that this scheme is intended to combine the advantages of stochastic approximation type of algorithm with the ability to obtain sensitivity estimates with respect to discrete decision variables.For each updating step of the Surrogate state (Step 4), it is computed (2M+1) times the objective function value by the simulation module. Hence, it becomes crucial to develop an efficient simulation module which performs an acceptable computation time. Some simplifications to reduce the calculation time of SM are introduced: the dynamic gradient step, the database of solution and green splits constraints.


### 4.1. Estimation of the Dynamic Gradient Step

A different green time ratio vector is able to provide the same value ofJD; hence, the gradient ∇JD will be equal to 0 and there is no update of the state (see Step 3 of Algorithm 2), forcing the convergence of the algorithm in a nonoptimal solution. For this reason, a perturbation of the gradient is introduced. The next step is to modify the component of the gradient equal to 0 through the counter z as follows (Algorithm 3):Algorithm 3: Dynamic gradient step estimation.
(1)
ifJgk≤ min Jgk−1 then(2)
p=1(3)
else(4)
p=p+1(5)
end if(6)
fori=1: n do(7)
if∇iJ<−ɛ and ∇iJ>ɛ then(8)
z=z+1(9)
∇iJ=rand∈−z,z(10)
ηi=0.5(11)
else(12)
ηi=0.5/p(13)
end if(14)
end for


### 4.2. Database of the Solutions

For every gradient estimation, the SM requires2M+1 values (see Step 3 of Algorithm 2). To improve the efficiency of the algorithm, each solution with relative delay function is memorized. If the value of green ratio is already calculated, the SM algorithm saves the traffic simulation.


### 4.3. Green Splits Constraints

The green splits constraints imply a simplification of the decision vector.(10)∑∀j:ej,i∈Egi=C.For every intersection, there is one independent variable only; as a matter of fact, the sum of green for every links of an intersection is equal to the cycle time. One decision variable for each intersection is taken into consideration (i.e., if the cycle is 100, and the intersection is composed by three intersection links, given the green times vector30,35,35 only the first component will be the decision variable). It is evident that if the decision green time variable changes (i.e., 30 + 1 = 31), also the neighbouring feasible states will change based on the time cycle (i.e., [31, 34, 35], [31, 34, 35]). The decision vector is chosen among the neighbourhood feasible states considering the green times vector that minimizes the objective function JD. This simplification reduces the dimension of the decision green time variables, and there is a green time variables for each intersection rather than each intersection link.Section 5.2 reports an analysis of these simplifications SM.


## 4.1. Estimation of the Dynamic Gradient Step

A different green time ratio vector is able to provide the same value ofJD; hence, the gradient ∇JD will be equal to 0 and there is no update of the state (see Step 3 of Algorithm 2), forcing the convergence of the algorithm in a nonoptimal solution. For this reason, a perturbation of the gradient is introduced. The next step is to modify the component of the gradient equal to 0 through the counter z as follows (Algorithm 3):Algorithm 3: Dynamic gradient step estimation.
(1)
ifJgk≤ min Jgk−1 then(2)
p=1(3)
else(4)
p=p+1(5)
end if(6)
fori=1: n do(7)
if∇iJ<−ɛ and ∇iJ>ɛ then(8)
z=z+1(9)
∇iJ=rand∈−z,z(10)
ηi=0.5(11)
else(12)
ηi=0.5/p(13)
end if(14)
end for


## 4.2. Database of the Solutions

For every gradient estimation, the SM requires2M+1 values (see Step 3 of Algorithm 2). To improve the efficiency of the algorithm, each solution with relative delay function is memorized. If the value of green ratio is already calculated, the SM algorithm saves the traffic simulation.


## 4.3. Green Splits Constraints

The green splits constraints imply a simplification of the decision vector.(10)∑∀j:ej,i∈Egi=C.For every intersection, there is one independent variable only; as a matter of fact, the sum of green for every links of an intersection is equal to the cycle time. One decision variable for each intersection is taken into consideration (i.e., if the cycle is 100, and the intersection is composed by three intersection links, given the green times vector30,35,35 only the first component will be the decision variable). It is evident that if the decision green time variable changes (i.e., 30 + 1 = 31), also the neighbouring feasible states will change based on the time cycle (i.e., [31, 34, 35], [31, 34, 35]). The decision vector is chosen among the neighbourhood feasible states considering the green times vector that minimizes the objective function JD. This simplification reduces the dimension of the decision green time variables, and there is a green time variables for each intersection rather than each intersection link.Section 5.2 reports an analysis of these simplifications SM.


## 5. Numerical Results

The results of the optimization approach applied on the entire network (centralized control) are compared to the results obtained while considering different network partitions and different levels of cooperation. The goal is to analyze whether the optimization must be applied on the entire network or obtain satisfying results just applying the Surrogate Method on subnetworks.The aim of this paper is to evaluate if the decentralized control can be used to solve the synchronization signal problem. For this reason the evaluation of the trade-off between efficiency (goodness of the solution) and efficacy (computational time) is fundamental. Each method is compared in terms of efficacy (ΔJD means that the variation on the total delay with respect to the centralized solution) and efficiency (ΔCT implies a variation in the calculation time with respect to the centralized solution), a positive percentage determines a worsening while a negative one an improvement if compared to the centralized solution.(i)
ΔJD=JDDecentralized−JDCentralized/JDCentralized∗100(ii)
ΔCT=Calculation TimeDecentralized−Calculation TimeCentralized/Calculation TimeCentralized∗100The Hybrid Algorithm is applied to Newman and K-means clustering methods. The Newman clustering is based on betweenness, considering in part our Priority Method. K-means takes in consideration the neighborhood concept, often used in the literature when a set of nodes are detected to be optimize. The results put in evidence that the best results are given by the Hybrid Method considering the Newman clustering, which provides the same solution of the centralized method. This highlights the efficiency and efficacy of our Priority Method that finds a subset of nodes that represent the whole network.


### 5.1. Small Case Study

In this section, to better explain the Network Clustering Method, it is carried out a small case study, and some results are presented. The small network is the same presented in [35] and for simplicity the considered parameters are here reported. The network is composed by 9 four way signal-controlled intersections and 12 centroids for the input/output flow on the network. The links (300 meters in length) have a capacity of 900 (veic/hour) and two lanes. The capacity and demand of the links are split over the two lanes fifty-fifty, except for the principal paths where the demands are represented in Figure 5.Figure 5
Small case study. The centroids are red, signalized intersections are red, and links are green.TheCTMUT models the behavior of urban drivers. It is considered an additional movement belonging to the right-turn so that the demand lane is split in right-turn (100%−ω turn demand) and through (ω turn demand) movements. This through demand is applied to all lanes for the right-turns of network and it is part of phase 1 for east-west/west-east directions and phase 2 for south-north/north-south directions. These percentages represent drivers that must move forward but, due to a mistake, take the channelized lane for right-turn. It is examined the ω varying from 2% to 6%. It is necessary to model flows crossing the channelized lanes, flow upstream intersection, and the complex flow intersection with detail level quite close to the microscopic models. The inflow demands is 500 (veic/h) from the nodes 11,13,15,18 during a simulation time of 400 sec.An inflow demand of 800 (veic/h) to exam different levels of congestion is also performed. The delay is calculated in seconds. All experiments are performed on a desktop computer with an Intel i5-3470 processor (3.2 GHz) with 8 GB of DDR3 RAM running 64-bit Windows 7. Even if each iteration takes 100 msec to complete, plus the communication overhead to calculate the objective function byCTMUT requiring approximately 10 sec, the SM (centralized version) would require about 35 minutes to provide the result.


### 5.2. Surrogate Model with Simplifications

It is here first reported a comparison for the extensions on theSM. What follows is the nomenclature:(i)
SM is the traditional version(ii)
DSSM considered the Database of solutions(iii)
DGSM used the Dynamic Gradient step estimation(iv)
DSDGSM used both the extensionsThe extensions of Surrogate Method are compared in terms of efficiency (number of times that theJD must be calculated NJD) Table 1. ΔNJD represents the savings percentage on the calculation time.Table 1
Efficiency of extensions.
JDNJDΔNJDSM7906291DSSM7906106−64%DGSM7743271−7%DSDGSM7743208−29%Despite the simplifications on theMS able to decrease the calculation time, the new dynamic gradient step estimation determines an improvement in the solution of 2% with respect to the traditional SM. The results obtained with the suggested SM extensions showed that when the DS is applied, a strong reduction in the efficiency occurs (64%).


### 5.3. Clustering Algorithms

An application of the clustering method is given in Figure6 on the left the clustering obtained by K-means partition (K = 4) and on the right the main subnetwork (i.e., the subnetwork with the highest Priority) and the most important nodes for each subnetwork are highlighted in red. The clustering given by the 4-means algorithm is (1,2),(7,8,9),(4),(3,5,6), in bold the main subnetwork and the nodes with the highest Priority in each subnetwork).Figure 6
Clustering individuated by 4-means partition. (a) 4-means clustering. (b) Priority process.
(a)(b)Example 2 (Hybrid-ALGORITHM).
Given the small dimension of the test network the dimension of the sub network introduced by Hybrid method is fixed to 5. The Hybrid clustering adds a cluster formed by the cluster with high Priority (1,2) together with the node with high Priority. One is for the others clusters, obtaining the clustering:1,2,4,6,8,7,9,3,5.Example 3 (COOPERATION).
InCOOP, the SM is applied on the main subnetwork together with the nodes with higher Priority one for each subnetwork of the clustering (i.e., SCP=1,2,4,6,8). In COOP1, the SM is applied at first on SCP optimizing all the control variables of the nodes (1,2,4,6,8) that are kept constant for the other subnetworks. Then the SM is applied in a parallel way on (7,8,9) considering the value of signal setting parameters for intersection 8, on (4) considering set 4, and on (3,5,6) considering set 6. In practice, the signal setting for the nodes with the highest Priority for each subnetworks are fixed by the main subnetwork. In COOP2, the approach is the same but the SM is applied in series on the subnetworks in a decreasing Priority order. In COOP3 we need more information. The SM is applied on SCP (1,2,4,6,8), then on (7,8,9) considering the value of signal setting parameters for intersection 8 set, though the total delay is calculated on the subnetwork (1,2,4,6,8,7,9), and so on.
Table2 takes into consideration the Newman partition and in Tables 3, and 4 the K-means partition for K=4 and K=3 are reported. The results of Hybrid approach based on 4-means clustering are also reported. In the tables, CT is the computation time and it is given in minutes. The results of Hybrid approach based on Newman clustering are optimal but not significant since the clustering is composed by four subnetworks, two of them composed by only one node and the main network is representative of the whole network (see Figure 3). It can be noticed that if the cooperation increases the solution improves, though the control requires a higher time interval.
These preliminary results stress that it is possible to find a good compromise between subnetwork and efficiency. The comparison is performed between the centralized approach (TotNet) and decentralized approaches with different levels of cooperation (main net without cooperation and COOP/1/2/3 with increasing levels of cooperation). The objective function gets worse from 0.03% to 8.2%, against an improved calculation from 34% to 98%. It is evident that the cooperation provides optimal solutions which approximate the centralized control, though with a significant reduction in the calculation time. In Figure 7, a comparison between Newman clustering and the Hybrid clustering based on 4-means is reported. It highlights the fast convergence of Hybrid method that provides solutions approaching the optimal level also with limited cooperation (COOP). It is possible to understand that a clustering based on Priority is able to best represent the whole network.Table 2
Decentralized vs centralized with Newman decomposition.
SubnetworksJDΔJDΔCTCTNewman[1,2,3,5,6],[4,7],[8,9]Tot net[1,2,3,4,5,6,7,8,9]599735Main net[1,2,3,5,6]63305.6%−84%5.6COOP[1,2,3,4,5,6,8]63185.3%−34%23COOP1[1,2,3,4,5,6,8],[4,7],[8,9]62143.6%−84%5,6COOP2[1,2,3,4,5,6,8],[4,7],[8,9]61953.3%−82%6COOP3[1,2,3,4,5,6,8],[4,7],[8,9]59990.03%−68%11Table 3
Decentralized vs centralized with 4-means inflow decomposition.
Sub-networksJDΔJDΔCTCT4-means[1,2],[3,5,6],[7,8,9],[4]Tot net[1,2,3,4,5,6,7,8,9]599735Main net[1,2]64897.6%−98%0.7COOP[1,2,4,6,8]64116.4%−82%6COOP1[1,2,4,6,8],[5,6,9],[7,8,9],[4]64116.4%−82%6COOP2[1,2,4,6,8],[5,6,9],[7,8,9],[4]63826.0%−79%7COOP3[1,2,4,6,8],[5,6,9],[7,8,9],[4]60170.3%−70%10.5Table 4
Decentralized vs centralized with 3-means adjacent decomposition.
SubnetworksJDΔJDΔCTCT3-means[5,7,8,9],[2,3,6],[4,1]Tot net[1,2,3,4,5,6,7,8,9]599735Main net[5,7,8,9]64116,9%−82%6COOP[2,4,5,7,8,9]61752.9%−52%17COOP1[[2,4,5,7,8,9],[2,3,6],[4,1]61732.9%−52%17COOP2[[2,4,5,7,8,9],[2,3,6],[4,1]61021.6%−47%19COOP3[[2,4,5,7,8,9],[2,3,6],[4,1]60931.7%−48%18Figure 7
Comparison between Newman clustering and Hybrid clustering (the delay is given in seconds).


### 5.4. Big Networks

The real case study has been conducted on a large-size network located in Rome, the area of Eur. Figure8 reports the network; it presents 56 signalized intersections and 39 intersections under control, 194 links and 26 centroids. The large network simulates the supply and demand of the real network, the in flow demand is about 1000 [veic/h] from the input centroids of principal paths during a simulation time of 600 sec. All experiments are performed on a desktop computer with an Intel i5-3470 processor(3.2 GHz) with 8 GB of DDR3 RAM running 64-bit Windows 7. Even if each iteration takes 100 msec to complete, plus the communication overhead to calculate the objective unction by CTMUT requiring approximately 80sec, the SM (centralized version) would require 3,7 hours (i.e., 222 minutes) approximately to provide the result.Figure 8
Real case study.
(a)(b)The Newman algorithm gives 4 clusters, and this is why K is set to 4 and 5. In Figure9 reports the relation of the most promising algorithms. The Hybrid (Newman) is the Hybrid Method applied on the Newman Clustering, instead Hybrid (K-means) is the Hybrid Method applied on the K-means clustering. The Hybrid Method improves the solution both in efficiency and efficacy. The best performance is provided by the curve on top of the right side of the figure. As a matter of fact the solution with small ΔJD introduces the higher efficacy and with big ΔCT higher efficiency.Figure 9
Trade-off efficiency-efficacy.It is important to notice that the decomposition approaches provide optimal results, and the worsening of the objective function can reach a maximum of10% against a reduction of the computation time of 93%; see Figure 9.The best results are given by the Hybrid Method considering the Newman clustering, which provides the same solution of the centralized method. The results of Hybrid decomposition based on Newman clustering are explicitly reported in Table5. CT means the computation time and it is given in minutes. As a matter of fact, it presents discrepancies between the centralized and decentralized controllers of 0.09% and an improvement of 75% in the calculation time. The results of the Hybrid Method considering the Newman clustering are explicitly reported in Table 6. These results confirm that the clustering based on the topology of the network and flow information provides better performances. It is evident that for the signal setting problem, the decomposition method gives optimal results. Bring the Surrogate Method to be an excellent tool for the optimization of signal setting problem for urban networks bypassing the critical aspect of the calculation time.Table 5
Decentralized vs centralized with Hybrid decomposition based on Newman clustering.
Sub-networksJDΔJDΔCTCTHybrid[4 7 9 14 16 18 35 41 45 48],[1 2 3 5 6 8], [31 32 33 38 39 40 46 47],[20 21 36 37 42 43 44],[22 23 24 25 26 27 28 29 30]Tot net15146222COOP[4 6 7 9 14 16 18 19 20 28 31 35 41 45 48]151770.21%−85%33COOP1152750.9%−77%51COOP2151590.09%−75%55COOP3151590.09%−62%106Table 6
Decentralized vs centralized with Hybrid decomposition based on 4-means.
Sub-networksJDΔJDΔCTCTHybrid[1,2,4,5,8],[6,3],[7,9]Tot net[1,2,3,4,5,6,7,8,9]599735Main net[1,2,4,5,8]64156.5%−92%3COOP[1,2,4,5,6,7,8]60811.3%−49%17COOP1[1,2,4,5,6,7,8],[6,3],[7,9]60510.8%−48%18COOP2[1,2,4,5,6,7,8],[6,3],[7,9]60510.8%−48%18COOP3[1,2,4,5,6,7,8],[6,3],[7,9]59990.03%−45%19


## 5.1. Small Case Study

In this section, to better explain the Network Clustering Method, it is carried out a small case study, and some results are presented. The small network is the same presented in [35] and for simplicity the considered parameters are here reported. The network is composed by 9 four way signal-controlled intersections and 12 centroids for the input/output flow on the network. The links (300 meters in length) have a capacity of 900 (veic/hour) and two lanes. The capacity and demand of the links are split over the two lanes fifty-fifty, except for the principal paths where the demands are represented in Figure 5.Figure 5
Small case study. The centroids are red, signalized intersections are red, and links are green.TheCTMUT models the behavior of urban drivers. It is considered an additional movement belonging to the right-turn so that the demand lane is split in right-turn (100%−ω turn demand) and through (ω turn demand) movements. This through demand is applied to all lanes for the right-turns of network and it is part of phase 1 for east-west/west-east directions and phase 2 for south-north/north-south directions. These percentages represent drivers that must move forward but, due to a mistake, take the channelized lane for right-turn. It is examined the ω varying from 2% to 6%. It is necessary to model flows crossing the channelized lanes, flow upstream intersection, and the complex flow intersection with detail level quite close to the microscopic models. The inflow demands is 500 (veic/h) from the nodes 11,13,15,18 during a simulation time of 400 sec.An inflow demand of 800 (veic/h) to exam different levels of congestion is also performed. The delay is calculated in seconds. All experiments are performed on a desktop computer with an Intel i5-3470 processor (3.2 GHz) with 8 GB of DDR3 RAM running 64-bit Windows 7. Even if each iteration takes 100 msec to complete, plus the communication overhead to calculate the objective function byCTMUT requiring approximately 10 sec, the SM (centralized version) would require about 35 minutes to provide the result.


## 5.2. Surrogate Model with Simplifications

It is here first reported a comparison for the extensions on theSM. What follows is the nomenclature:(i)
SM is the traditional version(ii)
DSSM considered the Database of solutions(iii)
DGSM used the Dynamic Gradient step estimation(iv)
DSDGSM used both the extensionsThe extensions of Surrogate Method are compared in terms of efficiency (number of times that theJD must be calculated NJD) Table 1. ΔNJD represents the savings percentage on the calculation time.Table 1
Efficiency of extensions.
JDNJDΔNJDSM7906291DSSM7906106−64%DGSM7743271−7%DSDGSM7743208−29%Despite the simplifications on theMS able to decrease the calculation time, the new dynamic gradient step estimation determines an improvement in the solution of 2% with respect to the traditional SM. The results obtained with the suggested SM extensions showed that when the DS is applied, a strong reduction in the efficiency occurs (64%).


## 5.3. Clustering Algorithms

An application of the clustering method is given in Figure6 on the left the clustering obtained by K-means partition (K = 4) and on the right the main subnetwork (i.e., the subnetwork with the highest Priority) and the most important nodes for each subnetwork are highlighted in red. The clustering given by the 4-means algorithm is (1,2),(7,8,9),(4),(3,5,6), in bold the main subnetwork and the nodes with the highest Priority in each subnetwork).Figure 6
Clustering individuated by 4-means partition. (a) 4-means clustering. (b) Priority process.
(a)(b)Example 2 (Hybrid-ALGORITHM).
Given the small dimension of the test network the dimension of the sub network introduced by Hybrid method is fixed to 5. The Hybrid clustering adds a cluster formed by the cluster with high Priority (1,2) together with the node with high Priority. One is for the others clusters, obtaining the clustering:1,2,4,6,8,7,9,3,5.Example 3 (COOPERATION).
InCOOP, the SM is applied on the main subnetwork together with the nodes with higher Priority one for each subnetwork of the clustering (i.e., SCP=1,2,4,6,8). In COOP1, the SM is applied at first on SCP optimizing all the control variables of the nodes (1,2,4,6,8) that are kept constant for the other subnetworks. Then the SM is applied in a parallel way on (7,8,9) considering the value of signal setting parameters for intersection 8, on (4) considering set 4, and on (3,5,6) considering set 6. In practice, the signal setting for the nodes with the highest Priority for each subnetworks are fixed by the main subnetwork. In COOP2, the approach is the same but the SM is applied in series on the subnetworks in a decreasing Priority order. In COOP3 we need more information. The SM is applied on SCP (1,2,4,6,8), then on (7,8,9) considering the value of signal setting parameters for intersection 8 set, though the total delay is calculated on the subnetwork (1,2,4,6,8,7,9), and so on.
Table2 takes into consideration the Newman partition and in Tables 3, and 4 the K-means partition for K=4 and K=3 are reported. The results of Hybrid approach based on 4-means clustering are also reported. In the tables, CT is the computation time and it is given in minutes. The results of Hybrid approach based on Newman clustering are optimal but not significant since the clustering is composed by four subnetworks, two of them composed by only one node and the main network is representative of the whole network (see Figure 3). It can be noticed that if the cooperation increases the solution improves, though the control requires a higher time interval.
These preliminary results stress that it is possible to find a good compromise between subnetwork and efficiency. The comparison is performed between the centralized approach (TotNet) and decentralized approaches with different levels of cooperation (main net without cooperation and COOP/1/2/3 with increasing levels of cooperation). The objective function gets worse from 0.03% to 8.2%, against an improved calculation from 34% to 98%. It is evident that the cooperation provides optimal solutions which approximate the centralized control, though with a significant reduction in the calculation time. In Figure 7, a comparison between Newman clustering and the Hybrid clustering based on 4-means is reported. It highlights the fast convergence of Hybrid method that provides solutions approaching the optimal level also with limited cooperation (COOP). It is possible to understand that a clustering based on Priority is able to best represent the whole network.Table 2
Decentralized vs centralized with Newman decomposition.
SubnetworksJDΔJDΔCTCTNewman[1,2,3,5,6],[4,7],[8,9]Tot net[1,2,3,4,5,6,7,8,9]599735Main net[1,2,3,5,6]63305.6%−84%5.6COOP[1,2,3,4,5,6,8]63185.3%−34%23COOP1[1,2,3,4,5,6,8],[4,7],[8,9]62143.6%−84%5,6COOP2[1,2,3,4,5,6,8],[4,7],[8,9]61953.3%−82%6COOP3[1,2,3,4,5,6,8],[4,7],[8,9]59990.03%−68%11Table 3
Decentralized vs centralized with 4-means inflow decomposition.
Sub-networksJDΔJDΔCTCT4-means[1,2],[3,5,6],[7,8,9],[4]Tot net[1,2,3,4,5,6,7,8,9]599735Main net[1,2]64897.6%−98%0.7COOP[1,2,4,6,8]64116.4%−82%6COOP1[1,2,4,6,8],[5,6,9],[7,8,9],[4]64116.4%−82%6COOP2[1,2,4,6,8],[5,6,9],[7,8,9],[4]63826.0%−79%7COOP3[1,2,4,6,8],[5,6,9],[7,8,9],[4]60170.3%−70%10.5Table 4
Decentralized vs centralized with 3-means adjacent decomposition.
SubnetworksJDΔJDΔCTCT3-means[5,7,8,9],[2,3,6],[4,1]Tot net[1,2,3,4,5,6,7,8,9]599735Main net[5,7,8,9]64116,9%−82%6COOP[2,4,5,7,8,9]61752.9%−52%17COOP1[[2,4,5,7,8,9],[2,3,6],[4,1]61732.9%−52%17COOP2[[2,4,5,7,8,9],[2,3,6],[4,1]61021.6%−47%19COOP3[[2,4,5,7,8,9],[2,3,6],[4,1]60931.7%−48%18Figure 7
Comparison between Newman clustering and Hybrid clustering (the delay is given in seconds).


## 5.4. Big Networks

The real case study has been conducted on a large-size network located in Rome, the area of Eur. Figure8 reports the network; it presents 56 signalized intersections and 39 intersections under control, 194 links and 26 centroids. The large network simulates the supply and demand of the real network, the in flow demand is about 1000 [veic/h] from the input centroids of principal paths during a simulation time of 600 sec. All experiments are performed on a desktop computer with an Intel i5-3470 processor(3.2 GHz) with 8 GB of DDR3 RAM running 64-bit Windows 7. Even if each iteration takes 100 msec to complete, plus the communication overhead to calculate the objective unction by CTMUT requiring approximately 80sec, the SM (centralized version) would require 3,7 hours (i.e., 222 minutes) approximately to provide the result.Figure 8
Real case study.
(a)(b)The Newman algorithm gives 4 clusters, and this is why K is set to 4 and 5. In Figure9 reports the relation of the most promising algorithms. The Hybrid (Newman) is the Hybrid Method applied on the Newman Clustering, instead Hybrid (K-means) is the Hybrid Method applied on the K-means clustering. The Hybrid Method improves the solution both in efficiency and efficacy. The best performance is provided by the curve on top of the right side of the figure. As a matter of fact the solution with small ΔJD introduces the higher efficacy and with big ΔCT higher efficiency.Figure 9
Trade-off efficiency-efficacy.It is important to notice that the decomposition approaches provide optimal results, and the worsening of the objective function can reach a maximum of10% against a reduction of the computation time of 93%; see Figure 9.The best results are given by the Hybrid Method considering the Newman clustering, which provides the same solution of the centralized method. The results of Hybrid decomposition based on Newman clustering are explicitly reported in Table5. CT means the computation time and it is given in minutes. As a matter of fact, it presents discrepancies between the centralized and decentralized controllers of 0.09% and an improvement of 75% in the calculation time. The results of the Hybrid Method considering the Newman clustering are explicitly reported in Table 6. These results confirm that the clustering based on the topology of the network and flow information provides better performances. It is evident that for the signal setting problem, the decomposition method gives optimal results. Bring the Surrogate Method to be an excellent tool for the optimization of signal setting problem for urban networks bypassing the critical aspect of the calculation time.Table 5
Decentralized vs centralized with Hybrid decomposition based on Newman clustering.
Sub-networksJDΔJDΔCTCTHybrid[4 7 9 14 16 18 35 41 45 48],[1 2 3 5 6 8], [31 32 33 38 39 40 46 47],[20 21 36 37 42 43 44],[22 23 24 25 26 27 28 29 30]Tot net15146222COOP[4 6 7 9 14 16 18 19 20 28 31 35 41 45 48]151770.21%−85%33COOP1152750.9%−77%51COOP2151590.09%−75%55COOP3151590.09%−62%106Table 6
Decentralized vs centralized with Hybrid decomposition based on 4-means.
Sub-networksJDΔJDΔCTCTHybrid[1,2,4,5,8],[6,3],[7,9]Tot net[1,2,3,4,5,6,7,8,9]599735Main net[1,2,4,5,8]64156.5%−92%3COOP[1,2,4,5,6,7,8]60811.3%−49%17COOP1[1,2,4,5,6,7,8],[6,3],[7,9]60510.8%−48%18COOP2[1,2,4,5,6,7,8],[6,3],[7,9]60510.8%−48%18COOP3[1,2,4,5,6,7,8],[6,3],[7,9]59990.03%−45%19


## 6. Conclusions

The signal setting problem is a nonconvex problem; usually to find an optimal solution for simple networks may take long time, when it is possible. It is here suggested a decentralized control, considering different clustering approaches for the network, together with a procedure to classify the nodes. The Surrogate Method is applied to solve the Traffic Signal Synchronization problem, for each identified subnetwork. This decomposition provides comforting results for other indexes concerning the composition is currently under study. The reduced computation time is not sufficient to run online; however, it is possible to run the decentralized approach more times in a day during principal time slices, while obtaining optimal results. An improvement of calculation time can give the possibility to apply theSM real time, although it is necessary to reduce the communication time for evaluating the total delay on the network. We are studying the possibility to dynamically change the network clustering based on traffic conditions and/or to fix a desired number of traffic lights for each subnetwork.



---

*Source: 8873962-2020-11-09.xml*