مکانیابی تسهیلات: برخی کاربردهای خاص (بخش سوم)

مقدمه

در این بخش، برخی کاربردهای خاص مسئله مکانیابی تسهیلات (که در ادبیات این حوزه در زمره پرکاربردترین مسائل کاربردی قرار می گیرند) را مختصرا معرفی شده و مدل پایه ای هر یک از آن ها را ارائه می نماییم. این شش کاربرد عبارتند از:

• مسئله مکانیابی انبار (Warehouse facility location problem)
• مسئله مکانیابی هاب (Hub location problem)
• مسئله مکانیابی اورژانس (Emergency facility location)
• مسئله مکانیابی تسهیلات ناخوشایند (Undesirable facility location)
• مسئله مکانیابی گردشی (مکانیابی- مسیریابی) ( Location-routing problem)
• مسئله مکانیابی تسهیلات سلسله مراتبی (Hierarchical facility location)

مسئله مکانیابی انبار

مدل مکانیابی انبار در ابتدا توسط Kuehen و Hamburger در سال ۱۹۶۳ بررسی شد. ایشان از روش های ابتکاری برای حل این مدل استفاده کردند. Efroymson و Ray در سال ۱۹۶۶ و پس از آن Khumawala در سال ۱۹۷۸ الگوریتم های شاخه و کران را برای حل این مدل مد نظر قرار دادند.

مسأله مکانیابی انبار یکی از انواع مختلف مسایل مکانیابی تخصیص است که هدف آن کمینه کردن کل هزینه در هر دوره زمانی با استقرار انبارها در نقاط کاندید و تخصیص مشتریان به انبارها است. با توجه به مدل های ریاضی متنوع از این مسئله در اینجا مدلی ساده از مکانیابی انبار را ارائه می نماییم که بر فرضیات زیر استوار است.

فرضیات مسئله

• مکانیابی به صورت گسسته انجام می گیرد. (انتخاب مکان از بین مجموعه ای از نقاط منفصل)
• ظرفیت مراکز، یکسان و محدود فرض می شود.
• با افزایش اندازه محموله، هزینه انتقال به صورت خطی افزایش می یابد.

پارامترهای مدل

• (i) : اندیس مربوط به مشتریان
• (j) : اندیس مربوط به مکان های کاندید
• (f_j) : هزینه استقرار یک انبار در مکان (j)، (j = 1,2,….p)
• (r_j) : تقاضای مشتری (i) در هر دوره زمانی، (i = 1,2,…,m)
• (p) : تعداد مکان های کاندید شده
• (m) : تعداد مشتریان
• (c_ij) : هزینه حمل و نقل کل تقاضای مشتری (i) از مکان (j) باید توجه داشت که معمولا (p<m) است.

متغیرهای تصمیم

• (y_j): برابر با ۱ (در صورت انتخاب مکان j برای احداث مرکز جدید) و برابر صفر (در غیر اینصورت)
• (x_ij) : کسری از تقاضای مشتری (i) که از مکان (j) تامین می شود.

مدل ریاضی

تابع هدف سعی در کمینه سازی مجموع هزینه های استقرار و تامین تقاضا (حمل و نقل) دارد. محدودیت اول بیان می کند که تقاضای هر مشتری حتما برآورده خواهد شد و حداکثر مقدار هر یک از x_ij ها برابر ۱ است. محدودیت دوم بیان می کند که تنها در صورتی که به مکان j انباری اختصاص یافته باشد می توان از آن انبار به مشتری iام خدمات ارائه داد. در واقع در این حالت است که می توان مشتری را به آن انبار تخصیص داد.

مسئله مکانیابی هاب

