基于改进遗传算法的带时间窗vrp问题研究

《基于改进遗传算法的带时间窗vrp问题研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于改进遗传算法的带时间窗VRP问题研究：带时间窗约束的VRP问题（VRPTX交叉算子和局部爬山变异算子；最后通过仿真实验与传统遗传算法和自适应遗传算法进行了对比研究，仿真结果表明改进遗传算法在解决带时间窗VRP问题中具有较高收敛速度和全局搜索能力。　　关键词：遗传算法；时间窗；车辆路径问题；基因库　　：TP202+.7：A：1009-3044(2011)10-2411-03　　ResearchonVRPTanagementCollege,NanjingUniversityofInformationScience&Technology,Nanjing210044,China)

2、　　Abstract:TheVehicleRoutingProbleme系数设置成非常大（一般为1000000）即可；TX）,在交叉过程中将隔离基因预先剔除，交叉完成后重新进行线路划分，以杜绝不可行解的出现。　　变异过程是对染色体上一个或几个基因位进行随机替换。本文将传统多点变异改进成局部爬山变异，即变异有若干个候选变异方向，算子将按照其中最好的方向实施变异，以达到局部最优。设计如下：在染色体编码序列中随机产生三个位置（非隔离基因0）pos1,pos2,pos3作为变异点如：　　pos1,pos2,pos3三个位置的编码值任意交换位置产生A33=6种组合，分别计算这六种组合所

3、对应的编码序列的适应度函数，将适应度最高的染色体保留下来作为变异的结果。如此使得变异算子具有局部爬山能力，可使染色体只向有利的方向变异，提高收敛速度。　　3仿真实验及分析　　3.1仿真条件及参数设置　　本文在JavaEclipseGalileo环境下进行了仿真，主机配置为Intel双核处理器，CPU主频1.8GHZ，内存2.0GB，采用Java和SQLSever2000编程实现。仿真数据如下：O是配送中心，坐标为[200,200]，配送车辆出发时间是8:00，A～J分别代表十个有配送需求的客户，客户信息见表1。算法参数为：种群大小=50，交叉概率=0.80，变异概率=0.01

4、，终止代数=500，车辆最大载重=8.0，早于时间窗惩罚因子=10.0，晚于时间窗惩罚因子=10.0。　　表1客户信息表　　3.2仿真结果及分析　　采用以上参数设置时经过687ms的计算取得了较为满意的计算结果见图6。结果显示，当种群进化到113代以后，配送车辆的规划路径已经不在发生变化（---OGFO---OAJHIO----OEDCBO----），并且总成本也趋于稳定直至254代以后完全固定在2244.098为止。图5则给出了最佳配送方案的直观展示，十个客户按照配送顺序被划分到①②③三个区域，分别由三辆配送车进行配送。　　为验证本文改进遗传算法的可行性和有效性，分别采用传

5、统遗传算法（SGA）、自适应遗传算法（ASA）和本文改进的遗传算法（IGA）对带时间窗VRP问题在相同实验环境和仿真数据下进行了100次对比仿真实验，结果如表2。　　表2表明：对于本文的带时间窗VRP问题，改进遗传算法的选择和变异操作中要比另外两种算法复杂，但局部的复杂却提高了算法全局的进化效率，收敛时间大为缩短。而且当问题规模较小时，三种方法虽都能得出最优解，但改进算法的最优解收敛次数却提高了13.64%以上。可见改进的遗传算法运算效率得到了提升而且全局搜索能力大大增强。　　4结束语　　采用遗传算法处理带时间窗约束的车辆路径问题，其实质就是将约束条件转化到遗传算子的设计中，

6、在成功处理了约束条件后，问题就简化为简单的TSP问题[6]，目前，具有较强实际意义的约束条件有载重约束、时间窗约束、路径长度约束、取货送货约束、回程约束和司机工作时间约束等等。随着约束条件的增加，遗传算法的设计难度也越大。因此，如何恰当的将各种约束条件进行转化成为解决车辆路径问题的关键，也是当前的研究热点。笔者希望通过本文的探讨研究能为VRP问题的研究者提供参考。