20+ Million Readerbase
Indexed In
  • Genamics JournalSeek
  • RefSeek
  • Hamdard University
  • EBSCO A-Z
  • OCLC- WorldCat
  • Publons
  • Euro Pub
  • Google Scholar
Share This Page
Recommended Webinars & Conferences

Global Summit on Robotics and Artificial Intelligence

Prague, Czech Republic
Journal Flyer
Flyer image

Research Article - (2014) Volume 3, Issue 1

Reverse Online Algorithm for the Dynamic Traffic Assignment inspired by Ant Colony Optimization for VANETs

Wilmer Arellano and Imad Mahgoub*
Department of Computer & Electrical Engineering and Computer Science, Florida Atlantic University, 777 Glades Road, S&E 406,Boca Raton, FL 33431, USA, E-mail: [email protected]
*Corresponding Author: Imad Mahgoub, Department of Computer & Electrical Engineering and Computer Science, Florida Atlantic University, 777 Glades Road, S&E 406,Boca Raton, FL 33431, USA, Tel: 561.297.3458, Fax: (561) 297-2800 Email:

Abstract

We present a novel decentralized and infrastructure-less algorithm to alleviate traffic congestions on road networks and to fill the void left by current algorithms which are either static, centralized, or require infrastructure. The algorithm follows an online approach that seeks stochastic user equilibrium and assigns traffic as it evolves in real time, without prior knowledge of the traffic demand or the schedule of the cars that will enter the road network in the future. Reverse Online Algorithm for the Dynamic Traffic Assignment inspired by Ant Colony Optimization for VANETs is a metaheuristic approach that uses reports from other vehicles to update the vehicle’s perceived view of the road network and change route if necessary. To alleviate the broadcast storm spontaneous clusters are created around traffic incidents and a threshold system based on the level of congestion is used to limit the number of incidents to be reported. Simulation results for the algorithm show a great improvement on travel time over routing based on shortest distance.

Introduction

Vehicular Ad hoc NETworks (VANETs) are a subclass of Mobile Ad hoc NETworks (MANETs) and represent a relatively new and very active field of research. Some particular characteristics of VANETs that make them unique are high-speed mobility, driver behavior depending on personality traits, and mobility constraints as cars move on roadways with set boundaries. VANETs will enable in the near future applications that will dramatically improve roadway safety and traffic efficiency and significantly improve the associated ecological impact. According to the Federal Highway Administration (FHWA) [1], the U.S. highway network was near completion by the late 1980s, there has been little construction of new roads and highways and the number of lane miles has been increased mainly by adding additional lanes to existing highways to carry more vehicles. From 1985 to 2006 the lane miles increased from 8 to 8.4 million while during the same period the vehicle miles traveled has doubled. From these figures and the familiar transit congestions that take place almost daily, it is clear that a new and intelligent approach is needed for optimizing road usage. Traffic assignment tries to distribute vehicles efficiently on the road network and in accordance with their origins and destinations [2-16]. Ant Colony Optimization (ACO) is a methaheuristic useful for obtaining minimum cost paths [17-24]. This methaheuristic has been applied successfully in different branches of engineering [25-35]. ACO has gained popularity recently for traffic assignment and many algorithms have been inspired by this metaheuristic [36-47]. In this paper we present a novel dynamic traffic assignment algorithm for VANET environments. The ACO inspired algorithm is decentralized and infrastructure-less. The algorithm employs a unique on the fly cluster system that minimizes maintenance overhead as clusters are formed just to report traffic incidents and vanish after the incident is reported. The algorithm avoids broadcast storm by blocking additional reports on the same road segment in a given aggregation period by setting a speed threshold in order not to report every speed reduction in the segment and by reporting only bad traffic conditions. The ant inspired algorithm differs from traditional ACO algorithms as ants know the whole road network map, are able to broadcast pheromone, and pheromone is used to mark bad trails. The rest of this paper is organized as follows. In Section 2, we introduce relevant related work. Section 3 presents an overview of traffic assignment. Section 4 introduces ant colony optimization and some of its applications. The proposed algorithm is presented in Section 5. The simulation setup is explained in Section 6. The results and analysis are presented in Section 7. Finally the conclusions are included in Section 8.

Related Work