هاب ها، مراکزی هستند که با ایجاد آن ها میانگین هزینه حمل و نقل و زمان تحویل کاهش می یابد. این مراکز در شبکه های هوایی و شبکه های حمل و نقلی که بارهای مختلف را ادغام و سپس به مقصد ارسال می کنند، کاربرد دارند. در این مسایل ابتدا باید مراکزی را به عنوان قطب تعیین نمود و سپس هر یک از مراکز باقیمانده را به یکی از قطب ها تخصیص داد. همچنین برای رسیدن از یک مرکز به مرکز دیگر حتما باید حداقل از یک قطب گذشت. محققان مدل مسئله مکانیابی هاب ها را در صنایع مختلف به صورت کاربردی استفاده کرده اند. به عنوان مثالToh و همکارانش در سال ۱۹۸۵، Aykin در سال ۱۹۹۴، Jaillet و همکارانش در سال ۱۹۹۶، Bania در سال ۱۹۹۲ و ۱۹۹۸، Sasaki در سال ۱۹۹۹، Kouliavtsev در سال ۱۹۹۹ و Martin و Roman در سال ۲۰۰۳ این مدل را در خطوط هوایی و فرودگاه ها استفاده نمودند. Cambell و همکارانش نیز در سال ۲۰۰۲ از این مدل در انبارهای زنجیره ای زنجیره تامین استفاده کردند. Donو همکارانش در سال ۱۹۹۵، Lumsden و همکارانش در سال ۱۹۹۹، Baird در سال ۲۰۰۶، Labbé و همکارانش در سال ۲۰۰۵ وAversa و همکارانش نیز در سال ۲۰۰۵ از این مدل در صنعت حمل و نقل و باربری استفاده کردند.

پارامترهای مدل

• (α): فاکتور تخفیف برای حمل و نقل بین هاب ها
• (h_ij): مقدار جریان بین مکان های (i) و (j)
• (c_ij): هزینه حمل و نقل هر واحد بین مکان های (i) و (j)

متغیرهای تصمیم

• (x_j): برابر با ۱ (در صورت انتخاب مکان j برای استقرار هاب) و برابر صفر (در غیر اینصورت)
• (y_ij) : برابر با ۱ (اگر تقاضای نقطه i از هاب مستقر در مکان j تامین شود) و برابر صفر (در غیر اینصورت)

مدل ریاضی

تابع هدف مجموع (۱) هزینه حمل و نقل کالا از مکان های غیرهاب به مکان هایی که گره ها به آن تخصیص داده شده اند، (۲) هزینه حمل و نقل کالا از قطب نهایی تا مقصد و (۳) هزینه حمل و نقل بین قطب ها را کمینه می کند. محدودیت اول تضمین می کند تعداد مراکزی که به عنوان قطب انتخاب می شوند، برابر با P است. محدودیت دوم، بیان گر این است که هر نقطه تقاضا دقیقا به یک قطب تخصیص می یابد. محدودیت سوم، هر نقطه تقاضا را تنها به مراکزی که به عنوان قطب انتخاب شده اند، تخصیص می دهد. محدودیت های چهارم و پنجم نیز محدودیت های دو دویی هستند.

مسئله مکانیابی اورژانس

در اینگونه مسائل به سوالاتی نظیر اینکه در یک مکان جغرافیایی خاص چه تعداد آمبولانس نیاز است، این آمبولانس ها کجا باید مستقر شوند تا از خدمت دهی قابل اطمینان به بیماران مطمئن شویم، ایستگاه های آتش نشانی کجای یک شهر باید مستقر شوند تا در زمان قابل قبولی حریق را اطفا و جان مردم را نجات دهند و … بایستی پاسخ داده شود.

یک معیار برای قضاوت در مورد کارایی خدمات اورژانس، سرعت عکس العمل در زمانی است که یک تماس اورژانس برقرار می شود. معیار دیگر توانایی پرسنل در رویارویی موثر با موقعیت اورژانس در زمان حاضر شدن در محل حادثه است. لازم به ذکر است منظور از خدمات اورژانس، تنها اورژانس پزشکی نیست. بلکه هر نوع خدمات اضطراری را که حتما باید در مدت زمان کوتاه و معینی به متقاضی آن داده شود، در بر می گیرد. از جمله این خدمات می توان به آتش نشانی، امداد جاده ای، خدمت دهی به حوادث آب و برق، اورژانس پزشکی و … اشاره کرد.

