بخشی از مقاله
چکیده
مساله مکانیابی-تخصیص یکی از مسائل پایهاي درحوزه مهندسی صنایع میباشد. در این نوع مسائل، مکانیابی تسهیلات و تخصیص مشتریان به آنها، براي پاسخگویی به تقاضاي مشتریان به طور همزمان انجام میگیرد. مساله مکانیابی-تخصیص، یک مساله NP-Hard است، از این رو استفاده از روشهاي دقیق ریاضی به تنهایی براي حل این مساله، بسیار پرهزینه و غیرممکن است. از این جهت در این مقاله، الگوریتم ابتکاري مبتنی بر روش تقریب هذلولی براي حل اینگونه مسائل استفاده شده و به بررسی اثر هزینه استقرار تسهیلات بر روي نحوه تخصیص تسهیلات پرداخته میشود.
این الگوریتم مبتنی بر روش تقریب هذلولی براي مسائل مکان یابی با فاصله اقلیدسی میباشد. در این مقاله، ابتدا روش تقریب هذلولی باتوجه به پارامترهاي آن در خصوص میزان همگرایی الگوریتم به جواب بهینه و انحراف از هزینه بهینه بررسی میشود. سپس مساله در فضاي پیوسته با دو فرض عدم محدودیت ومحدودیت ظرفیت مورد بررسی قرار می گیرد. نتایج حل، حاکی از کارایی الگوریتم اشاره شده نسبت به حل دقیق می باشد.
.1 مقدمه
معمولا در تمامی کارخانجات و سازمانها مسئله مکانیابی یکی از مسائل مهم میباشد که این نوع مسائل کاربردهاي گوناگونی از جمله تعیین محل استقرار کارخانجات، مراکز فروش، قرارگیري دستگاه جدید در کارخانه و همچنین شامل کاربردهاي فراوان دیگري میباشد. که هدف در کلیه این مسائل افزایش سود - با کمینه کردن هزینه - با توجه به محدودیتهاي مختلف موجود میباشد. این محدودیتها میتواند در مورد فضاي حل - پیوسته و گسسته - و ظرفیت تسهیلات مطرح شود.[1] یکی از این شاخهها، مسئله مکانیابی-تخصیص میباشد که در این نوع مسائل محدودیت مکانیابی برآورده کردن تقاضاهاي موجود و مشخص کردن نحوه پاسخگویی تقاضا میباشد.
بعبارت دیگر بدنبال یافتن بهترین تخصیص تقاضاها به تسهیلات می باشیم که تعداد تسهیلات نیز یکی از متغیرهاي تصمیم مسئله میباشد. تقاضا میتواند داراي مقداري ثابت، احتمالی[2] ویا فاري باشد . همچنین در مورد محل تقاضا [3]و ترکیب آنها [5 ,4] نیز میتواند مطرح شود. مساله مکانیابی-تخصیص با توجه به اینکه از متغیرهاي زیادي ازجمله تعداد تسهیلات، مکان تسهیلات و ...دارد، نیازمند ارائه روشهاي حل سادهتر میباشد. در این تحقیق هدف حل مساله مذکور با استفاده از روش تقریب هذلولی میباشد.
ضمن آنکه بدنبال ارزیابی تاثیرپایداري الگوریتم مورد نظرهستیم. ضرورت انجام این تحقیق، بررسی امکان استفاده از چنین روشهایی براي سایر مسائل پیچیدهترنظیرطراحی شبکه زنجیره تامین و... می باشد. نتایج این تحقیق میتواندامکان پذیري توسعه سایر الگوریتمهاي ابتکاري رابراساس این الگوریتم تضمین نماید . در این تحقیق الگوریتمهاي ارائه شده به زبان برنامه نویسی سی شارپ - - C# کد شده و عملکرد محاسباتی مناسبتري را نسبت به سایر زبانهاي محاسباتی نظیر متلب نشان می دهد. ساختار این تحقبق به صورت زیر است: دربخش آتی، مطالعات پیشین مورد بررسی قرار میگیرد؛ سپس مدلسازي مساله مکانیابیتخصیص در دو حالت بدون ظرفیت وظرفیت دار به همراه توصیف آنها در بخشهاي 3و4 ارائه شدهاست. مثالهاي عددي در بخش 5 ارائه شدهاست و نهایتا نتیجه گیري در بخش آخر آمده-است.
.2مرور ادبیات
مساله مکانیابی- تخصیص نخستین بار توسط کوهن و هامبورگر [6]مطرح شد. در واقع این مساله یکی از مسائل استقرار تسهیلات که در آن تعداد بهینه تسهیلات، محل استقرار تسهیلات و نحوه تخصیص آنها به مشتریان براي تامین تقاضاي مشتریان تعیین میشود. مکانیابی تخصیص داراي انواع گوناگونی میباشد که مختصرا به آنها اشاره میشود. این مسائل در فضاي گسسته و پیوسته تعریف میشوند. در فضاي گسسته با داشتن تعدادي محل بالقوه به دنبال یافتن تعداد، محلهاي استقرار تسهیلات جدید و نحوهي تخصیص مشتریان به تسهیلات میباشیم که با توجه به مساله هر تقاضا میتواند به یک یا چند تسهیل تخصیص یابد. تسهیلات میتوانند داراي ظرفیت محدود و یا نامحدود[7] باشند.
یکی از روشهاي ابتدایی حل فرمولبندي صفر و یک میباشد که حل توسعهیافته آن توسط افرویمسن و راي ارائه شده است که مساله بصورت برنامهریزي عدد صحیح صفر و یک مختلط فرمولبندي میشود و به روش شاخه و کران حل میگردد [9 , 8].مسئله در فضاي پیوسته همانند آنچه در مساله گسسته بیان شد، این نوع نیز میتواند با ظرفیت محدود یا نامحدود[11 , 10] مورد بررسی قرار گیرد . فرق اساسی این نوع با نوع گسسته در آن است که تسهیلات میتوانند در هر مکانی قرار گیرند و نقاط کاندیدایی وجود ندارد که این امر موجب پیچیدگی حل مساله میگردد.
در تمام موارد قید شده میتوان مساله را با توجه به نوع فاصله میان تسهیل و تقاضا مورد بررسی قرار داد. که از جمله آنها حل مساله با فاصله متعامد، مستقیم - اقلیدسی - و یا مربع اقلیدسی فراخور نوع مساله میباشد. از ترکیب روشهاي تصمیم گیري با معیارهاي چندگانه مثل DEAو برنانمه ریزي آرمانی میتوان براي حل موثر مساله مکانیابی- تخصیص استفاده نمودکه در آن مکانهاي موجود به کمک معیارها مورد نظر ارزیابی می-شوند، سپس براي محل هاي انتخاب شده مساله را حل مینماییم . [12] همچنین مساله را در حالتی حل نمود که تعادل در تخصیص نیز مد نظراست.[13] روشهاي حل گوناگونی براي حل مسائل مکانیابی–تخصیص وجود دارد. [19-14 ,11 ,6-4] که شکل - 1 - دسته بندي کلی روشهاي حل را نمایش میدهد.
شکل.1 دسته بندي کلی روشهاي حل
روش تقریب هذلولی - HAP - یکی از روشهاي تقریبی براي حل مساله مکانیابی میباشد . که در آن بدنبال پیدا کردن محل تسهیلات جدید با توجه به تقاضا یا تسهیلات موجود میباشیم. این روش براي حل مسائل با فاصله اقلیدسی مناسب میباشد؛ اما از آن براي سایر فواصل نیز میتوان استفاده نمود. با ایجاد تغییر در روش فوق روشی ابتکاري براي حل مساله مکانیابی–تخصیص ارائه شده است.
.3 مدل مساله درحالت ظرفیت نامحدود تسهیلات
در این مقاله هدف حل مساله مکانیابی تخصیص در فضاي پیوسته با در نظر گرفتن ظرفیت نامحدود تسهیلات میباشد. که در آن از روش HAP براي حل استفاده میشود؛ فرضیات مدل در الگوریتم HAP لحاظ میگردند. فرضیات مدل به شرح ذیل میباشد:
-1 مکان استقرار مشتریان - تقاضا - و میزان تقاضاي هریک از آنها مشخص است.
-2 محدودیت ظرفیت براي تسهیلات وجود ندارد.
-3 تسهیلات کاملا مشابه هستند.
-4 بین تسهیلات ارتباطی وجود ندارد . - ارسال و دریافت ندارند. -
-5 هر مشتري تنها به یک تسهیل تخصیص مییابد.
-6 فاصله میان مشتري و تسهیل از نوع اقلیدسی یا مستقیم میباشد.
-7 هزینه استقرار براي تسهیلات یکسان است.
در این مساله پارامترها عبارتند از میزان تقاضاي هر مشتري که با w نشان داده میشود، محل تقاضاها P - بردار مختصات تقاضا - ai ,bi می باشد. m تعداد تقاضا هاي موجود و هزینه استقرارتسهیل jام که با Costj نمایش داده میشود. nمتغیري است که تعداد تسهیلات جدید جهت استقرار را مشخص میکند و کمترین مقدار آن 1 و بیشترین مقدار آن برابر با تعداد محل هاي تقاضا - مشتریان - میباشد ؛kنشان دهندهي حداکثر نوع تسهیلات جدید میباشد. - بردار مختصات مکان تسهیلات جدید - محل استقرار تسهیلات جدید میباشد؛پارامتر میزان ارتباط بین تسهیل جدید i, j را بیان میکند.
مقدار صفر و یک دارد و مشخص کننده تخصیص مشتري به تسهیل میباشد و بصورت - - 1 تعریف می شود؛ متغیر باینري بصورت - 2 - تعریف میشود. تعاریف فوق و فرض ≤ - 2.3مدل - در تمام این مقاله برقرار می باشد. در قسمت 3 فرض بر یکسان بودن تمام هزینه هاي استقرار یا همان میباشد. تابع هدف مساله - 3 - کمینه کردن میزان هزینه حمل ونقل با توجه به فواصل بین تسهیل و مشتریان و هزینه استقرار تسهیلات با توجه به پارامترها و متغیر هاي تصمیم که تعداد تسهیلات نیز یکی از متغیر هاي تصمیم است، می باشد.محدودیت - 4 - تضمین میکند هرتقاضا تنها به یک تسهیل تخصیص می-یابد.محدودیت - 5 - نیز حداکثر تعداد تسهیلات جدید را کنترل مینماید.
