نشریه تخصصی مهندسی صنایع، دوره 48، شماره 1، فروردین ماه 1393، از صفحه 13 تا 22 مکان یابی براي دو تسهیل مستعد ازدحام با در نظر گرفتن مشتریان
کم حوصله

جمال ارکات*1و شکوفه زمانی2
استادیار گروه مهندسی صنایع – دانشگاه کردستان
دانش آموخته کارشناسی ارشد مهندسی صنایع – دانشگاه کردستان
(تاریخ دریافت 21/2/92، تاریخ دریافت روایت اصلاحشده 6/11/92، تاریخ تصویب 18/12/92 )

چکیده
در این مقاله، مسئله مکان یابی شبکه اي براي دو تسهیل مستعد ازدحام و مشتریان کم حوصله مورد بررسی قرار مـی گیـرد . هـر مشـتريهنگام مراجعه به تسهیل مربوطه، در صورتی که با اندازه صفی بیش از آستانه تحمل خود مواجه شود، از ورود منصرف شده و به تسهیل دیگـرمراجعه می کند. در تسهیل دوم نیز اگر وضعیتی مشابه وجود داشته باشد، مشتري از دریافت خدمت، منصـرف مـی شـو د. هـ دف ایـن مسـئله، انتخاب دو مکان از بین تعدادي مکان کاندیدا براي احداث دو تسهیل خدمت دهنده و تخصیص مشتریان شبکه به تسهیلات ذکرشده است؛ بـهگونه اي که میزان تقاضاي از دست رفته به دلیل وجود صف طولانی، کمینه شـو د. بـا تعریـف و توسـعه گونـه جدیـدي از سیسـتم هـاي صـففوق مکعبی، مدل ریاضی مسئله ارائه می شود و براي سنجش کارآیی و درستی آن، یک مثال عددي، ارائه و توسط نرم افزار GAMS حل می شود.

واژه هاي کلیدي: مکان یابی شبکه اي، تسهیلات پرازدحام، سیستم هاي صف فوق مکعبی، مشتریان کم حوصله

مقدمه
به طور کلی مسائل مکان یابی تسهیلات را می توان به دو دسته مکان یابی تسهیلات متحرك و مکان یابی تسهیلات ثابت تقسیم کرد. در مسائل مکان یابی تسهیلات ثابت، در هر تسهیل، یک یا چند خدمت دهنده مستقر هستند و هر مشتري براي دریافت خدمت مورد نیاز به محل استقرار تسهیل متناظر مراجعه می کند. مکان یابی دستگاه هاي خودپرداز بانک، وب پروکسی هاي1 مربوط به سیستم هاي ارتباطی و ایستگاه هاي سوخت رسانی از جمله کاربردهایی هستند که در ادبیات تحقیق به فراوانی به آنها پرداخته شده است. در مکان یابی تسهیلات متحرك، فرض می شود که یک یا چند خدمت دهنده که در هر یک از تسهیلات مستقر هستند، براي ارائه خدمات به محل مشتریان مراجعه می کنند و خدمت مربوطه در محل مشتري ارائه می شود. مکان یابی تسهیلات اضطراري مانند ایستگاه هاي آمبولانس، پلیس یا آتش نشانی، کاربردهاي اصلی براي این نوع از مسائل مکان یابی به شمار می روند.
Email: [email protected] ،08716660073 :نویسنده مسئول: تلفن *

