منابع پایان نامه ارشد با موضوع مکانیابی، مکان‌یابی، سلسله مراتبی

دانلود پایان نامه ارشد

قرارمی‌دهیم، درغیر اینصورت . همچنین را مجموعه همه جایگاه‌های کاندیدشده‌ای قرار می‌دهیم که می‌توانند گره تقاضای i را پوشش دهند. اینکه p تسهیل در کجا واقع شوند و کدام تسهیل باید کدام گره تقاضا را سرویس دهد، تصمیمات کلیدی در اینگونه مسائل هستند.
مسائل پوشش مجموعه در ابتدای دهه 70 ایجاد شد. هدف LSCP مکانیابی حداقل تعداد تسهیلات به گونه‌ای است که هر گره تقاضا بوسیله یک یا چند تسهیل «پوشش» داده شود. به طور کلی، تقاضا در یک گره i توسط تسهیل j پوشش داده شده نامیده می‌شود اگر فاصله (یا زمان سفر) بین گره‌ها کمتر از فاصله بحرانی D باشد. به علاوه، D به ماکزیمم فاصله یا زمان خدمتی که تصمیم‌گیرنده مشخص می‌کند اشاره می‌کند.
با این توضیحات، می‌توان مدل مکان پوشش مجموعه را که اولین بار توسط تورِگاس و همکارانش ارائه شد، به صورت زیر فرموله کرد:
(1.2)
(2.2)
(3.2)
تابع هدف (1.2) تعداد تسهیلاتی که استفاده می‌شوند را مینیمم می‌کند. محدودیت (2.2) تعیین می‌کند که برای هر نقطه تقاضای i، حداقل یک تسهیل باید در مجموعه ایجاد گردد که بتواند این گره را پوشش دهد. محدودیت‌های (3.2) محدودیت‌های تکمیلی هستند.

2-2-3-2- مسأله مکانیابی حداکثر پوشش
درمقابل مسأله پوشش مجموعه که در بالا آورده شد، مسأله مکانیابی حداکثر پوشش (MCLP) سعی نمی‌کند که همه مشتریان را پوشش دهد. تعداد p تسهیل را فرض کنید که هدف ما مکانیابی این تسهیلات به گونه‌ای است که بیشترین تعداد ممکن از مشتریان را پوشش دهیم. منظور از پوشش را نیز در بالا آوردیم.
با تعیین این محدودیت‌های مدل پوشش مجموعه، چِرچ و رِوِله مسأله مکانیابی حداکثر پوشش را به صورت زیر فرمول بندی کردند:
(4.2)
(5.2)
(6.2)
(3.2)
(7.2)
که اگر گره تقاضای i پوشش داده شود، برابر یک خواهد بود، درغیر اینصورت صفر می‌شود. تابع هدف (4.2) تعداد تقاضاهایی که پوشش داده می‌شوند را ماکزیمم می‌کند. محدودیت (5.2)، متغیرهای مکان و پوشش را به همدیگر مرتبط می‌کند و نشان می‌دهد که گره تقاضای i نمی‌تواند به عنوان پوشش داده شده تلقی گردد مگر اینکه ما حداقل یک تسهیل را در یکی از جایگاه‌های کاندید شده مستقر کنیم که بتواند آن گره را پوشش دهد. محدودیت (6.2) تعداد تسهیلات را به p محدود می‌کند و محدودیت‌های (3.2) و (7.2) محدودیت‌های تکمیلی هستند.
اگر تعداد تسهیلاتی که برای پوشش تمام تقاضاها نیاز است، از منابع دردسترس بیشتر شود، یک گزینه، راحت کردن الزامات برای پوشش کامل می‌باشد.
2-2-3-3- مسائل p-center
نوع دیگری از مسائل کلاسیک پوشش، اصطلاحاً مسائل p-center نامیده می‌شود. هدف مسائل p-center ، مکانیابی تعداد معین p تسهیل به گونه‌ای است که بزرگترین فاصله بین هر مشتری و نزدیکترین تسهیلش تا حد ممکن کوچک شود. اگرچه از دیدگاه نظری، مسائل p-center متفاوت هستند، اما یک روش دوبخشی ساده می‌تواند به کار گرفته شود تا مسائل p-center را به عنوان بخشی از مسائل پوشش حل نماید. این مسأله می‌تواند به صورت زیر فرمول بندی شود که Q ماکزیمم فاصله است که باید مینیمم گردد:
(8.2)
(9.2)
(10.2)
(6.2)
(11.2)
(3.2)
(12.2)
محدودیت (9.2) ما را مطمئن می‌کند که هر گره تقاضا تخصیص داده شده‌است، درحالیکه محدودیت (10.2) تصریح می‌کند که این تخصیصها می‌توانند فقط در تسهیلاتی که بهره برداری شده‌اند ایجاد شود. محدودیت (6.2) بیان می‌کند که دقیقاً p تسهیل می‌تواند ایجاد شود. محدودیت (11.2) ماکزیمم فاصله را برحسب متغیرهای تصمیم تعیین می‌کند. این محدودیت‌ها تصریح می‌کنند که Q باید بزرگتر یا مساوی با فاصله‌ای باشد که برای هر گره تقاضا تخصیص داده می‌شود.

