شـماره : ……………………………………………………….
تـاریخ : …………………………………………………………
پیوست : ……………………………………………………..
باسمه تعالی
فرم تعهد نامه اصالت رساله يا پايان نامه تحصیلی
اینجانب فریدون حبیب زاده بوکانی دانش آموخته مقطع کارشناسی ارشد ناپیوسته رشته مهندسی صنایع گرایش مدیریت سیستم و بهره‌وری که در تاریخ 21/11/92 از پایان نامه خود با عنوان: تخصیص ساده و چندگانه ظرفیت محدود مسئله مکان یابی محور با کسب نمره و درجه دفاع نموده‌ام، بدینوسیله متعهد می‌شوم:
1- اين پايان نامه حاصل تحقيق و پژوهش انجام شده توسط اينجانب بوده و در مواردی كه از دستاوردهای علمي و پژوهشي دیگران (اعم از پايان نامه، كتاب و مقاله) استفاده نموده ام، مطابق ضوابط و رويه موجود، نام منبع مورد استفاده و ساير مشخصات آن را در فهرست مربوطه ذكر و درج كرده‌ام.
2- اين پايان نامه قبلاً براي دريافت هیچ مدرک تحصیلی (هم سطح، پايين تر يا بالاتر)در ساير دانشگاهها و موسسات عالی ارائه نشده است.
3- چنانچه بعد از فراغت از تحصيل، قصد استفاده يا هر گونه بهره‌برداري اعم از چاپ كتاب، ثبت و اختراع و… از اين پايان نامه را داشته باشم، از حوزه معاونت پژوهشي واحد پرند مجوز هاي مربوطه را اخذ نمايم و در صورت ارائه مقاله در همايشها و مجلات با ذكر نام دانشگاه آزاد اسلامي واحد پرند در كنار نام نويسندگان به نحوي كه تعلق اثر به دانشگاه آزاد اسلامي واحد پرند كامل مسجل باشد حقوق دانشگاه را رعايت نماييم.
4- چنانچه در هر مقطع زماني خلاف موارد فوق ثابت شود ، عواقب ناشي از آن را مي پذيرم و واحد دانشگاهي مجاز است با اينجانب مطابق با ضوابط و مقررات رفتار نموده و در صورت ابطال مدرك تحصيلي‌ام هيچگونه ادعايي نخواهم داشت.
تاريخ و امضاء:
نشانی: تهران –آزادراه تهران ساوه- قبل از عوارضی دوم–شهر جدید پرند– دانشگاه آزاد اسلامی واحد پرند- تلفن: 56733080-021 – فکس : 56733081-021
Email:info@piau.ac.ir
دانشگاه آزاد اسلامی
واحد پرند
پایان‌نامه برای دریافت درجه کارشناسی ارشد «M.Sc»
رشته: مهندسی صنایع
گرایش: مدیریت سیستم و بهره‌وری
عنوان:
تخصیص ساده و چندگانه‌ی ظرفیت محدود مسئله‌ی مکان‌یابی محور مبتنی بر رویکرد بهینه‌سازی استوار
استاد راهنما:
دکتر بابک فرهنگ مقدم
استاد مشاور:
دکتر میر‌سامان پیشوائی
نگارش:
فریدون حبیب زاده بوکانی
زمستان 1392
سپاسگزاری
در اینجا لازم است تا از زحمات بی‌دریغ جناب آقای دکتر بابک فرهنگ مقدم و جناب آقای دکتر میر‌سامان پیشوائی کمال تشکر را داشته باشم، بی‌شک رهنمود‌های این دو عزیز در به ثمر رسیدن این پایان‌نامه تأثیر بسزایی داشته است.
تقدیم به
خانواده‌ام که در تمامی مراحل زندگی همواره حامی من بوده‌اند.
فهرست مطالبچکیده………………………………………………………………………………………………………………………………………………………….1مقدمه…………………………………………………………………………………………………………………………………………………………..2 فصل اول: کليات تحقيق…………………………………………………………………………………………………………….51-1. مقدمه…………………………………………………………………………………………………………………………………………………..61-2. تعاريف کلي از حوزه تحت بررسي………………………………………………………………………………………………………….61-2-1. مکان‌یابی محور…………………………………………………………………………………………………………………………………61-2-2. انواع کاربرد‌های مسئله‌ی مکان‌يابی محور……………………………………………………………………………………………..91-2-2-1. خطوط هوایی و فرودگاه‌ها……………………………………………………………………………………………………………..91-2-2-2. صنعت حمل‌و‌نقل و باربری…………………………………………………………………………………………………………….101-2-2-3. خدمات تحويل پستی و شرکت‌های تحويل سريع بسته………………………………………………………………………101-2-2-4. سيستم‌های ارتباط از راه دور و شبکه‌های تحويل پيام………………………………………………………………………..101-2-2-5. خدمات اضطراری………………………………………………………………………………………………………………………….101-2-2-6. انبارهای زنجیره‌ای زنجیره تأمین……………………………………………………………………………………………………..101-2-2-7. شرکت‌های توليدی در زمينه‌ی جابجايی صحيح………………………………………………………………………………..111-2-3. مثال‌های عملی از کاربرد مسئله‌ی مکان‌يابی محور…………………………………………………………………………………111-2-4. بهينه‌سازی استوار شبکه‌های لجستيک در شرايط غير‌قطعی………………………………………………………………………111-3. بيان مسئله و اهداف تحقيق……………………………………………………………………………………………………………………..131-4. ضرورت انجام تحقيق و کاربردهای آن…………………………………………………………………………………………………….131-5. ساختار پایان‌نامه…………………………………………………………………………………………………………………………………….14 فصل دوم: مروری بر ادبيات تحقيق……………………………………………………………………………………………152-1. مقدمه………………………………………………………………………………………………………………………………………………….162-2. طبقهبندي مقالات از مناظر مختلف…………………………………………………………………………………………………………..162-2-1. مدل‌های قطعی تخصيص ساده و چندگانه‌ی مسئله‌ی مکان‌يابی محور………………………………………………………162-2-2. مدل‌های غير‌قطعی تخصيص ساده و چندگانه‌ی مسئله‌ی مکان‌يابی محور………………………………………………….312-3. مروری بر ادبیات بهینه‌سازی استوار………………………………………………………………………………………………………….332-3-1. عدم قطعیت در شبکه‌های لجستيکی…………………………………………………………………………………………………….342-3-2. روش‌های بهينه‌سازی تحت عدم قطعیت………………………………………………………………………………………………362-3-3. بهینه‌سازی استوار………………………………………………………………………………………………………………………………362-3-3-1. مدل تأسف…………………………………………………………………………………………………………………………………..372-3-4. بهينه‌سازی استوار شبکه‌های لجستيکی………………………………………………………………………………………………….382-3-5. چالش‌های بهينه‌سازی استوار………………………………………………………………………………………………………………382-4. نتيجه‌گيری از تحقيقات گذشته و بيان ايده‌های تحقيق………………………………………………………………………………..39 فصل سوم: مدل پيشنهادی………………………………………………………………………………………………………….413-1. مقدمه………………………………………………………………………………………………………………………………………………….423-2. مدل‌های پيشنهادي…………………………………………………………………………………………………………………………………423-2-1. حالت قطعی تخصيص ساده‌ی ظرفيت محدود مسئله‌ی مکان‌يابی محور (CSAHLP)…………………………………423-2-1-1. نمادها و علائم بکار رفته در مدل رياضی………………………………………………………………………………………….433-2-1-1-1. مجموعه‌ها………………………………………………………………………………………………………………………………..433-2-1-1-2. پارامتر‌ها…………………………………………………………………………………………………………………………………..443-2-1-1-3. متغیرهای تصميم‌گيری……………………………………………………………………………………………………………….443-2-1-2. مدل رياضي………………………………………………………………………………………………………………………………….453-2-1-2-1. تابع هدف و محدوديتها…………………………………………………………………………………………………………..453-2-1-2-2. تشريح تابع هدف و محدوديتها………………………………………………………………………………………………..463-2-2. حالت قطعی تخصيص چندگانه‌ی ظرفيت محدود مسئله‌ی مکان‌يابی محور (CMAHLP)…………………………..463-2-2-1. نمادها و علائم بکار رفته در مدل رياضی………………………………………………………………………………………….473-2-2-1-1. مجموعه‌ها………………………………………………………………………………………………………………………………..473-2-2-1-2. پارامتر‌ها…………………………………………………………………………………………………………………………………..473-2-2-1-3. متغیرهای تصمیم‌گیری……………………………………………………………………………………………………………….483-2-2-2. مدل رياضي………………………………………………………………………………………………………………………………….483-2-2-2-1. تابع هدف و محدوديتها…………………………………………………………………………………………………………..493-2-2-2-2. تشريح تابع هدف و محدوديتها………………………………………………………………………………………………..503-3. مدل رویکرد بهینه‌سازی استوار………………………………………………………………………………………………………………..503-3-1. تخصیص ساده………………………………………………………………………………………………………………………………….513-3-2. تخصیص چندگانه……………………………………………………………………………………………………………………………..53 فصل چهارم: الگوريتم حل، نتايج و تفسير آن‌ها………………………………………………………………………..564-1. مقدمه…………………………………………………………………………………………………………………………………………………..574-2. روش حل پيشنهادي………………………………………………………………………………………………………………………………574-3. تشريح مطالعه موردي…………………………………………………………………………………………………………………………….574-4. نتايج محاسباتي (برای حالت قطعی)…………………………………………………………………………………………………………604-4-1. نتايج محاسباتی حالت قطعی تخصيص ساده‌ی ظرفيت محدود مسئله‌ی مکان‌يابی محور (CSAHLP)………….614-4-2. نتايج محاسباتی حالت قطعی تخصيص چندگانه‌ی ظرفيت محدود مسئله‌ی مکان‌يابی محور (CMAHLP)……654-5. نتايج محاسباتی (برای حالت غير‌قطعی)……………………………………………………………………………………………………694-5-1. نتايج محاسباتی حالت غير‌قطعی تخصيص ساده‌ی ظرفيت محدود مسئله‌ی مکان‌يابی محور (CSAHLP)……..704-5-2. نتايج محاسباتی حالت غير‌قطعی تخصيص چندگانه‌ی ظرفيت محدود مسئله‌ی مکان‌يابی محور (CMAHLP).75 فصل پنجم: جمع‌بندی، نتيجه‌گيری و پيشنهادها………………………………………………………………………….815-1. جمعبندي و نتيجهگيري………………………………………………………………………………………………………………………….825-2. نوآوريهاي مدل……………………………………………………………………………………………………………………………………855-3. پيشنهادها……………………………………………………………………………………………………………………………………………..86 منابع……………………………………………………………………………………………………………………………………………88پيوست الف: کد نوشته‌شده در نرم‌افزار GAMS برای حالت قطعی (CSAHLP)……………………………………………….97پيوست ب: کد نوشته‌شده در نرم‌افزار GAMS برای حالت قطعی (CMAHLP)………………………………………………..101پيوست ج: کد نوشته‌شده در نرم‌افزار GAMS برای حالت غیر‌قطعی (RCSAHLP)……………………………………………106پيوست د: کد نوشته‌شده در نرم‌افزار GAMS برای حالت غیر‌قطعی (RCMAHLP)……………………………………………109فهرست جدولهاجدول (2-1): منابع عدم قطعیت در زنجیره تأمین: قدرت اثرگذاری کم، متوسط و زیاد تصمیمات……………………………………..35جدول (2-2): تعیین جايگاه اين تحقيق و مروری بر ادبيات تحقيقات انجام‌شده……………………………………………………………40جدول (4-1): 37 گره‌ی موجود در مجموعه داده‌های IAD به ترتیب بزرگی جریان (از بالا به پایین)………………………59جدول (4-2): نتایج مدل قطعی تخصیص ساده‌ی ظرفیت محدود………………………………………………………………………..64جدول (4-3): نتایج مدل ‌قطعی تخصیص چندگانه‌ی ظرفیت محدود……………………………………………………………………69جدول (4-4): نتایج مدل غیر‌قطعی تخصیص ساده‌ی ظرفیت محدود……………………………………………………………………74جدول (4-5): نتایج مدل غیر‌قطعی تخصیص چندگانه‌ی ظرفیت محدود………………………………………………………………79فهرست شکلهاشکل (1-1): یک گراف کامل با 6 گره و 30 زوج مبدأ/مقصد…………………………………………………………………………….7شکل (1-2): یک شبکه‌ی تک محور با 6 گره و 30 زوج مبدأ/مقصد……………………………………………………………………7شکل (1-3): مثالی از یک شبکه‌ی 3 محور……………………………………………………………………………………………………….8شکل (4-1): تعدادی از فرودگاه‌های ایران در یک نگاه………………………………………………………………………………………58شکل (4-2): 37 شهر موجود در مجموعه داده‌های IAD……………………………………………………………………………………60شکل (4-3): نتایج مدل قطعی تخصیص ساده‌ی ظرفیت محدود به ازای 2/0 α=……………………………………………….61شکل (4-4): نتایج مدل قطعی تخصیص ساده‌ی ظرفیت محدود به ازای 4/0 α=……………………………………………….62شکل (4-5): نتایج مدل قطعی تخصیص ساده‌ی ظرفیت محدود به ازای 6/0 α=……………………………………………….63شکل (4-6): نتایج مدل قطعی تخصیص ساده‌ی ظرفیت محدود به ازای 8/0 α=……………………………………………….64شکل (4-7): نتایج مدل قطعی تخصیص چندگانه‌ی ظرفیت محدود به ازای 2/0 α=…………………………………………..65شکل (4-8): نتایج مدل قطعی تخصیص چندگانه‌ی ظرفیت محدود به ازای 4/0 α=…………………………………………..66شکل (4-9): نتایج مدل قطعی تخصیص چندگانه‌ی ظرفیت محدود به ازای 6/0 α=…………………………………………..67شکل (4-10): نتایج مدل قطعی تخصیص چندگانه‌ی ظرفیت محدود به ازای 8/0 α=…………………………………………68شکل (4-11): نتایج مدل غیر‌قطعی تخصیص ساده‌ی ظرفیت محدود به ازای 2/0 α=…………………………………………70شکل (4-12): نتایج مدل غیر‌قطعی تخصیص ساده‌ی ظرفیت محدود به ازای 4/0 α=…………………………………………71شکل (4-13): نتایج مدل غیر‌قطعی تخصیص ساده‌ی ظرفیت محدود به ازای 6/0 α=…………………………………………72شکل (4-14): نتایج مدل غیر‌قطعی تخصیص ساده‌ی ظرفیت محدود به ازای 8/0 α=…………………………………………73شکل (4-15): نتایج مدل غیر‌قطعی تخصیص چندگانه‌ی ظرفیت محدود به ازای 2/0 α=……………………………………75شکل (4-16): نتایج مدل غیر‌قطعی تخصیص چندگانه‌ی ظرفیت محدود به ازای 4/0 α=……………………………………76شکل (4-17): نتایج مدل غیر‌قطعی تخصیص چندگانه‌ی ظرفیت محدود به ازای 6/0 α=……………………………………77شکل (4-18): نتایج مدل غیر‌قطعی تخصیص چندگانه‌ی ظرفیت محدود به ازای 8/0 α=……………………………………78
چکيده
مسئله‌ی مکان‌یابی محور یکی از حوزه‌های نوظهور و تازه رونق گرفته در نظریه مکان‌یابی تسهیلات کلاسیک است که بایستی مدیران زنجیره تأمین سازمان‌ها و شرکت‌ها در هنگام طراحی شبکه‌ی زنجیره تأمین خود به عنوان بخشی از فرآیند تصمیم‌گیری، توجه ویژه‌ای به این مسائل داشته باشند. در برنامه‌ریزی استراتژیک، ممکن است تصمیم‌ها اثر طولانی مدتی داشته باشند و پیاده‌سازی برنامه‌ها زمان قابل‌توجهی را بگیرد. همچنین، داده‌های ورودی از قبل دقیقاً شناخته‌شده نباشند. از این رو، در تصمیمات گرفته‌شده بایستی عدم قطعیت در نظر گرفته شود. عدم قطعیت را می‌توان به عنوان خاصیتی از سیستم در نظر گرفت که توصیف‌کننده‌ی نقص دانش بشر درباره‌ی یک سیستم و وضعیت پیشرفت آن، است. در این تحقیق مدل‌های خاصی از مسائل مکان‌یابی محور تحت عنوان تخصیص ساده و چندگانه‌ در نظر گرفته شده است. ابتدا مدل‌ عمومی حالت‌های تخصیص ساده و چندگانه‌ی ظرفیت محدود معرفی‌شده و در ادامه مدل پیشنهادی این تحقیق برای نحوه‌ی برخورد با عدم قطعیت پارامترها که شامل حالت‌های تخصیص ساده و چندگانه‌ی ظرفیت محدود مکان‌یابی محور مبتنی بر رویکرد بهینه‌سازی استوار است، ارائه می‌شود. در انتها عدم قطعیت پارامترهایی مانند هزینه‌ی ثابت راه‌اندازی محور و ظرفیت مربوط به هر محور بر روی مجموعه داده‌های هواپیمایی ایران IAD1 با استفاده از رویکرد 2Minimax Regret بررسی و نتایج به دست آمده تجزیه و تحلیل می‌شود. نتایج به دست آمده حاکی از آن است که در نظر نگرفتن عدم قطعیت در طراحی شبکه‌های زنجیره تأمین، گاه باعث ایجاد خسارت‌ها و هزینه‌های هنگفتی می‌شود که این ضرر‌های متحمل شده به نوبه‌ی خود موجب تأخیر در اجرا و پیاده‌سازی برنامه‌های بلند‌مدت پیش‌بینی‌شده و تعلیق تمامی فعالیت‌های سازمان‌ها یا شرکت‌ها می‌شود.
واژه‌هاي کليدی: مکان‌یابی تسهیلات، مکان‌یابی محور، عدم قطعیت، تخصیص ساده و چندگانه‌ی ظرفیت محدود، بهینه‌سازی استوار، Minimax Regret
مقدمه
مكان‌يابي تسهيلات، واژه‌اي شناخته‌شده در حوزه مطالعات كاربردي تحقیق در عملیات است. تعداد بسیار زیاد مقاله‌ها و تحقیق‌های منتشرشده، گواه بر این ادعا است. با اين حال، كاربرد مدل‌هاي مكان‌يابي همواره مورد پرسش قرار دارند. البته سودمندي و كاربردي بودن مكان‌يابي به ویژه در لجستيك، هيچ‌گاه مورد ترديد قرار نگرفته است. قابل‌توجه‌ترین موارد لجستيك در اين حوزه، مديريت زنجيره تأمين است. در واقع، توسعه‌ی مدیریت زنجیره تأمین به طور مستقل از تحقیق در عملیات انجام‌گرفته و تحقیق در عملیات گام به گام وارد مباحث زنجیره تأمین شد. در نتيجه، مدل‌هاي مكان‌يابي تسهيلات، به تدريج وارد متون زنجيره تأمین‌شده و حوزه‌اي بسيار جذاب و مفيد به وجود آمد.
در روند اين توسعه، به طور طبيعي سؤالاتي متعدد به وجود مي‌آيند كه برخي از آن‌ها عبارت‌اند از:
مدل مكان‌يابي تسهيلات بايد داراي چه ويژگي‌هايي باشد تا در حوزه تأمين پذيرفته شود؟
آيا مدل‌هايي از مكان‌يابي تسهيلات وجود دارند كه قبلاً در حوزه زنجيره تأمين كارايي داشته‌اند؟
آيا اصولاً مدیریت زنجیره تأمین به مكان‌يابي تسهيلات نيازي دارد؟
يكي از مسائل مكان‌يابي تسهیلات، شناخت مجموعه‌اي از مشتريان با فواصل فيزيكي متفاوت و مجموعه‌اي از تسهيلات براي برآورده سازی تقاضای آن‌هاست. فاصله‌ها، زمان‌ها و هزينه‌هاي مشتريان و تسهيلات، مي‌بايستي با سنجه‌اي خاص اندازه‌گيري شود. سؤالات نيازمند به پاسخ شامل موارد ذيل مي‌شوند:
كدام يك از تسهيلات بايد مورد استفاده قرار گيرد (به لحاظ موقعيت مكاني)؟
كدام مشتري بايد از كدام تسهيلات خدمات دريافت كند تا هزينه به حداقل برسد؟
مدل‌هاي تعيين محل تسهيلات، نقش مهمي در طراحي و برنامه‌ريزي زنجيره تأمين دارند. اصولاً در طراحي و برنامه‌ريزي زنجيره تأمين 3 سطح بر اساس افق زماني شامل استراتژيك، تاكتيكي و عملياتي وجود دارد. سطح استراتژي با تصميماتي ارتباط دارد كه اثراتي بلندمدت بر سازمان شما مي‌گذارد. اين موارد، شامل تصميماتي در خصوص: تعداد، محل، ظرفيت انبار، ظرفيت توليد يا جريان مواد ‌اوليه در شبكه لجستيك است. مکان‌یابی تسهیلات حوزه‌های بسیار دیگری را نیز در بر می‌گیرد. یکی از جدیدترین و پر‌کاربردترین آن‌ها مکان‌یابی محور است. محورها تسهیلاتی هستند که در راستای خدمات‌رسانی به مردم، برآورده کردن تقاضاها، گردش اطلاعات و کالاهای مصرفی میان زوج‌های مبدأ و مقصد مورد نظر، به وجود آمده‌اند. از محورها برای کاهش تعداد اتصالات حمل‌و‌نقل بین گره‌های مبدأ و مقصد استفاده می‌شود (Zanjirani Farahani et al., 2013).
پس از مقاله‌های اولیه‌ی O’Kelly (1986, 1987) تحقیقات زیادی در این حوزه صورت گرفته است. مخصوصاً، مسائلی با اهداف و ویژگی‌های متفاوت، که بیشتر مورد توجه قرارگرفته‌اند. مسئله‌ی p-محور میانه و مسائل مکان‌یابی محور ظرفیت محدود و ظرفیت نامحدود از جمله موضوعاتی هستند که بیش‌ترین تکرار را در مقاله‌های منتشرشده دارند. در مسئله‌ی p-محور میانه هدف حداقل سازی هزینه‌های عملیاتی شبکه (هزینه‌های مسیریابی تقاضا) است، از طرفی دیگر در مسائل مکان‌یابی محور ظرفیت محدود و نامحدود هزینه‌های ثابت راه‌اندازی محورها نیز در تابع هدف در نظر گرفته می‌شود (Alumur et al., 2012).
در مسائل مکان‌یابی محور معمولاً تعدادی گره با میزان تقاضاهای متناظر وجود دارد که جریان بین این گره‌ها در حال انتقال است. در مدل تخصیص ساده‌ی مکان‌یابی محور تعدادی از گره‌ها به عنوان محور انتخاب می‌شوند و گره‌های دیگر یعنی گره‌های غیر محور (میله) هر کدام تنها به یک محور متصل می‌باشند. در این مدل هیچ‌گونه ارتباط مستقیمی بین گره‌های غیر محور وجود ندارد و جریان تنها از طریق محورهای مواصلاتی انتقال می‌یابد و از طریق اتصال محورها به همدیگر جریان در سراسر شبکه توزیع می‌گردد. در مدل تخصیص چندگانه نیز همانند حالت تخصیص ساده بین گره‌های غیر محور اتصالی برقرار نیست و جریان گره‌های غیر محور از طریق محورها انتقال می‌یابد اما با این تفاوت که در اینجا گره‌های غیر محور مجازند تا با بیش از یک محور در ارتباط باشند و از طریق آن‌ها جریان را به گره‌های دیگر شبکه برسانند.
در این پایان‌نامه مدل‌های خاصی از تخصیص ساده و چندگانه‌ی مسائل مکان‌یابی محور ارائه می‌شود. مسائلی که در آن‌ها ظرفیت هر مرکز سرویس‌دهی یا خدمات‌رسانی محدود است. با وجود این‌که هدف نهایی این نوع مسائل کمینه کردن هزینه‌های شبکه و تخصیص بهینه‌ی گره‌ها به محورهای ایجادشده است، به دلیل محدود بودن ظرفیت محورها در هنگام تخصیص گره‌های غیر محور، امکان دارد که سیاست تخصیص هر گره به نزدیک‌ترین محور در دسترس دچار اختلال شود و گره‌ها به دلیل برآورده نشدن تقاضای مورد نیازشان از جانب محوری خاص، تقاضای خود را به دیگر محورهای موجود در شبکه ارسال کنند. معمولاً مسائل دنیای واقعی با فرض غیر‌قابل تغییر بودن پارامترهای ورودی، مورد تحلیل قرار می‌گیرند. با این حال در عمل، غالباً داده‌های ورودی با مفروضات مدل‌های ریاضی متفاوت است. لذا، این مفروضات منجر به جواب‌هایی می‌شود که از بهینگی و حتی شدنی بودن در دنیای واقعی، به دور است. تقاضا، انواع هزینه‌ها، ظرفیت‌ها و … مواردی هستند که در طی زمان در مسائل مکان‌یابی تسهیلات طراحی شبکه تغییر می‌نمایند. در نتیجه بررسی و توسعه مدل ظرفیت محدود مکان‌یابی تسهیلات طراحی شبکه در حالت عدم قطعیت یکی از شکاف‌های تحقیقاتی موجود در این زمینه تلقی می‌شود که سعی خواهد شد این خلأ مورد بررسی قرار گیرد. بهینه‌سازی تحت عدم قطعیت نوعاً از دو دیدگاه بررسی می‌شود. (1) برنامه‌ریزی تصادفی و (2) بهینه‌سازی استوار. در برنامه‌ریزی تصادفی، پارامترهای نامعین توسط تابع توزیع احتمالی تحت کنترل بوده و مدل به دنبال ارائه‌ی راه‌حلی است که هزینه‌ی انتظاری تابع هدف را کمینه سازد. اما در بهینه‌سازی استوار احتمالات نامعین بوده و پارامترهای تصادفی از طریق سناریوهای گسسته یا فواصل بازه‌ای تخمین زده می‌شوند. در حالت گسسته، برای هر پارامتر بر اساس تجارب گذشته و مطالعات و امکان‌سنجی‌های صورت گرفته چندین عدد مختلف پیشنهاد می‌شود که به هر یک از آن‌ها عنوان سناریو اطلاق شده و در حالت پیوسته هر پارامتر غیر‌قطعی با یک بازه‌ی مشخص تعیین می‌گردد. در مسائل بهینه‌سازی استوار هدف نهایی کمینه ساختن بدترین هزینه یا میزان تأسف است که در این تحقیق نیز از همین مدل استفاده شده است.
در این تحقیق ابتدا مدل‌های تخصیص ساده و چندگانه‌ی ظرفیت محدود مسئله‌ی مکان‌یابی محور در نظر گرفته می‌شوند. سپس مدل توسعه داده‌شده را بر روی مجموعه داده‌های IAD که توسط Karmi and Bashiri (2011) تهیه و تنظیم شده است، آزمایش می‌کنیم و مکان‌های انتخابی حالت قطعی ظرفیت محدود این مدل‌ها را با نرم‌افزار GAMS ver.243 به دست می‌آوریم. سپس با توجه به حساسیت جواب‌های مدل نسبت به پارامترهای هزینه‌ی ثابت راه‌اندازی و ظرفیت هر محور از روش بهینه‌سازی استوار استفاده کرده و مدل‌های تخصیص ساده و چند‌گانه‌ی ظرفیت محدود را با نرم‌افزار GAMS حل کرده و مکان‌های انتخابی و هزینه‌های به وجود آمده را تجزیه و تحلیل می‌کنیم. در دنیای واقعی به ویژه در مورد مطالعه‌ای این تحقیق که بر روی 37 فرودگاه عمده‌ی ایران انجام شده است، فرودگاه‌های شهرهای مختلف هر کدام دارای ظرفیت‌های محدودی هستند، بسته به جمعیت و وسعت شهرها، ترافیک جریان هوایی، امکانات رفاهی حال مسافران، بودجه‌ی تخصیص داده‌شده به آن‌ها، وضعیت ناوگان حمل‌و‌نقل، فرسودگی هواپیماها و… وضعیت متفاوت است. به عنوان مثال در شهرستان‌های خیلی کوچکی (در قیاس با دیگر شهرهای مجموعه‌ی IAD) مانند ایلام، رامسر، یاسوج، خارک و … نمی‌توان همواره محور ایجاد کرد و جوابگوی تقاضاهای ورودی به آن‌ها نخواهیم بود.
ادامه‌ی موضوعات این تحقیق به این صورت است که ابتدا در فصل اول کلیات تحقیق که شامل تعاریف کلی از حوزه‌ی مورد بررسی، اهداف، ضرورت و کاربرد‌های تحقیق است، آورده می‌شود سپس در فصل دوم مرور ادبیات تحقیق بررسی می‌شود و در فصل سوم مدل پیشنهادی به خوبی تشریح شده و در فصل چهارم نتایج محاسباتی به دست آمده به صورت کامل توضیح داده خواهند شد و در نهایت در فصل پنجم جمع‌بندی کلی نتایج به دست آمده به همراه نوآوری‌ها و پیشنهاد برای تحقیقات آینده نیز ارائه می‌گردد.
فصل اول
کلیات تحقیق
1-1. مقدمه
1-2. تعاریف کلی از حوزه تحت بررسی
1-3. بیان مسئله و اهداف تحقیق
1-4. ضرورت انجام تحقیق و کاربردهای آن
1-5. ساختار پایان‌نامه
1-1. مقدمه
مكان‌يابي تسهيلات، واژه‌اي شناخته‌شده در حوزه مطالعات كاربردي تحقیق در عملیات است. تعداد بسیار زیاد مقاله‌ها و تحقیق‌های منتشرشده، گواه بر این ادعا است. با اين حال، كاربرد مدل‌هاي مكان‌يابي همواره مورد پرسش قرار دارند. البته سودمندي و كاربردي بودن مكان‌يابي به ویژه در لجستيك، هيچ‌گاه مورد ترديد قرار نگرفته است. قابل‌توجه‌ترین موارد لجستيك در اين حوزه، مديريت زنجيره تأمين است. در واقع، توسعه‌ی مدیریت زنجیره تأمین به طور مستقل از تحقیق در عملیات انجام‌گرفته و تحقیق در عملیات گام به گام وارد مباحث زنجیره تأمین شد. در نتيجه، مدل‌هاي مكان‌يابي تسهيلات، به تدريج وارد متون زنجيره تأمين شده و حوزه‌اي بسيار جذاب و مفيد به وجود آمد.
1-2. تعاريف کلی از حوزه تحت بررسی
1-2-1. مکان‌يابی محور
یکی از مباحث جدیدی که در حوزه‌ی مسائل مکان‌یابی تسهیلات مطرح شده است، مسئله‌ی مکان‌یابی محور است. این مبحث به جهت کاربردهای وسیعی که در دنیای واقعی دارد، از اهمیت زیادی برخوردار است. در این مبحث خدمتی که انجام می‌گیرد، شامل حرکت افراد، کالاها یا اطلاعات، بین یک مکان مبدأ و یک مکان مقصد است. هر زوج مبدأ/مقصد، خدمت متفاوتی از زوج‌های دیگر نیاز دارد. لذا برای بسته‌های حمل شده از تهران به مشهد با بسته‌های حمل شده از اصفهان به شیراز قابل تعویض نیست.
اگر N گره داشته باشیم و هر یک از آن‌ها بتوانند مبدأ یا مقصد باشند، در یک شبکه‌ی کاملاً متصل که هر گره به طور مستقیم به گره‌های دیگر متصل است، (1- N) N زوج مبدأ/مقصد خواهیم داشت. (به عنوان مثال زوج تهران/مشهد با زوج مشهد/تهران متفاوت است.) شکل(1-1) چنین شبکه‌ای را با 6 گره (6=N) نشان می‌دهد. اگر جابجایی کالا در این شبکه مدنظر باشد، با داشتن 18 خودرو و دانستن اینکه با هر خودرو در هر روز 5 زوج مبدأ/مقصد را می‌توانیم خدمات دهیم، آنگاه روزانه دقیقاً 10 گره را می‌توانیم خدمات دهیم.
شکل (1-1): یک گراف کامل با 6 گره و 30 زوج مبدأ/مقصد (Daskin, 1995)
اگر ما یک گره را به عنوان محور تعیین کنیم و همه‌ی گره‌های دیگر را به آن متصل کنیم، آنگاه تنها (1- N)2 اتصال را باید برای خدمت دادن به همه‌ی زوج‌های مبدأ/مقصد پوشش دهیم. شکل (1-1) چنین شبکه‌ای را با 6 گره (6=N) نشان می‌دهد. در این شبکه اگر خدمت حمل‌و‌نقلی داشته باشیم، با داشتن 18 خودرو و دانستن اینکه با هر خودرو در هر روز 5 زوج مبدأ/مقصد را نسبت به حالت شبکه‌ی کامل متصل می‌توانیم خدمات دهیم، آنگاه دقیقاً 46 گره را روزانه می‌توانیم خدمات‌رسانی کنیم.
در نتیجه با منابع حمل‌و‌نقل ثابت، شهرهای بیشتری را با شبکه‌ی محور می‌توانیم خدمات‌دهی کنیم.
شکل (1-2): یک شبکه‌ی تک محور با 6 گره و 30 زوج مبدأ/مقصد (Daskin, 1995)
عیب سیستم فوق (برای همه‌ی گره‌ها بجز گره‌ی محور) این است که بیش از یک جابجایی برای رفتن از مبدأ به مقصد لازم است، زیرا برای رفتن از هر گره‌ی غیر محور به گره‌ی غیر محور دیگر حتماً باید از گره‌ی محور عبور کنیم.
شکل (1-3): مثالی از یک شبکه‌ی 3 محور (Daskin, 1995)
در شبکه‌های چند محور، نوعاً فرض می‌کنیم که همه‌ی محورها به طور مستقیم با یکدیگر اتصال دارند و گره‌های غیر محور به یک محور ساده اتصال دارند. شکل (1-3) چنین شبکه‌ای را با 15 شهر که دارای 3 محور است، نشان می‌دهد. تعداد مسافر یا مقدار محموله‌های جابجا شده در اتصالات محور به محور از اتصالات محور به غیر محور یا غیر محور به محور بیشتر است. به طور مثال در شکل (1-3) اگر جریان بین هر زوج مبدأ/مقصد 10 واحد باشد (مسافر یا تن)، آنگاه 140 واحد جریان بین هر شهر غیر محور و محوری که به هم متصل هستند برقرار است، درحالی‌که بین هر دو محور 250 واحد جریان داریم.
در مسائل مکان‌یابی محور معمولاً تعدادی گره با میزان تقاضاهای متناظر وجود دارد که جریان بین این گره‌ها در حال انتقال است. در مدل تخصیص ساده‌ی مکان‌یابی محور تعدادی از گره‌ها به عنوان محور انتخاب می‌شوند و گره‌های دیگر یعنی گره‌های غیر محور (میله) هر کدام تنها به یک محور متصل می‌باشند. در این مدل هیچ‌گونه ارتباط مستقیمی بین گره‌های غیر محور وجود ندارد و جریان تنها از طریق محورهای مواصلاتی انتقال می‌یابد و از طریق اتصال محورها به همدیگر جریان در سراسر شبکه توزیع می‌گردد.
در مدل تخصیص چندگانه نیز همانند حالت تخصیص ساده بین گره‌های غیر محور اتصالی برقرار نیست و جریان گره‌های غیر محور از طریق محورها انتقال می‌یابد اما با این تفاوت که در اینجا گره‌های غیر محور مجازند تا با بیش از یک محور در ارتباط باشند و از طریق آن‌ها جریان را به گره‌های دیگر شبکه برسانند.
از دیگر دلایل استفاده از محور می‌توان به این اشاره کرد که به صرفه نیست (بسیار پر‌هزینه است) که بین هر گره مسیر مستقیم ایجاد کرد. برای مثال فرض کنید که در یک شبکه‌ی ارتباطی اعم از شبکه‌ی راه یا شبکه‌های رایانه‌ای بخواهیم بین هر یک از گره‌ها مسیر مستقیم ایجاد کنیم (de Camargo et al., 2006).
یکی از مزایای استفاده از محور این است که با ایجاد مسیرهای باکیفیت‌تر بین محورها از فواید صرفه‌جویی در مقیاس بهره‌مند می‌شویم.
همان شبکه‌های ارتباطی را در نظر بگیرید، وقتی در شبکه‌ی راه‌ها بین دو محور ارتباط زیادی وجود دارد به صرفه است که بین آن دو آزادراه چند خطه ایجاد کرد که در این صورت سرعت وسایل حمل‌و‌نقل بیشتر و سوخت مصرفی کمتر می‌شود که صرفه‌جویی در هزینه و زمان را به همراه خواهد داشت. برای مثال می‌توان به تهران و قم به عنوان دو محور اشاره کرد که بین این دو محور یک آزاد‌راه وجود دارد. در مورد شبکه‌های رایانه‌ای هم بین دو محور از خطوط فیبر نوری استفاده می‌شود که با توجه به میزان ارتباط بالای بین دو محور، به صرفه است درحالی‌که این کار اگر بین تمامی گره‌ها انجام شود توجیه اقتصادی نخواهد داشت.
1-2-2. انواع کاربرد‌های مسئله‌ی مکان‌يابی محور
همان طور که اشاره شد مسائل مکان‌یابی محور کارکردها و کاربردهای وسیع و گوناگونی در صنعت امروزه‌ی دنیا دارد که در ادامه در مورد انواع کاربردهای مسئله‌ی مکان‌یابی محور به بحث می‌پردازیم.
1-2-2-1. خطوط هوايی و فرودگاه‌ها
Toh and Higgins (1985), Aykin (1993), Shaw (1993), Aykin (1995), Jaillet et al. (1996), Bania et al. (1998), Sasaki et al. (1999), Martin and Roman (2003), Adler and Hashai (2005).
در مقاله‌ی Adler and Hashai (2005) خطوط و جابجایی هوایی با توجه به سیاست آسمان باز در خاورمیانه مورد بررسی قرار گرفت، جالب این است که در نتیجه‌ی این تحقیق به ترتیب قاهره، تهران، استانبول و ریاض به عنوان مکان‌های بهینه‌ی فرودگاه‌های محور به دست آمده‌اند و نامی از دُبی در آن دیده نمی‌شود. درحالی‌که هم اکنون دُبی به عنوان یکی از محور‌های بزرگ منطقه مورد توجه است و در آینده نیز پیش‌بینی می‌شود که دوحه (پایتخت کشور قطر) به عنوان محور مواصلاتی انتخاب شود. این نکته بیانگر آن است که در عمل مسائل سیاسی و اقتصادی بر بهتر بودن موقعیت مکانی غلبه کرده است.
1-2-2-2. صنعت حمل‌و‌نقل و باربری
Don et al. (1995), Lumsdenk et al. (1999), Aversa et al. (2005), Baird (2006), Cunha and Silva (2007), Yaman et al. (2007), Eiselt (2007).
در مقاله‌ی Eiselt (2007) به بحث مکان‌یابی محل دفن زباله به عنوان محور با توجه به ایستگاه‌های حمل‌و‌نقل زباله پرداخته شده است.
1-2-2-3. خدمات تحويل پستی و شرکت‌های تحويل سريع بسته
Kuby and Gray (1993), Krishnamoorthy et al. (1994), Ernst and Krishnamoorthy (1996), Ebery et al. (2000).
1-2-2-4. سيستم‌های ارتباط از راه دور و شبکه‌های تحويل پيام
Lee et al (1996) و Klincewicz (1998) در دو مقاله‌ی خود به این بحث پرداخته‌اند.
1-2-2-5. خدمات اضطراری
Hakimi (1964) و Berman (2007). در مقاله‌ی اخیر به مکان‌یابی محل استقرار بالگرد به عنوان محور برای ارائه‌ی خدمات به بیمارستان‌ها و مجروحان پرداخته شده است.
1-2-2-6. انبارهای زنجيره‌ای زنجيره تأمين
Campbell et al (2002) به بررسی انبارهای زنجیره‌ای زنجیره تأمین شرکت‌های بزرگی چون وال-مارت4 پرداخته‌اند.
1-2-2-7. شرکت‌های توليدی در زمينه‌ی جابجايی صحيح
ممکن است به عنوان مثال یک کارخانه‌ی مونتاژ بزرگ خواسته باشد مکان‌های بهینه‌ای برای انبار مواد اولیه تعیین کند تا تمامی قسمت‌های مونتاژ بتوانند به طور کارا مواد اولیه را دریافت کنند.
1-2-3. مثال‌های عملی از کاربرد مسئله‌ی مکان‌يابی محور
(1) شبکه‌ی راه‌آهن مجارستان که بوداپست پایتخت این کشور به عنوان محور انتخاب شده است.
(2) دو خط هوایی بزرگ آمریکا با ادارات مرکزی در آتلانتا و شیکاگو دارای شبکه‌ی محور هستند.
(3) فرودگاه دبی، محور بسیاری از پروازهای خارجی در خاورمیانه است.
(4) Aversa et al. (2005) یک مدل برنامه‌ریزی مختلط برای انتخاب یک بندر محور در ساحل شرقی آمریکای جنوبی از میان یک مجموعه‌ای از 11 بندر که به تقاضای منطقه‌ای برای حمل‌و‌نقل خدمات می‌دهند، ساختند. در این مطالعه بندر‌های برزیل، آرژانتین و اروگوئه به علاوه بندر‌های مبدأ/مقصد مختلف در جهان مورد بررسی قرار گرفتند. مدل شامل 3883 متغیر تصمیم و 4225 محدودیت شد. پس از حل مدل، بندر سانتوز در برزیل به عنوان بندر محور تعیین شد.
1-2-4. بهينه‌سازی استوار شبکه‌های لجستيک در شرايط غير‌قطعی
لجستیک، همان طور که به طور گسترده توسط Riopel et al. (2005) تعریف شده است «آن بخشی از فرآیند زنجیره تأمین است که جریان موثر پیشرو و معکوس را برنامه‌ریزی، ذخیره‌ی کالا‌ها را اجرا و عملکرد را کنترل می کند و جهت برآورده کردن نیاز‌های مشتری اطلاعات مربوط بین نقاط مبدأ و مصرف را تأمین می‌کند». خب واضح است که برنامه‌ریزی و مدیریت این طیف گسترده از فرآیند‌ها، بسیار پیچیده خواهد بود. به عبارتی دیگر تصمیم‌گیرندگان بایستی تمرکز خود را بر مدیریت هر خطر احتمالی سیستم لجستیک، از همان ابتدای کار یعنی فاز طراحی، بگذارند. در نتیجه شرایط پیش‌بینی‌نشده در مدت زمان پیاده‌سازی شاید کمتر منجر به بی‌اعتباری برنامه‌ی طراحی اولیه و یا مختل نمودن عملکرد اهداف شود.
یکی از دشواری‌های اصلی مسائل مدیریت لجستیک این است که چگونه عدم قطعیت آینده را به طور خردمندانه‌ای در مرحله‌ی مدل‌سازی در نظر بگیریم. در دنیای واقعی وجود اطلاعات و داده‌های شلوغ، ناقص و نادرست واقعیتی اجتناب‌ناپذیر است که در بسیاری از موارد بر کارایی فرآیند شبکه‌ی لجستیک (به عنوان مثال، مکان‌یابی مراکز لجستیک، طرح‌های توزیع و تقاضاهای مشتری) در مرحله‌ی پیاده‌سازی تأثیر می‌گذارند، بنابراین مدل‌سازی نادرست این عدم قطعیت‌های ذاتی ممکن است منجر به عملیاتی نشدن این طرح‌ها شود. همچنین یکی از نقش‌های حیاتی مدیران لجستیک به نحوه‌ی برخورد با محیط‌های شلوغ و غیر‌قطعی برمی‌گردد که به منظور دستیابی به شبکه‌هایی موثر با برنامه‌ریزی مجدد کمتر است.
اهمیت این موضوع باعث رشد قابل‌توجهی در تعداد مطالعات مربوط به عدم قطعیت در زنجیره تأمین، شبکه‌های لجستیک و روش‌های مدل‌سازی آن‌ها جهت بهینه‌سازی طراحی و عملکرد شبکه‌های تحت عدم قطعیت شده است.
در مطالعات و برنامه‌ریزی لجستیک از دو روش کلی برای مواجهه با عدم قطعیت استفاده می‌شود:
1- روش‌های واکنشی: آن‌ها پس بهینه هستند، در نتیجه هیچ مکانیزم مستقیمی جهت کنترل حساسیت تصمیمات گرفته‌شده در مورد عدم قطعیت ارائه نمی‌کنند. آنالیز حساسیت در این گروه طبقه‌بندی می‌شود.
2- روش‌های کنشی: بر‌خلاف گروه قبلی، این شیوه‌ها برای جواب‌های حاصلی به کار می‌روند که دارای حساسیت کمتری نسبت به عدم قطعیت هستند. برنامه‌ریزی تصادفی یک روش متعارف بهینه‌سازی با داده‌های احتمالی است که به این گروه تعلق دارد.
یکی از نقصان‌های برنامه‌ریزی تصادفی محدودیت آن در مدیریت اولویت‌ها و یا مغایرت ریسک تصمیم‌گیرندگان است. اخیراً یک برنامه‌ریزی بهبودیافته به نام برنامه‌ریزی استوار با توانایی مقابله با این نقصان توسعه داده شده است. با توجه به شایستگی‌های انعطاف‌پذیر مدل‌سازی اجازه داده‌شده در بهینه‌سازی استوار، کم‌کم انتظار می‌رود که این روش بتواند یک روشگان معتبر برای مسائل لجستیک غیر‌قطعی در دنیای واقعی ارائه دهد. به عبارتی دیگر، سادگی پیاده‌سازی این روش تصمیم‌گیرندگان را قادر می‌سازد تا سیستم لجستیک را بدون داشتن رویه‌های برنامه‌ریزی پیچیده، کنترل و مدیریت کنند.
1-3. بيان مسئله و اهداف تحقيق
در این پایان‌نامه مدل‌های خاصی از مسائل مکان‌یابی محور تحت عنوان مدل‌های تخصیص ساده و چندگانه‌‌ی ظرفیت محدود بررسی ‌شده‌اند. برای انجام این مهم مدل‌ها را بر اساس آنچه که در مقالات پیشین ارائه شده است، در اینجا نیز آورده‌ایم و آخرین تغییرات موجود در مرور ادبیات را بر روی آن‌ها اعمال کرده‌ایم. در این مدل‌ها بر اساس نوع الگوی آن‌ها که ساده و چندگانه است، گره‌های غیر محور را به محورهای مواصلاتی بهینه‌ای که مدل پس از حل آن‌ها را انتخاب می‌کند، وصل می‌کنیم. همان طور که می‌دانید هر زمان که بحث جریان، هزینه‌ی راه‌اندازی محور و ظرفیت هر گره پیش کشیده می‌شود، عدم قطعیت نیز در مدل مطرح‌ شده و اثر غیر‌قطعی بودن این پارامترهای یادشده نیز بررسی می‌شود.
به دلیل اینکه نوع الگوی تخصیص گره‌ها به محورهای بهینه‌ی منتخب، ظرفیت محدود انتخاب شده است، تنها اثر پارامترهایی چون ظرفیت هر گره و هزینه‌ی راه‌اندازی مربوط به هر محور را غیر‌قطعی در نظر گرفته و با استفاده از معیار حداقل حداکثر تأسف که نوع خاصی از رویکرد بهینه‌سازی استوار است به بررسی این مدل بر روی مجموعه داده‌های هواپیمایی ایران (IAD) می‌پردازیم.
مهم‌ترین هدف این تحقیق تخصیص بهینه‌ی ساده و چندگانه‌ی گره‌های غیر محور به گره‌های محور با در نظر گرفتن عدم قطعیت در پارامترهای ظرفیت و هزینه‌ی راه‌اندازی هر محور است. در کنار این هدف اصلی، هدف‌های فرعی دیگری نیز مانند بررسی هزینه‌های انتقال بین محورهای منتخب و اینکه با افزایش ضریب هزینه‌ی انتقال بین محورها چه تأثیری در انتخاب شدن گره‌های محور می‌توان مشاهده کرد، صورت گرفته است.
1-4. ضرورت انجام تحقيق و کاربردهای آن
همان طور که در قسمت قبلی نیز اشاره شد مسئله‌ی مورد بررسی در این پایان‌نامه الگوی تخصیص بهینه‌‌ی ساده و چندگانه‌ی ظرفیت محدود مسئله‌ی مکان‌یابی محور مبتنی بر رویکرد بهینه‌سازی استوار است. از آنجایی که در مقالات پیشین به بررسی این مدل‌ها در حالت ظرفیت محدود و در حضور پارامترهای غیر‌قطعی پرداخته نشده است، لازم است تا نتایج این مدل‌ها در حالت ظرفیت محدود و در حضور پارامترهای غیر‌قطعی چون هزینه‌ی راه‌اندازی محور و ظرفیت هر گره بیشتر مورد تجزیه و تحلیل قرار گیرد.
با نگاهی دقیق به مرور ادبیات متوجه می‌شویم که تعداد مقالات زیادی به تخصیص ساده و چندگانه‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی چه در حالت قطعی و چه در حالت غیر‌قطعی پرداخته‌اند اما در زمینه‌ی ظرفیت محدود این مسائل در حالت غیر‌قطعی مقاله‌ای دیده نمی‌شود که با استفاده از روش‌های رایج بهینه‌سازی اعم از بهینه‌سازی استوار، روش‌های فازی و … به بررسی این مسائل پرداخته شده باشد.
روشگان این پایان‌نامه بر روی داده‌های هواپیمایی فرودگاه‌های مختلف آزمایش شده است و محورهای بهینه در هر بار آزمایش انتخاب شده و به تصویر کشیده شده‌اند. همان طور که همه می‌دانیم هر فرودگاهی به نوبه‌ی خود دارای محدودیت‌هایی در سرویس‌دهی و ارائه‌ی خدمات به مشتریانش است. محدودیت‌هایی چون ظرفیت تقاضا، تعداد ناوگان‌های حمل‌و‌نقل، موقعیت جغرافیایی و استراتژیکی محل احداث فرودگاه و … در انتخاب محورهای مواصلاتی در بیشتر فرودگاه‌های کشور وجود دارند که در اکثر موارد در انتخاب محورهای مواصلاتی از این عامل‌های تعیین‌کننده چشم‌پوشی شده و فرودگاه‌ها در مکان‌های بسیار نامناسبی احداث ‌شده‌اند و این امر موجب نارضایتی مشتریان و کاهش کارایی و سود‌دهی فرودگاه‌ها شده ‌است.
1-5. ساختار پايان‌نامه
در فصل اول این پایان‌نامه به بررسی تعاریفی کلی از حوزه‌ی مورد تحقیق و کاربردهای نظریه و عملی آن پرداخته می‌شود و ضرورت‌های انجام تحقیق و اهداف و کاربردهای مهم آن در دنیای واقعی نشان داده‌ می‌شود. در فصل دوم به مرور ادبیات موجود در مقالات پیشین پرداخته و مقالات از منظرهای مختلف دسته‌بندی و طبقه‌بندی می‌شود و شکاف موجود در تحقیق به خوبی تشریح می‌شود. در فصل سوم مدل‌های ریاضی موجود در این زمینه معرفی شده و پارامترها و متغیرهای تصمیم‌گیری نیز ارائه خواهند شد. در فصل چهارم نتایج مدل‌های مختلف چه در حالت قطعی و چه در حالت غیر‌قطعی بررسی شده و به تفسیر در مورد آن‌ها به بحث خواهیم پرداخت. در فصل پنجم نیز خلاصه‌ای از فصول قبلی را آورده و برای انجام تحقیق‌های آینده نیز پیشنهاد‌هایی ارائه می‌گردد.
فصل دوم
مروری بر ادبیات تحقیق
2-1. مقدمه
2-2. طبقه‌بندی مقالات از مناظر مختلف
2-3. مروری بر ادبیات بهینه‌سازی استوار
2-4. نتیجه‌گیری از تحقیقات گذشته و بیان ایده‌های تحقیق
2-1. مقدمه
در این فصل به مرور ادبیات مقالات پیشین در باب مدل‌های تخصیص ساده و چندگانه‌ی مسئله‌ی مکان‌یابی ‌محور ظرفیت محدود و نامحدود در حالت‌های قطعی و غیر‌قطعی می‌پردازیم و خلاصه‌ای از کارهای انجام‌شده در مقالات مذکور را به تصویر می‌کشیم.
2-2. طبقه‌بندی مقالات از مناظر مختلف
برای بررسی هر چه دقیق‌تر مقالات ارائه‌شده در خصوص مدل‌های موجود در مرور ادبیات و مشخص کردن موضوعات مورد علاقه‌ی محققان در این زمینه 2 نوع دسته‌بندی در مرور ادبیات انجام می‌دهیم: (1) مروری بر ادبيات مدل‌های ساده و چندگانه در حالت قطعی و (2) مروری بر ادبيات مدل‌های تخصيص ساده و چندگانه در حالت غیر‌قطعی.
2-2-1. مدل‌های قطعی تخصيص ساده و چندگانه‌ی مسئله‌ی مکان‌يابی محور
اولین روش‌های ابتکاری برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه توسطO’Kelly (1987) ارائه شده است. در هر دوی روش‌های ابتکاری او، تمامی انتخاب‌های ممکن مکان‌های p-محور به حساب می‌آیند. در روش ابتکاری اول (HEUR1)، گره‌های تقاضا به نزدیک‌ترین محور اختصاص ‌یافته‌اند و در روش ابتکاری دوم (HEUR2)، بر اساس مقدار تابع هدف، بهترین دو محور نزدیک به گره‌ی تقاضا انتخاب می‌شوند. از روش‌های ابتکاری برای حل مجموعه داده‌های CAB5 استفاده شده است.
Klincewicz (1991, 1992) در مقاله‌های خود روش‌های ابتکاری متنوعی را برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه توسعه داده است. Klincewicz (1991) یک روش ابتکاری مبادله‌ای بر اساس بهبود مکانی که هر دوی رویه‌های ساده و مضاعف مبادله را لحاظ می‌کند، ارائه کرده است. مقایسه‌ی او نشان داد که این روش‌های ابتکاری نسبت به روش‌های ابتکاری خوشه‌ای و روش ابتکاری پیشنهادی در O’Kelly (1987) دارای برتری است. Klincewicz (1992) یک روش ابتکاری جستجوی ممنوعه6 و یک روش ابتکاری جستجوی حریصانه تصادفی (GRASP)7 پیشنهاد کرد که در هر دوی این روش‌ها گره‌های تقاضا به نزدیک‌ترین محورشان اختصاص ‌یافته‌اند. در هر دو مقاله‌ی Klincewicz, 1991, 1992)) از مجموعه داده‌های CAB و یک مجموعه داده‌ی بزرگ‌تر با 52 نقطه‌ی تقاضا و بالغ بر 10 محور جهت آزمایش عملکرد این روش‌های ابتکاری استفاده شده است.Campbell (1992) اولین فردی بود که تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور میانه را به عنوان یک برنامه‌ی عدد صحیح خطی مدل‌سازی کرد.
در مسئله‌ی p-محور میانه از هزینه‌های ثابت راه‌اندازی تسهیلات صرف‌نظر شده است (Alumur and Kara (2008)). در مقاله‌ی O’Kelly (1992a) نویسنده آن، تخصیص ساده‌ی مسئله‌ی مکان‌یابی محور را با هزینه‌های ثابت معرفی کرده‌ که تعداد محورها را به یک متغیر تصمیم‌گیری تبدیل می‌کند. او این مسئله را به عنوان یک برنامه‌ی عدد صحیح درجه دو مدل‌سازی کرده است. در این روش از آنجایی که تعداد محورهای انتخاب‌شده از قبل مشخص نیست، علاوه بر داشتن حالت‌های تخصیص چندگانه و ساده می‌توان به گونه‌های ظرفیت محدود و نامحدود این مسائل نیز دسترسی پیدا کرد.
Skorin-Kapov and Skorin-Kapov (1994) روش ابتکاری جستجوی ممنوعه‌ی دیگری را برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه ارائه کرده‌اند. آن‌ها با استفاده از مجموعه داده‌های CAB نتایج روش ابتکاری خود را با دو روش ابتکاری O’Kelly (1987) یعنی (HEUR1 و HEUR2) و جستجوی ممنوعه‌ی Klincewicz (1992) مقایسه کرده‌اند. نتایج آن‌ها بهتر است اما زمان واحد پردازشگر مرکزی8 روش آن‌ها به دلیل تأکید بیشتر بر فاز تخصیص مسئله، بزرگ‌تر بود.
Campbell (1994b) اولین مدل برنامه‌ریزی خطی را برای تخصیص ساده/چندگانه‌ی ظرفیت محدود/نامحدود مسئله‌ی مکان‌یابی محور ارائه کرده است.
Campbell (1994) ادعا کرد که در غیاب محدودیت‌های ظرفیت بر روی اتصال‌ها، از آنجایی که جریان کلی برای هر زوج مبدأ/مقصد بایستی حداقل از دو محور متصل به هم گردش یابد، اگرX_ijkm دارای مقدار 0 و 1 باشد مسئله دارای جواب بهینه است. بنابراین هیچ نیازی به عدد صحیح بودن متغیر X_ijkm نیست. او همچنین تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی ‌p-محور را با آستانه‌های جریان و هزینه‌های ثابت به عنوان یک برنامه‌ی عدد صحیح خطی مدل‌سازی کرد.
Campbell (1994b) اولین مدل برنامه‌ریزی عدد صحیح خطی را برای تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه ارائه کرد. مدل او تعداد (n^4+n^2+n) متغیر داشت که تعداد (n^2+n) متغیر آن دوتایی بودند و تعداد (n^4+〖2n〗^2+n+1) محدودیت خطی داشت. او همچنین مسئله‌ را با آستا‌نه‌ی جریان مدل‌سازی کرد و مقدار حداقل جریان مورد نیاز برای سرویس‌دهی به هر اتصال را تعیین کرد. هنگامی‌که آستانه‌ی جریان در حداکثر مقدار خود هستند، هر گره‌ی تقاضا به یک تک محور اختصاص داده شد و مدل به تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه تقلیل یافت.
Aykin (1994) حالت ظرفیت محدود مسئله‌ی مکان‌یابی محور را با هزینه‌های ثابت که در آن محورها دارای ظرفیت محدودند، بررسی کرده‌ است. او مسئله را چنان مدل‌سازی کرده است که اتصالات مستقیم (بین گره‌های غیر محور) نیز مجازند. او یک الگوریتم انشعاب و تحدید پیشنهاد کرده که کران‌های پایین توسط ساده‌سازی لاگرانژی به دست می‌آیند. Aykin (1995a) مسئله‌ی مشابهی را با هزینه‌های ثابت و تعداد محورهای داده‌شده جهت مکان‌یابی تجزیه و تحلیل کرده است. او دو سیاست انتخاب محور را که سیاست‌های اکید و غیر اکید (اتصال مستقیم اجازه داده‌شده) نامیده، مقایسه کرده است. او یک الگوریتم شمارشی9 و یک روش ابتکاری شبیه‌سازی تبرید10 بر اساس روش ابتکاری حریصانه مبادله‌ای پیشنهاد کرده است.
O’Kelly et al. (1995) یک فن کران پایین بر اساس خطی سازی تابع هدف درجه دوم که مسافت‌ها جهت برقراری نامساوی مثلثی فرض شده‌اند، برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه ارائه کرده‌اند. آن‌ها با استفاده از این روش نشان داده‌اند که روش جستجوی ممنوعه‌ی Skorin-Kapov and Skorin-Kapov (1994) برای مسائل کوچک‌تر (10 الی 15 گره) به طور متوسط دارای شکاف 3/3 درصد و برای مسائلی با 20 الی 25 گره به طور متوسط دارای شکاف 9/5 درصد است.
سپس Skorin-Kapov et al. (1996) با ساده‌سازی برنامه‌ریزی خطی مدل Campbell (1994b) جواب‌های بسیار کوچک‌تری به دست آوردند. آن‌ها مدل جدیدی برای تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه ارائه دادند. با تغییری که آن‌ها در مدل ایجاد کردند تعداد متغیرها به (n^4+n^2) کاهش یافت که از این تعداد، (n^2) متغیر دوتایی بودند و تعداد محدودیت‌های خطی نیز به (〖2n〗^3+n^2+n+1) محدودیت کاهش یافت. بر اساس اطلاعات ما آن‌ها، اولین تلاش‌ها را برای حل بهینه‌ی مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه انجام دادند. آن‌ها با استفاده از جواب‌های بهینه‌ی مجموعه داده‌های CAB، بهینگی راه‌ جستجوی ممنوعه‌ی به دست آمده در مقاله‌ی Skorin-Kapov and Skorin-Kapov (1994) را اعتبار ببخشند.
مبرهن است که جواب‌های مدل تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور میانه کران پایینی را برای جواب بهینه‌ی مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه مهیا می‌کند (Campbell, 1996). با استفاده از این ایده، Campbell (1996) دو روش ابتکاری برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه پیشنهاد داده است. این دو روش ابتکاری (MAXFLO و ALLFLO) جواب‌های مشتق شده از راه‌ مدل تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور میانه برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه هستند. در این روش‌های ابتکاری، تخصیص‌ها مطابق با نقش‌های متفاوت صورت گرفته اما تصمیم‌های مکانی همان تصمیم‌های قبلی هستند.
Ernst and Krishnamoorthy (1996) مدل برنامه‌ریزی خطی عدد صحیح جدیدی را برای مسئله‌ی تخصیص ساده ارائه کردند که دارای محدودیت‌ها و متغیرهای به مراتب کمتری بود و توانایی حل مسائل بزرگ‌تری را نیز داشت. آن‌ها انتقال‌های بین محور را به عنوان مسئله‌ی جریان چند محصولی تلقی کردند که در آن هر محصول بیانگر جریان ترافیک نشأت‌گرفته از یک گره‌ی خاص است. نویسندگان این مقاله چگونگی استفاده‌ی پست استرالیا (AP)11 از ضریب‌های کاهشی مختلف در جمع‌آوری و توزیع را مشاهده و مدل کردند و برای هر واحد هزینه‌ی جمع‌آوری و توزیع محصول یک ضریب کاهشی را اختصاص دادند (δ برای ضریب کاهشی توزیع و χ برای ضریب کاهشی جمع‌آوری محصول).
مدل آن‌ها دارای (n^3+n^2) متغیر بود که از این تعداد، (n^2) متغیر دوتایی بودند و تعداد محدودیت‌های خطی نیز (〖2n〗^2+n+1) بود. آن‌ها یک روش ابتکاری شبیه‌سازی تبرید را توسعه و نشان داده‌اند که روش آن‌ها از هر دو منظر کیفیت جواب و زمان محاسباتی، با روش ابتکاری جستجوی ممنوعه‌ی Skorin-Kapov and Skorin-Kapov (1994) قابل مقایسه است. آن‌ها از این کران بالای به دست آمده از روش ابتکاری شبیه‌سازی تبرید برای توسعه‌ی راه حل روش انشعاب و تحدید بر پایه‌ی برنامه‌ریزی خطی استفاده کردند. آن‌ها هر دوی روش‌های ابتکاری خود و الگوریتم انشعاب و تحدید را بر روی مجموعه داده‌های AP و CAB آزمایش کردند، اما آن‌ها قادر به حل مسائلی با بیش از 50 گره نبودند.
O’Kelly et al. (1996) با ارائه‌ی داده‌های برابر جریان مدلی پیشنهاد کردند که باعث کاهش اندازه‌ی مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه شد. هنوز هم مدل جدیدی که آن‌ها معرفی کرده‌اند در بیشتر مقالات مورد استفاده قرار می‌گیرد. مهم‌ترین چیزی که آن‌ها در مقاله‌ی خود مطرح کردند، حساسیت جواب‌ها به ضریب کاهشی بین محورها (α) بود.
Campbell (1996) یک روش ابتکاری حریصانه-مبادله‌ای را برای مدل تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور پیشنهاد کرده‌ است.Skorin-Kapov et al. (1996) یک مدل عدد صحیح مختلط جدید پیشنهاد کردند که در آن دو محدودیت مدل اولیه‌ی Campbell (1992) با حالت تجمعی‌شان جایگزین شده‌اند. این مدل دارای (n^4+n) متغیر است که تعداد (n) آن دوتایی است و نیاز به (〖2n〗^3+n^2+1) محدودیت خطی دارد. این مدل باعث ساده‌سازی‌های برنامه‌ریزی خطی فشرده‌تری شد و تولید نتایجی یکپارچه در تقریباً تمام مواردی که از مجموعه داده‌های CAB استفاده شده است، نمود. در مواردی که ساده‌سازی برنامه‌ریزی خطی راه‌حل یکپارچه‌ای به دست نمی‌دهد، نویسندگان این مقاله درخت جستجوی شمارش ضمنی را برای دستیابی به جواب‌های بهینه به کار بستند. این درخت جستجو معمولاً گره‌های درختی کمتر را شامل می‌شود.
Smith et al. (1996) مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه را برای شبکه‌ی عصبی اصلاح‌شده‌ی Hopfield ترسیم کرده‌اند. آن‌ها از مدل برنامه‌ریزی عدد صحیح درجه دوم O’Kelly (1987) استفاده کرده‌اند، زیرا این مدل تعداد کمتری متغیر و محدودیت دارد. آن‌ها نتایجشان را بر روی مجموعه داده‌های CAB با روش ابتکاری شبیه‌سازی تبرید Ernst and Krishnamoorthy (1996) و بسته‌ی تجاری نرم‌افزار GAMS با حل کننده‌ی MINOS-5 مقایسه کرده‌اند. آن‌ها پی بردند که عملکرد GAMS/MINOS-5 به طور قابل‌توجهی ضعیف‌تر از دیگر روش‌هاست زیرا که این نرم‌افزار برای کمینه کردن توابع محدّب طراحی شده است؛ همچنین آن‌ها پی بردند که روش شبکه‌ی عصبی Hopfield به صورت اثربخشی با شبیه‌سازی تبرید قابل محاسبه است.
برای مدل تخصیص چندگانه‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی محور، Klincewicz (1996) یک الگوریتم بر اساس فن‌های صعود دوتایی و تنظیم دوگانه درون طرح انشعاب و تحدید ارائه کرده‌ است. محورها از مجموعه‌ی از قبل تعیین‌شده‌ی محورهای بالقوه انتخاب شده و الگوریتم بر روی مجموعه داده‌های CAB آزموده شده‌اند.
Sohn and Park (1997) مدل تخصیص ساده‌ی مکان‌یابی دو محور میانه را بررسی کرده‌اند. آن‌ها نشان داده‌اند که این مسئله را در حالتی که مکان‌های محور ثابت هستند، می‌توان در زمان چندجمله‌ای حل نمود. آن‌ها یک مدل برنامه‌ریزی خطی را برای مسئله‌ی تخصیص ساده با مکان‌های محور ثابت ارائه کرده و نشان داده‌اند که مسئله را می‌توان به مسئله‌ی حداقل برش تغییر شکل داد. از آنجایی که (n^2) راه برای انتخاب مکان‌های محور وجود دارد، مسئله‌ی مکان‌یابی دو محور را می‌توان در زمان چندجمله‌ای حل کرد.
Ernst and Krishnamoorthy (1998b) الگوریتم انشعاب و تحدید دیگری را برای تخصیص ساده پیشنهاد داده‌اند که مسائل کوتاه‌ترین مسیر را جهت به دست آوردن کران‌های پایین حل می‌نمود. برخلاف الگوریتم‌های انشعاب و تحدید مرسوم، الگوریتم آن‌ها به جای شروع با یک گره‌ی ریشه ساده با مجموعه‌ای از گره‌های ریشه شروع به کار می‌کرد. آن‌ها اثربخشی این الگوریتم را با مقایسه‌ی عملکردش با نتایج تهیه‌شده در Ernst and Krishnamoorthy (1996) بر روی مجموعه داده‌های AP و CAB محاسبه کرده‌اند. آن‌ها ادعا کرده‌اند که این الگوریتم جدید برای مقادیر کوچک p بسیار سریع‌تر عمل می‌کند و به حافظه‌ی اشغال‌شده‌ی کمتری نسبت به الگوریتم انشعاب و تحدید بر پایه‌ی برنامه‌ریزی خطی ارائه‌شده در Ernst and Krishnamoorthy (1996) نیاز دارد. تا این تاریخ بزرگ‌ترین مسائل تخصیص ساده به صورت بهینه با این الگوریتم حل شده است. نویسندگان این مقاله مسائلی با 100 گره و 2 الی 3 محور را به ترتیب در حدود 228 و 2629 ثانیه حل نموده‌اند. با این وجود آن‌ها هنوز هم



قیمت: تومان

دسته بندی : پایان نامه ارشد

پاسخ دهید