از سویی، مسائل مکان یابی را می توان بر اساس معیار وجود یا نبود ازدحام2 در سیستم خدمت دهی به دو دسته تقسیم کرد. در دسته نخست، مسائل متعارفی همچون p-میانه3، c-مرکز4 و پوشش مجموعه5 قرار می گیرند که در آنها فرض می شود که خدمت دهی به هر مشتري بلافاصله پس از ورود وي به تسهیل انجام می گیرد و هیچگاه در سیستم، صف تشکیل نمی شود. در دسته دوم، زمان هاي خدمت دهی در مقایسه با فواصل زمانی بین ورود مشتریان متوالی، قابل ملاحظه هستند و بنابراین صف تشکیل می شود و مشتریان مجبور خواهند بود در نظامی از قبل مشخص، براي شروع خدمت دهی، منتظر بمانند. به دلیل نبود قطعیت در زمان هاي بین ورود مشتریان و زمان هاي خدمت دهی، مسائل مکان یابی با ازدحام، از مسائل پیچیده براي مدل سازي و حل به شمار می روند.
لارسون [1 و 2] نخستین محققی است که با ارائه ایده ایجاد ازدحام در ارائه خدمت به مشتریان، فرض متداول قطعی بودن ماهیت مسایل دنیاي واقعی را در مسائل مکان یابی به چالش کشید. مدل هاي مکان یابی با ازدحام ،بر اساس معیارهایی مانند تعداد خدمت دهندگان مستقر در هر تسهیل، قاعده تخصیص مشتریان به تسهیلات (مانند قاعده مجاورت6 و قاعده جاذبه7)، توزیع زمان هاي بین ورود مشتریان متوالی و توزیع زمان هاي خدمت دهی ،دسته بندي می شوند. مهم ترین وجه تمایز مدل هاي مکان یابی با تسهیلات با ازدحام، نوع تابع هدف به کار گرفته در آنها است و از این نظر، این مسائل به سه دستهمسائل میانه، مسائل پوششی و مسائل مرکز تقسیممی شوند.
مدل هاي میانه به مدلهایی اطلاق می شوند که در آنها توابع هدف به صورت حداقل کردن مجموع هزینه ها یا زمانهاي سفر و انتظار مشتریان تعریف می شوند. وانگ و همکاران [3] مدل مکان یابی تسهیلات پرازدحام با خدمت دهنده ثابت را براي حالتی که در هر تسهیل ،حداکثر یک خدمتدهنده مستقر شود و مدل صف ایجاد شده از نوع M/M/1 (یک خدمت دهنده، ورودهاي پواسان و زمان هاي خدمتنمایی) باشد، مورد مطالعه قرار دادند. تابع هدف مدل ارائه شده، با تأکید بر جنبه هاي مشتري مداري ،مجموع هزینه هاي سفر مشتریان و تسهیلات و هزینه هاي انتظار آنها در صف را کمینه می کند. برمن و درزنر [4] با توسعه مدل وانگ [3] از تسهیلات تک خدمت دهنده به تسهیلات چندخدمت دهنده، به بررسی سیستمهاي M/M/c پرداختهاند. در مدل ارائه شده، از قاعده مجاورت براي تخصیص مشتریان استفاده شده است. یعنی هر مشتري براي دریافت خدمت به نزدیک ترین خدمت دهنده مراجعه میکند و در شرایطی که دو یا چند خدمت دهنده در فاصله یکسانی از وي قرار داشته باشند، به نسبت یکسان ،از آنها استفاده می کند. در تابع هدف این تحقیق، مجموع هزینه هاي مربوط به زمانهاي سفر مشتریان به تسهیلات و میانگین زمانهاي صرف شده در صف انتظار، کمینه میشوند. نویسندگان براي حل این مسئله از سه روش فراابتکاري الگوریتم ژنتیک8، بازپخت شبیهسازي شده9 و جستجوي ممنوعه10 استفاده کرده اند و نشان دادهاند که الگوریتم ژنتیک نسبت به دو الگوریتم دیگري کارآیی بالاتري دارد.
مدل ریاضی ارائه شده توسط پسندیده و اخوان نیاکی [5] از جمله معدود مدل هایی است که به طور همزمان هر دو جنبه مشتري و خدمت دهنده را در تابع هدف در نظر گرفته است. محققان یک مدل دوهدفه را به صورت کمینه کردن همزمان مجموع زمان هاي سپري شده توسط مشتریان ( زمانهاي سفر و زمانهاي انتظار در سیستم) و درصد بیکاري خدمت دهندگان ارائه کرده اند. در این مدل، فرض شده است که در هر تسهیل، فقط یک خدمتدهنده میتواند مستقر شود، بنابراین مدل صف بررسی شده، ازنوع M/M/1 است. از آنجایی که مدل ارائه شده یک مدلدوهدفه عدد صحیح آمیخته غیرخطی است، نویسندگانبراي حل آن از الگوریتم ژنتیک استفاده کرده اند. مشابهتحقیق پیشین، چمبري و همکاران [6] یک مدل دوهدفه را با در نظر گرفتن همزمان دو جنبه مشتري و خدمت دهنده ارائه کرده اند. توابع هدف مدل ارائه شده ،مشابه توابع هدف تحقیق قبلی است. فرض اصلی که این مدل را از مدل پیشین متمایز می کند، در نظر گرفتن ظرفیت محدود براي فضاي انتظار در هر یک از تسهیلات و در نتیجه استفاده از نتایج مربوط به سیستم هاي صف M/M/1/K است. محققان براي به دست آوردن مجموعه نقاط نامغلوب، از دو روش فراابتکاري چندهدفه NRGA و NSGA-II استفاده کرده اند. نتایج محاسباتی ارائه شده حاکی از برتري روش دوم نسبت به روش نخست است.
بر خلاف دسته اول، مدل هاي مکان یابی تسهیلات پرازدحام با سرورهاي ثابت که در آنها تابع هدف به کیفیت پوشش مشتریان معطوف است، تمرکز تابع هدف دسته دوم این گونه مدل ها (یعنی مدل هاي پوششی) بر میزان پوشش مشتریان است. بدین ترتیب در دسته دوم ،توابع هدفی نظیر بیشینه کردن میزان پوشش یا کمینه کردن مشتریان خارج از محدوده پوشش تسهیلات، به کار برده شده اند. برمن و همکاران [7] تابع هدف حداکثر کردن امید تعداد مشتریان پوشش داده شده را براي مسئله مکان یابی تسهیلات، ثابت در نظر گرفته اند. در این تحقیق، معیار مجاورت یعنی مراجعه مشتري به نزدیک ترین تسهیل، به عنوان یکی از مفروضات اصلی در نظر گرفته شده است. در صورتی که تسهیل متناظر یک مشتري به حداکثر ظرفیت خود رسیده باشد و امکان پذیرش مشتریان جدید وجود نداشته باشد، مشتریان تخصیص یافته به آن، به نزدیک ترین تسهیل بعدي که تا کنون ملاقات نکرده اند، مراجعه می کنند. هاماگوچی و ناکاده [8] مسئله مکان یابی شبکه اي با تسهیلات ثابت را بر اساس سیستم صف M/G/1 مدل سازي کرده اند؛ بدین معنی که محققان فرض کرده اند که زمان هاي بین ورودهاي متوالی مشتریان از توزیع نمایی پیروي می کنند، اما زمان هاي خدمت دهی به صورت یک توزیع کلی در نظر گرفته می شوند. تابع هدف مدل ارائه شده، بیشینه کردن مجموع تقاضاهاي پوشش داده شده است. در این تحقیق، از روش تبدیل لاپلاس براي محاسبه تابع توزیع زمان انتظار مشتریان در سیستم استفاده شده است، اما به دلیل پیچیدگی وارون تبدیل لاپلاس، شکل صریحی برايزمان هاي انتظار مشتریان به دست نیامده و بنابراین محققان به روش هاي ابتکاري متوسل شده اند. معین مقدس و تقیزاده کاخکی [9] مسئله مکان یابی بیشینه پوشش را با در نظر گرفتن تسهیلات چندخدمت دهنده ،مورد بررسی قرار داده اند. در مدل ارائه شده براي این مسئله، فرض شده است که متوسط زمان انتظار در هر تسهیل و همچنین مجموع هزینه هاي برپایی تسهیلات و خدمت دهندگان از آستانه هاي مشخصی، تجاوز نکند. از آنجایی که تعداد خدمت دهندگان موجود در هر تسهیل ،جزو متغیرهاي تصمیم مدل ریاضی در نظر گرفته شده اند ،ساختار مدل ریاضی ارائه شده، به مراتب پیچیده تر از مدل هاي متعارف M/M/1 است. نویسندگان براي حل مسئله ارائه شده، دو الگوریتم ابتکاري جستجوي محلی را توسعه داده اند.
تابع هدف مدل هاي مکان یابی مرکز به عنوان دسته سوم از مسائل مکان یابی تسهیلات پرازدحام، از نوع کمینه کردن بیشینه (minimax) فاصله یا زمان هاي خدمت دهی است. استفاده از این نوع تابع هدف، مختص مسائل مکان یابی تسهیلات اورژانسی است، یعنی مسائلی که در آنها لازم است در کوتاه ترین زمان ممکن به دورترین مشتري نیز خدمت رسانی انجام شود. مسائلی همچون مکان یابی ایستگاه هاي آمبولانس، آتش نشانی یا پلیس از این قبیل مسائل هستند. به عنوان نمونه اي از تحقیقاتی که به این نوع از مسائل پرداخته اند، می توان به آبولین [10] اشاره کرد. در مدل ریاضی ارائه شده در این تحقیق ،بر بهینه کردن نیاز هر یک از مشتریان، تأکید و تابع هدف به صورت کمینه کردن حداکثر زمان طی شده براي هر مشتري در نظر گرفته شده است. همچنین زمان سپري شده توسط هر مشتري مشتمل بر زمان هاي سفر مشتري از مکان استقرار تا تسهیل تخصیص یافته به انضمام زمان هاي انتظار در صف دریافت خدمت، در نظر گرفته شده است.
فرض وجود ازدحام علاوه بر مسائل متعارف مکان یابی تسهیلات، در نسخه هاي جدیدتري از مسائل مکان یابی مانند مکان یابی هاب11، مکان یابی رقابتی12 و طراحی زنجیره تأمین، در نظر گرفته شده اند. دي کامارگو و میراندا [11] یک مدل برنامه ریزي ریاضی عدد صحیح آمیخته براي تعیین مکان استقرار هاب ها ارائه کرده اند. در این تحقیق هزینه هاي ناشی از ازدحام در هر هاب بهکمک تابعی از مقدار جریان در هاب محاسبه می شود. تابع هدف مدل پیشنهادي هزینه هاي استقرار، هزینه هاي حمل و نقل و هزینه هاي ناشی از ازدحام در هاب ها را کمینه می کند. محققان براي حل مدل پیشنهادي خود از روش تجزیه بندرز13 استفاده کردهاند. کونور و گیونس [12] یک مدل مکان یابی چندتسهیلی رقابتی را با در نظر گرفتن وقوع ازدحام ترافیکی در خطوط ارتباطی ارائه کرده اند. در این مدل تعدادي شرکت ضمن استقرار مراکز فروش خود ،براي افزایش منافع خود به رقابت می پردازند. هزینه هاي ازدحام در هر یک از مسیر هاي ارتباطی براي هر شرکت به صورت تابعی خطی از مقدار کل جریان در آن مسیر محاسبه می شود. محققان براي حل مدل، یک روش ابتکاري پیشنهاد و نتایج آن را با روش جستجوي تصادفی مقایسه کردند. جوزدانی و همکاران [13] یک مدل برنامه ریزي عدد صحیح آمیخته غیرخطی پویا براي برنامه ریزي زنجیره تأمین و مکان یابی تسهیلات مرتبط با چرخه تولید لبنیات ارائه کرده اند. در این مدل ،نبود قطعیت در مقادیر تقاضا به صورت اعداد فازي مثلثی نمایش داده شده است. علاوه بر این، فرض وقوع ازدحام ترافیکی در مسیر هاي ارتباطی از جمله فرض هاي کلیدي در این تحقیق محسوب می شود. تابع هدف مدل ارائه شده، مجموع هزینه هاي استقرار تسهیلات، هزینه هاي ناشی از ازدحام ترافیکی و هزینه هاي حمل شیر خام، شیر پردازش شده و محصولات لبنی را کمینه می کند.
یکی از موضوعات مهمی که در تحقیقات مکان یابی تسهیلات پرازدحام، کمتر بدان پرداخته شده است، امکان انصراف مشتري، قبل یا بعد از ورود به سیستم خدمت دهی است؛ مقوله اي که در بسیاري از سیستم هاي صف دنیاي واقعی، مشاهده می شود. انصراف قبل از ورود که به دلیل ازدحام بیش از آستانه تحمل مشتري اتفاق می افتد ،مهم ترین نوع انصراف به شمار می رود. همچنین در بسیاري از سیستم هاي صف دنیاي واقعی، مشتري پس از انصراف از ورود به یک تسهیل، ممکن است به امید خلوت تر بودن تسهیلات دیگر، به این تسهیلات مراجعه کند. تحقیق انجام شده توسط برمن و همکاران [7] از معدود مطالعاتی است که به موضوع انصراف مشتري پرداخته است. مدل صف در نظر گرفته شده در این مطالعه، از نوع M/M/1/K است. به دلیل ساختار پیچیده این
مسئله ، مدل ریاضی صریحی این تحقیق ارائه نشدهاست و فقط شکل ریاضی معیار ارزیابی راه حل ها (به عنوانتابع هدف) به صورت حداکثرکردن امید ریاضی تقاضاي جذب شده، ارائه شده است. بر اساس معیار ارزیابی مربوطه ،دو الگوریتم ابتکاري تقریبی براي حل مسئله پیشنهاد شده است. الگوریتم هاي ارائه شده ساختار تکراري حریصانه14 دارند؛ بدین معنی که در حلقههاي بهبود تکرارشونده، مکان هاي استقرار تسهیلات تا جایی تغییر داده می شوند که امکان بهبود راه حل وجود داشته باشد. به دلیل ساختار ابتکاري الگوریتم هاي ارائه شده، تضمینی براي بهینگی راه حل نهایی وجود ندارد.
در تحقیق حاضر ،مسئله مکان یابی شبکه اي براي دو تسهیل پرازدحام در قالب یک مدل پوششی مورد بررسی قرار می گیرد. در این مسئله، انصراف قبل از ورود (به دلیل فضاي انتظار تسهیل یا کم حوصلگی مشتري) به عنوان یکی از منابع از دست دادن تقاضا مدنظر قرار می گیرد.
بدین منظور فرض میشود که تقاضاي هر مشتري از طریق نزدیکترین تسهیل پوشش داده می شود و در صورتی که مشتري در لحظه ورود با تعداد مشتریانی بیش از آستانه انتظار، روبه رو شود، از ورود منصرف شده و به تسهیل باز دیگر مراجعه می کند. در صورتی که مشتري در تسهیل دوم نیز با صف بیش از حد تحمل، مواجه شود، از دریافت خدمت منصرف میشود و در نتیجه، تقاضاي وي به عنوان تقاضاي از دست رفته محسوب می شود. در مسئله دوتسهیلی حاضر به عنوان شکل خاصی از مسئله چندتسهیلی، هر تسهیل به عنوان پشتیبان براي تسهیل دیگر عمل می کند، بنابراین نیازي به گرفتن تصمیم در مورد انتخاب تسهیل پشتیبان براي هر تسهیل وجود ندارد. این در حالی است که در شکل اصلی مسئله، باید براي هر یک از تسهیلات احداث شده، تسهیل پشتیبان نیز با در نظر گرفتن متغیرهاي تصمیم مناسب، مشخص شود. در نظر گرفتن این مجموعه از متغیرهاي تصمیم ، مدلسازي مسئله را بسیار پیچیده می کند، به گونه اي که لازم است شیوه دیگري براي مدل سازي، مدنظر قرار گیرد.
ساختار مطالبی که در ادامه عنوان خواهند شد، بدین ترتیب است: در بخش بعدي، شکل کلی مسئله، تشریح و یک مدل ریاضی ارائه می شود. براي به دست آوردن شکل صریحی براي مدل ریاضی، مدل صف متناظر مسئله دربخش سوم، تحلیل و نتایج آن در بازنویسی مدل ریاضیمورد استفاده قرار می گیرد. در بخش چهارم، یک مثالعددي براي تشریح نحوه استفاده از مدل ریاضی و بهدست آوردن راه حل بهینه، ارائه می شود. در نهایت، جمع بندي ، نتیجه گیري و ارائه پیشنهادها در بخش آخر مقاله ارائه می شوند.

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

