— (292)

مساله مکان یابی چند تسهیله چند دوره ای در حضور یک مانع خطی با گذرگاه های ظرفیت بندی شده
پايان نامه براي دريافت درجه كارشناسي ارشد در رشته مهندسي صنايع – صنايع
استاد راهنما:
دكتر نیکبخش جوادیان
استاد مشاور:
مهندس صابر شیری پور
دانشجو:
نادیا بهادران
تابستان 1392

تقديم به
پدر دلسوز
و
مادر مهربانم
تشكر و قدردانیاینجانب بر خود لازم می دانم که صمیمانه مراتب تشکر و قدر دانی را از همه بزرگوارانی که درراه کسب علم و دانش ودر طول انجام این پایان نامه از هیچگونه کمکی مضایقه نکردند و حامی و پشتیبان من بوده اند، به جای آورم:
جناب آقای دکتر نیکبخش جوادیان، استاد راهنما ، به پاس راهنماییهای بیدریغشان و پیشنهادات ارائه شده از سوی ایشان و همچنین ایشان در تمامی طول تحصیل بهترین راهنما و پشتیبان من در عرصه علم و دانش و به ثمر رساندن کارهای علمی و تحقیقاتی اینجانب بوده اند.
وجناب آقای دکتر صابر شیری پور، استاد مشاور، به پاس زحمات بی دریغشان که در تمام مدت انجام این پایان نامه دوشادوش بنده بوده و تلاش نموده اند این پایان نامه به بهترین شکل ممکن به انجام برسد.
هر کس به واسطه معلوماتیکه دارد عالم نیست،
بلکه به واسطه مجهولاتیکه در عالم احساس می کند،عالم است.
چکیدهاین تحقیق مساله مکان یابی چند تسهیله چند دوره ای با فواصل متعامد در حضور یک مانع خطی با تعدادی گذرگاه با ظرفیت های محدودرا در نظر میگیرد.هدف یافتن مکان تسهیلات جدید در میان تسهیلات موجود در دوره های مختلف می باشد بگونه ای که مجموع کل فواصل با مانع وزن دهی شده تسیهلات جدید با تسهیلات جدید و موجود حداقل شوند. برای این منظور یک مدل برنامهریزی غیر خطی ارائه شده است.همچنین یک تعداد از ویژگیهای مساله مورد بررسی قرار گرفته و در ادامه برای درک مسئله مذکور یک مثال ارائه شده است.نتایج محاسباتی این تحقیق، نشان میدهد که مساله توسط نرمافزار LINGO در اندازههای کوچک در زمان معقول به حل بهینه دست پیدا نمیکند. بهمنظور نشان دادن کارایی مساله در مقیاسهای بزرگ، یک الگوریتم فرا ابتکاری (الگوریتم ژنتیک) پیشنهاد شده است.
کلمات کلیدی:
مکان یابی چند تسهیله چند دوره ای؛ مانع خطی؛ گذرگاه های با ظرفیت محدود؛ فاصله متعامد

AbstractIn this research, we consider a multi-period multi-facility location problem with rectilinear distance in presence of a line barrier with the capacitated passages. The objective is to find the locations of n new facilities among m existing facilities in different periods to minimize the summation of the weighted rectilinear barrier distances between the locations of new facilities and new and existing facilities. The proposed problem is a mixed-integer nonlinear programming model. The computational results show that the LINGO 9.0 software is effective in solving problems with small sizes. But, for larger sized problems, we make use the one metaheuristic method namely the genetic algorithm (GA) for optimization.
Keywords:
The Multi-Period Multi-Facility Location; Line barrier; The Capacitated Passages; The Rectilinear distance.
فهرست مطالبعنوان صفحه
TOC \o “1-3” \h \z \u تشكروقدردانیPAGEREF _Toc360392525 \h‌دچکیدهPAGEREF _Toc360392526 \h‌وAbstractPAGEREF _Toc360392527 \h‌زفهرست مطالبPAGEREF _Toc360392528 \h‌حفهرست جداولPAGEREF _Toc360392529 \h‌كفهرست شکلهاPAGEREF _Toc360392530 \h‌ل1-1- مقدمهPAGEREF _Toc360392531 \h21-2-ساختارپایان نامهPAGEREF _Toc360392532 \h42-1- مقدمهPAGEREF _Toc360392533 \h62-2-مسایل مکانیابی همراه باموانعPAGEREF _Toc360392534 \h82-3- مسایل مکانیابی چندتسهیلهPAGEREF _Toc360392535 \h132-4- مسایل مکانیابی چنددوره ایPAGEREF _Toc360392536 \h153-1- مقدمهPAGEREF _Toc360392537 \h183-2- فواصل درمسایل برنامه ريزي تسهيلاتPAGEREF _Toc360392538 \h193-2-1- فاصله خط مستقيم يااقليدسيPAGEREF _Toc360392539 \h193-2-2- فاصله مجذورخط مستقيم يااقليدسيPAGEREF _Toc360392540 \h203-2-3- فاصله منهتن یامتعامدPAGEREF _Toc360392541 \h203-2-4- فاصله چبيشفPAGEREF _Toc360392542 \h213-2-5- كوتاه‌ترين مسيرPAGEREF _Toc360392543 \h223-3- دسته‌بندي كلي مسایل برنامه‌ريزي تسهيلاتPAGEREF _Toc360392544 \h223-4- دسته بندي مسایل مكان‌يابي بانگرش سنتیPAGEREF _Toc360392545 \h233-5- دسته‌بندي مسایل مكا‌ن‌يابي بانگرش نوينPAGEREF _Toc360392546 \h253-6- مسایل مکانیابی میانه باانواع فاصلهPAGEREF _Toc360392547 \h263-7- تشریح الگوریتم ژنتیکPAGEREF _Toc360392548 \h293-7-1- مفاهيم کليدي الگوريتم ژنتیکPAGEREF _Toc360392549 \h303-7-1-1- كدينگPAGEREF _Toc360392550 \h303-7-1-2- ايجادجمعيت اوليهPAGEREF _Toc360392551 \h313-7-1-3- عملگرهای الگوریتم ژنتیکPAGEREF _Toc360392552 \h313-7-1-4- تابع برازشPAGEREF _Toc360392553 \h343-7-1-5- استراتژي برخوردبامحدوديتهاPAGEREF _Toc360392554 \h343-7-2- ساختاركلي الگوريتم ژنتیکPAGEREF _Toc360392555 \h364-1- مقدمهPAGEREF _Toc360392556 \h394-2- ساختارمسالهPAGEREF _Toc360392557 \h404-2-1- محاسبه فاصلهPAGEREF _Toc360392558 \h434-2-2- مکانیابی چندتسهیله چنددوره ایPAGEREF _Toc360392559 \h454-2-3- مدل ریاضی پیشنهادیPAGEREF _Toc360392560 \h464-2-3-1- مثالPAGEREF _Toc360392561 \h534-3- الگوریتم ژنتیکPAGEREF _Toc360392562 \h574-3-1- نمايش كروموزومPAGEREF _Toc360392563 \h574-3-2- آغازسازیPAGEREF _Toc360392564 \h584-3-3- ارزيابيPAGEREF _Toc360392566 \h594-3-4- معیارتوقفPAGEREF _Toc360392567 \h594-3-5- نخبه گراییPAGEREF _Toc360392568 \h604-3-6- عملگرتقاطعPAGEREF _Toc360392569 \h604-3-6-1- عملگرتقاطع نوعIPAGEREF _Toc360392570 \h604-3-6-2- عملگرتقاطع نوعIIPAGEREF _Toc360392571 \h624-3-7- عملگرجهشPAGEREF _Toc360392572 \h644-3-8- انتخابPAGEREF _Toc360392574 \h654-5-1- مسایل نمونهPAGEREF _Toc360392575 \h675-1- نتیجه گیریPAGEREF _Toc360392576 \h765-2- پیشنهادات آتیPAGEREF _Toc360392577 \h77مراجع فارسیPAGEREF _Toc360392578 \h79مراجع لاتینPAGEREF _Toc360392579 \h80

