Abstract: Emergency supplies scheduling in large-scale emergency is a classical Vehicle Routing Problem（VRP）. For large-scale VRP, traditional heuristic algorithms are easy to fall into local optimal and hard to obtain high quality scheduling scheme. To remedy this, a scheduling algorithm based on K-mean cluster and LK algorithm is proposed. K-mean cluster is used to divide the demand nodes into n subsets, after some regulations these subsets of demand nodes are dispatched to n vehicles. The routing of each vehicle is optimized by LK algorithm. Experimental results indicate that, the proposed algorithm can obtain better scheduling schemes. Moreover, the larger the number of demand nodes served by a single vehicle, the more outstanding superiority of the proposed algorithm.

Key words: emergency supplies scheduling, K-mean cluster, Lin-Kernighan（LK） algorithm

摘要： 突发性事件中应急物资调度方案最优化问题是典型的车辆路径规划（VRP）问题。对于大规模的VRP问题求解，经典的启发式算法易陷入局部最优，难以得到高质量的调度方案。针对这一问题，提出了一种基于K均值聚类和LK算法的调度方法。该方法采用K均值聚类方法将需求节点分成n个子集合，对聚类结果进行修正后分配给n辆运输车辆，采用LK算法对每辆运输车辆的运输路径进行优化。仿真实验结果表明，方法获得了较好的调度方案，而且单个运输车辆服务的需求节点个数越多，方法的优势越明显。

关键词: 应急物资调度, K均值聚类, LK算法