مجموعه اندیس ها
I : مجموعه مشتریان (i اندیس مشتریان) J : مجموعه سایت هاي بالقوه احداث تسهیل (j و r اندیس سایت هاي کاندیدا) L : مجموعه تسهیلات (l و k اندیس تسهیل)

پارامترها C : تعداد مشتریان
S : تعداد سایت هاي کاندیدا K : ظرفیت تسهیلات باز (آستانه تحمل مشتریان) di : نرخ تقاضا (تعداد در واحد زمان) براي مشتري i
 : نرخ خدمت دهی در هر یک از تسهیلات tij : کوتاه ترین فاصله بین گره i و گره j
1M و 2M : اعداد بزرگ مثبت Q : ماتریس نرخ انتقال براي وضعیت هاي سیستم صف

متغیرهاي تصمیم
y jl : اگر سایت بالقوه j به منظور استقرار تسهیل lام فعال شود، برابر 1 و در غیر این صورت برابر 0 است.
xijl : اگر مشتريi به تسهیلl ام که در سایت j مستقر است، تخصیص یابد، برابر 1 و در غیر این صورت برابر 0 است.
l : مجموع نرخ تقاضاي ورودي به تسهیل l.
Π : بردار احتمالات حدي براي سیستم صف.
,n m: احتمال حدي حضور n نفر در تسهیل اول و mنفر در تسهیل دوم.
با در نظر گرفتن نمادگذاري معرفی شده، مدل ریاضیمتناظر با مسئله به این ترتیب ارائه می شود:
Min Z K K,
cs
l x dijli  l
i 1 1j
s 2
xijl  1 i
j 1 1l
2
yjl  1j
l1
s
yjl  1l
j1
c
xijl  M y1 jl  ,j l
i1
s 2
x tirl ir  tijM2 1 yjk  i j k, ,
r 1 1l
Π.Q0
n m, n m, 1
x ,ijl yjl 0,1 i, ,j l (10)
l  0 (11)
0 (n m,)  1n m, (12)
در صورتی که مشتري هنگام مراجعه، با ظرفیت کامل هر دو تسهیل مواجه شود، امکان پوشش تقاضاي وي وجود ندارد. با این اوصاف، درصد اوقاتی که تقاضاي مشتریان از دست می رود، برابر با درصد اوقاتی است که هر دو تسهیل به طور کامل پر هستند (به عبارتی، امکان پذیرش مشتریان را ندارند). بنابراین تابع هدف مسئله به صورت کمینه کردن درصد زمان هاي بلوکه شدن هر دو تسهیل یعنی ,K K در رابطه (1) تعریف شده است. رابطه (2) مجموع تقاضاي مربوط به هر یک از تسهیلات را محاسبه می کند. محدودیت (3) تضمین می کند که هر مشتري به یک تسهیل، تخصیص داده شود. محدودیت (4) نشان می دهد که در هر سایت کاندیدا، حداکثر یک تسهیل مستقر می شود. محدودیت (5) تضمین می کند که هر تسهیل فقط در یکی از سایت هاي کاندیدا مستقر شود. محدودیت (6) تضمین می کند که مشتریان فقط به تسهیلات باز تخصیص یابند. این محدودیت ،1M
نشان دهنده یک عدد مثبت بزرگ است و حداقل باید برابربا تعداد کل نقاط تقاضا در نظر گرفته شود. محدودیت (7) قاعده مجاورت را تضمین می کند، بدین معنی که هر مشتري به نزدیکترین تسهیل، تخصیص می یابد. 2M نیز یک عدد مثبت بزرگ است و حداقل باید برابر با بزرگ ترین عدد موجود در ماتریس فاصله در نظر گرفته شود. محدودیت هاي (8) و (9) مجموعه معادلات تعادل مرتبط با سیستم صف را نشان می دهند. لازم به ذکر است که رابطه (8) فقط شکل کلی معادلات تعادل براي یک زنجیره مارکوف پیوسته است و لازم است پس از تحلیل سیستم صف به صورت مجموعه اي از معادلات صریح ،بازنویسی شود. محدودیت هاي (10) تا (12) دامنه متغیرهاي مربوط به مدل ارائه شده را نشان می دهند.

