基于TS的动态车辆调度问题的混合算法研究  

Mixed Tabu Search Algorithm for Dynamic Vehicle Scheduling Problem

作　　者：袁建清[1] 

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

出　　处：《计算机与现代化》2011年第6期73-75,共3页Computer and Modernization

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

摘　　要：对带时间窗的动态车辆调度问题进行分析,采用实时再优化方法进行研究,引入时间轴概念,建立动态车辆调度模型,并给出求解的混合禁忌搜索算法。该算法先用C-K节约算法求得初始解,然后用禁忌搜索进行优化,得到全局最优解。禁忌搜索算法中采用动态邻域移动方法构造候选解和动态禁忌长度选取策略设置紧急长度,提高算法的收敛速度。最后用实例证明该混合算法的可行性和有效性。On the basis of studying dynamic vehicle scheduling problem with time windows,a dynamic vehicle scheduling mathematical model is established through introducing time axis concept and adopting real-time optimizing research methods.Then a mixture algorithm based on a C-K economical method and Tabu Search algorithm is designed to solve dynamic vehicle scheduling problem.This algorithm improves convergence speed by using dynamic candidate solutions constructor method and dynamic length selection strategy.Finally computational results are provided to show that the mixed Tabu Search algorithm is feasible and efficient.

关 键 词：动态车辆调度 混合禁忌搜索算法 禁忌搜索算法 C-K节约法 动态信息 

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