# Urban Congestion Avoidance Methodology Based on Vehicular Traffic Thresholding
## 3 Vehicular Traffic Congestion Avoidance Methodology
In addition, for vehicle position estimation in a scalable manner, we use the KEP Tree data structure that we proposed in [8];
* S3--The computed routes in S3 were used to run vehicles on the selected road network topology in a vehicular traffic simulation environment. The vehicular traffic simulation environment was adapted to log vehicular traffic data that is parsed in the next step;
* S4--The generated vehicular traffic logs generated in S3 are parsed to provide data for evaluating the proposed solution in terms of congestion reduction and avoidance. The route computation algorithm presented in Algorithm 1 takes the start and destination points inputs and finds the context-specific best route, adapting [PERSON]'s algorithm by integrating the KEP tree and the proposed traffic thresholding mechanism. Beginning with  
Figure 1: Flowchart of the main concepts employed in the methodology. the starting point, it uses a priority queue to extend the route search graph by considering the unvisited neighbours of the first element from the queue. It selects the best match for the next road segment, which may be part of the route. The best match represents the road segment with the minimum effort value. To avoid traffic congestion, we defined a novel thresholding mechanism that penalizes efficiently the computed effort on a road segment to avoid congestion when possible. To achieve this, it is necessary to know the traffic state of each segment at any moment. For this purpose, we use the KEP tree for storage, and query and update the vehicular traffic state in a simulated ecosystem. The KEP tree data structure used to model vehicular traffic scales very well and is easy to implement. The algorithms that correspond to the query and update operations are described in [8]. The following notations and concepts are used as a model by Algorithm 1 and its sub-routines that use the traffic thresholding mechanism to avoid congestion:  
* \(p_{s}\)--starting point of a route given as GPS coordinates;
* \(p_{d}\)--destination point of a route given as GPS coordinates;
* segment\({}_{s}\) and segment\({}_{d}\)--road segments corresponding to \(p_{s}\) and \(p_{d}\), respectively. The road segments are found through map matching of \(p_{s}\) and \(p_{d}\), respectively. Each segment is represented by two GPS points that correspond to the begin and the end of the segment;
* \(t_{0}\)--variable representing the timestamp when a specific vehicle starts to run on its planned route;
* \(t_{s}\)--variable representing the timestamp when a specific vehicle starts to run on any segment. Used as a local variable in the algorithms;  
Figure 2: Flow diagram of vehicular traffic congestion avoidance solution. * \(\mathrm{t_{e}}\)--variable representing the timestamp when a specific vehicle leaves any segment. Used as a local variable in the algorithms;
* ETT--variable representing the current estimated travel time until passing any segment. Used as a local variable in the algorithms;
* route(\(\mathrm{p_{s}}\),\(\mathrm{p_{d}}\))--computed route between \(p_{s}\) and \(p_{d}\) represented by a set of consecutive connected road segments;
* \(\mathrm{\delta}\)--variable representing the average time spent for each traffic light (seconds). This has a specific value for each urban area;
* Esegment--variable representing the already computed effort value corresponding to a segment in a computed route. Its value is computed during route computation algorithm;
* N(node)--set of not visited neighbours of node. Each neighbour is represented by a road segment;
* Emax--numeric constant value representing the maximum effort factor used during effort computation (used to reduce graph exploration);
* Smin--numeric constant value representing the minimum speed factor used for speed computation in the case of congestion;
* Dmax--numeric constant value representing the maximum delay factor used for delay computation in the case of congestion;
* Lvehicle--numeric constant value representing the average length of the space needed by a vehicle on the road.