در آمدی بر الگوریتم های مسیریابی(دایجسترا، *A و . . .)

مسئله مسیریابی و انواع مختلف آن یک حوزه مطالعاتی مهم در صنعت حمل و نقل محسوب می گردد و با توجه به صفات وویژگی های مورد نظر آن از جمله مسائل بهینه سازی ترکیبی محسوب می گردد. لذا با شاخه های ریاضی، اقتصاد، علوم رایانه و تحقیق در عملیات و . . .  مرتبط می باشد.اصولا هدف از مسیریابی، طراحي و احداث يک مسير بين دو نقطه‌ی معلوم است. از طرف ديگر،در اتصال دو ناحيه با يک راه ارتباطي، انتخابهای فراواني بر اساس زمان، هزينه، فاصله، ايمني و . . . وجود دارد و از بين بيشمار انتخاب موجود در يک فضای راه حل بزرگ و شبکه پیچیده،(منظور از شبکه های پیچیده شبکه های پویا و بزرگ شامل میلیون ها گره و لینک می‌باشد)  بهينه‌ی آنها از هر سو بايد ملاک عمل قرار گيرد. بنابراین پیدا کردن نزدیک ترین در عین حال بهینه ترین فاصله بین دو نقطه و در کمترین زمان ممکن و با کمترین فاصله هنوز یکی از اصلی ترین مسائل جامعه علوم جغرافیایی محسوب می شود.

در این راستا برنامه ریزی مسیر برای مردم، وسایل نقلیه و . . . در میدان نامعلوم و خارج از شبکه جاده یا حالت تلفیقی با شبکه جاده نوع خاصی از مشکل برنامه ریزی مسیر است . در این راستا GIS پیشنهادات بهینه و تقریباٌ عالی در تلفیق با علوم دیگر در مواقع بحران دارد. که عملاً بهره وری لازم را نیز دارند. در بحران مردم عموماً اطلاعاتی در مورد اینکه کدام مسیر برای آنها بهینه ترین راه است را ندارند.از طرفی در شرایطی که بحران در آن رخ می دهد پیش بینی های دقیق و اقدامات پیشگیرانه با استفاده از مدل های فیزیکی و آماری به دلیل پیچیدگی فرآیند چالش برانگیز  است.  بنابراین در صورت وقوع بحران، مسئله مسیریابی پویا، تخلیه و اختصاص مردم مناطق مختلف به یک منطقه امن با توجه به نوع بحران مثلا پیشروی، جهت و سرعت سیل و سرعت وسایل و خودروهای در اختیار، در زمان های گوناگون ضروری می باشد. لذا مسیریابی با قابلیت پویا برای دفع بحران به وجود آمده مسئله مهم و بلاشک ضروری می باشد. به عبارت بهتر در زمان t   مسیر D مسیر بهینه و مناسب به منظور تخلیه و انتقال مردم و یا انتقال ایمن و درست مردم مستقر در منطقه A به منظور حرکت به منطقه امن B با عنایت به شاخص های مسیریابی مورد نظر کاربر و همچنین محل  و موقعیت قطعی و کنونی بحران مثلا ً سیل در زمان کنونی می باشد. امّا همین مسیر (مسیر D) احتمالاً در لحظه t+1 امن و ایمن برای حرکت به منطقه مورد نظر نباشد. بنابراین با توجه به تجربیات موجود حتی در سیل های اخیر مرداد ماه کشور به نظر می رسد مسئله مسیریابی پویا و بهینه و ایجاد مدلی پویا در شرایط بحران جز واجبات بحران ها می باشد.از طرفی امروزه با گسترش شبکه ها و سیستم ها و . . . مسئله مسیریابی در مقیاس بزرگ و در شرایط تقریبی عدم قطعیت و علی الخصوص میادین تقریباً نامعلوم به عنوان یک چالش برای شبکه های پیچیده مطرح می باشد. منظور از شبکه های پیچیده شبکه های پویا و بزرگ شامل میلیون ها گره و لینک می‌باشد. که علاوه بر این موارد خود عدم قطعیت موجود در بحران بر پیچیدگی و چالش برانگیز بودن مسئله مسیریابی در این نوع شبکه ها و در بحران می افزاید. (Sahhaf, et al., 2017) از طرفی نودها در شبکه های پیچیده به طور پیوسته دچار تغییر در مسیر عبوری از آنها می شوند که این خود نیاز به یک پروتکل مسیریابی که توانایی سازگاری با این تغییرات را داشته باشد نمایان می کند و همچنین مسئله امنیت مسیر نیز مدّ نظر بوده و از چالش های موجود در مسئله می‌باشد. (رحمتی, فرجی, احمدی جود, & طولابی, 1394) 