تحلیل سیستم صف
مدل ریاضی ارائه شده در بخش قبل، شکل صریحی ندارد. بدین معنی که براي به دست آوردن مقدار تابع هدف (احتمال انصراف مشتري) لازم است نخست دستگاه معادلات تعادل سیستم صف (روابط (8) و (9)) حل شود.
براي دستیابی به شکلی صریح براي تابع هدف، لازم است سیستم صف مربوطه، تحلیل و دستگاه معادلات تعادل آن ،حل شود. نخستین گام در تحلیل یک سیستم صف، ارائه تعریفی مناسب براي وضعیت هاي آن است. واضح است که دو خدمت دهنده موجود در شبکه به طور کامل مستقل عمل نمی کنند و بخشی از مشتریان هر یک از این دو تسهیل به دلیل وجود ازدحام بیش از حد انتظار (تکمیل ظرفیت) در خدمت دهنده متناظرشان، به خدمت دهنده دیگر، مراجعه می کنند. با این اوصاف، ورودي هر یک از تسهیلات، علاوه بر مشتریانی که به آن تخصیص یافته اند، شامل بخشی از مشتریان تسهیل دیگر که موفق به دریافت خدمت نشده اند نیز هست. بنابراین، فرآیند ورود به هر تسهیل، پواسان نیست و سیستم هاي صف مربوط به تسهیلات باز را نمی توان به صورت سیستم هاي مستقل M/M/1/K در نظر گرفت. وجود چنین مشکلی (نبود استقلال خدمت دهندگان) باعث می شود نتوان از تعریف وضعیت و نتایج سیستم هاي صف متعارف استفاده کرد. در نظر گرفتن همزمان تعداد مشتریان حاضر در دو تسهیلخدمت دهنده، به عنوان وضعیت سیستم صف، چنینمشکلی را حل می کند. بدین ترتیب، وضعیت سیستم صفبه صورت n m,  تعریف می شود که در آن ،n تعدادمشتریان موجود در تسهیل اول و m تعداد مشتریانموجود در تسهیل دوم را نشان می دهد. این نوع تعریف،وضعیت مشابه تعریف وضعیت براي سیستم هاي صف فوق مکعبی16 است. تحقیقاتی که به بررسی چنین سیستم هاي صفی پرداخته اند، به دشواري تحلیل این سیستم هاي صف، اذعان کرده اند. لارسون [1] اولین کسی است که از سیستم هاي صف فوق مکعبی در تحلیل مسئله مکان یابی تسهیلات اورژانسی استفاده کرده است. در این مسئله، فرض همکاري تسهیلات در ارائه خدمات در نظر گرفته شده است، بدین معنی که در صورتی که تسهیلی قادر به پاسخ گویی نیاز یکی از مشتریان خود نشود، سایر تسهیلات می توانند به عنوان پشتیبان، این نیاز را جوابگو باشند. محقق براي هر یک از تسهیلات، دو وضعیت صفر و یک را که معرف مشغول یا بیکار بودن تسهیل است، در نظر گرفته و به ارائه معادلات تعادل پرداخته است. چنین تعریف وضعیتی براي مسائل مکان یابی تسهیلات اورژانسی که در آنها فرض تسهیل پشتیبان در نظر گرفته می شود ،متداول است؛ به طور مثال می توان از ماریانوف و رول
[14] و آتکینسون [15] نام برد.
تعریف وضعیتی که در تحقیق حاضر استفاده شده است را می توان حالت تعمیم یافته اي از تعریف وضعیت مربوط به سیستم هاي صف فوق مکعبی در نظر گرفت. بدین صورت که وضعیت هر یک از تسهیلات خدمت دهنده به جاي بیکار یا مشغول بودن (صفر یا یک)، به صورت تعداد مشتریان موجود در آنها در نظر گرفته می شود. از آنجایی که وضعیت هر تسهیل به صورت تعداد نفرات موجود در آن تعریف شده است و ظرفیت هر یک از تسهیلات نیز K نفر است، تعداد کل وضعیت هاي سیستم2K 1 خواهد بود. معادلات تعادل مربوط به وضعیت هاي این سیستم صف به شرح روابط (13) تا (21) هستند:

    1  2  0,0   1,0  0,1  (13)
   1  2 n,0  1 n1,0
