فهرست مطالب
مقدمه
در مقاله های قبلی با پس از آشنایی با مسئله مکانیابی-مسیریابی، انواع این مسائل از منظر پارامترها، متغیرهای تصمیم و روش های حل معرفی گردید و همانطور که در خصوص روش های حل ذکر شد، روش های حل این مسائل در دو دسته کلی الگوریتم های دقیق و الگوریتم های ابتکاری قابل تفکیک می باشند. در این مقاله در ادامه مجموعه مقالات مرتبط با مسئله مکانیابی-مسیریابی، با جزئیات بیشتری از روش های حل دقیق این مسائل بر اساس تقسیم بندی ارائه شده توسط Laporte در سال ۱۹۹۲ و Min و همکاران در سال ۱۹۹۸ آشنا شده و پس از تجزیه و تحلیل و جمع بندی مهمترین مقالات ارائه شده تا سال ۲۰۰۸ ، پیشنهاداتی جهت توسعه این حوزه تحقیقاتی ارائه خواهد شد. پس با ما در «دیمکتب» همراه باشید.
الگوریتم های دقیق جهت حل مسئله مکانیابی-مسیریابی
الگوریتم های جستجوی مستقیم
این الگوریتم بر اساس ایجاد مسیرهای وسایل نقلیه توسط درخت شاخه و کران است که از دو استراتژی زیر پیروی می کند:
- انشعاب بر روی کمان ها: (یک انشعاب معادل است با شامل شدن یا عدم وجود آن کمان) یکی از کاربردهای ابتدایی در این زمینه توسط Christofides و Eilon در سال ۱۹۶۹ مطرح شده است.
- انشعاب بر روی مسیرها: در اینجا انشعاب معادل با یک مسیر شدنی است، الگوریتم ارائه شده Christofides در سال ۱۹۷۶ نمونه ای از این دسته می باشد.
برنامه ریزی پویا
این روش توسط بسیاری از نویسندگان برای حل مسئله مسیریابی وسایل نقلیه به کار گرفته شد. Eilon و همکارانش در سال ۱۹۷۱ یک مدل کلی را در این زمینه ارائه نمودند. اما این مدل ارائه شده به علت تعداد زیاد عبارت ها و متغیرها، دارای کاربرد محدودی است، اگرچه عملکرد برنامه ریزی پویا با تکنیک ساده سازی عبارت ها و متغیرها به طرز قابل ملاحظه ای قابل بهبود است (Christofides et al.,1985).
برنامه ریزی خطی عدد صحیح
الگوریتم های افراز مجموعه
الگوریتم های برنامه ریزی خطی عدد صحیح به عنوان یکی از ابزارهای مفید در حل مسائل مسیریابی وسایل نقلیه به شمار می آیند که در میان آن ها مدل های افراز مجموعه گروه بسیاری از مسائل را تحت پوشش قرار می دهند. Guandt و Balinski در سال ۱۹۶۴ یکی از ابتدایی ترین رویکردها در این زمینه را ارائه کردند. این روش نیز همان موانع مدل برنامه ریزی پویا را دارا می باشد و آن این است که تعداد متغیرهای آن برای مسائل کوچک، بسیار زیاد است. کاربرد موفق این تکنیک توسط Bell و همکارانش در سال ۱۹۸۳ در حل مسائل مسیریابی به کار گرفته شد.
الگوریتم های جریان کالا
مدل های جریان وسایل نقلیه و جریان کالا، دو گروه اساسی از مدل های برنامه ریزی خطی عدد صحیح هستند. مدل های جریان کالا مستقیما بر کمیت محموله های جابجا شده روی هر مسیر و جریان یافته از تسهیل مورد نظر، اشاره دارند. مثال متداول از این مدل، مساله مکانیابی انبار با ظرفیت محدود است (Kuehn&Hamburger,1963).
الگوریتم های جریان وسایل نقلیه
این مدل ها بیشتر در ارتباط با گردش و حرکت وسایل نقلیه بوده و هزینه های مستقیم و محدودیت های جریان کالا را شامل نمی شود. برخی از مسائل مانند مسیریابی وسایل نقلیه با ظرفیت محدود، توسط برخی از محققان با این روش مدل شده اند (Laporte,1986).
برنامه ریزی غیر خطی
این روش حل برای مدل هایی از مسئله مکانیابی- مسیریابی کاربرد دارد که یک یا تعدادی از متغیرهای تصمیم و یا پارامترهای آن احتمالی باشند. این روش حل معمولاً برای مسئله مکانیابی- مسیریابی در حالتی که مقدار تقاضای مشتریان احتمالی می باشد به کار می رود (Sambola et al., 2007).
تجزیه و تحلیل و جمع بندی مهمترین مقالات
مهمترین دستاورد این تحقیق دستیابی به حوزه های تحقیقاتی جدیدی است که در قسمت بعدی نیز به آن اشاره می شود. درست است که تا سال ۲۰۰۸، سه مقاله مروری در این حوزه چاپ شده و در این مقالات نیز به حوزه های تحقیقاتی اشاره شده است، اما با مطالعه مقالات جدیدتر نیز مشاهده شد که همچنان این حوزه ها به عنوان حوزه های تحقیقاتی جدید از طرف محققان معرفی شده اند. در این قسمت نیز بررسی اجمالی را از نظر تقسیم بندی های موجود در مرور ادبیات بر روی ۲۰ مقاله مطالعه شده با استفاده از جداول و اشکال زیر ارائه می نماییم. بررسی های انجام شده نشان داد که حوزه های تحقیقاتی زیر در مسئله مکانیابی- مسیریابی به صورت بسیار محدود مورد توجه محققان قرار گرفته اند، لذا این تحقیقات محدود دریچه ای را به روی انجام تحقیقات گسترده در این زمینه ها فراهم می آورد.
۱- مدل سازی و حل مسئله مکانیابی- مسیریابی در حالت پیوسته.
۲- حل مسئله مکانیابی- مسیریابی در حالتی که تقاضا احتمالی است.
۳- حل مسئله مکانیابی- مسیریابی در حالت چند هدفه.
دسته بندی مقالات مطالعه شده از نظر بعضی از پارامترها، متغیرها و فرضیات مدل
| Fac. capacity | Veh. capacity | Time window | Demand | Year | Article (Authors) | Number | |||
| Uncapa | Cap | Uncap | Cap | Sto | Det | ||||
| * | * | * | 2009 | Ambrosno et al. | 1 | ||||
| * | * | * | 2008 | Schwardt and Fischer | 2 | ||||
| * | * | * | 2008 | Lopes et al. | 3 | ||||
| * | * | * | 2007 | Alumur and Kara | 4 | ||||
| * | * | * | 2007 | Caballero et al. | 5 | ||||
| * | * | * | 2007 | Barreto et al. | 6 | ||||
| * | * | * | 2007 | Glickman and Penn | 7 | ||||
| * | * | * | 2007 | Sambola et al. | 8 | ||||
| * | * | * | 2007 | Nagy and Salhi | 9 | ||||
| * | * | * | 2006 | Prins et al. | 10 | ||||
| * | * | * | 2006 | Lin and Kwok | 11 | ||||
| * | * | * | 2005 | Liu and Lin | 12 | ||||
| * | * | * | 2005 | Melechovsky et al. | 13 | ||||
| * | * | * | 2005 | Sambola et al. | 14 | ||||
| * | * | * | 2003 | Lee et al. | 15 | ||||
| * | * | * | 2003 | Liu and Lee | 16 | ||||
| * | * | * | 2002 | Wu et al. | 17 | ||||
| * | * | * | 2001 | Chan et al. | 18 | ||||
| * | * | * | 1999 | Tuzun and Burke | 19 | ||||
| * | * | * | * | 1998 | Nagy and salhi | 20 |
دسته بندی مقالات مطالعه شده از نظر روش حل مدل
| Exact Alg | NN | Two Phase/Combined/GRASP | SA | TS | Year | Authors | Number |
| * | 2009 | Ambrosno et al. | 1 | ||||
| * | 2008 | Schwardt and Fischer | 2 | ||||
| * | 2008 | Lopes et al. | 3 | ||||
| * | 2007 | Alumur and Kara | 4 | ||||
| * | 2007 | Caballero et al. | 5 | ||||
| * | 2007 | Barreto et al. | 6 | ||||
| * | 2007 | Glickman and Penn | 7 | ||||
| * | 2007 | Sambola et al. | 8 | ||||
| * | 2007 | Nagy and Salhi | 9 | ||||
| * | 2006 | Prins et al. | 10 | ||||
| * | * | 2006 | Lin and Kwok | 11 | |||
| * | 2005 | Liu and Lin | 12 | ||||
| * | 2005 | Melechovsky et al. | 13 | ||||
| * | 2005 | Sambola et al. | 14 | ||||
| * | 2003 | Youngho Lee et al. | 15 | ||||
| * | 2003 | Liu and Lee | 16 | ||||
| * | 2002 | Wu et al. | 17 | ||||
| * | 2001 | Chan et al. | 18 | ||||
| * | 1999 | Tuzun and Burke | 19 | ||||
| * | 1998 | Nagy and salhi | 20 |
روش حل
با توجه به نتایج مناسب و سرعت حل الگوریتم های ابتکاری در مسائل ترکیبی، کاربرد این الگوریتم ها در مسئله مکانیابی- مسیریابی ، که خود جز مسائل ترکیبی است نیز رشد چشمگیری داشته است. همان طور که در شکل زیر می بینیم، ۸۵ درصد مقالات مطالعه شده، که مقالاتی به نسبت جدید و مربوط به سال ۲۰۰۰ تا ۲۰۰۸ می باشند، نیز از الگوریتم های ابتکاری برای حل مدل استفاده کرده اند.
ماهیت تقاضا
معمولاً در دنیای واقعی، تقاضای مشتریان در طول زمان ثابت نمی ماند و امکان تغییر این تقاضا از نظر مقدار و نوع نیاز نیز وجود دارد. درست است که مد نظر قرار دادن تقاضای احتمالی در مسئله مکانیابی- مسیریابی، موجب پیچیده تر شدن این مدل سازی و حل مسئله مکانیابی- مسیریابی می شود اما همین فرض، مدل های موجود را به واقعیت نزدیک تر می کند و در نتیجه محققان می توانند مدلی کارا ارائه نمایند. همان طور که در شکل زیر می بینیم تنها ۱۰ درصد از مقالات مطالعه شده، تقاضای احتمالی را در نظر گرفته اند.
پنجره زمانی
مد نظر قرار دادن بازه زمانی برای رساندن تقاضای مشتریان به عوامل متعددی وابسته است. تمامی این عوامل به صورت پارامترها، متغیرها و حتی هزینه های متفاوت در مدل سازی و تابع هدف مسئله مکانیابی- مسیریابی در نظر گرفته می شود. اگرچه مد نظر قرار دادن بازه زمانی موجب افزایش پیچیدگی مدل و حل آن می شود، اما مدل ها را به واقعیت نزدیک تر می سازد. همان طور که در شکل زیر می بینیم، تنها ۵ درصد از مقالات بازه زمانی را مد نظر قرار داده اند.
اعتبارسنجی
محققان معمولاً برای اعتبارسنجی خود از داده های شبیه سازی شده استفاده می کنند. و یا در صورت امکان مدل خود را در شرایط واقعی پیاده سازی می کنند، که این امر خود بر کارایی مدل ارائه شده دلالت می کند. همان طور که در شکل زیر می بینیم تنها ۲۵ درصد محققان از داده های واقعی استفاده می کنند.
محدودیت ظرفیت تسهیل
اگرچه اضافه نمودن محدودیت ظرفیت برای وسایل نقلیه و مراکز توزیع، موجب سخت تر شدن مدل می شود اما در نظر گرفتن فرض محدودیت ظرفیت کاملاً به شرایط مدل سازی و نظر محقق وابسته می باشد. اشکال زیر توزیع مقالات مرتبط با مسئله مکانیابی- مسیریابی از نظر ظرفیت تسهیل و ظرفیت وسیله نقلیه در خلال سال های ۲۰۰۰ تا ۲۰۰۸ را نشان می دهد.
تعداد و انواع وسایل نقلیه
در مورد شکل زیر نیز که نشان دهنده تعداد و انواع متفاوت وسایل نقلیه می باشد، در واقع موجب اضافه شدن فرضیات و محدودیت هایی در مدل سازی مسئله مکانیابی- مسیریابی می شود، که مد نظر قرار دادن این فرض همگی به نظر محقق وابسته می باشد.
نتیجه گیری
به طور کلی هدف از انجام این فصل شناسایی مرزهای دانش در حوزه مکانیابی – مسیریابی می باشد؛ به گونه ای که بتوان شناخت کاملی از پارامترها، متغیرها و فرضیات موجود از آن حوزه را به دست آورد. مدل سازی های متفاوت از مسئله را شناسایی نمود، الگوریتم های به کار گرفته شده برای حل این مدل ها را شناخت و در نهایت با مطالعه مقالات موجود در زمینه مورد نظر به تحقیقات آتی، که مهمترین هدف انجام این تحقیق است، دست یابیم. پس از مطالعه ادبیات مسئله مکانیابی- مسیریابی و با توجه به مقالات ارائه شده در ژورنال های معتبر، متوجه می شویم که تحقیقات گسترده ای بر روی دو مسئله مکانیابی و مسریابی صورت گرفته است. ولی در مقایسه، هنوز توجه به مسئله ترکیبی مکانیابی – مسیریابی چندان پر رنگ نمی باشد، لذا بیان موضوع و کاربردهایش بجا می باشد.
از سال ۱۹۸۸ تقریباً به مدت ۲۰ سال، ۳ مقاله مرور ادبیات در حوزه مکانیابی- مسیریابی چاپ شده است، که هر ۲ مورد از این مقالات توسط مجله معتبر و شناخته شده [۱]EJOR چاپ شده است. این ۳ مقاله شامل مقاله هایLaporte و همکارانش در سال ۱۹۸۸، Min و همکارانش در سال ۱۹۹۸ و Nagy و Salhi در سال ۲۰۰۷ می باشد.
Laporte و همکارانش در مقاله خود انواع مختلف مدل سازی مسئله مکانیابی- مسیریابی را با فرضیات و محدودیت های متفاوت ارائه کرده اند. Min و همکارانش در انتهای مقاله خود به موضوعات تحقیقاتی زیادی به عنوان تحقیقات آتی اشاره کرده اند. Nagy و Salhi به نوعی مقاله فوق را توسعه داده اند و آن ها نیز در انتهای مقاله خود به حوزه های تحقیقاتی زیادی اشاره کرده اند، که بسیاری از این حوزه ها همانند حوزه های تحقیقاتی اشاره شده در مقاله Min می باشد.
پاورقی ها
[۱] European Journal of Operation Research
بازدیدها: 362
