摘要
利用智能优化算法解决车辆路径问题(VRP)是组合优化领域的一个研究热点。论文介绍了蚁群算法,粒子群算法和模拟退火算法的算法原理和求解流程,选用了Solomon数据集的三种不同客户规模,通过利用python编制程序对三种智能优化算法的求解性能进行了测试。研究表明粒子群算法对各规模CVRP问题求解的效果均不尽人意;模拟退火算法在中小规模时算法求得最优解能力更好,蚁群算法求解大、中、小规模CVRP问题的综合评价最高。研究结果对于带容积限制的车辆路径问题的算法选择具有一定的参考价值。
One of research highlight in the field of combinatorial optimization is intelligent optimization algorithm to solve vehicle routing problem(VRP).The principle and solution processes of three algorithms including ant colony,particle swarm optimization and simulated annealing are introduced.Three different customer sizes of Solomon dataset are selected to test the solution performance of the three intelligent optimization algorithms by programming in Python.Results show that the effect of particle swarm optimization algorithm in solving capacitated vehicle routing problems(CVRP)of all scales is not satisfactory.Simulated annealing algorithm has better ability to obtain the optimal solution in small and medium-sized,and ant colony algorithm has the highest comprehensive evaluation for solving large,medium and small-scale CVRP problems.The research results could provide certain reference value for the algorithm selection of vehicle routing problem with volume constraints.
作者
李京忱
刘春
LI Jing-chen;LIU Chun(Faculty of Materials and Manufacturing,Beijing University of Technology,Beijing 100124,China;College of Artificial Intelligence,Beijing University of Post and Telecommunication,Beijing 100876,China)
出处
《价值工程》
2023年第2期161-165,共5页
Value Engineering
关键词
带容积限制车辆路径问题
粒子群算法
模拟退火算法
蚁群算法
capacitated vehicle routing problem
particle swarm optimization
simulated annealing
ant colony optimization
