Font Size: a A A

Applying ANT Colony Optimization To Intelligent Traffic Control In Vehicular AD HOC Networks(anets)

Posted on:2016-11-06Degree:DoctorType:Dissertation
Country:ChinaCandidate:Jerry John KponyoFull Text:PDF
GTID:1108330473956123Subject:Information and Communication Engineering
Abstract/Summary:PDF Full Text Request
Continuing increasing vehicle population not only just makes the road network congested but degrades the joy of driving because it is too much for the road network and traffic control/management system – this is much worse in developing countries like China. The resulting congestion or even jam especially in rush hours brings just weary long queues and/or even traffic accidents instead of eagerly expected convenience.Current traffic control systems regulate traffic flows only by switching traffic lights according to historical data collected from cameras or underground coils. Such traffic controlling systems provide drivers no choice but to follow traffic light signaling and make decisions according to their local traffic status. Therefore; traffic flow status-prediction and routing services provided by Tom Tom, Google Maps and Bing Maps, etc. along the path to a predefined destination are highly preferred by the drivers. However, accuracy of such predictions is very low even during non-rush hours since the traffic data is not frequently updated, due to the dynamic nature of traffic which is affected by randomness of individual travel planning, driving behaviors, road network and weather conditions.Swarm intelligence such as Ant Colony Optimization(ACO) explores collective behavior formed by simple individuals interacting with each other by global pheromones in the network to optimize system performance using multi-agent strategy for example to find optimal configuration in Job-shop scheduling problem(JSP), Multi-depot vehicle routing problem(MDVRP), Vehicle routing problem with pick-up and delivery etc. Though such solutions have been very successful, they are mainly non-dynamic, since, in ACO terms, food supply’s locations do not change at least during the optimization phases. However, traffic control in a city aims to maximize traffic throughput in the network while minimizing the average waiting queue and each vehicle’s travel time to its destination. In practice, the optimization must be carried out in a distributed manner; therefore swarm intelligence approaches like ACO are more suitable for traffic control/management.This thesis models the traffic control problem as a multi-agent-multi-purpose system(MAMP) where: 1) traffic information is collected not only by the abovementioned sensors but mainly by the vehicles themselves, 2) traffic flow is regulated by not only the traffic-light-based signaling networks but mainly by the population of vehicles proactively in a distributive fashion by vehicles – namely, Distributed Intelligent Traffic System(DITS). In other words, in DITS, the vehicles sense their local traffic status and spread it to other regions as pheromones, and they make choices at intersections according to the local status and incoming pheromones especially along its previously calculated path. The main works of this thesis are as follows:Firstly, we implemented DITS in Net Logo and conducted experiments on two cases, one with ACO, the other without ACO to investigate impact of ACO on the solution to the traffic problem. For all the experiments, average speed(v-) and waiting time t-w of vehicles and average number n- of stopped vehicles are collected. The results have shown that for any initial distributions of vehicles, ACO-strategy obtains higherv-, smaller t-w and n- than non-ACO-strategy. This observation holds during the experiments and for all experiments with different traffic densities and different road network topologies.Secondly, we focus on optimization of path selection to the predefined destination for individual vehicles and propose a Dynamic Travel Path Optimization approach based on ACO(DTPOS+ACO). As comparison, we also design a similar algorithm without ACO(DTPOS-ACO) and the difference between them is that in DTPOS+ACO a vehicle calculates its selection probability at each intersection based on traffic loads and lengths of the candidate branches while in DTPOS-ACO the selection probability is calculated only according to branch lengths. Both approaches are implemented in Net Logo where each test vehicle starts from a predefined location and mixed into the background traffic flow to a predefined destination and their travel time is averaged over several experiments to obtain t-t under the same configuration. The results demonstrate that t-t in DTPOS+ACO is much shorter time than that in DTPOS-ACO.Thirdly, we propose a clustering algorithm for efficient traffic information delivery in DITS. When introducing swarm intelligence into DITS, traffic information delivery serving as pheromone distribution should be in a distributed fashion, therefore a vehicular ad hoc network(VANET) is preferred. In VANET, clustering of vehicles before information dissemination has been considered as an important step. Current clustering techniques suffer frequent cluster reshaping and thus cluster instability. To overcome these shortcomings, we propose an approach by introducing Minimum Spanning Tree(MST) to cluster vehicles on demand. The proposal ensures that the vehicles are clustered only on demand and may be dissolved when there is no information transmission. Several clustering schemes exist however, for clustering on demand implementation Kruskal’s algorithm; Prim algorithm and Dijkstra’s algorithm are the only Minimum Spanning Tree(MST) algorithms which are most appropriate. Kruskal cannot be used in this particular application because it does not perfectly support the random selection of cluster-heads in its implementation. A Prim MST Clustering algorithm has therefore been proposed. The proposed algorithm has been implemented in MATLAB and tested on traffic data from three locations in the United States. Ten snapshots were taken and at every snapshot the vehicles captured were clustered, taking the Qo S of intra-cluster communication into consideration. The algorithm has been found to perform well compared to Dijkstra’s algorithm.
Keywords/Search Tags:ITS, Vehicular ad hoc Networks, Ant Colony Optimization, Minimum Spanning Tree Algorithm
PDF Full Text Request
Related items