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

Authors

  • Shambhavi Mishra Department of Civil Engineering, Indian Institute of Technology, Roorkee, Uttarakhand, India

DOI:

https://doi.org/10.3759/ttea.v3i3.2860

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.

References

Beni G, Wang J. Swarm Intelligence. In: Proceedings of the Seventh Annual Meeting of the Robotics Society of Japan. Tokyo: RSJ Press; 1989; 425–428p.

Dorigo M, Stutle T. Ant Colony Optimization. Cambridge, MA: MIT Press; 2004.

Deneubourg JL, Aron S, Goss S, et al. The Self-Organizing Exploratory Pattern of the Argentine Ant. Journal of Insect Behavior. 1990; 3: 159–168p.

Kristof Csorba, Balazs Todor. Ant Search on Large Maps to Find Wide Paths. Second IEEE International Conference on Intelligent Systems. 2004.

Shao-Han Liu, Jzau-Sheng Lin, Zi-Sheng Lin. A Shortest-Path Network Problem Using an Annealed Ant System Algorithm. Department of Computer Science and Information Engineering, National Chin-Yi Institute of Technology; 2005.

Yan Meng, Xiu Liu. Application of K-means Algorithm Based on Ant Clustering Algorithm in Macroscopic Planning of Highway Transportation Hub. Jinan, China: Department of Management and Economy, Shandong Normal University; 2007.

Van Zhang, Hao Wang, Yonghua Zhang, et al. BEST-WORST Ant System. 3rd International Conference on Advanced Computer Control, IEEE. 2011.

Majid Y, Farza D, Farhad R. Modification of the Elite Ant System in Order to Avoid Local Optimum Points in the Traveling Salesman Problem. Ithaca, New York: Cornell University; 2012.

Bullnheimer B, Kotsis G, Strauss C. Parallelization Strategies for the Ant System. In: De Leone R, Murli A, Pardalos P, et al., editors. High Performance Algorithms and Software in Nonlinear Optimization, Applied Optimization. Boston: Kluwer Academic Publishers; 1998; 87–100p.

Doerner KF, Hartl RF, Kiechle G, et al. Parallel Ant Systems for the Capacitated Vehicle Routing Problem. In: Evolutionary Computation in Combinatorial Optimization. Proceedings of the Lecture Notes in Computer Science. 2004; 3004: 72–83p.

Downloads

Published

2019-07-20

Issue

Vol. 3 No. 3 (2016)

Section

Articles

License

Declaration and Copyright Transfer Form

(to be completed by authors)

I/ We, the undersigned author(s) of the submitted manuscript, hereby declare, that the above manuscript which is submitted for publication in the STM Journals(s), is not published already in part or whole (except in the form of abstract) in any journal or magazine for private or public circulation, and, is not under consideration of publication elsewhere.

  • I/We will not withdraw the manuscript after 1 week of submission as I have read the Author Guidelines and will adhere to the guidelines.
  • I/We Author(s ) have niether given nor will give this manuscript elsewhere for publishing after submitting in STM Journal(s).
  • I/ We have read the original version of the manuscript and am/ are responsible for the thought contents embodied in it. The work dealt in the manuscript is my/ our own, and my/ our individual contribution to this work is significant enough to qualify for authorship.
  •  I/We also agree to the authorship of the article in the following order:

Author’s name                                    

 

1. ________________

2. ________________

3. ________________

4. ________________

 

We  Author(s) tick this box and would request you to consider it as our signature as we agree to the terms of this Copyright Notice, which will apply to this submission if and when it is published by this journal.