بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

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

١- مقدمه
با توجه به اينکه هزينه حمل کالا سهم بسزايي در قيمت نهايي کالا دارد؛ لذا، بهينه سازي سيستم توزيع کالا از اهداف اصلي شرکت هاي توزيع کالا است . شواهد موجود نشان ميدهد که بهينه سازي سيستم هاي خدمت رساني و توزيع کالا در کشورهاي اروپايي و آمريکاي شمالي نقش اساسي در کاهش چشمگير هزينه هاي حمل ونقل در اين کشورها داشته است [١]. مسئله مسيريابي وسيله نقليه (VRP) يکي از مسائل طراحي چند هدفه شبکه حمل و نقل است که هدف آن بهينه سازي فرآيند توزيع کالا يا جابجايي مسافر است . از کاربردهاي مسئله مسيريابي وسيله نقليه در بهينه سازي سيستم توزيع کالا ميتوان به مدل هاي ارائه شده براي توزيع بهينه غذا و مواد آشاميدني [٢]، روزنامه [٣-٤]، محموله هاي پستي [٣]، جمع آوري زباله هاي صنعتي و تجاري [٥-٦] و برنامه ريزي حمل و نقل هوايي بار [٧] اشاره کرد. علاوه بر اين ، امروزه مطالعات حمل ونقلي ، تدريجاً به سمت مديريت سيستم عرضه حمل و نقل و استفاده بهينه از زيرساخت ها به جاي گسترش زيرساخت هاي حمل ونقلي سوق داده شده اند و سرمايه گذاري در ترويج حمل ونقل همگاني و شبه همگاني و همچنين استفاده از سيستم هاي اطلاع رساني به مسافران و حمل ونقل هوشمند، گواه بر اين موضوع است [٨]. در اين راستا، بسياري از شرکت هاي ارائه دهنده خدمات حمل و نقل همگاني و شبه همگاني ٣ از مدل هاي مسيريابي وسيله نقليه براي جابجايي مسافران خود استفاده ميکنند که از آن مي توان به مسيريابي سرويس مدارس [٩-١٠] و انتقال بيماران به بيمارستان ها به صورت Dial-and-Ride [١١-١٢] اشاره کرد. مسئله مسيريابي وسيله نقليه (VRP) بارها مورد مطالعه دانشمندان علوم مختلف قرار گرفته است و افراد مختلفي سعي در حل اين مسئله کلاسيک داشته اند. مقاله دانتزينگ و همکاران (١٩٥٤) [١٣]
اولين مطالعه در ادبيات مسئله مسيريابي وسيله نقليه است که به حل مسئله فروشنده دوره گرد مي پردازد. بعدها براي اولين بار، کلارک و وايت (١٩٦٤) [١٤] روشي ابتکاري براي حل مسئله مسيريابي وسيله نقليه ارائه دادند. VRP در اوايل دهه ١٩٧٠ ميلادي تحت عناويني مانند مسيريابي ناوگان [١٥]، مديريت توزيع [١٦]، طراحي شبکه حمل و نقل [١٧] و مسيريابي وسايل نقليه خدمات عمومي [١٨] مورد بررسي و مطالعه قرار گرفت . مطالعه گُلدن و همکارانش (١٩٧٢) [١٩]، اولين مطالعه اي بود که نام متداول «مسئله مسيريابي وسيله نقليه » را در عنوان خود آورد و بعد از آن ساير مطالعات با اهداف بهينه سازي سيستم توزيع کالا از همين نام استفاده کردند و چنين مسائلي با نام «مسئله مسيريابي وسيله نقليه » معروف گشت . در ادامه تحقيقات در اين زمينه ، در اواخر دهه ١٩٧٠ و اوايل دهه ١٩٨٠ ميلادي ، مفاهيم احتمالي و پنجره هاي زماني به ترتيب توسط گلدن و استوارت (١٩٧٨)
[٢٠] و سالمن (١٩٨٣) [٢١] وارد ادبيات اين مسئله شدند. با پيشرفت رايانه و افزايش قدرت محاسبات آنها و همچنين پيدايش الگوريتم هاي جستجوي فرا ابتکاري ٥، مطالعه در زمينه VRP از اوايل دهه ١٩٩٠ ميلادي به صورت قابل ملاحضه اي گسترش يافت و تاکنون تعداد زيادي مطالعه در اين زمينه صورت گرفته است . لازم به ذکر است که دليل مطالعات بسيار در اين زمينه تنها کاربردي بودن اين مسئله نيست ؛ بلکه VRP مسئله اي بنيادين براي بررسي توانايي الگوريتم هاي بهينه سازي گسسته در پيدا کردن جواب بهينه است . در ادامه در اين مقاله ، ابتدا در بخش ٢، مسئله مسيريابي وسيله نقليه کلاسيک ، تبيين و تشريح مي - گردد. در بخش ٣، انواع توسعه يافته مسئله کلاسيک ارائه و تشريح ميشود. بخش چهارم اين مقاله به بيان روش هاي حل VRP اختصاص دارد. در نهايت در بخش ٥، پس ازجمع بندي ، افق هاي تحقيقاتي براي مطالعات آتي پيشنهاد ميشود.
٢- تعريف مسئله کلاسيک مسيريابي وسيله نقليه
مسئله مسيريابي وسيله نقليه از مهمترين مسائل بهينه سازي ترکيباتي است . هدف اين مسئله ، تعيين مجموعه اي از مسيرها براي خدمت رساني به مشتريان توسط گروهي از وسائل نقليه با کمترين هزينه عملياتي است . اجزاي اصلي VRP ، مشتريان ٦، وسايل نقليه ٧ و دپو٨ هستند. مشتريان ، مجموعه نقاط تقاضا براي دريافت خدمات يا تحويل بار هستندکه توسط گروهي از وسائل نقليه ملاقات ميگردند که اين وسايل نقليه ، سفرشان را از دپو شروع کرده و به مجموعه اي از مشتريان خدمات ميدهند و نهايتاً
به دپو باز ميگردند. مراکز اعزام و بازگشت وسائل نقليه را اصطلاحاً دپو مينامند. در حقيقت ، مسئله مسيريابي وسيله نقليه ، ترکيبي از دو مسئله بهينه سازي ترکيباتي : ١) مسئله فروشنده دوره گرد و ٢) مسئله پرکردن ظرف ٩ است [١]؛ زيرا در VRP، مشتريان را به گونه اي به وسايل نقليه اختصاص مي - دهيم که مجموع تقاضاي مشتريان اختصاص داده شده به هر وسيله نقليه از ظرفيت وسيله نقليه بيشتر نشود و تعداد وسائل نقليه کمينه گردد (مطابق الگوي مسئله پرکردن ظرف ). در ادامه ، پس از تعيين مشتريان يک وسيله نقليه ، تور بهينه هميلتوني از مشتريان آن وسيله نقليه راتعيين مي نماييم به طوري که هزينه کل کمينه گردد( مسئله فروشنده دوره گرد). لازم به ذکر است که تور بهينه هميلتوني ، جواب مسئله فروشنده دوره گرد است که در آن تمامي گره هاي يک گراف کامل توسط يک تور، يک و فقط يک بار ملاقات شده به طوري که مجموع هزينه ها (طول يالهاي تور) کمينه گردد.
مسئله مسيريابي وسيله نقليه کلاسيک ، به صورت گراف تعريف مي گردد که مجموعه رئوس گراف است و راس هاي گراف غير از V0 ، بيانگر مشتري هاي اين مسئله با تقاضاي غير منفي qi هستند. راس V0 ، متناظر با دپوي وسايل نقليه است . همچنين مجموعه يالهاي گراف است که Cij، بيانگر هزينه متناظر هر يال است .
ماتريس وزن يال ها ميتواند متقارن يا نامتقارن باشد و در صورتي که ماتريس وزن يال هاي گراف متقارن باشد؛ آنگاه مسئله را مسئله مسيريابي وسيله نقليه متقارن مينامند. هر وسيله نقليه k داراي ظرفيت Qk است که از دپو شروع به خدمت رساني مينمايد و در پايان خدمت رساني دوباره به دپو بر ميگردد. هدف VRP کلاسيک ، تعيين مجموعه مسيرهاي بهينه است به طوري که :
١- هر مشتري يک و فقط يک بار ملاقات گردد.
٢- هر وسيله نقليه از دپو شروع به حرکت مي کند و در پايان خدمت رساني به دپو باز مي گردد.
به عبارت ديگر، هر مسير از دپو شروع شده و دوباره به دپوختم گردد.
٣- تقاضاي کل مشتريان ملاقات شده توسط يک وسيله نقليه از ظرفيت وسيله نقليه تجاوز نکند.
براي مسئله مسيريابي وسيله نقليه کلاسيک ، توابع هدف متفاوتي بر اساس نوع مسئله ميتوان تعريف کرد ولي عموماً، هدف به صورت کمينه کردن هزينه کل به منظور خدمت رساني به گروهي از مشتريان با تقاضاي مشخص بيان ميگردد و به صورت يک برنامه ريزي عدد صحيح مرکب مدل ميگردد به طوريکه [٢٢]:

