مسیرهای ارتباطی

مسیرهای ارتباطی

محدودیتی برای تعداد گرههای منبع و مقصد وجود ندارد.
این ساختار ماتریس ارتباط داخلی به صورت ایدهآلی برای الگوریتم جستجوی مسیر بحث شده در بخش 4 مناسب است.
3-2-2- عملیات اولیه ریاضی
با داشتن یک شبکه گرهای، فرض میکنیم که و به ترتیب نشاندهنده گرههای منبع و مقصد هستند. آنگاه امین مسیر بین گرههای منبع و مقصد برای گراف مستقیم گرهای به صورت زیر تعریف میشود:
که در آن ، و تعداد مسیرها است.
براساس رابطه (3-1)، ممکن است یک شکاف بنیادی تعریف شود. یک برش بنیادی به عنوان برشی تعریف میشود که گراف را دقیقاً به دو قسمت تقسیم میکند. در اینصورت، مجموعه
همه گرههای برش اولین مرتبه را در شبکه نشان میدهد. معادله (3-2) شامل گرههای متصل شبکه است ]52[. معادله (3-1) و (3-2) یک اساسی را برای تعریف برش دومین و سومین و مرتبههای بالاتر، تهیه میکند. برش دومین مرتبه توسط شبیهسازی برداشتن دو گرهای در شبکه که گراف را به دو بخش مجزا تقسیم میکند، تعیین میشود. با استفاده از معادله (3-1) و (3-2) مجموعه جفت مرتب گرهها برای برش دومین مرتبه میتواند به صورت زیر تعریف شود:

که در آن مجموعه مسیرهای و برابر با همه مسیرهایی است که به ترتیب شامل گرههای و است. با گسترش معادله (3-3) برای برش بیشتر از دو مرتبه میتواند به صورت زیر تعریف شود:
3-2-3- الگوریتم کوتاهترین مسیر
الگوریتم کوتاهترین مسیر تنها نیازمند اجزای قدیمی به عنوان یک داده ورودی میباشد. به همین خاطر (تکنیک داده ورودی سابق) نامیده میشود. الگوریتم جستجوی مسیر در ماتریس اتصال داخلی عمل میکند، و 2 روش که جستجو و مبادله نامیده میشود، را برای استنباط تمام حداقل مسیرها بکار میبرد. فرآیند جستجو از طریق ماتریس اتصال داخلی برای پیدا کردن دومین جزء در مسیر جاری اقدام میکند. اگر این جزء یک منبع باشد، فرآیند جستجو متوقف میشود و تمامی مسیرهای کامل شده در ماتریس مسیر را ذخیره میکند و فرآیند مبادله شروع به اجرا در شاخه جاری میکند. برای اجرایی کردن تمامی کوتاهترین مسیر موجود بین گرههای منبع و مقصد خاص، فرآیند گام به گام برای الگوریتم مطابق زیر است:
قدم 0: شناسایی مسیر جاری، برای .
قدم1: یک گره مقصد جدید انتخاب کنید و آنرا گرهی جاری قرار دهید. هر وقت یک گره جاری شد، میتواند در ماتریس مسیر بعنوان بخشی از مسیر جاری ذخیره شود.
قدم2: تعداد اجزایی که قبل از گره جاری است، را چک کنید. اگر صفر باشد، گرهی منبع افزایش مییابد و مسیر کامل میشود؛ مسیر را به 1 افزایش دهیم و به قدم 3 بروید، در غیر اینصورت ادامه دهید.
اگر تعداد اجزا که به آن گفته میشود، قبل از گره جاری برابر 1 باشد، یعنی باشد، این گره جاری را به عنوان گره شاخه انتخاب و را ذخیره میکنید؛ در غیر اینصورت را به عنوان گرهی جاری انتخاب کنید و به قدم 2 بروید. اولین جزء را انتخاب کنید و آنرا گره جاری بنامید و به قدم 2 بروید.
قدم 3: تعداد گرههای شاخهی باقیمانده را چک کنید. اگر صفر باشد، تمامی مسیرهای در گرهی مبدا جاری پایان یافتهی اجرایی شده است، به مرحله 5 بروید، در غیر اینصورت به گام 4 بروید.
قدم 4: یک گره شاخهی با تعداد پیشنیاز برابر انتخاب کنید و بصورت زیر عمل کنید:
اجزا را در امین سطر به طوری جانشین کنید که هر جزء در مکان فقط یکبار ظاهر شود. بعد از هر عملیات جانشین کردن به قدم 2 بروید. مبادله را در دفعه انجام دهید. تعداد گرههای شاخهزده باقیمانده را یکی کم کنید.
قدم 5: تعداد گرههای مقصد باقیمانده را چک کنید؛ اگر صفر باشد، متوقف شود تا وقتی که تمامی مسیرها در شبکه پیدا شوند، در غیر اینصورت به گام 1 بروید. یک نمودار برای الگوریتم کوتاهترین مسیر در شکل 3-2 توضیح داده شده است.
شکل 3-2. نمودار الگوریتم حداقل مسیر]2[
الغنیم [2] یک زمان تقریبا خطی را برای تعدادی از شبکه گرهها نشان داد و برای یک شبکه با 101 گره، که شامل 10 گره شاخهای بود، زمان محاسباتی هر مسیر 518/0 ثانیه را در نظر گرفته است (بر روی یک کامپیوتر با قدرت 486 اجرا شد). کوبایشی و یاماموتو [53] نشان دادند که همه کوتاهترین مسیرها برای یک مساله تصادفی با 30 گره و 100 کمان بیشتر از 1300 ثانیه نمیباشد. البته باید به این نکته نیز توجه داشت که در این تحقیق علاوه بر کوتاهترین مسیر، امین کوتاهترین مسیر نیز محاسبه میشود که برای این کار بعد از محاسبه کوتاهترین مسیر توسط الگوریتمهای ذکر شده در بالا، با حذف این کوتاهترین مسیر، اولویت بعدی کوتاهترین مسیر محاسبه میشود.
3-3- مدل تعیین سیاست بهینه در سناریو دوم
در سناریو دوم که مربوط به بعد از حادثه است، به بررسی شرایط مسیرهای ارتباطی بعد از وقوع حادثه پرداخته و بررسی میکنیم که با توجه به مرکز و شدت حادثه بهترین تصمیم برای تعمیر یا انتقال با تجهیزات پیشرفته و هزینه بیشتر و یا جایگزینی مسیر با توجه به مینیمم کردن هزینه و زمان چه تصمیمی خواهد بود. برای مثال، زلزله با قدرت 5/5 ریشتر در منطقه زیر رخ داده است که تسهیلات کمکرسانی با دایره و نقاط تقاضا با ستاره و مسیرهای ارتباطی با خط نشان داده شدهاند. مرکز و ریشتر زلزله نیز در شکل مشخص شده است. حال با دایرههای خطچین شعاعهایی که نشاندهنده تاثیر حادثه است، مشخص میشود. با مشخص کردن مسافتی از مسیرها که در این دوایر قرار میگیرد میزان تخریب مسیرهای ارتباطی تعیین شده و بهترین تصمیم با توجه به مینیمم هزینه و زمان تعیین میشود.

Share