(14)
  n1,0  n,1 ;0  n K
   1  21,m  0,0m,m1 ; 020,m 1 m K
   1  2 K,0  1 K1,0 K ,1
   1  2 0,K  20,K1 1,K
   1  22  n m,  1 n m1, 2 n m, 1
 n m1, n m, 1 ;0 n m K, 
    1  22 n K, 21  n K, n K 1,( ; 01  2 )n Kn K1,
    1  22  K m,  ( 12 ) K m, 1
1 K m1, K m, 1 ;0  m K
2 KK,    1  2  K K1, KK, 1 

در حقیقت این معادلات، هم ارز شکل ماتریسی معادلات تعادل است که در رابطه (8) نشان داده شده اند. با مشخص بودن ظرفیت تسهیلات (K ) و نرخ خدمت دهی در هر تسهیل ()، می توان با پارامتریک در نظر گرفتن نرخ هاي ورود هر یک از تسهیلات ( 1 و 2)، احتمالات حدي را از حل دستگاه معادلات بالا به دست آورد. از سویی، از آنجایی که مجموع نرخ هاي ورود به دو تسهیل برابر با کل نرخ تقاضاي مشتریان (  i ) است، می توان احتمالات حدي را فقط بر حسب 1

جدول 1: ماتریس فاصله اي و نرخ هاي وقوع تقاضا
10 9 8 7 6 5 4 3 2 1
77 74 103 84 12 83 13 34 26 0 1
79 49 77 86 14 85 38 36 0 26 2
43 44 73 50 32 49 43 0 36 34 3
82 86 115 93 24 92 0 43 38 13 4
16 57 60 20 82 0 92 49 85 83 5
76 62 91 82 0 82 24 32 14 12 6
36 38 40 0 82 20 93 50 86 84 7
76 29 0 40 91 60 115 73 77 103 8
74 0 29 38 62 57 86 44 49 74 9
0 74 76 36 76 16 82 43 79 77 10
0.08 0.19 0.18 0.19 0.04 0.06 0.06 0.07 0.05 0.08 d

