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

مقدمه

در این بخش حالت های مختلف پارامترها و الگوریتم های به کار رفته را در دسته بندی های جدا از هم ارائه می نماییم که مشابه آن در مقاله Min و همکارانش در سال ۱۹۹۸ و همچنین در مقاله Nagy و Salhi در سال ۲۰۰۷ ارائه شده است موجود می باشد.

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

مسئله مکانیابی- مسیریابی را بر اساس پارامترها و متغیرهای تصمیم می توان به صورت نمودار زیر دسته بندی نمود.

در ادامه مختصرا بخش هایی از نمودار فوق را به همراه نمونه هایی از مقالات موجود در شاخه مربوطه را ارائه می نماییم.

ساختار سلسله مراتبی

ساختار اکثر مسائل مکانیابی- مسیریابی بر این اصل استوار است که تعدادی تسهیل برای خدمت رسانی به مشتریان وجود دارد که ارتباط بین این تسهیلات و مشتری ها تنها از طریق وسایل نقلیه امکان پذیر می باشد. فرض پایه ای در مسئله مکانیابی- مسیریابی این است که هیچ مسیری بین تسهیلات با یکدیگر وجود ندارد. البته برای تمامی مسائل این حوزه این فرض برقرار نمی باشد. ساختار سلسله مراتبی مسئله مکانیابی- مسیریابی به دو صورت تک سطحی و چند سطحی مطرح می باشد. منظور از ساختار سلسله مراتبی یک سطحی این است که تنها یک نوع تسهیل قرار است مستقر شود (مثلاً یک مرکز توزیع) و منظور از ساختار سلسله مراتبی چند سطحی این است که چند نوع تسهیل برای استقرار وجود دارد (مثلاً یک کارخانه تولیدی و یک مرکز توزیع). در سال ۱۹۸۱، Laporte و Nobert و Averbakh و Berman نیز در سال ۱۹۹۴ در مقاله خود مسئله مکانیابی- مسیریابی سلسله مراتبی یک سطحی را استفاده نمودند.

بازه زمانی

منظور از بازه زمانی، مدت زمانی است که در آن فاصله و محدوده زمانی می توان به مشتری خدمت رسانی نمود. Lin و Kwok در سال ۲۰۰۶ و Nagy و Salhi در سال ۱۹۹۸ در مقاله خود بازه زمانی را برای رساندن کالا و خدمات به مشتریان مد نظر قرار دادند.

نوع داده ورودی

داده های ورودی یک مسئله می تواند بر اساس واقعیت بوده و یا از داده های فرضی و شبیه سازی شده استفاده شود. از دیدگاه دیگر می توان داده ها را به دو دسته احتمالی و قطعی تقسیم نمود. به گونه ای که در مسئله مکانیابی- مسیریابی معمولأ داده احتمالی مربوط به تقاضای احتمالی مشتریان می باشد. در مقاله Laporte و Nobert که در سال ۱۹۸۱ ارائه شده است از داده های فرضی و شبیه سازی شده استفاده شده است. همچنین Sambola و همکارانش در سال ۲۰۰۷ و Chan و همکارانش نیز در سال ۲۰۰۱ در مقاله خود تقاضای مشتریان را به صورت احتمالی در نظر گرفته اند.

دوره برنامه ریزی

برنامه ریزی مسئله مکانیابی- مسیریابی می تواند به صورت یک دوره ای و یا چند دوره ای طراحی شود. مسائل با برنامه ریزی تک دوره ای به عنوان مسائل استاتیک و مسائل با برنامه ریزی چند دوره ای به عنوان مسائل دینامیک معرفی می شوند که اکثر مقالات ارائه شده در این حوزه معمولاً در زمینه استاتیک می باشند. Laporte و Dejax در سال ۱۹۸۹ در مقاله خود مسئله مکانیابی- مسیریابی داینامیک را مورد بررسی قرار داده است. Revelle و همکارانش نیز در مقاله خود که در سال ۱۹۹۱ منتشر شده است، مسئله مکانیابی- مسیریابی زباله های خطرناک را به صورت استاتیک مورد بررسی قرار داده است.

تابع هدف

به طور کلی هدف مسئله مکانیابی- مسیریابی کمینه کردن هزینه ها می باشد. هزینه های این مسئله معمولاً شامل هزینه استقرار، هزینه حمل و نقل و به کارگیری وسایل نقلیه می باشد. این مسئله در مواردی که اهداف دیگری برای مسئله مکانیابی- مسیریابی مد نظر قرار می گیرد نیز می تواند به صورت مسئله با اهداف چند گانه مطرح گردد. Caballero و همکارانش در مقاله خود که در سال ۲۰۰۷ منتشر شده است از اهداف چندگانه برای مدل سازی مسئله مکانیابی- مسیریابی استفاده نموده است.

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

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

روش های حل مسئله مکانیابی- مسیریابی را می توان به کمک مطالعه ادبیات این حوزه و با توجه به نمودار زیر ارائه شده، به دو دسته کلی الگوریتم های دقیق و الگوریتم های ابتکاری[۱] تقسیم بندی نمود. با توجه به ترکیبی بودن مسئله مکانیابی- مسیریابی و مشکل بودن حل این نوع مسائل، استفاده از الگوریتم های ابتکاری برای حل اینگونه مسائل متداول است. معمولاً این الگوریتم ها مساله را به اجزایش تقسیم کرده و بجای حل مساله در یک مرحله، آن را در چند مرحله حل می کنند. Laporte در سال ۱۹۸۸ در دو گروه این الگوریتم ها را طبقه بندی نمود.

الگوریتم های LAR[2]

این الگوریتم حل به ترتیب شامل مراحل مکانیابی، تخصیص و مسیریابی است. در برخی از این الگوریتم ها هر سه مرحله مجزا و جداگانه انجام می شود. مانند الگوریتمی که در سال ۱۹۷۳ توسط Watson-Gandy و Dohrn ارائه شد. در صورتی که در برخی دیگر از الگوریتم ها این امر در دو مرحله انجام می گیرد، به این صورت که در مرحله اول مکانیابی و تخصیص و در مرحله دوم مسیریابی انجام می شود. مانند الگوریتم هایی که Or و Pierskalla و همچنین Von Bednar و Strohmeir در سال ۱۹۷۹ ارائه کردند.

الگوریتم های ARL[3]

در این گونه از الگوریتم ها، ابتدا فرض بر این است که در تمامی مناطق کاندید جهت استقرار، تسهیل جدید مستقر شده است. سپس با این فرض، تخصیص و مسیریابی به صورت همزمان انجام می شوند و در مرحله دوم مکانیابی با حذف یک سری از تسهیلات مستقر شده انجام گرفته و تصمیمات قبلی تخصیص و مسیریابی به روز می شود. نمونه ای از این الگوریتم در سال ۱۹۸۰ توسط Jacobsen و Madsen و در سال ۱۹۸۴ توسط Srikar و Srivastava مطرح شد. Laporte در سال ۱۹۸۸ بیان داشت که عموماً این الگوریتم ها برای مسائل با محدودیت های زیاد که در آن ها ایجاد مسیرهای قابل قبول مشکل است، توصیه می شود. البته باید توجه داشت که تمام الگوریتم های هیوریستیک به راحتی در طبقه بندی ارائه شده قرار نمی گیرند. به عنوان مثال الگوریتمی که Nambiar و همکارانش در سال ۱۹۸۱ پیشنهاد کرد، فاقد فاز تخصیص می باشد.

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

همچنین در مقاله مرور ادبیاتی که Nagy و Salhi در سال ۲۰۰۷ ارائه نمودند در یک تقسیم بندی کلی، روش های حل ابتکاری برای مسئله مکانیابی- مسیریابی را به سه دسته روش مبتنی بر خوشه بندی[۴]، روش تکرار[۵]، روش مرتبه ای[۶] تقسیم نمودند. در ادامه هر یک از این روش ها تشریح شده اند.

