实例介绍
【实例简介】
时间窗的车辆路径问题进行研究，建立以最小化车辆数量和行驶路程为目标的多目标数学模型，提出一 种结合改进差分进化算法和变邻域下降搜索的基于Pareto支配的混合差分进化算法。首先重新定义了个体的生成 方式。其次，结合双种群策略和变邻域下降搜索技术来平衡算法的全局探索能力和局部开发能力，并在搜索过程中用 随机个体替代种群中的重复个体，维持种群的多样性。然后引入Pareto支配的概念来评价个体的优劣性，并采用擂 台法则构造非支配解集
其中,N是种群规模,gem为当前进化代数, gem为最大进化按照这种方法,直到所有的顾客都被服务。这种解码方法可 代数。 以使解码后的路径和解码前染色体中所对应的路径方案· 在进化过程中,采用双种群机制,使算法既能从局部极值致,并且使用车辆的数量可以在解码过程中灵活动态地获得, 的邻域跳转到全局最优解的邻域,又能在全局最优解的邻域从而实现对车辆数量的自动寻优。例如染色体串361857 内进行精细搜索,在每代进化完后通过子种群重组实现信息294,经过路径解码为:路线1:0→3→-6→0;路线2:0→1→8 交流和融合,平衡算法的全局探索能力和局部开发能力 →57→0;路线3:0→2→9-4→0 随着进化过程的进行,种群中的个体会趋于一致,因此在3.3.2初始种群生成 每次执行完变异、交义、选择操作后,采用随机个体替换掉种 产生初始种群时,为了保证种群的多样性,其中90%的 群中的重复个体,维持种群的多样性,以增强种群的全局探索个体采用N个顾客节点随机排列的方式来产生,应用前向插 能力,然后从种群中随机选取若干个个体进行变邻域下降搜启发式算法(PFH)来生成剩下10%的个体。 索进一步提高算法的局部开发能力降低算法陷入局部最优3.3.3变异操作 的风险。 鉴于标准差分进化算法采用实数编码,不能直接应用于 3.2算法步骤 VRPW问题,由于采用了自然数编码,因此重新设计了变异 基丁以上的算法思想描述,混合差分进化算法的具体步操作方式来产生变异个体。由标准DE算法可知,变异个体 骤如下 是由目标种群中随机选择的3个目标个体相互作用的结果 步骤1设置算法的相关参数,生成算法的初始种群设记x=[x,x2,…,x]V=[1,2, 进化代数gen=0; [uE,1,t2,…,n]分别为第G代目标种群变异种群和试验 步骤2根据 Pareto支配思想对种群中的个体适应值进种群的第z个个体。 行评价,利用擂台法则和拥挤距离机制将种群个体分层排序, (1)P1子种群采用“DE/best/1”变异策略,重新定义 得到每个个体的非支配层等级和拥挤距离值; v=g(F⑧g(x,Y),X) 步骤3按照个体的非支配层等级和拥挤距离,并根据式中,1r2是区间[1,n里互不相等的整数;X是当前目 式(12)式(13将种群划分为两个不同大小的子群P1和P2 标种群中最好的个体,在本文中从非支配层等级序号最小的 步骤4P1子群执行DE/bes1变异策略,P2子群执行非支配层中随机选取;F为缩放因子,且F∈[0,门 DE/rand/1变异策略,并根据3.3.4节执行交叉操作; 式(14)由两部分组成,第一部分为 步骤5将初始种群与子群P1、P2重组为一个混合种 △=F⑧g(X°,Y) 群 g(班,X),rand()<F (15 步骤6对混合种群多次使用擂台法则构造多层非支配 rand()≥F 集 通过式(15)产生一个扰动个体,其中g(班,)的实现 步骤7对多层非支配集,使用基于非支配层等级和拥过程如下:①从中随机选择一段基因,将其放在M%的前 挤距离的选择操作生成下一代目标种群 面或者后面;②删除X"与该段基因相同的顾客 步骤8用随机个体替代新一代目标种群中的重复个 第二部分由=g(△°,Xx:)构成,其实现方法与g 体,以保证种群的多样性; (X,X)相同 步骤9从月标种群中随机选取若干个个体执行变邻域 (2)P2子种群采用“DE/rand/1”变异策略,重新定义 下降搜索,根据 Pareto支配思想评价个体并更新种群; V=g(FQg(‰,X),X) (16) 步骤10判断是否满足终止条件gen≤ gen,如果是, 式(16)的具体操作过程与P1子群的操作过程类似 则输出 Pareto非支配解集,算法结束;如果否,则转至步骤3,3.3.4交叉操作 gem=gen+1。 交叉操作是通过变异个体和日标个体之间的交叉作用来 3.3改进差分进化算法 产生试验个体 3.3.1染色体編码设计及路径解码 U=CR凶g(V,x) 本文算法中的染色体编码采用自然数编码机制,用(l1 g(V,Xi), rando<CR (17) l2,23,…,l2,…,Ln)表示一条染色体,其中染色体中的每个基 rand(≥CR 因位L1代表一个顾客点,L是[1,n]之间的一个不重复的自然式中,CR为交叉概率且CR∈[0,1],g(W,x)的操作方式 数,基因位间自然数的顺序体现了车辆访问顾客点的次序这与g(X,Y)相同。 样的编码方式满足了每个顾客点只能被车辆访问一次的约3.3.5选择操作 束。该种编码方式的染色体中没有作为子路径分隔符的基因 在单目标优化中,标准DE采用一对一竞争的选择操作 位,这样就不需要预先估计所使用的车辆数量 方式来生成下一代日标个体但是不适合直接用在多目标优 由于此种编码方式不能从染色体中直接得到问题的解,化问题中。在本文中,当目标个体生成试验个体时,不比较它 即问题的调度方案因此设计一种解码算子来将染色体转换们之间的优劣,而是在两个目标子种群中的个体都产生试验 成可行的行驶路径。解码时按照染色体中基因位上的白然数个体后,将初始种群与两个试验了种群合并成混合种群;然后 排列顺序依次将每个自然数表示的顾客点插入到路径中,当使用基于非支[层等级和拥挤距离的选择操作从混合种 插入某个顾客点违反了时间窗约東或者车辆最大载重量约束群中选择下一代目标种群。使用这种选择操作力式可以实现 时,就重新使用一辆车来服务该顾客点,开辟一条新的路径,精英保留策略,从而加快算法的收敛速度。 ·222· 3.4变邻域下降搜索 标都是服从聚类分布的;R类问题中的所有顾客点坐标则全 变邻域下降搜索的具体步骤:将经过变异、交叉选择操部服从均匀分布;RC类问题中的顾客点则兼有聚类分布和 作之后得到的个体作为初始解选择一种邻域结构进行局部均匀分布的特征。C1,R1、RC1这3类问题的辆最大载重 搜索,直到找到局部最优解;然后再以当前局部最优解为初始量较小且配送中心的时间窗也较窄,因此每辆车能服务的顾 解使用另外一种邻域结构继续进行局部搜索;当任意一种邻客较少;而C2、R2、RC2这3类问题的车辆载重量较大月配送 域结构都不能继续优化当前解时,则结束VN)过程。 中心的时间窗较宽,因此每辆车能服务较多的顾客。 3.4.1邻城结构 本文的实验结果都是通过使用VC++6.0编程,在Inte 在使用变邻域下降搜索前需要定义一组邻域结构。本 Pentium cpue54002.72GHz,2.00GB内存 Windows XP 文采用基于顾客排序的自然数编码方式,因此采用以下2种SP3的主机上运行所得的。本文算法的实验参数设置:对于 邻域结构 25个顾客集,种群规模为40,进化代数 gen为400;对于50 (1)插入( Insert)邻域:在路径序列中随机选择两个不同个顾客集,种群规模为100,进化代数genm为1000;对于100 的位置ab,把位置a对应的顾客插入到位置b上,得到新的个顾客集,种群规模为100,进化代数 genmax为100。VND 路径序列。 搜索的最大迭代次数为100,最大无改进迭代次数为10。P1、 (2)百换(Sup)邻域:在路径序列中随机选择两个不同P子种群的缩放因子F分别取0.4和0.8,交叉概率CR取 的位置a、b,交换这两个位置对应的顾客,得到新的路径序0.08 列 4.1混合算法的性能测试 插人邻域结构对解的结构破坏程度较小,有利于算法的 为∫验证本文所提的混合差分进化算法的性能,分别进 小范闹迁移;互换邻域结构对解的结构破坏程度稍大,可以保行两组实验第一组实验不加人WND,只使用改进的差分进 证解的广域搜索。但插人邻域和互换邻域两种邻域结构的直化算法第二组实验使用本文提出的混合差分进化算法IE 径都相对较小,而在车辆路径问题領域中,局部最优解与全局ⅥND.不失一般性,分别从 Solomon算例的25个顾客集、50 最优解在解空间上的位置彼此比较靠近,因此采用这两种邻个顾客集和100个顾客集中选取18个算例作为实验测试数 域结构可以将搜索操作控制在一个紧凑的解空间里,从而达据,实验结果如表1所列。 到有效的搜索 表1混合启发式算法 IDE VND的性能测试结果 3.4.2VND算法伪码 IDE 算例顾客数 算法1VND 车辆数量厅驶路程车辆数量行驶路程 1.输入初始解x选择一组邻域结构Nk,k=1,2,…,knx;令t=0; C104 211.0 187, 215.5 2. WHIlE t<k do R103 00.9 473.4 4. WhIlE k<=kmax DO 464.4 5.以x为初始解,在Nk定义的邻域中进行局部搜索,直到找到 526 RC1O1 490.3 2 局部最优解x为止; RC20825 269.6 6.IFx支配 X THEN 00.6 99.6 x-x 1 Cl0350 388.2 5 C201 t=0 3 61.8 R101 1063 1046.7 1C t=t+1 IZ 1C72.2 11. END IF 854.0 12.k=k-1 1327.7 904.0 5 993. 8 947.0 13. END WHILE RC294 49. 14. END WHILE 15.输出x算法结束 l00 828.9 在使用一种邻域结构局部搜索时,由于邻域解较多,为了 cecI 603.9 591.6 减少搜索成本,因此设置最人无改进迭代次数来避免对整个 RIC3 100 16 1496.6 5 1235,5 邻域空间的可行解进行穷举搜索,当满足最大无改进迭代次 R2C1100 I557.4 1174.8 数时,则变换另一种邻域结构继续搜索。当达到邻域搜索的 6 1268.7 100 1921.5 1675.1 最大迭代次数时,停止VND搜索。实验采用随机的邻域结 1957 构顺序来进行变邻域下降搜索。 RC205100 8 77.4 2115.5 1461.0 4实验分析 通过表1,从求解具有最短路程的解来看,在2个算例 为了测试算汯的有效性,使用著名的 Solomon算例16作(25个顾客规模算例C201和50个顾客规模算例C201)上 为本文的测试实例。该算例有3种不同规模顾客数(25,50 IDE VND与I求解结果相同,而在其余的算例上,本文算 和100个顾客点)的数据集,每种数据集包含56个测试问题,法 IDE VND的求解结果比不混合VND的IE算法更优;相 并且根据顾客的地理位置分布分为6类:C1、C2、R1、R2、比于 IDE, IDE VND在此类解的行驶路程目标上最大提高 RC1、RC2。其中C类问题中包含多个组,每组中的顾客点坐31.53%,而在此类解的车辆数量目标上最大提高23.08% 223 从求解具有最少车辆数量的解来看,在5个算例(25个顾客值与目前最优解的平均相对偏差较小,均控制在4.5%以内; 规模算例R103,50个顾客规模算例RC01以及100个顾客所有算例的平均值与目前已知最优解的平均值的相对偏差为 规模算例C101、R103RC101)上, IDE VND可以求得比DE2.21%每个算例的标准差相对平均值较小。由此可以看出, 具有更少车辆数量的解;而且在解具有相同车辆数量的情况算法 IDE VND在求解ⅤRTW时具有较强的稳定性。 下, IDE VND求得的路程更短。由此可以得出,将DE和 以算例R101(50个顾客)为例,给出了DE和 IDE VND ND混合是有效的。 的运行收敛情况,如图1所示。从图中可以看出,不论是在行 为了更好地验证 IDE VND算法的稳定性,本文对每个驶路程上还是在车辆数量上, IDE VND的收敛速度均快于 算例分别求解20次。表2给出20次实验的统计结果,主要mDE,并且在收敛结果的质量上也好于IE。 列举了各算例在行驶路程目标上20次求解得到的最优解的 平均值、平均值与已知最优解之间的相对偏差以及标准差 IDE\ 1300 表2对每个算例求解20次得到的平均结果 算例 顾客数已知最 DEVD运行20次的结果 优解平均值平均相对偏差标准差 C104 186.91 188.z 0.70% l.22 214.7215.5 0.37% 0 454.6461.6 1.54% 6.43 进化代数 进化代数 25463.3 0.24 0 RC101 61.1468.0 1.50% 图1算例R101(50个顾客)的收敛情况 R 269.1270.7 0.59% 1.67 Clo 0.22% 4.2与现有算法的对比实验 0.44% 为进一步验证本文算法的性能,将算法 IDE VND求得 R 1049.6 0.54% R201 50 791.9 1.39 的最优解及20次平均值分别与文献[17中的ABC(人工蜂 RC101 944958.5 1.53% 群算法)算法和已知最优解的结果进行比较结果如表3所 RC204 444.2459.5 3.44% 7.47 c101 1c0 837.3828.9 0.19% 0 列。表中平均值为20次运行中所得到的所有非支配解分别 RC201 100 589.1 59l.6 0.42% 0 在车辆数量和行驶路程上的平均值;最后一列的相对偏差表 R103 1001208.71252,9 3.66% 11.18 R201 1143.21188.2 3.94% 12.60 示的是本文算法的最优解与已知最优解在车辆数量和行驶路 RClo11001619.81690.2 4.35% 8.91 程两个日标上的差距,可采用式(18)计算 RC205100 1154 1201.3 4.10% 16.80 相对偏差=(最优解一已知最优解)*100%已知最优解 从表2可以看出, IDE VND算法求解每个算例的平均 (18) 表3算法 IDE VND和现有算法在不同规模算例上的实验结果比较 DE VND 算例顾客 ABC 最优解 平均值 最优解 平均值 已知最优解 数 相对偏差 车辆数辆行驶路程车辆数量行驶路程车辆数辆行驶路程车辆数量行驶路程车辆数量行驶路程 C104 25 187.5 189,0 3 187.5 188.23 186.90.00%0.32% C2CI 215.5 2 216.7 215.5 2 2155 214.70.00%0.37% R103 5455.74, 461.6 454.6C.00%0.24% 479.2 5.4 468.1 473.4 4.7 61.6 20.00%4.14% R201 464.4 3.6 464.4 463.30.00%0.24% 3.6 526.8 501.8 50.00%13.71% RCIO 25 463.6 4.9 462.24.3468.0 4 461.10.00% % RC208 2 269.6 2 270.8 269.10.00%0.19% 309.6 293.4 50.00%15.05% C10350 392.2 6.1 439.9 362.2 362.2 361.40.00%0.22% C∠01l 50 373.8 3.8 411.5 361.8 2.5 337,2 360.20.00%0.44% 387.2 33.33%23.54% R10150 131049.513.11081.8 1046.7 122 1049.6 10440.00%0.26% 1061,213.1 1081.8 829.8 7.4 872.7 6 794.3 902.5 791.90.00%0.30% 872.8 7.4 872.7 3 904.0 902.5 -50.00%14.16% RC101 50 986.6 8 947.0 958.5 8 9440.00%0.32% 9 982.6 986,6 RC20450 508,1 449.22. 474.4 44.20.00%1.13% 508.l 483.02.5 474.4 33.33%8.73% 100 10828.910.2846.2 828.9 10827.30.00%0.19% C201100 618.6 591.6 591.6 589.10.00%0.42% 00 1264.5 153 273.9 1235.515.31252.9 1208.715.38%2.22% R201 100 1227.210.81245.9 1174.8 61245.181143.212.50%276% 1261.710.81245.9 1268.7 6 1245. 5.00%10.98% RC101100 l698 1821734.1 17 1675.1 17.2 1690.2 1619.813.33%3.41% RC20510 1221.68.91249.3 81177.47.61312.3 14.29%2.039 1249.7 8.9 1249.3 461.0 7.6 1312.3 8.57%26.60% 在表3中,从最小化行驶路程的目标来看,DE_ND在6个算例(25个顾客规模算例C104、C201、R103、R201、 224 RC208和100个顾客规模算例C101)上与ABC求解结果相的局部寻优能力,提高了算法的求解质量,加速了算法的收 同,在其余算例上 IDE VND的求解质量优于ABC;相比于敛。最后对18个不同规模的 Solomon算例进行实验测试结 ABC, IDE VND的求解质量最大提高7.65%;并且ⅢE_果表明本文算法是求解 VRPTW的一种有效方法,为 VND与已知最优解的相对偏差均控制在3.5%以内。从最 VRPTW提供了一种新的求解思路,同时对研究其他类型的 小化车辆数量的目标来看,DVD在9个算例(25个顾客车辆路径问题具有一定的借鉴意义。 规模算例R201、RC208,50个顾客规模算例C201、R201、 参考文献 RC101以及100个顾客规模算例C201、R201、RCl1 RC205)F可以找到比ABC具有更少车辆数量的解;与已知[1] Dantzig G, Ramser J. The truck dispatching problem[Mna 最优解相比, IDE VND可以在8个算例(25个顾客规模算例 gement Science, 1959(6):80-91 [2] Jung S, Moon B. R A Hybrid genetic algorithm for the vehicle R103,R201、RC208,50个顾客规模算例C201、R201、RC204 routing problem with time windows[Cl/Proceedings of Genctic 以及100个顾客规模算例R201、RC205)上找到具有更少车 and Evolutionary Computation. San Francisco, CA, USA, 2002 辆数量的解。从20次运行所得的非支配解的平均值来看,在 1309-1316 具有唯一解的算例中, IDE VND的优势相比ABC更加明显;[3] Balseiro SR An ant colony algorithm hybridized with insertion 在一些具有多个非支配解的算例中,ABC的行驶路程的平均 heuristics for the time dependent vehicle routing problem with 值优于 IDE VND的行驶路程的平均值,而在车辆数量的平 time windows[J]. Computers and Operations Research, 2011, 38 均值上要劣于DE_VND,原因是 IDE VND可以求得更少的 车辆数量但是相对增加了行驶路程在车辆数量平均值和行[1]魏明,靳文舟求解车辆路径问题的离散粒子群算法计算机 科学,2010,37(4):187-191 驶路程平均值上, IDE VND相比于ABC分别最大提高39 [5 Ston R Differential evolution design of an IIR-filter [Cl//Pro- 19%和17.66%。 lings of IEEE Conference Evolutionary Computation 由此表明, IDE VND算法充分利用了差分进化算法较 (S07803-29023). Nagoya, Japan,1996:268-273 强的全局搜索能力和双种群的协同搜索能力;同时变邻域下[6]MiMi, Xue Hui-feng, Zhong ming,eta. An improved differen- 降搜索有效地增强了算法的局部开发能力,避免了算法过早 tial evolution algorithm for TSP problem[Cl/Proceedings of 陷人局部最优,提高了算法的求解质量。 Intelligent Computation Technology and Automation. Washing- 图2—图4给出了3种算法以25个顾客规模算例R201 ton do,USA,2010:544547 [7] Onwubolu G, Davendra D Scheduling flow shops using differen- 50个顾客规模算例R201以及100个顾客规模算例RC205 tial evolution algorithm [J]. European Journal of Operational 为例的 Pareto前沿对比情况。比较3种算法可以看出,在 Research,2006,171(2);674-69 Pareto解的数量和质量上, IDE VND具有更加明显的优势,[8]曹二保赖明勇,聂凯带时间窗的车辆路径问题的改进差分进 所求得的 Pareto前沿更加逼近实际 Pareto前沿。 化算法研究[].系统仿真学报,2009,21(8):2420-2423 700 DDE VND [9]王君.带时间窗车辆路径问题的差分进化混合算法[门].计算机 IDE VND - IDE IDE 工程与应用,2013,49(2):2428,66 600 [10] Babu B V, Jehan MM L. Differential evolution for multi-objec- tive optimization[c]//Proceedings of the IEEE Congress on Evo- lutionary Computation(CEC 2003 ). Canberra, Australia, 2003 26962703 车辆数量 车辆数量 [11] Hansen P, Mladenovic N. Variable neighburhood search: princi- 图2算例R201(25个顾客)中的图3算例R201(50个顾客)中 ples and applications [J]. European Journal of Operational Re- Parcto前沿比较 的 Pareto前沿比较 search,2001,130(3):449-467 [12]陈萍,黄厚宽,董兴业求解卸装一体化的车辆路径问题的混合 启发式算法[]计算机学报,2008,31(4):565573 一ABC [13]郑金华,蒋浩,达,等.用擂台法则构造多目标 Pareto最优解 21700 集的方法[J]软件学报,2007,18(6):1287-1297 [14]刘敏多目标遗传算法在车辆路径优化中的应用研究D].湘 潭:湘潭大学,2006 车辆数量 [15] Deb K, Pratap A, Agarwal S, et al. a fast and elitist multiobject- 图4算例RC205(100个顾客)中的 Pareto前沿比较 tive genetic algorithm: NSGA-IILJ] IEEE Transactions on Evo- lutionary Computationl, 2002, 6(2) 结束语本文对带时间窗的车辆路径问题进行了研究,[16]htp:// zeb. cba. neu,edu/~ solomon/ problems.hm 从多目标的角度出发,同等地考虑行驶路程和车辆数量这两[17] Nahum OE, Hadas y, Spiegel U. Multi-objective vehicle routing 个目标,提出一种结合改进差分进化算法和变邻域下降搜索 problem with time windows: a vector evaluated artificial bee colo 的基于 Pareto支配的混合差分进化算法IDE_VND。利用改 ny approach[J]. International Journal of Computer and Informa 进差分进化算法良好的全局探索能力和变邻域下降搜索较强 tion Technology, 2014, 3(1): 41-47 225 一种求解带时间窗车辆路径问题的混合差分进化算法 旧 肟万据 WANEANG DATA文献链接 作者: 宋晓宇,朱加园,孙焕良, SONG Xiao-yu, ZHU Jia-yuan, SUN Huan-1iang 作者单位 沈阳建筑大学信息与控制工程学院沈驲110168 刊名: 计算机科学 STIC PKU 英文刊名: Computer science 年,卷(期): 2014,41(12) 引用本文格式:宋晓宇.朱加园.孙焕良.SCNGⅪiao-ψu. ZHU Jia-yuan. sUN Huan-iang一种求解带时冋窗车路径冋题的混合差分 进化算法[期刊论文]计算机科学2014(12) 【实例截图】
【核心代码】
时间窗的车辆路径问题进行研究，建立以最小化车辆数量和行驶路程为目标的多目标数学模型，提出一 种结合改进差分进化算法和变邻域下降搜索的基于Pareto支配的混合差分进化算法。首先重新定义了个体的生成 方式。其次，结合双种群策略和变邻域下降搜索技术来平衡算法的全局探索能力和局部开发能力，并在搜索过程中用 随机个体替代种群中的重复个体，维持种群的多样性。然后引入Pareto支配的概念来评价个体的优劣性，并采用擂 台法则构造非支配解集
其中,N是种群规模,gem为当前进化代数, gem为最大进化按照这种方法,直到所有的顾客都被服务。这种解码方法可 代数。 以使解码后的路径和解码前染色体中所对应的路径方案· 在进化过程中,采用双种群机制,使算法既能从局部极值致,并且使用车辆的数量可以在解码过程中灵活动态地获得, 的邻域跳转到全局最优解的邻域,又能在全局最优解的邻域从而实现对车辆数量的自动寻优。例如染色体串361857 内进行精细搜索,在每代进化完后通过子种群重组实现信息294,经过路径解码为:路线1:0→3→-6→0;路线2:0→1→8 交流和融合,平衡算法的全局探索能力和局部开发能力 →57→0;路线3:0→2→9-4→0 随着进化过程的进行,种群中的个体会趋于一致,因此在3.3.2初始种群生成 每次执行完变异、交义、选择操作后,采用随机个体替换掉种 产生初始种群时,为了保证种群的多样性,其中90%的 群中的重复个体,维持种群的多样性,以增强种群的全局探索个体采用N个顾客节点随机排列的方式来产生,应用前向插 能力,然后从种群中随机选取若干个个体进行变邻域下降搜启发式算法(PFH)来生成剩下10%的个体。 索进一步提高算法的局部开发能力降低算法陷入局部最优3.3.3变异操作 的风险。 鉴于标准差分进化算法采用实数编码,不能直接应用于 3.2算法步骤 VRPW问题,由于采用了自然数编码,因此重新设计了变异 基丁以上的算法思想描述,混合差分进化算法的具体步操作方式来产生变异个体。由标准DE算法可知,变异个体 骤如下 是由目标种群中随机选择的3个目标个体相互作用的结果 步骤1设置算法的相关参数,生成算法的初始种群设记x=[x,x2,…,x]V=[1,2, 进化代数gen=0; [uE,1,t2,…,n]分别为第G代目标种群变异种群和试验 步骤2根据 Pareto支配思想对种群中的个体适应值进种群的第z个个体。 行评价,利用擂台法则和拥挤距离机制将种群个体分层排序, (1)P1子种群采用“DE/best/1”变异策略,重新定义 得到每个个体的非支配层等级和拥挤距离值; v=g(F⑧g(x,Y),X) 步骤3按照个体的非支配层等级和拥挤距离,并根据式中,1r2是区间[1,n里互不相等的整数;X是当前目 式(12)式(13将种群划分为两个不同大小的子群P1和P2 标种群中最好的个体,在本文中从非支配层等级序号最小的 步骤4P1子群执行DE/bes1变异策略,P2子群执行非支配层中随机选取;F为缩放因子,且F∈[0,门 DE/rand/1变异策略,并根据3.3.4节执行交叉操作; 式(14)由两部分组成,第一部分为 步骤5将初始种群与子群P1、P2重组为一个混合种 △=F⑧g(X°,Y) 群 g(班,X),rand()<F (15 步骤6对混合种群多次使用擂台法则构造多层非支配 rand()≥F 集 通过式(15)产生一个扰动个体,其中g(班,)的实现 步骤7对多层非支配集,使用基于非支配层等级和拥过程如下:①从中随机选择一段基因,将其放在M%的前 挤距离的选择操作生成下一代目标种群 面或者后面;②删除X"与该段基因相同的顾客 步骤8用随机个体替代新一代目标种群中的重复个 第二部分由=g(△°,Xx:)构成,其实现方法与g 体,以保证种群的多样性; (X,X)相同 步骤9从月标种群中随机选取若干个个体执行变邻域 (2)P2子种群采用“DE/rand/1”变异策略,重新定义 下降搜索,根据 Pareto支配思想评价个体并更新种群; V=g(FQg(‰,X),X) (16) 步骤10判断是否满足终止条件gen≤ gen,如果是, 式(16)的具体操作过程与P1子群的操作过程类似 则输出 Pareto非支配解集,算法结束;如果否,则转至步骤3,3.3.4交叉操作 gem=gen+1。 交叉操作是通过变异个体和日标个体之间的交叉作用来 3.3改进差分进化算法 产生试验个体 3.3.1染色体編码设计及路径解码 U=CR凶g(V,x) 本文算法中的染色体编码采用自然数编码机制,用(l1 g(V,Xi), rando<CR (17) l2,23,…,l2,…,Ln)表示一条染色体,其中染色体中的每个基 rand(≥CR 因位L1代表一个顾客点,L是[1,n]之间的一个不重复的自然式中,CR为交叉概率且CR∈[0,1],g(W,x)的操作方式 数,基因位间自然数的顺序体现了车辆访问顾客点的次序这与g(X,Y)相同。 样的编码方式满足了每个顾客点只能被车辆访问一次的约3.3.5选择操作 束。该种编码方式的染色体中没有作为子路径分隔符的基因 在单目标优化中,标准DE采用一对一竞争的选择操作 位,这样就不需要预先估计所使用的车辆数量 方式来生成下一代日标个体但是不适合直接用在多目标优 由于此种编码方式不能从染色体中直接得到问题的解,化问题中。在本文中,当目标个体生成试验个体时,不比较它 即问题的调度方案因此设计一种解码算子来将染色体转换们之间的优劣,而是在两个目标子种群中的个体都产生试验 成可行的行驶路径。解码时按照染色体中基因位上的白然数个体后,将初始种群与两个试验了种群合并成混合种群;然后 排列顺序依次将每个自然数表示的顾客点插入到路径中,当使用基于非支[层等级和拥挤距离的选择操作从混合种 插入某个顾客点违反了时间窗约東或者车辆最大载重量约束群中选择下一代目标种群。使用这种选择操作力式可以实现 时,就重新使用一辆车来服务该顾客点,开辟一条新的路径,精英保留策略,从而加快算法的收敛速度。 ·222· 3.4变邻域下降搜索 标都是服从聚类分布的;R类问题中的所有顾客点坐标则全 变邻域下降搜索的具体步骤:将经过变异、交叉选择操部服从均匀分布;RC类问题中的顾客点则兼有聚类分布和 作之后得到的个体作为初始解选择一种邻域结构进行局部均匀分布的特征。C1,R1、RC1这3类问题的辆最大载重 搜索,直到找到局部最优解;然后再以当前局部最优解为初始量较小且配送中心的时间窗也较窄,因此每辆车能服务的顾 解使用另外一种邻域结构继续进行局部搜索;当任意一种邻客较少;而C2、R2、RC2这3类问题的车辆载重量较大月配送 域结构都不能继续优化当前解时,则结束VN)过程。 中心的时间窗较宽,因此每辆车能服务较多的顾客。 3.4.1邻城结构 本文的实验结果都是通过使用VC++6.0编程,在Inte 在使用变邻域下降搜索前需要定义一组邻域结构。本 Pentium cpue54002.72GHz,2.00GB内存 Windows XP 文采用基于顾客排序的自然数编码方式,因此采用以下2种SP3的主机上运行所得的。本文算法的实验参数设置:对于 邻域结构 25个顾客集,种群规模为40,进化代数 gen为400;对于50 (1)插入( Insert)邻域:在路径序列中随机选择两个不同个顾客集,种群规模为100,进化代数genm为1000;对于100 的位置ab,把位置a对应的顾客插入到位置b上,得到新的个顾客集,种群规模为100,进化代数 genmax为100。VND 路径序列。 搜索的最大迭代次数为100,最大无改进迭代次数为10。P1、 (2)百换(Sup)邻域:在路径序列中随机选择两个不同P子种群的缩放因子F分别取0.4和0.8,交叉概率CR取 的位置a、b,交换这两个位置对应的顾客,得到新的路径序0.08 列 4.1混合算法的性能测试 插人邻域结构对解的结构破坏程度较小,有利于算法的 为∫验证本文所提的混合差分进化算法的性能,分别进 小范闹迁移;互换邻域结构对解的结构破坏程度稍大,可以保行两组实验第一组实验不加人WND,只使用改进的差分进 证解的广域搜索。但插人邻域和互换邻域两种邻域结构的直化算法第二组实验使用本文提出的混合差分进化算法IE 径都相对较小,而在车辆路径问题領域中,局部最优解与全局ⅥND.不失一般性,分别从 Solomon算例的25个顾客集、50 最优解在解空间上的位置彼此比较靠近,因此采用这两种邻个顾客集和100个顾客集中选取18个算例作为实验测试数 域结构可以将搜索操作控制在一个紧凑的解空间里,从而达据,实验结果如表1所列。 到有效的搜索 表1混合启发式算法 IDE VND的性能测试结果 3.4.2VND算法伪码 IDE 算例顾客数 算法1VND 车辆数量厅驶路程车辆数量行驶路程 1.输入初始解x选择一组邻域结构Nk,k=1,2,…,knx;令t=0; C104 211.0 187, 215.5 2. WHIlE t<k do R103 00.9 473.4 4. WhIlE k<=kmax DO 464.4 5.以x为初始解,在Nk定义的邻域中进行局部搜索,直到找到 526 RC1O1 490.3 2 局部最优解x为止; RC20825 269.6 6.IFx支配 X THEN 00.6 99.6 x-x 1 Cl0350 388.2 5 C201 t=0 3 61.8 R101 1063 1046.7 1C t=t+1 IZ 1C72.2 11. END IF 854.0 12.k=k-1 1327.7 904.0 5 993. 8 947.0 13. END WHILE RC294 49. 14. END WHILE 15.输出x算法结束 l00 828.9 在使用一种邻域结构局部搜索时,由于邻域解较多,为了 cecI 603.9 591.6 减少搜索成本,因此设置最人无改进迭代次数来避免对整个 RIC3 100 16 1496.6 5 1235,5 邻域空间的可行解进行穷举搜索,当满足最大无改进迭代次 R2C1100 I557.4 1174.8 数时,则变换另一种邻域结构继续搜索。当达到邻域搜索的 6 1268.7 100 1921.5 1675.1 最大迭代次数时,停止VND搜索。实验采用随机的邻域结 1957 构顺序来进行变邻域下降搜索。 RC205100 8 77.4 2115.5 1461.0 4实验分析 通过表1,从求解具有最短路程的解来看,在2个算例 为了测试算汯的有效性,使用著名的 Solomon算例16作(25个顾客规模算例C201和50个顾客规模算例C201)上 为本文的测试实例。该算例有3种不同规模顾客数(25,50 IDE VND与I求解结果相同,而在其余的算例上,本文算 和100个顾客点)的数据集,每种数据集包含56个测试问题,法 IDE VND的求解结果比不混合VND的IE算法更优;相 并且根据顾客的地理位置分布分为6类:C1、C2、R1、R2、比于 IDE, IDE VND在此类解的行驶路程目标上最大提高 RC1、RC2。其中C类问题中包含多个组,每组中的顾客点坐31.53%,而在此类解的车辆数量目标上最大提高23.08% 223 从求解具有最少车辆数量的解来看,在5个算例(25个顾客值与目前最优解的平均相对偏差较小,均控制在4.5%以内; 规模算例R103,50个顾客规模算例RC01以及100个顾客所有算例的平均值与目前已知最优解的平均值的相对偏差为 规模算例C101、R103RC101)上, IDE VND可以求得比DE2.21%每个算例的标准差相对平均值较小。由此可以看出, 具有更少车辆数量的解;而且在解具有相同车辆数量的情况算法 IDE VND在求解ⅤRTW时具有较强的稳定性。 下, IDE VND求得的路程更短。由此可以得出,将DE和 以算例R101(50个顾客)为例,给出了DE和 IDE VND ND混合是有效的。 的运行收敛情况,如图1所示。从图中可以看出,不论是在行 为了更好地验证 IDE VND算法的稳定性,本文对每个驶路程上还是在车辆数量上, IDE VND的收敛速度均快于 算例分别求解20次。表2给出20次实验的统计结果,主要mDE,并且在收敛结果的质量上也好于IE。 列举了各算例在行驶路程目标上20次求解得到的最优解的 平均值、平均值与已知最优解之间的相对偏差以及标准差 IDE\ 1300 表2对每个算例求解20次得到的平均结果 算例 顾客数已知最 DEVD运行20次的结果 优解平均值平均相对偏差标准差 C104 186.91 188.z 0.70% l.22 214.7215.5 0.37% 0 454.6461.6 1.54% 6.43 进化代数 进化代数 25463.3 0.24 0 RC101 61.1468.0 1.50% 图1算例R101(50个顾客)的收敛情况 R 269.1270.7 0.59% 1.67 Clo 0.22% 4.2与现有算法的对比实验 0.44% 为进一步验证本文算法的性能,将算法 IDE VND求得 R 1049.6 0.54% R201 50 791.9 1.39 的最优解及20次平均值分别与文献[17中的ABC(人工蜂 RC101 944958.5 1.53% 群算法)算法和已知最优解的结果进行比较结果如表3所 RC204 444.2459.5 3.44% 7.47 c101 1c0 837.3828.9 0.19% 0 列。表中平均值为20次运行中所得到的所有非支配解分别 RC201 100 589.1 59l.6 0.42% 0 在车辆数量和行驶路程上的平均值;最后一列的相对偏差表 R103 1001208.71252,9 3.66% 11.18 R201 1143.21188.2 3.94% 12.60 示的是本文算法的最优解与已知最优解在车辆数量和行驶路 RClo11001619.81690.2 4.35% 8.91 程两个日标上的差距,可采用式(18)计算 RC205100 1154 1201.3 4.10% 16.80 相对偏差=(最优解一已知最优解)*100%已知最优解 从表2可以看出, IDE VND算法求解每个算例的平均 (18) 表3算法 IDE VND和现有算法在不同规模算例上的实验结果比较 DE VND 算例顾客 ABC 最优解 平均值 最优解 平均值 已知最优解 数 相对偏差 车辆数辆行驶路程车辆数量行驶路程车辆数辆行驶路程车辆数量行驶路程车辆数量行驶路程 C104 25 187.5 189,0 3 187.5 188.23 186.90.00%0.32% C2CI 215.5 2 216.7 215.5 2 2155 214.70.00%0.37% R103 5455.74, 461.6 454.6C.00%0.24% 479.2 5.4 468.1 473.4 4.7 61.6 20.00%4.14% R201 464.4 3.6 464.4 463.30.00%0.24% 3.6 526.8 501.8 50.00%13.71% RCIO 25 463.6 4.9 462.24.3468.0 4 461.10.00% % RC208 2 269.6 2 270.8 269.10.00%0.19% 309.6 293.4 50.00%15.05% C10350 392.2 6.1 439.9 362.2 362.2 361.40.00%0.22% C∠01l 50 373.8 3.8 411.5 361.8 2.5 337,2 360.20.00%0.44% 387.2 33.33%23.54% R10150 131049.513.11081.8 1046.7 122 1049.6 10440.00%0.26% 1061,213.1 1081.8 829.8 7.4 872.7 6 794.3 902.5 791.90.00%0.30% 872.8 7.4 872.7 3 904.0 902.5 -50.00%14.16% RC101 50 986.6 8 947.0 958.5 8 9440.00%0.32% 9 982.6 986,6 RC20450 508,1 449.22. 474.4 44.20.00%1.13% 508.l 483.02.5 474.4 33.33%8.73% 100 10828.910.2846.2 828.9 10827.30.00%0.19% C201100 618.6 591.6 591.6 589.10.00%0.42% 00 1264.5 153 273.9 1235.515.31252.9 1208.715.38%2.22% R201 100 1227.210.81245.9 1174.8 61245.181143.212.50%276% 1261.710.81245.9 1268.7 6 1245. 5.00%10.98% RC101100 l698 1821734.1 17 1675.1 17.2 1690.2 1619.813.33%3.41% RC20510 1221.68.91249.3 81177.47.61312.3 14.29%2.039 1249.7 8.9 1249.3 461.0 7.6 1312.3 8.57%26.60% 在表3中,从最小化行驶路程的目标来看,DE_ND在6个算例(25个顾客规模算例C104、C201、R103、R201、 224 RC208和100个顾客规模算例C101)上与ABC求解结果相的局部寻优能力,提高了算法的求解质量,加速了算法的收 同,在其余算例上 IDE VND的求解质量优于ABC;相比于敛。最后对18个不同规模的 Solomon算例进行实验测试结 ABC, IDE VND的求解质量最大提高7.65%;并且ⅢE_果表明本文算法是求解 VRPTW的一种有效方法,为 VND与已知最优解的相对偏差均控制在3.5%以内。从最 VRPTW提供了一种新的求解思路,同时对研究其他类型的 小化车辆数量的目标来看,DVD在9个算例(25个顾客车辆路径问题具有一定的借鉴意义。 规模算例R201、RC208,50个顾客规模算例C201、R201、 参考文献 RC101以及100个顾客规模算例C201、R201、RCl1 RC205)F可以找到比ABC具有更少车辆数量的解;与已知[1] Dantzig G, Ramser J. The truck dispatching problem[Mna 最优解相比, IDE VND可以在8个算例(25个顾客规模算例 gement Science, 1959(6):80-91 [2] Jung S, Moon B. R A Hybrid genetic algorithm for the vehicle R103,R201、RC208,50个顾客规模算例C201、R201、RC204 routing problem with time windows[Cl/Proceedings of Genctic 以及100个顾客规模算例R201、RC205)上找到具有更少车 and Evolutionary Computation. San Francisco, CA, USA, 2002 辆数量的解。从20次运行所得的非支配解的平均值来看,在 1309-1316 具有唯一解的算例中, IDE VND的优势相比ABC更加明显;[3] Balseiro SR An ant colony algorithm hybridized with insertion 在一些具有多个非支配解的算例中,ABC的行驶路程的平均 heuristics for the time dependent vehicle routing problem with 值优于 IDE VND的行驶路程的平均值,而在车辆数量的平 time windows[J]. Computers and Operations Research, 2011, 38 均值上要劣于DE_VND,原因是 IDE VND可以求得更少的 车辆数量但是相对增加了行驶路程在车辆数量平均值和行[1]魏明,靳文舟求解车辆路径问题的离散粒子群算法计算机 科学,2010,37(4):187-191 驶路程平均值上, IDE VND相比于ABC分别最大提高39 [5 Ston R Differential evolution design of an IIR-filter [Cl//Pro- 19%和17.66%。 lings of IEEE Conference Evolutionary Computation 由此表明, IDE VND算法充分利用了差分进化算法较 (S07803-29023). Nagoya, Japan,1996:268-273 强的全局搜索能力和双种群的协同搜索能力;同时变邻域下[6]MiMi, Xue Hui-feng, Zhong ming,eta. An improved differen- 降搜索有效地增强了算法的局部开发能力,避免了算法过早 tial evolution algorithm for TSP problem[Cl/Proceedings of 陷人局部最优,提高了算法的求解质量。 Intelligent Computation Technology and Automation. Washing- 图2—图4给出了3种算法以25个顾客规模算例R201 ton do,USA,2010:544547 [7] Onwubolu G, Davendra D Scheduling flow shops using differen- 50个顾客规模算例R201以及100个顾客规模算例RC205 tial evolution algorithm [J]. European Journal of Operational 为例的 Pareto前沿对比情况。比较3种算法可以看出,在 Research,2006,171(2);674-69 Pareto解的数量和质量上, IDE VND具有更加明显的优势,[8]曹二保赖明勇,聂凯带时间窗的车辆路径问题的改进差分进 所求得的 Pareto前沿更加逼近实际 Pareto前沿。 化算法研究[].系统仿真学报,2009,21(8):2420-2423 700 DDE VND [9]王君.带时间窗车辆路径问题的差分进化混合算法[门].计算机 IDE VND - IDE IDE 工程与应用,2013,49(2):2428,66 600 [10] Babu B V, Jehan MM L. Differential evolution for multi-objec- tive optimization[c]//Proceedings of the IEEE Congress on Evo- lutionary Computation(CEC 2003 ). Canberra, Australia, 2003 26962703 车辆数量 车辆数量 [11] Hansen P, Mladenovic N. Variable neighburhood search: princi- 图2算例R201(25个顾客)中的图3算例R201(50个顾客)中 ples and applications [J]. European Journal of Operational Re- Parcto前沿比较 的 Pareto前沿比较 search,2001,130(3):449-467 [12]陈萍,黄厚宽,董兴业求解卸装一体化的车辆路径问题的混合 启发式算法[]计算机学报,2008,31(4):565573 一ABC [13]郑金华,蒋浩,达,等.用擂台法则构造多目标 Pareto最优解 21700 集的方法[J]软件学报,2007,18(6):1287-1297 [14]刘敏多目标遗传算法在车辆路径优化中的应用研究D].湘 潭:湘潭大学,2006 车辆数量 [15] Deb K, Pratap A, Agarwal S, et al. a fast and elitist multiobject- 图4算例RC205(100个顾客)中的 Pareto前沿比较 tive genetic algorithm: NSGA-IILJ] IEEE Transactions on Evo- lutionary Computationl, 2002, 6(2) 结束语本文对带时间窗的车辆路径问题进行了研究,[16]htp:// zeb. cba. neu,edu/~ solomon/ problems.hm 从多目标的角度出发,同等地考虑行驶路程和车辆数量这两[17] Nahum OE, Hadas y, Spiegel U. Multi-objective vehicle routing 个目标,提出一种结合改进差分进化算法和变邻域下降搜索 problem with time windows: a vector evaluated artificial bee colo 的基于 Pareto支配的混合差分进化算法IDE_VND。利用改 ny approach[J]. International Journal of Computer and Informa 进差分进化算法良好的全局探索能力和变邻域下降搜索较强 tion Technology, 2014, 3(1): 41-47 225 一种求解带时间窗车辆路径问题的混合差分进化算法 旧 肟万据 WANEANG DATA文献链接 作者: 宋晓宇,朱加园,孙焕良, SONG Xiao-yu, ZHU Jia-yuan, SUN Huan-1iang 作者单位 沈阳建筑大学信息与控制工程学院沈驲110168 刊名: 计算机科学 STIC PKU 英文刊名: Computer science 年,卷(期): 2014,41(12) 引用本文格式:宋晓宇.朱加园.孙焕良.SCNGⅪiao-ψu. ZHU Jia-yuan. sUN Huan-iang一种求解带时冋窗车路径冋题的混合差分 进化算法[期刊论文]计算机科学2014(12) 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论