تعيين مسيرهاي بهينه شبكه اتوبوس شهري با استفاده از يك الگوريتم فراابتكاري

Optimal route network design for urban buses using a metaheuristic algorithm

مسأله‌ي مسيريابي شبكهي حمل‌ونقل همگاني يك مسأله‌ي NP-hard است كه به ساخت شبكه‌ي مسيرهاي حمل‌ونقل همگاني با توجه به قيدهاي چندگانهي موجود براي شبكه مي‌پردازد. موضوع چالش‌برانگيز در اين مسأله وجود فضاي جستجوي گستردهي آن و مجموعه مسيرهايي در شبكه است كه به دليل برآورده نكردن شرايط محدوديت‌هاي مسأله به عنوان جوابي غيرقابل‌قبول و ناممكن تلقي ميشوند. ذات اين مسأله به گونهاي است كه با افزايش ابعاد آن زمان حل محاسبات بسيار افزايش مييابد از اين رو الگوريتمهاي فراابتكاري روش حلي مناسب محسوب ميشوند. در اين مطالعه با دو هدف كاهش مجموع زمان سفر مسافران و مجموع تعداد انتقالها براي كل تقاضاي شبكه به پيدا كردن مسيرهاي بهينه در شبكه پرداخته شد. به منظور حل مسأله، از الگوريتم جستجوي فاخته بر روي شبكه‌ي مندل استفاده و به پيدا كردن مجموعه‌ي مسيرهاي بهينه در شرايط مختلف پرداخته شد. نتايج به دست آمده در اين مطالعه با نتايج مشابه در مطالعات پيشين با استفاده از مجموعه‌اي از پارامترها مورد بررسي و مقايسه قرار گرفتند. نتيجه‌ي اين مقايسه حاكي از كارايي مناسب روش اين الگوريتم در حل مسألهي مسيريابي شبكهي حملونقل همگاني بود.

Urban Transit Routing Problem (UTRP) is a NP-hard problem in which the routes of the public transportation network are determined by considering operational constraints. It is necessary for these routes to improve the efficiency of the network from passengers’ perspective while minimizing the operator cost. In this study, UTRP was solved by Cuckoo search algorithm. Results were compared on the basis of Mandl’s network as an accepted benchmark network in the relevant literature. This comparison showed that the cuckoo search algorithm had a good performance in finding the routes of the public transportation network regarding the objectives considered in this study.