فهرست جداولعنوان صفحه
فصـل دوم:TOC \h \z \c “جدول (2-”
فصـل سـوم:TOC \h \z \c “جدول (3-”
جدول (3- 1). توابع فاصله بکارگرفته شده درمسایل مکانیابی [3].PAGEREF _Toc360396332 \h28فصـل چهارم:TOC \h \z \c “جدول (4-”
جدول (4- 1). اطلاعات تسهیلات موجود.PAGEREF _Toc360396339 \h53جدول (4- 2). وزن بین تسهیلات جدیدPAGEREF _Toc360396340 \h53جدول (4- 3). اوزان مابین تسهیلات موجودوجدید.PAGEREF _Toc360396341 \h54جدول (4- 4). مختصات گذرگاههاPAGEREF _Toc360396342 \h54جدول (4- 5). ظرفیت گذرگاههاPAGEREF _Toc360396343 \h54جدول (4- 6). مختصات مکانهای بهینه تسهیلات جدیددرمثال نمونه.PAGEREF _Toc360396344 \h55جدول (4- 7). مقادیرپارامترهای الگوریتم ژنتیک.PAGEREF _Toc360396345 \h67جدول (4- 8). نتایج محاسباتی برای اندازه کوچک.PAGEREF _Toc360396346 \h69جدول (4- 9). نتایج محاسباتی برای اندازه بزرگ.PAGEREF _Toc360396347 \h71TOC \h \z \c “جدول (5-”

فهرست شکلهاعنوان صفحه
فصـل سـوم:
TOC \h \z \c “شکل (3-” شکل (3- 1). فاصله اقلیدسی درصفحهPAGEREF _Toc360395957 \h20شکل (3- 2). مسیرهای مختلف متعامدبینXو. XiPAGEREF _Toc360395958 \h21شکل (3- 3). دسته بندی کلی مسائل برنامه ریزی تسهیلات [1].PAGEREF _Toc360395959 \h23شکل (3- 4). دسته بندی نوین مسائل مکانیابی [1].PAGEREF _Toc360395960 \h25فصـل چهـارم:TOC \h \z \c “شکل (4-”
شکل (4- 1). تسهیلات موجودویک مانع خطی بادوگذرگاه.PAGEREF _Toc360395963 \h43شکل (4- 2). شرایط پدیداری.PAGEREF _Toc360395964 \h44شکل (4- 3). تقسیم فضای مساله به دونیم صفحه.PAGEREF _Toc360395965 \h47شکل (4- 4). مکان تسهیلات موجودوتسهیلات جدیددر 2 دوره.PAGEREF _Toc360395966 \h56شکل (4- 5). فلوچارت الگوریتم ژنتیکPAGEREF _Toc360395967 \h66شکل (4- 6).مقدارgapالگوریتم ژنتیک دراندازه های متفاوتPAGEREF _Toc360395968 \h72شکل (4- 7). نمودارمقایسه زمان محاسباتیLingo والگوریم ژنتیک دراندازه های متفاوت.PAGEREF _Toc360395969 \h74TOC \h \z \c “شکل (5-”

فصـل اول: کلیات تحقیق و ساختار پایاننامه

1-1- مقدمهيكي از مسایلي كه بايد در مراحل اوليه طراحي سيستم‌هاي صنعتي مورد توجه قرار گيرد مسالة مكان‌يابي (جایابی) واستقرار تسهيلات است. مطالعه پيرامون مكان بهينه از ديدگاه جغرافيدانان و علماي علم اقتصادي همواره داراي اهميت و اولويت بوده است [1].در ادبيات موضوعي، معمولاً چند حالت از مسایل مكانيابي پيوسته، مورد بحث قرار گرفتند، مانند مساله ميانه، مساله مركز و مساله مركز-ميانه. در مساله میانه هدف، پیدا کردن مکان وسیله (تسهیل) جدید میباشد، بطوریکه مجموع فواصل وزندهی شده بین تسهیل جدید و تسهیلات موجود، حداقل گردد. این مساله، در تئوری مکانیابی به مساله وِبِر و مساله کمینه مجموع نیز شهرت دارد. مسایل مکانیابی بر اساس نوع تابع فاصله نیز تقسیمبندی میشوند، مانند فاصله اقلیدسی و متعامد. مساله میانه با فواصل اقلیدسی یکی از قدیمی ترین مسایل مکانیابی تسهیلات میباشد. برای حل بهینه این نوع مساله، روشهای حل مختلفی پیشنهاد شدهاست که مشهورترین آن روش تکراریی میباشد، که توسط ویزفلد [2] توسعه داده شد.
در گونهاي از مسایل میانه با محدوديت در قرار گيري و يا حركتمواجه هستيم.در دستهای از این نوع مسایل، نواحی وجود دارند كه تسهيل (یا تسهیلات) جديد نه مي‌تواند در آنجا استقرار يابد و نه مي‌تواند از ميان آن عبور كند. این نواحي، نواحي بامانع ناميده مي‌شوند.درياچه‌ها، كوهستانها، مناطق نظامي، رودخانه‌ها و بزرگ‌راه‌ها ودر مقياس كوچكتر، ماشینآلات و واگنهای حمل مواد در كارخانجات، مثالهايي از اين نواحي مي‌باشند.این مسایل در مقایسه با مسایل مكانيابي كلاسيك خيلي عمليتر ونزديك‌تر به دنياي واقعي مي‌باشند، اما بهعلت پيچيد‌گي محاسباتي که اين نوع مسایل دارند، تنها در چند دهه اخير مورد بررسی قرار گرفتند. در برخی موارد با موانعی مواجه هستیم که عبور از آنها تنها از طریق چند گذرگاهبر روی مانع خطیامکان پذیر می باشد. مدل پیشنهادی این تحقیق، یک مساله میانه با فواصل متعامد میباشد، بطوریکه در ناحیه پیوسته یک مانع خطی افقی وجود دارد که بر روی آن تعدادی گذرگاه وجود دارد که ظرفیت هر یک از گذرگاه ها محدود می باشد. فرضیات مساله پیشنهادی بقرار زیر در نظر گرفته میشوند:
با مساله مکانیابی پیوسته میانه متعامد چند تسهيله با ظرفیت نامحدود برای تسهیلات جدید سرو کار داریم،
تعامل هم مابین تسهیلات جدید و جدید، و هم ما بین تسهیلات جدید و موجود برقرار است.
تابع فاصله از نوع متعامد می‌باشد.
تنها یک مانع خطی با تعدادی گذرگاه با مختصات های معین، در مدل وجود دارد.
مساله مکانیابی چند دوره ای میباشد.
ظرفیت هر یک از گذرگاه ها در دوره های مختلف محدود می باشد.
هر تسهیل موجود دارای مکان ثابت با مختصات معین، قطعی و دارای وزن غیرمنفی میباشد.
مانع بر روی یک مسیر افقی قرار دارد.
تسهیلات موجود در مسیر مانع مستقر نیستند.
تسهیلات جدید بر روی مسیر مانع خطی نمیتوانند استقرار یابند.
1-2-ساختار پایاننامهدر ادامه در فصل 2، ادبیات موضوعی مسایل بامانع ومسایلمکان‌یابی چند تسهیله را مورد بررسی قرار خواهیم داد. در فصل 3 زمینههای علمی تحقیق شامل دستهبندی مسایل مکانیابی، انواع توابع فاصله، مساله مکانیابی کلاسیک و الگوریتم ژنتیک بطور مفصل تشریح خواهند شد. در فصل 4 به تشریح مساله و مدل پیشنهادی می پردازیم. در ادامه این فصل به منظور درک بهتر رفتار مدل، یک مثال نمونهای ارائه خواهیم داد، اما با توجه به پیچیدگیهای مدل پیشنهادی در مقیاس های بزرگ، الگوریتم فراابتکاریژنتیکرا معرفی و نتایج محاسبات مربوط به این الگوریتم را مورد بررسی قرار خواهیم داد. در نهایت، تعدادی از توسعههای آتی بههمراه نتیجهگیری در فصل 5 مورد بررسی قرار گرفتند.

فصـل دوم: مروری بر ادبیّات موضوعی مسایل مکانیابی بامانع

2-1- مقدمهمسایل مكانيابي تک وسیلهای (تک تسهیله) پيوسته در سطح، يكي از حوزه‌هاي گسترده در مدل سازي رياضي، در دنياي واقعي مي‌باشند، كه دراین مسایل يك تسهيل جديد (تسهیل عرضه) به مجموعهاي از تسهيلات موجود ( تسهیلات متقاضی)، با توجه به تقاضاهايشان، سرويس میدهد.
در ادبيات موضوعي، معمولاً چند حالت از مسایل مكانيابي پيوسته، مورد بحث قرار میگیرد، مانند مساله ميانه، مساله مركز و مساله مركز-ميانه.در مساله میانه كلاسيك( که غالبا مساله وبِر، مساله فرمارت اشنایدر وبر و مساله حداقل مجموعنیزنامیده ميشود)، در صدد یافتن مكان تسهيل جديد هستيم، بطوريكه مجموعه فواصل وزن دهي شده‌ با تسهيلات موجود، حداقل گردد.براي اطلاعات بیشتر در اين زمينه به فراهانی و حکمتفر [3] و کلامروس [4] مراجعه كنيد.در گونهاي از مسایل میانه، ‌با محدوديت در قرارگيري و يا حركت مواجه هستيم.در ادبيات موضوعي اين نوع مسایل، معمولاً سه دسته از اين مسا یل مورد مطالعه قرار گرفتهاند.اولين دسته، نواحي ممنوعه نامیده می شوند كه در این نواحی تسهيلاتنمي‌توانند درآنجا قرار گيرند اما حركت در ميان اين نواحي بلامانع و بدون جريمه مي‌باشد(مانند مناطق و پاركهاي حفاظت شده و یا مناطقی که مشخصههای جغرافیای از قبیل شیب تند زمین از ایجاد تسهیل مورد نظر ممانعت میکند).براي مطالعه بروي مسایل مكانيابي میانه ‌و مرکز درنواحی ممنوعه به هاماخر و نیکل [5]مراجعه كنيد.
دسته دوم به عنواننواحي متراکمشناخته میشوند كه در اين نواحي قرارگيري يك تسهيل ممنوع بوده اما حركت از ميان آن با جريمه همراه مي‌باشد(مانند درياچه‌اي كه، با قايق بتوان از دو طرف آن عبور و مرور كرد. برای نمونه، مسایل مکانیابی با نواحی متراکم، با سرعت و هزینههای سفر مختلف، در بوت [6] و بوت و کاوالیر [7] مورد بحث و بررسی قرار گرفتهاند.
دسته سوم نواحی هستند كه تسهيل جديد نه مي‌تواند در آنجا استقرار يابد و نه مي‌تواند از ميان آن عبور كند. این نواحي، نواحي با مانع ناميده مي‌شوند.درياچه‌ها، كوهستانها، مناطق نظامي، رودخانه‌ها و بزرگراه‌ها ودر مقياس كوچكتر، نوار نقاله‌ها،ماشینآلات موجود در كارخانجات، مثالهايي از اين نواحي مي‌باشند.
2-2- مسایل مکانیابی همراه با موانعاگر چه مسایل مكانيابي با مانع، در مقایسه با مسایل مكانيابي كلاسيك خيلي عمليتر ونزديك‌تر به دنياي واقعي مي‌باشند اما به علت پيچيدگي محاسباتي که اين نوع مسایل دارند، تنها در چند دهه اخير، وارد ادبيات موضوعيشده‌اند.
مدلسازي مكانيابي بانواحي با مانع‌، براي اولين بار توسط کاتز و کوپر [8] معرفي شد. نويسندگان يك مساله وبر صفحهای را با فواصل اقليدسي و يك مانع دايره‌اي در نظر گرفتند.همچنين آنها، نشان دادند كه چنين مسایلی دارای تابع هدف غيرمحدب هستند و در ادامه براي حل آن يك روش ابتکاری مبتني بر تکنیک کمینه سازی متوالی بدون محدودیت (SUMT) پيشنهاد دادند.بعداًکلامروس [9]‌، برخي فواصل جبري اين مساله را بررسي كرد. نویسنده، ناحيه شدني را به يك تعداد سلول‌هاي محدب با تابع هدف محدب تجزيه كرد. اگرN، تعداد تسهيلات موجود ‌باشد، تعداد این سلولهاي محدب تابع دوجملهای ( یعنی، برابر O(N2))میباشد. با توجه به اينكه با افزايشN، ساخت اين سلول‌هاي محدب سنگين و پر مشقت مي‌شود، بایشوف و کلامروس [10]،با پيشنهاد يك روشحل مبتني بر الگوريتم ژنتيك GA)) ، براين مشكل فائق گشتند. در ادامه بایشوف و همکاران [11] از متد فوق برای مساله مکانیابی- تخصیص تسهیلات در حضور موانع چندوجهی و فاصله اقلیدسی استفاده کردند. نویسندگان دو روش ابتکاری که هر کدام از روشها از دو حل ابتدای استفاده میکرد را معرفی کردند، سپس بر اساس نتیجه محاسباتی، به بررسی روشهای ابتکاری معرفی شده پرداختند.
انجا و پارلر[12] و، بوت و کاوالیر [13] براي مسایلمیانه در سطح و در حضور موانع چندوجهي، روشهای ابتکاریی را توسعه دادند. انجا و پارلر[12]بر مبناي مفهوم پدیداریو با بکارگیری الگوريتم كوتاهترين مسير دایجسترابراي مساله مكان‌يابي در حضور موانع چند وجهي (نه لزوما محدب) تحت شرایطی که تابع فاصله از نوع اقليدسي باشد، به کمک الگوریتم فرا ابتکاری شبیه سازی تبرید(SA)، حل بهينه تخميني را بدست آوردند. بوت و کاوالیر [13] حالت خاص مساله انجا و پارلر[12] را كه موانع چند وجهي محدب بودند را درنظر گرفتند.نویسندگان با استفاده از گراف پدیداریو با پیشنهاد يك روش ابتکاری، مساله وِبِر محدودیت دار ‌را به مسالهبدون وِبِر محدودیت در هر تکرار الگوریتم،تبدیلکردند، سپس بر اساس شرط توقف معرفي شده، الگوريتم منجر به حل بهینه موضعی شد.در ادامه کلامروس[14]‌، با يك رويكردتجزيه سازي متفاوت و كاراتر، مساله اصلي غير محدب را به يك تعداد زير مساله محدب متناهي تبدیلکرد، سپس يك حل دقيق و يك روش ابتکاری مبتني بر اين رويكرد تجزيه سازي، توسعه داد.
مکگاروی و کاوالیر [15] از روش اصلاح شده «مربع بزرگ مربع کوچک (BSSS)»، براي مساله مکانیابی میانهدر حضورموانع چندوجهی و فواصل اقليدسي بهره بردند. روشBSSS يك الگوريتم هندسی شاخه وكران مي‌باشد كه توسط هانسن و همکاران [16] پيشنهاد شد. روش BSSS در ابتدا برای حل مسایل مکانیابی تسهیلات ناخوشایند پیشنهاد شد. اين الگوريتم براي مسایلمكانيابي پيوسته به اين صورت طراحي شد كه از طريق گسسته سازي‌، یک سطح یا صفحه پيوستهناحيه شدني را به يك تعداد زير منطقه مربعي شکل تقسيم مي‌كند.
فریث و همکاران [17] یک مساله مکانیابی مرکز را در حضور موانع چندوجهی همراه با تابع فاصله اقلیدسی در نظر گرفتند. نویسندگان با استفاده از رويكرد انتشار امواج راديويي دايره‌اي ، كوتاهترين فاصله بین نقاط را تعيين كردند و سپس يك آزمايش تجربي مورد بررسی قرار داده و يك شبيه سازي كامپيوتري براي فواصل اقليدسي و متعامد،ارائه کردند.
در حالت خاص از فاصله منهتن (متعامد)، نتایج گسسته سازی توسط لارسون و صدیق [18] برای مساله وِبِر با اشكال دلخواه موانع بررسی شد. نويسندگان با ايجاد ساختار شبكه‌اي (شبكه موازاييكي) از گره ويال و با تعيين مجموعه متناهي مسلط و با بکارگیری مساله p-median، مشخص كردند كه این شبکه حاوي حداقل يك حل بهينه مي‌باشد.
مقاله فوق زمينهای برای توسعه و تحقيقات مشابه شد. باتا و همکاران [19]، دو مساله مكانيابي سطحي با فاصله متعامد را هم براي نواحي ممنوعه و هم موانع با اشکال دلخواه در نظر گرفتند. نويسنگان ابتدا يك مساله p-median و سپس يك مساله صف احتمالی میانه را در حضور موانع با اشکال دلخواه بررسي كردند.
گسسته سازي مشابه با لارسون و صدیق [18]، توسط هاماخر و کلامروس [20] براي مساله وِبِر با موانع و فواصل بلوکی، انجام گرفت. كارايي محاسباتي روشهاي فوق‌الذكر، توسط دیرینگ و سگراس [22-21] بطور قابل ملاحضه ای بهبود داده شد. نويسندگان نشان دادند که يك مجموعه مسلط کاهیده شده براي اين مساله کافی و مناسب مي‌باشد. همچنين دیرینگ و همکاران [23] نيز يك الگوريتم مبتني بر يك مجموعه متناهي كانديد، به نام مجموعه مسلط‌ براي مساله مرکز با فواصل متعامد پيشنهاد كردند.اين نتايج سپس توسط دیرینگ و همکاران [24] برای فواصل با نُرم بلوکی توسعه داده شدند.
دسته‌اي ديگر از تحقيقات، در ادامهی مطالعات لارسون و صدیق [18] و باتا و همکاران [19] توسط ساواش و همکاران [25]‌ آغاز شد. نويسندگان مدلي براي قرارگيري تسهيلات با اندازه متناهی توسعه دادند كه ممکن است اندازهشان براي خودشان به عنوان مانع عمل کنند. وانگ و همکاران [26]، مساله مكانيابي تك تسهيله را در جانماییکف یک فروشگاهبا فواصل متعامد مورد مطالعه قرار دادند. در اين مقاله، با توجه به نقاط ورودی و خروجی تسهيلاتِ تقاضایِ مستطيلي شكل با مکان ثابت‌، حداقل هزينه‌ي مسافتِ كل، از تسهيل عرضه، كه به اين تسهيلات سرويس مي‌دهد، بدست آمد.گسترشي از کار ساواش و همکاران [25] توسط کلاچنکاتیو و همکاران [27]، انجام شده است. نویسندگان استقرار يك تسهيل با اندازه محدود را در چیدمان در صورتي كه تسهيل جديد و دپارتمانهاي موجود مستطيل شكل و فواصل ازنوع نرم 1l‌ باشند، در نظر گرفتند. آنها بواسطه اينكه تسهيل جديد بعلت برخي محدوديتها نمي‌تواند در مكان بهينه استقرار يابد، از خطوط كانتور به منظور یافتنِ مكان مناسب جايگزين برای دپارتمان جديد، استفاده كردند.
ناندیکوندا و همکاران [28] مساله مكانيابيمرکز ‌را در حضور موانع با اشکال دلخواه و فواصل منهتن بررسي كردند. نویسندگان از تكنيك تجزيه سازي ناحيه شدني به سلولها كه توسط لارسون و صدیق [18] مطرح شده بود را براي اين مساله توسعه دادند.گسترشی از مطالعه ناندیکوندا و همکاران [28]، توسط سرکار و همکاران [29] كه مكانيابي يك تسهیل با اندازه محدود و شکل دلخواه ‌را در حضور موانع با اشکال دلخواه و تابع هدف مرکز و تابع فاصله متعامد در نظر گرفتند، انجام شد.همچنين نویسندگان، بر خلاف ساواش و همکاران [25] ‌بجاي مساله میانه‌،مساله مرکزرا و همينطور فقط رابطه ميان تسهيل جديد و تسهیلات موجود را در نظر گرفتند.
در ادبيات موضوعي مسایلوِبِر علاوه بر موانع چندوجهی و دایرهای، يك مانع خطي، همراه با تعدادي گذرگاه توسط کلامروس [30] براي هر نوع فاصله دلخواه، معرفي شد. در ادامه کلامروس و ویچک [31] مدل فوق را براي مساله دو هدفه میانه بررسي كردند. شیری پور و همکاران [32] مساله مکانیابی- تخصیص ظرفیت دهی شده را در حضور یک مانع خطی با تعدادی گذرگاه با فاصله متعامد را مطرح و یک مدل غیرخطی برای این مساله ارائه دادند. آنها تاثیر تعداد و مکان گذرگاه ها بر روی مکان تسهیلات جدید و تخصصیص تسهیلات موجود به جدید را مورد بررسی قرار دادند. در ادامه امیری عارف و همکاران [33] مدل فوق را برای فاصله اقلیدسی بررسی کردند.
2-3- مسایل مکانیابی چند تسهیلهدر دسته ای دیگر از مسایل وبر که مسئله مکانیابی چند تسهیله نامیده میشوند، ما مکانهای بیش از یک تسهیل جدید را در فضای شدنی مسئله جستجو میکنیم. در واقع مسایل مکانیابی تک تسهیله حالت خاصی ازمسایل مکانیابی چند تسهیله می باشند با این تفاوت که در مکانیابی چند تسهیله نه تنها بین تسهیلات جدید و موجود تعامل برقرار است بلکه تسهیلات جدید نیز با یکدیگرتعامل دارند و بایستی تصمیمگیری راجع به مکانهای چند تسهیل بطور همزمان صورت گیرد.
فرانسیس [34] یک حالت خاصی از مسئله مکانیابی چند تسهیله با فاصله متعامد را در نظر گرفت که در آنجا تمامی اوزان یکسان فرض شدهاند. شرلی و شتی[35] یک مسئله مکانیابی چند تسهیله چند محصولی را معرفی کردند که تابع فاصله بکارگرفتهشده بصورت متعامد بوده است. وسکلوسکی و لاو[36، 37] از مفاهیم نواحی متعامد در مسئله مکانیابی چند تسهیله استفاده کردند و با در نظر گرفتن تسهیلات بصورت نواحی بیان داشتند که در بسیاری زمینه های متفاوت، می توان مکان عرضه را بصورت یک ناحیه (منطقه) در نظر گرفت ( مثل مکان یک کتابخانه یا خدمات اورژانسی). داکس [38] یک روش جدیدی برای مسایل مکانیابی چند تسهیله با فاصله متعامد معرفی کرد که در آن خوشههای بزرگی در نظر گرفته شده که چندین تسهیل جدید با همدیگر در یک نقطه قرار میگیرند.
ورجین و راگرس [39] یک روش ابتکاری برای حل مسئله مکانیابی چند تسهیله با فاصله مستقیم معرفی کردند. این روش درهر مرحله، ابتدا یک تسهیل جدید را بطور موقتی در یک مکان مستقر میکند و سپس مکان تسهیل جدید بعدی را بر اساس مکانهای تسهیلاتی که تا کنون مستقر شده اند بدست میآورد. این فرآیند ادامه مییابد تا اینکه همه تسهیلات جدید مکانیابی گردند. داوود پور و نصرتی [40] یک روش فرا ابتکاری بهینهسازیجمعیت مورچگان برای مسایل مکانیابی چند تسهیله با فواصل متعامد و مستقیم ارائه دادندکه این الگوریتم برای نمونه های تا حدود 20 تسهیل جدید منجر به جواب بهینه شد. سیلوا و دلا فیگورا [41] یک مسئله مکانیابی تسهیل ظرفیتدهیشده با احتمالات پشتیبانی محدود شده را معرفی کردند. آنها تقاضا را بصورت احتمالی در نظر گرفتند و هر یک از تسهیلات را بصورت یک صف مستقل فرمول بندی کردند. سپس یک روش ابتکاری برای حل مدل فرمول بندی معرفی کردند. اسمالوود [42] مدلی را به منظور پیدا کردن مکانهای تعداد معینی ایستگاه بازرسی طراحی کرد و آنرا در غالب یک مطالعه موردی در ایالات متحده امریکا پیاده سازی کرد. به منظور تحقیق و بررسی بیشتر مسایل مکانیابی چند تسهیله، میتوانید به فراهانی و حکمتفر [3] مراجعه فرمایید.

2-4- مسایل مکانیابی چند دوره ایدر این قسمت، مقالات تحقیقاتی که در زمینه مدلسازی و یا حل مسایل مکانیابی تسهیل چند دوره ای انجام شده است، ارائه می شود. وسولووسکی [43]برای اولین بار هزینه جابجایی-مستقل را معرفی کرد. سپس کلی و ماروچک[44]یک مدل برنامه ریزی خطی صحیح ترکیبی برای مسئله مکانیابی پویا در یک افق برنامه ریزی معین معرفی کردند. فرانتزسکیکیس و واتسون گاندی [45]یک مسئله مکانیابی تسهیل چند دوره ای با جابجایی در طی یک افق برنامه ریزی داده شده را توصیف نمودند و روش های برنامه ریزی پویا و شاخه و حد را برای حل چنین مسائلی پیشنهاد کردند. گالواو و سانتیبانز-گونزالس [46]تعمیمی از مسئله p-میانه را ارائه دادند و برای حل این مسئله یک روش ابتکاری لاگرانژی را معرفی کردند. کارنت و همکاران [47]یک مسئله مکانیابی تسهیل چند دوره ای چند معیاره را توسعه دادند که در آن تعداد کل تسهیلاتی که مکانیابی شده اند نامعین می باشد. هینوجوسا و همکاران [48] یک مسئله مکانیابی تسهیل ظرفیت بندی شده دو چند چند دوره ای را مورد بررسی و یک مدل برنامه ریزی صحیح ترکیبی برای آن ارائه دادند. آنها از یک ساده سازی لاگرانژی بهره گرفتند و مدل را ساده نمودند و یک روش حل ابتکاری برای حل مسئله ارائه دادند. سپس، کنل و همکاران [49]یک مسئله مکانیابی تسهیل ظرفیت بندی شده چند چند مرحله ای چند دوره ای با جابجایی مجاز تسهیل را مورد بررسی قرار دادند. آنها یک الگوریتم بوسیله روش های صحیح سازی DP و شاخه و حد پیشنهاد دادند. ملو و همکاران [50]یک مدل ریاضی برای مسئله مکانیابی تسهیل ظرفیت بندی شده چند چند دوره ای در اندازه ای بزرگ با در نظر گرفتن جابجایی تدریجی تسهیلات در طول افق برنامه ریزی، فرموله کردند. سپس، ملو و همکاران [51] روی همین مسئله برای برنامه ریزی زنجیره تامین استراتژیک متمرکز شدند. بعلاوه، ملو و همکاران [52] یک مسئله مکانیابی تسهیل چند دوره ای کلی با مکانیابی مجدد (جابجایی) برای مسائل مقیاس بزرگ را مورد بررسی قرار دادند و سپس یک الگوریتم ابتکاری دو مرحله ای کارا برای حل مساله معرفی کردند. وانگ و همکاران [53] یک مدل برنامه ریزی ریاضی برای یک مسئله مکانیابی با محدودیت بودجه با در نظر گرفتن جابجایی بعضی از تسهیلات موجود در طی افق برنامه ریزی پیشنهاد و سه الگوریتم ابتکاری نیز برای حل این مدل ارائه دادند. پورتو و رودریگز-چیا [54]مسئله مکانیابی تسهیل چند دوره ای تعمیم یافته در فضای یک بعدی و دو بعدی را بوسیله الگوریتم ویزفلد حل کردند و همگرایی روش شان به سمت جواب منطقی را ثابت نمودند. یک مسئله مکانیابی پویا با باز سازی، بسته سازی و بازسازی مجدد تسهیلات توسط دیاس و همکاران [55] پیشنهاد داده شد. آنها یک روش ابتکاری اولیه-دوگان برای حل این مسئله ارائه دادند که بطور متوالی منجر به جوابهای خوب گشته است. یک مسئله مکانیابی تسهیل ظرفیت بندی شده چند چند دوره ای با جابجایی تسهیلات یا تغییر ظرفیت در طی یک افق زمانی توسط بهمردی و لی [56] مورد تحقیق قرار گرفت. یک مسئله مکانیابی تسهیل چند دوره ای چند هدفه با ظرفیت محدود و نامحدود با بیشتر از یکبار جابجایی در طی افق برنامه ریزی توسط دیاس و همکاران [57] مورد تحقیق و بررسی قرار گرفته است. البردا و همکاران [58]یک مسئله مکانیابی تسهیل خدمات چند دوره ای در طی یک افق زمانی معین را معرفی کردند. آنها برای بدست آوردن حدود پایین و بالا، روش های ابتکاری را پیشنهاد دادند. سرانجام آنها نشان دادند که در آزمایشات محاسباتی بین این حدود درصد اختلاف کمی وجود دارد. یک مسئله مکانیابی تک تسهیله با وزن های وابسته به زمان برای فواصل متعامد، مستقیم و مجذور فاصله مستقیم توسط فراهانی و همکاران [59]مورد تحقیق قرار گرفت که در آن بیان شده است که افق زمانی می تواند معین یا نامعین باشد. به منظور واقعی تر شدن مسئله، آنها یک هزینه جابجایی وابسته به مکان را در مدل در نظر گرفتند. همچنین برای حل مسئله یک الگوریتمی ارائه دادند که منجر به جواب بهینه می گردد. بروتکورن و همکاران [60]یک بررسی جامع روی مدل های مکانیابی و جابجایی آمبولانس انجام دادند و سپس یک مسئله مکانیابی آمبولانس پویا با جابجایی در سرتاسر روز پیشنهاد دادند. باسار و همکاران [61]یک روش دو-همگرایی چند دوره ای برای مکان ایستگاه خدمات پزشکی اورژانس در استانبولبه منظور تامین یک ایستگاه پشتیبانی در حالتی که هیچ آمبولانسی در دسترس نیست، معرفی کردند و سپس مسئله را با استفاده از الگوریتم جستجوی ممنوع حل نمودند.
فصـل سوم: زمینـههای علمـی تحقیـق

3-1- مقدمهبرنامه‌ريزي تسهيلات كه از مباحث مهم در مهندسي صنايع است دو بخش عمده مکانیابی (جایابی) و طرا‌حي را شامل مي‌شود كه مهم‌ترين بخش طراحي، استقرار يا جا‌نمايي و بخش‌هاي ديگر آ‌ن، حمل ‌و نقل و طراحي ساختمان و تاسيسات منظور از تسهيلات، هر مجموعه، شامل كارخانه، دانشگاه، بيمارستان و غیره است.
در مکانیابی، ما به برر‌سي محل قرار گرفتن يك وسيله براي رسيدن به اهداف مورد نظر مي‌پردازيم كه براي تعيين محل آن، معيار‌هاي مهمي موثرند‌‌‌‌‌‌‌‌؛ از جمله نزديكي به جاده‌ها‌ي اصلي، بازار مصرف، منابع تأمين مواد اوليه، دردسترس بودن نيروي انساني مورد نياز، شرايط محيطي، امكان توسعه، مقرارت وقوانين دولتي و…، و در طرح استقرار مي‌خواهيم نحوه قرار گرفتن اجزاي يك وسيله را بر‌اي رسيدن به بهترين بهره‌وري تعيين كنيم. روش‌هاي زيادي تاكنون براي حل اين‌گونه مسایل مطرح شده‌اند كه از آن جمله مي‌توان به برنامه‌ريزي رياضي، استفاده از تصميم‌گير‌ي‌هاي چند‌گانه ‌و غیره اشا‌ر‌ه كرد [1].
مراكز صنعتي و كارخانجات براي تعين مكان احداث كارخانه، استقرار تجهيزات و دپا‌رتمانهاي خود در كارخانه، استقراردفاتر‌شان در سطح شهر، تعيين مراكز توزيع محصولات وغیره، با مسایل مکانیابی گونا‌گوني در بخش‌هاي دولتي و خصوصي، اعم از صنعتي و غيرصنعتي مواجه میشوند. در بخش‌ دولتي، تعيين مكان مراكز خدماتي، نظير ايستگاه‌هاي پليسراه، اورژانس، بيمارستان‌ها، ايستگاه‌هاي آتش‌نشاني و غیره نياز به اتخاذ چنين تصميماتي دارد. لذا تصميم‌گيري در مورد مكان‌يابي تسهيلات عمدتاً از تصميم‌گيري‌هاي بلندمدت و استراتژيك شركت‌هاي بزرگ خصوصي و دولتی است و هزينه‌هاي بالاي مربوط به جايايي و استقر‌ار و راه اندازي تسهيلات، پروژه‌هاي مكان‌يابي را به سرمايه‌گذاري‌هاي بلند مدت تبديل كرده است. لذا موفقيت يا شكست مراكز تسهيلاتي در هر كدام از بخش‌هاي دولتي و خصوصي، بستگي كامل به مكان‌هاي انتخابي براي‌آن‌ها دارد. بدين ترتيب، اهميت مساله مكان‌يابي واستقرار تسهيلات و ضرورت پرداختن بدان بر همگان روشن است [1].
3-2- فواصل در مسایل برنامهريزي تسهيلاتاگر مختصات تسهیل جديدX=(x,y) و براي وسيله موجود Xi=(xi,yi) در صفحه 2-بعدی باشند، آنگاه فواصل زير را مي‌توانيم تعريف كنيم.
3-2-1- فاصله خط مستقيم يا اقليدسيفاصله اقليدسي بين X و Xi به صورت زير تعريف مي‌شود :
(3-1) d2X,Xi=x-xi2+y-yi2 .فاصله اقليدسي براي برخي از مسایل جايايي شبكه، شامل نقاله و سفر هوايي به كار مي‌رود. برخي از مسایل سيم‌كشي الكتريكي و مسایل طراحي لوله‌كشي نيز نمونه‌ها‌يي از مسایل فاصله اقليدسي هستند. شکل (3-1) مسیر حاصل از این فاصله را بين X و Xi با خط تیره مشخص میسازد.
5797552423160شکل (3- SEQ شکل_(3- \* ARABIC1). فاصله قلیدسی در صفحه00شکل (3- SEQ شکل_(3- \* ARABIC1). فاصله قلیدسی در صفحه00X
Xi
x
y
00X
Xi
x
y

3-2-2- فاصله مجذور خط مستقيم يا اقليدسيدر برخي مسایل جايايي تسهيلات، هزينه تابع درجه اول فاصله نيست. به عنوان مثال، انتظار مي‌رود هزينه مرتبط با عكس‌العمل يك ماشين آتش‌نشاني با فاصله غيرخطي باشد. فرض كنيد، هزينه با مربع فاصله اقليدسی بين X و Xi متناسب باشد. فاصله اقليدسي بين X و Xiبه صورت زير تعريف مي‌شود:
(3-2) dESX,Xi=x-xi2+y-yi2. اين نوع فاصله مي‌تواند در مسایل خدمات اورژانس و آتشنشانی كاربرد داشته باشد.
3-2-3- فاصله منهتن یا متعامددر بيشتر مسایل مکانیابی ماشين، فاصله در مجمو‌عهاي از راهروهايي پيموده مي‌شود كه در الگويي مستطيلي و موازي با ديو‌ارهاي ساختمان هستند. در چنين وضعيتي، فاصله متناسب به صورت متعامد مستطيلي، كلان شهر‌ي يا منهتن است (گاهی اوقات فاصله خطی شکسته، پلهای و راهرویی نیز نامیده میشود). فاصله متعامد بين X و Xiرا بصورت زير تعريف ميكنيم‌‌:
(3-3) d1X,Xi=x-xi+y-yi.فاصله متعامد بر‌اي تحليل‌هاي جايابي شهري مناسب است كه در آن سفر در امتداد مجموعه محدبي از خيابان‌ها اتفاق مي‌افتد. به علا‌وه، تعدادي از ادارات، مجموعه از راهرو‌هاي و تا‌لارهاي متعامد را براي حركت پرسنل به كار مي‌برند. شکل (3-2) مسیرهای متعامد مختلف بین X و Xiرا نشان میدهد که فواصل متعامد یکسان دارند.
10534652018030شکل (3- SEQ شکل_(3- \* ARABIC2). مسیرهای مختلف متعامد بین X و . Xi00شکل (3- SEQ شکل_(3- \* ARABIC2). مسیرهای مختلف متعامد بین X و . Xi6350X
Xi
y
X
Xi
x
00X
Xi
y
X
Xi
x

3-2-4- فاصله چبيشففاصله چبيشف بين دو نقطه بینX و Xi با علامت t(X, Xi) نمايش داده ميشود و به صورت زیر تعريف ميگردد:
(3-4) tX,Xi=maxx-xi,y-yi.
در حالي كه فاصله متعامد برابر مجموع فواصل افقي و عمودي دو نقطه است. فاصله چبي‌شف بر‌‌ابر حداکثر فواصل ‌افقي و عمودي دو نقطه است.
از جمله كاربردهاي اين فاصله این است كه حركت مواد در كارخانه به كمك جرثقيل‌هاي مجهز‌‌‌ به دو موتور انجام مي‌شود كه موتور سبب حركت در جهت محور x‌ ها و ديگري سبب حركت در محورy ها است. همچنين در مسایل انتخاب سفارش نيز اين فاصله كاربرد دارد.
3-2-5- كوتاه‌ترين مسيردر مسایل مكان‌يابي روي شبكه از آن‌جا كه معمولاً بيش از يك مسير بين هر دو گره وجود دارد، روش كوتا‌هترين مسير براي تعيين فاصله بين دو گروه مورد استفاده قرار مي گيرد‌.
3-3- دسته‌بندي كلي مسایل برنامه‌ريزي تسهيلاتمسایل برنامه‌ريزي تسهيلات به چهار دسته عمده مكان‌يابي،مسیریابی، تخصيص و طراحي تقسيم مي‌شود. با تركيب اين مؤلفه‌ها مسایل مكان‌يابي- مسيريابي، مكان‌يابي- تخصيص به دست مي‌آيد [1]. در شکل (3-3) این دسته بندی نشان داده شده است.
6153153458210شکل (3- SEQ شکل_(3- \* ARABIC3).دستهبندی کلی مسائل برنامهریزی تسهیلات [1].00شکل (3- SEQ شکل_(3- \* ARABIC3).دستهبندی کلی مسائل برنامهریزی تسهیلات [1].00برنامهریزی تسهیلات
تخصیص تسهیلات
مکانیابی تسهیلات
مسیریابی تسهیلات
طراحی تسهیلات
مکانیابی- تخصیص تسهیلات
مکانیابی- مسیریابی تسهیلات
جانمایی تسهیلات
انتقال مواد
طراحی ساختاری
00برنامهریزی تسهیلات
تخصیص تسهیلات
مکانیابی تسهیلات
مسیریابی تسهیلات
طراحی تسهیلات
مکانیابی- تخصیص تسهیلات
مکانیابی- مسیریابی تسهیلات
جانمایی تسهیلات
انتقال مواد
طراحی ساختاری

3-4- دسته بندي مسایل مكان‌يابي با نگرش سنتیدسته‌بندهاي كلاسيك مسایل مكان‌يابي عمدتاً بر اساس موارد زير بوده است‌‌:
براساس خصوصيات وسايل جديد
مساله مكان‌يابي تك وسيله/چند وسيله
مساله مكان‌يابي با وسايل نقطه‌اي/ناحيه
بر اساس خصوصيات وسايل موجود
مساله مكان‌يابي با وسايل ايستا/پويا
مساله مكان‌يابي وسايل با مكان قطعي/احتمالي
بر اساس نوع ار تباط وسايل موجود وجديد
مساله مكان‌يابي با ارتباطات برون‌زا/درون‌زا
مساله مكان‌يابي با ارتباطات ايستا/پويا
مساله مكان‌يابي با ارتباطات قطعي/احتمالي
بر اساس فضاي جواب
مسایل مكان‌يابي روي خط/صفحه
مساله مكان يابي گسسته/روي شبكه
مساله مكان‌يابي با فضاي مقيد/نامفيد
بر اساس نوع تابع فاصله
مساله مكان‌يابي با فواصل متعامد/چبيشف
مساله مكان‌يابي با فواصل اقلیدسی/مجذور اقلیدسی
مساله مكان‌يابي با سنجههای خاص
بر اساس نوع و تعداد هدف و شاخص انتخاب
مسایل تك هدفه/چند هدفه
مسایل تك شاخصه/چند شاخصه
مسایل ميا‌نه/ مركز / پوشش
بر اساس زمينه مساله
مساله مكان‌يابي انبار/كارخانه
مساله مكان‌يابي نقاط تبادل
مساله مكان‌يابي وسايل ناخو‌شايند
مساله مكان‌يابي وسايل گردشي«مسایل مكان‌يابي- مسير‌يابي»
مساله مكان‌يابي سلسه‌ مراتبي
3-5- دسته‌بندي مسایل مكا‌ن‌يابي با نگرش نوينمسایل مكان‌يابي و استقرار را بر مبناي نگرش در مدل‌سازي و حل در شکل (3-4) دسته‌بندي شدهاند. در اين دسته‌بندي چهار رويكرد عمده نظری و عملي وجود دارد.
2006604136390شکل (3- SEQ شکل_(3- \* ARABIC4).دسته بندی نوین مسائل مکانیابی[1].00شکل (3- SEQ شکل_(3- \* ARABIC4).دسته بندی نوین مسائل مکانیابی[1].00SLF
DFL
CFL
رویکردهای استراتژیک
FL
NN
MH
هوش مصنوعی
ٍEG
IT
رویکردهای عملی
SCM
DM
EM
رویکردهای دیگر
SLF : مکانیابیتسهیلات استراتژیک
DFL : مکانیابی تسهیلات پویا
CFL : مکانیابی تسهیلات رقابتی
FL : منطق فازی
NN : شبکههای عصبی
MH : الگوریتمهای فراابتکاری
EG : جغرافیای اقتصادی
IT : فنآوری اطلاعات
SCM : مدیریت زنجیره تامین
DM : داده کاوی
EM : سنجش بهره وری
یادداشت:
00SLF
DFL
CFL
رویکردهای استراتژیک
FL
NN
MH
هوش مصنوعی
ٍEG
IT
رویکردهای عملی
SCM
DM
EM
رویکردهای دیگر
SLF : مکانیابیتسهیلات استراتژیک
DFL : مکانیابی تسهیلات پویا
CFL : مکانیابی تسهیلات رقابتی
FL : منطق فازی
NN : شبکههای عصبی
MH : الگوریتمهای فراابتکاری
EG : جغرافیای اقتصادی
IT : فنآوری اطلاعات
SCM : مدیریت زنجیره تامین
DM : داده کاوی
EM : سنجش بهره وری
یادداشت:

3-6- مسایل مکانیابی میانه با انواع فاصلهدر اين قسمت، مساله تعيین مكان چند وسيله جديد نسبت به يك تعداد وسيله موجود مورد بررسي قرار مي‌گيرد. مكانهای كه به دنبال آنها هستيم، جايي است كه يك تابع هزينه كل تعريف شده را حداقل ميكند و هز ينه كل مذ‌كور متناسب با فاصله در نظر گرفته مي‌شود.
تعدادي از مسایل مکانیابی چند تسهيله جالب وجود دارند كه براي نمونه تعيين مكان تسهيلات زير قابل ارائه است:
ماشينهای تراش جديد در يك مكان توليدي،
انبارهای جديد بر‌اي تسهيلات توليدي و مشتريان،
بيمارستان، ايستگاه آتشنشاني، اداره پليس يا كتابخانه در يك كلانشهر،
ساختمانهای كلاس درس جديد در زمين يك دانشكده،
مناطق هوايي جديد كه براي تامين تعدادي پايگاه‌هاي نظامي استفاده مي‌شود،
جرثقيل در بخشي از بزرگراه براي پيش‌بيني تصادفات ترافيكي،
سكوهاي بارگيري در يك انبار،
اسبابهای جديد در يك آشپزخانه،
منابع آب در يك ساختمان،
دستگاههای كپي در يك كتابخانه،
به عنوان نمونه خيلي ساده از مساله مکانیابی چند تسهيله، وسایل جديد مي‌تواند كارخانههایی باشند كه تامين كننده انبارهايي است كه تسهيلات موجودند وهزينه‌هاي حمل ونقل متناسب با فاصله بين كارخانه وانبار‌ها هستند؛ wij مي تواند هزينه كل حمل ونقل به ازاي هر واحد فاصله بين كارخانهj-ام و انبارi-ام باشد، و همچنینvjk مي تواند هزينه كل حمل ونقل به ازاي هر واحد فاصله بين كارخانههای جدید j-ام و k-ام باشد. در نمونه ديگر، وسايل جديد مي‌توانند ماشينهایی جديد باشند كه قرار است در يك طرح استقرار ماشين‌آلات جايابي شوند. از آنجا كه محصولات بين ماشين‌هاي جديد و موجود به عقب و جلو سفر ميكنند، هزينهها متناسب با فاصله هستند.
سوال اين است كه «يك فاصله متناسب» به چه معنا است؟
در بيشترمسایل جايابي ماشين، فاصله در مجموعهاي از راهروهايي پيموده ميشود كه الگويي مستطیلي و موازي با ديوارهاي ساختمان هستند. در چنين وضعيتي، فاصله متناسب به صورت متعامد، مستطيلي، يا منهتن است. چنانچه از فاصله متعامد بين Xj، j=1,…J و Xi، i=1,…I، استفاده كنيم تابع هزینه کل، به صورت زير در مي‌آيد:
(3-5) f(X)=i=1Ij=1Jwijxj-xi+yj-yi+j=1Jk=1k>jJvjkxj-xk+yj-yk.فاصله متعامد براي برخي تحليل‌هاي جايابي شهري مناسب است كه در آن سفر در امتداد مجموعه محدبي از خيابان‌ها اتقاق مي‌افتد. به علاوه، تعدادي از ادار‌ات، مجموعه‌اي از راهروها و تالارهاي متعامد را براي حركت پرسنل به كار مي‌برند. در اين حالت هزينه تابع خطي درجه اول از فاصله است.
در برخي مسایل جايابي تسهيلات، هزينه، تابع خطي درجه اول نيست. به عنوان مثال، انتظار مي‌رود هزينه مرتبط با عكس‌العمل يك ماشين آتش‌نشاني با فاصله غير خطي متناسب باشد، بنابر‌اين در مساله جايابي f(x) ميتواند فرمول بندي‌هاي متفا‌وتي داشته باشد.
يكي از شكل‌هاي f(x) غيرخطي هنگامي است كه فاصله به صورت خط مستقيم يا اقليدسي باشد. اگر مختصات تسهیلات جديدXj=(xj,yj) و براي وسيله موجود Xi=(xi,yi) باشند، رابطه هزينه کل برای فواصل اقلیدسی بهشرح زیر میباشد:
(3-6) f(X)=i=1Ij=1Jwij2xj-xi2+yj-yi2+j=1Jk=1k>jJvjk2xj-xk2+yj-yk2.فاصله اقليدسي براي برخي از مسایل جايابي شبكه، شامل نقاله‌‌ها وسفر هوايي به كار مي‌رود. برخي از مسایل سيم‌كشي الكتر‌يكي و مسایل طراحي لوله‌كشي نيز نمونه‌هايي از مسایل فاصله اقليدسي هستند.
يكي ديگر از شكل‌هاي f(x) غيرخطي كه در اين قسمت بررسي مي‌شود مساله مركز ثقل یا مربع اقلیدسی است. فرض كنيد هزينه با مربع فاصله اقليدسي بين Xj، j=1,…J و Xi، i=1,…I، متناسب باشد. بنابر‌اين، رابطه هزينه به صورت زير در مي‌آيد:
(3-7) f(X)=i=1Ij=1Jwijxj-xi2+yj-yi2+j=1Jk=1k>jJvjkxj-xk2+yj-yk2.مسایل جايابي كه فرمول‌بندي داده شده در رابطه فوق را دارند به مسایل مركز ثقل تعبير مي‌شوند.
جدول (3-1) يك مرور اجمالي براي تعدادی از انواع مسایل مکانیابی، توابع فاصله بكار رفته و توسعه‌دهندگان آن‌ها را نشان مي‌دهد.
جدول (3- SEQ جدول_(3- \* ARABIC1). توابع فاصله بکار گرفتهشده در مسایل مکانیابی [3].سال توسعه مساله تابع فاصله توسعهدهندگان
1909 مساله مکانیابی پیوسته اقلیدسی وبر
1937 مساله مکانیابی چند تسهیله اقلیدسی ویزفلد
1963 مساله مکانیابی چند تسهیله متعامد فرانسیس
1973 مساله مکانیابی چند تسهیله اقلیدسی و متعامد (روش HAP) ایستر و همکاران
1981 مساله مکانیابی میانه با مانع اقلیدسی کاتز و کوپر
1983 مساله مکانیابی میانه با مانع متعامد لارسون و صدیق
1986 مساله مکانیابی تسهیلات ناخوشایند اقلیدسی و متعامد ملاچرنیودیس و کولینین
1994 مساله مکانیابی رقابتی اقلیدسی درزنر
3-7- تشریح الگوریتم ژنتیکالگوريتمهايژنتیکتکنيکنسبتاًجديدیهستندکه،ازآنبرای حل مسایل مختلفاستفادهشدهاست.دوويژگي اصلي اينتکنيکيکيالهامگيريآنازپديدههايطبيعيخلقتوديگريقابليتپردازشموازيميباشد. الگوريتمهايژنتیکباالهامازفرآيند تکاملطبيعيوبهعنوانيکروشجستجويهوشمنددرحلمسایلبهينهسازيکاربردگستردهاي يافتهاست. الگوریتم ژنتیک برگرفته از الگوريتم تکاملی است که اولين بار توسط جان هالند [62] در دانشگاه ميشيگان پيشنهاد شد و استراتژي‌ها و برنامه‌ريزي‌هاي تکاملي که توسط رچنبرگو چيفل و فوگوگل و کوزا ايجاد شدند، از جمله روش‌هاي محاسبه تکاملي هستند.
روش‌هاي بهينه‌سازي الهام گرفته از طبيعت با روش‌هاي متعارف بهينه‌سازي تفاوت مهمي دارند. در روش‌هاي متعارف هرجواب کانديداي جديد در صورتي به عنوان جواب جديد انتخاب مي‌شود که مقدار تابع هدف را بهبود بخشد ولي در الگوريتم‌هاي الهام گرفته از طبيعت به تمام جواب‌هاي کانديداي جديد شانس انتخاب داده مي‌شود.الگوريتم‌هاي ژنتیک، تکنيک‌هاي جستجوي تصادفي هستند که بر اساس انتخاب طبيعي و نسل‌شناسي طبيعي کار مي‌کنند. الگوريتم ژنتیک روشي مستقل از دامنه مساله است و به سرعت فضاي جستجو را براي نقاطي با تابع صلاحيت بهتر، جستجو مي‌کند.
3-7-1- مفاهيم کليدي الگوريتم ژنتیکبا نگاهي به آنچه تا كنون مطرح شده مشخص است كه در تبيين الگوريتم ژنتیک مباحث كليدي ذيل بايد مورد بررسي قرار گيرند. بنابراين در ادامه اين مباحث بررسي خواهند شد:
تعريف يك سيستم كدينگ
ايجاد جمعيت اوليه
تعريف عمليات ژنتيك
تابع برازش
استراتژی برخورد با محدوديتها
3-7-1-1- كدينگاولين گام در بكارگيري و پيادهسازي يك الگوريتم ژنتیک نمايش جواب‌هاي مساله بصورت يك كروموزوم است. در حقيقت اين عمل يك مفهوم كليدي در الگوريتم‌هاي ژنتيك مي‌باشد که با استفاده از عمل کدینگ ما می توانیم مسئله را به زبان برنامه نویسی تبدیل نماییم.
3-7-1-2- ايجاد جمعيت اوليهاولين مرحله بعد از تعيين تكنيكي كه براي تبديل هر جواب به يك كروموزوم بكار مي‌رود ايجاد يك جمعيت اوليه از كروموزوم‌هاست. در اين مرحله جواب اوليه معمولاً به صورت تصادفي توليد مي‌شود. البته در بعضي موارد با توجه به نوع مساله و براي بالابردن سرعت همگرايي الگوريتم از روش‌هاي ابتكاري نيز استفاده گرديده است.
3-7-1-3- عملگرهایالگوریتم ژنتیکعمليات ژنتيك فرآيند انتقال موروثي ژن‌ها را براي ايجاد اولاد جديد در هر نسل تقليد مي‌كنند. يك بخش مهم در الگوريتم ژنتیک ايجاد كروموزوم‌هاي جديد موسوم به اولاد از طريق بعضي كروموزوم‌هاي قديم موسوم به والدين است. اين فرآيند مهم توسط عمليات ژنتیک صورت مي‌گيرد. به طور كلي اين عمليات توسط دو عملگر عمده انجام مي‌شود. عملگر جهشي و عملگر تقاطعي. اما عملا عملگرها بر حسب نوع مساله تعريف شده و كاملا به توانايي تحليل‌گر وابسته بوده و تجربي مي‌باشند. كارايي اين عملگرها در رسيدن به جواب بهينه در مسايل مختلف متفاوت است. بعضي از عملگرها فقط يك كروموزوم را در نظر گرفته و بر اساس اطلاعات آن، كروموزوم ايجاد مي‌كنند اما بعضي ديگر بر روي چند كروموزوم يا حتي كليه كروموزوم‌هاي جمعيت قبل عمليات انجام مي‌دهند.
3-7-1-3-1- عملگرهاي جهشي
عملگرهايي كه يك يا چند ژن از يك كروموزوم را انتخاب و مقادير آنها را تغيير مي‌دهند. در اين عملگرها يك يا چند محل از يك رشته كاراكتري با طول خاص در نظر گرفته شده و مقادير كاراكترها در آن محل‌ها تغيير مي‌يابد. مواردي كه در اين نوع مهم است عبارتند از:
تعداد محلهايي كه قرار است تغيير يابند،
نحوه انتخاب محل‌ها،
نحوه عمليات تغيير،
با مشخص شدن موارد فوق يك عملگر خاص ايجاد مي‌شود كه به آن عملگر جهشي گفته مي‌شود. در اين نوع عملگرها از اطلاعات يك جواب استفاده كرده و جواب ديگري ايجاد مي‌شود. اين تغيير ممكن است كم يا زياد بوده كه به همان ميزان از اطلاعات زياد يا كم استفاده مي‌شود. به عبارت ديگر هر چه تغييرات زيادتر باشد جواب حاصله تصادفي‌تر خواهد بود و اين تصادفي ‌بودن براي ورود مواد ژنتيكي جديد به داخل جمعيت مفيد مي‌باشد.
وقتي كه جمعيت به سمت جواب خاصي همگرا مي‌شود احتمال جهش بايد زياد شده تا از اين عمل جلوگيري نمايد و بالعكس وقتي جمعيت داراي جواب‌هاي غير يكسان است بايد احتمال جهش كم شود.
3-7-1-3-2- عملگرهاي تقاطعي
عملگرهايي كه يك يا چند نقطه از دو يا چند جواب را انتخاب و مقادير آنها را تعويض مي‌كنند. اين عملگرها يك جواب را در نظر گرفته و محل‌هايي از جواب را با جواب‌هاي ديگر معاوضه كرده و جواب‌هاي جديد را بوجود مي‌آورند. به اين نوع عملگرها، عملگرهاي تقاطعي گفته مي‌شود.
عملگر تقاطعي در يك لحظه بر روي دو كروموزوم اعمال شده و دو نوزاد بوسيله تركيب ساختار دو كروموزوم ايجاد مي‌گردد. يك مفهوم مهم كه در ارتباط با اين عملگر مطرح است نرخ تقاطعي مي‌باشد.
3-7-1-3-3- مکانيسم نمونه‌گيريمکانيسم نمونه‌گيري به چگونگي انتخاب کروموزوم‌ها از فضاي نمونه‌گيري مربوط مي‌شود و يکی از رويکردهای آن نمونه‌گيري تصادفي است:
دو نمونه‌گيري تصادفي که اکثرا از آن استفاده مي‌شود عبارتند از: انتخاب چرخ رولت و انتخاب کلي تصادفي. انتخاب چرخ رولت که اولين‌بار توسط هالند پيشنهاد شد يکي از مناسب‌ترين انتخاب‌هاي تصادفي بوده که ايده آن احتمال انتخاب مي‌باشد. احتمال انتخاب متناظر با هر کروموزوم، بر اساس برازندگي آن محاسبه مي‌شود بطوريکه اگر fk مقدار برازندگي کروموزوم kام باشد احتمال بقاي متناظر با آن کروموزوم عبارت است از:
pk=fk/i=0nfi,(3-8)
بطوریکه n اندازه جمعیت هر نسل میباشد. حال کروموزومها را بر اساس pkمرتب کرده و qkکه همان مقادير تجمعي pk مي‌باشد به صورت زير به دست مي‌آيد:
qk=j=0kpj.(3-9)
در روش انتخاب چرخ رولت به اين صورت عمل مي‌شود که براي انتخاب هر کروموزوم ابتدا يک عدد تصادفي بين يک و صفر توليد شده و سپس عدد مذکور در هر بازه‌اي که قرار گرفت کروموزوم متناظر با آن انتخاب مي‌شود. البته روش پياده کردن چرخ رولت به اين شکل است که يک دايره را در نظر گرفته و آن را به تعداد کروموزوم‌ها طوري تقسيم مي‌کنيم که هر بخش متناظر با مقدار برازندگي کروموزوم مربوطه باشد. حال چرخ را چرخانده و هر کجا که چرخ متوقف شد به شاخص چرخ نگاه کرده، کروموزوم مربوط به آن بخش انتخاب مي‌گردد.
3-7-1-4- تابع برازشهمانطور که ديده شد در فرآيند انتخاب بارها از عبارت کروموزوم مناسب‌تر صحبت به بيان مي‌آيد. بديهي است که براي تشخيص کروموزوم مناسب‌تر بايد يک شاخص جهت ارزيابي کروموزوم‌ها وجود داشته باشد.
در مورد مسايل بهينه‌سازي توابع، معمولا اين شاخص همان مقدار تابع هدف مساله مي‌باشد، يعني هر کروموزوم تبديل به جواب متناظر شده و در تابع هدف قرار مي‌گيرد، آنگاه مقدار تابع هدف براي هر جوابي که بهتر باشد کروموزوم متناظر با آن جواب مناسب‌تر خواهد بود. اما در مورد بعضي مسايل که پيچيده‌تر هستند بايد اقدام به تعريف تابع برازش نمود.
3-7-1-5- استراتژي برخورد با محدوديتهابحث ديگري كه در اجراي الگوريتم ژنتیک وجود دارد چگونگي برخورد با محدوديت‌هاي مساله مي‌باشد زيرا عملگرهاي ژنتیک مورد استفاده در الگوريتم باعث توليد كروموزوم‌هاي غيرموجه مي‌شود. چند تكنيك معمول جهت مواجهه با محدوديت،وجود دارد كه در ادامه به چند تا از آنها اشاره مي‌شود.
3-7-1-5- 1- استراتژي اصلاح عملگرها
يك روش براي جلوگيري از توليد كروموزوم غير موجه اين است كه عملگر ژنتيكي طوري تعريف گردد كه پس از عمل بر روي كروموزوم‌ها، كروموزوم توليد شده نيز موجه باشد. در اين حالت يكسري مشكلات وجود دارد. مثلا پيدا كردن عملگري كه داراي شرايط فوق باشد بسيار دشوار بوده و از مساله‌اي به مساله ديگر متفاوت مي‌باشد.
3-7-1-5- 2- استراتژي ردي
در اين روش پس از توليد هر كروموزوم آن را از نظر موجه‌بودن تست كرده و در صورت غيرموجه بودن حذف مي‌گردد. اين روش بسيار ساده و كارا مي‌باشد.
3-7-1-5- 3- استراتژي اصلاحي
در اين روش به جاي اينكه كروموزوم غيرموجه حذف گردد تبديل به يك كروموزوم موجه مي‌شود. اين روش نيز مانند روش اول به مساله وابسته بوده و يافتن فر‌آيند اصلاح گاهي بسيار پيچيده مي‌باشد.
3-7-1-5- 4- استراتژي جريمه‌اي
در اين روش بر خلاف سه روش قبل كه از ورود جواب‌هاي غير موجه جلوگيري مي‌كردند، جواب‌هاي غير موجه با احتمال كم امكان حضور مي‌يابند. سه روش فوق داراي اين اشکال بودند كه به هيچ نقطه‌اي بيرون از فضاي موجه توجه نمي‌كردند، اما در بعضي مسايل بهينه‌سازي جواب‌هاي غير موجه درصد زيادي از جمعيت را اشغال مي‌كنند. در چنين شرايطي اگر جستجو فقط در ناحيه موجه انجام گيرد شايد يافتن جواب موجه خيلي وقت‌گير و مشكل باشد.استراتژي جريمه‌اي از متداولترين تكنيك‌هاي مورد استفاده براي پذيرش با جواب‌هاي غيرموجه مي‌باشد كه در آن ابتدا محدوديت‌هاي مساله در نظر گرفته نمي‌شوند،سپس‌ براي هر تخلف از محدوديت‌ها، يك جريمه اختصاص داده مي‌شود كه اين جريمه در تابع هدف قرار مي‌گيرد.
3-7-2- ساختار كلي الگوريتم ژنتیکساختار كلي يك الگوريتم ژنتیک را مي‌توان به صورت ذيل تصور كرد.
ابتدا پيش از هر چيز بايد مكانيسمي براي تبديل هر جواب مساله به يك كروموزوم تعريف كرد. پس از آن يك مجموعه از كروموزوم‌ها كه در حقيقت مجموعه‌اي از جواب‌هاي مساله هستند به عنوان يك جمعيت آغازين تهيه مي‌گردند. اين مجموعه كه اندازه آن دلخواه است و توسط كاربر تعريف مي‌شود، اغلب به صورت تصادفي ايجاد مي‌گردد.
بعد از اين مرحله بايد با بكارگيري عمليات ژنتيك اقدام به ايجاد كروموزوم‌هاي جديد موسوم به نوزاد نمود. اين عمليات به دو گونه عمده تقاطعي و جهشي تقسيم‌بندي مي‌شوند. همچنين براي گزينش كروموزوم‌هايي كه بايد نقش والدين را بازي كنند دو مفهوم نرخ تقاطعي و نرخجهشي كاربرد فراوان دارند كه اين دو نيز پيش از شروع الگوريتم توسط كاربر تعيين مي‌شوند.
بعد از توليد يكسري كروموزوم جديد يا اولاد بايد با استفاده از عمل تحول اقدام به انتخاب برازنده‌ترين كروموزوم‌ها نمود. اين فرآيندكه در فرآيند انتخاب نمود مي‌يابد، گلچين‌كردن كروموزوم‌هاي برازنده در ميان والدين و اولاد است، به طوريكه تعداد كروموزوم‌هاي منتخب برابر با اندازه جمعيت اوليه باشد. فرآيند انتخاب مبتني بر مقدار برازندگي هر رشته است. در حقيقت فرآيند ارزيابي محوري‌ترين بحث در فرآيند انتخاب است.
تا بدين مرحله يك تكرار يا يك نسل از الگوريتم طي شده است. الگوريتم بعد از طي چندين نسل به تدريج به سمت جواب بهينه همگرا مي‌شود. شرط توقف مساله نيز طي‌كردن تعداد معيني تكرار است كه پيش از آغاز الگوريتم توسط كاربر تعيين مي‌شود.
ساختار كلي يك الگوريتم ژنتیک را مي‌توان به صورت ذيل بيان كرد
روند الگوریتم ژنتیک.
Step 1: Set t:=0
Step 2: Generate initial population, p(t).
Step 3: Evaluate p(t) to create fitness values
Step 4: While (not termination condition) do:
Recombine p(t) to yield c(t), selecting from p(t) according to the fitness values.
Evaluate c(t)
Generate p(t+1) from p(t) and c(t)
Set t:=t+1
End.
Step 5: Stop.

فصـل چهارم: ارائه مـدل ریاضی

4-1- مقدمهمعمولاًبرای سادهسازی و نمادگذاری، از طبقهبندی Pos1/Pos2/Pos3/Pos4/Pos5 در مسایل مکانیابی همانگونه که هاماخر[5]و، هاماخر و نیکل[63]، معرفی کردهاند، استفاده میشود. در این طرح طبقهبندی،Pos1، تعداد (یا شکل) تسهیلات جدید را مشخص میسازد. در حالتیکه میخواهیمبرایN≥1، مکان نقاط جدید (X1, …, XN∈Rn)، را بیابیم، این مکان، شامل عدد صحیح مثبت، می‌باشد. درPos2 ، فضای تصمیم مساله مکانیابی را نشان میدهیم، یعنی،Rn برای مسایلn-بعدی پیوسته، یا P (یاR2) برای مسایل بروی سطح. علاوه بر این، برای شناسایی مسایل مکانیابی شبکه در این مکان از نماد G، استفاده میشود. در این مدل طبقهبندیPos3 ، برای اختصاص ویژگیهای خاص از یک مسله مکانیابی مفروض میباشد. برای نمونه این مکان، میتواند برای تاکید بروی نواحی ممنوعه در که استقرار تسهیلات جدید در این نواحی ممنوع است، باشد که توسط نماد R ، نشان داده میشود، و همچنینبرای نواحی با مانع که علاوه بر استقرار تسهیل جدید، حرکت نیز در این نواحی ممنوع میباشد با نماد Bنمایش میدهیم. در مدلهای پیوسته،Pos4، شامل اطلاعاتی راجع به تابع فاصله میباشد، برای مثال l2 نشان دهنده فاصله اقلیدسی، l1 نشان دهنده فاصله منهتن(متعامد یا پلهای)، و یا dB نشان دهندهی حالتی است که تابع فاصله با مانع توسط یک معیار مفروضd ، محاسبه شود، میباشد. برای مسایل مکانیابی شبکه،این Posبرای مشخص کردن، فواصل در شبکه میباشد، خواه فواصلِ فقط مابین گره های شبکه(dG(V, V)) باشد،و خواه، محاسبه فاصله ما بین هر نقطه در گراف(dG(V,E)) باشد، مورد استفاده قرار میگیرد. در این طبقهبندیPos5 ، نشان دهنده تابع هدف مساله میباشد. برای نمونه، اگر یک مسئله وبر یا میانه مدنظر باشد، از نماد ∑ در این Pos استفاده میشود. مسایل مرکز با نماد max، مسایل وبر ترتیبی توسط ord∑ نشان داده میشوند. همچنین تابع هدف محدب کلی با نماد،f convex، نشان داده میشود. اگر فرض خاصی در هر کدام از این مکانها مدنظر قرار نگیرد، آنگاه این مکان را با نماد یک گلوله ( “•”)، نشان میدهند.
خلاصه مبحث فوق این است که، مسایلوِبِر، مرکز، میانه با نواحی چند وجهی ممنوعه، و مساله وبر در سطح با فواصل اقلیدسی همراه با یک مانع دایرهای بترتیب با نماد، 1/Rn/∙/d/∑،1/Rn/∙/d/max،1/P/(R=Npolyhedra)/d/∑ و 1/P/(B=1 circle)/d/∑دستهبندی و طبقهبندی میشوند. همچنین برای مسایل مکانیابی شبکه و مسایل مکانیابی شبکه گرهای نیز بترتیب بصورت 1/G/∙/dG(V,E)/fو 1/G/∙/dG(V,V)/fطبقه بندی میشوند. پس بدین ترتیب، این تحقیق طبق این دستهبندی از نوع N/R2/B=1 -Line/d1/∑ میباشد.
4-2- ساختار مسالهفرض کنید{B1, …, BN}، یک مجموعه متناهی از موانع بسته و دو به دو نامتصل بهم درRn باشند و نیز فرض کنید B=⋃i=1NBi باشد. استقرار یک تسهیل جدید و حرکت در درون این نواحی (یعنی،int(B))، ممنوع میباشد. بنابراین ناحیه شدنیF⊆R2، برای استقرار تسهیلات جدید و حرکت، این چنین نمایش داده میشود:
F =R2\intB.در نظریه مکانیابی، یک مجموعه تسهیل (یا وسیله) موجود متناهی Ex={ Xi∈R2: i=1,…,I}، وجود دارند. همچنین فرض بر این است که تمام تسهیلات موجود در ناحیه شدنی قرار گرفته باشند، یعنی برای تمامی i∈F داریم Xi∈F. قبل از اینکه برروی ساختار مساله بحث کنیم، اجازه بدهید مفهوم تابع فاصله dpB، که فاصله با مانع با نرم p نامیده میشود، را تشریح کنیم. دو نقطه دلخواه X2,X1 را در صفحه در نظر بگیرید، بطوری که X2,X1∈F ، بنابرین ما فاصله با مانع با نُرم p را این چنین تعریف میکنیم:
dpBX1,X2= infdP: P feasible X1-X2 path,بقسمی که، P یک مسیر شدنی مابین دو نقطه دلخواه بوده و dP طول این مسیر شدنی میباشد. دو نقطه دلخواهX1,X2∈F ، p-visible نامیده میشوند، اگر فاصله بامانع با نرم p مابین دو نقطه برابر فاصله بدون مانع با نرم p این دو نقطه باشد، یعنی dpB(X1,X2)=dp(X1,X2). بعبارت دیگر حضور مانع تاثیری بر پدیداری دو نقطه X1,X2 نگذاشته است. بنابراین مجوعه نقاطی که نسبت به نقطه X1∈F پدیدار هستند، این چنین تعریف میشوند:
visibleX1=X2∈F:dpBX1,X2=dpX1,X2. بطور مشابه، مجموعه نقاط X2∈F که نسبت به نقطه X1∈F پدیدار نیستند، را سایهیX1 مینامیم، یعنی:
shadowX1=X2∈F:dpBX1,X2>dpX1,X2.اگر نقاط نسبت به یکدیگر p-shadow باشند، آنگاه فاصله مابین آنها یک فاصله با مانع با نرم p میشود که در کل یک تابع غیر محدب میباشد. برای کسب اطلاعات بیشتر بر روی مفهوم پدیداری، به کلامروس [4] مراجعه نمایید.
فرض کنید I تسهیل موجود بصورت نقطهای در صفحه داریم، بنابراین مساله مکانیابی میانه چند تسهیلاتی متعامد با مانع بصورت زیر فرموله میشود:
mini=1Ij=1Jwij.d1LB (Xj, Xi)+j=1Jk=1j<kKvjk.d1LB (Xj, Xk),(4-1)
بقسمی که، wij وزن یا میزان تواتربین تسهیل جدید j و تسهیل موجود i بوده وvjk وزن یا میزان تواتربین تسهیل جدید j و تسهیل جدید k می‌باشد. همچنین d1LB (Xj, Xi) فاصله متعامد با مانع بین تسهیل جدید j، (Xj = (xj,yj) QUOTE X=x,y, j =1,…,J) و تسهیل موجود i، (Xi = (ai,bi) QUOTE X=x,y,i =1,…,I) QUOTE X=x,yوd1LBXj, Xk فاصله متعامد با مانع بین تسهیل جدید j وk می‌باشد. همچنین، ما فرض میکنیم که یک مانع خطی دارای مختصه ثابت y=b در یک مسیر افقی وجود دارد که عبور از روی این مانع خطی تنها از طریق تعدادی گذرگاه با مختصات های Pp=xpp,ypp,p =1,…,P امکان پذیر می باشد.اما ظرفیت این گذرگاه ها جهت عبور از داخل آنها محدود می باشد. همچنین فرض بر این است که از عرض مانع صرفنظر میشود. شکل (4-1) این مساله را نشان میدهد.

شکل (4- SEQ شکل_(4- \* ARABIC1). تسهیلات موجود و یک مانع خطی با دو گذرگاه.محاسبه فاصله متعامد یک تسهیل جدید و موجود با یکدیگر یا دو تسهیل جدید نسبت به هم بستگی به موقعیت دو تسهیل نسبت به هم و نسبت به مانع خطی دارد. یعنی اگر تسهیل جدید X1 و تسهیل موجود یا جدید X2 در نیم صفحه یکسانی قرار بگیرند این دوتسهیل نسبت به هم پدیدار می باشند و فاصله بین این دو تسهیل یک فاصله متعامد بدون مانع خواهد بود یعنی: d1LB(X1,X2)=d1(X1,X2). اما اگر تسهیل جدید X1 و تسهیل موجود یا جدید X2 در نیم صفحه متفاوت قرار بگیرند این دوتسهیل نسبت به هم سایه می باشند و فاصله بین این دو تسهیل یک فاصله متعامد با مانع خواهد بود ( d1LB(X1,X2)) که در این شرایط جهت ایجاد تعامل بین این دو تسهیل می بایستی از یکی از گذرگاه ها جهت عبور استفاده نمود
4-2-1-محاسبه فاصلهمطالب آتی به ما کمک میکند تا درک بهتری راجع به تابع توزیع فاصله با مانع داشته باشیم.با توجه به اینکه تابع هدف مسئله به دنبال کمینه کردن مجموع فواصل وزن دهی شده می باشد، تعیین کوتاهترین مسیر برای ایجاد تعامل بین این دو تسهیل نقش حیاتی خواهد داشت. با توجه به پارامترهای تعریف شده می توان کوتاهترین فاصله بین دو تسهیل (نقطه) را بسته به موقعیتی که در صفحه دارند بصورت زیر فرموله کرد:
(4-2) d1LBXi,Xj=d1Xi,XjXi∈Fm, Xj∈Fmminpd1Xi,Pp+d1Pp,XjXi∈Fm, Xj∈Fm’m≠m’,, i=1,…,I;j=1,…,J;m=1,2در رابطه فوق عبارت اول به این معناست که اگر هر دو تسهیل Xi و Xj در نیم صفحه یکسان قرار بگیرند (شکل (a) 4-2)فاصله بین این دو تسهیل یک فاصله متعامد بدون مانع خواهدبود و عیارت دوم بیانگر آنست که اگر دو تسهیل در نیم صفحه های متفاوت نسبت به هم قرار بگیرند(شکل (b) 4-2)فاصله بین این دو تسهیل یک فاصله متعامد با مانع خواهدبود که در این شرایط بایستی کوتاهترین مسیر مجاز بین دو تسهیل از طریق گذرگاه های مختلف در نظر گرفته شود.
16573504197350062865072453500
(b)1-Shadow (a) 1-Visible
217995558420شکل (4- SEQ شکل_(4- \* ARABIC2). شرایط پدیداری.00شکل (4- SEQ شکل_(4- \* ARABIC2). شرایط پدیداری.
با توجه به اینکه تابع فاصله مورد استفاده در این تحقیق از نوع متعامد می باشد می توان رابطه فوق را بصورت زیر بیان نمود:
(4-3) d1LBXi,Xj=ai-xj+bi-yjXi∈Fm, Xj∈Fmminkai-xpp+bi-ypp+xpp-xjh+ypp-yjhXi∈Fm, Xj∈Fm’m≠m’,, i=1,…,I;j=1,…,J;m=1,2با توجه به اینکه در مساله مکانیابی چند تسهیله علاوه بر تعامل تسهیلات موجود و جدید با یکدیگر تسهیلات جدید نیز با یکدیگر تعامل دارند بنابراین رابطه فوق برای تسهیلات جدید Xj و Xkنیز بصورت زیر برقرار می باشد:
(4-4) d1LBXj,Xk=xj-xk+yj-ykXj∈Fm, Xk∈Fmminkxj-xpp+yj-ypp+xpp-xk+ypp-ykXj∈Fm, Xk∈Fm’m≠m’,, j=1,…,J;k=1,…,K;m=1,2لازم به ذکر استکه چنانچه در شکل (4-2) مکان دو نقطه Xj وXi با یکدیگر عوض شوند، کلیه محاسبات مشابه با حالت قبل خواهد بود.
4-2-2- مکانیابی چند تسهیله چند دوره ایدر این تحقیق ما به دنبال یافتن مکان بهینه تسهیلات جدید از میان تسهیلات موجود در دوره های زمانی مختلف می باشیم. یعنی مساله ای که با آن سروکار داریم یک مساله مکانیابی چند تسهیله چند دوره ای می باشد. بنابراین با تعریف متغیر , h =1,…,HXjh = (xjh,yjh) QUOTE X=x,y, j =1,…,J مکان تسهیلات جدید در دوره های مختلف را نمایش می دهیم. اما لازم به ذکر است که مکان تسهیلات موجود در دوره های مختلف ثابت باقی می ماند.
چنانچه در قسمت قبل اشاره شد، ظرفیت گذرگاه ها محدود می باشد. اکنون با توجه به چند دوره ای بودن مساله، ظرفیت گذرگاه ها را در دوره های مختلف نیز محدود و متفاوت در نظر می گیریم.همچنین فرض بر آنست که علاوه بر ظرفیت گذرگاه ها، مقادیر اوزان تسهیلات جدید با یکدیگر و با تسهیلات موجود در دوره های مختلف متفاوت می باشد (Vjkhو Wijh).
همچنین برای نشان دادن وابستگی یک تسهیل جدید به مکان آن در دو دوره متوالی، هزینه ای تحت عنوان هزینه جابجایی بایستی به سیستم تحمیل گردد. یعنی وقتی یک تسهیلی در یک دوره ای در یک مکان مانند A مستقر شده باشد و در دوره بعد در مکان دیگری مانند B مستقر گردد به ازای این تغییر مکانی که در این تسهیل ایجاد گردیده یک هزینه جابجایی به سیستم تحمیل می گردد که این هزینه را نیز باید در تابه هدف مساله لحاظ نمود ( در قسمت بعد این هزینه را در تابع هدف خواهید دید).
4-2-3- مدل ریاضی پیشنهادیدر این بخش ما می‌خواهیم یک مدل ریاضی برای مسئله مکان‌یابی چند تسهیله چند دوره ای در حضور یک مانع خطی با تعدای گذرگاه با ظرفیت های محدود ارائه دهیم. به این منظور ما صفحه را به دو نیمصفحه تقسیم میکنیم بطوریکه، یک نیم صفحه در زیر مسیر مانع و دیگری در ناحیه بالایی مسیر مانع خطی باشد و فرض می‌کنیم تعدادی از تسهیلات موجود در نیم صفحه پایینی و تعدادی دیگر در نیم صفحه بالایی قرار دارند (شکل 4-3 را مشاهده کنید).

شکل (4- SEQ شکل_(4- \* ARABIC3). تقسیم فضای مساله به دو نیم صفحه.حال با توجه به این تقسیم سازی، پارامتر ها و متغیرهای پیوسته و باینری مساله را بصورت زیر تعریف می‌کنیم:
پارامترها:
وزن یا میزان تواتربین تسهیل جدید j و تسهیل موجود i در دوره h-ام Wijh=وزن یا میزان تواتربین تسهیل جدید j و تسهیل جدید k در دوره h-ام Vjkh=
ظرفیت گذرگاه p-ام در دوره h-ام Cph=
هزینه متغیر جابجایی در شروع دوره h-ام Varh=
مختصات تسهیل موجود i-ام Xi=( ai, bi)مختصات گذرگاه p-ام Xp=(xpp,ypp)(4-5) ∀iqi=1 , اگر bi>b 0 , درغیراینصورتمتغیرها:
مختصات تسهیل جدید j-ام در دوره h-ام Xjh=(xjh,yjh)gjh=1 , اگر yjh>b 0 , درغیراینصورت∀j(4-6)
tijh= 1 , قراربگیرندمتفاوتصفحهدرنیمام- h دردوره j جدیدتسهیلو i موجود اگرتسهیل0 , درغیراینصورت∀i, j,h (4-7)
t’jkh=1 , قراربگیرندمتفاوتصفحهدرنیمام- h دردوره k و j جدیداگرتسهیلات0 , درغیراینصورت∀j,k,h j<k(4-8)
t”jkh=1 , قراربگیردمتفاوتصفحهدرنیم h-1 بهنسبت h دردوره j جدیداگرتسهیل0 , درغیراینصورت∀j, k, j=k∀h>1(4-9)
uijph= 1 , باشدداشتهتعامل i موجودتسهیلبا p گذرگاهطریقاز j جدید تسهیلام- h دردورهاگر0 , درغیراینصورت∀i, j, p, h (4-10)
u’jkph= 1 , باشدداشتهتعامل k جدیدتسهیلبا p گذرگاهطریقاز j جدید تسهیلام- h دردورهاگر0 , درغیراینصورت∀j,k,p, h j<k(4-11)
u”jkph= 1 , پذیردصورت p گذرگاهازطریق h-1 بهنسبت h دردوره j جدیدتسهیلتغییرموقعیتاگر0 , درغیراینصورت∀j,k,p, j=k, ∀h>1(4-12)
اکنون با استفاده از این متغیرهای تصمیم‌گیری و عبارت‌های (4-3) و(4-4) که برای محاسبه فاصله با مانع ارائه داده شده‌اند، ما مدل ریاضی غیر خطی زیر را برای مسئله مکان‌یابی چند تسهیله چند دوره ای در حضور یک مانع خطی با P گذرگاه ارائه می‌دهیم:
Min hijWijhpai-xpp+bi-ypp+xpp-xjh+ypp-yjh.uijph.tijh+ai-xjh+bi-yjh.(1-tijh)+jkj<kVjkhpxjh-xpp+yjh-ypp+xpp-xkh+ypp-ykh.u’jkph.t’jkh+xjh-xkh+yjh-ykh.(1-t’jkh)+hh>1jkj=kVarhpxjh-1-xpp+yjh-1-ypp+xpp-xjh+ypp-yjh.u”jkph.t”jkh+xjh-1-xjh+yjh-1-yjh.(1-t”jkh)(4-13) ∀i2.bi.qi-2.qi.b≥bi-b(4-14) ∀j,h2.yjh.gjh-2.gjh.b≥yjh-b(4-15) ∀i,j,hqi-gjh=tijh(4-16) ∀j,k, h j<kgjh-gkh=t’jkh(4-17) ∀j, k, j=k,∀h>1gjh-gkh-1=t”jkh(4-18) ∀i,j,hpuijph=tijh(4-19) ∀j,k, h, j<kpu’jkph=t’jkh(4-20) ∀j, k, j=k,∀h>1pu”jkph=t”jkh(4-21) ∀p, hijuijph+jkj<ku’jkph≤Cph(4-22) ∀i,j,k,p, h, j<k qi, gjh,tijh,t’jkh,uijph,u’jkphϵ0,1(4-23) ∀j,k,p, j=k,∀h>1 t”jkh,u”jkphϵ0,1(4-24) ∀j,k, h, j<kxjh, xkh, yjh, ykh≥0 ,قسمت اول تابع هدف فوق، مجموع فواصل مانع متعامد وزن دهی شده از هر تسهیل جدید تا تسهیلات موجود را محاسبه می‌کند که در آن اگر متغیر tijhدر یک دوره hمقدار یک بگیرد، نشان دهنده آنست کهاین دو تسهیل در نیم صفحه های متفاوت قرار دارند و از این رو حضور مانع در محاسبه فاصله متعامد بین تسهیل جدید j و تسهیلات موجود i موثر خواهد بود.در چنین شرایطی مدل ملزم به انتخاب یک گذرگاه بطوریکه کوتاهترین مسیر را منجر شود، می باشد که این تصمیم گیری با استفاده از متغیر باینری uijph در تابع هدف انجام می گیرد. اما اگر متغیر tijhدر دوره ای مقدار صفر بگیرد، نشان دهنده آنست



قیمت: 10000 تومان

متن کامل در سایت homatez.com

About: admin


دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *