چکیده: در این تحقیق مکان یابی چند تسهیل و یک انبار مرکزی با تقاضا برنولیمورد بررسی قرار گرفت که مکان ها بصورت گسسته می باشند. هدف این مسئله مکان یابی- تخصیص، تعیین مکان بهینه تسهیلات و تخصیص تمام مشتریان به تسهیلات مستقر شده و همچنین مکان یابی یک انبار از بین مکان های کاندید انبار به عنوان انبار مرکزی و تخصیص تسهیلات به آن انبار می باشد بطوریکه بتوانیم مجموع هزینه های ثابت تسهیلات مکان یابی شده و انبار مرکزی و بعلاوه هزینه سرویس دهی و هزینه منابع برون سپار آنها را مینیمم شود.نتايجمحاسباتياينتحقيق، نشانمي دهدكهمسالهتوسطنرم افزارLINGO در اندازه های بزرگ در زمان معقول به حل بهینه دست پیدا نمی کند. به منظورنشاندادنكاراييمسالهدرمقياس هايبزرگ،دوالگوريتمفراابتكاري(الگوريتمژنتيك)وابتکاری( الگوریتم آزاد سازی لاگرانژ)پيشنهادوبايكديگرمقايسهشدهاند. كلمات كليدي:مساله مکان یابی – برون سپاری تقاضا- انبار- تقاضا برنولی - الگوریتم ژنتیک- الگوریتم آزاد سازی لاگرانژ. فهرست مطالبچکیده vفهرست مطالب viفهرست جداول ixفهرست شکل ها xفصل اول 1کلیات تحقیق 11-1 مقدمه 21-2 دستهبنديكليمسايلبرنامهريزيتسهيلات 31-3 دسته بندی مسائل مکانیابی با نگرش سنتی 31-4 دسته بندی مسائل مکانیابی با نگرش نوین 51-5 اهداف تحقیق 61-7 ساختار پایان نامه 7فصل دوم 8ادبیات موضوع 82-1 مقدمه 92-2 ادبیات موضوع 9فصل سوم 16ارائه مدل و الگوریتم های پیشنهادی.. 161-3 مقدمه 173-2 ساختار مسئله 183-2-1مفروضات مدل 183-2-2 زیر نویس های مدل 193-2-3 پارامتر های مدل 193-2-4 متغیر های تصمیم مدل 203-2-5 ساير علائم مدل رياضي 203-2-6 مدل ریاضی پیشنهادی 213-2-7 تشریح جزئیات و عملکرد مدل 223-3 خطی سازی مدل پیشنهادی 263-4 مثال 283-5 لزوم استفاده از رويكرد فرا ابتكاريو ابتکاری 313-6 تشریح الگوریتم ژنتیک 323-7 مفاهيم كليدي الگوريتم ژنتيك 333-7-1 کدینگ 333-7-2 ایجاد جمعیت اولیه 343-7-3 عملگر های الگوریتم ژنتیک 343-7-4 تابع برازش 373-7-5 استراتژي برخورد با محدوديت ها 373-8 ساختار كلي الگوريتم ژنتيك 383-9 رویه انجام الگوریتم ژنتیک 403-9-1 نمايش كروموزوم 403-9-2 جمعیت اولیه 413-9-3 ارزیابی 423-9-4 معیار توقف 423-9-5 نخبه گرایی 423-9-6 عملگر 423-10 الگوریتم آزاد سازی لاگرانژ 483-10 -1 مراحل الگوریتم آزاد سازی لاگرانژ 503-10 -2 شرایط توقف الگوریتم آزاد سازی لاگرانژ 503-11 رویه انجام الگوریتم آزاد سازی لاگرانژ 51فصل چهارم...................................................................................................................................... 54نتایج محاسباتی 544-1 نتايج محاسباتي 555-2 مسايل نمونه 55نتیجه گیری و پیشنهادات آتی 655-1 نتیجه گیری 665-2 پیشنهادات آتی67مراجع فارسی 68مراجع لاتین 69Abstract72 فهرست جداولفصل دومجدول (1- 1). خلاصه ادبیات موضوعی مساله مکان یابی- تخصیص... 14 فصل سوم جدول (3 - 1). تعداد متغیر های مسئله خطی و غیر خطی.. 28جدول (3 - 2). تعداد متغیر های مسئله خطی و غیر خطی.. 28جدول (3 - 3). مقادیر پارامتر . 29جدول (3 - 4). مقادیر پارامتر برای تسهیلات i29جدول (3- 5). مقادیر پارامتر های انبار.. 29جدول (3- 6). مقادیر تابع هدف.. 30جدول (3- 7). جواب بهینه مسئله.. 30جدول(3- 8). روند الگوريتم ژنتيك.39جدول(3- 9) مراحل بهینه سازی گرادیان.. 53 فصل چهارم جدول(4- 1). پارامترهاي الگوريتم ژنتيك.. 56جدول(4- 2). پارامترهاي الگوريتم لاگرانژ.. 56جدول(4- 3). نتایج محاسباتی در مقیاس های کوچک.. 60جدول(4- 4). نتایج محاسباتی در مقیاس های بزرگ.. 61جدول(4- 5). مقایسه جواب های B&B و الگوریتم GA.. 62 فهرست شکل ها فصل اولشکل(1- 1).دسته بندی کلی مسائل برنامه ریزی تسهیلات[1].3شکل( 1 - 2).دسته بندی نوین مسائل مکان یابی [1].6 فصل سوم شکل(3- 1). کروموزم... 41شکل(3- 2). تقاطع نوع I. 43شکل(3- 3(.تقاطع نوعII. 45شکل(3- 4). جهش نوع I. 46شکل(3- 5). جهش نوعII. 47 فصل چهارم شکل (4- 1). نمودار همگرایی مقادیر تابع هدف در GA.. 63شکل (4- 2). نمودارمقايسهزمانمحاسباتيالگوريتمژنتيكوالگوريتمآزاد سازی لاگرانژ و Lingo دراندازههايمتفاوت.. 64 1-1 مقدمهمسائل مکان یابی- تخصیص[1] شامل استقرار مجموعه ای ازتسهیلات جدید[2] در بین تسهیلات موجود و تخصیص تسهیلات موجود به تسهیلات جدید استبصورتی که تقاضای تسهیلات موجود برآورده شود[2]. در دنیای واقعی بسیاری از مسائل را می توان با استفاده از مدلهای ارائه شده برای این دسته از مسائل حل کرد و جوابهای بسیار خوبی دست یافت که با اجرای آنها از صرف هزینه های اضافی می توان جلوگیری کرد و سود فراوانی بدست آورد. در واقع این مدلها را می توان با اهداف بهبودی و یا در زمینه- های طراحی بکار برد. این گونه مسائل ابتدا توسط کوپر[3] در سال 1963 ارائه شد.مسائل مکان یابی نه تنها تعیین می کنند که هر مشتری چه مقدار کالا از هر واحد دریافت میکند، بلکه تعداد تسهیلات ، محل قرارگیری و ظرفیت آنها را نیز مشخص می کند. این مسائل را می توان بر مبنای ماهیت مسئله مطرح شده به دسته های زیر دسته بندی کرد.1.فضای تخصیصدر بعضی مسائل نمی توان از تمامی سطح بصورت پیوسته استفاده کرد که این مسائل می بایستی بصورت گسسته[4] مورد تحلیل قرارگیرند.2. ظرفیت سرویس دهنده هاظرفیت تسهیلاتی که مسولیت سرویس دهی را بر عهده دارند در اغلب موارد محدود[5] است لذا تسهیلات جدید به دو دسته ظرفیت محدود و نامحدود تقسیم می شوند.3.تقاضاتقاضایمشتریان[6] را می توان بصورت احتمالیو یا قطعی در نظر گرفت.مسايلبرنامهريزيتسهيلاتبهچهاردستهعمدهمكانيابي،مسيريابي[7]،تخصيصوطراحيتقسيمميشود.باتركيباينمؤلفههامسايلمكانيابي- مسيريابي[8]،مكانيابي- تخصيصبهدستميآيد [1]. در شکل (3-1) این دسته بندی نشان داده شده است.مکان یابی-تخصیص تسهیلاتمکان یابی- مسیریابی تسهیلاتشکل(1- 1).دسته بندی کلی مسائل برنامه ریزی تسهیلات[1].عموما دسته بندی با نگرش سنتی برای مسائل مکانیابی بر اساس موارد زیر تقسیم بندی می شود.v بر اساس خصوصیات وسایل جدید1) مساله مکانیابی تک وسیله/ چند وسیله2) مساله مکانیابی با وسایل ناحیهای/نقطه ایv بر اساس نوع ارتباط وسایل موجود و جدید1) مساله مکانیابی با ارتباطات برونزا/ درونزا2) مساله مکانیابی با ارتباطات ایستا/ پویا3) مساله مکانیابی با ارتباطات قطعی/ احتمالیv بر اساس خصوصیات وسایل موجود1) مساله مکانیابی با وسایل ایستا/ پویا2) مساله مکانیابی وسایل با مکان قطعی/ احتمالیv بر اساس فضای جواب1) مسائل مکانیابی روی خط/ صفحه2) مسائل مکانیابی گسسته/روی شبکه3) مسائل مکانیابی با فضای مقید/ نا مقیدv بر اساس نوع و تعداد هدف و شاخص انتخاب1) مسائل تک هدفه/ چند هدفه2) مسائل تک شاخصه/ چند شاخصه3) مسائل میانه/ مرکز/ پوشش[9]v بر اساس نوع تابع فاصله1) مسئله مکانیابی با فاصله متعامد/ چبیشف2) مسئله مکانیابی با فواصل اقلیدسی/ مجذور اقلیدسی3) مسئله مکانیابی تابع فاصله خاصv بر اساس زمینه مسئله1) مسئله مکانیابی انبار/ کارخانه2) مسئله مکانیابی نقاط تبادل[10]3) مسئله مکانیابی وسایل ناخوشایند4) مسئله مکانیابی- مسیر یابی « مسائل مکانیابی وسایل گردشی »5) مسئله مکانیابی سلسله مراتبیمسائل مکانیابی و استقرار بر اساس نگرش نوین در چهار رویکرد عمده نظری و عملی در مدل سازی و حل مسائل به صورت زیر دسته بندی می شود. رویکردهای استراتژیکCFLDFLSLFهوش مصنوعیMHNNFLرویکردهای عملیITEGرویکردهای دیگرEMDMSCMیادداشت:SLF: مکان یابی تسهیلات استراتژیکDFL: مکان یابی تسهیلات پویاCFL: مکان یابی تسهیلات رقابتیFL: منطق فازیNN: شبکه های عصبیMH: الگوریتم های فراابتکاریEG: جغرافیای اقتصادیIT: فناوری اصلاعاتSCM: مدیریت زنجیره تامینDM: داده کاویEM: سنجش بهره وریشکل( 1 - 2).دسته بندی نوین مسائل مکان یابی [1]. همانطور که در بخش قبل تشریح گردید، عموما مسائل مکان یابی- تخصیص با هدف حداقل کردن هزینه ها همراه است بدین منظور برآورد تقاضای مشتریان با حداقل تسهیلات مد نظر قرار می گیرد.بمنظور حداقل نمودن تعداد تسهیلات، گاهی استفاده از منابع خارجی[11] یا یک انبار[12] مرکزی وارد مدل شده و در واقع نوآوری مدل را دراین راستا رقم زده است.پيشرفتروزبهروزمسايلمرتبطبرنامه ریزی تسهیلاتدرفصلدومبررسيخواهد شد.همانطوركهاشاره گرديد،مسايلبامفاهيمجديدونزديكشدنبهواقعيتپيچيده ترميشوند. درنظرگرفتن پارامترهايغيرقطعي،مويداينمطلبهستند. بديهياستكهدرنظرگرفتنكليهمواردفوقبطورهمزمان،مسألهرابسيارپيچيدهو عملاًغيرقابلحلخواهدساخت.هرچند؛انتخابتركيبيازفرضیاتواهداففوقبراييكمسألهجديد، بايدبسيارسنجيدهوباتوجهبهرويكردهاوامكاناتپردازشيدردسترسانجامشود.امروزهبامعرفي رويكردهايغيردقيقهمانندرويكردهاي ابتکاری وفراابتكاريبرايمواجههباابعادواقعيمسايل،دانشمندانتوانستهاند بهجوابهاينزديكبهبهينهدستيابند،وليازآنجايي كهاينرويكردهابيشتربهساختارمسالهوابسته ميباشند،براياثباتكارآييآنهاهمچناننيازبهشبيهسازيومدلسازيمسالهمی باشد؛تابتوانبهجواببهينه آندرابعادكوچكيامتوسطدستيافت.دراينتحقيقبهارايهيكمدلرياضيبهمنظورمکان یابی تسهیلات و تخصیص مشتریان به تسهیلات مستقر شده و مکان یابی و تخصیص یک انبار مرکزی به تسهیلاتباهدفحداقلنمودنهزینه انتظاریبادرنظرگرفتناحتمالی بودن تقاضای مشتریان می باشد.در ادامه در فصل دوم، ادبیات موضوعی مسایل مکان یابی-تخصیص تسهیلات را مورد بررسی قرار خواهیم داد. در فصل سوم به تشریح و مدل سازی مسئله می پردازیم،در فصل چهارم الگوریتم ژنتیک و آزاد سازی لاگرانژ به بطور مفصل تشریح خواهد شد. نتايج محاسباتي در فصل پنجم تجزيه وتحليل شده است وكارآيي مدل و نيز الگوريتمهایفراابتكاري و ابتکاری مورد مقايسه قرار گرفته است.سرانجام، در فصل ششم به نتيجه گيري كلي و ارايه پيشنهادات براي تحقيقات آتي و زمينه هاي گسترش مدل پرداخته شده است كه زمينه خوبي براي فعاليت ساير محققين فراهم شده است. 2-1 مقدمهدراينفصلبهبررسيسايرتحقيقاتوفعاليتهايصورتگرفتهدرزمينهاينتحقيقپرداختهمي-شود. سيرمنطقيگسترشاينبخشازمسايلمکان یابی- تخصیصبررسيشدهونهايتادرقسمتنتيجهگيري،نوآوريوجايگاهاينتحقيقدرقبلازسايرتحقيقاتترسيموتشريحمي گردد. باشدكه اينتحقيقزمينهايبرايرشدوارتقاءدانشمکان یابی درعملمفيدواقعگرددكهمحققراآرزوييجز ايننيست. 2-2 ادبیات موضوعمسئله مکانیابی اولین بار توسط آلفرد وبر [3]در سال 1909 که یک مسئله تک تسهیلی که فاصله بین انبار و مشتریان موجود را کمینه می‌کرد، معرفی شد. و برای اولین بار مسایل مکان یابی- تخصیص توسط کوپر[4] در سال 1963 برای مدلی با 2 تسهیل جدید و 7 تسهیل موجود معرفی و حل شد.بعدها کوپر[5] یک روش ابتکاری برای این مسئله ارائه داد. زمانیکه مکان های مورد قبول(کاندید) تسهیلات از قبل به عنوان داده های مشخص و محدود باشدآن بعنوان یک مسئله مکان یابی گسسته تلقی می شود، اگرچه این نوع مسایل در دنیای واقعی بندرت اتفاق می افتد.ظرفیت تسهیلات در اغلب موارد محدود است که این محدودیت میتواند ناشی از محدودیت فضا، محدودیت نیروی انسانی و غیره باشد. اما برای مواردی هم محدودیت ظرفیت بر روی تسهیلات وجود ندارد. لذااین مسایل به دو دسته، مسایل با ظرفیت محدود و نامحدود دسته بندی می شود.بونگارتز و همکاران[6]، یک مدل مکان یابی- تخصیص که ظرفیت تسهیل ها محدود است را ارائه دادند. یک الگوریتم حل برای مدل مکان یابی هاب تک تخصیص[13] محدود توسط ارنست و همکاران[9] ارائه شد. همچنین بدری و هودی و همکاران [7و8 ] مطالعات متفاوتی را در این راستا انجام داده اند. همچنین بریمبرگ و همکاران[10] وگالوآردی[11] مسئله مکان یابی تسهیل با ظرفیت نامحدود بررسی کردند.یک مدل عمومی برای مکان یابی تسهیل و انبار توسط باروس[12] پیشنهاد شد که تسهیل نامحدود می باشد.وای.هینجوسا و همکاران[23] مسئله مکان یابی تسهیل در دو سطح توزیع متفاوت با انتخاب چندین دوره زمانی به منظور حداقل کردن هزینه کل تقاضا مطرح کردند که محققین یک الگوریتم ابتکاری(آزاد سازی لاگرانژ) نیز برای حل مسئله نیز ارائه دادند...