خلاصه پایان نامه تخصیص ساده و چندگانهی ظرفیت محدود مسئله‌ی مکان یابی محور مبتنی بر رویکرد بهینه سازی استوار
پایان‌نامه برای دریافت درجه کارشناسی ارشد «M.Sc»
رشته: مهندسی صنایع
گرایش: مدیریت سیستم و بهره‌وری
زمستان 1392
چکیده
مسئله‌ی مکان‌یابی محور یکی از حوزه‌های نوظهور و تازه رونق گرفته در نظریه مکان‌یابی تسهیلات کلاسیک است که بایستی مدیران زنجیره تأمین سازمان‌ها و شرکت‌ها در هنگام طراحی شبکه‌ی زنجیره تأمین خود به عنوان بخشی از فرآیند تصمیم‌گیری، توجه ویژه‌ای به این مسائل داشته باشند. در برنامه‌ریزی استراتژیک، ممکن است تصمیم‌ها اثر طولانی مدتی داشته باشند و پیاده‌سازی برنامه‌ها زمان قابل‌توجهی را بگیرد. همچنین، داده‌های ورودی از قبل دقیقاً شناخته‌شده نباشند. از این رو، در تصمیمات گرفته‌شده بایستی عدم قطعیت در نظر گرفته شود. عدم قطعیت را می‌توان به عنوان خاصیتی از سیستم در نظر گرفت که توصیف‌کننده‌ی نقص دانش بشر درباره‌ی یک سیستم و وضعیت پیشرفت آن، است. در این تحقیق مدل‌های خاصی از مسائل مکان‌یابی محور تحت عنوان تخصیص ساده و چندگانه در نظر گرفته شده است. ابتدا مدل عمومی حالت‌های تخصیص ساده و چندگانهی ظرفیت محدود معرفی‌شده و در ادامه مدل پیشنهادی این تحقیق برای نحوه‌ی برخورد با عدم قطعیت پارامترها که شامل حالت‌های تخصیص ساده و چندگانهی ظرفیت محدود مکان‌یابی محور مبتنی بر رویکرد بهینه‌سازی استوار است، ارائه می‌شود. در انتها عدم قطعیت پارامترهایی مانند هزینه‌ی ثابت راه‌اندازی محور و ظرفیت مربوط به هر محور بر روی مجموعه داده‌های هواپیمایی ایران IAD[1] با استفاده از رویکرد [2]Minimax 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.24[3] به دست می‌آوریم. سپس با توجه به حساسیت جواب‌های مدل نسبت به پارامترهای هزینه‌ی ثابت راه‌اندازی و ظرفیت هر محور از روش بهینه‌سازی استوار استفاده کرده و مدل‌های تخصیص ساده و چندگانهی ظرفیت محدود را با نرم‌افزار 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 گره را می‌توانیم خدمات دهیم.
Abstract
فهرست پایان نامه تخصیص ساده و چندگانهی ظرفیت محدود مسئله‌ی مکان یابی محور مبتنی بر رویکرد بهینه سازی استوار
چکیده...............................................................................................................................................................................
مقدمه................................................................................................................................................................................
فصل اول: کلیات تحقیق............................................................................................................................
1-1. مقدمه.......................................................................................................................................................................
1-2. تعاریف کلی از حوزه تحت بررسی.........................................................................................................................
1-2-1. مکان‌یابی محور...................................................................................................................................................
1-2-2. انواع کاربردهای مسئله‌ی مکان‌یابی محور...........................................................................................................
1-2-2-1. خطوط هوایی و فرودگاه‌ها.............................................................................................................................
1-2-2-2. صنعت حمل‌و‌نقل و باربری............................................................................................................................
1-2-2-3. خدمات تحویل پستی و شرکت‌های تحویل سریع بسته.................................................................................
1-2-2-4. سیستم‌های ارتباط از راه دور و شبکه‌های تحویل پیام...................................................................................
1-2-2-5. خدمات اضطراری...........................................................................................................................................
1-2-2-6. انبارهای زنجیره‌ای زنجیره تأمین....................................................................................................................
1-2-2-7. شرکت‌های تولیدی در زمینه‌ی جابجایی صحیح............................................................................................
1-2-3. مثال‌های عملی از کاربرد مسئله‌ی مکان‌یابی محور.............................................................................................
1-2-4. بهینه‌سازی استوار شبکه‌های لجستیک در شرایط غیر‌قطعی.................................................................................
1-3. بیان مسئله و اهداف تحقیق......................................................................................................................................
1-4. ضرورت انجام تحقیق و کاربردهای آن...................................................................................................................
1-5. ساختار پایان‌نامه.......................................................................................................................................................
فصل دوم: مروری بر ادبیات تحقیق.........................................................................................................
2-1. مقدمه......................................................................................................................................................................
2-2. طبقهبندی مقالات از مناظر مختلف..........................................................................................................................
2-2-1. مدل‌های قطعی تخصیص ساده و چندگانهی مسئله‌ی مکان‌یابی محور...............................................................
2-2-2. مدل‌های غیر‌قطعی تخصیص ساده و چندگانهی مسئله‌ی مکان‌یابی محور..........................................................
2-3. مروری بر ادبیات بهینه‌سازی استوار.........................................................................................................................
2-3-1. عدم قطعیت در شبکه‌های لجستیکی...................................................................................................................
2-3-2. روش‌های بهینه‌سازی تحت عدم قطعیت............................................................................................................
2-3-3. بهینه‌سازی استوار................................................................................................................................................
2-3-3-1. مدل تأسف.....................................................................................................................................................
2-3-4. بهینه‌سازی استوار شبکه‌های لجستیکی................................................................................................................
2-3-5. چالش‌های بهینه‌سازی استوار..............................................................................................................................
2-4. نتیجهگیری از تحقیقات گذشته و بیان ایده‌های تحقیق............................................................................................
فصل سوم: مدل پیشنهادی.........................................................................................................................
3-1. مقدمه......................................................................................................................................................................
3-2. مدل‌های پیشنهادی...................................................................................................................................................
3-2-1. حالت قطعی تخصیص ساده‌ی ظرفیت محدود مسئله‌ی مکان‌یابی محور (CSAHLP).......................................
3-2-1-1. نمادها و علائم بکار رفته در مدل ریاضی.......................................................................................................
3-2-1-1-1. مجموعه‌ها..................................................................................................................................................
3-2-1-1-2. پارامترها.....................................................................................................................................................
3-2-1-1-3. متغیرهای تصمیم‌گیری...............................................................................................................................
3-2-1-2. مدل ریاضی....................................................................................................................................................
3-2-1-2-1. تابع هدف و محدودیتها..........................................................................................................................
3-2-1-2-2. تشریح تابع هدف و محدودیتها..............................................................................................................
3-2-2. حالت قطعی تخصیص چندگانهی ظرفیت محدود مسئله‌ی مکان‌یابی محور (CMAHLP)................................
3-2-2-1. نمادها و علائم بکار رفته در مدل ریاضی.......................................................................................................
3-2-2-1-1. مجموعه‌ها..................................................................................................................................................
3-2-2-1-2. پارامترها.....................................................................................................................................................
3-2-2-1-3. متغیرهای تصمیم‌گیری...............................................................................................................................
3-2-2-2. مدل ریاضی....................................................................................................................................................
3-2-2-2-1. تابع هدف و محدودیتها..........................................................................................................................
3-2-2-2-2. تشریح تابع هدف و محدودیتها..............................................................................................................
3-3. مدل رویکرد بهینه‌سازی استوار................................................................................................................................
3-3-1. تخصیص ساده....................................................................................................................................................
3-3-2. تخصیص چندگانه...............................................................................................................................................
فصل چهارم: الگوریتم حل، نتایج و تفسیر آن‌ها...................................................................................
4-1. مقدمه.......................................................................................................................................................................
4-2. روش حل پیشنهادی................................................................................................................................................
4-3. تشریح مطالعه موردی..............................................................................................................................................
4-4. نتایج محاسباتی (برای حالت قطعی)........................................................................................................................
4-4-1. نتایج محاسباتی حالت قطعی تخصیص ساده‌ی ظرفیت محدود مسئله‌ی مکان‌یابی محور (CSAHLP).............
4-4-2. نتایج محاسباتی حالت قطعی تخصیص چندگانهی ظرفیت محدود مسئله‌ی مکان‌یابی محور (CMAHLP)......
4-5. نتایج محاسباتی (برای حالت غیر‌قطعی)..................................................................................................................
4-5-1. نتایج محاسباتی حالت غیر‌قطعی تخصیص ساده‌ی ظرفیت محدود مسئله‌ی مکان‌یابی محور (CSAHLP)........
4-5-2. نتایج محاسباتی حالت غیر‌قطعی تخصیص چندگانهی ظرفیت محدود مسئله‌ی مکان‌یابی محور (CMAHLP).
فصل پنجم: جمعبندی، نتیجهگیری و پیشنهادها.....................................................................................
5-1. جمعبندی و نتیجهگیری...........................................................................................................................................
5-2. نوآوریهای مدل......................................................................................................................................................
5-3. پیشنهادها.................................................................................................................................................................
منابع...............................................................................................................................................................
پیوست الف: کد نوشته‌شده در نرم‌افزار GAMS برای حالت قطعی (CSAHLP).......................................................
پیوست ب: کد نوشته‌شده در نرم‌افزار GAMS برای حالت قطعی (CMAHLP)........................................................
پیوست ج: کد نوشته‌شده در نرم‌افزار GAMS برای حالت غیر‌قطعی (RCSAHLP)...................................................
پیوست د: کد نوشته‌شده در نرم‌افزار GAMS برای حالت غیر‌قطعی (RCMAHLP)...................................................