کاربرد الگوریتم اجتماع مورچه در مسیریابی بهینه گروه های امدادی بین شهری بین‌شهری

نوع مقاله : مقاله علمی پژوهشی

نویسنده

عضو هیئت علمی دانشگاه زابل

چکیده

سرعت عمل گروه‌های امدادی و در رأس آن‌ها آمبولانس‌های بین‌شهری نقش بسیار مهمی در کارایی آن‌ها در حین حوادث غیرمترقبه دارد. در این راستا مسیریابی بهینه این گروه‌ها به‌منظور پوشش بیشینه مراکز جمعیتی ضروری به نظر می‌رسد. بدین منظور استفاده از هوش مصنوعی و اصطلاح الگوریتم‌های مسیریابی نوین، و بومی‌سازی آن در بخش شهری و بین‌شهری با توجه به وسعت و گستردگی شهرها، می‌تواند در ساماندهی مدیریت شهری و امدادرسانی کارآمد باشد. بنابراین هدف این تحقیق استفاده کاربردی از الگوریتم اجتماع مورچه‌ها به‌منظور مسیریابی بهینه و کمینه‌سازی مسافت طی شده می‌باشد. در این تحقیق مطالعه موردی بر روی بالغ‌بر 29 نقطه شهری و روستایی به مرکزیت شهر پارس‌آباد در محیط متلب انجام‌گرفته و در محیط GIS نمایش داده‌شده است. مدل ارائه‌شده در این مقاله، علاوه بر مسئله موردبررسی می‌تواند به‌منظور مسیریابی بهینه توزیع کالاهای اساسی به هنگام وقوع بحران‌های طبیعی و انسانی، مسئله ترافیک و غیره مورداستفاده قرار گیرد. لازم به ذکر است که در الگوریتم پیشنهادی برای انتخاب تصادفی همسایگی‌ها از روش Rolette wheel Selection استفاده‌شده است. نتایج تحقیق نشان داد که با توجه به وسعت کم منطقه موردمطالعه، زمان و کیفیت دستیابی به مسیر بهینه در الگوریتم اجتماع مورچه با زمانی برابر با 0.19 میلی‌ثانیه بهینه تر از روش تجربی محاسبه شد. همچنین به دلیل وجود بانک داده های مکانی و اعمال آن در الگوریتم مورچه ها، زمان رسیدن به محل حادثه توسط آمبولانس‌ها نیز با فرض حرکت 30 مورچه، برای الگوریتم اجتماع مورچه‌ها وحالت تجربی به ترتیب 19 دقیقه و 45 ثانیه و 27 دقیقه و 15 ثانیه محاسبه شد.

کلیدواژه‌ها


عنوان مقاله [English]

Application of Ant Colony Algorithm in Optimal Routing of Inter- Cities Ambulances

چکیده [English]

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 .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 Experimental Method, whereas, given the movement of 30 ants, the time required to arrive to the scene by the ambulances for ant colony algorithm and the Experimental Method was calculated 19' 45'' and 27' 15'', respectively.

