بخشی از مقاله
چکیده
حمل و نقل در سیستمهای اقتصادی تولیدی و خدماتی از جایگاه مهمی برخوردار است و بخش قابل توجهی از تولیدناخالص ملی - GNP - هر کشوری را به خود اختصاص میدهد. به همین جهت محققان نسبت به بهبود مسیرها وحذفسفرهای غیرضروری و یا ایجاد مسیرهای کوتاه جایگزین، اقدام کردهاند.مباحثی مانند فروشنده دورهگرد، مسیریابیوسیله نقلیه - VRP - و غیرهدر همین راستا توسعه یافتهاند. عموماً، در مورد مسیریابی تسهیلات فرض بر این است کهنوعی انحصار در محیط وجود دارد و هیچ گونه توجهی به تاثیر بر مسیریابی مناسب بر رقابت در نظر گرفته نشده است .مسئله مسیریابی وسایط نقلیه جزء مسائل NP-HARD است.
این مسالهدرصدد است تا با مدلهای ریاضی و بهینهسازی به گونهای عملکند که مسافت طی شده، زمان کل سفر، تعداد وسایط نقلیه،جریمههای دیرکرد و در نهایت تابع هزینه حمل و نقل کمینه ودر نهایت رضایت مشتریان حداکثر شود. به علت ساختار بسیار مشکل مسئلهVRPالگوریتمهای دقیق به ندرت برای این مسئله مورد استفاده واقعشده است اماالگوریتمهای ابتکاری و فراابتکاری از اقبالبیشتریبرخوردار بوده است. برای نمونه از الگوریتمهای باکیفیت میتوانبه روش تولید ستون اشاره کرد. که در این تحقیق مورد استفاده قرار گرفته است.روش تولید ستون یک روش حل برنامه ریزی غیر صحیح برای برنامه های کاربردی - با تقاضای زیاد - و گرد کردن به نزدیکترین عدد صحیح باپاسخ رضایت بخش می باشد.
-1 مقدمه
مسئله مسیریابی وسایط نقلیه دارای نقش بسیار مهمی درلجستیک و توزیع کالاست، مدل کلاسیک مسئله مسیریابی وسایط نقلیه با در نظر گرفتن ظرفیت محدود وسایط به وسیله یک گراف که درآن گرهها، مشتریان - - m هستند و یالها مسیر بینمشتریان را نشان میدهند، ارائه شد. در این مدل هر مشتری مقدار مشخصی تقاضا دارد که تمامی این تقاضاها - q - بایستی با ی کوسیله نقلیه حمل شود.
با توجه به مشاهدات واقعی، در بین توزیع کنندگان در محیط رقابتی وجود دارد که لازم است علاوه بر در نظر گرفتن طول مسیر و میزان گنجایش وسایط نقلیه که منجر به کاهش هزینه حمل و نقل میشود، باید زمان رسیدن رقبای دیگر نیز به مقاصد در نظر گرفته شود. اهمیت این موضوع چنان است که واحدهای تولیدی برای به دست آوردنبیشترین نقدینگی و از دست ندادن بازار فروش، مسیریابی وسایط نقلیه را بر اساس وضیعت رقبای دیگر تعیین میکنند.
دنتزیگ و همکاران برای اولین بار مسئله مسیریابی وسایط حمل و نقل را مدل کردند و بر اساس روشهای ریاضی به حل آن پرداختند. در ادامه کلارک و رایت الگوریتم صرفه جویی را برای حل VRPپیشنهاد کردند که مبنای بسیاری از تحقیقات بعدی قرار گرفت همچنین در ادامه توکلی مقدم و همکاران یک مدل ریاضی برای مسئله حمل و نقل وسایط نقلیه بازگشتی - VRPB - را توسعه دادند که به دلیل پیچیدگی مدل، از الگوریتم ممتیک برای حل آن استفاده کردند.
فیشر و لاپورت وهمکاران برای حل مسئله مسیریابی وسایط نقلیه، رویکردهای گوناگونی از روش شاخه و حد - کران - را توسعه دادند. در چند سال اخیر به مسیریابی وسایط نقلیه چند هدفه توجه زیادی شده است، از جمله اهدافی که در این مقالات مورد توجه قرارگرفته، میتوان به موارد میزان کالایی که درهر مسیر جابجا میشود، تعداد مشتریانی که در هر مسیر قرار می گیرند، طول مسیرها و با زمان عبور از مسیر ها اشاره کرد . همچنین راسل به منظور بهبود جوابهای ارائه شده، روش مناسبی برای ایجاد زیر تور و جستجوی محلی ارائه کرد.
جوزیفیس و همکاران به بررسی مسیریابی وسایط نقلیه با هدف کمینه کردن طول مسیر و بالانس کردن مسیرها پرداختند که برای حل مسئله از روشهای فراابتکاری با اپراتورهای سنتی مربوط به مسائل چندهدفه استفاده کردهاند. بریوب و همکاران به بررسی مسائل چند هدفه و بررسی حل آنها به وسیله روش -ε محدودیت پرداختند، آنها در ادامه مسئله فروشنده دوره گرد را با ارائه روشهای فراابتکاری سریع در حالت چند هدفه حل کردند . قصیری و قنادپور یک مسئله مسیریابی وسایط نقلیه - لوکوموتیوها - با پنجره زمانی را در نظر گرفتند که هدف آن کمینه کردن کل هزینه تخصیص لوکوموتیوها با توجه به هزینه مسافت، زمان، هزینه تأخیرها و انتظارهاست.
آنها از یک الگوریتم ژنتیک تلفیقی با معرفی دو اپراتور جدید برای حل مساله مورد نظر استفاده کردند که نتایج مربوطه با نرم افزار Lingo 8 مقایسه شده است. سپهری و حسینی مطلق یک مدل ریاضی جدید، مبتنی بر مسئله فروشنده دوره گرد تعمیم یافته ،ارائه کردند که درآن مسئله مسیریابی بهینه سیستمهای حمل ونقل اقلام و قطعات از یک سیستم گذاشت و برداشت اتوماتیک - AS/RS - برگرفته شده است.
برای حل مسئله مورد نظر از الگوریتم اجتماع مورچگان استفاده شده است که جوابهای به دست آمده با نرم افزار Lingo 8 مورد مقایسه قرار گرفته است. توکلی مقدم و همکاران مسئله وسایط نقلیه را درحالت تقاضای جدا شده در نظر گرفتند، دراین مسئله اجازه داده میشود که تقاضای هر مشتری توسط چند وسیله تامین شود. تابع هدف کمینه مسافت طی شده و حداکثر کردن استفاده از ظرفیت وسایط نقلیه در این تحقیق مورد توجه قرار گرفته است. این روش ازحل کامل مسئله اصلی - MP - اجتناب کرده و به جای آن به حل متناوب - RMP - میپردازدکه به یک زیر مسئله اشاره دارد.
-2 روش مبتنی بر تولید ستون - : - CG 1-2 روش ایجاد ستون:
روش ایجاد ستون روش موثر و کارایی برای مسائلی استکه تعداد متغیرهای تصمیمگیری زیادی در فرمولبندی ریاضی آن به کار گرفته شده است. در این روش، همهی متغیرهای به کارگرفته شده در مسئله در نظر گرفته نمیشوند بلکه به صورت تدریجی متغیرهای ضروری به مسئله اضافه میشوند و میتوان یک جواب شدنی مسئله را بدون داشتن همه متغیرهایش تعیین کرد. شکل زیر یک مسئله برنامه ریزی خطی را نشان می دهد که قسمت هاشور خورده متغیرهایی که برای بدست آوردن جواب بهینه مورد نیاز نمی باشند را نشان می دهد و این متغیرها در حل مسئله می توانند استفاده نشوند و مسئله با تعداد متغیر های کمتری در زمان مناسب تری حل شود.
شکل : 1 ساختار مدل
در این روش، از مسئله اصلی یا مسئله اولیه 1 - MP - یک مسئله اصلی محدود 2 - RMP - که شامل زیر مجموعه هایی از 1 n lمتغیر از متغیرهای مسئله است به دست میآید که در آن بقیه n - l متغیر صفر قرار داده میشوند. در ابتدا RMP شامل این متغیرها و همهی محدودیتهای MP مرتبط با اینمتغیرها، میباشد توجه شود که متغیرهایی که در RMP قرارمیگیرند و این مسئله را تشکیل میدهند باید یک جواب شدنی را برای این مسئله تولید کنند - سپس ستونهای - متغیرهای بعدی با حل یک مسئله بهینه سازی خاص، که مسئله فرعی نامیده میشود، شناسایی و به RMP اضافه میشوند. هدف RMP تعیین مقدار متغیرهای دوگان محدودیتهای مسئله است. با درنظر گرفتن مسئلهی زیر، گامهای روش ایجاد ستون در زیر نشان داده شده است.
2-1-2 گام :2
RMP با روش سیمپلکس یا سیمپلکس اصلاح شده ، حل می شود و جواب بهینه مسئله تعیین و مقادیر متغیرهای تا مشخص می شوند. این جواب همچین برای MP شدنی است زیرا در RMP همه ی محدودیت های MP حفظ شده اند. در این گام قیمتهای سایه تولید می شوند. باید توجه کرد که قیمت سایه میزان تغییر تابع هدف توسط افزایش بردار سمت راست است.در RMP قیمت سایه برای تعریف متغیر ورودی بعدی و بررسی اینکه جواب بدست آمده بهینه است یا نه به کار گرفته میشود.در مسائل بزرگ مقیاس که هزاران متغیر وجود دارد قیمت گذاری همه ی متغیرهای غیر پایه ای کاری بس دشوار و خسته کننده است.در چنین وضعیتی روش ایجاد ستون نقش کلیدی و مهمی بازی میکند. ایده اصلی روش ایجاد ستون آن است که با روشی موثر ستونی را یافته که قیمتی مناسب برای ورود به پایه داشته باشد.
