摘要
车辆路径问题(VRP)是一个典型的NP-hard问题,采用传统方法求解往往找不到满意解。在分析现有求解该问题的遗传算法的基础上,对现有的交叉算子进行了改进,并设计了基于自然数编码的遗传算法,用来求解一般的和有时间窗限制的车辆路径问题。采用文献中的实例进行了数值试验,试验结果表明该算法是有效的。
The vehicle routing problem is a classical NP-hard problem,and it is usually difficult for traditional methods to obtain satisfying solutions.In this paper,on the basis of analysis of the existing genetic algorithms,an improved crossover operator is presented,and a genetic algorithm for solving vehicle routing problems with and without time windows is proposed which is based on a natural number coding scheme.The performance of the proposed algorithm is evaluated in numerical simulations.The results shows the efficiency of the proposed algorithm.
出处
《系统管理学报》
北大核心
2006年第6期528-533,共6页
Journal of Systems & Management
基金
国家自然科学基金资助项目(70301005)
教育部南开-天津大学刘徽应用数学中心资助项目
关键词
车辆路径问题
遗传算法
时间窗
部分匹配交叉
vehicle routing problem
genetic algorithm
time window
partially matched crossover
