مساله مسیریابی وسایل نقلیه
اسلاید 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
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.