تحليل و ارزيابي روش‌هاي فراابتكاري، ابتكاري و قطعي در ارايه مسير بهينه براي شبكه‌هاي كوچك، متوسط و بزرگ

Analysis and evaluation of metaheuristic, heuristic, and deterministic methods in providing an optimal path for small, medium, and large networks

مسيريابي بهينه يكي از پركاربردترين مسايل شبكه در برنامه‌ريزي حمل و نقل است و هدف از آن يافتن كوتاهترين مسير از ميان مسيرهاي موجود است. مسئله كوتاهترين مسير روي يافتن مسير با كمترين فاصله، زمان يا هزينه از گره منبع به گره مقصد تمركز دارد. از جهت ديگر زمان انجام اين پردازش در كاربردهاي مربوط به حمل و نقل هوشمند و كاربر مبنا اهميت زيادي مي‌يابد. براي انجام مسيريابي از الگوريتمهاي قطعي و ابتكاري مختلفي استفاده مي‌شود. يكي از اين الگوريتمها، الگوريتم فراابتكاري بهينه سازي كلوني مورچه است كه از رفتار جمع آوري آذوقه مورچه‌ها الهام گرفته شده است و به ذات به مسئله مسيريابي از لانه تا آذوقه مي‌پردازد و در مقاله حاضر نتايج آن با دو الگوريتم ديگر يعني ژنتيك و دايكسترا مقايسه مي‌شود. الگوريتم ژنتيك يك الگوريتم فراابتكاري مي‌باشد و در مقابل آن دايكسترا الگوريتمي قطعي است. هر سه الگوريتم روي سه شبكه كوچك با 200 گره، متوسط با 1000 گروه و بزرگ با 2000 گره بررسي شدند. با بررسي نتايج مشخص شد كه الگوريتم كلوني مورچه‌ها در شبكه‌هاي بزرگا نتايج بهتري مي‌دهد. زمان محاسباتي الگوريتم فراابتكاري كلوني مورچگان نزديك به زمان محاسباتي الگوريتم ژنتيك است اما دقت بيشتري داشته و دقت محاسبات آن همانند روش الگوريتم قطعي دايكسترا است.

Optimal routing is one of the most widely used network issues in transportation planning and aims to find the shortest route among the available routes. Shortest Path Problem Focuses on finding the path with the least distance, time, or cost from source node to destination node. On the other hand, this processing time is very important in applications related to intelligent and user-based transportation. Various deterministic and innovative algorithms are used to perform routing. One of these algorithms is the ant colloquial ant colony optimization algorithm, which is inspired by the ant feeding behavior of ants and deals with the issue of routing from nest to feed, and in the present article, its results with two other algorithms, namely genetics. an‎d Dijkstra is compared. Genetic algorithm is a meta-heuristic algorithm and Dijkstra is a definite algorithm. All three algorithms were tested on three small networks with 200 nodes, medium with 1000 nodes and large with 2000 nodes. Examination of the results showed that the ant colony algorithm gives better results in large networks. The computational time of the ant colony algorithm algorithm is close to the computational time of the genetic algorithm, but it is more accurate and its computational accuracy is the same as the Diextra definitive algorithm method.