مروری بر روشهای مسیریابی قطعی و ابتکاری مورد استفاده در GIS

هر سال ترافیک راههاي شهري افزايش مييابد و تقريباً همهي افراد ساعاتي از زمان خود را در ترافیک از دست دادهاند. بديهي است که اين مشکل هم به لحاظ اقتصادي و هم به لحاظ سلامت جسمي و رواني به جامعه ضربه میزند. يکي از ابزارهايي که در سیستم اطلاعات مکاني 1 ، ميتواند هم از تشکیل ترافیکهاي طولاني و هم از گیرافتادن در ترافیک جلوگیري کند، استفاده از الگوريتمهاي بهینه در بخش مسیريابي است.
الگوريتمهاي مسیريابي، الگوريتمهايي هستند که بین دو يا چند نقطه، بهترين يا کم هزينهترين مسیر را مشخص مينمايند. اين هزينه ميتواند مسافت، زمان سفر، علاقهمندي، ترافیک و بسیاري پارامترهاي ديگر باشد. معمولاً در اين مسائل، ابتدا شبکهي راه بهصورت گرافي وزندار مدل ميشود. گراف در حقیقت مدلي رياضي است که ترکیبي از گره و لینک است و ميتواند روابط را مدل کند. در مرحله بعدي بايد وزن لینکها تعیین شود.
همانطور که گفته شد، وزني که به گراف نسبت داده ميشود ميتواند بسته به معیارها، متفاوت باشد. پس از تعیین وزن لینکها الگوريتم مسیريابي بر روي گراف اجرا ميشود.
گاهي به دلیل استفاده از فناوريهاي جديد، کاربر با جريان دادهها مواجه است. در اين مواقع، وزني که به لینکهاي گراف نسبت دادهشده قابلیت تغییر در زمان را دارد و کاربر با گرافي پويا مواجه خواهد بود. براي مسیريابي روي اين گرافها نميتوان از الگوريتمهاي ايستا که در گذشته رايج بودند، استفاده کرد، زيرا هزينههاي گراف دائماً در حال تغییر است. به همین دلیل از الگوريتمهاي پويا استفاده ميشود. نمونهاي از چند الگوريتم پويا نیز در قسمتهاي مختلف ذکر شدهاند.
الگوريتمهاي مسیريابي بررسي شده در اين مقاله در 2 دستهي الگوريتمهاي قطعي و الگوريتمهاي ابتکاري دستهبندي ميشوند. ابتدا الگوريتمهاي مسیريابي قطعي و سپس الگوريتمهاي مسیريابي ابتکاري بررسي ميشوند. در نهايت در قسمت نتیجه گیري، الگوريتمها با يکديگر مقايسه ميشوند.

الگوریتمهای قطعی

روند ثابتي براي اکثر الگوريتمهاي کوتاهترين مسیر وجود دارد. قبل از پرداختن به اين منظور بايد با چند اصطلاح آشنا شد. منظور از برچسب در اين مقاله عددي است که به هر گره i نسبت داده ميشود و هزينهي حرکت از گره مبدأ به گره مورد نظر i است و با Li نمايش داده ميشود. Pi لیستي است که در آن ترتیب لینکهاي کوتاهترين مسیر تا گره i مشخص شده است. Q هم مجموعهاي از گرههاي واجد شرايطي است که بايد مورد بررسي قرار بگیرند. حال روند الگوريتمهاي کوتاهترين :) مسیر به اين شکل است

1 2 الگوریتمهای تعیین برچسب - - LS

Dijkstra

1 2 2 الگوریتم - - - Bellman-Ford

2 2 2 الگوریتم - - - Floyd-Warshll

2 2 الگوریتمهای تصحیح برچسب - - LC

3 2 2 الگوریتم - - - Johnson

3 الگوریتمهای ابتکاری -

1 3 محدود کردن منطقه جستجو - -

1 1 3 روش هرس کردن شاخه - - -

2 1 3 روش - - - A*

- - - - 1 2 1 3 *A پویا 1 ( *D )

- - - - 2 2 1 3 Anytime D*

2 3 تجزیه مسئلهی جستجو - - 1

1 2 3 روش جستجوی دو جهته - - - 2

2 2 3 روش هدف فرعی - - -

3 3 محدود کردن لینکهای جستجو شده - -

1 3 3 روش جستجوی سلسله مراتبی - - -

2 3 3 روش جستجوی برد مبنا - - - 1

3 3 3 روش استفاده از میانبر - - - 1

4 مقایسه الگوریتمهای قطعی و ابتکاری -

5 مسائل پیچیده و پیشرفته در مسیریابی -