摘要： 在对带时间窗的开放式车辆路径问题描述的基础上提出求解该类问题的一种多开始禁忌搜索算法。使用扫描算法和向前插入法相结合的两阶段方法产生随机的初始解，采用一种混合的启发式算法构建邻域结构，设计全局和局部2个禁忌表加强算法的全局寻优能力。用标准的测试算例对算法进行实验，结果表明该算法得到了较好的寻优效果。
关键词:
开放式车辆路径问题,
禁忌搜索算法,
时间窗
Abstract: On the basis of describing the Open Vehicle Routing Problem with Time Windows(OVRPTW), a Multi-Start Tabu Search(MS-TS) algorithm is presented. In this algorithm, the random initial solution is generated by the two-phase method of combining the sweep algorithm and push forward insertion heuristic, the neighborhood structure is constructed by a mixed heuristic algorithm, the capability of global optimization is improved by designing global and local Tabu list. With the normal test examples, the experiment is done, and a good optimization result is obtained.
Key words:
open vehicle routing problem,
Tabu search algorithm,
time windows
中图分类号:
李三彬, 王黎明. 求解OVRPTW的多开始禁忌搜索算法[J]. 计算机工程, 2011, 37(6): 187-189.
LI San-Ban, WANG Li-Meng. Multi-start Tabu Search Algorithm for Solving OVRPTW[J]. Computer Engineering, 2011, 37(6): 187-189.