Traffic assignment is the process of assigning the traffic demand to the routes on a road network. Wardrop [2] defined two equilibrium criteria for the traffic flowing from a set of origins to a set of destinations: user equilibrium assignment (UE) and system Optimum Assignment (SO), depending on whether we optimize from the user’s point of view or from the system’s point of view. These criteria are also referred to as deterministic user equilibrium assignment (D-UE) and deterministic system Optimum Assignment (D-SO). Traffic assignment is commonly modeled by means of two different mathematical formulations, the static traffic assignment (STA), and the dynamic traffic assignment (DTA) depending on whether the traffic flow is constant or time dependent. An STA model for both Wardrop's principles was first presented in [3]. DTA originated from the seminal works of Yagar in 1971 [4,5], and Merchant and Nemhauser in 1978 [48,6]. DTA problems can be classified as mathematical programming formulations, optimal control formulations, variational inequalities formulations, and simulation-based models [6]. Heuristic approaches and simulation-based models are used in pursuit of realistic traffic solutions. Of great importance are the probabilistic or stochastic heuristic methods that in general provide more accurate results than the deterministic counterparts [7]. Achieving UE analytically is in general a very difficult task unless some simplifications are made. The Stochastic Network Loading (S-N-L) type of problems assumes that the measured travel times are independent of the link flows [7]. S-N-L problems can be approached with analytical methods [8] or by stochastic simulation [9]. Totally different approaches that do not make this assumption are based on the ants foraging behavior [17]. An Ant Colony Optimization (ACO) model using multiple ant colonies, one colony for every origin destination pair is used in [36] and [37], where stochastic user equilibrium (S-UE) algorithms for the fixed-point traffic assignment problem are proposed. Information on transportation fixed-point problems can be found in [10,16]. Approaches based on Ant Colony System (ACS) are presented in [38,49], for both S-UE and D-UE. An ACO approach for solving the Local Optimization of Signal Settings (LOSS) is presented in [39]. This problem deals with the local optimization of traffic light signals based on the vehicle route choices and the traffic flow on that particular intersection. An ACO algorithm for the Vehicle Routing Problem is presented in [41]. So far all of these ant-inspired algorithms are intended for the STA and there is a need for algorithms for the DTA. [40] Presents an ACO based algorithm for DTA by routing vehicles at intersections. However, this algorithm is centralized. Centralized algorithms for VANETs require the existence of an infrastructure that may not always be available and suffer from great computational complexity. Claes et al. [42] presents a DTA approach based on ACO inspired agents representing vehicles and roads. This system is decentralized but requires infrastructure. In [43] a local control of traffic lights is proposed along with an infrastructure supported, cluster organized system, where vehicles use ACO inspired algorithms for routing. In [44] a centralized system is proposed where ants going from a given origin to a destination select the 5 best routes and update pheromone just in those routes. In case of congestion ants choose alternate best routes until the situation is resolved. Tatomir et al., [45] presents a DTA system where the road map is divided into zones in a hierarchical way. Vehicles interchange information with infrastructure to allow travel time estimation and best route selection by ACO. In [46] two strategies to avoid congestion are presented using pheromone marks on a decentralized system of servers. [47] presents an infrastructure supported dynamic routing system to replace static routing such as Dijkstra's. The intersections contain routing tables based on history and on cars in the simulation. In Table 1 we illustrate the advantage of the proposed algorithm. The algorithm we present in this paper is for the DTA and is decentralized and infrastructure-less.

Algorithm DTA Decentralized Infrastructure-less
ACS, [36] and [37]      
ACO-based algorithm for solving the LOSS problem, [39]      
ACR, [40] X    
Anticipatory Vehicle Routing Using Delegate Multiagent Systems, [42] X X  
Vehicular Routing with Optimal Path, [43] X X  
Dynamic System for Avoiding Traffic Jam, [44] X    
H-ABC, [45] X X  
Self-organizing congestion evasion strategies, [46] X X  
Dynamic routing system based on Ant Based Control (ABC), [47] X X  
Proposed algorithm, Road-ACO X X X

Table 1: Comparison of different ACO inspired algorithms with the proposed algorithm.

Overview of Traffic Assignment

The road network is represented as a graph G = (N,L), where vector N represents the nodes (intersections) and vector L represents the links (lanes). For each arclεL we define the free travel time, as the minimum travel time required when traversing a at the maximal allowed speed. We represent with OD N x N the set of fixed origins and destinations the road network. We use od to denote an origin destination pair, od ⊂ OD, and Rod to denote the set of all routes or paths that connect the origin of od with its destination. A route is an ordered sequence of consecutive links connecting the origin of certain od to its destination, where the end node of any link coincides with the start node of the next link. We represent road segments with edges. We define edge as a set of lanes, which physically run in parallel next to each other, connecting two adjacent nodes. As in real life, edges may include lanes with traffic flow in opposite directions.

Traffic assignment

There are two different models that can be identified when investigating road networks transit problems, the transportation planning models and the traffic flow models [11]. Transportation planning models deal with modeling the route and schedule decisions made by individuals who use the roads and the approaches used by researchers to optimize traffic. Traffic flow models deals with modeling the physical propagation of traffic flows. As physical tests can be difficult and expensive to implement Traffic flow models are used for testing the new traffic solutions proposed by researchers. When selecting the best routes in traffic assignment it is typical to assign a cost based on distance and/or time to the different edges and then use a shortest path algorithm such as Dijkstra’s algorithm [50]. Wardrop [2] established two equilibrium criteria relating to the traffic flow from a given origin to a certain destination using the available routes:

User equilibrium assignment (UE). The journey times on all the routes actually used are equal, and less than those which would be experienced by a single vehicle on any unused route [2].

System Optimum Assignment (SO). The average journey time is minimum [2].

These criteria are also referred to in the literature, as deterministic user equilibrium assignment (D-UE) and deterministic system Optimum Assignment (D-SO). In Figure 1 we can see this classification. We could say that in D-UE all decisions are made in an egoistic and rational way and all users have knowledge of the paths costs. In D-SO there may be cooperation among individuals or a centralized system coordinating the route assignment.

Figure

Figure 1: Traffic Equilibrium Classification.

The optimization of transportation on a road network is commonly formulated by means of two different mathematical formulations, the static traffic assignment (STA), and the dynamic traffic assignment (DTA). The STA approach deals with networks in equilibrium where the traffic demand and the edge flows are constant over time. On the other hand, the DTA deals with the more realistic situation of time dependent edge flows and congestion.

The static traffic assignment

The Static Traffic Assignment (STA) assigns routes to a set of drivers with fixed origins and destinations under steady state flow conditions. A model of the equilibrium assignment for both Wardrop's principles, the UE and the SO, was first presented by Martin Beckmann, Bartlett McGuire and Christopher Winsten (BMW) [3]. This solution became a standard in transportation planning since it was introduced. Currently as new approaches have emerged. Solutions based on dynamic traffic assignment have become available for dealing with congestion and variable conditions.

The dynamic traffic assignment

The dynamic traffic assignment (DTA) refers to a broad variety of problems that deals with time-varying flows and originated with the seminal works of Yagar in 1971 [4,5], and Merchant and Nemhauser in 1978 [6,48]. These models aim at representing the interaction between route choices, traffic flows, and time and cost metrics in a coherent fashion as time passes [12]. DTA problems can be classified as [6] mathematical programming formulations, Optimal control formulations, variational inequalities formulations, and Simulation-based models [6]. The first three types of approaches suffer from problems induced by the algorithms such as artificial delays at junctions [6,13], and first in first out (FIFO) violations [6,13,14]. These problems are not consistent with traffic realism [6]. Simulation-based models utilize traffic flow propagation models to model the critical constraints that regulate traffic flow. The simulation is used as an approach to produce realistic solutions that satisfy the FIFO constraint and prevent the artificial delays.

Heuristic stochastic approaches

Heuristic methods can be used for both STA and DTA. Much effort has been dedicated to heuristic approaches. These approaches can be subdivided into deterministic and probabilistic or stochastic methods. The first type usually fails on uncongested road networks where stochastic approaches provide more accurate results [7]. A new equilibrium criterion is needed for these approaches, the stochastic user equilibrium (S-UE). For the traffic flow from a given origin to a certain destination using the available routes, in S-UE no user believes he/she can improve his journey time by unilaterally changing routes [7]. In an S-UE system the vehicles have access to a graph representing the network where the edge costs are represented by a vector of stochastic and unobserved perceived travel times. In general these edge travel times may change in time and differ from vehicle to vehicle. Achieving UE analytically is in general a very difficult task unless some simplifications are made. For example, the Stochastic Network Loading (S-N-L) problems assume that the measured travel times are independent of the edge flows [7].

Simulation-based models are used to model realistically the critical constraints that regulate traffic flow. Social insects exhibit efficient behaviors for path selection [18], next we present Ant Colony Optimization (ACO), a metaheuristic that has proved to be useful in determining minimum cost paths [17] and may be used in simulation-based models.

Ant Colony Optimization

Ant Colony Optimization (ACO) is a relatively new metaheuristic based on the social behavior of ants. These insects are very efficient in finding the best path/food-source combination. Their interesting methods are based on individuals with simple behaviors that interchange information indirectly by means of chemical compounds (pheromones) they use to mark their paths. Ant colony optimization was introduced by M. Dorigo and colleagues [19-21]. According to [21], this new metaheuristic was greatly inspired by the behavior of real ants [22-24]. Great effort has been dedicated to ACO applications in computer science and engineering. Several ACO algorithms have been proposed for the Traveling Salesman Problem (TSP) [25,26]. ACO approaches for the Job Shop Scheduling Problem (JSSP) and the Flexible Job Shop Scheduling Problem (FJSSP) have applications in controlling mechanical engineering machines [27,28]. ACO algorithms have been used in civil engineering for economic optimization of reinforced concrete [29].

Research in Ant Colony Optimization has also been conducted in digital image processing [30], electrical engineering where a system has been proposed for environmental/economic dispatch [31], as well as several routing protocols in computer engineering [32,33]. More information on ACO applications can be found in [34,35].

