— (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

NameEmailWebsite

پاسخ دهید

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