مسئله مکانیابی-مسیریابی (بخش اول): معرفی مسئله

مقدمه

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

مفاهیم پایه ای مسئله مکانیابی-مسیریابی

برای توصیف بهتر و جامع تر مسئله مکانیابی- مسیریابی[۱]، در این بخش ابتدا نحوه پیدایش این مسئله را بیان کرده، تعاریف کلیدی موجود برای این مسئله را ارائه کرده و پس از آن به مفاهیم کلی این مسئله و زیر مسائل موجود در آن می پردازیم.

پیدایش مسئله

مفاهیم پایه ای مسئله مکانیابی-مسیریابی به تحقیقات انجام شده توسط Von Boventer در سال ۱۹۶۱، Maranzana در سال ۱۹۶۵، Lawrence و Pengilly در سال ۱۹۶۹، Christofides و Eilon در سال ۱۹۶۹، Higgins در سال ۱۹۷۲ و Webb در سال ۱۹۸۶ بر می گردد. اگرچه تحقیقات اولیه بسیار ساده تر از آن هستند که بتواند پیچیدگی مسئله مکانیابی- مسیریابی را نشان دهد، اما این مقالات اولین مقالاتی بودند که ارتباط نزدیک بین مکانیابی و حمل و نقل را مورد بررسی قرار داده اند. Cooper در سال های ۱۹۷۱ و ۱۹۷۶ به مسئله حمل و نقل- مکانیابی[۲]، با هدف یافتن مکان بهینه مراکز توزیع و کمینه کردن هزینه حمل و نقل از مراکز توزیع به مقصدها، کلیت بخشید. کار او توسط Tapiero در سال ۱۹۷۱ با در نظر گرفتن مدت زمان حمل و نقل در مدل عمومی حمل و نقل-مکانیابی، اصلاح شد. در هیچ کدام از تحقیقات اشاره شده موضوع تور در حمل و نقل شبکه ای در نظر گرفته نشده است، بنابراین این مدل ها نمی توانند درک درستی از مسئله حمل و نقل-مکانیابی را ارائه نمایند.

 Watson-Gandy و Dohrn در سال ۱۹۷۳ اولین افرادی هستند که موضوع تور را در مسیریابی وسایل نقلیه برای مسئله حمل و نقل-مکانیابی، در نظر گرفته اند. اضافه شدن این فرض در مسئله حمل و نقل- مکانیابی عمومی، موجب پیدایش مسئله مکانیابی- مسیریابی شده است، که مدل سازی این مسئله به مراتب پیچیده تر از مدل سازی مسئله حمل و نقل-مکانیابی است. با این وجود، توسعه مسئله مکانیابی- مسیریابی با فرضیات صحیح در اواخر دهه ۱۹۷۰ و اوایل دهه ۱۹۸۰ صورت گرفته است. در این مدت محققان دریافتند که حل همزمان دو مسئله مکانیابی و مسیریابی نتایجی به مراتب بهتر از حل جداگانه آن ها ارائه می دهد (Min et al.,1998).

تعاریف مرتبط

برای مسئله مسیریابی نمی توان تعریفی دقیق ارائه کرد، اما این مسئله را می توان جزئی از تئوری مکانیابی دانست. در واقع مسئله مکانیابی-مسیریابی یک روش برای مدل سازی و حل مسائل مکانیابی است، به گونه ای که مسیرهای بهینه برای حمل و نقل انتخاب شوند. علاوه بر آن در سطوح عملیاتی به تصمیمات پایه ای برای سازماندهی مراکز خدمت رسانی نیاز است که منجر به مسئله مکانیابی-مسیریابی می شود. علاوه بر موارد اشاره شده، مسائل مکانیابی-مسیریابی، به محاسبه مسافت بین مشتریان نیز نیاز دارد. در اکثر کاربردهای عملی، مکان تسهیلات نه تنها بر روی هزینه های استقرار تأثیرگذار است بلکه به طور کامل بر روی هزینه های مسیریابی نیز اثر می گذارد. در این شرایط تصمیم گیری های لازم برای پیدا کردن مکان مناسب مراکز خدمت رسانی جزئی از مسائل چند سطحی هستند، که در واقع به ترکیب دو مسئله مکانیابی مراکز و مسیریابی وسایل نقلیه نیاز است (Sambola,2003).

Burns در سال ۱۹۹۸ در مقاله خود مسئله مکانیابی- مسیریابی را اینگونه تعریف می کند: برنامه ریزی مکانیابی با مد نظر قرار دادن جنبه های برنامه ریزی سفر[۳].

Balakrishman و همکارانش در سال ۱۹۸۷ در مقاله خود مسئله مکانیابی- مسیریابی را این گونه تعریف می کنند: مسئله مکانیابی- مسیریابی، تصمیم گیری های استراتژیک لازم در مورد مکانیابی تسهیلات است[۴].

Sambola در سال ۲۰۰۳ در پایان نامه خود مکانیابی- مسیریابی را این گونه تعریف کرده  است: مسئله مکانیابی- مسیریابی یکی از مهمترین تصمیمات استراتژیک در طراحی سیستم لجستیک مربوط به تعیین مکان تسهیلات می باشد. مکان های مورد نظر برای استقرار تسهیلات باید یکسری از نیازمندی ها مانند دسترس پذیری فیزیکی و اقتصادی و همچنین شرایط خاصی که به کاربرد هر مرکز مستقر شده  وابسته است، مثل محدودیت های دولتی و سیاست های کارخانجات، را برآورده کنند.

Tuzun نیز در سال ۱۹۹۸ در پایان نامه خود مسئله مکانیابی- مسیریابی را این گونه تعریف می کند: یک مجموعه از مراکز مستقر شده و یک مجموعه از مشتریان با تقاضای معین وجود دارند. هر مشتری به یک مرکز تخصیص داده می شود تا تقاضایش فراهم شود. محموله تقاضای مشتریان توسط وسایل نقلیه، حمل می شوند. این وسایل نقلیه از مراکز فرستاده می شوند و در طول مسیر، تقاضای مشتریان را برآورده می سازند. هزینه ثابتی برای استقرار هر مرکز توزیع وجود دارد. هزینه ای متناسب با طول مسیر برای حمل و نقل کالا و هزینه ثابتی جهت تهیه وسایل نقلیه در نظر گرفته می شود. بنابراین مسئله مکانیابی- مسیریابی مسئله ای است که مکان مراکز را مشخص کرده و مسیرهای لازم برای انتقال تقاضای مشتریان از مراکز به آن ها را تعیین کرده، به گونه ای که مجموع هزینه های استقرار و حمل و نقل کمینه شود (Tuzun,1998).

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

کلیاتی در خصوص رویکرد حل مسئله مکانیابی-مسیریابی

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

به هر حال کارایی یک سیستم به فاکتورهای مهم و متفاوت دیگری مانند ساختار و مدیریت ناوگان ها وابسته است. بنابراین علاوه بر مکانیابی تسهیلات، تصمیم گیرندگان معمولاً با انتخاب تعداد و نوع وسایل نقلیه تخصیص یافته به هر مرکز مستقر  شده ای روبه رو می شوند. همچنین این افراد برای انتخاب مسیری که هر وسیله نقلیه باید آن را طی کند و تخصیص مشتریان به مراکز مستقر شده برای تأمین تقاضا، نیز باید تصمیم گیری نمایند. به این خانواده از مسائل معمولاً مسائل مسیریابی وسایل نقلیه[۵] نام می دهند.

از نظر محققان عملیاتی[۶] مسئله مسیریابی و مسئله مکانیابی طی چند دهه اخیر موضوعات تحقیقاتی جذابی هستند و از دیدگاه محققان، این دو حوزه هنوز هم جز حوزه های تحقیقاتی فعال می باشند. که پویایی این مسائل تنها به علت برنامه ریزی ریاضی و مدل سازی های متفاوت از این دو مسئله می باشد و در اغلب موارد این دو مسئله جز مسائل بهینه  سازی ترکیبی[۷] دسته بندی می شوند.

اغلب اوقات، هرگاه هر دو مسئله ای، به عنوان مثال مسئله مکانیابی تسهیلات و مسئله مسیریابی وسایل نقلیه، به همراه هم در یک مسئله تعریف شوند، هر کدام به صورت جداگانه مطالعه، بررسی و حل می شوند. این نوع گرایش حل برای مسئله مکانیابی و مسئله مسیریابی به صورت گام های پی در پی، راهی برای توجیه مشکل بودن حل مسائل ترکیبی می باشد. هر دو مسئله مکانیابی و مسیریابی از نوع NP-Hard هستند، ترکیب این دو مسئله بدون شک مسئله ای را از نوع NP-Hard می سازد، محققانی همچون Karp در سال ۱۹۷۲ و Nagy و Salhi نیز در سال ۲۰۰۷ در مقالات خود به این نکته اشاره نموده اند. به هر حال این موضوع شناخته شده  است که مسیریابی وسایل نقلیه تنها در صورتی که مکان بهینه این مراکز مشخص و ثابت باشند و تنها مشتریان به این مراکز تخصیص داده شوند امکان پذیر است.

با وجود دشواری حل این مسائل تجهیزات محاسباتی قوی که امروزه در دسترس می باشند، امکان حل همزمان مسئله ترکیبی مکانیابی- مسیریابی را در یک بازه زمانی قابل قبول بدون نیاز به تقسیم این مسئله به دو زیر مسئله جدا از هم، فراهم نموده  است. در حقیقت، پس از پیدایش این وسایل محاسباتی قوی، تعریف مسائل ترکیبی رو به افزایش می باشد. با توجه به مرور ادبیات های موجود برای مسئله مکانیابی- مسیریابی ترکیبی، حل این مسئله در ابعاد بزرگ تنها با روش های ابتکاری امکان پذیر می باشد و حتی حل این مسئله در ابعاد متوسط نیز با الگوریتم های قطعی، در یک بازه زمانی قابل قبول، امکان پذیر نمی باشد. تنوع و گوناگونی مسئله مکانیابی- مسیریابی از ۴ منبع سرچشمه می گیرد (Sambola,2003):

• ساختار سیستم
• حدود تصمیم گیری
• نوع داده ها
• نوع افق برنامه ریزی[۸]

دسته بندی کاملی از مسئله مکانیابی- مسیریابی در مقاله Laport که در سال ۱۹۸۸ ارائه شده است موجود می باشد.

ارتباط و جایگاه مسئله مکانیابی-مسیریابی در حوزه مکانیابی

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

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

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

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

• کدام مشتریان به کدام تسهیل اختصاص یابند.
• کدام مشتریان به کدام مسیر تخصیص داده شوند.
• به چه ترتیبی مشتریان در هر مسیر سرویس دهی شوند.

نحوه خدمت رسانی به مشتریان با توجه به نحوه استقرار تسهیل

نحوه خدمت رسانی به مشتریان با توجه به نحوه استقرار تسهیلات به دو دسته کلی تقسیم می شوند:

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

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

مدل ریاضی مسئله مکانیابی-مسیریابی

با توجه به بررسی های انجام شده، مدل های ریاضی متفاوتی برای این مسئله ارائه شده است. گوناگونی این مدل ها به نظر تصمیم گیرنده، اهداف مورد نظر، فرضیات و پارامترهای متفاوت مسئله بستگی دارد. اکثر محققان از مدل ریاضی Perl و Daskin که در سال ۱۹۸۵ برای مسئله مکانیابی- مسیریابی چند دیپوته[۹] ارائه نموده اند، به عنوان مدل پایه ای مسئله مکانیابی- مسیریابی استفاده می نمایند. در این بخش ما نیز این مدل ریاضی را ارائه می نماییم با این تفاوت که با توجه به فرضیات موجود در مقاله Wu و همکارانش که در سال ۲۰۰۲ ارائه نمودند، به این مدل ریاضی محدودیت حذف زیرتور[۱۰] اضافه شده، دیپوت ها با ظرفیت های متفاوت موجود می باشند و هزینه موجودی در تابع هدف در نظر گرفته نمی شود.

نمایه ها و پارامترها

نمایه ها و پارامترهای مورد استفاده جهت مدل سازی مسئله مکانیابی-مسیریابی به شرح جدول زیر می باشد:

مدل ریاضی

مدل ریاضی مسئله مکانیابی-مسیریابی به شرح ذیل می باشد:

توضیحات تکمیلی مدل

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

پاورقی ها

• [۱] Location Routing
• [۲] Transportation Location
• [۳] Location Planning with Tour planning aspects taken into account (Burns,1998).
• [۴] Location-Routing Problems are essentially strategic decisions concerning facility location (Balakrishnan, 1987).
• [۵] Vehicle Routing Problem (VRP)
• [۶] Operational Researchers
• [۷] Combinatorial Optimization
• [۸] Type of the Planning Horizon
• [۹] Depot
• [۱۰] Sub-Tour