کتاب رویکرد بهینه سازی استوار برای مکان یابی و مسیریابی با ویژگی های متنوع

فهرست
عنوان صفحه
فصـل اول 11
مکانیابي تسهیلات 13
مکان یابي محور 15
محور 15
طبقه بندی های شبکه محور 19
مدل های پایه مکان یابي محور 23
كاربردهای مکان یابي محور 23
فصـل دوم 27
پیشینه مربوط به مسائل مکانیابي محور 28
اولین مدل مسأله مکان یابي محور 29
مسأله مکانیابي P- محور میانه 31
مسأله مکان یابي محور با هزینه های ثابت 35
مسأله مکانیابي P- محور مركز 39
مکان یابي محور پوشش 40
مجموعه داده های موجود در مکان یابي محور 43
عدم قطعیت در مسائل مکان یابي 44
رویکردهای مقابله با عدم قطعیت 45
بهینه سازی استوار 47
رویکردهای مبتني بر سناریوهای گسسته 48
رویکردهای استوار مبتني بر مجموعه های عدم قطعیت 50
پیشینه تحقیق مربوط به مفهوم عدم قطعیت در مسائل مکانیابي محور 56
فصـل سوم 65
مباني و مفاهیم بهینه سازی استوار مبتني بر مجموعه های عدم قطعیت 65
تعریف نرم 67
انواع مجموعه های عدم قطعیت 68
مجموعه عدم قطعیت جعبه ای 68
مجموعه عدم قطعیت بیضوی 69
مجموعه عدم قطعیت چندوجهي 70
مجموعه عدم قطعیت جعبه ای – بیضوی 70
مجموعه عدم قطعیت جعبه ای – چندوجهي 71
فرمول بندی همتای استوار 72
همتای استوار محدودیت iام برای مجموعه عدم قطعیت جعبه ای 74
همتای استوار محدودیت iام برای مجموعه عدم قطعیت بیضوی 75
همتای استوار محدودیت iام برای مجموعه عدم قطعیت چندوجهي 75
همتای استوار محدودیت iام برای مجموعه عدم قطعیت جعبه ای -بیضوی 75
همتای استوار محدودیت iام برای مجموعه عدم قطعیت جعبه ای چندوجهي 75
مدل قطعي 76
مدل های همتای استوار مسأله مکان یابي محور 79
مدل همتای استوار بر اساس مجموعه عدم قطعیت جعبه ای: 79
مدل همتای استوار بر اساس مجموعه چندوجهي: 79
مدل همتای استوار بر اساس مجموعه بازه ای – چندوجهي: 80
فصـل چهارم 83
نتایج محاسباتي 83
مقایسه نتایج محاسباتي حاصل از مدل قطعي و مدل های استوار 84
مقایسه پیکربندی شبکه در شرایط قطعیت و عدم قطعیت 88
مقایسه استواری جواب های حاصل از مدل قطعي و مدل های استوار 90
میزان چشم پوشي از بهینگي در مدل های استوار 92
فصـل پنجم 95
نتیجه گیری 95
منـابع و مآخـذ 99