در مدل فوق ، K تعداد وسايل نقليه ، N تعداد مشتريان ، di ميزان تقاضاي مشتري i ،Cij هزينه حمل بين مشتري هاي i وj و متغير تصميم گيري است که مي تواند صفر يا يک باشد. در صورتيکه مساوي با ١ باشد آنگاه مشتري j پس از مشتري i توسط وسيله نقليه k ملاقات شده است و در غير اينصورت مشتري j پس از مشتري i توسط وسيله نقليه k ملاقات نشده است . همچنين رابطه دوم ، به ظرفيت هر وسيله نقليه اشاره دارد. رابطه سوم فوق ، بيان ميکند که هر وسيله نقليه از دپو شروع به حرکت مينمايد و سرانجام به دپو بر ميگردد و در نهايت رابطه چهارم ، بيانگر محدوديت تعداد وسائل نقليه است . شکل هاي ١ و ٢ به ترتيب ورودي و خروجي هاي يک مسئله مسيريابي وسيله نقليه کلاسيک را نشان ميدهند.


٣- انواع مسئله مسيريابي وسيله نقليه
تابع هدف و محدوديت هاي مسئله مسيريابي وسيله نقليه در سيستم هاي توزيع کالا و جابجايي مسافر بر حسب ويژگي هاي ساختاري و اجرايي سيستم توزيع ، متفاوت است . اين تفاوت ها منجر به ايجاد طيف وسيعي از مسائل با ويژگي هاي عملياتي گوناگوني شده است که در اين قسمت سعي مي -شود تا تعدادي از اصلي ترين انواع توسعه يافته مسئله کلاسيک مسيريابي وسيله نقليه تبيين و به صورت اجمالي شريح شوند.
٣-١ مسئله مسيريابي وسيله نقليه با چندين دپو
امروزه بسياري از شرکت هاي توزيع کالا از چندين دپو براي جمع آوري يا توزيع کالا استفاده مي نمايند؛ زيرا به کارگيري يک دپو براي توزيع کالا در محدوده خدمت رساني از ديدگاه اقتصادي مقرون به صرفه نيست [٢٣]. مسئله مسيريابي وسيله نقليه با چندين دپو (MDVRP)، شکل کلي مسائلي را در بر ميگيرد که در آن از چندين دپو براي خدمت رساني به مشتريان استفاده مي شود. در اين مسئله ، هر وسيله نقليه از يک دپو حرکت مينمايد و پس از ملاقات مشتريانش دوباره به همان دپو بر ميگردد. اين مسئله داراي سه مرحله تصميم گيري ميباشد. در مرحله اول هر مشتري به يک دپو اختصاص داده ميشود و مشتريان گروه بندي ميگردند، سپس در مرحله دوم ، به مشتريان يک گروه ، وسيله نقليه اي اختصاص داده ميشود و در نهايت در مرحله سوم ، نحوه و ترتيب ملاقات مشتريان توسط يک وسيله نقليه مشخص ميگردد. شکل ٣، نمونه اي از حل يک مسئله مسيريابي وسيله نقليه با چندين دپو را نشان ميدهد. تعداد مطالعات نسبتا" زيادي در زمينه حل مسئله مسيريابي وسيله نقليه با چندين دپو صورت گرفته است . در اين راستا، سِميرچارز و مُرکام [٢٤]، حمل مواد خام از چندين دپو به مجموعه اي از کارخانه - ها را در قالب مسئله مسئله مسيريابي وسيله نقليه با چندين دپو مدل نمود و روش ابتکاري بر اساس الگوريتم کلارک و وايت [١٤] براي حل اين مسئله ارائه دادند. رِ نود و همکاران [٢٥]، از يک روش ابتکاري براي حل MDVRP بهره بردند. در اين روش ، ابتدا يک جواب شدني ١٢ براي اين مسئله تعيين ميشود و در مرحله بعد از الگوريتم جستجوي ممنوع ١٣ براي بهبود جواب ها استفاده مي شود. در ادامه مطالعات قبل ، هادجي کُونستانتينو وَ بلداچ [٢٦]، ارائه سرويس خدمات تعمير و نگهداري به مجموعه - اي از مشتريان را در قالب MDVRP فرموله کردند و روش ابتکاري براي حل اين مسئله ارائه دادند که در مرحله اول ، مشتريان به يکي از دپوها اختصاص داده ميشوند و در مرحله دوم يک مسئله کلاسيک VRP براي هر دپو حل ميشود و در آخرين مرحله ، از الگوريتم حل مسئله فروشنده دوره گرد براي بهبود هر تور استفاده ميشود. خوانندگان علاقمند براي آشنايي بيشتر در اين زمينه ، مي توانند به مطالعهُ لو و همکاران (٢٠١١) [٢٧] مراجعه نمايند.

