این تحقیق مساله مکان یابی چند تسهیله چند دوره ای با فواصل متعامد در حضور یک مانع خطی با تعدادی گذرگاه با ظرفیت های محدودرا در نظر میگیرد.هدف یافتن مکان تسهیلات جدید در میان تسهیلات موجود در دوره های مختلف می باشد بگونه ای که مجموع کل فواصل با مانع وزن دهی شده تسیهلات جدید با تسهیلات جدید و موجود حداقل شوند. برای این منظور یک مدل برنامهریزی غیر خطی ارائه شده است.همچنین یک تعداد از ویژگیهای مساله مورد بررسی قرار گرفته و در ادامه برای درک مسئله مذکور یک مثال ارائه شده است.نتایج محاسباتی این تحقیق، نشان میدهد که مساله توسط نرمافزار LINGO در اندازههای کوچک در زمان معقول به حل بهینه دست پیدا نمیکند. بهمنظور نشان دادن کارایی مساله در مقیاسهای بزرگ، یک الگوریتم فرا ابتکاری (الگوریتم ژنتیک) پیشنهاد شده است.کلمات کلیدی:مکان یابی چند تسهیله چند دوره ای؛ مانع خطی؛ گذرگاه های با ظرفیت محدود؛ فاصله متعامدIn 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.تشكروقدردانیدچکیدهوAbstractزفهرست مطالبحفهرست جداولكفهرست شکلها‌ل1-1- مقدمه21-2-ساختارپایان نامه42-1- مقدمه62-2-مسایل مکانیابی همراه باموانع82-3- مسایل مکانیابی چندتسهیله132-4- مسایل مکانیابی چنددوره ای153-1- مقدمه183-2- فواصل درمسایل برنامه ريزي تسهيلات193-2-1- فاصله خط مستقيم يااقليدسي193-2-2- فاصله مجذورخط مستقيم يااقليدسي203-2-3- فاصله منهتن یامتعامد203-2-4- فاصله چبيشف213-2-5- كوتاه‌ترين مسير223-3- دسته‌بندي كلي مسایل برنامه‌ريزي تسهيلات223-4- دسته بندي مسایل مكانيابي بانگرش سنتی233-5- دسته‌بندي مسایل مكانيابي بانگرش نوين253-6- مسایل مکانیابی میانه باانواع فاصله263-7- تشریح الگوریتم ژنتیک293-7-1- مفاهيم کليدي الگوريتم ژنتیک303-7-1-1- كدينگ303-7-1-2- ايجادجمعيت اوليه313-7-1-3- عملگرهای الگوریتم ژنتیک313-7-1-4- تابع برازش343-7-1-5- استراتژي برخوردبامحدوديتها343-7-2- ساختاركلي الگوريتم ژنتیک364-1- مقدمه394-2- ساختارمساله404-2-1- محاسبه فاصله434-2-2- مکانیابی چندتسهیله چنددوره ای454-2-3- مدل ریاضی پیشنهادی464-2-3-1- مثال534-3- الگوریتم ژنتیک574-3-1- نمايش كروموزوم574-3-2- آغازسازی584-3-3- ارزيابي594-3-4- معیارتوقف594-3-5- نخبه گرایی604-3-6- عملگرتقاطع604-3-6-1- عملگرتقاطع نوعI604-3-6-2- عملگرتقاطع نوعII624-3-7- عملگرجهش644-3-8- انتخاب654-5-1- مسایل نمونه675-1- نتیجه گیری765-2- پیشنهادات آتی77مراجع فارسی79مراجع لاتین80 فهرست جداولفصـل دوم:فصـل سـوم:جدول (3- 1). توابع فاصله بکارگرفته شده درمسایل مکانیابی [3].28فصـل چهارم:جدول (4- 1). اطلاعات تسهیلات موجود.53جدول (4- 2). وزن بین تسهیلات جدید53جدول (4- 3). اوزان مابین تسهیلات موجودوجدید.54جدول (4- 4). مختصات گذرگاهها54جدول (4- 5). ظرفیت گذرگاهها54جدول (4- 6). مختصات مکانهای بهینه تسهیلات جدیددرمثال نمونه.55جدول (4- 7). مقادیرپارامترهای الگوریتم ژنتیک.67جدول (4- 8). نتایج محاسباتی برای اندازه کوچک.69جدول (4- 9). نتایج محاسباتی برای اندازه بزرگ.71 فهرست شکلهافصـل سـوم:شکل (3- 1). فاصله اقلیدسی درصفحه20شکل (3- 2). مسیرهای مختلف متعامدبینو21شکل (3- 3). دسته بندی کلی مسائل برنامه ریزی تسهیلات [1].23شکل (3- 4). دسته بندی نوین مسائل مکانیابی [1].25فصـل چهـارم:شکل (4- 1). تسهیلات موجودویک مانع خطی بادوگذرگاه.43شکل (4- 2). شرایط پدیداری.44شکل (4- 3). تقسیم فضای مساله به دونیم صفحه.47شکل (4- 4). مکان تسهیلات موجودوتسهیلات جدیددر 2 دوره.56شکل (4- 5). فلوچارت الگوریتم ژنتیک66شکل (4- 6).مقدارgapالگوریتم ژنتیک دراندازه های متفاوت72شکل (4- 7). نمودارمقایسه زمان محاسباتیLingo والگوریم ژنتیک دراندازه های متفاوت.74 فصـل اول:کلیات تحقیق و ساختار پایاننامهيكي از مسایلي كه بايد در مراحل اوليه طراحي سيستم‌هاي صنعتي مورد توجه قرار گيرد مسالة مكانيابي[1] (جایابی) واستقرار تسهيلات است. مطالعه پيرامون مكان بهينه از ديدگاه جغرافيدانان و علماي علم اقتصادي همواره داراي اهميت و اولويت بوده است [1].در ادبيات موضوعي، معمولاً چند حالت از مسایل مكانيابي پيوسته، مورد بحث قرار گرفتند، مانند مساله ميانه[2]، مساله مركز[3] و مساله مركز-ميانه[4]. در مساله میانه هدف، پیدا کردن مکان وسیله (تسهیل) جدید میباشد، بطوریکه مجموع فواصل وزندهی شده بین تسهیل جدید و تسهیلات موجود، حداقل گردد. این مساله، در تئوری مکانیابی به مساله وِبِر[5] و مساله کمینه مجموع[6] نیز شهرت دارد. مسایل مکانیابی بر اساس نوع تابع فاصله نیز تقسیمبندی میشوند، مانند فاصله اقلیدسی و متعامد. مساله میانه با فواصل اقلیدسی یکی از قدیمی ترین مسایل مکانیابی تسهیلات میباشد. برای حل بهینه این نوع مساله، روشهای حل مختلفی پیشنهاد شدهاست که مشهورترین آن روش تکراریی میباشد، که توسط ویزفلد [2] توسعه داده شد.در گونهاي از مسایل میانه با محدوديت در قرار گيري[7] و يا حركت[8]مواجه هستيم.در دستهای از این نوع مسایل، نواحی وجود دارند كه تسهيل (یا تسهیلات) جديد نه مي‌تواند در آنجا استقرار يابد و نه مي‌تواند از ميان آن عبور كند. این نواحي، نواحي بامانع[9] ناميده مي‌شوند.درياچه‌ها، كوهستانها، مناطق نظامي، رودخانه‌ها و بزرگراهها ودر مقياس كوچكتر، ماشینآلات و واگنهای حمل مواد در كارخانجات، مثالهايي از اين نواحي مي‌باشند.این مسایل در مقایسه با مسایل مكانيابي كلاسيك خيلي عمليتر ونزديك‌تر به دنياي واقعي مي‌باشند، اما بهعلت پيچيدگي محاسباتي که اين نوع مسایل دارند، تنها در چند دهه اخير مورد بررسی قرار گرفتند. در برخی موارد با موانعی مواجه هستیم که عبور از آنها تنها از طریق چند گذرگاه[10]بر روی مانع خطیامکان پذیر می باشد. مدل پیشنهادی این تحقیق، یک مساله میانه با فواصل متعامد میباشد، بطوریکه در ناحیه پیوسته یک مانع خطی افقی وجود دارد که بر روی آن تعدادی گذرگاه وجود دارد که ظرفیت هر یک از گذرگاه ها محدود می باشد. فرضیات مساله پیشنهادی بقرار زیر در نظر گرفته میشوند:در ادامه در فصل 2، ادبیات موضوعی مسایل بامانع ومسایلمکان‌یابی چند تسهیله[11] را مورد بررسی قرار خواهیم داد. در فصل 3 زمینههای علمی تحقیق شامل دستهبندی مسایل مکانیابی، انواع توابع فاصله، مساله مکانیابی کلاسیک و الگوریتم ژنتیک بطور مفصل تشریح خواهند شد. در فصل 4 به تشریح مساله و مدل پیشنهادی می پردازیم. در ادامه این فصل به منظور درک بهتر رفتار مدل، یک مثال نمونهای ارائه خواهیم داد، اما با توجه به پیچیدگیهای مدل پیشنهادی در مقیاس های بزرگ، الگوریتم فراابتکاریژنتیکرا معرفی و نتایج محاسبات مربوط به این الگوریتم را مورد بررسی قرار خواهیم داد. در نهایت، تعدادی از توسعههای آتی بههمراه نتیجهگیری در فصل 5 مورد بررسی قرار گرفتند. فصـل دوم:مروری بر ادبیّات موضوعی مسایل مکانیابی بامانع 2-1- مقدمهمسایل مكانيابي تک وسیلهای (تک تسهیله) پيوسته در سطح[12]، يكي از حوزه‌هاي گسترده در مدل سازي رياضي، در دنياي واقعي مي‌باشند، كه دراین مسایل يك تسهيل جديد (تسهیل عرضه) به مجموعهاي از تسهيلات موجود ( تسهیلات متقاضی)، با توجه به تقاضاهايشان، سرويس میدهد.در ادبيات موضوعي، معمولاً چند حالت از مسایل مكانيابي پيوسته، مورد بحث قرار میگیرد، مانند مساله ميانه، مساله مركز و مساله مركز-ميانه.در مساله میانه كلاسيك( که غالبا مساله وبِر، مساله فرمارت اشنایدر وبر[13] و مساله حداقل مجموع[14]نیزنامیده ميشود)، در صدد یافتن مكان تسهيل جديد هستيم، بطوريكه مجموعه فواصل وزن دهي شده[15] با تسهيلات موجود، حداقل گردد.براي اطلاعات بیشتر در اين زمينه به فراهانی و حکمتفر [3] و کلامروس [4] مراجعه كنيد.در گونهاي از مسایل میانه، با محدوديت در قرارگيري و يا حركت مواجه هستيم.در ادبيات موضوعي اين نوع مسایل، معمولاً سه دسته از اين مسا یل مورد مطالعه قرار گرفتهاند.اولين دسته، نواحي ممنوعه[16] نامیده می شوند كه در این نواحی تسهيلاتنمي‌توانند درآنجا قرار گيرند اما حركت در ميان اين نواحي بلامانع و بدون جريمه مي‌باشد(مانند مناطق و پاركهاي حفاظت شده و یا مناطقی که مشخصههای جغرافیای از قبیل شیب تند زمین از ایجاد تسهیل مورد نظر ممانعت میکند).براي مطالعه بروي مسایل مكانيابي میانه و مرکز درنواحی ممنوعه به هاماخر و نیکل [5]مراجعه كنيد.دسته دوم به عنواننواحي متراکم[17]شناخته میشوند كه در اين نواحي قرارگيري يك تسهيل ممنوع بوده اما حركت از ميان آن با جريمه [18] همراه مي‌باشد(مانند درياچه‌اي كه، با قايق بتوان از دو طرف آن عبور و مرور كرد. برای نمونه، مسایل مکانیابی با نواحی متراکم، با سرعت و هزینههای سفر مختلف، در بوت [6] و بوت و کاوالیر [7] مورد بحث و بررسی قرار گرفتهاند.دسته سوم نواحی هستند كه تسهيل جديد نه مي‌تواند در آنجا استقرار يابد و نه مي‌تواند از ميان آن عبور كند. این نواحي، نواحي با مانع ناميده مي‌شوند.درياچه‌ها، كوهستانها، مناطق نظامي، رودخانه‌ها و بزرگراهها ودر مقياس كوچكتر، نوار نقاله‌ها،ماشینآلات موجود در كارخانجات، مثالهايي از اين نواحي مي‌باشند. 2-2- مسایل مکانیابی همراه با موانع[19]اگر چه مسایل مكانيابي با مانع، در مقایسه با مسایل مكانيابي كلاسيك خيلي عمليتر ونزديك‌تر به دنياي واقعي مي‌باشند اما به علت پيچيدگي محاسباتي که اين نوع مسایل دارند، تنها در چند دهه اخير، وارد ادبيات موضوعيشده‌اند.مدلسازي مكانيابي بانواحي با مانع، براي اولين بار توسط کاتز و کوپر [8] معرفي شد. نويسندگان يك مساله وبر صفحهای[20] را با فواصل اقليدسي و يك مانع دايره‌اي در نظر گرفتند.همچنين آنها، نشان دادند كه چنين مسایلی دارای تابع هدف غيرمحدب هستند و در ادامه براي حل آن يك روش ابتکاری مبتني بر تکنیک کمینه سازی متوالی بدون محدودیت[21] (SUMT) پيشنهاد دادند.بعداًکلامروس [9]، برخي فواصل جبري اين مساله را بررسي كرد. نویسنده، ناحيه شدني را به يك تعداد سلولهاي محدب با تابع هدف محدب تجزيه كرد. اگرN، تعداد تسهيلات موجود باشد، تعداد این سلولهاي محدب تابع دوجملهای ( یعنی، برابر O(N2))میباشد. با توجه به اينكه با افزايشN، ساخت اين سلولهاي محدب سنگين و پر مشقت ميشود، بایشوف و کلامروس [10]،با پيشنهاد يك روشحل مبتني بر الگوريتم ژنتيك GA)) ، براين مشكل فائق گشتند. در ادامه بایشوف و همکاران [11] از متد فوق برای مساله مکانیابی- تخصیص تسهیلات[22] در حضور موانع چندوجهی و فاصله اقلیدسی استفاده کردند. نویسندگان دو روش ابتکاری که هر کدام از روشها از دو حل ابتدای استفاده میکرد را معرفی کردند، سپس بر اساس نتیجه محاسباتی، به بررسی روشهای ابتکاری معرفی شده پرداختند.