基于约束聚类和粒子群算法的多路径规划  

Multi Path Planning Based on Constrained Clustering and Particle Swarm Optimization

作　　者：韩雪 HAN Xue(College of Information Engineering,Xuzhou Open University,Xuzhou 221000,China)

机构地区：[1]徐州开放大学信息工程学院,江苏徐州221000

出　　处：《计算机与现代化》2023年第8期7-11,共5页Computer and Modernization

摘　　要：大型物流中心物流管理信息系统在进行物流配送中,必须进行多配送中心车辆路径问题研究,用尽可能少的车辆,完成货物的配送,并使得行驶总里程最小。业界已经针对多中心路径规划中k条最短路径难问题进行了深入的研究,通过采用传统的聚类算法已经能够实现多路径规划问题,但是在现实多配送中心车辆路径规划中,运输工具的运输能力和用户的需求存在特定限制,本文在聚类算法基础上引入约束机制,将多配送中心问题通过聚类算法降维为单配送中心问题,并在此基础上引入粒子群算法求解单配送中心多路径规划的最优解。通过实验验证该方法的优越性,他比传统粒子群算法的收敛速度至少提升了n(配送中心个数)倍,为路径规划提出了新的解决思路。In Large-scale logistics center,if logistics management information system can be used normally,it is necessary to study the problem of vehicle routing in multi-distribution centers.We want to use as few vehicles as possible to complete the deliv‐ery of goods and minimize the total mileage.K-shortest paths in multi-center path planning has conducted in-depth research,the multi-path planning problem has been realized by using the traditional clustering algorithm.However,in the real multi-distribution-center vehicle routing planning,there are specific restrictions on the transportation capacity of transportation ve‐hicles and the needs of users.We introduce constraint mechanism on the clustering algorithm to reduce the dimension of multi distribution center problem to single distribution center problem by clustering algorithm,and particle swarm optimization is intro‐duced to solve the optimal solution of multi-path planning for single distribution center.The experiment proves the superiority of this method:the practice proves that the convergence speed of this method is at least n(number of distribution centers)times faster than that of the traditional particle swarm optimization algorithm,which provides a new solution for path planning.

关 键 词：路径规划 聚类分析 数据分割 k条最短路径 K-MEANS算法 粒子群算法 

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