از نکات قابل توجه در انتخاب مراکز تسهیلات اورژانسی (مثل مرکز ذخایر دارویی یا مکان های استقرار موقت) پوشش دهی مراکز تقاضا می باشد. یک پوشش دهی مناسب از مراکز تقاضا با تسهیلات می تواند ارائه خدمات درمانی و اورژانسی صحیح به افراد را تضمین کند. از این رو تلفات در موارد اضطراری را حداقل می سازد. مدل های ریاضی متفاوتی برای مکانیابی تسهیلات اورژانسی وجود دارد که در ادامه مدل ریاضی که بر اساس پوشش مجموعه ها می باشد ارائه می شود.

پارامترهای مدل

• (j): مجموعه مکان های مطلوب مراکز اورژانس (نقاط کاندید)
• (i): مجموعه نقاط تقاضا
• (t_ji): کوتاهترین زمان از مکان (j) (وسیله بالقوه) تا نقطه تقاضای (i)
• (S): زمان یا مسافت استاندارد برای خدمات دهی و پوشش متقاضیان (حداکثر زمان یا مسافت قابل قبول)
• N: مجموعه مکان ها یا نقاط کاندیدایی که در فاصله زمانی آن ها از نقطه تقاضای (i)، از زمان استاندارد (S) بیشتر نیست.

متغیرهای تصمیم

• (x_j): برابر با ۱ (در صورت استقرار یک مرکز در مکان j) و برابر صفر (در غیر اینصورت)

مدل ریاضی

هدف این مدل، کمینه کردن تعداد مراکز مورد نیاز است. محدودیت ها بیان می کنند که تقاضای هر مشتری باید توسط حداقل یک مرکز که در فاصله یا زمان استاندارد قرار دارد، پوشش داده شود.

مسئله مکانیابی تسهیلات ناخوشایند

به دلایل امنیتی، بهداشتی و یا رفاه افراد، برخی تسهیلات خوشایند نبوده و مدل ساز سعی دارد این تسهیلات را تا حد ممکن از مراکز تقاضا دور سازد. به عنوان یک مثال از این دسته مسائل، می توان به محل دفن زباله های شهری اشاره نمود. نکته جالب توجه در این دسته مسائل آنجاست که مراکز تقاضا خود تولیدکنندگان زباله بوده و در عین حال به شدت از قرار داشتن تسهیلات مرتبط با این موضوع در نزدیکی خود گریزانند. به دلیل هزینه بالای احداث این تسهیلات از یک سو و هزینه حمل بالای مواد ناخوشایند تا فواصل دور، تصمیم گیرنده می بایست به حل یک مسئله دوگانه (دور کردن از محل سکونت افراد و کمینه سازی هزینه حمل و نقل) بپردازد. این در حالی است که به دلایل امنیتی و همچنین خطرات ناشی از حمل مواد خطرناک تولید شده در این مراکز، مسیریابی حمل این مواد نیز اهمیت بسیار ویژه ای در مسائل تسهیلات ناخوشایند می یابد که در سال های اخیر به شدت مورد توجه متخصصین قرار گرفته است. مسأله مکانیابی تسهیلات ناخوشایند برای اولین بار توسط Goldman و Dearing در سال ۱۹۷۵ مطرح شد و اولین راه حل آن در سال ۱۹۷۸ توسط Church و Garfinnkel ارائه شد. همچنین Ting در سال ۱۹۸۴ الگوریتمی جهت مسئله MaxiSum بر یک درخت توسعه داد که مسئله مکانیابی تسهیلات ناخوشایند را در زمان کوتاهتری حل می نمود. Melachrinoudis و Smith نیز در سال ۱۹۹۵ الگوریتمی را توسعه دادند که با وجود m یال و n گره به عنوان تسهیلات موجود و با فرض فواصل اقلیدسی در یک فضا جواب مسئله مکانیابی تسهیلات ناخوشایند را در مدت زمان کوتاهتری محاسبه می نمود. اما این پایان راه مسائل مکانیابی تسهیلات ناخوشایند نبود و انواع این مسأله با فرضیات گوناگون و در سال های آتی نیز مورد توجه محققان قرار گرفته است.