When natural ants are faced with a food source that can be reached only by crossing one of two bridges of different length, they usually choose the shortest bridge. At the beginning some ants may use the shortest bridge and others may choose the longest one. As the ants walk they drop pheromones to mark the path. Ants that started the shortest way will arrive earlier at the food source and will return following the scent on the trail they used while they drop more pheromones increasing the scent on the shortest trail faster. For the ants starting the process, the stronger scent will orient them towards the shortest path. The process is a little bit more complex and is affected by factors such as evaporation, dropping frequency modulated by the quality of the food source, system feedback, and sensors imperfection, among others. Evaporation is an important component that helps minimize the impact of wrong decisions and may also decrease interest on a route in case of food depletion.

The path selection mechanism has inspired software approaches with artificial ants for problems where a minimum cost path solution is required both in communications and in road networks [32,41]. The artificial ants travel the network and update the nodes information with artificial pheromone that can be sensed by other ants to make routing decisions. It is common that artificial ants mark the information of the arcs they visited only on the way back to the source according to equation (1). In this equation the pheromone concentration from node i to node j at node i, τij, is updated by the traveling ant kwith pheromone deposit Δτkafter evaporation coefficient ρ is applied.

Proposed Algorithm

We propose a novel algorithm, Reverse Online Algorithm for the Dynamic-Traffic-Assignment Ant-Colony-Optimization inspired (Road-ACO) that assigns traffic as it evolves in real time, without prior knowledge of the traffic demand or the schedule of the cars that will enter the road network in the future. This novel decentralized online algorithm employs a new breed of ants which are position aware, capable of broadcasting pheromone information, have the road map in memory along with perceived edge costs, and execute shortest path algorithms in a selfish manner consistent with S-UE, just like a VANET enabled car. Additionally these ants differ from the traditional ants by the reverse way they use pheromone. Higher intensity indicates road segments of lesser quality, in contrast to better routes in traditional ants. Similar to traditional ants, the new breed of ants use pheromone subject to evaporation, and make routing decisions based on the pheromone concentration on the edges, although they make decisions based on the pheromone concentrations on the entire map and not just on the current node. In real life ants evaporation indicates routes becoming less appealing due to food quality depletion. In our case, evaporation is the mechanism that progressively increases the quality of routes as decreased pheromone concentration means less congestion. Using the terms ant and vehicles indistinctively, we now proceed to describe Road-ACO.

Algorithm variables

We now define the simulation variables which can be divided into global and local variables. The global variables are constant and have the same value for all vehicles. Local variables store data corresponding to the individual vehicles. We now list all the variables of interest.

Global variables

Aggregation period (ap). Duration window which defines the time used by vehicles to determine travel conditions.

Edge default travel time (edtt). The time it takes to travel that edge at the maximum allowed speed.

• ρ. Represents the pheromone evaporation. •Speed aggregation threshold (sat). Threshold used to trigger a vehicle to become a cluster head.

Consensus threshold (ct). Threshold that triggers when a cluster head reports a traffic incident.

Local variables

Step counter. Used as a timer variable, to cycle through the Aggregation period.

• τij.Represents the pheromone concentration or edge cost from node to node at node , as perceived by the individual vehicle.

• Δτk.Represents the pheromone intensity used by cluster head k to mark the edge it is currently in, in case of traffic incident.

Speed moving average (sma). Stores the modified moving average of the vehicle speed.

Aggregated average speed (aas). Used by cluster heads to aggregate the average speed of reporting vehicles.

Aggregated travel time (att). Used by cluster heads to compute the pheromone intensity.

The algorithm

The algorithm can be subdivided into three sub algorithms, the speed aggregation, cluster, and the communication algorithms. The speed aggregation and the communication algorithms run concurrently at all times while the cluster algorithm is executed only when an abnormal traffic flow condition occurs. Each vehicle on the simulated road network independently executes these algorithms in a decentralized fashion.

The speed aggregation algorithm

Figure 2 illustrates the speed aggregation algorithm. When a vehicle enters into the simulated road network, the global variables are read, the step counter is set to 1, and the speed moving average is set to 0. At every time step thereafter the vehicle performs the following actions:

Figure

Figure 2: Speed aggregation algorithm.

•Applies evaporation to the perceived edge costs according to τij=(1-ρ) τij

•If, for a certain edge, the new τij value is less than the edge default travel time, then τij =default travel time is used.

•Acquires the current speed at which it is traveling and updates the speed moving average as:

sma(sma*(ap-1)+current speed)/ap.

•The step counter is incremented by 1.

•At the end of its aggregation period, the vehicle checks if the speed moving average falls under the speed aggregation threshold. If this is true the vehicle will execute the cluster algorithm.

The cluster algorithm

This algorithm is executed when the speed moving average falls under the speed aggregation threshold in the speed aggregation algorithm. Figure 3 illustrates this algorithm. The vehicle that satisfies the mentioned condition organizes a cluster on the edge it is currently in by broadcasting a request message and becoming the cluster head. Each cluster member will reply with a reply message containing the member's average speed. During an entire aggregation cycle the cluster head aggregates the received average speeds sent by the cluster members into aggregated average speed. At the end of this cycle, if the ratio of number of reply messages in consensus with the low speed condition (nrmc) to the total number of reply messages (TNRM) exceeds the consensus threshold, a pheromone drop is broadcasted in a traffic incident message and the cluster dissolves. The pheromone drop intensity is calculated according to:

