A Review: Application of Ant Algorithm in Transport Network Design Problems

Abstract

A dependable and reliable information source for transportation route planning and ready response to traveler demand, have become a hot topic of research these days. Transportation route planning, analysis and processing of traveler demand are among most important factors affecting response to traveler demand. Because of highly dynamic networks and frequent discontinuity, it is desirable to establish routes for fast delivery of people and goods, having a low probability of disconnection. Thus public transport network design problem is becoming one of the most important problems faced by bus operators and city authorities in the world. This problem belongs to the class of difficult combinatorial optimization problem, whose optimal solution is difficult to discover. When designing the network, the interests of both, the operator and the traveler must be taken into account. Opposing nature of these interests, make transport network design a multi criteria decision-making problem. While designing the transport network, the number of satisfied travelers is to be maximized, the total number of transfers, and the total travel time of travelers is to be minimized. The concept of agent-based modelling can be applied to these complicated problems. In this paper, we will discuss applications of ant algorithm in detail. Ant algorithm is a hybrid algorithm, mimicking the foraging behavior of social ants that can be used for route planning as well as route maintenance. Ants basically use pheromone as a chemical messenger in order to direct path to future ants foraging for food and the pheromone concentration can be treated as the indicator of quality solutions to a problem of interest. The visibility is a parameter that makes the probability of choosing nearer points higher than farther points. Ant-based algorithms are particularly suitable for discrete optimization problems. The pheromone controlling the passage of ants will evaporate over time. Without such time-dependent evaporation, ant algorithms will lead to early convergence to the local (often wrong) solutions. Ant algorithms can be used in solving public transit problems, vehicle routing and scheduling problems.