计算机应用 ›› 2016, Vol. 36 ›› Issue (11): 3141-3145.DOI: 10.11772/j.issn.1001-9081.2016.11.3141

• 人工智能 • 上一篇    下一篇

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

向婷, 潘大志   

  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

XIANG Ting, PAN Dazhi   

  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).

摘要: 针对需求可拆分车辆路径问题(SDVRP),提出一种先分组后路径的聚类算法。该算法考虑车辆载重的均衡性和可行解的特征,优先安排载重大于等于车辆限载的客户;然后结合客户间的距离和载重,设定一个拆分阈值限定车辆载重范围,按照就近原则对客户进行聚类分组,当组内客户载重未达到车辆载重最小值而加入新客户后超出限载时,对新加入客户进行拆分和调整,最终完成对所有客户的分组;最后采用蚁群优化算法对各组内客户进行线路规划。实验结果表明,所提算法在求解需求可拆分车辆路径问题时,具有更高的稳定性,得到的结果更优。

关键词: 需求可拆分车辆路径问题, 聚类算法, 蚁群算法, 启发式算法

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.

Key words: Split Delivery Vehicle Routing Problem (SDVRP), clustering algorithm, Ant Colony Optimization (ACO), heuristic algorithm

中图分类号: