论文研究-求解带时间窗取送货问题的遗传算法.pdf

所需积分/C币:13 2019-09-20 16:52:47 473KB .PDF
8
收藏 收藏
举报

论文研究-求解带时间窗取送货问题的遗传算法.pdf,  首先介绍基于时差的插入法,进而设计求解带时间窗取送货问题的遗传算法.与传统求解该问题的遗传算法相比, 本算法有 以下特点:一是设计了基于时差插入法的交叉算子、R1变异算子与R2变异算子;二是采用非代际搜索策略. 应用56个标准测试算 例测试显示,其求解质量比已有文献报道的同类算法高.
122 系统工程理论与实践 第32卷 本文将时差插入应用于遗传算法当中.为此,设计了两类时差插入方法:快速时差插入( fast time difference insertion heuristics. FTDIH)与最优时差插入( optimization time difference insertion heuristics,OIDH 设当前可行线路为 route;(Po,P1,…,P-1,P2,P+1,…,Pn,P)(=1,2,…,m),车辆的最大载重 量为Cmax,车辆在各点的当前载重为Lood2(=1,2,…,m),将一PD点对(分别用P2,Pq表示)插入 route 1)FTDI步骤如下 步骤1计算 router;各点的EF2与LS2(i=1,2,……,m) 步骤2从P点的第一个可能插入位置Po,P1开始,计算该位置的时差TD,a+1(=0,1,……,m),计算 EF,若该点在该位置满足定理1,则将P插入到该位置,并记P2点后的位置为D- ansertbeain 步骤3依次更新P点之后各点的EF、LS、Lod2值.若所有Lon值均小于等于Cmax,则记 D- inserter为该线路的末尾位置;若有某些点的Load,值大于Cmax,设第·次出现该情况点为Pks,记Pk 之前的位置为D_ inserted 步骤4从 D-insertbeain到 D_inserted依次计算各位置的时差与EF,并检查是否满足定理1,若满足 则将Pd插入,转步骤5:若所有位置均检查后都不能插入,则该PD点对插入失败 步骤5更新从P开始到线路术的EF、LS、Lod1值 2) OTDIH步骤如下 步骤1计算 route;各点的EF2与LS2(=1.2,,n) 步骤2从P点的第一个可能插入位置Po,P1开始,计算该位置的时差TD,x+1(i=0,1,…,n) EF,以及插入后,目标函数的增量.选择插入位置满足定理1且目标函数增量最小的位置,将P插入,记 下该位置为 D_inserts 步骤3依次更新P,点之后各点的EF、LS、Jwd值.若所有Loud1值均小于等于Cmax,则记 D- inserted为该线路的末尾位置;若有某些点的Lood,值大于Cmax,设第一次出现该情况点为Pk,记Pk 之前的位置为D. inserted. 步骤4从D- inserthegin到 D_inserted依次计算各位置的时差与EF,及插入Pa后目标函数的增量, 选择插入位置满足定理1且目标函数増量最小的位置,将插λ,转步骤3:若所有位置均检查后都不能插 入,则该PD点对插入失败 步骤5更新从P开始到线路末的EF;、LS;、 Load1值 上TDIH插入的速度较快,且具有一定的随机性,主要应用于遗传算法初始解的构造.而 OTDIH每次插 入均选择当前的最优位置插入,具有较强的局部寻优能力,主要用于交叉算子与变异算子的设计,以加快遗 传算法的收敛速度. 3求解 PDPTW的遗传算法设计 3.1算法的基本架构 遗传算法是1975年由美国 Holland10教授与其学生共同创立发展的一种慨率式搜索算法,目前已在组 合最优化、机器学习和并行处理等领域得到越来越广泛的应用标准的遗传算法是基于种群的并行搜索机制, 而本文采用是基于个体搜索机制的非代际遗传算法,其最初由 Goldberg(1提出.本文设计的遗传算法基本 框架如下 初始化种群Pop; 若终止条件不符合 按染色体的适应度选择二个染色体x,y; 依交叉慨率 Pcross对r,y实施交叉算子,生成两个新个体x’,y 依变异概率Pmut对x',y′实施变异算子,生成两个新个体x",y′ 替换染色体 算法结算,返回种群中适应度值最大的染色体; 每个染色体均表示 PDPTW的一个可行解,算法迭代过程中始终保持每个解可行.为了加快算法的收敛 速度,本文还对 goldberg的算法框架作如下处理:一是采用快速时差插入法生成初始解;二是对原有算 第1期 潘立军.等:求解带时间窗取送货问题的遗传算法 123 法框架中替换染色体操作进行改进,即当x",y′与原种群中染色体不相同且其适度度值优于原种群中适应 度最小的染色体,则进行替换,否则不替换.算法的终止条件有两个:一是生成的新染色体个数超过S-max, 二是算法连续Nm次没更新种群中的染色体,S-max与Nm均为事先确定的参数 32算法的编码 算法采用客户编号作为基本编码信息,1,2,……,m代表客户,每一编号代表一基本的基因位.为了更好地 利用时差插入法,每一基因位还增加了当车辆到达该编号客户时的EF与LS值信息 33适应度函数及多目标求解的处理 本文 PDPTW旳求解目标按其重要性程度依次为:最少化车辆使用数量、最小化车辆行驶总距离、最 小化车辆行驶总时间、最小化车辆等待总时间.为处理以上求解目标,设计目标函数为 min Z()=a1K(r)+a2 Dist(a)+as Duration(a)+aWait(a) K(x),Dist(x), Duration(x),Wait(x)依次表示染色体x所使用的车辆数量、车辆行驶总距离、车辆行 驶总时间、车辆总等待时间;ω1、a、a、u为系数,且有a1>>a>>a3>>a4.设计的适应度评价函数 为 Fit(a)=Z()/Zmin z(x)为染色体x的目标函数,Zmin为当前种群中所有染色体目标函数中的最小值 34交叉算子 本文设计的交叉算子对 Pankratz5的交叉算子作」改进染色体片断交换的最小单位为路径.进行交 义的两个父染色体A,B分别选取若干条路径进行交换.对因交换引起的重复客户号实施删除,引起的客户 号缺失则组成各染色体的再插入集,最后利用 OTDIH进行再插入得到交叉后的染色体4,B′.若插入不成 功,则在染色体末尾再生成一条空线路重新进行插入 35变异算子 有两种变异算子:一是R1变异算子,该算子在参与变异的染色体中随机选取一条路径,将其从原染色体 中删除,然后将该路径上的PD点对运用 OTDIH插入到原染色体中.R1变异算子可有效的减少路径数量. 二是R2变异算子,该算子从参与变异的染色体中随机选取一PD点对,将该PD点对运用 OTDIH插入到 頂路径中.R2变异算子在算法后期,可有效对路径进行最优重排 4算法测试与比较 算法采用 Matlabτ.0编程实现,运行于奔腾πV2.0G的PC上,运算结果精确到两位小数.使用 PDPTW 标准测试算例集(问题规模为100个客户,共56个算例,来自http://www.sintef.no/projectwEb/top/probl ens/ PDPTW)进行测试 测试过程的参数均采用以下设置:种群规模为100,交叉概率为0.5,变异概率为1.0,算法最大搜索个数 S-max=10000连续未更新种群次数Nm=30.每个算例运行10次,取10次的最优结果与其它文献进行比 较 在以往的文就当中,只有Li与Lim4设计的算法(下文用LLA表示)其求解目标与本文一致,而其它 算法的求解目标均仅为最小化车辆数量和最小化车辆行驶距离,不具有直接可比性.因此,本文将测试结果 与IA比较 表1、表2为本文算法与LLA的对比情况:表1依问题集比较了两种算法的平均结果,并计算了本文 算法相比于LLA在各求解目标上的平均节约值,除问题集LC2、LR1本文算法与LLA的求解质量相当外, 其它问题集本文算法的求解质量均优于LLA算法 表2为求解结果的详细对比情况,有11个(20%算例的结果优于LLA(在表中用粗体表示)其中 第一目标优于LLΔ的有2个,第二目标优于的有9个,第三目标优于的有5个,第四目标优于的有2个;有 40个(占71%)算例的结果与LLA相当(在表中加*号表示),有5个(占9%)算例的结果在第二目标或第 三目标上略低于LLA.总休米看,除LC2集以外,其它问题集本文算法均找到了新的当前最好解. 而在算法求解速度方面,本文在表1与表2中均列出了两种算法的平均求解时间与问题集的平均求解 时间,但因两种算法的测试环境不同,所以两种算法的求解速度没有直接可比性.但总体分析认为,本文算法 的求解时间是可以接受的 124 系统工程理论与实践 第32卷 5结论 本文设计了可在构造 PDPTW求解算法中使用的时差插入法,设计了基于时差插入法的交叉算子与变 异算子,进而设计了求解 PDPTW的遗传算法,并在算法中引入个体搜索机制及层级目标函数.最后,本文 用 Matlab7.0编程实现了该算法,并釆用标准测试算例集测试,与其它算法相比,本文算法显示出了较高的 求解质量 表1本文算法与LLA的求解结果综合对比表 Li and limt 本文算法 问题 节约值(单位:‰) 集 MD MDur MW CPU MDur MW SV Sd SDur Sw (MV) (MCPU) (MV) (MCPU) LC1832099874.2142.1233-1257860.819901.4526.2617.80 1.1 155.31 989) (225.56)(978 IC2589.239609.7431.7727-746 589.939610.7720.8148.690 272.17 (3.00) (19625)(3.00 (14162) LR11222202467.74245.5469-11681222.202467.742455419.00 79.94 (1192) (37108)(11.92) (4103) LR2973.872455.75478.601934204971.792449.34477.5514884 00.210.260.22 (1876.36)(2.73) (346.14) LRC11387602537.22149.621196501386.742529.521427825.33 1.10.060.34.5 68.08 (11.63) 261.2 (4783) LRC21187822736.97549.15266-41061145.692742.14596.45109.86 478.0 (325) (1536.13)(3.25) 22321) 注:MD=路长平均值;MV=车辆使用数量平均值;MDur=总时长平均值:MW=总等待时间平均值;加粗表示优于 LLA的结果CPU命一算法运行时间范围(单位为秒),基于平台为 Linux kernel2215-5.0 smp on i86;CPU(M)-平均 运算时间范圄(单位为秒),基于的平台为 XP on pentiumⅣV2.0G;MCPU=问题集的半均运算时间 表2本文算法与LLA的求解结果对比表 Li and lim 4 本文算法 Li and lim 4 问题 问题 本文算法 Dur(W)CPU·DDur(W)CPU号DDur(W)CPU·D(V)Dur(W)CPU# (V (V) lc10182894982894338289498289417.80lr1121003.772013.176381003.772013.1750.72 (10)*(0) (9)(9.41) lc10282894982894718289498289435.31lr2011263.843195.811931253.2331958214884 (10)( 10 0 )(1231.97) (124259) lc103827.8610058.031911082.4010300.8641.45lr2021197.672749.398851197.672749.39351.09 (10) 230.17) (89.08 55173) (55173) lc104861.9510006.91254865.9410009.2578.02lr203949.402762.801950949.40276280283.44 (144.95) (9)(143.31) (81340) (81340) lc10582894982894478289498289429.09lr204849051988.572655849.051988.5763984 (10)(0) (10)(0) (2)(139.52) (139.52) lc10682894982894438289498289431.54lr2051054022550.135851054.02250.13252.11 第1期 潘立军.等:求解带时间窗取送货问题的遗传算法 125 表2续表 Li and lim 4 本文算法 Li and lim( 本文算法 问题 问题 号D Dur(W) CPU Dur(W)CPU号DDur(W)CPU命D(V)Dur(W)CPU (V) 10 (496.11) (496.1) lc10782894982894548289498289135.21lr206931.632502.16717931.632502.16391.81 (10)(0) (10)(0) (570.84) (570.84) lc108826.449826.4482826.449826.4461.41lr207903.061936.44159490306193644304.63 (10)(0) (33.38) (33.38) lc10982782983178255827.829831.78155.31lr208743851858.363572738.871849.67503.16 (10)(3.96) (11080) lc201591.569591.5627591.569591564869lr209937052432.61277:930.782405.01316.72 (47432) lc202591.569591.5694591.569591.5683.4llr210964.222782.061482970.54278206280.25 (3)*(0) 81783) (81152) lc203585.569521.66145591.179601.72150.98l211927.81954.574204911.491920.34438.5 (3)(26.09) (3)(10.54) (2)(2677) (885 lc204591.179591.17746591.179591.17252.34lrcl011708802956.321191708802956.3225.33 (14)(247.52) (14)*(24752) lc205588889588881905888895888886.67lrc1021563.552764.141521558.072703924205 (13)(200.59) (12)(14585 lc2065884995881988588.199588.19181.2lrcl031258.742443.6817512587421136810.36 (11)(184.95) (11)*(184.95) lc207588.299660.4102588299588.52203.44lrc1041128.402238.172021128.402238.1753.48 (0) (10)( lc208588.329744.23178588.329744.23272.17lrc1051637.622830.161791637.622830.1628.19 155.91) (3)*(155.91) (13)(19254) (19254) lr1011650.783599.45871650.783599.4519lrc1061425.532475.014591424.732474.225983 948.6 (11)(49.49 lr1021487.573202.4611681487.573202.4643.56lrc1071230.152344.941541230.152344.9468.08 (17)(714.89) 714.89 (11)(114.8) (11)*(1148 lr1031292682729.151691292.682729.1538.48lrc1081147.972245.36501147,432244.7665.3 (13)*(436.48 l1041013.392050.854591013.392050.8570.94lrc2011468.963358.412661421.203358.4110986 3746) 37.46) (4)(889.45) 93721) lr1051377.112631.56691377.112631.5628.81lrc2021374.272657.149871374.272657.14180.42 (25445) 4)(254.45) 28287) )*(28287) lr1061252.622412.11871252.622412.1129.06lrc2031089.072700.316051089072700.318688 (159.49) (12)(159.49 (3)(611.23) (61123) lr1071111.312220.272871111.312220.2733.03lrc204827.782537.833634827.782537.83478.05 (10)(108.96) (10)(108.96) 710.05) (710.05) lr10896897202993415968.972029.9346.19lrc2051302.23464.616391302.23464.61185.44 (9)(60.96) (60.96 (4)(1162.41) (116241) lr1091239962311.373481239.962311.3742.61lrc2061162.912444.874451159.06244490133.83 126 系统工程理论与实践 第32卷 表2续表 Li and lim 4 本文算法 Li and lim( 本文算法 问题 问题 号D Dur(W) CPU Dur(W)CPU号DDur(W)CPU命D(V)Dur(W)CPU (V) (11)(71.42) (11)(71.42 (281.96) (28584) 1101159.352222995471159.3522229951.89lrc2071121.62461.126071062052417.5128854 (10)(63.64) (10)(63.64) (3)3682) (355.46) lr111110892189.53179110892189.5338.09lrc208852.762271.194106918.6823440445685 (10)(80.63) (10)(80.63) (3)(41844) (42536) 注:D=总路长;V=使用年辆数量;Dmr=总时长:W=总等待时间;CPU·=算法运行时间(单位为秒),基于平台为Tmx Kernel2215-5.0 smp on if686;CPU=10次运算的平均时间(单位为秒),基于的平台为 XP on Pentium Iv2.0G;*表示 与IIA的结果相当,加粗表示优于IA的结果 参考文献 1 Dantzig G B, Ramser J II. The truck dispatching problemJ. 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 combincd ship scheduling and allocation problcm J Journal Opcration Rcscarch Society2000,51:834842 4 Li H, Iim A. A metaheurist ic for the pickup and delivery problem with time windows[Cl//13th TFEE 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-st age hybrid algorithm for pickup and delivery vehicle routing problems with time windowsJ. Compute Operation Research, 2006, 33: 875-893 Savelsbergh M W P, Sol M. The general pickup and delivery problemJ]. 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. The University of Michigan Press, Ann, 1975 1l Goldberg D E, Korb B, Deb K. Messy genetic algorithms: motivation, analysis, and first result[J. Complex Systems,1990,3:493530

...展开详情
试读 7P 论文研究-求解带时间窗取送货问题的遗传算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_38743481 欢迎大家使用并留下宝贵意见
2019-09-20
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

    成功上传501个资源即可获取
关注 私信
上传资源赚积分or赚钱
最新推荐
论文研究-求解带时间窗取送货问题的遗传算法.pdf 13积分/C币 立即下载
1/7
论文研究-求解带时间窗取送货问题的遗传算法.pdf第1页
论文研究-求解带时间窗取送货问题的遗传算法.pdf第2页

试读结束, 可继续读1页

13积分/C币 立即下载 >