روش مبتنی بر خوشه بندی

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

• در هر دسته ابتدا مرکز توزیع مکانیابی می شود و سپس مسئله مسیریابی برای آن دسته حل می شود.
• ابتدا برای هر دسته مشتری یک مسئله فروشنده دوره گرد حل می شود و سپس مسئله مکانیابی مراکز در این دسته ها مطرح می گردد.

روش تکرار

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

روش مرتبه ای

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

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

Billionnet و همکارانش در سال ۲۰۰۵ از روش خوشه بندی برای حل مسئله مکانیابی- مسیریابی مقاله خود استفاده نمودند. Sambola و همکارانش نیز در سال ۲۰۰۵ از روش سلسله مراتبی برای حل مدل مقاله خود استفاده نمودند. Salhi و Fraser در سال ۱۹۹۶ از روش حل تکرار شونده برای حل مدل مسئله مکانیابی- مسیریابی استفاده نمودند.

با مطالعه ادبیات این حوزه متوجه می شویم که محققان در دهه اخیر از روش های حل متاهیوریستیک نیز برای حل مسئله مکانیابی- مسیریابی استفاده نمودند. به عنوان مثال Schwardt و Fischer در سال ۲۰۰۸ در مقاله خود از الگوریتم شبکه های عصبی[۷] برای حل مدل مکانیابی- مسیریابی استفاده نمودند. Nagy و Salhi در سال ۲۰۰۷ از الگوریتم جستجوی ممنوع[۸] که یکی از کارا ترین الگوریتم های متاهیوریستیک در حل مسائل ترکیبی می باشد، برای حل مسئله مکانیابی- مسیریابی استفاده نمودند. Wu و همکارانش نیز در سال ۲۰۰۲ از الگوریتم بازپخت شبیه سازی شده[۹] برای حل مسئله مکانیابی- مسیریابی استفاده نمودند. Min و همکارانش در مقاله مرور ادبیاتی که در سال ۱۹۹۸ منتشر کردند، طبقه بندی الگوریتم های دقیق برای حل مسئله مکانیابی- مسیریابی را که در سال ۱۹۹۲ توسط Laporte پیشنهاد شده بود، به صورت زیر دسته بندی نمودند:

• الگوریتم های جستجوی مستقیم[۱۰]
• برنامه ریزی پویا[۱۱]
• برنامه ریزی خطی عدد صحیح[۱۲]
• برنامه ریزی غیر خطی[۱۳]

با بررسی ادبیات موجود این حوزه، مشاهده می شود که کاربرد برنامه ریزی خطی عدد صحیح در مقایسه با الگوریتم های دقیق دیگر بیشتر است. به گونه ای که Laporte در سال ۱۹۸۸ با استفاده از تقسیم بندی Magnanti در سال ۱۹۸۱ الگوریتم های برنامه ریزی خطی عدد صحیح را به صورت زیر بیان نمود:

• الگوریتم های افراز مجموعه[۱۴]
• الگوریتم های جریان کالا[۱۵]
• الگوریتم های جریان وسایل نقلیه[۱۶]

پاورقی ها

• [۱]  از آنجایی که الگوریتم های فراابتکاری فی الذاته نوعی الگوریتم ابتکاری قلمداد می شوند، لذا تمامی این الگوریتم ها به رسم مرور ادبیات های انجام شده در این حوزه در ذیل نام الگوریتم های ابتکاری آورده شده اند.
• [۲] Location-Allocation-Routing
• [۳] Allocation-Routing-Location
• [۴] Clustering Based Methods
• [۵] Iterative Methods
• [۶] Hierarchical Methods
• [۷] Neural Network
• [۸] Tabu Search
• [۹] Simulated Annealing
• [۱۰] Direct Search Algorithms
• [۱۱] Dynamic Programming
• [۱۲] Integer linear Programming
• [۱۳] Non-linear Programming
• [۱۴] Set Partitioning Algorithms
• [۱۵] Commodity Flow Algorithms
• [۱۶] Vehicle Flow Algorithms