论文部分内容阅读
现代物流业需要快速高效并智能化制定物流运输方案。传统路径优化方法适合处理中小规模的车辆路径问题,计算时间较长,方案质量较低,故需发展短时间内能提供高质量路径方案的启发式算法。针对大规模物流车辆路径优化,本文提出了一种Voronoi邻近的快速优化方法。该方法先创建初始解,而后进行迭代优化。初始解创建利用Voronoi邻近关系,顾及车辆容量约束,自底向上进行客户点空间聚类,将问题降维;采用最廉价插入算法安排聚类内部路径,生成性质良好的初始解。迭代优化在客户点Voronoi邻近内进行有效的局部搜索,利用模拟退火机制接受较差解,从而跳出局部最优,不断提高解的质量。本文利用模拟生成的北京市大规模车辆路径问题进行实验,结果表明:本文算法能够在4500s内优化客户点高达12 000个物流车辆路径问题,计算时间较短,解的质量优良,算法性能稳定。本文与其他算法比较,能在较短时间内提供高质量车辆路径方案,适用于大规模物流车辆路径的优化。
Modern logistics industry needs fast, efficient and intelligent development of logistics and transport solutions. The traditional path optimization method is suitable for the small and medium-sized vehicle routing problem. It takes a longer time and has lower program quality. Therefore, a heuristic algorithm that can provide high-quality path solutions in a short period of time needs to be developed. In order to optimize the path of large-scale logistics vehicles, a fast optimization method of Voronoi neighborhood is proposed in this paper. The method first creates the initial solution and then iteratively optimizes it. The initial solution is constructed using the Voronoi neighborhood, taking into account the vehicle capacity constraints, spatial clustering of customer points from the bottom to the bottom of the problem, and the problem is reduced in dimension. The cheapest insertion algorithm is used to arrange the internal paths of clusters to generate good initial solutions. Iterative optimization performs effective local search in the Voronoi neighborhood of customer points and accepts the worst solution using the simulated annealing mechanism to jump out of local optima and improve the quality of solution. In this paper, the simulation of large-scale vehicle routing problem in Beijing is carried out. The experimental results show that the proposed algorithm can optimize the logistics path of up to 12 000 logistics vehicles within 4500s. The calculation time is short, the quality of the solution is good and the performance of the algorithm is stable. Compared with other algorithms, this paper can provide a high-quality vehicle routing solution in a short period of time, which is suitable for the optimization of large-scale logistics vehicles.