محاسبه کرد. بدین ترتیب، تابع هدف مدل ریاضی ارائهشده در بخش قبل ( .K K) به صورت تابعی از متغیرتصمیم 1 بازنویسی شده و مجموعه معادلات تعادل(روابط (8) و (9)) از مجموعه محدودیت هاي مسئله حذفمی شوند. با انجام این مراحل، مدل ریاضی در شکلی صریح به دست خواهد آمد و می توان از نرم افزارهاي بهینه ساز براي حل آن استفاده کرد.

مثال عددي
در این قسمت، مدل ارائه شده براي یک مثال عددي ،حل و بررسی می شود. مثال عددي ارائه شده شامل 10 نقطه تقاضا است و هر نقطه تقاضا به عنوان یک مکان کاندیدا براي احداث دو تسهیل در نظر گرفته شده است.
محدودیت فضا براي هر یک از تسهیلات، سه نفر در نظر گرفته شده است. ماتریس فواصل بین جفت گره هاي شبکه و همچنین نرخ هاي تقاضاي مربوط به هر گره (مشتري) در جدول (1) نشان داده شده اند. نرخ خدمت دهی براي هر یک از دو تسهیل برابر با یک خدمت در واحد زمان در نظر گرفته شده است. مجموع کل تقاضاي مشتریان نیز که از آخرین سطر جدول (1) قابل محاسبه است، برابر با یک تقاضا در واحد زمان است.
با توجه به آنچه در بخش قبل گفته شد، تعداد کل وضعیت هاي سیستم ،16 وضعیت است. بنابراین 16 معادله تعادل نیز متناظر با این وضعیت ها بر اساس روابط (13) تا (21) به دست می آیند. از آنجایی که این معادلات وابستگی خطی دارند، دستگاه معادلات تعادل مربوط به سیستم صف از جایگزین کردن یکی از معادلات با رابطه مربوط به مجموع احتمالات حدي (رابطه (9)) به دست خواهد آمد. با انجام جایگزینی هاي 1 و 2 1 1   در دستگاه معادلات به دست آمده، می توان مقادیر احتمالات حدي را بر حسب 1 به دست آورد. پس از حل پارامتریک این دستگاه معادلات، مقدار تابع هدف به صورت زیر به دست می آید:
K K, 

A
B
که در آن A و B چندجمله اي هایی به شکل زیر هستند:
A243536   16 72 219715 54 14 12 13 351812
1
B36016 10802 15 67414 45213
84356 84762102212
11
با در اختیار داشتن شکل صریح تابع هدف، می توان مدل ریاضی ارائه شده را با در نظر گرفتن رابطه (22) به عنوان تابع هدف و محدودیت هاي (2) تا (7) و (10) و (11) بازنویسی کرد. مدل ایجادشده توسط حل کننده COUENNE از نرم افزار بهینهسازGAMS حل شده است. نتایج حل، حاکی از آن است که در راهحل بهینه ،تسهیلات 1 و 2 به ترتیب در مکانهاي کاندیداي 3 و 5 مستقر شده و به ترتیب مجموعه مشتریان {1، 2، 3، 4، 6 و 9} و {5، 7، 8 و 10} را با مجموع تقاضاهاي 49/0 و 51/0 پوشش می دهند. مقدار بهینه به دست آمده براي تابع هدف نیز 016/0 است.
با توجه به اینکه پارامترهاي K (ظرفیت تسهیلات) و  (نرخ خدمتدهی در هر تسهیل) از اصلی ترین پارامترهاي مؤثر بر درصد تقاضاي از دست رفته هستند ،در این قسمت به تحلیل حساسیت و بررسی تأثیر این دو پارامتر بر نتایج حل مدل می پردازیم. براي این منظور، مثال یاد شده، با در نظر گرفتن مقادیر K و  مختلف ،حل می شود. جداول (2) و (3) مقادیر مربوط بهپارامترهاي یاد شده و نتایج حل مثال عددي را نمایشمی دهد. نتایج حل حاکی از آن است که با افزایش ظرفیتتسهیلات (آستانه تحمل مشتریان)، درصد تقاضاي ازدست رفته کاهش می یابد. علاوه بر این، افزایش نرخخدمت دهی در تسهیلات نیز به کاهش درصد تقاضاي ازدست رفته کمک می کند.