مکانیابی تسهیلات بخشی از فرآیند طراحی سیستم های صنعتی و از مسائل مهم در حوزه مهندسی صنایع می باشد. یافتن مکان بهینه برای استقرار تسهیلات، نه تنها مورد توجه مراکز صنعتی بلکه مورد توجه مراکز غیرصنعتی در بخش های دولتی و خصوصی از قبیل مراکز خدماتی، ایستگاه های پلیس، ایستگاه های آتش نشانی، فرودگاه ها و… می باشد. مکانیابی تسهیلات معمولاً از جمله تصمیم گیری های استراتژیک و بلندمدت شرکت های عمومی و خصوصی بوده و به دلیل هزینه های بالای استقرار و راه اندازی تسهیلات و همچنین تـأثیرات بلندمدت تصمیم گیری های مربوط به این مسائل، مطالعه ی مسائل مکانیابی تسهیلات از اهمیت ویژه ای برخوردار است.
مسائل مکانیابی محور از مباحث جدید در حوزه مسائل مکانیابی است که به دلیل کاربردهای فراوان در سیستم های حمل و نقل زمینی و هوایی، سیستم های مخابراتی و شبکه های پستی مورد توجه بسیاری از محققین در رشته های مختلفی قرار گرفته است. محورها تسهیلاتی هستند که به عنوان نقاطی برای انتقال ، تغییر جهت و یا مرتب سازی جریان میان جفت مبادی و مقاصد، در سیستم های توزیع چند به چند به کار برده می شود. در یک مسأله مکانیابی محور، از میان نقاط مبدأ و مقصد موجود، تعدادی از نقاط به عنوان محور انتخاب می شوند که وظیفه جمع آوری و توزیع جریان را بر عهده دارند.
در واقع محورها به عنوان اتصالات میانی، جریان میان جفت مبادی و مقاصد را طوری جمع آوری و توزیع می کنند تا خطوط ارتباطی در شبکه کاهش یابد.
صرفه جویی به مقیاس مهمترین مزیت استفاده از محورها است که کاربرد محورها را توجیه می کند. برای درک بهتر این مفهوم می توان شبکه های هواپیمایی را مثال زد، اگر قرار باشد میان هر جفت مبدأ و مقصد ارتباط مستقیم برقرار باشد هزینه های زیادی برای تأمین هواپیماهای مورد نیاز برای شرکت های هواپیمایی تحمیل می شود و چه بسا ممکن است این کار عملاً امکانپذیر نباشد و یا در صورت امکان به دلیل کمبود تقاضا میان برخی از جفت مبادی و مقاصد، برخی از هواپیماها خالی از سرنشین پرواز کنند و درآمد حاصل از این تقاضای اندک کمتر از هزینه تحمیلی باشد.
طراحی شبکه های محور، بخشی از فرآیند برنامه ریزی استراتژیک یک مؤسسه محسوب می شود. از آنجایی که پیاده سازی و اجرای تصمیمات استراتژیک زمان بر و هزینه بر بوده و تأثیر این تصمیمات بلندمدت و اثرگذار بر عملکرد صحیح سیستم می باشد، طراحی شبکه محور اهمیت ویژه ای دارد. از طرف دیگر، پارامترهایی که در طراحی شبکه مدنظر قرار می گیرند از قبیل تقاضا، هزینه حمل و نقل و هزینه ثابت راه اندازی به دلایل وجود خطاهای پیش بینی ، اندازه گیری و پیاده سازی دچار عدم قطعیت هستند. باید توجه داشت که وجود پارامترهای غیرقطعی در مدل ها بر کیفیت جواب تأثیر می گذارد، در چنین شرایطی استفاده از مدل های قطعی برای طراحی شبکه معقول نبوده و ممکن است منجر به راه حل های زیربهینه و حتی نشدنی شود. در نتیجه توجه به عدم قطعیت در مدلسازی و طراحی شبکه های محور یک امر ضروری بوده و عدم توجه به این مهم ممکن است هزینه های زیادی را به سیستم تحمیل کند.
مکانیابي تسهیلات
مکانیابی تسهیلات از مؤلفه های مهم برنامه ریزی استراتژیک برای بسیاری از مؤسسات عمومی و خصوصی می باشد. هزینه های بالای مربوط به مالکیت دارایی و ساخت تسهیلات، پروژه های مکانیابی تسهیلات را به سرمایه گذاری های بلندمدت تبدیل کرده است. مؤسسات به دنبال یافتن مکان مناسبی برای تسهیلات خود هستند به طوری که سیستم بتواند نه تنها در شرایط کنونی بلکه در تمام مدت طول عمر مؤسسه عملکرد خوبی داشته باشد. یافتن مکان بهینه و استوار برای تسهیلات نیاز به توجه به عدم قطعیت و آینده مؤسسه دارد.
مطالعه تئوری مکان یابی اولین بار توسط آلفرد وبر در سال 1901 آغاز شد. او در پی یافتن جواب این سؤال بود که چگونه مکان یک انبار را بیابد تا فاصله آن با تمامی مشتریان حداقل گردد. با الهام گرفتن از کار او، محققان مختلف در رشته های دیگر نیز پژوهش هایی انجام دادند.
با مقاله حکیمی در سال 1964تئوری مکان یابی دوباره مورد توجه ویژه بسیاری از محققان قرار گرفته و پس از او کارهای زیادی در این زمینه انجام شده است. اصطلاح آنالیز مکان مربوط به مدلسازی، فرمول بندی و یافتن راه حل گروهی از مسائل است که می توان این گونه تعریف کرد: استقرار تسهیلات در فضای معین. قرارگیری ، موقعیت یابی ، استقرار واژگان مترادفی هستند که مفهوم مکانیابی را می رسانند.
بین مسائل مکانیابی تسهیلات و چیدمان تسهیلات تفاوت وجود دارد، چرا که در مسائل مکانیابی، ابعاد تسهیلات در مقایسه با فضای استقرار کوچک هستند و تقابل میان تسهیلات ممکن است وجود داشته و یا نداشته باشد. در مقابل در مسائل چیدمان تسهیلات، ابعاد تسهیلات نسبت به فضای استقرار بزرگ و قابل توجه بوده و معمولاً میان تسهیلات تقابل وجود دارد.

