摘要
带时间窗约束的vRP问题（VRPTW）属于NP-hard问题，采用改进遗传算法探索最优方案。首先分析了带时间窗VRP问题的一般数学模型，并采用罚函数的方法对时间窗约束进行处理；设计了带权重的适应度函数，并采用了基于基因库的跨世代精英选择算子、PMX交叉算子和局部爬山变异算子；最后通过仿真实验与传统遗传算法和自适应遗传算法进行了对比研究，仿真结果表明改进遗传算法在解决带时间窗VRP问题中具有较高收敛速度和全局搜索能力。
The Vehicle Routing Problem with Time Windows （VRPTW） is NP-hard, this paper explored the optimal solution by improved Genetic Algorithm, and firstly analyzed the general mathematical model of the Vehicle Routing Problem with Time Window, and dealt with Time Window through penalty function. Then designed a fitness function with weight in-built, then adopted the elite selection operator based on gene pool ,PMX crossover operator and local_climbing mutation operator. Finally compared the algorithm with simple genetic algorithm and adaptive genetic algorithm by simulation. The results indicate that the improved genetic algorithm has higher convergent speed and global searching capability.
作者
范月林
周素萍
FAN Yue-lin, ZHOU Su-ping （Economy Management College, Nanjing University of Information Science ＆ Technology, Nanjing 210044, China）
出处
《电脑知识与技术》
2011年第4期2411-2413,共3页
Computer Knowledge and Technology
