适应性禁忌搜索算法求解带回程的时变速度车辆路径问题

Reactive tabu search algorithm for time-dependent vehicle routing problem with backhauls

为求解带回程的时变速度车辆路径问题,建立了问题的数学模型并提出适应性禁忌搜索算法求解。适应性禁忌搜索算法为两阶段的启发式方法,改进固定速度下的启发式方法用于生成时变速度下的初始解,然后运用适应性禁忌搜索算法进一步优化,包括邻域生成规则定义,采用Hash表存储搜索过程中的解,检测解的重复状态,定义逃离局部搜索区域规则。对改进的标准问题进行测试,同时与最近邻域搜索算法的结果作比较,结果表明算法是有效的。与固定速度情形相比较,时变速度模型得到的调度方案更加合理。

To solve the time-dependent vehicle routing problem with backhauls, a mathematical model was constructed and a reactive tabu search algorithm was put forward. This method was a two-phase heuristic method. The original solution was generated through improving traditional heuristic method, and then the initial solutions were optimized by the reactive tabu search algorithm, including the definition of the neighborhood generation mechanism, applying Hash table data structure to store the solution during the search, checking the repetition status of the solution, and the definition of the escaping mechanism from local space. Compared to nearest neighborhood search algorithm, the algorithm was verified to he efficient through a number of standard test cases. In addition, the results with time-dependent were more reasonable than that of the constant speed setting.