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

摘要

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节约法和禁忌搜索的混合禁忌搜索算法进行求解.算法中使用动态方法构造候选解和动态禁忌长度的选取策略来提高算法的收敛速度,最后通过测试实例验证了该混合算法解决动态车辆调度问题的有效性和可行性.