کلیدواژه‌ها [English]

  • Ant Colony Algorithm
  • Parsabad
  • Ambulance
  • routing
  1. حبیبی.، مجید. حسین کریمی. مصطفی عابدزاده. 1392. مدل‌سازی و حل مسئله مسیریابی وسیله نقلیه وابسته زمان با پنجره‌های زمانی نیمه نرم در گراف‌های چندگانه. پژوهشنامه حمل ‌و نقل، سال دهم، شماره 3، تهران.
  2. حسینی سمنانی، سمانه. کامران زمانی‌فر. 1387. استفاده از الگوریتم Ant Colony در حل مسئله مسیریابی در شبکه‌های پویا، پنجمین کنفرانس بین‌المللی مدیریت فناوری اطلاعات و ارتباطات.
  3. ذوالفقاری، اکرم. زینب کرکه­آبادی. 1391. مسیریابی هوشمند اکیپ‌های امدادی با استفاده از الگوریتم تئوری بازی‌ها (نمونه موردی شهر سمنان). فصلنامه مهندسی حمل ‌و نقل، سال پنجم، شماره 1، تهران.
  4. رحمانی، پریسا. مهدی دادبخش. مهدی طرقی‌حقیقت. 1386. توازن بار ترافیک شبکه و مسیریابی مبتنی بر مهندسی ترافیک با استفاده از کولونی مورچه‌ها. اولین کنفرانس فازی و هوش مصنوعی، دانشگاه فردوسی مشهد، ایران.
  5. سپهری، محمدمهدی. 1392. طراحی مدل استقرار مجدد آمبولانس‌های مکان یافته. نشریه بین‌المللی مهندسی صنایع و مدیریت تولید، شماره 24(2).
  6. سلامی پور، اعظم. علی سلامی­پور. مهدی سلامی­پور. 1387. مسیریابی بهینه در شبکه‌هایAd Hoc  با استفاده از الگوریتم کلونی مورچه‌ها، یازدهمین کنفرانس دانشجویی مهندسی برق، دانشگاه زنجان.
  7. قیصری، کیوان. فهیمه مرشد سلوک. 1384. ارائه یک مدل ابتکاری مبتنی بر سیستم اجتماع مورچه‌ها برای حل مسئله زمان‌بندی حرکت قطار. پژوهش‌‌نامه حمل‌ و نقل، سال دوم، شماره چهارم، تهران.
  8. مرادی، شمیم. 1384. الگوریتم کلونی مورچه‌ها و پیاده‌سازی یک کاربرد.  
  9. مرکز آمار ایران، 1390.

10. معصومی، زهره. ابوالقاسم صادق نیارکی. محمد مسگری. 1390. به‌کارگیری الگوریتم کلونی مورچه چند معیاره در سیستم‌های حمل‌ونقل هوشمند و کاربر مبنا. پژوهشنامه حمل‌ونقل، سال هشتم، شماره 1، تهران.

  1. مولایی، ناصر. 1387. مسیریابی با استفاده از جی‌ای اس با تأکید بر مقایسه روش‌های وزن دهی و تلفیق لایه‌ها با الگوریتم‌های هوشمند. دانشگاه پیام نور بناب

12. یوسفی، مجید. فرهاد رحمتی. 1390. یک الگوریتم بهبودیافته جمعیت مورچگان برای حل مسئله مسیریابی وسیله نقلیه همراه با دریافت و تحویل همزمان کالا. پژوهشنامه حمل‌ونقل، سال هشتم، شماره 2، تهران.

  1. Dorigo, Marco, Gambardella, Lusa, 1997. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transaction on Evolutionary Computation, 1:1, Milan.
  2. Dorigo, Marco, Caro, Gianni Di., Gambardella, Luca, 1991 Ants Algorithms for Discrete Optimization, Artificial Life , 5: 3, Bruxelles.
  3. Eksioglu, Burak, Vural, Arif. Volkan and Reisman, Arnold, 2009. The vehicle routing problem: A taxonomic review, Computers, Industrial Engineering, 57:2, Turkey.
  4. Higgins, Arnold, Kozan, Eran, 1998. Modeling train delays in urban networks, Transportation Science, 32:4, Newton.
  5. Malandraki, Chryssi, Daskin, Mark, 1992. Time dependent vehicle routing problems, formulations, properties, and heuristic algorithms, Transportation Science, 26: 3.
  6. Shil Haoj Zhou, Judy, 2004. Ant Colony Optimization Algorithm with Random Perturbation behavior to the  roblem of Optimal Unit Commitment with Probabilistic Spinning Reserve Determination, Elsevier Electric, Power Systems Research, 69 (2): 295-303.
  7. Smsons, S, 2010, best routing fix it, MKA University.
  8. Wang, Ying, Xie, Jianiling, 1999. Ant Colony Optimization for Multicast Routing, the 2000 IEEE Asian Pacific Conference on Circuits and Systems, IEEE Apcc as 2000, 12:1, Seul.
  9. wood, Adrian, wollenberg, Bruce, 1996. Power Generation Operation and Control, 2nd Ed. John Wiley and Sons, New York, 1996.