• 人工智能 •

### 求解需求可拆分车辆路径问题的聚类算法

1. 西华师范大学 数学与信息学院, 四川 南充 637009
• 收稿日期:2016-05-25 修回日期:2016-06-25 出版日期:2016-11-10 发布日期:2016-11-12
• 通讯作者: 潘大志
• 作者简介:向婷(1991-),女,四川巴中人,硕士研究生,主要研究方向:智能计算、数值计算;潘大志(1974-),男,四川三台人,教授,博士,主要研究方向:智能计算、算法设计。
• 基金资助:
四川省教育厅自然科学基金资助项目（14ZA0127）；西华师范大学博士启动基金资助项目（12B022）。

### Clustering algorithm for split delivery vehicle routing problem

1. College of Mathematics and Information, China West Normal University, Nanchong Sichuan 637009, China
• Received:2016-05-25 Revised:2016-06-25 Online:2016-11-10 Published:2016-11-12
• Supported by:
This work is partially supported by the Natural Science Foundation of Sichuan Provincial Education Department (14ZA0127), the Doctor Startup Fund of China West Normal University (122B022).

Abstract: A clustering algorithm which arranges paths after grouping was proposed to solve Split Delivery Vehicle Routing Problem (SDVRP). Considering the balance of vehicle load and characteristics of feasible solution, first, the customers which load were greater or equal to the vehicle load limit were arranged in advance. Then combined with the distance between customers and load, a split threshold was set to limit the load of vehicle to a certain range. According to the nearest principle, all customers were clustered and grouped. If the customer load in a group does not reach the minimum load of vehicle and is beyond the limit load when new customers are added in, the new customers were split and adjusted. Finally, while all the customers were divided into groups, the customers paths for each group was arranged by Ant Colony Optimization (ACO) algorithm. The experimental results show that the proposed algorithm has higher stability, and better results in SDVRP.