از طرفی همانطور که می دانیم هدف از بهینه سازی یافتن بهترین جواب قابل قبول، با توجه به محدودیت ها و نیازهای مسئله است بنابراین شناسایی محدودیت ها و نیازها در حل مسائل علی الخصوص بحران ها به صورت منظم، مداوم و دقیق بسیار ضروری می باشد برای مثال به منظور بررسی  یک بحران سیل واقعی برخی مواقع خود شبکه های جاده در صورت موجود بودن یک محدودیت مهم به شمار می آیند. بنابراین برای  يك مسئله، ممكن است جواب‌هاي مختلف و متفاوتی در زمان های مختلف وجود داشته باشد كه براي مقايسه آن‌ها و انتخاب جواب  بهينه، تابعي به نام تابع هدف تعريف مي‌شود. انتخاب اين تابع به طبيعت مسئله وابسته است به‌عنوان‌مثال، زمان سفر يا هزينه ازجمله اهداف رايج بهينه‌سازي شبكه‌هاي حمل‌ونقل و مسیریابی مي‌باشد. به‌هرحال، انتخاب تابع هدف مناسب يكي از مهم‌ترین گام‌هاي بهينه‌سازي است. ساده‌ترين راه در برخورد با این‌گونه مسائل، تشكيل يك تابع هدف جديد به‌صورت تركيب خطي توابع هدف اصلي است كه در اين تركيب ميزان اثرگذاري هر تابع با وزن اختصاص يافته به آن مشخص مي‌شود. لکن برخی مسائل مانند برنامه ریزی بهینه مسیر برای مردم و تخصیص مسیرهای بهینه به گروههای مختلف آنها در زمان های مختلف بحران سیل و با توجه به شرایط تقریباً غیر قطعی و نامشخص سیل به منظور برقرار نمودن مسیر درست و در امان ماندن از بحران سیل و . . . در میدان نامعلوم ، به عنوان مردم ، نوع خاصی از مشکل برنامه ریزی مسیر است و یا حتی تخصیص مصدومان احتمالی  به مراکز درمانی در شرایط به وجود آمدن بحران های سیل که در دسته مسائل تخصیص ظرفیت دار قرار می گیرند  و با افزایش تعداد نقاط تقاضا در مواقع بحران به پیچیدگی و حجم محاسبات مسئله به صورت نمایی افزوده می گردد. بنابراین در اینگونه مسائل نمی توان با یک تابع هدف خطی مسئله را حل نمود  (آقا محمّدی, 1392) در این راستا برخی از الگوریتم های موجود مانند الگوریتم های فراابتکاری به علت قرار نگرفتن در جواب های بهینه محلی و کاربرد آنها در مسائل مختلف شاید بیشتر از الگوریتم های ابتکاری  موثر و کارآ می باشند. امّا با توجه به ماهیّت مسئله (مسیریابی پویا و بهینه در بحران) و فاکتور فوق العاده با اهمیّت زمان به نظر می رسد این نوع الگوریتم ها در حال حاضر قادر به پیدا کردن جواب بهینه در زمان اندک مناسب نمی‌باشند. (حداد & عبدوس, 1399) در این راستا و باتوجه به زمان بر بودن این نوع الگوریتم ها و ثابت بودن فرآیند حل مسئله توسط آنها و همچنین در نظر گرفتن فضای کل مسئله در الگوریتم های قطعی مسیریابی، بنابراین به نظر می رسد ما بایستی به دنبال استفاده حداکثری، ابداع یا بهینه نمودن الگوریتم های ابتکاری در حل مسئله مسیریابی در بحرانی مثل سیل باشیم لذا برای درک بهتر موضوع و الگوریتم های مطرح شده و به منظور آشنایی با نقاط قوّت و ضعف آنها، برخی از این الگوریتم ها مورد بررسی قرار گرفته اند.

الگوریتم  قطعی دایجسترا :

الگوریتم دایجسترا در سال ۱۹۵۶، توسط دانشمند کامپیوتری با نام «ادسخر ویبه دیکسترا» (Edsger Wybe Dijkstra) مطرح و سه سال بعد، منتشر شد. الگوریتم دایجسترا دارای انواع گوناگونی است. الگوریتم اصلی، کوتاه‌ترین مسیر بین دو گره را پیدا می‌کند؛ اما نوع متداول‌تر این الگوریتم، یک گره یکتا را به عنوان گره مبدا (آغازین) در نظر می‌گیرد و کوتاه‌ترین مسیر از مبدا به دیگر گره‌ها در گراف را با ساختن درخت کوتاه‌ترین مسیر پیدا می‌کند. ( Jaliparthi Venkat, 2014)

الگوریتم دایجسترا یک الگوریتم حریصانه است در روش حریصانه، تقسیم مسأله ها به زیر مسأله ها انجام نمی‌گیرد و روش تكرارشونده را به كار می برند. در روش حریصانه در هر لحظه، با توجه به عناصر داده ای مفروض، عنصری را كه دارای ویژگی بهترین یا بهینه است (مانند كوتاه ترین مسیر، بالاترین ارزش، كمترین سرمایه گذاری، بیشترین سود و …) انتخاب می كنند در واقع در هر مرحله از الگوریتم، راسی پیدا می‌شود که در مجموعه راس‌های در نظر گرفته نشده قرار دارد و دارای کمترین فاصله از ریشه است. بدون این كه انتخاب های قبلی و ما بعدی را در نظر بگیرد ولی انتخاب های بهینه محلی همواره منجر به راه حل بهینه سراسری نمی شود برای مثال مطابق شکل

 برای حرکت از نود “آ” به نود “ح” در شکل 2 مرحله اول یال با ارزش 3 انتخاب می شود و مسیر به سمت نود “ب ” پیش می رود در مرحله بعد طول یال آ- ت برابر 7 و آ – ب – پ و آ – پ برابر 4 و طول یال آ-ب -ج برابر 8 می گردد بنابراین نود بعدی انتخاب شده نود “پ” می باشد و به همین ترتیب نود بعدی، نود “ت” می باشد . امّا برای انتخاب نود بعدی جمع ارزش ها در در نود آ-ب-ج  (عدد 8)کمتر از آ-ب-پ-ت -چ یا ث یا . . .  می باشد . بنابراین در این مرحله نود بعدی انتخاب شده بعد از نود “ت”، نود “ج” خواهد بود. همانطور که مشخص است یکی از معایب این الگوریتم سرعت پایین به علت جستجوی اضافی آن در گراف و بررسی همه نودها می باشد . (المدرسی, آزرده پاشائی, & یاوری, 1393) و البته در مورد طول یال های منفی نیز ناکارآمد می باشد(علّت کاملاً مشخص است هزینه و وزن هر یال باید مثبت باشد هزینه و وزن منفی برای یال در این نوع از الگوریتم بی معنی می باشد در واقع در الگوریتم دایجسترا فواصل به صورت تابع وزن دار از مجموعه یال ها به اعداد حقیقی ارائه می شوند).در مدل دایجسترا نهایتاً کوتاهترین مسیر به صورت برگشتی از آخرین نود به صورت بازگشتی از بیشترین مقدار تجمعی ارزش ها به طرف کمترین مقدار ارزش تجمعی (نقطه شروع با ارزش صفر) ادامه می یابد و یالهای عبوری مسیر را مشخص می کنند.

