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

بخشی از مقاله

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

تصمیمات در زنجیره تأمین به سه سطح استراتژیک، تاکتیکی و عملیاتی تقسیمبندی شدهاند که تصمیمات مکان یابی در حیطهی تصمیمات استراتژیک قرار داشته و امکان تغییر در این تصمیمات وجود ندارد و مستلزم هزینه زیادی است اما تصمیمات مسیریابی
جز تصمیمات تاکتیکی هستند و قابلیت ایجاد تغییر در این دسته از تصمیمات وجود دارد . مسائل مکان یابی – مسیریابی نوعی از مسائل بهینه سازی ترکیبی هستند که در این مسائل به طور همزمان به حل مسئله مکانیابی – تخصیص و مسیریابی وسایل نقلیه پرداخته شده است. در این مقاله دسته بندی جامعی روی مسائل مکان یابی – مسیریابی بر اساس ساختار مسئله و روش حل بر روی پژوهشهایی از سال 2003 تا 2014 انجام شده است.

واژگان کلیدی: مکانیابی تسهیﻻت، مسیریابی وسایل نقلیه، روشهای ابتکاری ، فراابتکاری، دقیق

-1 مقدمه

مسئلهی مکانیابی - مسیریابی ترکیبی از تصمیمات در سطوح استراتژیک و تاکتیکی است چون در آن تصمیمات مکانیابی و مسیریابی بطور همزمان انجام میشود. ایدهی ترکیب این دو مسئله به 50 سال قبل برمیگردد، Watson و (1973) Dohrn اولین کسانی بودند که مشتریان را در هنگام یافتن مکان برای مراکز توزیع در نظر گرفتند و Salhi و (1989 ) Rand نیز سودمندی استفاده همزمان این تصمیمات را نشان دادند و بیان کردند که حل این دو مسئله بطور جداگانه منجر به تولید جوابهای غیربهینه1 میشود. ( Watson-Gandy and Dohrn, 1973, Salhi and .(Rand, 1989

اگر تمام مشتریان بطور مستقیم به مراکز عرضه متصل باشند مسئلهی مکانیابی - مسیریابی یک مسئلهی استاندارد مکان یابی است. این مسائل بخشی از مدیریت توزیع هستند و از نظر ریاضیاتی نیز جز مسائل بهینهسازی ترکیبی میباشند. مسئلهی مکانیابی - مسیریابی بصورت مجموعهای از مسائل مکانیابی و مسیریابی و برنامهریزی مکان با در نظر گرفتن جنبههای مسیریابی است .(Perl and Daskin, 1985) دربیشتر مطالعات آکادمیک به دﻻیل زیر از در نظر گرفتن روابط بین دو مبحث مکان یابی و مسیریابی به دﻻیل زیر صرف نظر شده است : (Nagy and Salhi, 2007)

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

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

✓ از نظر مفهومی مسئلهی مکانیابی - مسیریابی از مکانیابی مشکل تر است.

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

در این بخش طبقهبندی روی مسائل مکانیابی - مسیریابی بر پایه فرضیات و ساختار مسئله انجام شده و سپس اجزای این طبقه بندی تشریح گردیده است در جدول (1) این طبقهبندی آورده شده است(.(Nagy and Salhi, 2007, Prodhon and Prins, 2014

1-2 سطوح سلسله مراتب

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

.(Hemmelmayr et al., 2012 , Min et al., 1998) مکانیابی - مسیریابی دو سطحی1 دارای کاربردهای زیادی در مسائل واقعی از قبیل توزیع روزنامه است .(Jacobsen and Madsen, 1980)

2-2 تعداد تسهیﻻت

اگر مسئله یافتن مکان بهینه تنها یک تسهیل یا مرکز توزیع باشد مسئله از نوع تک تسهیلی و اگر یافتن مکان چندین مرکز باشد از نوع چند تسهیلی است.

3-2 ماهیت پارامترها

به علت ماهیت پیچیده و پویای زنجیرهی تأمین عدم قطعیت بر فاز برنامه ریزی زنجیرهی تأمین اثر گذار است و موجب اثرگذاری بر کل کارایی زنجیرهی تأمین میگردد .(Klibi et al., 2010b) در یک زنجیرهی تأمین انواع مختلفی از عدم قطعیتها وجود دارد مواردی از قبیل عدم قطعیت در تقاضا و تأمین که ناشی از کارایی2 و رفتار مشتریان است. از دیگر موارد عدم قطعیت در یک سیستم میتوان به عدم قطعیت در تولید، توزیع، جمعآوری و فرایند بازیافت، زمانهای تحویل و هزینههای تولید اشاره کرد .(Vahdani et al., 2013) تعیین پارامترهای مسئلهی مکانیابی - مسیریابی نیز بطور قطعی غیرمنطقی است چون همواره تحت تأثیر شرایطی قرار میگیرد که قطعیت را از بین می برد از این رو در تعداد زیادی از مطالعات انجام شده به بررسی مسئلهی مکانیابی - مسیریابی احتمالی پرداخته شده است و یک رویکرد دیگر برای مقابله با عدم قطعیت استفاده از پارامترهای فازی برای مسئله است.

در بسیاری از موارد پارامترهایی از قبیل میزان تقاضای مشتریان، میزان عرضه و زمانهای سفر دارای عدم قطعیت هستند که میزان این پارامترها را میتوان از تولید اعداد تصادفی با توزیعی معین بدست آورد. از جمله تکنیکهایی که تا کنون مورد استفاده قرار گرفته است عبارتند از: شبیه سازی3، برنامه ریزی با محدودیت شانسی4 و روش های منابع. 5 یکی دیگر از روشها برای در نظرگرفتن عدم قطعیت استفاده از پارامترهای فازی است. میزان تقاضای مشتریان میتواند بصورت فازی باشد .(Chan et al., 2001, Wei-long and Qing, 2007, Zhou and Liu , 2003) در بعضی موارد نیز میزان تقاضای مشتریان بصورت متغیرهای تصادفی برنولی فرض شدهاند .(Albareda-Sambola et al., 2007) در بعضی نیز میزان تقاضای مشتریان را بصورت فازی در نظرگرفته شده اند ( Cui and Li , 2007, Fazel Zarandi et al., 2013, Golozari et al., 2013, Zare .(Mehrjerdi and Nadizadeh, 2013

4-2 ماهیت زمانهای سفر

پارامتر زمان سفر برای طی مسافت بین دو گره را میتوان بصورت قطعی یا غیر قطعی فرض کرد. در شرایط واقعی مدت زمان ﻻزم برای طی مسافت در یک شبکه همواره با عدم قطعیت همراه است. از این رو در تحقیقات زیادی این پارامتر بصورت غیرقطعی فرض شده است. به عنوان مثال Ghafari-Nasab و همکاران (2013) زمانهای سفر را بصورت احتمالی و Fazel Zarandi و همکاران (2011) نیز زمانهای سفر را بصورت فازی در نظرگرفتهاند از برنامه ریزی با محدودیت شانسی همراه با تئوری اعتبارپذیری1 به منظور مدلسازی استفاده کرده اند. ( Ghaffari-Nasab et al.,

.(2013b, Zarandi et al., 2011

5-2 ظرفیت مراکز توزیع
اگر مراکز تولید یا نگهداری یا همان مراکز توزیع داری محدودیت در میزان تولید یا ظرفیت نگهداری باشند مسئله از نوع ظرفیتدار2 است ( Harks .(et al., 2013 اگر دارای محدودیتی در ظرفیت نباشد از نوع بدون ظرفیت است .(Doong et al., 2007)

6-2 محدودیت زمانی وسایل نقلیه

در صورتی که وسایل نقلیه تنها در بازه زمانی مشخصی در اختیار سیستم باشند وسایل نقلیه دارای محدودیت زمانی خواهند بود در غیراینصورت بصورت تمام وقت در اختیار سیستم خواهند بود و محدودیتی در زمان برای آنها وجود ندارد .(Burks Jr, 2006)
7-2پنجرههای زمانی

چنانچه زمان انجام خدمتدهی به زمانهای خاصی از دورهی برنامه ریزی محدود باشد مسئله دارای پنجرهی زمانی است. Govindan و همکاران (2013) به بررسی و حل مسئلهی مکانیابی – مسیریابی با در نظر گرفتن پنجره زمانی پرداختهاند. بطور کلی دو نوع پنجره زمانی میتوان در نظر گرفت که در پنجره زمانی نرم میتوان با اعمال جریمه از محدودیتها تخطی کرد اما در نوع سخت به هیچ وجه نمیتوان از محدودیتها تخطی کرد. Fazel Zarandi و همکاران (2013) نیز به بررسی مسئلهی LRP3 را با در نظر گرفتن پنجرههای زمانی تحت شرایط عدم قطعیت پرداختند که میزان تقاضای مشتریان و زمانهای سفر را به صورت احتمالی در نظر گرفتند و از روش مدلسازی برنامه ریزی محدود شانسی4 و تئوری اعتبارپذیری5 استفاده کردند و سپس مدل را با الگوریتم ابتکاری تبرید شبیهسازی حل نمودند. .(Fazel Zarandi et al., 2013, Govindan et al., 2013)

8-2 نوع عملیات
در بیشتر مسائل LRP عملیات تنها از نوع تحویل (یا بارگیری) می باشد در حالی که در برخی شامل هر دو عملیات تحویل و بارگیری است که هم شامل تحویل کاﻻ به مشتریان و هم دریافت کاﻻ از مشتریان است از جمله تحقیقات در این زمینه میتوان به Ropke و Pisinger در سال 2006 و Karaogla در سال 2011 اشاره کرد. (Karaoglan et al., 2011, Ropke and Pisinger, 2006)

9-2 نوع مسیر

چنانچه وسیله نقلیه پس از بارگیری از مبدأ و تحویل کاﻻ به مشتریان به مبدأ برگردد مسیر از نوع بسته خواهد بود در این حالت معموﻻً وسایل نقلیه متعلق به شرکت هستند و چنانچه به مبدأ برنگردد مسیر از نوع باز خواهد بود و در این حالت وسایل نقلیه به شرکت متعلق نیستند ( Berger,

.(1997

10-2 مکان مشتریان در شبکه

در صورتی وسایل نقلیه برای خدمت دهی از گرههای معینی که مشتریان در آنها قرار دارند عبور کنند مسئله بصورت مسیریابی گرهها است ولی چنانچه بصورت یافتن یالها برای خدمت دهی به مشتریان باشد از نوع مسیریابی یالها است ( Levy and Bodin, 1989, Hashemi Doulabi
.(and Seifi, 2013

11-2 افق برنامهریزی

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

است Laporte .(Nagy and Salhi, 2007) و (1989) Dejax و Klibi و همکاران (2010) نیز افق برنامه ریزی را بصورت پویا در نظر گرفته اند.

12-2 توابع هدف

مسائل موجود در ادبیات موضوع به دو دسته تک هدفه و یا چندین تابع هدفه تقسیم شدهاند. در مسائل تک هدفه تابع هدف بصورت کمینه کردن هزینها است و در مسائل چند هدفه معموﻻً هدف اولیه کمینه کردن هزینهها و اهداف ثانویه مواردی از قبیل: حداقل کردن اثرات زیست محیطی (Govindan et al., 2013) ، حداقل کردن فاصله سفر اضافی (Ghaffari-Nasab et al., 2013a) ، حداکثر کردن میزان تقاضای پوشش دادهشده (Rath and Gutjahr , 2011) ، حداقل کردن ریسک برای افرادی که در معرض حمل مواد خطرناک هستند، حداقل کردن ریسک برای افرادی که در نزدیکی دفع مواد زائد هستند (Samanlioglu, 2013) ، حداقل کردن زمان اضافی سفر((Perugia et al., 2011 ، بیشینه کردن سطح خدمت (از نظر خدمت رسانی به موقع و یا تعداد مشتریان پوشش یافته) (Hassan-Pour et al., 2009) ، حداقل کردن ریسک ( Alumur and Kara, (2007 و حداقل کردن هزینه سفر، حداقل کردن اثرات مضر زبالهی حیوانات بر افراد جامعه که در مسیر و نزدیکی محل دفع مواد زائد قرار دارند

.(Caballero et al., 2007)

13-2 نوع مرکز توزیع

مراکز توزیع یا تسهیﻻت میتوانند به دو شکل ثابت و متحرک باشند، در اکثر مسائل این مراکز بصورت ثابت فرض شدهاند اما مسائلی وجود دارد که در آنها مراکز توزیع یا تسهیﻻت بصورت متحرک هستند، در این مسائل، مسئله بصورت مکانیابی - مسیریابی یالها میباشد. در اینجا به دو نمونه از تحقیقات انجام شده در این زمینه اشاره شدهاست. در اولین مورد Amaya و همکاران (2007) به بررسی مسئلهی خط کشی1 در جادهها پرداختهاند که در آن وسیلهی نقلیهای که خط کشی انجام میدهد، باید توسط وسیلهی نقلیه دیگری دوباره پر شود. دومین مورد Del Pia و (2006) Filipi به بررسی مسئلهی جمع آوری ضایعات پرداختهاند که کار جمع آوری توسط دو وسیله نقلیه بزرگ و کوچک انجام میشود که وسیله نقلیه بزرگ قابلیت دسترسی به مراکز شهری با خیابانهای باریک را ندارد، وسیلهی نقلیه کوچک ضایعات را جمع آوری کرده و سپس به سمت وسیله نقلیه بزرگتر حمل میکند. (Amaya, 2007, Del Pia and Filipi)

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

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

1-3 روشهای دقیق
به علت ماهیت NP-hard بودن مسئلهی مکان یابی - مسیریابی تعداد کمی از تحقیقات انجام شده با روشهای دقیق حل شدهاند. روشهای حل دقیق تنها در موارد خاصی از مسائل مکان یابی - مسیریابی کاربرد دارند، این روشها بر اساس برنامهریزی ریاضی، معرفی مجدد و آزاد سازی برخی محدودیتها از قبیل حذف زیرتورها2، عدم اتصال دو مرکز توزیع و عدد صحیح بودن پارامترها می باشند .(Nagy and Salhi , 2007) روشهای حل دقیق تنها قابلیت حل مسائل با اندازه کوچک را دارند و نهایتاً قابلیت حل مسئله با 50 مشتری و 5 تا 10 مرکز توزیع را دارند ( Prodhon and .(Prins, 2014 در زیر دسته بندی جامعی بر اساس روشهای حل دقیق ارائه شده است. روشهای حل دقیق به 5 دسته تقسیم بندی می شوند که میتوان مواردی از قبیل جستجوی درخت مستقیم / انشعاب و تحدید، برنامهریزی پویا، برنامه ریزی عددصحیح، برنامه ریزی غیرخطی، آزادسازی و معرفی مجدد محدودیتها را نام برد. تا کنون از روشهای حل دقیق متفاوتی به منظور حل مسائل مکانیابی - مسیریابی استفاده شده است مواردی از قبیل: صفحات برش (Laporte et al., 1983) ، شاخه - برش(Belenguer et al., 2011)3 ، شاخه – برش - هزینه(Contardo et al., 2011) 4 ، شاخه - کران(Laporte et al., 1988) 5 ، صفحات برش(Laporte, 1989) 6 ، بهینه سازی عددی(Drezner, 1982) 7، تئوری گراف8

.(Averbakh and Berman, 2002)

2-3 روشهای ابتکاری

در دههی اخیر در تعداد معدودی از تحقیقات به ارائه روش حل ابتکاری برای مسائل مکانیابی - مسیریابی پرداخته شده است. طبق این طبقهبندی روشهای ابتکاری به سه دسته تقسیم بندی شدهاند: روشهای ترتیبی1، روشها بر اساس خوشه بندی2و روشهای مبتنی بر تکرار. در روشهای ترتیبی ابتدا مسئلهی مکان یابی با هدف حداقل کردن فاصله شعاعی مشتری تا مرکز توزیع و سپس مسئلهی مسیریابی با توجه به مکانهای بدست آمده برای مرکز توزیع حل شده و در این روشها به این دلیل که هیچ بازخوردی از فاز دوم به اولیه وجود ندارد باعث زیربهینه بودن جواب نهایی شده است .(Nagy and Salhi , 2007)

در روشهای مبتنی بر خوشه بندی مشتریان به خوشههایی تقسیم شده که هر خوشه بر اساس یک مرکز توزیع یا مسیر کاندید است و سپس روش حل بر اساس یکی از روشهای زیر ادامه مییابد: الف) مکانیابی یک انبار در هر خوشه و سپس حل مسئلهی مسیریابی برای هر یک از خوشهها ب) حل یک مسئلهی فروشنده دورهگرد برای هر یک از خوشهها و سپس مکانیابی انبارها، در این روشها نیز هیچ بازخوردی بین دو فاز آن وجود ندارد در جدول (2-2) مواردی از این روش آورده شده است. در روشهای مبتنی بر تکرار مسئله به دو زیر مسئله تشکیل دهنده آن تجزیه شده و سپس این زیر مسئلهها بصورت تکراری و پشت سر هم با بازخوانی اطﻻعات بدست آمده از هریک حل میشوند. Wu و همکاران (2002) از ترکیبی از الگوریتمهای جستجوی ممنوع و تبرید شبیه سازی به منظور حل مسئله استفاده کرده اند Salhi و (2009) Nagy از مفهوم "نقطه نهایی"3 استفاده نموده و مسئله را با تعداد معین مراکز توزیع درنظرگرفته اند.