پارامترهای مدل

• (h_i): بیانگر میزان تقاضای نقطه (i) است.
• (d_ij): نمایانگر فاصله بین نقطه تقاضای (i) و مکان کاندید (j) است.
• (p): تعداد تسهیلاتی است که باید مستقر گردند.

متغیرهای تصمیم

• (x_j): برابر با ۱ (چنانچه تسهیل در نقطه j مستقر شود) و برابر صفر (در غیر اینصورت)
• (y_ij) : برابر با ۱ (چنانچه تقاضای نقطه i از تسهیل مستقر در نقطه j تامین شود) و برابر صفر (در غیر اینصورت)

مدل ریاضی

تابع هدف، مجموع وزنی تقاضا و فاصله را کمینه می سازد. محدودیت اول بیان می دارد که تقاضای کلیه نقاط تقاضا باید توسط یک تسهیل برآورده شود. محدودیت دوم تعداد کل تسهیلات قابل استقرار را برابر P در نظر می گیرد. محدودیت سوم بیان می دارد که زمانی تقاضای مشتری i از مکان j تامین می شود که تسهیل مورد نظر در مکان j مستقر شده باشد. محدودیت های چهارم و پنجم نیز بیانگر دودویی بودن متغیرهای x_j و y_ij هستند.

مسئله مکانیابی گردشی (مکانیابی-مسیریابی)

مفاهیم پایه ای مسئله مکانیابی- مسیریابی به تحقیقات انجام شده توسط Boventer در سال ۱۹۶۱، Maranzana در سال ۱۹۶۴، Webb در سال ۱۹۶۸، Lawrence و Pengilly در سال ۱۹۶۹، Christofides و Eilon در سال ۱۹۶۹ وHiggins در سال ۱۹۷۲ باز می گردد. اگرچه این تحقیقات اولیه بسیار دورتر از آن است که بتواند پیچیدگی مسئله مکانیابی- مسیریابی را نشان دهد، اما آن ها اولین افرادی هستند که ارتباط نزدیک بین مکانیابی و حمل و نقل را دریافتند. بعدها، Cooper در سال های ۱۹۷۲ و ۱۹۷۶ به مسئله حمل و نقل- مکانیابی، با هدف یافتن مکان بهینه مراکز توزیع و کمینه کردن هزینه حمل و نقل از مراکز توزیع به مقصدها، کلیت بخشید. کار او توسط Tapiero در سال ۱۹۷۱ با در نظر گرفتن مدت زمان حمل و نقل در مدل عمومی حمل و نقل- مکانیابی، اصلاح شد. در هیچ کدام از تحقیقات اشاره شده موضوع تور (Tour) در حمل و نقل شبکه ای در نظر گرفته نشده است، بنابراین این مدل ها نمی توانند درک درستی از مسئله حمل و نقل- مکانیابی را ارائه نمایند. Watson-Gandy در سال ۱۹۷۳ اولین افرادی هستند که مفهوم تور را در مسیریابی وسایل نقلیه برای مسئله حمل و نقل- مکانیابی، در نظر گرفته است. اضافه شدن این فرض در مسئله حمل و نقل- مکانیابی عمومی، موجب پیدایش مسئله مکانیابی- مسیریابی شده است، که مدل سازی این مسئله به مراتب سخت تر از مدل سازی مسئله حمل و نقل- مکانیابی است. با این وجود، شاهد هستیم که توسعه مسئله مکانیابی- مسیریابی با فرضیات صحیح در اواخر دهه ۱۹۷۰ و اوایل دهه ۱۹۸۰ صورت گرفته است. در این مدت محققان دریافتند که حل همزمان دو مسئله مکانیابی و مسیریابی نتایجی به مراتب بهتر از حل جداگانه آن ها ارائه می دهد(Min et al.,1998).

هدف این مسئله تعیین مکان های استقرار و تعیین مجموعه ای از مسیرهای انتقال می باشد به نحوی که مجموع هزینه های مسیریابی و هزینه ثابت احداث مراکز با توجه به محدودیت مسافت حداقل شود. مجموعه مسیرها باید به گونه ای باشند که هر مسیر، هر مشتری را دقیقا یک بار ملاقات کند و طول هر مسیر از حداکثر مسافت مجاز تجاوز نکند.

پارامترهای مدل

• (i): مجموعه مکان های مشتریان
• (j): مجموعه مکان های مراکز کاندید
• (p_j): مجموعه مسیرهای امکان پذیر از مرکز (j)
• (c_jk): هزینه مسیر (k) مربوط به مرکز (j)
• (f_j): هزینه ثابت انتخاب مرکز (j)
• (α): ضریب وزنی (نشان دهنده اهمیت نسبی هزینه های ثابت احداث مراکز به هزینه های مسیریابی است)

متغیرهای تصمیم

• (a_ijk): اگر مشتری (i) در مسیر (k) از مرکز (j) خدمت بگیرد، برابر ۱ و در غیر این صورت ۰ است.
• (x_j): اگر مرکز (j) انتخاب شود، برابر ۱ و در غیر این صورت برابر ۰ است.
• (y_jk): اگر مسیر (k) مربوط به مرکز (j) انتخاب شود، برابر ۱ و در غیر این صورت برابر ۰ است.

مدل ریاضی

تابع هدف، به دنبال کمینه کردن مجموع وزن دار هزینه های احداث مراکز و مسیریابی است. محدودیت اول بیانگر آن است که هر مشتری i، دقیقا توسط یکی از مسیرهای انتخابی خدمت داده می شود. محدودیت دوم بیان می کند که مرکز j وقتی انتخاب می شود که حداقل یک مسیر مثل k از آن مرکز انتخاب شود. محدودیت سوم و چهارم نیز محدودیت صفر و یک بودن متغیرها را تضمین می کنند.

مسئله مکانیابی تسهیلات سلسله مراتبی

مدل های پایه ای که تا کنون بررسی شده اند، اغلب با این پیش فرض در نظر گرفته می شوند که تنها یک نوع تسهیل قرار است مکانیابی شود، در صورتیکه در بسیاری مواقع مدیران قصد مکانیابی تسهیلات مختلفی را دارند که به یک یا چند طریق با هم مرتبط هستند. معمولا تسهیلات بر اساس نوع خدماتی که ارائه می دهند، طبقه بندی می شوند. نمونه هایی از این تسهیلات را می توان در خدمات آموزشی، خدمات بانکی، خدمات پستی، مکانیابی سیستم های توزیع و مکانیابی شبکه راه های اصلی و فرعی مشاهده نمود. به عنوان مثال در خدمات پستی در پایین ترین سطح سرویس دهی، صندوق های پستی هستند که مشتریان می توانند به راحتی نامه های خود را از طریق آن ها پست کنند. در شعبات پستی مشتریان می توانند نامه پست کنند، تمبر بخرند و برخی خدمات پستی محدود دیگر را انجام دهند و در نهایت در شعب مرکزی تمام خدمات پستی انجام می شود در ضمنِ اینکه برخی خدمات پشتیبانی، نظیر طبقه بندی نامه ها برای کل شهر نیز فقط در این شعبات انجام می شود.

بر این اساس در مکانیابی سلسله مراتبی، تسهیلات با توجه به نوع خدماتی که ارائه می دهند طبقه بندی می شوند. علاوه بر این می بایست یک عامل، تسهیلات در طبقات مختلف را با هم مرتبط سازد. این عامل می تواند محدودیت بودجه کل موجود برای تسهیلات باشد و یا ارتباطات واضح دیگری که به عنوان مثال، در خدمات پستی باید مشخص شود که هر شعبه مسئول جمع کردن نامه ها از کدام صندوق های پستی است. باید توجه داشت که مدل ریاضی ارائه شده مربوط به مدل ریاضی پایه ای مکانیابی سلسله مراتبی بر اساس مدل میانه می باشد.

پارامترهای مدل

