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

صفحه 1:
oN ae Malt cs مساله مسیریابی وسایل نقلیه ‎Vehicle Routing‏ ‎Problem‏ (ee ‏د کت‎ sabe ‎eile‏ و ‏پاییز ۱۳۸۸ 

صفحه 2:
عناوین معرفی ‎VRP‏ شرح مساله ‎Gm‏ ‏مدلسازی ریاضی کد ینگو 

صفحه 3:
۱۷/۳۳ ‏معرفی‎ ‎Diinimum Spanning Tree © Shores Park Prostem | Traveter Setesman Prostom | MASP J Vehicle Routing 12 

صفحه 4:
شرح ماله ' مساله تامين تقاضاى كالا براى ۷ شهر با یک مبدا " ظرفیت وسایل نقلیه حمل کالاء محدود و مشابه زمان سرویس در هر شهر ثابت» مشخص و يكسان فاصله بین شهرها مشخص. ابت و متقارن " دارای پنجره زمانی با احتساب جریمه تاخیر ‎Window‏ ی وت ۱/۰۱ ی ‎ 

صفحه 5:
شرح مساله(ادامه) هدف: کم کردن هزینه بابت حمل کالا و جریمه ها هزینه حمل کالا: هر واحد مسافت یک واحد پولی هزینه جریمه تاخیر: هر واحد زمانی ۱۰ واحد پولی متغیرهای مدل: يال از أ به با وسیله >ا عازن زمان تاخیر/ انتظار أ ‎w; a;‏ تقاضای تجمعی پس از عبور از أ به ل[ زمان تجمعى هنكام رسيد نأ ‎t;‏ 

صفحه 6:
شرح مساله(ادامه) جدول فاصله هاى زمانى شهرها ‎KC Hou ۶‏ 2160 1060 500 1160 1020 590 0 1740 1720 0 0 710 0 770 0 210 1530 1580 1820 1900 160 1220 2280 Oak 1570 1520 250 1050 2680 Ana 

صفحه 7:
مدلسازی ریاضی داف کی ] عزيئه بابت حمل کالا و جریمه بو ‎١‏ منرم 0 ورود و خروج مبدا ‎N‏ 11ر1 د 58 DD © REAM PS Yay ‏كا‎ ۲ محدوديت ظرفيت عور مساك ور 7 

صفحه 8:
۳ ورود و خروج شهرهای دیگ ‎sees‏ ‏6 ى ديكر ۶0 را د الار دم 9 ge = 1 WP ‏سب‎ 0 Nii =O محدودیت پیوستگی مسیر هر توب ۵ محدودیتهای پنجره زمانى 5" ا 8 هعوةة 

صفحه 9:
ا سا پیب ‎MODE!‏ 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; bist = © 990 2160 1060 500 2050 9999 2050 © 0.1160 1020 590 1060 1220 1050 01160 0.1740 1720 210 160 250 010201740 0 710 1530 1900 1520 0 590 1720 710 0 1580 1820 1570 0.1060 210 15301580 0 370 30 01220 160 1900 1820 370 0 400 01050 25015201570 30 400 0; VCAP = 18; S=15; ENDDATA MIN = @SUM( CXC: DIST * x) +@SUM(CITY:10*d); 

صفحه 10:
مع __ @FOR CITY ۵: x(RR)=0! Q@SUM(CITY(i)| i ANEZR AAND H(i HEQ# 1 4ORFQ(i) + QR) ALEFVCAP): xi) =! @SUM(CITY())|j ANEFR ZAND 4 j HEQ#1 ORF) +1 R) LLEAVCAP): x(Rj))=15 oa Ai 

صفحه 11:
کد لینگو(ادامه) > eon ByORCITW i anEeR AAD sie ul R) <="VCAP - (VCAP -Q( R)) * 206 4,8)! @BND(Q( Rw &), VCAP)! 

صفحه 12:
ان الحلك 2054© 1 نه ع 0027# ‎@FOR( CITY i]t‏ UR) >=t( i) +(S+DIST( i, R)) *x( i, R) -10000+10000 *( x(R,i) +x(i,R)) = (S+DIST(i, &))*x( Ri)! ‏و‎ t-d4S <=LTi t(R) >= E(k) - (ET(R) -DIST(7,h)) *x( 7,8)! 

صفحه 13:
كد لينكو @FOR( CXC: @BIN(x))! vehclf = @SUM( CITY(+)| i #GT#7:Q(4))/ VCAP! vehclr =vehclf + 7.999 - @WRAP(vehiclf-0.007,1): oo “Ao 2, @SUM( CITY (j)|j 4GT#7:x« 7,9) >=vehclr! Cp, END نكته: تابع ©(100410ما ,»صلم )00000000 كوجكترين ضريب “بارا به »جلك به كونه اى مى افزايد كه حاصل از ‎١‏ بيشتر شود 

صفحه 14:
نتایج دول مربوط به متفیزهای 7 Chi KC Hou Fres Den Ana Oak 8 | ه| ه | ه| ها ه| ها د 

صفحه 15:
نتایج (ادامه 

صفحه 16:
نتا یج (ادامه) زمانهای رسیدن به هر شهر و میزان تاخیر م ‎a‏ Chi Den Fres KC LA Oak Ana وت ۷ ‎w t‏ 0 9 ° 0 0 ۰ 0 1440 990 ° 6 6 0 1440 2765 740 2 و 14400 1425 0 8 15 0 .79۷0 700 9 7 7 1 1440 2095 670 و 14 120 1440 2340 915 4 12 0 1440 2050 625 5 5 

صفحه 17:
بجع ل Soe Sa 2 ‏و‎ ‘Votes Mose Chex ۹ Tat 35 Mods Oise up Tal rise a Nae ‏من مه عه‎ || 552 a Side Giebat Gpeinum | bese bce ٠ | ‏كك ۸ بت هد‎ sari: 0 Test ‏هد‎ eit 0 Tut 154 0 nin ‏سا‎ a 07 161957 ors — todd Scher Sate Teal 840 anda che Se ac Solker ne Bend-p | Nenwse 7 Scher Type Bang-p || ۷ | seston 35100 | Gena Yancy Used ‏دم‎ 21072 | Bernat Meno Ul ‏تسه‎ 5 4 | ‏ممم‎ ‏م‎ Sehr Se Votes ۳۱ 3748 ‏يد ی | هد تمرم طسوت‎ (| . 0۵ Side: Giebat Gpeinum ‏رز‎ hese 0 Obie as | ‏هد‎ ‎۱ ‏مت سس‎ mew || wa 5 ‏ل‎ ‎etn 2947220 — Sande See Se ‏مدا‎ 892 ‏ممع ا‎ ۱ ۳ 1 ‏سا مس 31332 و‎ — Digan nine a oe 120645 eign ‏مس‎ ‏ا‎ 0 0 

صفحه 18:
7 030 Bes 08 ‏موه‎ لابح ياي ا يب حا دح جر fern) 

صفحه 19:
Types 4 ۰5۷۵ ‏أعر‎ ‎“Deliver ‎“Backhal ‎“Dyno ‎“Rowe by "Split de + 4 “Open ۰-6 ide Eksioglu, Arif Volkan Vural, Arnold Reisman(2009) The vehicle routing problem:A taxonomicreview 

صفحه 20:
اه ee NoterBxaictcs ring methodss "Constructive heuristic igeneticalaovithin “Nearest neighborhood 9 *Clarkand Wright *Tabusearch “Improvement heuristics 5 ۰2-01 °3-opt *Ant colony ‘K-opt *Simulatedannealing *Two-phases Sone *CFRS “RFCS 

الرحیم الرحمن ّ بسم اهلل ّ مساله مسیریابی وسایل نقليه ‏Vehicle Routing ‏Problem 1 پاییز 1388  معرفي VRP ‏ شرح مساله ‏ مدلسازی ریاضی ‏ کد لینگو ‏ نتایج ‏ بیشتر 2      M inimum S panning T ree Minimum Spanning Tree SShortest hortest P ath P roblem Path Problem TTraveler raveler S alesman P roblem Salesman Problem MTSP MTSP V ehicle R outing P roblem Vehicle Routing Problem 3  مساله تامین تقاضای کاال برای 7شهر با یک مبدا ‏ ظرفیت وسایل نقلیه حمل کاال ،محدود و مشابه ‏ زمان سرویس در هر شهر ،ثابت ،مشخص و یکسان ‏ فاصله بین شهرها مشخص ،ثابت و متقارن ‏ دارای پنجره زمانی با احتساب جریمه تاخیر ‏CVRPSTW ‏Soft ‏Time Window 4  ‏ 5 هدف :کم کردن هزینه بابت حمل کاال و جریمه ها ‏ هزینه حمل کاال :هر واحد مسافت یک واحد پولی ‏ هزینه جریمه تاخیر :هر واحد زمانی 10واحد پولی متغیرهای مدل: ‏ یال از iبه jبا وسیله k ‏ زمان تاخیر /انتظار i ‏ تقاضای تجمعی پس از عبور از iبه j ‏ زمان تجمعی هنگام رسیدنi Ana Oak LA 2050 9999 2130 2050 250 160 1050 1520 1220 1900 Chi 1160 0 0 990 210 1720 1740 0 1160 0 2160 Fres 0 710 1720 590 0 500 KC 1060 1530 400 0 370 400 Den 2160 1580 0 Fres 1060 1820 370 Hou 500 1570 30 KC 590 710 1020 210 1060 0 2050 250 1050 0 2050 1530 30 1570 1520 1900 160 1020 0 1740 1580 1820 990 0 0  جدول فاصله های زمانی شهرها 1220 0 1060 0 2130 Chi Den Hou LA Oak Ana 6  7 هدف :کمترین هزینه بابت حمل کاال و جریمه )1 ورود و خروج مبدا )2 محدودیت ظرفیت 8 )3 ورود و خروج شهرهای دیگر )4 محدودیت پیوستگی مسیر هر تور )5 محدودیتهای پنجره زمانی 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; ENDDATA MIN = @SUM( CXC: DIST * x) +@SUM(CITY:10*d); 9 @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; ); 5 3 4 2 6 7 8 @FOR( CITY( k)| k #GT# 1: @FOR( CITY( i)| i #NE# k #AND# i #NE# 1: K u( k) >= u( i) + Q( k) - VCAP + VCAP *( x( k, i) + x( i, k)) - ( Q( k) + Q( i))* x( k, i); ); ); u( k) <= VCAP - ( VCAP - Q( k)) * x( 1, k); I K I u( k)>= Q( k)+ @SUM( CITY( i)| i #GT# 1: Q( i) * x( i, k)); @BND( Q( k), u( k), VCAP); I K 11 @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 @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; END :نکته را بهLIMIT کوچکترین ضریبWRAP( index, LIMIT)@ تابع بیشتر شود1 به گونه ای می افزاید که حاصل ازindex 13 Xij جدول مربوط به متغیرهای Ana 1 0 0 Oak 0 0 1 0 0 0 0 0 0 0 0 0 0 LA 0 0 0 0 0 0 0 1 KC 1 0 0 0 0 0 0 0 Hou Fres 0 0 0 0 1 0 0 0 0 0 0 Den 1 1 0 0 0 0 0 0 0 0 0 0 0 Chi 0 0 Chi Den 0 Fres 0 KC 1 1 1 0 Hou LA Oak Ana 14 u=7 گراف پاسخ بهینه 5 ‏u=15 4 ‏u=9 ‏u=6 2 ‏u=14 6 8 ‏u=5 15 7 ‏u=13 3 زمانهای رسیدن به هر شهر و میزان تاخیر u Q d 6 6 0 15 8 0 9 0 0 t LT ET 990 1440 0 1425 1440 0 3 740 2165 7 7 0 700 13 4 14 5 0 9 670 2095 5 625 2050 915 2340 0 1440 0 Chi Den 0 Fres 1440 120 KC 1440 120 1440 1440 0 120 120 Hou LA Oak Ana 16  9شهر 8شهر 10شهر 17  10شهر 15شهر 20شهر 18 Types Typesof ofVRP: VRP: •Symmetric Symmetricor orAsymmetric Asymmetric •Delivery Deliveryand andpick pickup up •Backhauls Backhauls •Dynamic Dynamic •Route Routebalancing balancing •Split Splitdemands demands •Single Singleor ormulti-depot multi-depot •Open Open •1-skip 1-skipproblem problem •… … Burak Eksioglu, Arif Volkan Vural, Arnold Reisman(2009) The vehicle routing problem: A taxonomic review 19 Non-Exact HeuristicsSolving Metaheuristics methods •Constructive heuristic •Nearest neighborhood •Clark and Wright •Improvement heuristics •2-opt •3-opt •K-opt •… •Two-phases •CFRS •RFCS •Genetic algorithm •Tabu search •Scatter search •Ant colony •Simulated annealing •… 20