بخشی از مقاله
چکیده
یکی از مهم ترین گسترش های مساله مسیریابی وسایل نقلیه، مساله مسیریابی وسایل نقلیه با ناوگان ناهمگن است .در این مساله هدف تعیین مسیرهایی با هزینه کمینه برای یک ناوگان ناهمگن از وسایل نقلیه است که تقاضای مشتریان را برطرف می کند .در این مقاله روش فراابتکاری شیرمورچه برای حل مساله بکار گرفته می شود .در پایان نیز با ارایه نتایج عددی کارایی روش مورد بررسی قرار گرفته می شود.
مقدمه
بی تردید در دنیای امروز توجه به توسعه پایدار و بهرهگیری کارا از منابع، از ضروریات و الزامات هر ساختاری است .محدود بودن منابع و گسترش رو به رشد تقاضا در اغلب صنایع، باعث گردیده که بیشتر سازمانها به دنبال کاهش هزینه و افزایش بهرهوری باشند و این دو را در سیاستهای کلان خود جای داده و تقسیمات سازمانی را مبتنی بر این دو مقوله اخذ نمایند. اکثر سازمانها بر این باورند که اگر چنین اعتقاد و نگرشی نداشته باشند؛ از چرخه رقابت در دنیای امروز خارج خواهند شد و برای آنها هیچ جایگاهی وجود نخواهد داشت.
لازم به ذکر است که بخش حمل و نقل درصد قابل توجهی از تولید ناخالص ملی هر کشور را به خود اختصاص داده و در برخی کشورها این عدد در حدود کل تولید ناخالص ملی است. از طرف دیگر به دلیل استفاده از سوخت فسیلی در سیستم های حمل و نقل و حساس بودن این منابع بحرانی، توجه به مباحث بهرهوری و کاهش هزینه و مصرف از جایگاه خاصی برخوردار است. روشهای متنوعی برای کاهش مصرف سوخت و کاهش هزینه در حملو نقل وجود دارد که یکی از اینها کاهش حجم سفر است. منظور از کاهش حجم سفر، بهینه نمودن حجم سفر است. به عبارت دیگر با حجم کمتری از مسافرت می توان به اهداف قبلی دست یافت و یا با همان حجم قبلی سفر به اهداف بیشتری رسید.
مروری بر مقالات چاپ شده نشان می دهد که این مساله از مسایل روز بوده و در حال حاضر تحقیقات در این زمینه صورت میگیرد که این موضوع بر جذابیت مساله می افزاید. مساله مسیریابی وسایل نقلیه با ناوگان ناهمگن - 1HFVRP - از مسایل مهم در حمل و نقل بوده و می تواند تاثیر بسیاری در کاهش هزینههای حملونقل داشته باشد. در این راستا استفاده از الگوریتمهای فراابتکاری دارای نقش شایانی در توسعه بکارگیری از این مساله به عنوان ابزاری برای برنامهریزی مسیرها و وسایل حمل و نقل دارد.
هر مطالعه و تحقیق ضمن آن که مبتنی بر مطالعات قبلی است، مقدمه و پایه ی مطالعات بعدی نیز می باشد. هر قدر تعداد ارتباط ها و پیوندهای ممکن یک مطالعه با مطالعه پیشین و نظریههای موجود بیشتر باشد، اهمیت و سهم آن مطالعه در بسط دانش آدمی بیشتر خواهد بود. پژوهشگران نیز باید با بررسی تحقیقات پیشین که حول موضوع صورت گرفته است تحقیق جدید را به گونه ای طراحی کند که با مطالعات پیشین ارتباط مستقیم داشته باشد برخی از کارهای انجام شده در این زمینه آورده شده است.
مساله VRP برای اولین بار در سال 1959 توسط دانتزیک و رامسر - Dantzing and Ramset, 1959 - مطرح شد. آنها در پژوهش خود به مسیریابی بهینهی دسته ای از کامیون های حمل بنزین بین پایانه توزیع و تعداد زیادی از پمپ بنزین ها پرداختند و روشی مبنی بر مدل برنامه ریزی خطی برای دست یابی به راهحل نزدیک به بهینه را ارایه دادند. مساله HFVRP اولین بار در سال 1984 توسط گلدن و همکاران - Golden et at, 1984 - مورد بررسی قرار گرفت. آنها در مقاله خود دو روش ابتکاری را توسعه دادند که یکی براساس روش ذخیره سازی که توسط کلارک و رایت در سال - Clarke and Wright, 1964 - 1964 و دیگری بر اساس استفاده از طرح تور بزرگ بود.
علاوه بر این آنها یک فرمول بندی ریاضی برای حلVRP با حجم و هزینه ثابت معرفی کردند و کران های پایینی برای جواب بهینه مساله مورد استفاده معرفی کردند. آن ها سپس چندین روش دقیق را برای مساله2FSMF مورد بحث قرار دادند. تایلارد - Taillard, 1999 - مسالهHFVRP براساس روش تولید ستون حل نمود. تارانتیلیس و کراندویس - Tarantilis and Kiranoudis, 2003 - در سال 2003 دو مساله برنامه ریزی که یکی در رابطه با توزیع غذاهای فاسدشدنی برای یک شرکت لبنی بزرگ و دیگری در مورد توزیع بتن آماده که برای ساخت وساز شرکت به کار میرفت را ارایه کردند و همچنین مساله HFVRP را با استفاده از یک روش پذیرش آستانه ای حل نمودندپرینز - Prins, 2009 - در سال 2009 دو روش ابتکاری که براساس روش های فراابتکاری برای برای حل انواع HFVRP و FSM بود را ارایه کردند.
در سال 20012 تان و همکاران - Tan et at, 20012 - در پژوهشی به بررسی الگوریتم مورچگان برای حل مساله مسیریابی وسایل نقلیه ظرفیتدهی شده با ناوگان ناهمگن پرداختند. آنها رویه تبخیر فرمون توسط مورچه های مصنوعی را برای یافتن جوابها بکار گرفتند. این الگوریتم بر روی مسایل نمونه آزمایش شد و نتایج نشان داد که الگوریتم، جواب هایی با کیفیت بالا و زمان اجرای خوب ارایه میدهد.
مساله HFVRP
مساله HVRP یکی از گسترش های مساله VRP است که در آن باید ناوگانی از وسایل نقلیه مختلف به تعدادی از مشتریان با تقاضای مشخص سرویس دهی کنند .در این مساله وسایل نقلیه از نظر ظرفیت، هزینه ثابت - نگهداری و تامین - و هزینه وابسته - واحد مسافت - با یکدیگر تفاوت دارند که از هر نوع تعداد محدودی وجود دارد .به عبارت دیگر در این مساله چگونگی استفاده بهینه از این ناوگان، برای سرویس دهی به مشتریان، مورد نظر است که سبب بدست آمدن کمترین هزینه می شود .
توجه به این نکته ضروری است که در صنعت حمل و نقل به ندرت از ناوگان همگن که در آن وسایل نقلیه با هم مشابهت کامل دارند، برای ارایه خدمات مختلف به مشتریان استفاده می شود؛ زیرا یک ناوگان معمولا برای یک دوره زمانی طولانی خریداری می شود و صاحبان شرکت های حمل و نقل بطور معمول تمایل دارند که دارای ناوگانی از وسایل نقلیه متفاوت برای فعالیت در زمینه های مختلف باشند.
در پایان برای هر یال یک هزینه Ciju = dijru در نظر گرفته میشود که در آن dij فاصله بین راسهای i و j است و ru هزینه وابسته وسیله نقلیه u برای هر واحد فاصله میباشد. مقدار کالایی که وسیله نقلیه u ام هنگام سفر از گره i به گره j حمل میکند، با yiju نشان داده میشود و هر مسیر با زوج مرتب - R,u - مشخص میشود، که در آن R= - i1,i2'…'L|R| - و i1 =i |R| = 0 و ' {i2 '…' L|R|-1} به عبارت دیگر، هر مسیر یک دور در گراف است که شامل نقطه شروع میباشد و به وسیله نقلیه u اختصاص یافته است.
اگر میزان تقاضای مشتریان از ظرفیت وسیله نقلیه تجاوز نکند، آنگاه مسیر - R,u - شدنی است و هزینه اختصاص یافته به یک مسیر جمع هزینه ثابت وسیله نقلیه متناظر و هزینه یالهای پیموده شده میباشد. مساله HFVRP شامل تعیین مجموعهای از مسیرها و تخصیص آنها به وسایل نقلیه موجود است. در این مساله هدف، کمینه کردن مجموع هزینههای مسیرهای پیموده شده توسط این وسایل نقلیه است، بطوری که شرایط زیر برقرار باشد:
الف - همهی وسایل نقلیه در ابتدای مساله باید در نقطه 0 باشند.
ب - در سرویسدهی به مشتریان تنها از وسایل نقلیه موجود استفاده شود.
ج - تقاضای هر مشتری توسط یک وسیله نقلیه و در یک ملاقات برآورده شود.
د - هیچ کدام از تقاضای مشتریها نباید بیشتر از ظرفیت مجاز برای سرویسدهندهها باشد.
به عبارت دیگر برای هر 0 L n باید حداقل u ای وجود داشته باشد که qi Qu باشد.
و - هیچ سرویسدهنده u ام در طول مسیر مجاز نیست که بیشتر از ظرفیت معین شده Qu بار گذاری کند.
