基于禁忌搜索的动态车辆路径问题研究

Research of Dynamic Vehicle Routing Problem Based on Tabu Search Algorithm

在对动态车辆路径问题进行描述的基础上,分析了求解动态车辆路径问题的主要策略.通过将计划周期分片,将动态车辆路径问题转换为一系列的静态子问题,对静态子问题采用禁忌搜索算法进行求解.采用该算法对9个算例进行了测试,与文献中其他算法的计算结果相比较,有3个问题得到了最好解,7个问题得到了最好平均解,表明了算法的有效性.

In this paper dynamic vehicle routing problem is described and its treatment strategies are an- alyzed. Planning horizon is divided and dynamic vehicle routing problem are partitioned into a series of static sub-problems, which is solved by tabu search. Instances are tested and results are compared with other algorithms in literature, three best solutions and seven best average solutions have been found among nine instances by tabu search. It demonstrates the effectiveness and robustness of the algorithm in solving these problems.