با ما در تماس باشید 09351983731|info@dmaktab.ir
>>>مسئله مکانیابی-مسیریابی (بخش سوم): الگوریتم های دقیق و تحقیقات آتی

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

مقدمه

در مقاله های قبلی با پس از آشنایی با مسئله مکانیابی-مسیریابی، انواع این مسائل از منظر پارامترها، متغیرهای تصمیم و روش های حل معرفی گردید و همانطور که در خصوص روش های حل ذکر شد، روش های حل این مسائل در دو دسته کلی الگوریتم های دقیق و الگوریتم های ابتکاری قابل تفکیک می باشند. در این مقاله در ادامه مجموعه مقالات مرتبط با مسئله مکانیابی-مسیریابی، با جزئیات بیشتری از روش های حل دقیق این مسائل بر اساس تقسیم بندی ارائه شده توسط Laporte در سال ۱۹۹۲ و Min و همکاران در سال ۱۹۹۸ آشنا شده و پس از تجزیه و تحلیل و جمع بندی مهمترین مقالات ارائه شده تا سال ۲۰۰۸ ، پیشنهاداتی جهت توسعه این حوزه تحقیقاتی ارائه خواهد شد. پس با ما در «دیمکتب» همراه باشید.

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

الگوریتم های جستجوی مستقیم

این الگوریتم بر اساس ایجاد مسیرهای وسایل نقلیه توسط درخت شاخه و کران است که از دو استراتژی زیر پیروی می کند:

  • انشعاب بر روی کمان ها: (یک انشعاب معادل است با شامل شدن یا عدم وجود آن کمان) یکی از کاربردهای ابتدایی در این زمینه توسط Christofides و Eilon در سال ۱۹۶۹ مطرح شده است.
  • انشعاب بر روی مسیرها: در اینجا انشعاب معادل با یک مسیر شدنی است، الگوریتم ارائه شده Christofides در سال ۱۹۷۶ نمونه ای از این دسته می باشد.

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

این روش توسط بسیاری از نویسندگان برای حل مسئله مسیریابی وسایل نقلیه به کار گرفته شد. Eilon و همکارانش در سال ۱۹۷۱ یک مدل کلی را در این زمینه ارائه نمودند. اما این مدل ارائه شده به علت تعداد زیاد عبارت ها و متغیرها، دارای کاربرد محدودی است، اگرچه عملکرد برنامه ریزی پویا با تکنیک ساده سازی عبارت ها و متغیرها به طرز قابل ملاحظه ای قابل بهبود است (Christofides et al.,1985).

مطالب مشابه  مکانیابی تسهیلات رقابتی (Competitive Facility Location): تصاحب بازار (بخش پنجم)

برنامه ریزی خطی عدد صحیح

الگوریتم های افراز مجموعه

الگوریتم های برنامه ریزی خطی عدد صحیح به عنوان یکی از ابزارهای مفید در حل مسائل مسیریابی وسایل نقلیه به شمار می آیند که در میان آن ها مدل های افراز مجموعه گروه بسیاری از مسائل را تحت پوشش قرار می دهند. Guandt و Balinski در سال ۱۹۶۴ یکی از ابتدایی ترین رویکردها در این زمینه را ارائه کردند. این روش نیز همان موانع مدل برنامه ریزی پویا را دارا می باشد و آن این است که تعداد متغیرهای آن برای مسائل کوچک، بسیار زیاد است. کاربرد موفق این تکنیک توسط Bell و همکارانش در سال ۱۹۸۳ در حل مسائل مسیریابی به کار گرفته شد.

الگوریتم های جریان کالا

مدل های جریان وسایل نقلیه و جریان کالا، دو گروه اساسی از مدل های برنامه ریزی خطی عدد صحیح هستند. مدل های جریان کالا مستقیما بر کمیت محموله های جابجا شده روی هر مسیر و جریان یافته از تسهیل مورد نظر، اشاره دارند. مثال متداول از این مدل، مساله مکانیابی انبار با ظرفیت محدود است (Kuehn&Hamburger,1963).

الگوریتم های جریان وسایل نقلیه

این مدل ها بیشتر در ارتباط با گردش و حرکت وسایل نقلیه بوده و هزینه های مستقیم و محدودیت های جریان کالا را شامل نمی شود. برخی از مسائل مانند مسیریابی وسایل نقلیه با ظرفیت محدود، توسط برخی از محققان با این روش مدل شده اند (Laporte,1986).

برنامه ریزی غیر خطی

این روش حل برای مدل هایی از مسئله مکانیابی- مسیریابی کاربرد دارد که یک یا تعدادی از متغیرهای تصمیم و یا پارامترهای آن احتمالی باشند. این روش حل معمولاً برای مسئله مکانیابی- مسیریابی در حالتی که مقدار تقاضای مشتریان احتمالی می باشد به کار می رود (Sambola et al., 2007).

 

تجزیه و تحلیل و جمع بندی مهمترین مقالات

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

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

۲- حل مسئله مکانیابی- مسیریابی در حالتی که تقاضا احتمالی است.

۳- حل مسئله مکانیابی- مسیریابی در حالت چند هدفه.


دسته بندی مقالات مطالعه شده از نظر بعضی از پارامترها، متغیرها و فرضیات مدل