2-2-3-4- مسائل p-median
درمقابل مسائل p-center با اهداف مینیماکسش که در قسمت قبل توضیح داده شد، مسائل
p-median اهداف مینیمم مجموع دارند. به عبارت دیگر مسائل p-median ، p تسهیل را به‌گونه‌ای مکان‌یابی می‌کنند که مجموع فواصل بین همه مشتریان و نزدیکترین تسهیل مرتبطشان مینیمم گردد. رِوِله و سواين47 مسأله p-median را به صورت زیر فرمول بندی کردند:
(13.2)
(9.2)
(10.2)
(6.2)
(3.2)
(12.2)
تابع هدف (13.2) کل فاصله‌ای که در تقاضا ضرب شده‌است را مینیمم می‌کند. از آنجائیکه تقاضاها مشخص هستند و کل تقاضا ثابت است، این هدف در حکم مینیمم کردن متوسط فاصله ضرب در تقاضا است. به خاطر داشته باشید که این فرمول بندی خیلی شبیه به فرمول بندی مسأله
p-center است مگر در تابع هدف و محدودیت شماره (11.2).

2-2-4- مسائل دیگر مکانیابی [8]
در این بخش به اختصار به انواع دیگری از مدل‌های مکانیابی که در مقالات استفاده شده‌است اشاره می‌کنیم. اولین نوع، مدل‌هایی هستند که به تسهیلات نامطلوب48 اشاره می‌کنند. چنین مدل‌هایی به مکانیابی تسهیلاتی همچون تأسیسات تصفیه فاضلاب، محل‌های بازیافت زباله‌ها، نیروگاه‌ها یا زندان‌ها می‌پردازند که همسایگی آنها با نواحی مسکونی نامطلوب به نظر می‌رسد.
به عنوان سیستم‌هایی که معمولاً شامل دو یا چند سطح از تسهیلات می‌شوند، از سیستمهای سلسله مراتبی49 استفاده می‌کنیم. بسیاری از سیستمها در طبیعت سلسله مراتبی هستند. این تسهیلات معمولاً برحسب نوع خدماتی که ارائه می‌کنند سلسله مراتبی هستند. مثلاً مراکز مراقبت‌های پزشکی را درنظر بگیرید که شامل کلینیک‌های عمومی، بیمارستان‌ها و مراکز دارویی هستند.
نوع دیگری از مدل‌ها، به مدل‌های مکانیابی می‌پردازد که اهداف «یکسان»50 دارند. این مدل‌ها، تسهیلات را به گونه‌ای مکانیابی می‌کنند که برای همه مشتریان به طور مساوی دردسترس باشند.
ناحیه فعال دیگر در این زمینه، مکانیابی هاب‌هاست. هاب به عنوان توپ در مرکز یک چرخ است و منظور از آن، تسهیلاتی است که به بعضی جفت‌های منبأ-مقصد به عنوان گره‌های معاوضه و حمل و نقل سرویس دهی می‌کند و در سیستمهای ترافیک و ارتباطات استفاده می‌شود.
نوع دیگر از مدل‌های مکانیابی، مدل‌های مکانیابی رقابتی51 است. مثالی از این نمونه به این صورت است که دو فروشنده انحصاری یک محصول را درنظر بگیرید که تسهیلی را هر کدام در یک پاره خط ایجاد می‌کنند. آنها از ابزاری مشابه استفاده می‌کنند و در مکان و قیمت رقابت می‌کنند.
در پایان، تسهیلات گسترده52 و مسائل جانمایی تسهیلات53 را درنظر بگیرید. در هر دو زمینه، به خاطر اینکه اندازه تسهیلات در قیاس با فضایی که در آن واقع شده‌اند قابل چشم پوشی نیست، تسهیلات نمی‌توانند به صورت یک نقطه بر روی نقشه نشان داده شوند و خیلی بزرگتر از آن هستند که به صورت یک نقطه درنظر گرفته شوند. به عنوان نمونه‌هایی از مسائل جانمایی، آرایش ایستگاه‌های کاری در یک اداره و قراردادن اتاق‌ها در یک بیمارستان را می‌توان نام برد.
2-2-5- مسائل مکانیابی تسهیلات با تقاضای تصادفی و تراکم
ما در این بخش به مسائل پیدا کردن مکان‌های بهینه برای مجموعه‌ای از تسهیلات در حضور تقاضای مشتریان تصادفی و تراکم در آن تسهیلات می‌پردازیم. ما به این گونه مسائل به عنوان «مسائل مکانیابی با تقاضای تصادفی و تراکم» (LPSDC)54 نگاه می‌کنیم [9]. اکثراً ما بحث درباره مسائل را به شبکه محدود می‌کنیم، حتی اگر این مدل‌ها بتواند به مکان‌های گسسته گسترش یابند.
اهمیت مشهود پرداختن به مسائل مکانیابی تسهیلات در حضور عدم قطعیت‌های گوناگون، منجر به تعداد زیادی از مقالات در این موضوع می‌شود. اصولاً مدل‌های LPSDC بر روی دو منبع از عدم قطعیت متمرکز می‌شود: (1) مقدار واقعی و مقدار زمانی که تقاضا بوسیله هر مکان مشتری تولید می‌شود و (2) از دست دادن تقاضا (یا جریمه پولی) به علت ناتوانی تسهیل در فراهم کردن سرویس مناسب به (بعضی از) مشتریان به علت تراکم در آن تسهیل.
این گونه مسائل به پیدا کردن بهترین مکان‌ها برای مجموعه‌ای از تسهیلات می‌پردازند تا ظرفیت سرویس (تعداد خدمت دهندگان) را در تسهیل j مشخص کند. نتیجه چنین سیستمی می‌تواند به صورت یک سیستم صف با M صف و سرویس دهنده مشاهده شود. حتی تحلیل‌های توصیفی چنین سیستمهایی (یعنی با فرض اینکه تصمیمات مکانیابی در حال حاضر گرفته شده‌اند) می‌تواند توانایی حال حاضر سیستم صف را گسترش دهد. چنین مسائلی، قابلیت‌های مسائل مکان‌یابی «کلاسیک» (که بیشتر آن‌ها NP-complete شناخته می‌شوند) را با پویایی پیچیده سیستم‌های صف ترکیب می‌کند. بنابراین، در ساختن یک مدل LPSDC کاربردی، بعضی فرض‌ها و تخمین‌های ساده سازی باید انجام شود تا مدل را قابل حل کند.
یک ناحیه مهم کاربرد مدل‌های LPSDC، مکان‌یابی تسهیلات خدمات اورژانسی (مانند بیمارستان‌ها)، ایستگاه‌های پلیس، ایستگاه‌های آتش نشانی و آمبولانس‌ها هستند. توانایی پاسخگویی به یک درخواست برای خدمت‌رسانی در زمان مناسب، به چنین سیستم‌هایی اختصاص دارد (مثلاً استاندارد رایج برای آمبولانس‌ها در آمریکای شمالی برای پاسخگویی به تلفن‌های با ارجحیت بالا، 3 دقیقه می‌باشد). خصوصیت پایه چنین سیستم‌هایی غیرقابل پیش بینی بودن تعداد و زمان رسیدن تلفن‌ها برای درخواست و اثری که روی کارایی سیستم تراکمی می‌گذارد است و هنگامی‌که بعضی از این تسهیلات درخواست‌های بسیاری را برای خدمت در دوره زمانی مشخصی دریافت می‌کنند، نتیجه آن مشخص می‌شود. به راستی که از لحاظ تاریخی، مسأله مکان‌یابی تسهیلات خدمات اورژانسی، محرّک اصلی برای تحقیقات بیشتر در این زمینه را فراهم کرده‌است.
دیگر ناحیه مهم کاربرد این مسائل که کمتر مورد تجزیه و تحلیل قرار گرفته‌است، مکان‌یابی خرده فروشی‌ها یا تسهیلات خدمت‌رسانی دیگر است که مقدار کل تجارت (تقاضای مشتری) در یک تسهیل ممکن است هنگامی‌که نرخ خدمت‌رسانی به علت تراکم کاهش می‌یابد، به طور معکوس عمل کند. درحالی که بعضی از مدل‌هایی که برای مکان‌یابی تسهیلات اورژانسی توسعه پیدا کرده‌اند، می‌توانند به خوبی برای تسهیلات غیراورژانسی نیز به کار روند، این دو دسته از کاربردها، خصوصیات مختلف خودشان را نیز ایجاد می‌کنند.
2-2-5-1- مرور ادبیات مسائل مکانیابی تسهیلات با تقاضای تصادفی و تراکم [10]
باتوجه به انعطاف پذیری تقاضا، دسترسی به یک تسهیل می‌تواند برحسب مجاورت با مشتریان بالقوه اش (وِرتر و لاپيِره55)، به صورت کل زمان موردنیاز برای دریافت سرویس (پارکر و سرينيواسان56) مدل سازی شود. در این مورد یا موارد دیگر، شکل تابع تقاضای مورداستفاده، گسترشی از انعطاف پذیری تقاضا را نشان می‌دهند. بیشتر توابع تقاضای رایج در مقالات به شکل‌های زیر هستند: تابع خطی (وِرتر و لاپيِره؛ پارکر و سرينيواسان)؛ تابع نمایی (بِرمن و پارکان57؛ بِرمن و کاپلان58 و درِزنِر)؛ و تابع مرحله‌ای (بِرمن و کِراس).
اگر انتخاب مشتری را درنظر بگیریم ( که بدین معنی است که هر عضو این حق را دارد که خود تسهیلش را انتخاب کند و نه اینکه توسط یک مرکز به یکی اختصاص پیدا کند)، یک گروه از مقالات، انتخاب بهینه را فرض می‌کنند، یعنی، هر مشتری، تسهیلی که برحسب مزیتش بهینه است را انتخاب می‌کند. بسیاری از نویسندگان به سادگی فرض می‌کنند که مشتریان به نزدیکترین تسهیل مراجعه می‌کنند، درحالیکه پارکر و سرينيواسان فرض می‌کنند که مشتریان، تسهیلی که بیشترین منفعت را دارد انتخاب می‌کنند. درمقابل، گروه دوم مطالعات، انتخاب احتمالی را فرض می‌کنند، یعنی، انتخاب تسهیل توسط مشتری، براساس توزیع احتمالی است که از سودمندی و مجاورت هر تسهیل ایجاد می‌شود. این فرض اغلب در محیط بازار استفاده می‌شود و شاید یک کار اصولی از هاف59، مؤثرترین مدل در این دسته باشد. همچنین ماريانوف60 و همکارانش یک مسأله مکانیابی تسهیلات با تراکم را پیشنهاد کردند که از یک مدل انتخابی احتمالی برای نشان دادن رفتار تخصیص مشتریان استفاده می‌کرد.
مسأله موردنظر ما که تا حدودی در تئوری مکان‌یابی تسهیلات، پایه‌ای به حساب می‌آید، توجّهات بسیاری را در مقالات به خود جلب

پایان نامه
Previous Entries منابع پایان نامه ارشد با موضوع مکانیابی، زنجیره تأمین، مدل سازی Next Entries منابع پایان نامه ارشد با موضوع مکانیابی، ساده سازی، قانونگذاری