جدول 2: نتایج تحلیل حساسیت روي ظرفیت تسهیلات
K شماره تسهیلات تابع هدف
1 2 , 7 0.200
2 1 , 10 0.055
3 3 , 5 0.016
4 2 , 10 0.005
5 2 , 10 0.001

جدول 3: نتایج تحلیل حساسیت بر روي نرخ دمت دهی
 شماره تسهیلات تابع هدف
0.8 2 , 10 0.041
0.9 3 , 5 0.025
1 3 , 5 0.016
1.1 2 , 10 0.011
1.2 2 , 10 0.007

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

مراجع
براي استقرار بهینه تعداد بیشتري از تسهیلات می توانـد درتحقیقات بعدي مـدنظر قـرار گیـرد. در ایـن مقالـه شـکلخاصی از بی حوصلگی مشتریان (انصـراف قبـل از ورود بـهدلیـل مش اهده جمعیت ی ب یش از آس تانه تحم ل ) م وردمطالعـه قـرار گرفـت. در بسـیاري از سیسـتم هـاي دنیـايواقعی، مشتریان با توجه بـه تعـداد نفـرات موجـود در هـرتسهیل در مورد ورود یا انصراف، تصمیم گیري می کنند. در واقع با افزایش تعـداد نفـرات منتظـر در تسـهیل، احتمـالورود فرد جدید به آن تسهیل کـاهش مـی یابـد . از سـویی،افرادي که در صف منتظر هستند، ممکن است قبل از آنکه نوبت آنها برسد، از دریافت خدمت منصرف شده و سیسـتمرا تــرك کننــد (انصــراف بعــد از ورود). در نظــر گــرفتن گونه هاي دیگر انصـراف مشـتریان و حـالات ترکیبـی ایـندسته ها، می تواند زمینـه تحقیقـاتی مناسـبی بـراي ادامـهمطالعات باشد.
Larson, R. C. (1974). “A hypercube queuing model for facility location and redistricting in urban emergency services.” Computers and Operations Research., 1, PP. 67–95.
Larson, R. C. (1975). “Approximating the performance of urban emergency service systems.” Operations Research., PP. 845–868.
Wang, Q., Batta, R. and Rump, C. (2002). “Algorithms for a facility location problems with stochastic customer demand and immobile servers.” Annals of Operations Research., 111, PP. 17–34.
Berman, O. and Drezner, Z. (2007). “The multiple server location problem.” Journal of the Operational Research Society., 58:91–9.
Pasandideh, S. H. R. and Akhavan Niaki, S. T. (2010). “Genetic application in a facility location problem with random demand within queuing framework.” J Intell Manuf., DOI 10.1007/s10845-010-0416-1
Chambari, A. H., Rahmati, S. H. Hajipoor, V. and Karimi, A. (2011). “A Bi-Objective Model for LocationAllocation Problem within Queuing Framework.” World Academy of Science, Engineering and Technology., .87
Berman, O., Huang. R . Kim, S. and Menezes. (2007). “Locating capacitated facilities to maximize captured demand.” IIE Transactions., 39, PP. 1015–.9201
Hamaguch, T. and Nakade, K. (2010). “Optimal Location of Facilities on a Network in Which Each Facility is Operating as an M/G/1 Queue.” J. Service Science & Management., 3, 287-.792
Moghadas, F. M. and Taghizadeh, K. (2011). “Maximal covering location-allocation problem with M/M/k queuing system and side constraints.” Iranian Journal of Operations Research., 2(2), 1-.61
Aboolian, R., Berman, O. and Drezner, Z. (2009). “The multiple server center location problem.” Journal of Operations Research., 167:337–.25
De Camargo, R. S. and Miranda, G. (2012). Single allocation hub location problem under congestion:
Network owner and user perspectives. Expert Systems with Applications, 39(3), 3385-.1933
Konur, D. and Geunes, J. (2012). Competitive multi-facility location games with non-identical firms and convex traffic congestion costs. Transportation Research Part E: Logistics and Transportation Review, 48(1), 373-385.
Jouzdani, J., Sadjadi, S. J. and Fathian, M. (2013). Dynamic dairy facility location and supply chain planning under traffic congestion and demand uncertainty: A case study of Tehran. Applied Mathematical Modelling, 37(18), 8467-8483.
Marianov, V. and ReVelle, C. (1996). “The queueing maximal availability location problem: a model for the siting of emergency vehicles.” European Journal of Operational Research., 93:110–20.
Atkinson, J., Kovalenko, I. Kuznetsov, N. and Mykhalevych,K. (2008). “A hypercube queueing loss model with customer-dependent service rates.” European Journal of Operational Research., 191 (1), ISSN 0377-
2217, PP. 223 – 239.
واژه هاي انگلیسی به ترتیب استفاده در متن
1 – Web Proxy 2 – Congestion
– p median
– c center
– Set Covering
– Proximity Rule
– Gravity Rule
Genetic Algorithm
Simulated Annealing
Tabu Search
Hub Location Problem
Competitive Facility Location
Benders Decomposition
Greedy
Steady State
Hypercube Queuing Model



قیمت: تومان


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