Comparative study of ants colony algorithm and genetic algorithm for optimal routing ( Case study: Parsabad town and suburbs, Iran

Document Type : Scientific - Research

Authors

1 Assistant Professor, Department of Geography and Urban Planning, University of Zabol , Zabol, Iran

2 MSc. Department of Geography and Urban Planning, University of Zabol , Zabol, Iran

3 MSc Student, Department of Geography and Urban Planning, University of Zabol , Zabol, Iran

Abstract

 Promptness of relief groups and especially, of inter- cities ambulances has a vital role in their performance during unpredicted disasters. In this regard, optimal routing of these groups seems necessary in order to cover maximum population centers. For this purpose, the use of artificial intelligence and the so-called “new routing algorithms,” and its localization among inter/ intra- cities sections, based on their extent and spread, can be an efficient way for efficient urban management and relief organization. Therefore, the aim of this study was to show the practical application of ant colony algorithm for optimizing routing and minimizing the travelled distance.  Ultimately, to demonstrate the capabilities of this algorithm, it was compared with the genetic algorithm.  In this research, the case study was performed on over 29 urban and rural points, originated in Parsabad city, in MATLAB and shown in the GIS environment. The proposed model in this paper can not only be used to analyze the issue, but it also  can be used to optimize the routing of distribution of basic goods in cases of natural and human disasters, traffic problem, and so on. Need to note that in the proposed method, the Rolette wheel Selection method is used for random selection of the neighborhoods.The results showed that due to the limited area of the case study, time and quality of achieving to optimal route in ant colony algorithm were calculated 0.19 ms faster than the genetic theory, whereas, given the movement of 30 ants, the time required to arrive to the scene by the ambulances for ant colony algorithm and the genetic algorithm was calculated 19' 45'' and 24' 15'', respectively. 

Keywords


- امینی، بهنام و  اسرافیلی، حنا (1391) "بسط توابع زمان سفر- حجم برای راههای دو خطه دو طرفه برون شهری ایران" ، فصلنامه مهندسی حمل‌ونقل ، سال چهار، شماره 2، زمستان 91، ص 103-116.
- بهاالدینی، مهدی، منظوری، فرزاد (1386) "الگوریتم ژنتیک و کاربرد آن در حل مسایل "MILP"، سمینار مهندسی صنایع، 12ص.
- توکلی مقدم، رضا، علینقیان، رضا و سلامت بخش، رضا (1393) "مساله مسیریابی وسایط نقلیه دوره‌ای با پنجره زمانی در حالت رقابتی با روش شبیه‌سازی تبرید بهبودیافته"، فصلنامه مهندسی حمل‌ونقل، سال پنجم، شماره 4، تابستان 93، ص 449-470
- جوادی، محمد (1383) "الگوریتم ژنتیک"، انتشارات دانشگاه امام حسین، موسسه چاپ و انتشارات، 80ص.
- حسینی سمنانی، سمانه و زمانی فر، کامران (1387) "استفاده از الگوریتم Ant Colony در حل مسئله مسیریابی در شبکه‌های پویا"، پنجمین کنفرانس بین‌المللی مدیریت فناوری اطلاعات و ارتباطات، ص 3.
- ذوالفقاری، اکرم و کرکه آبادی، زینب (1392) "مسیریابی هوشمند اکیپ‌های امدادی با استفاده از الگوریتم تئوری بازی‌ها، نمونه موردی، شهر سمنان"،  فصلنامه مهندسی حمل‌ونقل، سال پنجم، شماره اول، ص 16-32
- رحمانی، پریسا، دادبخش مهدی و طرقی حقیقت، مهدی (1386) "توازن بار ترافیک شبکه و مسیریابی مبتنی بر مهندسی ترافیک با استفاده از کلونی مورچه‌ها"، اولین کنفرانس فازی و هوش مصنوعی، دانشگاه فردوسی مشهد، ایران، ص 4.
- سپهری، محمدمهدی (1392) "طراحی مدل استقرار مجدد آمبولانس‌های مکان یافته"، نشریه بین‌المللی مهندسی صنایع و مدیریت  تولید، شماره دوم، جلد 24، ص. 172-182.
- سلامی پور، اعظم، سلامی پور، علی و سلامی پور، مهدی (1387) "مسیریابی بهینه در شبکه‌های Ad Hoc  با استفاده از الگوریتم کلونی مورچه‌ها" ، یازدهمین کنفرانس دانشجویی مهندسی برق، دانشگاه زنجان، ص 2.
- قصیری، کیوان و مرشد سلوک، فهیمه (1384) "ارائه یک مدل ابتکاری مبتنی بر سیستم اجتماع مورچه‌ها برای حل مسئله زمان‌بندی حرکت قطار"، پژوهش‌نامه حمل‌ونقل، سال دوم، شماره چهارم، ص 14.
- مسعودی، شقایق، جوانشیر، حسن و توکلی مقدم، مهدی (1393) "حل مساله مسیریابی وسائط نقلیه ناهمگن چند قرارگاهی با پنجره زمانی توسط الگوریتم تکامل دیفرانسیلی چندهدفه: مطالعه موردی"، فصلنامه مهندسی حمل‌ونقل، سال ششم، شماره 2، زمستان 93، ص 325-340
- مولایی، ناصر (1387) "مسیریابی با استفاده از جی‌ای اس با تأکید بر مقایسه روش‌های وزن دهی و تلفیق لایه‌ها با الگوریتم‌های هوشمند"، انتشارات دانشگاه پیام نور بناب، ص 13-16.
- Dorigo, M. and Gambardella, L. M.  (1997) “Ant colony system: a cooperative learning approach to the traveling salesman problem”, IEEE Transaction on Evolutionary Computation, Vol.1, NO. 1, pp. 53-63.
- Dorigo, M., Caro, G. D. and Gambardella, L. M (1999) “Ants algorithms for discrete optimization”, Artificial Life, vol. 5, No. 3, pp. 137-172.
- Eksioglu, B., Vural, A. V. and Reisman, A. (2009) “The vehicle routing problem: A taxonomic review, Computers”, Industrial Engineering, NO. 57, pp. 1472-1483.
- Higgins, A. and Kozan, E. (1998) “Modeling train delays in urban networks”, Transportation Science, Vol. 32, No 4, pp. 346- 357.
- Malandraki, C. and  Daskin, M. (1992) “Time dependent vehicle routing problems”, formulations, properties, and heuristic algorithms, Transportation Science, No. 26, pp. 185-200.
- Shi, Liao, Hao, Jiu, Zhjou, Jiaqi and Xu, Guoyu (2004) “Ant colony optimization algorithm with random perturbation behavior to the problem of optimal unit commitment with probabilistic spinning reserve determination”, Elsevier Electric, Power Systems Research, No 69, pp. 295-303.
- Smsons, S. (2010) “Best routing fix it”, MKA University.
- Wang, Y. and Xie, J. (1999) “Ant colony optimization for multicast routing”, The 2000 IEEE Asian Pacific Conference on Circuits and Systems, IEEE APCC, as 2000,  pp. 54.57.
- Wood, A. J. and Wollenberg, B. F. (1996) “Power generation operation and control”, 2nd Ed. John Wiley and Sons, New York, 1996.