基于改进k-means和遗传算法的油田特种车辆优化调度  

Optimal scheduling of oilfield special vehicle based on improved k-means and genetic algorithm

作　　者：戴永寿[1] 李韶光[1] 李立刚[1] 于肖雯 

机构地区：[1]中国石油大学(华东)信息与控制工程学院,山东青岛266580

出　　处：《计算机应用》2016年第A01期86-89,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(40974072);山东省自然科学基金资助项目(ZR2010DM14)

摘　　要：针对采油厂特种车辆数目少、作业任务多、调度复杂且人工安排结果差的问题,提出了一种基于改进k-means和遗传算法的多目标分阶段求解的特车优化调度方法。该方法以最少车辆使用数目为主要目标,采用改进k-means算法完成对所有任务的最优分组;以最大任务完成数目为次要目标,利用基于贪婪修正策略和裂变策略的改进遗传算法调整最优分组方案;最后,以最短行驶距离为次要目标,利用穷举法优化行车路线。理论分析和仿真实验表明,k-means算法求得的任务分组结果要明显优于禁忌搜索算法、模拟退火算法,改进遗传算法求得的任务完成结果要比传统遗传算法好,故该方法可在现有车辆不足的情况下尽可能多地完成上报的需求不同的任务,并减少车辆的行驶距离,因此尤其适用于求解车载能力有限的需车型、需车数不确定的调度问题。For the question of small number of special vehicles,a lot of tasks and poor results of personnel arrangement,this paper proposed an optimal scheduling method of special vehicle based on improved k-means and Genetic algorithm,which solved this problem multi-objectively and in stages.First,this paper took the minimum number of vehicles as the main target,and used improved k-means method to group all tasks optimally.Second,we took the maximum number of tasks as the secondary target,and used improved genetic algorithm to make the number of completion tasks become the largest.At last,this paper took the shortest distance as the third target,and used the exhaustive method to optimize the vehicle path.The theoretical analysis and simulation results show that the grouping result of tasks by k-means is better than Tabu Search（ TS）and Simulated Annealing（ SA）,and the completion result of tasks by improved GA is better than GA.So,the method was applied to solve the problem which vehicle type and number is uncertain.

关 键 词：特种车辆 优化调度 多目标 K-MEANS算法 遗传算法 

分 类 号：TP315[自动化与计算机技术—计算机软件与理论]