求解动态车辆调度问题的混合禁忌搜索算法  

HYBRID TABU SEARCH ALGORITHM FOR SOLVING DYNAMIC VEHICLE SCHEDULING

作　　者：袁建清[1] 

机构地区：[1]黑龙江东方学院计算机科学与电气工程学部,黑龙江哈尔滨150086

出　　处：《计算机应用与软件》2012年第4期148-150,155,共4页Computer Applications and Software

基　　金：黑龙江省教育厅科学技术研究项目(11544037)

摘　　要：对带时间窗的动态车辆调度问题进行分析,引入虚拟点和时间轴概念,建立基于时间轴的动态车辆调度模型,并提出基于C-W节约法和禁忌搜索的混合禁忌搜索算法进行求解。算法中使用动态方法构造候选解和动态禁忌长度的选取策略来提高算法的收敛速度,最后通过测试实例验证了该混合算法解决动态车辆调度问题的有效性和可行性。On the basis of analysing dynamic vehicle scheduling problem with time windows,a dynamic vehicle scheduling mathematical model based on time axis is proposed by introducing the concept of virtual point and time axis.A hybrid tabu algorithm based on C-W algorithm and tabu algorithm is designed to solve the problem,which uses the candidate solutions constructed with dynamic method and the dynamic tabu length selection strategy to improve convergence speed.Then the test instances are provided to demonstrate that the hybrid tabu search algorithm is effective and feasible in solving dynamic vehicle scheduling problem.

关 键 词：动态车辆调度 禁忌搜索算法 C-W节约法 

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