Fac. capacityVeh. capacityTime windowDemandYearArticle (Authors)Number
UncapaCapUncapCapStoDet
***2009Ambrosno et al.1
***2008Schwardt and Fischer2
***2008Lopes et al.3
***2007Alumur and Kara4
***2007Caballero et al.5
***2007Barreto et al.6
***2007Glickman and Penn7
***2007Sambola et al.8
***2007Nagy and Salhi9
***2006Prins et al.10
***2006Lin and Kwok11
***2005Liu and Lin12
***2005Melechovsky et al.13
***2005Sambola et al.14
***2003Lee et al.15
***2003Liu and Lee16
***2002Wu et al.17
***2001Chan et al.18
***1999Tuzun and Burke19
****1998Nagy and salhi20

مطالب مشابه  مسئله طراحی و چیدمان تسهیلات: روش های حل (بخش پنجم)


دسته بندی مقالات مطالعه شده از نظر روش حل مدل

Exact AlgNNTwo Phase/Combined/GRASPSATSYearAuthorsNumber
*2009Ambrosno et al.1
*2008Schwardt and Fischer2
*2008Lopes et al.3
*2007Alumur and Kara4
*2007Caballero et al.5
*2007Barreto et al.6
*2007Glickman and Penn7
*2007Sambola et al.8
*2007Nagy and Salhi9
*2006Prins et al.10
**2006Lin and Kwok11
*2005Liu and Lin12
*2005Melechovsky et al.13
*2005Sambola et al.14
*2003Youngho Lee et al.15
*2003Liu and Lee16
*2002Wu et al.17
*2001Chan et al.18
*1999Tuzun and Burke19
*1998Nagy and salhi20

مطالب مشابه  مسئله مکانیابی تسهیلات صف بندی شده (بخش چهارم): مدل های مبتنی بر میانه

روش حل

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

توزیع مقالات مرتبط با مسئله مکانیابی- مسیریابی از نظر روش حل (2000 تا 2008)

ماهیت تقاضا

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

توزیع مقالات مرتبط با مسئله مکانیابی- مسیریابی از نظر ماهیت تقاضا (2000 تا 2008)

مطالب مشابه  مکانیابی تسهیلات رقابتی (Competitive Facility Location): تعاریف و پژوهش های اولیه (بخش اول)

پنجره زمانی

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

توزیع مقالات مرتبط با مسئله مکانیابی- مسیریابی از لحاظ مد نظر قرار دادن پنجره زمانی (2000 تا 2008)

اعتبارسنجی

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

توزیع مقالات مرتبط با مسئله مکانیابی- مسیریابی از نظر نوع داده های مدل (2000 تا 2008)

محدودیت ظرفیت تسهیل

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

توزیع مقالات مرتبط با مسئله مکانیابی- مسیریابی از نظر ظرفیت تسهیلات (2000 تا 2008)توزیع مقالات مرتبط با مسئله مکانیابی- مسیریابی از نظر ظرفیت وسایل نقلیه (2000 تا 2008)

تعداد و انواع وسایل نقلیه

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

توزیع مقالات مرتبط با مسئله مکانیابی- مسیریابی از نظر تعداد و انواع متفاوت وسایل نقلیه (2000 تا 2008)

مطالب مشابه  مکانیابی تسهیلات رقابتی (Competitive Facility Location): انواع و نحوه رقابت، تقاضا و رفتار مشتری گرایی (بخش دوم)

نتیجه گیری

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

از سال ۱۹۸۸ تقریباً به مدت ۲۰ سال، ۳ مقاله مرور ادبیات در حوزه مکانیابی- مسیریابی چاپ شده  است، که هر ۲ مورد از این مقالات توسط مجله معتبر و شناخته شده [۱]EJOR چاپ شده  است. این ۳ مقاله شامل مقاله هایLaporte و همکارانش در سال ۱۹۸۸، Min و همکارانش در سال ۱۹۹۸ و Nagy و Salhi در سال ۲۰۰۷ می باشد.

Laporte و همکارانش در مقاله خود انواع مختلف مدل سازی مسئله مکانیابی- مسیریابی را با فرضیات و محدودیت های متفاوت ارائه کرده اند. Min و همکارانش در انتهای مقاله خود به موضوعات تحقیقاتی زیادی به عنوان تحقیقات آتی اشاره کرده اند. Nagy و Salhi به نوعی مقاله فوق را توسعه داده اند و آن ها نیز در انتهای مقاله خود به حوزه های تحقیقاتی زیادی اشاره کرده اند، که بسیاری از این حوزه ها همانند حوزه های تحقیقاتی اشاره شده در مقاله Min می باشد.

پاورقی ها

[۱] European Journal of Operation Research

پرسش یا دیدگاه خود را از این قسمت مطرح بفرمایید

بخش اسلایدینگ بار را میتوانید فعال یا غیر فعال کنید و هر ابزارکی را میتوانید در این قسمت فراخوانی کنید و همچنین می‌توانید در این قسمت از کدهای HTML نیز استفاده کنید.
اسلایدینگ بار دارای 4 ستون هستش که شما میتوانید در 1 ، 2، 3 و یا 4 ستون محتوای خودتون رو قرار بدید. میتوانید رنگ پس زمینه رو تغییر بدید، رنگ جداکننده ستون‌ها و همچنین حالت شیشه‌ای رو فعال کنید، خط بالایی را فعال کنید یا بطوری کلی در موبایل یا PC غیر فعالش کنید. با آوادا هرکاری ممکنه فقط باید بخواهید.

کارهای اخیر

اطلاعات تماس

تهران، خیابان ولیعصر، خیابان مینا، شماره 333

Phone: 8888 9999 - 021

Mobile: 9999 888 - 0912

Fax: 6666 7777 - 021

Web: iranavada.com