مسائل کلاسیک مکانیابی تسهیلات، برای مدت زمان طولانی مورد توجه و مطالعه محققان قرار گرفته است. با اینکه مسائل مکان یابی محور حوزه ی جدیدی در سری مسائل مکان یابی محسوب می شود اما محققان زیادی در این زمینه کار کرده و مدل های مختلف و الگوریتم های متنوعی برای حل انواع مسائل مکان یابی محور ارائه کرده اند.
همانطور که در فصل قبل اشاره گردید، یکی از جنبه های مهم مسائل برنامه ریزی ریاضی که باید مورد توجه قرار بگیرد، وجود عدم قطعیت در پارامترهای مسأله می باشد. مسائل مکان یابی نیز از این امر مستثنی نبوده و عدم قطعیت بر روی جواب های به دست آمده از این مسائل اثر گذاشته و ممکن است هزینه های زیادی بر سیستم تحمیل کند. با اینکه در دهه های اخیر عدم قطعیت در مسائل مکان یابی تسهیلات مورد توجه بسیاری از محققین قرار گرفته است، اما کارهایی که عدم قطعیت را در مدل های مکان یابی محور مدنظر قرار داده اند اندک می باشند.
در این بخش، سعی شده است تا مروری بر مطالعات پیشین در انواع مدل های پایه ی مکان یابی محور ارائه گردد. سپس انواع رویکردهای مواجهه با عدم قطعیت، معایب و مزایای هر یک بیان می گردد. در نهایت مروری بر مقالاتی که عدم قطعیت را بر روی پارامترهای مختلفی از مسائل مکان یابی محور در نظر گرفته اند، انجام می گیرد.
پیشینه مربوط به مسائل مکانیابي محور
می توان گفت نخستین مقالاتی که ایده مکانیابی محور را مطرح کرده اند، کارهای بنیادین حکیمی [9] و[10] در سال های 1964و 1965 در حوزه مکان یابی شبکه است. او در مقاله خود که به مطالعه شبکه ارتباطی پرداخته اشاره کرده است که جریان های آغازی از مبادی مختلف، قبل از اینکه به مقصد نهایی برسند، باید به یک مرکز فرستاده شوند. او در ادامه کار خود در دومین مقاله، مراکز متعددی را در شبکه خود مطرح کرده است به طوری که جریان می تواند میان این مراکز منتقل شود.
با این حال از آنجایی که هزینه انتقال بین مراکز را ناچیز در نظر گرفته است، این مدل را نمی توان جزو مسائل محور در نظر گرفت[11].
گلدمن در سال 1969 با الهام گرفتن از کارهای حکیمی، مدلی ارائه نمود که شاید بتوان گفت اولین مدل مکان یابی محور بوده است. او نرخ هزینه های متفاوتی برای تجمیع جریان در گره اول سپس انتقال جریان به گره دوم و در نهایت توزیع جریان از گره دوم به مقاصد نهایی معرفی کرد[12]. گلدمن همچنین به اهمیت مزیت صرفه جویی به مقیاس اشاره کرده، ولی هیچ مثال عددی و یا الگوریتم حلی ارائه نکرده بود[11].
در واقع نقطه آغاز مطالعات در زمینه مسائل مکان یابی محور به مقالات اوکلی در سال 1987 بر می گردد. اوکلی نقش بسیار مهمی در گسترش مدل های مکان یابی محور داشته است. او در سال 1987 اولین فرمول ریاضیاتی شناخته شده ای در این زمینه ارائه نمود که یک مدل کوادراتیک بود. او مدل خود را بر اساس مطالعه شبکه هوایی مسافربری ارائه نمود، این مدل به مدل مکانیابی P- محور میانه با تخصیص تکی معروف است[13].
از جمله مطالعات مروری که در حوزه مسائل مکان یابی محور انجام گرفته است، می توان به مقالات اوکلی و مایلر [7]، آلومور و کارا [3]، کمپبل و اوکلی[11] و زنجیرانی فراهانی و همکاران[6] اشاره کرد.
اولین مدل مسأله مکان یابي محور
همانطور که پیش تر اشاره شد، اولین مدل ریاضیاتی در مجموعه مسائل محور توسط اوکلی در سال 1987 معرفی گردید. این مدل به مسأله P- محور میانه با تخصیص یگانه معروف است، چرا که تابع هدف از نوع حداقل کردن هزینه های حمل و نقل بوده و هزینه احداث محورها مد نظر قرار نمی گیرد. گره های غیرمحور تنها اجازه اتصال به یک محور را دارند و محدودیت ظرفیت در این مدل لحاظ نمی گردد[13]. بزرگترین ایراد وارده به این مدل، تابع هدف غیرخطی آن است که محققین سعی در رفع این مورد در ادامه مطالعات مسائل محور داشته اند. پارامترها و متغیرهای مدل بدین ترتیب می باشند: