开放式车辆路线问题的改进混合遗传算法

2012年04月10日11:40:54 本网站我要评论(2)字号：T | T | T

关键字：应用

任春玉
黑龙江大学信息科学与技术学院，黑龙江哈尔滨

摘　　　要：针对传统的遗传算法存在收敛速度慢，局部搜索能力差，易早熟的缺点，采用混合遗传算法进行优化求解开放式车辆路线问题。即采用二重结构编码，可以使问题变得更简洁，提高遗传法的搜索效率。用个体数量控制选择策略，以保证群体的多样性，用改进的顺序交叉算子避免优良基因片断在顺序交叉时被破坏，保证算法能够收敛到全局较优。较后，结合具体实例，通过实验计算证明了该改进算法的良好性能。

关　键　词：开放式车辆路线问题；二重结构编码；个体数量控制；顺序交叉；混合遗传算法

１　引　言
开放式车辆路线问题（ＯｐｅｎＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍ，ＯＶＲＰ）是经典车辆路线问题（ＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍ，ＶＲＰ）的拓展问题。ＯＶＲＰ问题研究方法主要包括精确算法、启发式算法［１２］和智能优化方法［３４］。在求解大规模、复杂问题时，智能优化算法应用更广泛，其中，遗传算法具有简单通用、鲁棒性好、隐并行性和求解组合优化问题的良好特性。肖天国通过应用交叉、变异概率的自适应机制和交叉算子等技术，构造了一个求解带软时间窗的开放式车辆路径问题的遗传算法［５］。邓猛针对开放的车辆路线安排问题，建立了以车流为基础的数学模型，利用罚函数法来化简约束条件，并设计了基于自然数编码的遗传算法［６］。但由于ＯＶＲＰ的特殊性，借助于标准遗传算法存在收敛速度慢，局部搜索能力差，易早熟的缺点。因此，针对这些缺点，本文设计了一种混合遗传算法进行优化求解。较后，通过算例，对模型和算法的性能进行了验证。

登录网站后可下载文件

开放式车辆路线问题的改进混合遗传算法

相关阅读: