بخشی از مقاله
چکیده:
مساله کوتاهترین مسیر با هزینه های فازی یکی از رایج ترین مسائل در زمینه سیستم ها و مجموعه های فازی است که در این مقاله با استفاده از تعمیم الگوریتم کلاسیک فورد - مور - بلمن در محیط نامعین، به حل این گونه مسائل خواهیم پرداخت. در این نوع مسائل دو موضوع کلیدی یعنی چگونگی تعیین کردن مجموع دو یال و همچنین مقایسه فاصله بین دو مسیر که اعداد فازی هستند، باید مورد بررسی قرار گیرد که در این مقاله برای مقایسه اعداد فازی از شاخص های رتبه بندی ارائه شده توسط کافمن و گوپتا استفاده می کنیم. مثال های عددی حل شده بوسیله روش پیشنهادی با بکارگیری این شاخص رتبه بندی و همچنین مقایسه آن با الگوریتم مشابه در کار هرناندز و همکاران ، تاثیر و کارایی این روش را به خوبی آشکار می سازد.
مقدمه
مساله یافتن کوتاهترین مسیر از یک گره معین به گره های دیگر از موضوعات اساسی در نظریه گراف و یکی از رایج ترین مطالعات فعلی در زمینه سیستم ها و مجموعه های فازی است.[1-7] این مساله کاربردهای بسیاری در حوزه حمل و نقل، مسیریابی، ارتباطات ، مدیریت زنجیره تامین، و غیره دارد.فاصله - هزینه - یک مسیر، مجموع وزن یال های روی مسیر است و از آنجایی که در یک گراف بین هر دو راس می تواند بیشتر از یک مسیر وجود داشته باشد لذا مساله یافتن یک مسیر با کمترین هزینه بین دو راس معین مطرح می شود که مساله کوتاهترین مسیر - 1 - SPP نامیده می شود.
اما در شبکه های دنیای واقعی، معمولا پارامترهای شبکه مثل هزینه، ظرفیت، تقاضا، زمان و غیره، مقادیری دقیق نیستند و از آنجا که نظریه مجموعه های فازی توانایی بکارگیری اطلاعات مبهم را فراهم می آورد، لذا اعداد فازی[4,8] برای مدلبندی چنین مسائلی مناسب هستند و بحث مساله کوتاهترین مسیر فازی - 2 - FSPP مطرح می شود. در FSPP ، مسائل شامل اعمال محاسباتی و مقایسه بین اعداد فازی - بویژه اعداد فازی مثلثی - هستند در نتیجه این مساله مشکل تر از SPP معمولی است که در آن تنها اعداد حقیقی را داریم . درFSPP هزینه های نهایی اعداد فازی هستند و آنچه که یافتن مسیر کوتاهتر از بقیه مسیرها را دشوار می سازد مقایسه بین اعداد فازی است که این عمل می تواند به روش های مختلفی تعریف گردد.
مقالات زیادی در مورد FSPP منتشر شده است[5,6,9-16] که در آن از الگوریتم های مختلفی با بکارگیری شاخص های رتبه بندی متعدد برای حل این گونه مسائل استفاده شده است. از جمله این کارها می توان به مقاله هرناندز و همکاران[17] اشاره کرد که در آن از تعمیم الگوریتم کلاسیک فورد - مور- بلمن - 3 - FMB برای حل مسائل FSPP استفاده شده است و برای مقایسه اعداد فازی از یک شاخص رتبه بندی کلی استفاده شده است که تصمیم گیرنده می تواند برحسب نیاز از شاخص های رتبه بندی مختلف استفاده نماید.
اما نتایج بدست آمده نقص و ناکارآمد بودن تمامی شاخص های رتبه بندی بکار گرفته شده در این کار را برای بدست آوردن برخی از کوتاهترین مسیرهای فازی بهینه نشان می دهد، بطوری که نمی توان هیچ کدام از آنها را برای تمام مسیرها کارآمد توصیف نمود. در این مقاله به بازنویسی این الگوریتم پرداخته و با بکارگیری شاخص رتبه بندی ارائه شده توسط کافمن و گوپتا[18] و نیز مقایسه نتایج بدست آمده با استفاده از این روش پیشنهادی، تاثیر و کارایی آن را در یافتن تمامی کوتاهترین مسیرهای فازی بهینه از یک گره معین به دیگر گره ها را مشاهده می کنیم. مقاله به این ترتیب سازماندهی شده است که در بخش 2، خلاصه ای از مفاهیم نظریه فازی مورد استفاده در این کار بیان می شود. در بخش 3، مدلبندی ریاضی FSPP و تشریح الگوریتم پیشنهادی و مثال های عددی ارائه می شود و در پایان، نتیجه گیری و منابع مقاله را مرور خواهیم کرد.
2-3 الگوریتم پیشنهادی
در این بخش روش پیشنهادی بر اساس تعمیم الگوریتم کلاسیک FMB ارائه شده است. این روش برای گراف هایی با یال های دارای هزینه های فازی قابل اجرا می باشد و همانند الگوریتم کلاسیک آن برای گراف های با هزینه های منفی - بدون دور منفی - نیز می تواند بکار گرفته شود. روش پیشنهادی از نوع تصحیح برچسب است یعنی به هر گره یک برچسب تخصیص می یابد که نشان دهنده فاصله مسیر فازی از گره مبدا به گره ، در G است، و این برچسب در هر تکرار تصحیح می شود - یعنی کاهش می یابد یا بدون تغییر می ماند - ، تا زمانی که در تکرار نهایی برابر با طول کوتاهترین مسیر فازی از گره مبدا به گره می شود.
3-3 آزمایشات عددی
در این بخش، دو مثال عددی از مساله کوتاهترین مسیر فازی که در کار هرناندز و همکاران[17] تشریح شده است، با استفاده از روش پیشنهادی و شاخص رتبه بندی کافمن و گوپتا حل می شود و نتایج بدست آمده را با جواب های متناظر در الگوریتم هرناندز و همکاران مقایسه می کنیم تا تاثیر و کارایی آن اثبات شود. در مقاله هرناندز و همکاران مثال هایی از دو شبکه با استفاده از شش شاخص رتبه بندی از جمله شاخص لیو و وانگ [24] ، شاخص گارسیا و لاماتا [25] ، شاخص اوکادا و سوپر[12] ، شاخص یاگر [26,27,28]، شاخص نعیم و پال[5] ، و شاخص دوبویس و پراد[8] با مقادیر ذکر شده در جدول 1 بررسی شده است:
