مسئله حمل و نقل -مکانیابی

مقدمه

به دلیل رشد و توسعه روز افزون صنعت و به منظور بهبود سیستم لجستیک و کاهش هزینه های کل سیستم برای کارخانه ها، شرکت ها و مراکز خدمات رسانی، اهداف متعددی در حوزه مسائل مکانیابی تسهیلات[۱] پدیدار شد و به تبع آن مسائل دیگری مانند مساله مسیر یابی وسائل حمل و نقل[۲]، مساله تخصیص[۳] و مساله حمل و نقل[۴] به وجود آمد، که هر یک از پیچیدگی های خاص خود برخوردارند. مساله حمل و نقل به منظور بهینه سازی الگوی جریان کالا از یک یا چند منبع یا تامین کننده به یک یا چند مقصد یا مشتری و با هدف کمینه سازی هزینه های حمل و نقل و حصول اطمینان از تامین کامل نیاز مشتری ها با توجه به محدودیت در ظرفیت و توانایی تامین کنندگان، معرفی شده است. در طول سال های متمادی نویسندگان و محققین بسیاری به بررسی و معرفی روش های مختلف حل این مسائل از جمله مساله مکانیابی و نیز مساله حمل و نقل، با توجه به شرایط و اهداف متفاوت و مطرح در هر مساله، پرداخته اند.

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

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

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

تعاریف و مفاهیم

مساله حمل و نقل – مکانیابی اولین بار توسط Leon Cooper در سال ۱۹۷۱ مطرح گردید و از آن سال به بعد روش های متفاوتی به منظور حل این مساله ارائه شد. در این نوع مسائل دو هدف بسیار مهم به طور هم زمان در نظر گرفته می شود. هدف اول، جستجوی مقدار بهینه کالا برای انتقال از هر منبع یا تامین کننده به نقطه تقاضا یا مشتری مورد نظر و به عبارت دیگر تعیین میزان تخصیص کالای مورد نیاز هر مشتری از هر منبع است به گونه ای که هزینه های مربوط به حمل و نقل کالاها حداقل گردد. هدف دوم، یافتن مکان بهینه برای استقرار منابع و تسهیلات می باشد. لازم به ذکر است که این دو هدف در یک سطح از اولویت قرار دارند. Cooper مساله حمل و نقل- مکانیابی را همان گونه که در شکل زیر دیده می شود ترکیبی از دو مساله حمل و نقل (Hadley et al.,1962) و مکانیابی- تخصیص (Cooper,1963) می داند (Cooper,1967). وی در مقاله خود در سال ۱۹۷۱ مساله مکانیابی – حمل و نقل را به طور رسمی و با یک ساختار جامع و با جزئیات بیشتر معرفی نموده است.

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

معرفی مدل پایه برای مساله حمل و نقل – مکانیابی

مدلی که در اینجا به عنوان مدل پایه ای معرفی می شود، مدلی است که Cooper در سال ۱۹۷۱ ارائه نموده است. فرضیاتی که در این مقاله مد نظر قرار گرفت عبارتند از (Cooper,1971):

• تعداد n مکان و یا مشتری وجود دارد که مقصد نامیده می شود.
• ابعاد این نقاط (مکان ها) در فضای اقلیدسی به صورت زیر نشان داده می شود.

• مقدار تقاضای هر مشتری یا مقصد، قطعی و معین است.
• فضای حل گسسته است.
• هر منبع دارای ظرفیت محدود است.

هدف یافتن m مکان بهینه برای m منبع یا تسهیل از میان n مکان موجود است. در تابع هدف این مساله ضریبی به شکل βj وجود دارد که به عنوان وزن نیاز هر مشتری معرفی شده است. برای مثال این وزن می تواند تعداد دفعاتی باشد که هر مشتری در هر دوره زمانی سرویس داده می شود. این مساله به دنبال جستجوی مکان بهینه هر تسهیل (x_i,y_i) و نیز مقدار بهینه کالای منتقل شده از منبع i به مشتری j که با نماد w_ij نشان داده می شود به همراه کاهش هزینه های حمل و نقل است. مساله در ساختار یک مدل خطی و به صورت کمینه سازی مجموع هزینه ها با توجه به محدودیت های عرضه و تقاضا، به صورت زیر تعریف می گردد:

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

مروری بر مسائل حمل و نقل- مکانیابی

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

همانگونه که اشاره شد، Leon Cooper برای اولین بار در سال ۱۹۷۱ و در مقاله (Cooper,1971) مساله حمل و نقل – مکانیابی را معرفی نموده و با کمک مدل سازی خطی، مدل ریاضی این مساله را ارائه کرده است. فرضیات مدل به این صورت است که کلیه تقاضای مشتریان که در یک مسیر معین تامین می شود کمتر از ظرفیت وسیله نقلیه مشخص شده می باشد و ظرفیت منابع، نامحدود است. همچنین تقاضا قطعی و معین بوده و فضای حل، گسسته در نظر گرفته شده است.

او ۴ الگوریتم برای حل این مدل معرفی نموده است که شامل ۲ مدل قطعی ساده و Enumeration و ۲ مدل ابتکاری است. همچنین برای اعتبار سنجی مدل ها مثال های عددی زده شده و با این الگوریتم ها حل شده است. نتایج نشان می دهند که این الگوریتم ها دارای دو ضعف اساسی می باشند. نخست این که زمان حل مدل توسط این الگوریتم ها طولانی است و در نهایت این که روش های مذکور برای مسائل با اندازه های بزرگ، از عملکرد مناسبی برخوردار نیستند.

اما Cooper مطالعات خویش را در زمینه مسائل حمل و نقل – مکانیابی رها نکرد. وی در مقاله بعدی خود در سال ۱۹۷۶، روش ابتکاری جدیدی را برای حل مدل مساله حمل و نقل – مکانیابی که در مقاله سال ۱۹۷۱ خود ارائه کرده بود، معرفی نموده است. وی پس از آزمایش الگوریتم مذکور بر روی چندین مساله و مشاهده و تحلیل نتایج به دست آمده از حل آن ها، بیان داشته است که این الگوریتم ابتکاری بسیار کاراتر بوده و از زمان حل بسیار پایین تری نسبت به الگوریتم های ارائه شده در گذشته برخوردار است. هم چنین این الگوریتم ابتکاری جدید بر خلاف الگوریتم های قبلی علاوه بر حل مسائل با اندازه های بزرگ، به خوبی قادر به حل مسائل با اندازه کوچک می باشد. وی برای مطالعات بیش تر و دقیق تر بر روی مسائل حمل و نقل – مکانیابی برای دیگر محققین، پیشنهاد خاصی را ارائه نکرده است.

در پی مطالعات انجام شده، Leblanc در سال ۱۹۷۷ در مقاله ای تحت نظر Cooper فرضیات جدیدی به مساله پایه حمل و نقل – مکانیابی افزوده است. از جمله این که مکان های کاندید را گسسته در نظر گرفته و تقاضای مشتریان را به صورت یک متغیر تصادفی معرفی نموده است. وی یک الگوریتم ابتکاری بسیار ساده را برای حل مدل با هدف مینیمم سازی هزینه های موجودی در حال انتظار و نیز هزینه های کمبود ارائه کرده و در نهایت ۴۲ مساله فرضی را به طور آزمایشی با کمک این الگوریتم حل نموده است. نتایج نشان داده اند که تمام این ۴۲ مساله به جواب بهینه دست یافته اند و الگوریتم ارائه شده از کارایی مناسبی برخوردار است.

پنج سال بعد، Franca و Luna در سال ۱۹۸۲ در مقاله خویش در پی تکمیل مطالعات Leblanc یک الگوریتم ابتکاری با نام GBD[8] معرفی نمودند و توسط آزمایش بر روی ۱۰ مثال عددی نشان دادند که این الگوریتم از کارایی نسبی بهتری برخوردار است.

همچنین Lundqvist در سال ۱۹۷۳ مدلی یکپارچه برای برنامه ریزی استفاده بهینه از زمین و فضای موجود ارائه نموده است. باید توجه نمود که این برنامه ریزی بسیار وابسته به شبکه حمل و نقل و فعالیت های مکانیابی است. وی با کمک برنامه ریزی خطی مدل را ارائه کرده و آن را با الگوریتم ابتکاری جستجوی درختی حل نموده است. در نهایت روش حل را با داده های واقعی در یک منطقه (استکهلم) به صورت پویا اعتبار سنجی نموده است. وی در پایان اشاره نموده که با افزایش دانش در رابطه با فضای این مدل می توان آن را به خوبی ارتقا داد. لازم به ذکر است که این مقاله رابطه مستقیمی با مساله حمل و نقل – مکانیابی ندارد؛ اما از فرضیات موجود در این مساله و مفاهیم آن به خوبی بهره برده است.

OR و Pierskalla نیز در سال ۱۹۷۹ مدلی برای مساله حمل و نقل – مکانیابی مراکز بانک خون و نیز تخصیص بیمارستان ها به این مراکز برای پاسخ به نیاز بیمارستان ها برای دریافت خون ارائه نموده و دو الگوریتم ابتکاری برای حل این مدل معرفی کرده اند. هدف این مقاله مینیمم سازی مجموع هزینه های حمل و نقل و هزینه های سیستم خون رسانی است. فرضیات مساله به این ترتیب است که تعداد بانک های خون ثابت، مکان های کاندید مشخص، تعداد دفعات دریافت خون توسط بیمارستان ها محدود بوده و در نهایت دوره زمانی تحویل به عنوان یک پارامتر مدل به صورت روزانه در نظر گرفته شده است. ایشان الگوریتم های پیشنهادی خویش را با آزمایش بر روی داده های واقعی دریافت شده از منطقه شیکاگو و تمام بیمارستان های آن اعتبار سنجی نموده و به نتایج مطلوبی دست یافته اند.

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

