The International Arab Journal of Information Technology (IAJIT)

..............................
..............................
..............................


Using the Ant Colony Algorithm for Real-Time

#
  Transportation and distribution systems are improvi ng with an increasing pace with the help of current technological facilities and additionally, the comp lexity of those systems are increasing. Vehicle Rou ting Problems (VRPs) are difficult to solve with conventional techniques. Im proving routes used in distribution systems provide s significant savings in terms of time and costs. In this paper, current rou tes in school buses, which is a sub-branch of vehic le routing problems, are optimized using the Ant Colony Optimization (ACO), which is a heuristic artificial intelligence algorithm. Developed software is used for recommending the most suitable and the shortest route illustrated on a map by taking the instantaneous student wait locations online. Results of this study sugges t that the current routes can be improved by using the ACO. 


[1] Alayk ran K., and Engin O., Ant Colony Metaheuristic and an Application on Traveling Salesman Problem, J. Fac. Eng. Arch. Gazi Univ. , vol. 20, no. 1, pp. 69976, 2005.

[2] Bowerman R., Hall B., and Calamai P., A Multi9Objective Optimization Approach to Urban School Bus Routing: Formulation and Solution Method, Transportation Research Part A: Policy and Practice , vol. 29, no. 2, pp. 1079123, 1993.

[3] Br ysy O., A Reactive Variable Neighborhood Search for the Vehicle Routing Problem with Time Windows, INFORMS Journal on Computing , vol. 15, no. 4, pp. 3479368, 2003.

[4] Chin T., Abbou F., and Tat E., Simulation Study of a Heuristic Near9Maximum Ant9Based Dynamic Routing, The International Arab Journal of Information Technology , vol. 5, no. 3, pp. 2309233, 2008.

[5] Clarke G. and Wright J., Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operations Research , vol. 12, no. 4, pp. 5689581, 1964.

[6] Dorigo M. and Gambardella L., Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation , vol. 1, no. 1, pp. 53966, 1997.

[7] Ekin E., and Yakhno T., A Case Study of Adopting Ant System to Optimization Problems, the Tenth Turkish Symposium on Artificial Intelligence and Neural Networks, TAINN2001 , Gazimagusa, T.R.N.C., pp. 20925 2001.

[8] Garcia M., Montiel O., Castillo O., Sep lveda R., and Melin P., Path Planning for Autonomous Mobile Robot Navigation with Ant Colony Optimization and Fuzzy Cost Function Evaluation, Applied Soft Computing , vol. 9, no. 3, pp. 110291110, 2009.

[9] Gendreau M., Hertz A., and Laporte G., A Tabu Search Heuristic for the Vehicle Routing Problem, Management Science , vol. 40, no. 10, pp. 127691290, 1994.

[10] Ghafurian S. and Javadian N., An Ant Colony Algorithm for Solving Fixed Destination Multi9 Depot Multiple Traveling Salesmen Problems, Applied Soft Computing , vol. 11, no. 1, pp. 12569 1262, 2011.

[11] Kilby P., Prosser P., and Shaw P., Guided Local Search for the Vehicle Routing Problem, available at: http://citeseerx.ist.psu.edu/viewdoc/ download?doi=10.1.1.11.689&rep=rep1&type=p df, last visited 1999.

[12] Newton R. and Thomas W., Design of School Bus Routes by Computer, Socio-Economic Planning Sciences , vol. 3, no. 1, pp. 75985, 1969.

[13] Osman I., Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem, Annals of Operations Research , vol. 41, no. 4, pp. 4219451, 1993.

[14] Park J. and Kim B., The School Bus Routing Problem: A Review, European Journal of Operational Research , vol. 202, no. 2, pp. 3119 319, 2010.

[15] Reimann M., Doerner K., and Hartl R., D9ants: Savings based Ants Divide and Conquer the Vehicle Routing Problem, Computers and Operations Research , vol. 31, no. 4, pp. 5639591, 2004.

[16] Rizzoli A., Montemanni R., Lucibello E., and Gambardella L., Ant Colony Optimization for Real9World Vehicle Routing Problems, Swarm Intelligence , vol. 1, no. 2, pp. 1359151, 2007.

[17] Soyler H. and Keskinturk T., Global Ant Colony Optimization, J. Fac. Eng. Arch. Gazi Univ. , vol. 21, no. 4, pp. 6899698, 2006.

[18] Taillard ., Badeau P., Gendreau M., Guertin F., and Potvin J., A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows, Transportation Science , vol. 31, no. 2, pp. 1709186, 1997.

[19] Van Breedam A., An Analysis of the Effect of Local Improvement Operators in Genetic Algorithms and Simulated Annealing for the Vehicle Routing Problem, RUCA Working Paper 96/14 , University of Antwerp, Belgium, 1996. Using the Ant Colony Algorithm for Real-Time Automatic Route of School Buses 565 Tuncay Yigit received his BS, MS and PhD degrees from the University of Gazi in Turkey, in 1997, 2000 and 2005. Since 2007, he is working as a professor in the Department of Computer Engineering, University of S leyman Demirel. He is interested in artificial intelligence, optimization, distance education, sof tware technologies and computer systems. Ozkan Unsal received his BS and MS degrees from the University of Gazi in Turkey, in 2008 and 2011. He is currently pursuing his PhD degree in the Department of Computer Engineering, University of S leyman Demirel. He is interested in machine learning, artificial intellig ence, optimization and software technologies.