٣-٢ مسئله مسيريابي وسيله نقليه با کالاي برگشتي
مسئله مسيريابي وسيله نقليه با کالاي بازگشتي(VRPB)، نوعي از مسائل مسيريابي را شامل مي شود که در آن مشتريان علاوه بر اينکه کالاهايي را دريافت ميکنند ميتوانند بعضي کالاها را به دپو باز گردانند. مثلا فرض کنيد که در يک کارخانه توليدي ، لازم است که محصولات توليد شده در بين مشتريان توزيع شوند ، همچنين مواد اوليه مورد نياز کارخانه نيز از تامين کنندگان مواد اوليه ، به کارخانه حمل شود به طوريکه که در هر لحظه مجموع مواد توزيعي و مواد اوليه دريافت شده از تامين کنندگان کمتر از ظرفيت وسيله نقليه باشد و هر مشتري دريافت کننده يا تامين کننده کالا، يک و فقط يک بار و تنها توسط يک وسيله ملاقات گردد.
مسئله مسيريابي وسيله نقليه با کالاي بازگشتي ، اولين بار توسط ديف و بودين ( ١٩٨٤) [٢٨] مطرح گرديد. جِتچالکس و جِيکُبز (١٩٨٩) [٢٩] وکَسکُو و همکاران (١٩٨٨) [٣٠] سعي کردند که اين مسئله را حل نمايند.ُ توس و ويگو (١٩٩٧) [٣١] يک مدل رياضي براي اين مسئله ارائه دادند و آن را با الگوريتم هاي دقيق براي حداکثر ١٠٠ مشتري حل نمودند. برَ ندُ (٢٠٠٦) [٣٢] از الگوريتم فرا ابتکاري جستجوي ممنوع براي حل اين مسئله استفاده کرد که جوابهاي بدست آمده نسبت به مطالعات قبلي بهتر است . در ادامه اين مطالعات ، گَچپال وَ اباد (٢٠٠٩) [٣٣] روشي براي حل اين مسئله بر اساس الگوريتم مورچگان ١٥ چندگانه ارائه دادند. همچنين زَچرياديس و کِرَنديس (٢٠١٢) [٣٤] يک عملگر جستجوي محلي کارا براي حل VRPB پيشنهاد کردند.
٣-٣ مسئله مسيريابي وسيله نقليه با پنجره هاي زماني

مسيريابي وسيله نقليه با پنجره هاي زماني (VRPTW)، يکي از مهمترين و کاربردي ترين انواع VRP است . در حقيقت به منظور جلب رضايت مشتريان، شرکت هاي توزيع کننده کالا سعي کردند که از مدل هايي براي ارائه خدمات خود استفاده کنند که در آن هر مشتري در يک بازه زماني معين از پيش تعيين شده (پنجره زماني ) ملاقات ميگردد؛ در نتيجه ، سرويس دادن به مشتري قبل از اين پنجره زماني منجر به اضافه شدن يک زمان انتظار در کل زمان سفر ميشود. به عبارت ديگر، خدمت رساني به هر مشتري i بايد در يک بازه زماني [ bi ,ai ] صورت گيرد به طوريکه يک وسيله نقليه اگر قبل از زمان ai به مشتري i برسد بايد تا زمان ai صبر کند، همچنين خدمت رساني به اين مشتري نبايد بعد از زمان bi انجام گيرد.
عثمان (١٩٩٣) [٣٥]، لاپورته (١٩٩٢) [٣٦]،ِ برتسيماس و سِمچي (١٩٩٦) [٣٧] و بودين و همکاران (١٩٨٣) [٧] مرور کاملي بر انواع مسئله مسيريابي وسيله نقليه با پنجره هاي زماني داشته اند. روش هاي ابتکاري زيادي براي حل اين مسئله ارائه شده است ؛ براي مثال،گارسيا و همکاران (١٩٩٤) [٣٨]، پوتوين وهمکاران (١٩٩٦) [٣٩] از الگوريتم جستجوي ممنوع ١٧ در حل اين مسئله استفاده کرده اند.
الگوريتم ژنتيک ١٨ نيز در مطالعاتي مانند آمبُکي و همکاران (٢٠٠٦) [٤٠] وَ تن و همکارانش (٢٠٠١) [٤١] به کار رفته است . عثمان [٣٥] نيزيک الگوريتم ترکيبي بر اساس الگوريتم هاي شبيه سازي تبريدي ١٩ و جستجوي ممنوع ارائه داده است . خوانندگان علاقمند ميتوانند از مراجع [٤٢-٤٣] براي مطالعه بيشتر در اين زمينه استفاده نمايند.
٣-٤ مسئله مسيريابي وسيله نقليه باز
هدف مسئله مسيريابي وسيله نقليه باز(OVRP)، تعيين مسيرهاي بهينه براي مجموعه اي از وسائل نقليه به منظور خدمت رساني به تعدادي مشتري مشخص است به طوري که هر وسيله نقليه از دپو، سفرش را شروع مي نمايد ولي در پايان خدمت رساني به دپو باز نمي گردد. در حقيقت اصلي ترين تفاوت بين مسئله کلاسيک VRP و OVRP در نوع مسيرها مي باشد؛ در VRP هر مسير يک تور هميلتوني است در حاليکه در OVRP هر مسير يک مسير هميلتوني است [٤٤].
مسئله مسيريابي وسيله نقليه باز، اولين بار توسط سچراگ (١٩٨١) [٤٥] بيان شد و تا سال ٢٠٠٠ کمتر مورد توجه قرار گرفت [٤]. بعد از سال ٢٠٠٠ ميلادي ، مطالعات نسبتاً زيادي در اين زمينه صورت گرفت به طوري که چندين الگوريتم ابتکاري براي حل اين مسئله ارائه شد. ساريکليس و پوئل (٢٠٠٠) [٤٦] يک الگوريتم دو مرحله اي ابتکاري ارائه دادند که در مرحله اول مشتريان گروه بندي ميشوند و در مرحله دوم نحوه ملاقات هر مشتري در هر گروه (بطور مجزا) تعيين مي گردد. براندائو (٢٠٠٤) [٤٤] از الگوريتم جستجوي ممنوع براي حل اين مسئله استفاده کرد. در اين روش ابتدا يک جواب اوليه براي مسئله تعيين ميشود و در مرحله بعد با استفاده از روش هاي بهبود، جواب هاي شدني بهتري ايجاد ميشود. در سالهاي اخير نيز، کائو و لاي (٢٠١٠)

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