车辆路径问题的禁忌搜索算法研究

Study on tabu search algorithm for stochastic vehicle routing problem

简要回顾了车辆路径问题的禁忌搜索算法的发展现状,提出了一种改进的禁忌搜索算法。该算法将路径问题按不同的车辆-顾客分配结构分解成若干子问题,然后用禁忌搜索算法求解每个子问题,最后从所有子问题的最优解中选出全局最优解。理论分析和实验结果表明该算法比以往的算法有以下优点:拓展了搜索空间,提高了最优解的效果;是一种将问题进行空间分解的并行算法,可采用多台计算机同时运算以减少整体运行时间。

On the basis of describing the vehicle routing problem briefly,a new improved tabu search algorithm is presented.In this algorithm,routing problem is divided into several sub-problems according to vehicle-customer assigning structure,and an inner tabu search algorithm is applied for each sub-problem,at last the answer of the whole problem is find among the answers of all sub-problems.Two conclusions are drawn by computation results and theory：the algorithm extends the search scope,improving the optimisation effect;The algorithm is a collateral algorithm that can be run by several computer at the same time to decrease the whole optimisation time.