بنابراین تحقیقات مختلفی  الگویتم دایجسترا را بهبود و بهینه نموده اند و به مرور برخی از الگوریتم ها جای این الگوریتم مورد استفاده قرار گرفته اند یکی از راههای بهینه سازی الگوریتم دایجسترا در محدود کردن تعداد نودها می باشد که باعث می شود از پیچیدگی مسئله کاسته و بر عملکرد الگوریتم افزوده گردد. ( Wang & Pa, 2021)

الگوریتم قطعی RRT (Rapidly-exploring Random Tree) : الگوریتم درخت تصادفی با کاوش سریع از مفهوم شاخه ها استفاده می کند و از نقطه شروع با استفاده از نمونه برداری تدریجی و پوشش همه فضای مسئله گسترش می یابد و به طور مداوم درخت تصادفی را بدون برخورد با موانع گسترش داده تا زمانی که به نقطه هدف برسد از این الگوریتم می توان در محیط های چند بعدی استفاده کرد و از لحاظ محاسباتی کارآمد می باشد. امّا تعداد بالای نمونه گیری بهترین راه حل را ارائه نمی دهد و زمان بالایی برای یافتن مسیر با این الگو مورد نیاز است . ( A. Raheem & I. Hameed, 2018)

الگوریتم ابتکاری A* :

این الگوریتم تعمیمی از از الگوریتم دایجسترا می باشد الگوریتم A* اولین بار در سال 1968 به عنوان یک الگوریتم اکتشافی ارائه شد  رمز موفقیت الگوریتم A* نسبت به الگوریتم های جستجوی بیش از آن استفاده از تابع ابتکاری بوده است الگوریتم A* با معرفی تابع ابتکاری کارایی محاسباتی را تا حدی بهبود داده است استفاده از روش تابع ابتکاری باعث می شود تنها گره هایی از شبکه جستجو بررسی شوند که به نظر می رسد برای رسیدن به مقصد گزینه مناسب تری هستند هر چه تابع ابتکاری تخمین دقیق تری داشته باشد فاصله هر گره تا مقصد دقیق تر مشخص می شود. بنابراین تنها گره هایی که بر روی مسیر نهایی هستند بررسی خواهند شد در نتیجه تابع ابتکاری مناسب سبب افزایش سرعت الگوریتم می‌گردد پر واضح است که زمانی تابع ابتکاری تخمین صفر داشته باشد الگوریتم ای استار شبیه به الگوریتم دایجسترا عمل خواهد کرد و زمانیکه تابع ابتکاری برای تخمین هزینه از فاصله اقلیدسی استفاده می‌کند تنها گره هایی که هزینه کمتری تا مقصد ایجاد می کنند انتخاب می شوند به عبارتی اگر تابع ابتکاری تخمین حد بالا انجام دهد فضای جستجو به سمت گره مقصد هدایت می شود بنابراین تخمین حد بالا سبب بسط تعداد گره کمتری در فضای جستجو می شود البته اینکه مقدار حد بالا چه مقدار باشد خود مساله ای است که راه حل عمومی برای آن مطرح نشده است در نتیجه الگوریتم A* می تواند یک جستجوی سراسری را پیاده سازی کند و تمام گره های مسیر را شناسایی کند که این خود قابلیت الگوریتم را تضمین می کند. امّا تشخیص تعداد زیاد گره های مسیر خود منجر به کندی عملکرد می گردد. (ZENG, LU, LIU, & LIU, 2021)بنابراین یکی از راههای بهبود این الگوریتم پویاسازی آن و تغییر هزینه آرک ها در طول مسیریابی می باشد. در واقع در این الگوریتم تصمیم گیری حرکت از یک نود به نود دیگر وابسته است به هزینه حرکت از نود فعلی به نود بعدی بعلاوه هزینه تابع ابتکاری که مقدار هزینه حرکت از نود فعلی به مقصد(هدف) تخمین می زند. بنابراین این الگوریتم زمانی بهینه می شود که  هزینه رسیدن به هدف را بیش از اندازه واقعی برآورد نکند.

سایت جی آی ارث با داشتن سابقه انجام پروژه مسیریابی آماده مشاوره و یا انجام هرگونه پروژه در این زمینه با استفاده از تکنولوژی جی آی اس و تلفیق آن با فناوری اطلاعات می باشد.