计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (5): 261-264.

• 工程与应用 • 上一篇    下一篇

基于双层模糊聚类的多车场车辆路径遗传算法

李  波,邱红艳   

  1. 天津大学 管理与经济学部,天津 300072
  • 出版日期:2014-03-01 发布日期:2015-05-12

Two-stage fuzzy clustering genetic algorithm for multiple-depot vehicle routing problem

LI Bo, QIU Hongyan   

  1. College of Management and Economics, Tianjin University, Tianjin 300072, China
  • Online:2014-03-01 Published:2015-05-12

摘要: 对大规模多车场车辆路径问题,设计了基于双层模糊聚类的改进遗传算法求解框架,上层静态区域划分利用k-means技术将多车场到多客户的问题转化为一对多的子问题,下层模糊聚类从保证客户满意度和整合物流资源的角度出发,利用模糊聚类算法根据客户需求属性形成基于客户订单配送的动态客户群。进一步,通过改进选择算子和交叉算子来设计车辆路径优化的遗传算法。通过随机算例仿真实验,证明了提出方法和求解策略的有效性。

关键词: 多车场车辆路径问题, 双层模糊聚类, 改进遗传算法

Abstract: An improved genetic algorithm is proposed to solve the large-scale Multiple-Depot Vehicle Routing Problem(MDVRP), which is based on the presented two-stage fuzzy clustering algorithm. In the first stage, k-means is used to divide the MDVRP into several sub-problems. In terms of improving the customer satisfaction and integrating logistics resource, fuzzy clustering algorithm is applied to cluster customers into groups based on multi-attribute customer orders. Furthermore, the improved GA is designed to solve the VRP by changing the selecting operator and the crossover operator. The stochastic simulation experiments show the proposed algorithm is efficient.

Key words: Multiple-Depot Vehicle Routing Problem(MDVRP), two-stage fuzzy clustering, improved Genetic Algorithm(GA)