در این تحقیق یک مسئله مکانیابی- تخصیص چندتسهیله ظرفیت دهی شده در محیط گسسته که با تقاضای برنولی مشتریان روبرو است، مورد بررسی قرار میگیرد. هدف این مسئله احتمالی مکانیابی- تخصیص تعیین مکان بهینه تسهیلات از میان مکانهای بالقوه و تخصیص تمامی مشتریان به تسهیلاتی که مستقر شدهاند میباشد، بطوریکه هزینه های ثابت برای استقرار تسهیلات و کل هزینه ارزش انتظاری استراتژیها کمینه شود. در این مسئله برای تصمیم گیری در مورد تقاضای مشتریان، با در نظر گرفتن دو استراتژی متفاوت فرمولبندی و مورد بررسی قرار گرفته است و در ادامه برای درک مسئله مذکور یک مثال عددی ارائه شده است.نتایج محاسباتی این تحقیق، نشان میدهدکه مسئله توسط نرم افزار بهینه سازی LINGO در اندازههای بزرگ در زمان معقول به حل بهینه دست پیدا نمیکند. به منظور نشان دادن کارائی مسئله در مقیاسهای بزرگ، یک الگوریتم فراابتکاری (الگوریتم ژنتیک) پیشنهاد شد. الگوریتم فرا ابیکاری پیشنهادی با یک حد پایین کارا (آزاد سازی لاگرانژ) مقایسه میشود. كلمات كليديمکانیابی- تخصیص تسهیلات؛ تقاضای برنولی؛ برنامه ریزی احتمالی؛ الگوریتم ژنتیک؛ آزاد سازی لاگرانژ. فهرست مطالبعنوان صفحهتقدیم بهتتشکر و قدردانیثچكيدهجفهرست مطالبحفهرست جداولرفهرست شکلهازفصل اولکلیات تحقیق و ساختار پایان نامه11-1-مقدمه21-2- ساختار پایاننامه4فصل دومادبياتموضوعيو زمينههايعلمي تحقیق62-1- ابیادت موضوع72-1-1- مقدمه72-1-2- مسائل با تقاضای احتمالی در ادبیات موضوعی82-1-3- مسائل با تقاضای احتمالی برنولی در ادبیات موضوعی122-2- زمینه های علمی تحقیق152-2-1- مقدمه152-2-2- مسائل مکانیابی162-2-3- مسائل مکانیابی- تخصیص202-2-4- دستهبنديكليمسايلبرنامهريزيتسهيلات242-2-5- دسته بندی مسائل مکانیابی با نگرش سنتی252-2-6- دسته بندی مسائل مکانیابی با نگرش نوین26فصل سومارائه مدل ریاضی و الگوریتم های پیشنهادی283-1- مقدمه293-2- تعریف مساله303-2-1- فرضیات مساله313-2-2- پارامترهای مساله323-2-3- متغیر های تصمیم مساله333-2-4- استراتژی های موجود مساله353-2-5- همگن سازی373-2-6- خطی سازی مدل ریاضی413-2-7- مثال443-3- الگوریتم ژنتیک463-3-1- نمایش کروموزوم473-3-2- آغاز سازی473-3-3- ارزیابی493-3-4- معیار توقف493-3-5- نخبه گرایی503-3-6- عملگر تقاطع503-3-6-1- عملگر تقاطع نوع 1503-3-6-2- عملگر تقاطع نوع 2513-3-7- عملگر جهش523-3-7-1- عملگرجهش نوع 1533-3-7-2- عملگرجهش نوع 2533-3-8- انتخاب543-3-9- معیار توقف543-4- آزادسازی لاگرانژ563-4-1- مقدمه563-4-2- مراحل الگوریتم آزاد سازی لاگرانژ563-4-3- شرط توقف573-4-4- رویه انجام الگوریتم آزاد سازی لاگرانژ57فصل چهارمنتایج محاسباتی604-1- مقدمه614-2- مسائل نمونه62فصل پنجمنتیجه گیری و پیشنهادات آتی715-1- نتیجه گیری725-2- پیشنهادات آتی72مراجع فارسی73مراجع لاتین74پیوست الف78تشریح الگوریتم ژنتیک781- ويژگيهايالگوريتمژنتيك792- واژگان الگوريتم ژنتيك803- ساختار كلي الگوريتم ژنتيك814- مفاهيم کليدي الگوريتم ژنتيک834-1- كدينگ844-2- ايجاد جمعيت اوليه844-3- عملگرهای الگوریتمژنتيك854-3-1- عملیات تقاطع854-3-2- عملیات جهش864-3-3- مکانيسم نمونهگيري864-4- تابع برازش884-5- استراتژي برخورد با محدوديتها884-5-1- استراتژي ردي884-5-2- استراتژي اصلاحي884-5-3- استراتژي جريمهاي89Abstract90 فصل دوم:جدول( 2- 1). خلاصهای از ادبیات موضوع7جدول( 2- 2). عوامل موثر در تصمیمات مکان یابی17 فصل سوم:جدول (3- 1) . تعداد متغیر در مدل خطی و غیر خطی43جدول( 3- 2). تعداد محدودیت در مدل خطی و غیر خطی43جدول( 3- 3). مقادیر پارامتر برای 44جدول( 3- 4). مقادیر پارامتر برای. 44جدول( 3- 5). مقادیر پارامتر برای. 44جدول( 3- 6). نتایج محاسباتی مثال نوعی45جدول( 3- 7). روش بهینه سازی گرادیان59 فصل چهارم:جدول(4- 1). مقادیر پارامترهای الگوریتم ژنتیک62جدول(4- 2). نتایج محاسبات برای اندازه کوچک65جدول(4- 3). نتایج محاسبات برای اندازه کوچک66جدول(4- 4). مقایسه نتایج مثال نوعی69 فهرست شکلهافصل دوم:شکل( 2- 1).دسته بندی کلی مسائل برنامه ریزی تسهیلات[1].25شکل( 2- 2). دسته بندی نوین مسائل مکان یابی [1].27 فصل سوم:شکل( 3- 1). روند آغازسازی48شکل( 3- 2). روند ارزیابی49شکل( 3- 3). فلوچارت الگوریت ژنتیک55 فصل چهارم:شکل(4- 1). نمودار Gapهای بدست آمده از الگوریتم ژنتیک و الگوریتم آزاد سازی لاگرانژ68شکل(4- 2). نمودار سرعت همگرای الگوریتم ژنتیک70 1-1-مقدمهیکی از مسایلی که باید در مراحل اولیه طراحی سیستمهای صنعتی مورد توجه قرار گیرد مسئله مکانیابی- تخصیص[1]، که استقرار تسهیلات و تخصیص مشتریان به تسهیلات مستقر شده میباشد، است. مطالعه پیرامون مکان بهینه از دیدگاه جغرافیدانان و علمای علم اقتصادی همواره دارای اهمیت و الویت بوده است[1]. در ادبیات موضوع، مسایل مکانیابی[2]و مکانیابی - تخصیص مورد بحث قرار گرفتند و چند حالت از از این مسائل معرفی میشوند. مانند مسئله ظرفیتدهی[3] شده، مسئله بدون محدودیت ظرفیت[4] ، مسئله احتمالی[5] و مسائلی که تقاضایشان دارای توزیع برنولی[6] میباشند. منظور از مکانیابی، مجموعهای از اصول است که با توسل به آن مکان بهینه فعالیتهای (نقطه منطبق بر حداکثر سود یا حداقل هزینه) تعیین میشود. تصمیم گیری در مورد مکان تسهیلات از اجزاء بحرانی در برنامهریزی استراتژیک شرکتهای بزرگ خصوصی و عمومی محسوب میشود. مطالعه و تحقیق پیرامون مکان بهینه صنعتی همواره دارای اهمیت و الویت بسیار بوده است [2].مسائل مکانیابی در فضای گسسته[7] شامل تعیین مکان یک یا چندین تسهیلات در یک یا چند مکان بالقوه است تا هزینه تأمین نیاز های مشتریان را کمینه کند. درمسائل مکانیابی- تخصیص استقرار مجموعهای از تسهیلات جدید در بین تسهیلات موجود و تخصیص تسهیلات موجود به این تسهیلات جدید به صورتی که تقاضای موجود برآوردشود است مورد بحث قرار میگیرد. در دنیای واقعی بسیاری از مسائل را می توان با استفاده از مدلهای مسائل مکانیابی- تخصیص حل نمودو به جواب بهینه ومعقولی دست یافت که با اجرای این مدلها از صرف هزینههای اضافی میتوان جلوگیری کردو سود فراوانی بدست آورد [2].در گونهای از مسائل مکانیابی- تخصیص محدودیت در ظرفیت برای تسهیلاتی که وظیفه خدمت رسانی را دارند وجود دارد. این محدودیت میتواند ناشی از محدودیت فضا، محدودیت نیروی انسانی و یا حتی محدودیتهای از قبیل ظرفیت معابر جهت دستیابی به تسهیلات موجود باشد. تقاضای مشتریان را میتوان در مسائل مکانیابی- تخصیص بصورت احتمالی[8] و یا قطعی[9] در نظر گرفت. البته بدیهی است اگر بخواهیم خیلی دقیق با مسائل برخورد کنیم میبابستی تمامی مسائل را بصورت احتمالی در نظر بگیریم که به خاطر پیچیدگی و گران بودن روشهای حل مسائل احتمالی و به فراخور نیاز های مسئله را بصورت قطعی در نظر می گیریم. در حالی که مسائل مکانیابی- تخصیص با تقاضای احتمالی در مقایسه با مسائل مکانیابی- تخصیص کلاسیک خیلی عملیتر و نزدیکتر به دنیای واقعی میباشند،اما به علت پیچیدگی محاسباتی که این نوع مسائل دارند، تنها در چند دهه اخیر مورد بررسی قرار گرفتند.در این تحقیق مساله مکانیابی تسهیلات با تقاضای برنولی مورد بررسی قرار می گیرد. این تحقیق شامل مسئله احتمالی مکان یابی گسسته است که هدف آن مکان یابی بهینه تسهیلات بین مکان های کاندید وتخصیص مشتریان به تسهیلات باز می باشد. تابع هدف مینییم کردن جمع هزینه ثابت تسهیلات باز، بعلاوه ارزش انتظاری دیگر هزینه ها که شامل هزینه سرویس دهی، هزینه منابع برونسپاری وهزینه تقاضای برآورده نشده میباشد. هدف از این تحقیق مکانیابی بهینه تسهیلات بین مکان های کاندید وتخصیص مشتریان به تسهیلات میباشد. در تحقیقات اخیراین مطلب مد نظر بوده که اگر تسهیلی بیش از ظرفیت خود تقاضا داشته باشد از منابع برون سپار برای تامین تقاضای خود استفاده می کند.در حالی که ما در این تحقیق علاوه بر این حالت،حالت تقاضای برآورد نشده را در نظر می گیریم. مفروضاتمسالهپيشنهاديبقرارزيردرنظرگرفتهميشوند:1- فضای جواب گسسته است و یک مجموعه محدودی از مکانهای بالقوه برای تسهیلات وجود دارد.2- یک حداقل ظرفیتی برای تسهیلات وجود دارد.3- اگر یک تسهیلی مستقر شد، باید به اندازه حداقل ظرفیت خود به مشتریان سرویس دهد.4-هر تسهیل دارای حداکثر ظرفیتی میباشد و میتواند به اندازه ظرفیتاش به مشتریان سرویس دهد.5- ظرفیت محدود تاثیری بر تعداد مشتریانی که به یک تسهیل تخصیص مییابند، ندارد. این به آن معناست که به هر تسهیل بیشتر از ظرفیتاش، مشتری تخصیص یابد.6- دو نوع استراتژی مختلف برای تسهیلاتی که بیشتر از ظرفیتشان مشتری دارند، رخ میدهد.7- ممکن است تمامی تقاضای مشتریان را برآورد نشود. درادامهدرفصل2 ،ادبياتموضوعيو زمينههايعلميتحقيق را مورد بررسی خواهیم داد. ادبیات موضوع شامل مسئله مکانیابی، مکانیابی- تخصیص، مسئله مکانیابی- تخصیص ظرفیتدهی شده ، مسئله مکانیابی- تخصیص احتمالی و مسائلی که تقاضا مشتریان دارای توزیع احتمالی برنولی هستند، میباشد.در زمينههايعلميتحقيقدستهبندي مسايلمكانيابي ومسايلمكانيابي- تخصیص،انواعاین مسائل،مسالهمكانيابيكلاسيك مورد بررسی قرار میگیرد. درفصل 3بهتشريحمسالهومدلپيشنهاديميپردازيم. درادامهاينفصلبهمنظوردركبهتررفتارمدل،يكمثالنمونهايارائهخواهيمداد،اماباتوجهبهپيچيدگيهايمدلپيشنهاديدرمقياسهايبزرگ،یکالگوريتمفراابتكاري (الگوريتمژنتيك) و یک حد پایین (ساده سازی لاگرانژ)معرفيخواهیم کرد.نتايجمحاسباتمربوطبه الگوريتمها پیشنهادی در فصل 4 موردبررسيومقايسهقرارخواهيمداد. درنهايت،تعداديازتوسعههايآتيبه همراهنتيجهگيريدرفصل5موردبررسيقرارگرفتند. 2-1- ابیادت موضوعمسايلمكانيابي- تخصیص،يكيازحوزههايگستردهدرمدلسازيرياضي،دردنيايواقعيميباشند، دراین مسائل استقرار مجموعهای از تسهیلات جدید در بین تسهیلات موجود و تخصیص تسهیلات موجود به این تسهیلات جدید به صورتی که تقاضای موجود برآوردشود است مورد بحث قرار میگیرد.مسئله مکانیابی اولین بار توسط آلفرد وبر [3]در سال 1909معرفی شد. او یک مسئله تک تسهیلی که فاصله بین انبار و مشتریان موجود را کمینه میکرد، در نظر گرفت. مسئله مکانیابی- تخصیص اولین با توسط کوپر [4]در سال 1963 برای مدلی با دو تسهیل جدید و هفت تسهیل موجود معرفی و حل شد. در ادامه کوپر یک روش ابتکاری برای این مسئله توسعه داد و حل نمود[5]. ظرفیت تسهیلات که مسئولیت خدمت رسانی را بر عهده دارند در اغلب موارد محدود است که این محدودیت میتواند ناشی از محدودیت فضا، محدودیت نیروی انسانی و غیره باشد. اما برای مواردی هم محدودیت ظرفیت بر روی تسهیلات وجود ندارد. لذا تسهیلات جدید به دو دسته ظرفیت محدود و نامحدود تقسیم میشوند. مسئله مکانیابی- تخصیص با ظرفیت محدود اولین بار توسط مورتاگ و همکاران[6]معرفی شود. همچنین یک تعدادی از محققین ظرفیت نامحدود برای مسائل مکانیابی- تخصیص در نظر گرفتند از جمله این افراد درزنر [7]، اون و داسکین [8، 9] بودند.
مسئله مکان یابی- تخصیص چند تسهیله ظرفیت دهی شده استراتژی محور با تقاضای برنولی word
در این تحقیق یک مسئله مکانیابی- تخصیص چندتسهیله ظرفیت دهی شده در محیط گسسته که با تقاضای برنولی مشتریان روبرو است، مورد بررسی قرار میگیرد. هدف این مسئله احتمالی مکانیابی- تخصیص تعیین مکان بهینه تسهیلات از میان مکانهای بالقوه و تخصیص تمامی مشتریان به تسهیلاتی که مستقر شدهاند میباشد، بطوریکه هزینه های ثابت برای استقرار تسهیلات و کل هزینه ارزش انتظاری استراتژیها کمینه شود. در این مسئله برای تصمیم گیری در مورد تقاضای مشتریان، با در نظر گرفتن دو استراتژی متفاوت فرمولبندی و مورد بررسی قرار گرفته است و در ادامه برای درک مسئله مذکور یک مثال عددی ارائه شده است.نتایج محاسباتی این تحقیق، نشان میدهدکه مسئله توسط نرم افزار بهینه سازی LINGO در اندازههای بزرگ در زمان معقول به حل بهینه دست پیدا نمیکند. به منظور نشان دادن کارائی مسئله در مقیاسهای بزرگ، یک الگوریتم فراابتکاری (الگوریتم ژنتیک) پیشنهاد شد. الگوریتم فرا ابیکاری پیشنهادی با یک حد پایین کارا (آزاد سازی لاگرانژ) مقایسه میشود. كلمات كليديمکانیابی- تخصیص تسهیلات؛ تقاضای برنولی؛ برنامه ریزی احتمالی؛ الگوریتم ژنتیک؛ آزاد سازی لاگرانژ. فهرست مطالبعنوان صفحهتقدیم بهتتشکر و قدردانیثچكيدهجفهرست مطالبحفهرست جداولرفهرست شکلهازفصل اولکلیات تحقیق و ساختار پایان نامه11-1-مقدمه21-2- ساختار پایاننامه4فصل دومادبياتموضوعيو زمينههايعلمي تحقیق62-1- ابیادت موضوع72-1-1- مقدمه72-1-2- مسائل با تقاضای احتمالی در ادبیات موضوعی82-1-3- مسائل با تقاضای احتمالی برنولی در ادبیات موضوعی122-2- زمینه های علمی تحقیق152-2-1- مقدمه152-2-2- مسائل مکانیابی162-2-3- مسائل مکانیابی- تخصیص202-2-4- دستهبنديكليمسايلبرنامهريزيتسهيلات242-2-5- دسته بندی مسائل مکانیابی با نگرش سنتی252-2-6- دسته بندی مسائل مکانیابی با نگرش نوین26فصل سومارائه مدل ریاضی و الگوریتم های پیشنهادی283-1- مقدمه293-2- تعریف مساله303-2-1- فرضیات مساله313-2-2- پارامترهای مساله323-2-3- متغیر های تصمیم مساله333-2-4- استراتژی های موجود مساله353-2-5- همگن سازی373-2-6- خطی سازی مدل ریاضی413-2-7- مثال443-3- الگوریتم ژنتیک463-3-1- نمایش کروموزوم473-3-2- آغاز سازی473-3-3- ارزیابی493-3-4- معیار توقف493-3-5- نخبه گرایی503-3-6- عملگر تقاطع503-3-6-1- عملگر تقاطع نوع 1503-3-6-2- عملگر تقاطع نوع 2513-3-7- عملگر جهش523-3-7-1- عملگرجهش نوع 1533-3-7-2- عملگرجهش نوع 2533-3-8- انتخاب543-3-9- معیار توقف543-4- آزادسازی لاگرانژ563-4-1- مقدمه563-4-2- مراحل الگوریتم آزاد سازی لاگرانژ563-4-3- شرط توقف573-4-4- رویه انجام الگوریتم آزاد سازی لاگرانژ57فصل چهارمنتایج محاسباتی604-1- مقدمه614-2- مسائل نمونه62فصل پنجمنتیجه گیری و پیشنهادات آتی715-1- نتیجه گیری725-2- پیشنهادات آتی72مراجع فارسی73مراجع لاتین74پیوست الف78تشریح الگوریتم ژنتیک781- ويژگيهايالگوريتمژنتيك792- واژگان الگوريتم ژنتيك803- ساختار كلي الگوريتم ژنتيك814- مفاهيم کليدي الگوريتم ژنتيک834-1- كدينگ844-2- ايجاد جمعيت اوليه844-3- عملگرهای الگوریتمژنتيك854-3-1- عملیات تقاطع854-3-2- عملیات جهش864-3-3- مکانيسم نمونهگيري864-4- تابع برازش884-5- استراتژي برخورد با محدوديتها884-5-1- استراتژي ردي884-5-2- استراتژي اصلاحي884-5-3- استراتژي جريمهاي89Abstract90 فصل دوم:جدول( 2- 1). خلاصهای از ادبیات موضوع7جدول( 2- 2). عوامل موثر در تصمیمات مکان یابی17 فصل سوم:جدول (3- 1) . تعداد متغیر در مدل خطی و غیر خطی43جدول( 3- 2). تعداد محدودیت در مدل خطی و غیر خطی43جدول( 3- 3). مقادیر پارامتر برای 44جدول( 3- 4). مقادیر پارامتر برای. 44جدول( 3- 5). مقادیر پارامتر برای. 44جدول( 3- 6). نتایج محاسباتی مثال نوعی45جدول( 3- 7). روش بهینه سازی گرادیان59 فصل چهارم:جدول(4- 1). مقادیر پارامترهای الگوریتم ژنتیک62جدول(4- 2). نتایج محاسبات برای اندازه کوچک65جدول(4- 3). نتایج محاسبات برای اندازه کوچک66جدول(4- 4). مقایسه نتایج مثال نوعی69 فهرست شکلهافصل دوم:شکل( 2- 1).دسته بندی کلی مسائل برنامه ریزی تسهیلات[1].25شکل( 2- 2). دسته بندی نوین مسائل مکان یابی [1].27 فصل سوم:شکل( 3- 1). روند آغازسازی48شکل( 3- 2). روند ارزیابی49شکل( 3- 3). فلوچارت الگوریت ژنتیک55 فصل چهارم:شکل(4- 1). نمودار Gapهای بدست آمده از الگوریتم ژنتیک و الگوریتم آزاد سازی لاگرانژ68شکل(4- 2). نمودار سرعت همگرای الگوریتم ژنتیک70 1-1-مقدمهیکی از مسایلی که باید در مراحل اولیه طراحی سیستمهای صنعتی مورد توجه قرار گیرد مسئله مکانیابی- تخصیص[1]، که استقرار تسهیلات و تخصیص مشتریان به تسهیلات مستقر شده میباشد، است. مطالعه پیرامون مکان بهینه از دیدگاه جغرافیدانان و علمای علم اقتصادی همواره دارای اهمیت و الویت بوده است[1]. در ادبیات موضوع، مسایل مکانیابی[2]و مکانیابی - تخصیص مورد بحث قرار گرفتند و چند حالت از از این مسائل معرفی میشوند. مانند مسئله ظرفیتدهی[3] شده، مسئله بدون محدودیت ظرفیت[4] ، مسئله احتمالی[5] و مسائلی که تقاضایشان دارای توزیع برنولی[6] میباشند. منظور از مکانیابی، مجموعهای از اصول است که با توسل به آن مکان بهینه فعالیتهای (نقطه منطبق بر حداکثر سود یا حداقل هزینه) تعیین میشود. تصمیم گیری در مورد مکان تسهیلات از اجزاء بحرانی در برنامهریزی استراتژیک شرکتهای بزرگ خصوصی و عمومی محسوب میشود. مطالعه و تحقیق پیرامون مکان بهینه صنعتی همواره دارای اهمیت و الویت بسیار بوده است [2].مسائل مکانیابی در فضای گسسته[7] شامل تعیین مکان یک یا چندین تسهیلات در یک یا چند مکان بالقوه است تا هزینه تأمین نیاز های مشتریان را کمینه کند. درمسائل مکانیابی- تخصیص استقرار مجموعهای از تسهیلات جدید در بین تسهیلات موجود و تخصیص تسهیلات موجود به این تسهیلات جدید به صورتی که تقاضای موجود برآوردشود است مورد بحث قرار میگیرد. در دنیای واقعی بسیاری از مسائل را می توان با استفاده از مدلهای مسائل مکانیابی- تخصیص حل نمودو به جواب بهینه ومعقولی دست یافت که با اجرای این مدلها از صرف هزینههای اضافی میتوان جلوگیری کردو سود فراوانی بدست آورد [2].در گونهای از مسائل مکانیابی- تخصیص محدودیت در ظرفیت برای تسهیلاتی که وظیفه خدمت رسانی را دارند وجود دارد. این محدودیت میتواند ناشی از محدودیت فضا، محدودیت نیروی انسانی و یا حتی محدودیتهای از قبیل ظرفیت معابر جهت دستیابی به تسهیلات موجود باشد. تقاضای مشتریان را میتوان در مسائل مکانیابی- تخصیص بصورت احتمالی[8] و یا قطعی[9] در نظر گرفت. البته بدیهی است اگر بخواهیم خیلی دقیق با مسائل برخورد کنیم میبابستی تمامی مسائل را بصورت احتمالی در نظر بگیریم که به خاطر پیچیدگی و گران بودن روشهای حل مسائل احتمالی و به فراخور نیاز های مسئله را بصورت قطعی در نظر می گیریم. در حالی که مسائل مکانیابی- تخصیص با تقاضای احتمالی در مقایسه با مسائل مکانیابی- تخصیص کلاسیک خیلی عملیتر و نزدیکتر به دنیای واقعی میباشند،اما به علت پیچیدگی محاسباتی که این نوع مسائل دارند، تنها در چند دهه اخیر مورد بررسی قرار گرفتند.در این تحقیق مساله مکانیابی تسهیلات با تقاضای برنولی مورد بررسی قرار می گیرد. این تحقیق شامل مسئله احتمالی مکان یابی گسسته است که هدف آن مکان یابی بهینه تسهیلات بین مکان های کاندید وتخصیص مشتریان به تسهیلات باز می باشد. تابع هدف مینییم کردن جمع هزینه ثابت تسهیلات باز، بعلاوه ارزش انتظاری دیگر هزینه ها که شامل هزینه سرویس دهی، هزینه منابع برونسپاری وهزینه تقاضای برآورده نشده میباشد. هدف از این تحقیق مکانیابی بهینه تسهیلات بین مکان های کاندید وتخصیص مشتریان به تسهیلات میباشد. در تحقیقات اخیراین مطلب مد نظر بوده که اگر تسهیلی بیش از ظرفیت خود تقاضا داشته باشد از منابع برون سپار برای تامین تقاضای خود استفاده می کند.در حالی که ما در این تحقیق علاوه بر این حالت،حالت تقاضای برآورد نشده را در نظر می گیریم. مفروضاتمسالهپيشنهاديبقرارزيردرنظرگرفتهميشوند:1- فضای جواب گسسته است و یک مجموعه محدودی از مکانهای بالقوه برای تسهیلات وجود دارد.2- یک حداقل ظرفیتی برای تسهیلات وجود دارد.3- اگر یک تسهیلی مستقر شد، باید به اندازه حداقل ظرفیت خود به مشتریان سرویس دهد.4-هر تسهیل دارای حداکثر ظرفیتی میباشد و میتواند به اندازه ظرفیتاش به مشتریان سرویس دهد.5- ظرفیت محدود تاثیری بر تعداد مشتریانی که به یک تسهیل تخصیص مییابند، ندارد. این به آن معناست که به هر تسهیل بیشتر از ظرفیتاش، مشتری تخصیص یابد.6- دو نوع استراتژی مختلف برای تسهیلاتی که بیشتر از ظرفیتشان مشتری دارند، رخ میدهد.7- ممکن است تمامی تقاضای مشتریان را برآورد نشود. درادامهدرفصل2 ،ادبياتموضوعيو زمينههايعلميتحقيق را مورد بررسی خواهیم داد. ادبیات موضوع شامل مسئله مکانیابی، مکانیابی- تخصیص، مسئله مکانیابی- تخصیص ظرفیتدهی شده ، مسئله مکانیابی- تخصیص احتمالی و مسائلی که تقاضا مشتریان دارای توزیع احتمالی برنولی هستند، میباشد.در زمينههايعلميتحقيقدستهبندي مسايلمكانيابي ومسايلمكانيابي- تخصیص،انواعاین مسائل،مسالهمكانيابيكلاسيك مورد بررسی قرار میگیرد. درفصل 3بهتشريحمسالهومدلپيشنهاديميپردازيم. درادامهاينفصلبهمنظوردركبهتررفتارمدل،يكمثالنمونهايارائهخواهيمداد،اماباتوجهبهپيچيدگيهايمدلپيشنهاديدرمقياسهايبزرگ،یکالگوريتمفراابتكاري (الگوريتمژنتيك) و یک حد پایین (ساده سازی لاگرانژ)معرفيخواهیم کرد.نتايجمحاسباتمربوطبه الگوريتمها پیشنهادی در فصل 4 موردبررسيومقايسهقرارخواهيمداد. درنهايت،تعداديازتوسعههايآتيبه همراهنتيجهگيريدرفصل5موردبررسيقرارگرفتند. 2-1- ابیادت موضوعمسايلمكانيابي- تخصیص،يكيازحوزههايگستردهدرمدلسازيرياضي،دردنيايواقعيميباشند، دراین مسائل استقرار مجموعهای از تسهیلات جدید در بین تسهیلات موجود و تخصیص تسهیلات موجود به این تسهیلات جدید به صورتی که تقاضای موجود برآوردشود است مورد بحث قرار میگیرد.مسئله مکانیابی اولین بار توسط آلفرد وبر [3]در سال 1909معرفی شد. او یک مسئله تک تسهیلی که فاصله بین انبار و مشتریان موجود را کمینه میکرد، در نظر گرفت. مسئله مکانیابی- تخصیص اولین با توسط کوپر [4]در سال 1963 برای مدلی با دو تسهیل جدید و هفت تسهیل موجود معرفی و حل شد. در ادامه کوپر یک روش ابتکاری برای این مسئله توسعه داد و حل نمود[5]. ظرفیت تسهیلات که مسئولیت خدمت رسانی را بر عهده دارند در اغلب موارد محدود است که این محدودیت میتواند ناشی از محدودیت فضا، محدودیت نیروی انسانی و غیره باشد. اما برای مواردی هم محدودیت ظرفیت بر روی تسهیلات وجود ندارد. لذا تسهیلات جدید به دو دسته ظرفیت محدود و نامحدود تقسیم میشوند. مسئله مکانیابی- تخصیص با ظرفیت محدود اولین بار توسط مورتاگ و همکاران[6]معرفی شود. همچنین یک تعدادی از محققین ظرفیت نامحدود برای مسائل مکانیابی- تخصیص در نظر گرفتند از جمله این افراد درزنر [7]، اون و داسکین [8، 9] بودند.