Figure

Figure 3: Cluster Algorithm

Δτk← (edtt +att*(nrmc -1)/TNRM

The formula above produces pheromone drop intensity increasing with the number of reply messages in consensus. If the total number of reply messages is large but the number of reply messages in consensus is small, the drop has low intensity as one would expect and could be negligible. The cluster formation process is explained in the communication algorithm.

The communication algorithm

Figure 4 illustrates the communication algorithm. Vehicles on the simulated road network continuously monitor the communication channel waiting for two different kind of messages, request messages and traffic incident messages. Every vehicle on the same edge as the cluster head that receives the request message will send a reply message containing its average speed and resets its step counter to 1 to prevent broadcasting any new request message until the end of the new aggregation cycle. Every vehicle receiving the traffic incident message will update the edge cost according to and execute a shortest path algorithm using its internal map and the perceived costs in memory. The vehicle will reroute if a better route is found.

Figure

Figure 4: Communication Algorithm.

Adverse scenarios

There are two situations that may impair the operation of the algorithm:

•Road blockages. In the presence of a total road blockage the algorithm will not work. Given the way road networks are structured usually with multiple lanes and alternate roads, a total blockage is not likely to happen. As mentioned before, in Wardrop's UE users make routing decisions in an egoistic and rational way and all users have knowledge of the paths costs. Our algorithm uses egoistic routing with knowledge of the paths costs as in Wardrop's UE. In the case of a partial blockage, where vehicles can use alternate routing options, our algorithm will approach a new Wardrop's UE corresponding to the new network conditions.

Delayed information. The performance of the algorithm can be impaired if the paths costs information is not updated frequently. This may lead to oscillations as routing based on old information may send incoming vehicles to selected roads for long periods of time increasing congestion on those roads. When these new levels of congestion are reported it will favor alternate routes and repeat the process while the traffic on the previous roads subsides. To avoid this problem we chose a sufficiently small update period (5 seconds). As an example, at 70 MPH and a headway of 1 second, just 4 cars per lane will arrive at an intersection during a 5 second window. In the future we will investigate the impact of this parameter on the algorithm performance.

Next we proceed to explain our simulation details.

Simulation

Setup

We evaluate the algorithm performance in a simulation environment composed of OMNET++ [51], SUMO [52], and Veins [53], similar to the environment described in [54]. The simulation is performed according to IEEE 1609.4 as implemented in Veins. In the next section, we describe the simulated environment, state the assumptions, and define the input and output parameters.

Simulated environment

Figure 5 and Table 2 show the simulated road network. As we explain bellow, some vehicles may need to reroute to improve their travel times. All roads have two lanes in each direction, a maximum speed of 40 MPH, and U turns are permitted. The horizontal edges are 495 ftlong, and all other edges are 720 ft long. The road network contains 5 nodes: -4, -6, -8, - 10, -12, -14, (-n denotes node n). Nodes -10, -14 are origins and node -4 is the only destination. From each origin node, -10, and -14, 1,000 vehicles depart to the common destination -4. When vehicles depart they have a planed route based on a shortest route algorithm (SR). Even though this road network is very symmetric and would suggest that all vehicles should use the shortest routes, differences in the traffic light signals and the allowed lane changes make the top route faster and vehicles may need to reroute to improve their travel times. The upper route is more favorable because: first, the traffic lights at nodes-8 and -6 both offer green light in sync to the incoming vehicles, while for the lower route when the traffic light at junction-12 is green, the traffic light at junction-6 has the red light on. Second, the intersection-6 favors the upper edge as the two lanes on it allow travel towards the destination while just one lane from the bottom route allows transit to the destination, since the other lane is forced to turn left. Figure 6 illustrates these lane details. All the traffic lights in the direction towards the destination have the following cycle: green, yellow, red, equal to 31, 6, and 49 seconds respectively. This was the default cycle assigned by SUMO.

Figure

Figure 5: Road Network Description.

Node Description denotes node
Origins -10, -14
Destinations -4
Junctions -8, -12, -6
Traffic Demand
OD Volume
(-10, -4) 1,000
(-14, -4) 2,000

Table 2: Road Network Description.

Figure

Figure 6: Lane Connection Detail, intersection-6.

Simulation assumptions

It is assumed that the algorithm messages would be broadcasted using regular IEEE1609 standard beacons. All vehicles are 16.4 ft long and acceleration and deceleration are 8.53 and 14.76 ft/s2 respectively.

Input parameters

The number of vehicles entering the simulated road network from each origin. Vehicles enter the network as fast as the congestion of the roads allows. For our simulation we used 1,000 vehicles per origin. This number was selected based on reasonable simulation time and because it produces significant traffic congestion when routing by SR.

The evaporation. Several values of this parameter are tested to assess the impact on the solution of the speed at which pheromone vanishes when recovering from wrong decisions and congestion. The value of this variable was systematically changed to obtain the greatest traffic flow improvement.

The speed aggregation threshold. This parameter is varied to assess the impact of ignoring certain values of congestion level over the solution. The value of this variable was systematically changed to determine how much of congestion can be ignored and still obtain significant traffic flow improvements.

Output parameters

The outputs of the simulation are the vehicle’s average traveling time, and the total time, measured from the start of the simulation to the moment that the last vehicle reaches its destination. The values of these two parameters are obtained for the cases of route selected by SR, UE as calculated by traffic simulator SUMO (SUMO-DTA), and with the proposed algorithm for several different input parameters. The Veins framework which controls the simulation keeps record of many and diverse simulation results, from there we were able to obtain our parameters of interest, average traveling time and the total time. In the next section the simulation results are analyzed.

Results and Analysis

Evaluating the performance of a DTA algorithm under UE, by using the definition of UE, is a difficult task as this equilibrium implies that no vehicle can improve its travel time by changing routes and that is hard to assess. We base our evaluation on average trip times. A solution that seeks UE should have average trip times close to that of the optimal UE. Otherwise some vehicles could be able to reduced their individual travel times, contradicting the definition of UE. Our algorithm does not minimize average trip times as that would produce SO and not UE, however it is known that UE, even though less efficient, is practical to achieve and not so far from SO [15]. Table 3 contains the 24 simulation results. Row 1 contains the data for the case when shortest route algorithm is used; it is the worst case as it shows the largest simulation and average trip times. On the other hand, row 2 shows the data for the case of SUMO-DTA. This solution presents the best simulation and average trip times with an improvement of 34.97% in average trip times. The rest of the rows show the data for the proposed algorithm for different input parameters. All of the proposed algorithm trials show improvement over the average trip times of the SR. If any two solutions present similar average trip time, we prefer the one with the lowest simulation time. The best outcome is 29.17% for an evaporation of 25% and speed aggregation threshold of 50%. Evaporation of 25% appears to be a good choice in this scenario as the three best outcomes include this value. The best solution has a speed aggregation threshold value of 50%, this implies less use of the communication channel and prevents unnecessary rerouting.

Row Algorithm Evaporation ( % ) Speed AggregationThreshold(%) Simulation Time(seconds) Average VehicleTripTime(seconds) Improvement ( % )
1 SR N/A 100 7,803 278.25 0
2 SUMO-DTA N/A 100 4,142 180.95 34.97
3 ACO 25 50 5,426 197.09 29.17
4 ACO 25 100 5,229 197.31 29.09
5 ACO 25 25 5,306 200.38 27.99
6 ACO 20 100 5,345 203.88 26.73
7 ACO 25 75 5,476 204.51 26.5
8 ACO 50 100 5,647 207.13 25.56
9 ACO 5 100 5,598 213.16 23.39
10 ACO 10 100 5,663 218.89 21.33

Table 3: Simulation Results. ct=25%, ap=5.

Conclusions

We introduce and evaluate Road-ACO, a novel decentralized algorithm to alleviate traffic congestions on road networks and to fill the void left by current algorithms which are either static, centralized, or require infrastructure. Road-ACO is an algorithm inspired by Ant Colony Optimization for the Dynamic Traffic Assignment in VANETS. Initial results indicate a promising future for approaches based on this algorithm. Simulation results for the algorithm show an improvement on travel time of 29.17%, over the SR case, which is fairly close to the improvement introduced by SUMO-DTA (34.97%). It is important to indicate that Road-ACO is a realistic approach as it improves traffic as it evolves, in real time, without prior knowledge of the traffic demand or the schedule of the cars that will enter the road network in the future. Also Road-ACO enjoys the benefits of being decentralized and infrastructure-less. We expect the algorithm to perform well if we increase the road network complexity and the number of vehicles. However, in this case the algorithm needs to be modified to include multi-hops and Time To Live (TTL). Our main concern is the simulation time as the interactions between simulators SUMO and OMNET++ are time consuming. We plan to address this problem by reducing the number of interactions by including in OMNET++ some of the functions that are currently executed by SUMO like the case of changing the oute to the one with the lowest cost. In the near future we will continue to investigate the performance Road-ACO in larger and more complex road networks.

References

  1. “Our Nation’s Highways - onh.pdf.” [Online]. Available: http://www.fhwa.dot.gov/policyinformation/pubs/pl08021/pdf/onh.pdf. [Accessed: 24-Oct-2013].
  2. Wardrop JG (1952) “ROAD PAPER. SOME THEORETICAL ASPECTS OF ROAD TRAFFIC RESEARCH.,” in ICE Proceedings: Engineering Divisions, 1: 325–362.
  3. Beckmann M, McGuire CB, Winsten CB (1956) “Studies in the Economics of Transportation” Research Memoranda, Rand Corporation.
  4. Yagar S (1971) “Dynamic traffic assignment by individual path minimization and queuing,” Transp. Res, 5: 179–196.
  5. Szeto WY, Wong SC (2012) “Dynamic traffic assignment: model classifications and recent advances in travel choice principles,” Cent. Eur. J. Eng, 2: 1–18.
  6. Peeta S, Ziliaskopoulos AK (2001) “Foundations of dynamic traffic assignment: The past, the present and the future,” Netw. Spat. Econ, 1: 233–265.
  7. Daganzo CF, Sheffi Y (1977) “On stochastic models of traffic assignment,” Transp. Sci, 11: 253–274.
  8. Dial RB (1971) “A probabilistic multipath traffic assignment model which obviates path enumeration,” Transp. Res, 5: 83–111.
  9. von Falkenhausen H (1966) Traffic assignment by a stochastic model. MIT, Cambridge, USA.
  10. Daganzo CF (1983) “Stochastic Network Equilibrium with Multiple Vehicle Types and Asymmetric, Indefinite Link Cost Jacobians,” Transp. Sci., 17: 282–300.
  11. Maerivoet S, De Moor B (2005) “Transportation planning and traffic flow models,” ArXivPrepr. Physics 0507127.
  12. Chiu YC, Bottom J, Mahut M, Paz A, Balakrishna R, Waller T, Hicks J (2011) “Dynamic traffic assignment: A primer,” Transp. Res. E-Circ., no. E-C153.
  13. Carey M, Subrahmanian E (2000) “An approach to modelling time-varying flows on congested networks,” Transp. Res. Part B Methodol., 34: 157–183.
  14. Carey M (1992) “Nonconvexity of the dynamic traffic assignment problem,” Transp. Res. Part B Methodol., 26: 127–133.
  15. Correa JR, Schulz AS, Stier-Moses NE (2004) “Selfish routing in capacitated networks,” Math. Oper. Res., 29: 961–976.
  16. Cantarella GE (1997) “A General Fixed-Point Approach to Multimode Multi-User Equilibrium Assignment with Elastic Demand,” Transp. Sci., 31: 107– 128.
  17. Dorigo M, Stützle T (2004) Ant Colony Optimization, Fist ed. MIT Press, USA.
  18. Arellano W, Mahgoub I (2007) “Swarm Intelligence-Inspired Routing Algorithms for Ad Hoc Wireless Networks,” in Encyclopedia of Wireless and Mobile Communications, Second Edition, Taylor & Francis.
  19. Dorigo M (1992) “Optimization, learning and natural algorithms,” Ph Thesis Politec. Milano Italy.
  20. Dorigo M, Maniezzo V, Colorni A, Maniezzo AC (1991)“Positive Feedback as a Search Strategy,” .
  21. Dorigo M, Maniezzo V, Colorni A, “Ant system: optimization by a colony of cooperating agents,” IEEE Trans. Syst. Man Cybern. Part B Cybern., 26: 29–41.
  22. Deneubourg JL, Pasteels JM, Verhaeghe JC (1983) “Probabilistic behaviour in ants: A strategy of errors?,” J. Theor. Biol., 105: 259–271.
  23. Deneubourg JL, Goss S (1989) “Collective patterns and decision-making,” Ethol. Ecol. Evol., 1: 295–311.
  24. Goss S, Beckers R, Deneubourg JL, Aron S, Pasteels JM (1990) “How trail laying and trail following can solve foraging problems for ant colonies,” in BehMech Food Sel, 20: 661–678.
  25. Dorigo M, Gambardella LM (1997) “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Trans. Evol. Comput., 1: 53–66.
  26. López-Ibáñez M, Blum C (2010) “Beam-ACO for the travelling salesman problem with time windows,” Comput. Oper. Res., 37: 1570–1583.
  27. Xing LN, Chen YW, Wang P, Zhao QS, Xiong J (2010) “A Knowledge-Based Ant Colony Optimization for Flexible Job Shop Scheduling Problems,” Appl. Soft Comput., 10: 888–896.
  28. Heinonen J,  Pettersson F (2007) “Hybrid ant colony optimization and visibility studies applied to a job-shop scheduling problem,” Appl. Math. Comput., 187: 989–998.
  29. Martínez FJ, González-Vidosa F, Hospitaler A, Yepes V (2010) “Heuristic optimization of RC bridge piers with rectangular hollow sections,” Comput. Struct., 88: 375–386.
  30. Yu Z, Au OC, Zou R, Yu W, Tian J (2010) “An adaptive unsupervised approach toward pixel clustering and color image segmentation,” Pattern Recognit., 43: 1889–1906.
  31. Cai J, Ma X, Li Q, Li L, Peng H (2010) “A multi-objective chaotic ant swarm optimization for environmental/economic dispatch,” Int. J. Electr. Power Energy Syst., 32: 337–344.
  32. Di Caro G, Dorigo M (2011) “AntNet: Distributed stigmergetic control for communications networks,” ArxivPrepr. ArXiv11055449, 2011.
  33. Di Caro G, Ducatelle F, Gambardella LM (2005) “AntHocNet: an adaptive nature-inspired algorithm for routing in mobile ad hoc networks,” Eur. Trans. Telecommun., 16: 443–455.
  34. Dorigo M, Blum C (2005) “Ant colony optimization theory: A survey,” Theor. Comput. Sci., 44: 243–278.
  35. Chandra Mohan B, Baskaran R (2012) “A survey: Ant Colony Optimization based recent research and implementation on several engineering domain,” Expert Syst. Appl., 39: 4618–4627.
  36. Mussone L, Ponzi M, Matteucci M (2005) “Ant colony optimization for stochastic user equilibrium,” Sist. Str. Trasp. Nella Soc. Dell’informazioneMonit. Simulazione E PredisposizioneBasi Inf. Din., Italy.
  37. LD Acierno, Montella B, Lucia FD (2006) “A Stochastic Traffic Assignment Algorithm Based on Ant Colony Optimisation,” in Ant Col Opt Swarm Intel, 4: 25–36.
  38. Matteucci M, Mussone L (2006) “Ant Colony Optimization Technique for Equilibrium Assignment in Congested Transportation Networks,” in Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, New York, NY, USA.
  39. Acierno LD, Gallo M, Montella B (2012) “An Ant Colony Optimisation algorithm for solving the asymmetric traffic assignment problem,” Eur. J. Oper. Res., 217: 459–469.
  40. Cong J, Schutter BD, Babuška R (2013) “Ant Colony Routing algorithm for freeway networks,” Transp. Res. Part C Emerg. Technol., 37: 1–19.
  41. Bell JE, McMullen PR (2004) “Ant colony optimization techniques for the vehicle routing problem,” Adv. Eng. Inform., 18: 41–48.
  42. Claes R, Holvoet T, Weyns D (2011) “A Decentralized Approach for Anticipatory Vehicle Routing Using Delegate Multiagent Systems,” IEEE Trans. Intell. Transp. Syst., 12: 364–373.
  43. Sattari MRJ, Malakooti H, Jalooli A, Noor RM (2014) “A Dynamic Vehicular Traffic Control Using Ant Colony and Traffic Light Optimization,” in Adv Sys Sci, 240: 57–66.
  44. Bedi P, Mediratta N, Dhand S, Sharma R, Singhal A (2007) “Avoiding Traffic Jam Using Ant Colony Optimization - A Novel Approach,” in International Conference on Conference on Computational Intelligence and Multimedia Applications, 1: 61–67.
  45. Tatomir B, Rothkrantz L (2006) “Hierarchical Routing in Traffic Using Swarm-Intelligence,” in IEEE Intelligent Transportation Systems Conference, Toronto, USA.
  46. Narzt W, Wilflingseder U, Pomberger G, Kolb D, Hortner H (2010) “Self-organising congestion evasion strategies using ant-based pheromones,” Intell. Transp. Syst. IET, 4: 93–102.
  47. Tatomir B, Rothkrantz LJ, Suson AC (2009) “Travel time prediction for dynamic routing using ant based control,” in Simulation Conference (WSC), Proceedings of the 2009 Winter, Austin, USA.
  48. Merchant DK, Nemhauser GL (1978) “A Model and an Algorithm for the Dynamic Traffic Assignment Problems,” Transp. Sci., 12: 183–199.
  49. Matteucci M, Mussone L (2013) “An ant colony system for transportation user equilibrium analysis in congested networks,” Swarm Intell., 7: 255– 277.
  50. Dijkstra EW (1959) “A note on two problems in connexion with graphs,” Numer. Math., 1: 269–271.
  51. Varga, A. (2010), "OMNeT++". Chapter in the book "Modeling and Tools for Network Simulation", Wehrle, Klaus; Günes, Mesut; Gross, James (Eds.)  Springer Verlag, 2010. ISBN: 978-3-642-12330-6.
  52. “SUMO - Simulation of Urban Mobility.” [Online]. Available: http://sumo.sourceforge.net/. [Accessed: 06-Apr-2013].
  53. “Veins.” [Online]. Available: http://veins.car2x.org/. [Accessed: 30-Mar-2014].
  54. Arellano W, Mahgoub I (2013) “TrafficModeler extensions: A case for rapid VANET simulation using OMNET++, SUMO, and VEINS,” in 2013 10th International Conference on High Capacity Optical Networks and Enabling Technologies (HONET-CNS), Magosa, Turkey.
Citation: Mahgoub I, Arellano W (2014) Reverse Online Algorithm for the Dynamic Traffic Assignment inspired by Ant Colony Optimization for VANETs. Int J of Swarm Intel Evol Comput 3:111.

Copyright: © 2014 Mahgoub I, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
bellicon