در سال ۱۹۹۷ Marin و Pelegrin الگوریتم انشعاب و تحدیدی را برای حل مساله حمل و نقل – مکانیابی برای p نقطه ترابری ارائه نموده اند که هدف آن کاهش هزینه های حمل و نقل می باشد. در همان سال Nilssen مساله مکانیابی ترتیبی را در حالی که هزینه های حمل و نقل نامتقارن می باشد را توسط روش Hotelling مدل نموده و آن را با یک روش قطعی حل کرده است.

به منظور تکمیل مطالعات انجام شده بر روی مسائل حمل و نقل- مکانیابی در سال ۱۹۹۸ Holmberg مساله مکانیابی تسهیلات غیر ظرفیت دار شده با هزینه های حمل و نقل محدب و غیر خطی را معرفی نموده و پس از مدل سازی مساله به روش برنامه ریزی غیر خطی عدد صحیح ناب، آن را با ۴ الگوریتم قطعی پیشنهادی روش انشعاب و تحدید استاندارد، روش DAA[9]، روش [۱۰]DABB و روش BD[11] و به منظور کاهش مجموع هزینه های حمل و نقل و مکانیابی تسهیلات حل کرده اند.

در سال ۲۰۰۲ دو مقاله با رویکرد فرا ابتکاری به حل مسائل حمل و نقل – مکانیابی پرداخته اند.

در مقاله اول در سال ۲۰۰۲،Chowdhury و همکارانش یک الگوریتم ترکیبی فرا ابتکاری Simulated Annealing با برنامه ریزی خطی سنتی را برای حل نزدیک به بهینه مساله حمل و نقل – مکانیابی در اندازه بزرگ و با فواصل اقلیدسی و به منظور مینیمم سازی هزینه های حمل و نقل معرفی نموده اند. سپس مساله پیشنهادی در مقاله Cooper را که در سال ۱۹۷۱ ارائه شده است با الگوریتم پیشنهادی حل نموده و با روش حل قطعی ارائه شده توسط Cooper مقایسه کرده است.

در مقاله دوم در سال ۲۰۰۲، Udhaya و همکارانش به مقایسه عملکرد دو الگوریتم فرا ابتکاریِ الگوریتم ژنتیک وSimulated Annealing در حل مسائل حمل و نقل – مکانیابی و تخصیص با فواصل اقلیدسی و با هدف مینیمم سازی هزینه های حمل و نقل پرداخته است. سپس مساله مطرح در مقاله Cooper را که در سال ۱۹۷۱ ارائه شده است با الگوریتم پیشنهادی حل نموده و با روش حل قطعی ارائه شده توسط Cooper مقایسه کرده است.

دسته بندی مسائل حمل و نقل – مکانیابی (پارامترها، متغیرها و الگوریتم های حل)

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

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

نتیجه گیری

حجم مطالعات

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

الگوریتم های حل

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

لازم به ذکر است به دلیل استفاده برخی از مقالات از دو روش قطعی و ابتکاری به طور جداگانه مجموع درصدها بیش از یک می باشد.

اعتبارسنجی و داده های تحقیق

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

۱- استفاده از داده های شبیه سازی شده،

۲- به کار گیری مدل برای حل یک مسئله واقعی.

همان طور که در نمودار زیر مشاهده می شود تنها ۱۷ درصد محققان از داده های واقعی استفاده نموده اند و ۸ درصد مقالات فاقد اعتبارسنجی می باشند.

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

زمینه های تحقیقات آتی

همان طور که شرح داده شد، Cooper مسئله حمل و نقل- مکانیابی را با هدف یافتن مکان بهینه مراکز توزیع و کمینه کردن هزینه حمل و نقل از مراکز توزیع به مقصد ها، کلیت بخشید. کار او توسط Tapiero در سال ۱۹۷۱ با در نظر گرفتن مدت زمان حمل و نقل در مدل عمومی حمل و نقل – مکانیابی، اصلاح شد. اما Watson-Gandy در سال ۱۹۷۳ در تحقیقات خویش نشان داد که اهداف مسائل حمل و نقل – مکانیابی نمی توانند نیازهای موجود را به خوبی پاسخ گو باشند. چرا که مسیر، که جز جدایی ناپذیر شبکه های حمل و نقل است در این نوع مسائل در نظر گرفته نمی شود.

مد نظر قرار دادن این فرض در مسئله حمل و نقل- مکانیابی عمومی، موجب پیدایش مسئله مکانیابی – مسیریابی شده است، که مدل سازی این مسئله به مراتب پیچیده تر از مدل سازی مسئله حمل و نقل- مکانیابی است (Min et al.,1998).

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

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

پاورقی ها

• [۱] Facility Location Problems
• [۲] Vehicle Routing Problem
• [۳] Allocation Problem
• [۴] Transportation Problem
• [۵] Transportation-location problem
• [۶] Location-routing problem
• [۷] Allocation-location problem
• [۸] Generalized Benders Decomposition
• [۹] Dual ascent and adjustment
• [۱۰] Dual ascent and branch and bound
• [۱۱] Benders decomposition