基于K均值聚类和LK算法的应急物资调度  

Emergency supplies scheduling based on K-mean cluster and LK algorithm

作　　者：汪亮[1] 解建仓[1] 罗军刚[1] 

机构地区：[1]西安理工大学陕西省西北旱区生态水利工程重点实验室,西安710048

出　　处：《计算机工程与应用》2012年第21期35-40,共6页Computer Engineering and Applications

基　　金：国家自然科学基金(No.51109175);国家"863"计划(No.2006AA01A126);中国博士后科学基金(No.20110490170);陕西省工业攻关计划(No.2012K06-20)

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]