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）

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

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