07-05-2014, 03:15 PM
Update Vehicle Traffic Routing Using Ant Colony Optimization Algorithm
Abstract
In this paper, the authors want to implement the solution of combinatorial problem, based on the heuristic behavior
of ant. This paper focuses on a highly developed solution procedure using ACO algorithm. This helps to solve
routing problems easily. It also reflects the method considering flow, distance, cost, and emergency etc. Here, a
new algorithm named UVTR (Update Vehicle Traffic Routing) is represented to overcome the complexity of the
previous algorithm. It yields the typical process for removing traffic problems in case of flow, distance, cost etc. This
formulation is represented with systematic rules based case study for the Dhaka City.
Introduction
Motivation
In billions years of evolution, many complex living systems arose. We can observe a variety of interesting
behaviors of plants and animals. In last decades many attempts were made to exploit these products of evolution
that are in fact soldiers in the natural optimization war. They are vehicles for carrying and reproduction of genes
and they are equipped with a bulk of abilities to solve everyday problems of the environment they populate.
One group of animals is very special among others in the way they live together with other individuals of the same
species. It’s a social insect such as ants. These small and relatively simple insects’ lives are so successful in the
fight for survival that the total weight of all these millimeter-sized creatures in the world is estimated to be same as
the weight of all living humans. They build armies and form specialized castes with various body structures and
scope of work, some species actually cultivate sponges and breed aphides and that can be seen as elemental
agriculture. All this without using a complex brain like people.
Objectives
The aim of this thesis is to Updating Vehicle Traffic Routing and dynamically control the traffic network equilibrium
such that traffic flow in the network is optimized. The authors introduce a novel Ant Traffic Control System
algorithm, derived from the existing class of Ant Colony Optimization (ACO) algorithms.
For transporting all car drivers without delay, the capacity of the highways is insufficient. Especially in the busy
times there are enormous traffic jams. Traffic jam occurs due to ecological, financial or political reasons; hence the
losses in time and money are excessive.
Related Work
The A* algorithm (Chabini and Lan 2002), which is widely used in vehicle navigation, is an improved version of the
Dijkstras algorithm. It makes use of an appropriate heuristic function to search the most promising nodes first
thereby reducing the computation time. To minimize the traveling time. The authors need a decentralized routing
algorithm which is able to adapt to the dynamic changes that take place in the traffic network.
Ants in Nature
Simply how ants can find shortest paths between food sources and their nest. The food foraging behavior of ants
gives food path, food source depending on the pheromone laid down by the ants when they come back from food
source. The ants choose the path based on pheromone from different paths. The other hunger ants informed of
food by previously visited ants. If the food at the food source is inadequate to satiate the ant’s hunger, the ant goes
in the direction of maximum food pheromone concentration without laying any food pheromone [3]. Soon, due to
evaporation of the food pheromone, the location of the exhausted food source is lost.
Ant as a single individual has a very limited effectiveness. But as a part of a well-organized colony, it becomes one
powerful agent, working for the development of the colony. The ant lives for the colony and exists only as a part of
it. Each ant is able to communicate, learn, cooperate, and all together they are capable of develop themselves and
colonies a large area. They manage such great successes by increasing the number of individuals and being
exceptionally well organized. The self organizing principles they are using allow a highly coordinated behavior of
the colony.
The Pheromones
Pheromones represent in some ways the common memory. The fact that it is external and not a part of the ants /
agents confers to it an easy access for everyone. The memory is saved in without regarding the configuration of
the ground, the number of ants, etc. It is totally independent, and still remains extremely simple. In our
implementation we will see that two different types of pheromones are used. The first one is represented in red and
is let by the ants which do not carry the food. We will call it the Away pheromone, as it means that the ant is going
away from the nest. Oppositely, the ants which carry the food to bring it back to the nest let a blue trace behind
them, the Back pheromone. Pheromones just proceed to one task: nature will take care of it in the real life,
although it is a simple process in algorithms [4]. In course of time, a global reduction of the pheromones by a
certain factor is applied, simulating the evaporation process. Thus the non-succeeding path will see their
concentration of pheromones reduced, although good solutions will stay full of pheromones as the ants keep using
it.
ACO based Traffic Control System
The authors developed the notion of a “virtual pheromone” inspired by the chemical markers used by ants and
termites for communication and coordination. It is implemented by messages relayed from central traffic control to
sensor. Virtual pheromones includes following properties: Without specifying a recipient, obviating the need for
unique identities that are impractical in large groups Pheromones are locally transmitted. The authors get essential
navigational clues from pheromone diffusion gradients. Pheromone evaporates with increasing time, decreasing for
error or garbage information. A pictorial representation of ant based traffic control system has been shown below
(Fig. 3.2). Central traffic control (CTC) is bi-directional communication in sensor and update road information
getting on CTC via traffic signaling element.
Conclusion
We have considered a perfect ant-based vehicles traffic routing algorithm to solve the traffic problem. In this paper
we also discussed the techniques of choosing road in busy hour. Getting up-to-date update traffic information in
particular vehicles. This model-based VTR algorithm was designed to solve the traffic network problem. We also
introduce four factor effecting function cost, distance, flow and Emergency which are value added parameter to
reducing traffic shortest path. The algorithm shows experimental result in vehicles traffic network (VTN) involving the
Dhaka City. The snap short indicated the assumption that the behavior modes seen in the UVTR
mathematical model still hold in a simulated environment since the routing is continuous. To recapitulate,
continuity routing m e a n s the colony is foraging on multiple sources, and node of 0 means the source has
converged on one distance to another. Although, f o r each step node check routing would be expected.
This is
attributed to noise in data a n d also because for certain e n v i r o n m e n t settings, many time steps to converge
on the best, in this case the closest, source. This evidence is further supported by Figs 6.1 to 6 . 1 5 where
the total step and (Figs 6.15) final state of routing and states for one (of the 16) simulations for values of node
for each cost value are calculated.