第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
论文研究-求解带时间窗取送货问题的遗传算法.pdf
32 1
2012 1
Systems Engineering — Theory & Practice
Vol.32, No.1
Jan., 2012
: 1000-6788(2012)01-0120-07
: O211
: A
1,2, 1
(1. , 410075; 2. , 411104)
"#$%&’, ()*,."012 4$67’. 7,
:4$67’;, ’>@: AB*C"#%&’$EÆ R1
Æ R2 Æ; GB IJ NO. 56 PRSTRSUV, W,X
Z\$^’_.
12 4; "0; 67’; "#%&’; IJ
Genetic algorithm for the pickup and delivery problem with time
windows
PAN Li-jun1,2, FU Zhuo1
(1. School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China;
2. School of Economics and Management, Hunan Institute of Engineering, Xiangtan 411104, China)
Abstract
In this paper, an insertion heuristic based on time difference is introduced. Based on this
insertion heuristic, a genetic algorithm for pickup and delivery problem with time windows (PDPTW)
is proposed. Comparing with other genetic algorithms, our algorithm holds two characters: 1) Cross
operation as well as R1- mutation operation and R2- mutation operation are based on time difference
insertion heuristic; 2) Non-generation search strategy is applied to the algorithm. Our algorithm is subject
to a comparative test on the benchmark problem sets that comprise 56 PDPTW instances. The results
show that the solution quality is better than the reported algorithm whose objective function is the same
as ours.
Keywords pickup and delivery problem; time window; genetic algorithm; time difference insertion heuris-
tic; non-generation search strategy
1 ‘a
(vehicle routing problem, VRP) 1959 Dantzig Ramser[1] ,
Æ. ÆÆ ,
VRP , , (vehicle routing
problem with time windows, VRPTW). (pickup and delivery problem with time win-
dows, PDPTW) VRPTW , :
!, ! ,
( ), ,
, #. , !
, !", !. $, !#"#%,
!’$ %, &$, ’ ’%.
PDPTW ’ ’ &. () , )*’!!!,
(), "#! *, !)*’ %. - [2] (!-%
!: 2010-03-22
de": &’#.)* (70671108); +/ .0.1/-..0 %
g’: 3 (1977–), , +01, /218, 213: 4956, 49956, E-mail: pansoftware@
126.com; 1 (1960–), , +:, ;, /8 <, 213: 4956.
1
3 , 4: =4 >56?6<7=8
121
, - [3] 7:.
? VRPTW, PDPTW -8%. @9@A: ;,-A" *
= PDPTW. Li Lim[4] Æ>?@ CEAA"- , <*= F CC 100
= . Pankratz[5] DF G (group genetic algorithms, GGA). EHH>I
=IFJ, IG G>I ?ÆJ , *=CC 100 = ,
#8H*=K. Popken[6] L) , I*= PDPTW, AB
PDPTW MK. Bent Van Hentenryck [7] LC>A" . DLCCEA
A"L$ , DELCL) FJL).
, *=@=B:L!$$), L:8%, G
I, MO KO /A0=. , PPK A" *
=B@= PDPTW SOP.
G VRP Q8*=KO, RG T>G HI
*= PDPTW. 1A: PPTJ 8, PDPTW P
S, - [8] PDPTW $C. DELMG HI ; DSLMTU*
= PDPTW G AVW )X$ B@=A ?2 ÆJ2; DLM
JT, W JT ; DLMTLM.
2 345 (time difference insertion heuristics, TDIH)
I VRPTW $W /AA" . Solomon[9] YI (push
forward insertion heuristics, PFIH), PY7 P . PFIH [I \LI
T>, Solomon PP,*= VRPTW A" , = J, *=K8H. Pankratz
- [5] M PFIH GGA ?T>*= PDPTW, #8HK. PP,IA"
—— HI , PZ:
2.1 8:k
P%$ Routei (P0, P1,··· , Pi−1, Pi, Pi+1,··· , Pn, P0), P0 , Pi (i = 1, 2,··· , n)
A;*#, Bi Li (i = 1, 2,··· , n) ;*
, Pi ;* O#( [Bi, Li] <, , A Bi P ;*, B0 L0
MQ P0 :S, ’A L0 < ;*, . Si Pi ;
*T!, Ti−1.i ! Pi−1 Pi :
:k 1 P Pi ;* EFi, EFi = max(Bi + Si, EFi−1 + Ti−1.i + Si)
(i = 1, 2,··· , n).
: 1 P%$ Routei (P0, P1, ···, Pi−1, Pi, Pi+1, ···, Pn, P0) (i = 1, 2,··· , n), Pj I
B Pi−1, Pi C
PP*= PDPTW G , X =W, ?2 ÆJ2W_ (pickup
and delivery points, PD) IY; ( PD I$, <DI ). ,
:k 2 P Pi ;* LSi, LSi = min(Li, LSi+1 − Ti.i+1 − Si).
P0 T!;*, S0=0, ] EF0=B0, LS0=L0, EF0 LS0 MQ=\ \P
Routei EF LS 7.
P Routei O?L Pi−1, Pi(i = 1, 2,··· , n), EFi−1 U ! P0
Pi−1 T!;*, G LSi UA ; ! Pi Pn ;*, Pi ;
*^. V Pi−1, Pi i), LSj Pj , EFi
Pi , H T Di,j = LSj − EFi.
2.2 8> m@
122
5 6 [ . Z c [
32
HI G . , PPHI : HI (fast time difference
insertion heuristics, FTDIH) HI (optimization time difference insertion heuristics, OTDIH).
P$ Routei (P0, P1, ···, Pi−1, Pi, Pi+1, ···, Pn, P0) (i = 1, 2,··· , n), /
C max, / Load i (i = 1, 2,··· , n), PD (MQ Pp, Pq U) I
Routei.
1) FTDIH Z:
Fn 1 P Routei EFi LSi (i = 1, 2,··· , n).
Fn 2 ! Pp DIB P0, P1 , PBH TDi,i+1 (i = 0, 1,··· , n), P
EFp, VB" 1, Pp IB, fdj<AÆ)#kk . =G G , < fS,
GbG l fSSG , X Goldberg[11]. PPG G
jVZ:
X , Pop;
VTU%e>
fl )REfl x, y;
e? O Pcross x, y g?2, ’ l x, y;
eÆJ O Pmut x, y
gÆJ2, ’ l x, y;
Ffl
T, , )7fl;
flU PDPTW =, hE Ti=.
), Goldberg[11] jV;ZA: b HI ’ X =; E_
3 , 4: =4 >56?6<7=8
123
1
jVFflY;j, x, y
_, fl?))7 _,
)Lfl, F, ^F. TU%: ’ fl$E S max,
E m Num \i, fl, S max Num nk$.
3.2 qCVW
b#>k;G>Ip, 1, 2,··· , n U#, >kUGG. Hl
;HI , G>k# EF LS 7p.
3.3 sXY Z[\]^
PDPTW *=@=/A)e\: %!$ L&lm
L& L. A#*=@=, PP@=X$:
min Z(x) = a1K(x) + a2Dist(x) + a3Duration(x) + a4W ait(x)
(1)
K(x), Dist(x), Duration(x), W ait(x) e\Ufl x ’!$ &lm
& ; a1 a2 a3 a4 $, a1 >> a2 >> a3 >> a4. PP )knX$
:
F it(x) = Z(x)/Zmin
(2)
Z(x) fl x @=X$, Zmin , ’fl@=X$L7.
3.4 abq
PP?2 Pankratz[5] ?2;j, fllmL.
?ofl A, B MQRV%. qm/p#kgnq, qm#
ko] flIp, ; OTDIH I#?fl A, B. VI
, fl\f’ %$/I.
3.5 dvq
,ÆJ2: R1 ÆJ2, 2kÆJflfR%, !_fl
nq, # PD OTDIH I_fl. R1 ÆJ2K%$ .
E R2 ÆJ2, 2!kÆJflfR PD , PD OTDIH I
_. R2 ÆJ2 p, K/.
4 Æ5exfg
b Matlab7.0 >I, Æ IV2.0G PC #, TtL$. ! PDPTW
=J p (CC 100 #, i 56 , http://www.sintef.no/Projectweb/TOP/Probl-
ems/PDPTW) J.
JEk$bZPB: , CC 100, ? O 0.5, ÆJ O 1.0, $
S max=10000, m , \$ Num=30. 10 \, 10 \TW-
8.
s-, Li Lim[4] PP (Z LLA U) *=@=h, GW
*=@=IL$ L&lm, e! . , JT
LLA 8.
U 1 U 2 LLA MK: U 1 ep 8, qT,
124
5
5 6 [ . Z c [
32
PPW PDPTW *= !HI , PPG HI ?2Æ
J2, GPP*= PDPTW G , < ql fS_ux@=X$. ,
Matlab7.0 >I , x{y; MW= {4>5x{y; |z{x
= >5z ({~), )xx|{ Linux Kernel 2.2.15-5.0smp on i686; CPU(M)= x{
LLA 7}~; CPU
>5z ({~), )x7x|{ XP on Pentium IV 2.0G; MCPU= 5.
♠
n 2 oyzp{ LLA r uwxn
<
D
(V)
Li and Lim[4]
Li and Lim[4]
<
Dur(W) CPU
♠
D
(V)
Dur(W) CPU
D
(V)
Dur(W) CPU
♠
D (V)
Dur(W) CPU
lc101 828.94 9828.94
(10)
(0)
lc102 828.94 9828.94
(10)
(0)
lc103 827.86 10058.03 191
(10)
(230.17)
lc104 861.95 10006.9
(144.95)
lc105 828.94 9828.94
(9)
(10)
(0)
(0)
33
71
(9)
(0)
(9.41)
17.80 lr112 1003.77 2013.17
35.31 lr201 1263.84 3495.81
828.94 9828.94
(10)*
828.94 9828.94
(10)*
1082.40 10300.86 41.45 lr202 1197.67 2749.39
(9)
(551.73)
1254 865.94 10009.25 78.02 lr203 949.40 2762.80
(813.40)
29.09 lr204 849.05 1988.57
(139.52)
(89.08)
47
(3)
(3)
(2)
(4)
(1231.97)
(9)
(143.31)
828.94 9828.94
(10)
*
828.94 9828.94
(0)
638
193
885
2013.17
(9.41)
1003.77
(9)*
1253.23 3495.82
(4)
1197.67
(3) *
50.72
148.84
351.09
283.44
639.84
(1242.59)
2749.39
(551.73)
2762.80
(813.40)
1988.57
(139.52)
1950 949.40
(3) *
2655 849.05
(2) *
lc106 828.94 9828.94
43
31.54 lr205 1054.02 2550.13
585
1054.02
2550.13
252.11
1
3 , 4: =4 >56?6<7=8
125
{ 2 }{
<
D
(V)
Li and Lim[4]
Li and Lim[4]
<
Dur(W) CPU
♠
D
(V)
Dur(W) CPU
D
(V)
Dur(W) CPU
♠
D (V)
Dur(W) CPU
(10)
(0)
lc107 828.94 9828.94
(10)
(0)
lc108 826.44 9826.44
(10)
(0)
lc109 827.82 9831.78
(10)
(3.96)
lc201 591.56 9591.56
(3)
(0)
lc202 591.56 9591.56
(3)
(0)
lc203 585.56 9521.66
(26.09)
lc204 591.17 9591.17
(3)
(3)
(0)
lc205 588.88 9588.88
(3)
(0)
lc206 588.49 9588.49
(3)
(0)
(3)
(3)
(19)
lc207 588.29 9660.4
(72.12)
lc208 588.32 9744.23
(155.91)
lr101 1650.78 3599.45
(948.65)
lr102 1487.57 3202.46
(714.89)
lr103 1292.68 2729.15
(436.48)
lr104 1013.39 2050.85
(37.46)
lr105 1377.11 2631.56
(254.45)
(13)
(17)
(14)
(9)
lr106 1252.62 2412.11
(159.49)
(12)
lr107 1111.31 2220.27
(108.96)
(10)
lr108 968.97 2029.93
(60.96)
lr109 1239.96 2311.37
(9)
(0)
255
145
(3)
(3)
(0)
(0)
(2)
(2)
54
82
746
190
(0)
(0)
(3)
(3)
(0)
(0)
(14)
27
94
(13)
(3.96)
(496.11)
150.98 lr211 927.8
61.41 lr207 903.06 1936.44
(33.38)
155.31 lr208 743.85 1858.36
(123.51)
35.21 lr206 931.63 2502.46
(570.84)
(10)
*
828.94 9828.94
(10)
*
826.44 9826.44
(10)
*
827.82 9831.78
(10)
*
48.69 lr209 937.05 2432.61
591.56 9591.56
(459.56)
(3) *
83.41 lr210 964.22 2782.06
591.56 9591.56
(817.83)
(3) *
1954.57
591.17 9601.72
(26.77)
(3)
(10.54)
252.34 lrc101 1708.80 2956.32
591.17 9591.17
(247.52)
(3)*
86.67 lrc102 1563.55 2764.14
588.88 9588.88
(200.59)
(3)*
184.2 lrc103 1258.74 2443.68
588.49 9588.49
(3)*
(184.95)
588.29 9588.52 203.44 lrc104 1128.40 2238.17
(3)
(109.77)
272.17 lrc105 1637.62 2830.16
588.32 9744.23
(3)*
(155.91)
(192.54)
lrc106 1425.53 2475.01
1650.78 3599.45
(19)*
(948.65)
(49.48)
43.56 lrc107 1230.15 2344.94
1168 1487.57 3202.46
(17)*
(714.89)
(114.8)
38.48 lrc108 1147.97 2245.3
1292.68 2729.15
(13)*
(97.34)
(436.48)
70.94 lrc201 1468.96 3358.41
1013.39 2050.85
(9) *
(37.46)
(889.45)
28.81 lrc202 1374.27 2657.14
1377.11 2631.56
(282.87)
(254.45)
(14)
*
1252.62 2412.11
(12)
(159.49)
*
1111.31 2220.27
(10)
(108.96)
*
968.97 2029.93
(9) *
(60.96)
1239.96 2311.37
33.03 lrc204 827.78 2537.83
(710.05)
42.61 lrc206 1162.91 2444.87
46.19 lrc205 1302.2 3464.61
29.06 lrc203 1089.07 2700.3
(611.23)
(11)
(10)
(0)
(0)
(4)
(3)
(11)
(10)
169
459
102
178
415
348
69
87
(3)
(3)
(13)
(11)
88
87
287
(2)
19
(4)
(1162.41)
(3) *
(496.11)
747
931.63
(3) *
2502.46
(570.84)
394.84
1594 903.06
(2) *
1936.44
(33.38)
304.63
3572 738.87
(2)
1849.67 503.16
(110.80)
2773 930.78
(3)
1482 970.54
(3)
4204 911.49
316.72
280.25
2405.01
(474.32)
2782.06
(811.52)
1920.34 438.5
(8.85)
2956.32
(247.52)
25.33
40.36
53.48
(145.85)
2443.68
(184.95)
2238.17
(109.77)
2830.16
(192.54)
(2)
1708.80
(14)*
1558.07 2703.92 42.05
(12)
1258.74
(11) *
1128.40
(10) *
1637.62
(13) *
1424.73 2474.22 59.83
(11)
1230.15
(11) *
1147.43 2244.76 65.33
(10)
(97.34)
1421.20 3358.41
(937.21)
(4)
1374.27
2657.14
(282.87)
(3)*
(49.49)
2344.94
(114.8)
68.08
28.19
109.86
180.42
119
152
175
202
179
459
154
650
266
987
1605 1089.07
(3)*
2700.3
(611.23)
186.88
3634 827.78
(3)*
2537.83
(710.05)
478.05
639
445
1302.2
(4)*
1159.06 2444.90
3464.61
(1162.41)
185.44
133.83
126
{ 2 }{
<
D
(V)
5 6 [ . Z c [
32
Li and Lim[4]
Li and Lim[4]
<
Dur(W) CPU
♠
D
(V)
Dur(W) CPU
D
(V)
Dur(W) CPU
♠
D (V)
Dur(W) CPU
(11)
(71.42)
lr110 1159.35 2222.99
(63.64)
(10)
547
lr111 1108.9 2189.53
(80.63)
(10)
179
(71.42)
(11)
*
1159.35 2222.99
(10)
(63.64)
*
1108.9 2189.53
(80.63)
(10)
*
(3)
(281.96)
(3)
(285.84)
51.89 lrc207 1424.6 2461.42
(36.82)
(3)
607
1062.05 2417.51 288.54
(3)
(355.46)
38.09 lrc208 852.76 2271.19
(418.44)
(3)
4106 918.68
(3)
2344.04
(425.36)
456.85
= >5 ({~), )xx|{ Linux
: D= {w; V= z{|; Dur= {>; W= {4>5; CPU
Kernel 2.2.15–5.0smp on i686; CPU=10 } 7x{>5 ({~), )x7x|{ XP on Pentium IV 2.0G; * {
c LLA 7}~~, |z{x LLA 7}~
♠
}}~
[1] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80–91.
[2] Rekiek B, Delchambre A, Saleh H A. Handicapped person transportation: An application of the grouping genetic
algorithm[J]. Eng Appl Artif Intel, 2006, 19: 511–520.
[3] Fagerholt K, Christiansen M. A combined ship scheduling and allocation problem[J]. Journal Operation Research
Society 2000, 51: 834–842.
[4] Li H, Lim A. A metaheuristic for the pickup and delivery problem with time windows[C]// 13th IEEE Inter-
national Conference on Tools with Artificial Intelligence, IEEE Computer Society, Los Alamitos, CA, 2001:
333–340.
[5] Pankratz G. A grouping genetic algorithm for the pickup and delivery problem with time windows[J]. Operation
Research Spectrum, 2005, 27: 21–41.
[6] Popken D A. Controlling order circuity in pickup and delivery problems[J]. Transport Research E-Log, 2006, 42:
431–443.
[7] Bent R, Van Hentenryck P. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with
time windows[J]. Compute Operation Research, 2006, 33: 875–893.
[8] Savelsbergh M W P, Sol M. The general pickup and delivery problem[J]. Transportation Science, 1995, 29: 17–29.
[9] Solomon M. Algorithms for the vehicle routing and scheduling problem with time window constraints[J]. Oper-
ations Research, 1987, 35(2): 254–265.
[10] Holland J H. Adaptation in Natural and Artificial Systems — An Introductory Analysis with Applications to
Biology, Control, and Artificial Intelligence[M]. The University of Michigan Press, Ann, 1975.
[11] Goldberg D E, Korb B, Deb K. Messy genetic algorithms: motivation, analysis, and first result[J]. Complex
Systems, 1990, 3: 493–530.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