• (h_ik): تقاضای موجود در نقطه (i) برای سرویس سطح (k)
• (d_ij): فاصله بین نقطه (i) و محل کاندید (j)
• (P_k): تعداد تسهیلات سطح (k) که باید مکانیابی شوند.

متغیرهای تصمیم

• (X_jk): اگر یک تسهیل سطح (k) در محل کاندید (j) قرار گیرد، برابر ۱ و در غیر این صورت برابر ۰ است.
• (Y_ijk): اگر تقاضای موجود در نقطه (i) برای سرویس سطح (k) توسط تسهیلی در محل کاندید (j) برآورده شود، برابر ۱ و در غیر این صورت برابر ۰ است.

مدل ریاضی

در مدل فوق تابع هدف، مجموع تقاضا در فاصله را حداقل می کند. محدودیت اول تضمین می کند که تقاضای مشتری i در تمام سطوح کاملا برآورده شود. محدودیت دوم نشان می دهد که تعداد تسهیل سطح k که باید مکانیابی شود، برابر با P_k است. محدودیت سوم تضمین کننده این مطلب است که زمانی تقاضای مشتری i برای سرویس سطح k می تواند از محل j برآورده شود که یک تسهیل سطح k یا سطح بالاتر در محل j قرار گرفته باشد.

جمع بندی و نتیجه گیری

آنچه که امروزه بسیار حائز اهمیت است، توجه به افزایش قابلیت کاربرد (Applicability) در مدل های مکانیابی تسهیلات است. با تمرکزی که بر روی مقالات مختلف این حوزه صورت گرفت، گرایش به افزایش قابلیت کاربرد مدل های مکانیابی وجود دارد چرا که افزایش در قابلیت کاربرد مدل ها را می توان به عنوان تعبیری از واقعی سازی مدل ها دانست. به عبارت بهتر ایجاد مدل هایی که به واسطه آن ها بتوان پارامترهای بیشتری از دنیای واقعی را مد نظر قرار داد، از اهمیت پژوهشی بالایی برخوردار خواهد بود. اگر مبالغه نکنیم، اهمیت این گونه تحقیقات به مراتب از توسعه ابزارها و روش هایی که با آن ها مسائل ساده شدۀ مکانیابی را توسعه داده و یا آن ها را حل می نماییم بالاتر خواهد بود؛ چرا که واقعی سازی دغدغه گذشته و امروز محققان است. این ادعا را می توان با استناد به برخی از مقالات معتبر در حوزه مکانیابی تسهیلات، نظیر مقاله Melo و همکارانش (Melo et al.,2008)، ثابت نمود.

هر چند بحث فوق را از دیدگاه مکانیابی تسهیلات مد نظر قرار دادیم؛ اما با نگاهی مجدد به استدلال ارائه شده، پر واضح است که واقعی سازی مدل ها در بسیاری از شاخه های علوم مختلف به منظور افزایش قابلیت کاربرد مدل ها، دغدغه پژوهشگران در هر شاخه از علم است. در سال ۱۹۸۴، Banks و Carson روش صحیح مدل سازی را چنین دانسته اند که ابتدا بایستی با مدلی بسیار ساده شروع کرد و به تدریج به کامل کردن و واقعی تر کردن آن پرداخت (Banks&Carson,1984). برای مثال مسئله Weber که در آن هدف یافتن نقطه بهینه استقرار (x*,y*) به گونه ای است که مجموع فواصل اقلیدسی وزنی از این نقطه تا نقاط ثابت و موجود با مختصات (a_i , b_i) مینیمم شود، می باشد؛ امروزه این مسئله شامل مدل های بسیار پیچیده و مبتنی بر ریاضیات و هندسه پیچیده تری می باشد. این مسئله امروزه چنان پیشرفت کرده است که پروفسور Drezner یکی از اساتید صاحب نام در حوزه مکانیابی تسهیلات در سال ۱۹۹۵، فصل اول یکی از دو کتاب معروف خود را به مرور ادبیات در ارتباط با این مسئله اختصاص داده است (Drezner,1995).