基于混合禁忌搜索算法的动态车辆路径研究

Research on dynamic vehicle routing problem based on hybrid tabu search algorithm

为解决需求不确定下的带时间窗车辆调度问题,提出将新需求点收集、路径优化、路径执行时间分开的实时优化策略.对需求的特点进行分类,提出一种预处理机制处理紧急需求,确保所有的需求点都能得到满足.以在较短的时间内得到近似最优解为目标,在将结点插入可行位置并进行局部优化的基础上,运用带交叉算子的禁忌搜索算法进行优化.通过实验,验证了该方法的有效性和优越性.

In order to solve the Vehicle Routing Problem with Time Windows （VRPTW） under uncertain demands , this paper gives a real-time optimization strategy for separating the demand collecting time from path optimization time and the path execution time. The demand nodes are divided into several categories and a pretreatment mechanism to deal with the urgent requirement is proposed in order to meet all demands from every node. The target of this problem is to get the approximately optimal solution in a relatively short time. While the node is inserted in the possible position and be optimized locally. Then the result is optimized with the hybrid tabu search algorithm with crossover operators. The experiments show that the algorithm is effective and excellent.