مساله مسیریابی وسایل نقلیه

مساله مسیریابی وسایل نقلیه

اسلاید 1: ارائه: امیرمحسن کریمی مجدبسم الله الرّحمن الرّحیممساله مسیریابی وسایل نقليهVehicle Routing Problem1پاییز 1388استاد: دکتر سیفی

اسلاید 2: عناوینمعرفي VRPشرح مسالهمدلسازی ریاضیکد لینگونتایجبیشتر2

اسلاید 3: معرفی VRPShortest Path Problem3Traveler Salesman ProblemMTSPVehicle Routing ProblemMinimum Spanning Tree

اسلاید 4: شرح مسالهمساله تامین تقاضای کالا برای 7 شهر با یک مبداظرفیت وسایل نقلیه حمل کالا، محدود و مشابهزمان سرویس در هر شهر، ثابت، مشخص و یکسانفاصله بین شهرها مشخص، ثابت و متقارندارای پنجره زمانی با احتساب جریمه تاخیر4Time WindowSoftCVRPSTW

اسلاید 5: متغیرهای مدل:یال از i به j با وسیله kزمان تاخیر/ انتظار iتقاضای تجمعی پس از عبور از i به jزمان تجمعی هنگام رسیدنiشرح مساله(ادامه)هدف: کم کردن هزینه بابت حمل کالا و جریمه هاهزینه حمل کالا: هر واحد مسافت یک واحد پولیهزینه جریمه تاخیر: هر واحد زمانی 10 واحد پولی5

اسلاید 6: شرح مساله(ادامه)AnaOakLAKCHouFresDenChi205021302050500106021609900Chi105012201060590102011600990Den25016021017201740011602160Fres1520190015307100174010201060Hou15701820158007101720590500KC3037001580153021010602050LA40003701820190016012202130Oak0400301570152025010502050Anaجدول فاصله های زمانی شهرها6AnaOakLAKCHouFresDenChi205099992050500106021609900Chi1050122010605901020116000Den25016021017201740011600Fres1520190015307100174010200Hou157018201580071017205900KC3037001580153021010600LA40003701820190016012200Oak0400301570152025010500Ana

اسلاید 7: مدلسازی ریاضیهدف: کمترین هزینه بابت حمل کالا و جریمهورود و خروج مبدامحدودیت ظرفیت7

اسلاید 8: مدلسازی ریاضی(ادامه)ورود و خروج شهرهای دیگرمحدودیت پیوستگی مسیر هر تورمحدودیتهای پنجره زمانی2 -n-18n

اسلاید 9: کد لینگوMODEL: SETS:CITY/1..8/: Q, u, t, d, ET, LT;CXC( CITY, CITY): DIST, x; ENDSETS  DATA: Q = 0 6 3 8 7 9 4 5; ET = 0 0 0 0 120 120 120 120; LT = 0 1440 1440 1440 1440 1440 1440 1440;DIST = 0 990 2160 1060 500 2050 9999 2050 0 0 1160 1020 590 1060 1220 1050 0 1160 0 1740 1720 210 160 250 0 1020 1740 0 710 1530 1900 1520 0 590 1720 710 0 1580 1820 1570 0 1060 210 1530 1580 0 370 30 0 1220 160 1900 1820 370 0 400 0 1050 250 1520 1570 30 400 0;  VCAP = 18; S=15; ENDDATAMIN = @SUM( CXC: DIST * x) +@SUM(CITY:10*d);9

اسلاید 10: کد لینگو(ادامه)@FOR( CITY( k)| k #GT# 1: x( k, k) = 0; @SUM( CITY( i)| i #NE# k #AND# ( i #EQ# 1 #OR# Q( i) + Q( k) #LE# VCAP): x( i, k)) = 1;  @SUM( CITY( j)| j #NE# k #AND# ( j #EQ# 1 #OR# Q( j) + Q( k) #LE#VCAP): x( k, j)) = 1;);102375648

اسلاید 11: u( k) <= VCAP - ( VCAP - Q( k)) * x( 1, k); u( k)>= Q( k)+ @SUM( CITY( i)| i #GT# 1: Q( i) * x( i, k)); @BND( Q( k), u( k), VCAP); کد لینگو(ادامه) @FOR( CITY( k)| k #GT# 1: @FOR( CITY( i)| i #NE# k #AND# i #NE# 1: u( k) >= u( i) + Q( k) - VCAP + VCAP *( x( k, i) + x( i, k)) - ( Q( k) + Q( i))* x( k, i); ); );11KIKIIK

اسلاید 12: کد لینگو@FOR( CITY( k)| k #GT# 1:  @FOR( CITY( i)| i #NE# k #AND# i #NE# 1: t( k) >= t( i) + (S+DIST( i, k))*x( i, k) -10000+10000 *( x(k, i) + x(i, k)) - (S+DIST(i, k))*x(k, i); ); t -d +S <= LT; t( k) >= ET(k) - ( ET(k) - DIST(1, k)) * x( 1, k); );12

اسلاید 13: کد لینگو@FOR( CXC: @BIN( x));vehclf = @SUM( CITY( i)| i #GT# 1: Q( i))/ VCAP;vehclr = vehclf + 1.999 - @WRAP( vehclf-0.001 , 1);@SUM( CITY( j)| j #GT# 1: x( 1, j)) >= vehclr; END13Bin Packing Problemنکته:تابع @WRAP( index, LIMIT) کوچکترین ضریب LIMIT را به index به گونه ای می افزاید که حاصل از 1 بیشتر شود

اسلاید 14: AnaOakLAKCHouFresDenChi10010010Chi00000100Den01000000Fres00000001Hou00001000KC00000001LA00000001Oak00100000Anaجدول مربوط به متغیرهای Xij14نتایج

اسلاید 15: گراف پاسخ بهینه237564815u=7u=15u=5u=14u=13u=6u=9نتایج(ادامه)

اسلاید 16: نتایج(ادامه)زمانهای رسیدن به هر شهر و میزان تاخیرuQdtLTET000000Chi66099014400Den93740216514400Fres1580142514400Hou7707001440120KC14967020951440120LA13491523401440120Oak5562520501440120Ana16

اسلاید 17: نتایج(ادامه)178 شهر10 شهر9 شهر

اسلاید 18: نتایج(ادامه)1810 شهر20 شهر15 شهر

اسلاید 19: بیشتر19Types of VRP:Symmetric or AsymmetricDelivery and pick upBackhaulsDynamicRoute balancingSplit demandsSingle or multi-depotOpen1-skip problem…Burak Eksioglu, Arif Volkan Vural, Arnold Reisman(2009) The vehicle routing problem: A taxonomic review

اسلاید 20: بیشتر20 Heuristics MetaheuristicsConstructive heuristicNearest neighborhoodClark and WrightImprovement heuristics2-opt3-optK-opt…Two-phasesCFRSRFCSGenetic algorithmTabu searchScatter searchAnt colonySimulated annealing…`Non-Exact Solving method