صفحه 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