摘要
对蚁群算法进行改进以增加其在处理带容量限制的车辆路径问题时的性能。改进后的算法建立每一个点的临近点序列以增加生成解的质量并减少计算时间。设定一个信息素最小值,避免算法由于部分边上信息素值过低而被忽略。在计算选择概率时将所有边全部减小一个相同的值,以增加边长在决定选择时的作用。增加一只记忆蚂蚁来增强算法的收敛能力,令蚂蚁在前进过程中有可能回到出发点,通过这种方法让算法具有检索所有解的可能。在算法的最后加入对解的调整操作,进一步靠近全局最优解。用该算法计算通用的VRP算例,验证了算法的有效性。
Improvements were made to enhance the performance of the ant colony algorithm when used to solve vehicle routing problem.The improved algorithm establishes the near point sequence to improve the quality of solutions and reduce the calculating time.Set a minimum value of pheromone,to avoid that the algorithm ignored edges with low pheromone.Reduced the value of all edges when calculating the selective possibility to enhance the effect of the length of edges when calculating selective possibility.Added a memory ant to enhance the convergence ability.Gave the ants a possibility to return when going forward,this method gives the algorithm the possibility to search all solutions.Added a procedure of modifying the solution at the last of the algorithm to make the solution approach the global optimal solution.Used the universal examples for VRP to test the effectiveness of algorithm,which proved that the algorithm is effective.
作者
徐泽峰
蔡延光
Xu Zefeng Cai Yanguang(School of Automation, Guangdong University of Technolog)
出处
《自动化与信息工程》
2016年第4期19-23,共5页
Automation & Information Engineering
基金
国家自然科学基金(61074147)
广东省自然科学基金(S2011010005059)
广东省教育部产学研结合项目(2012B091000171
2011B090400460)
广东省科技计划项目(2012B050600028
2014B010118004
2016A050502060)
广州市花都区科技计划项目(HD14ZD001)
关键词
CVRP
蚁群算法
临近点序列
CVRP
Ant Colony Algorithm
Near Point Sequence
