Sudip Kumar Sahana; Aruna Jain; Prabhat Kumar Mahanti

Ant Colony Optimization for Train Scheduling: An Analysis

Full Text (PDF, 560KB), PP.29-36

Views: 0 Downloads: 0

Author(s)

Sudip Kumar Sahana ^1,* Aruna Jain ² Prabhat Kumar Mahanti ³

1. Department of Computer Science and Engineering, Birla Institute of Technology, Mesra, Ranchi, India

2. Department of Information Technology, Birla Institute of Technology, Mesra, Ranchi, India

3. Department of Computer Science & Applied Statistics, University of New Brunswick, Canada

* Corresponding author.

DOI: https://doi.org/10.5815/ijisa.2014.02.04

Received: 4 May 2013 / Revised: 20 Sep. 2013 / Accepted: 15 Nov. 2013 / Published: 8 Jan. 2014

Index Terms

Ant Colony Optimization, Train Scheduling Problem, Pheromone, State Transition Rule, Local Pheromone Update Rule, Global Pheromone Update Rule

Abstract

This paper deals on cargo train scheduling between source station and destination station in Indian railways scenario. It uses Ant Colony Optimization (ACO) technique which is based on ant’s food finding behavior. Iteration wise convergence process and the convergence time for the algorithm are studied and analyzed. Finally, the run time analysis of Ant Colony Optimization Train Scheduling (ACOTS) and Standard Train Scheduling (STS) algorithm has been performed.

Cite This Paper

Sudip Kumar Sahana, Aruna Jain, Prabhat Kumar Mahanti, "Ant Colony Optimization for Train Scheduling: An Analysis", International Journal of Intelligent Systems and Applications(IJISA), vol.6, no.2, pp.29-36, 2014. DOI:10.5815/ijisa.2014.02.04

Reference

[1]Bell J.E., McMullen PR. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Information 2004; 18 (2004):41–48.

[2]Bullnheimer B, Hartl RF, Strauss C. An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research 1999; 89 (1999), 319–328.

[3]Dorigo M, Maniezzo V, Colorni A. The ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics - Part B: Cybernetics 1996; 26(1): 29–41.

[4]Sahana, S.K., Jain, A. An Improved Modular Hybrid Ant Colony Approach for Solving Traveling Salesman Problem, International Journal on Computing (JoC) 2011;1(2) :23-127 , ISSN: 2010-2283,doi: 10.5176-2010-2283_1.249.

[5]Sahana,S,K., Al-Fayoumi,M., Jain,A Mahanti,P.K. Solution of Traveling Salesman Problem Using Hybrid Ant Colony Algorithm, Advances in Information Technology and Applied Computing (ISSN 2251-3418) 2012; 1: 11-16, ISSN 2251-3418.

[6]Colorni A, Dorigo M, Maniezzo V, Trubian M. Ant system for job-shop scheduling. JORBEL - Belgian Journal of Operations Research Statistics and Computer Science 1994; 34(1): 39–53.

[7]Maier HR, Simpson AR, Zecchin AC, Foong W.K, Phang KY, Seah HY, Tan CL. Ant colony optimization for design of water distribution systems. Journal of Water Resources Planning and Management 2003; 129(3):200–209.

[8]Gambardella LM, Mastrolilli M, Rizzoli AE, Zaffalon M. An integrated approach to the optimization of an intermodal terminal based on efficient resource allocation and scheduling. Journal of Intelligent Manufacturing 2001; 12(5/6):521–534.

[9]Mathur,V.N., Operating manual for Indian Railways, http://www.indianrailways.gov.in/ railway-board/ uploads/ codesmanual/ operating%20manual-traffic.pdf

[10]Narayan Rangaraj. A note on section scheduling on the IndianRailways, http://www.me.iitb.ac.in/~narayan/note-on-section-scheduling.pdf.

[11]Cai X, Goh CH. A fast heuristic for the train scheduling problem. Computers and Operation Research 1994;21(5): 499–510.

[12]Khairnar, H.S., Mengale, S.P , Khairnar, C.H. A decision support system for scheduling a new train in Indian Railway network, 1109/IAMA.2009.5228047 Intelligent Agent & Multi-Agent Systems, 2009. IAMA 2009. p.1-6.

[13]Ghoseiri K, Morshedsolouk F. Train scheduling using ant colony system. Journal of applied mathematics and decision science. 2006; 2006:1-28.

[14]Reimann M and Leal,J.E. Single line train Scheduling with ACO,13th European Conference EvoCOP 2013, Vienna, 2013. , LNCS 7832, pp226-337.

[15]Dollevoet, T., Huisman, D., Schobel, A. and Schmidt, M., 2012. Delay Management including Capacities of Stations,2012, Econometric Institute Report EI 2012-22, Erasmus University Rotterdam, Econometric Institute.

[16]Dollevoet, T. and Huisman, D. Fast Heuristics for Delay Management with Passenger Rerouting, 2011, Econometric Institute Report EI 2011-35, Erasmus University Rotterdam, Econometric Institute.

[17]Bonabeau E, Dorigo M, Theraulaz G. Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York, 1999.

[18]Dorigo M, Birattari M, Stutzle T. Ant Colony Optimization, Iridia technical report series, Report no. TR/IRIDIA/2006, p. 1-23.

[19]Dorigo M, Birattari M, Stutzle T. Ant Colony Optimization. IEEE computational intelligence magazine, November 2006:143-159.

[20]Dorigo M, Stutzle T. Ant Colony Optimization. Mit: Mit Press; 2006.

International Journal of Intelligent Systems and Applications (IJISA)