基于遗传算法的多目标路径优化算法的研究  

Research on Multi-target Path Optimization Algorithm Based on Genetic Algorithm

作　　者：金仙力[1] 李金刚 

机构地区：[1]南京邮电大学计算机学院软件学院,江苏南京210003

出　　处：《计算机技术与发展》2018年第2期54-58,共5页Computer Technology and Development

基　　金：国家自然科学基金(61373139)

摘　　要：物流行业在发展过程中存在着许多制约因素,比如车辆路由问题(VRP)等。VRP的目标是以一个最小的成本服务于一系列服务点。对此,提出一种基于遗传算法的路径优化算法,用以解决服务点有序且带时间约束条件的车辆路由问题。首先,根据问题建立相应的模型,并将遗传算法运用到问题求解当中;然后,通过添加算子调节等操作来改进遗传算法,增加了算法的适用范围,加快了算法的收敛速度,提高了算法的效率;最后,将算法应用于实际生活当中,并与传统的遗传算法进行对比。结果表明,改进后的算法收敛速度更快、效率更高,能够有效地解决服务点有序且带时间约束条件的车辆路由问题。There are many constraints in the development of the logistics industry,such as vehicle routing problem （VRP）,the goal of whichis to serve a range of service points at a minimum cost. For this,we propose a path optimization algorithm based on genetic algorithm for theVRP with orderly service point and time constraints. First of all,we establish the corresponding model according to the problem,and applythe genetic algorithm for problem solving. Then,the genetic algorithm is improved by adding operator adjustment and other operations,in鄄creasing its application range,accelerating its convergence speed and rising its efficiency. Finally,the algorithm is applied to real life andcompared with traditional genetic algorithm,which shows that it can effectively solve the VRP with service point order and time constraints,with faster convergence speed and higher efficiency.

关 键 词：物流 车辆路由问题 时间约束 遗传算法 收敛 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]