基于改进禁忌搜索算法的车辆路径问题模型

A Model of Vehicle Routing Problem Based on Improved Tabu Search Algorithm

为了解决传统禁忌搜索算法程序复杂、独立性低下等问题,在考虑带有时间窗的车辆路径问题的基础上,提出了带有时间窗和异构车队的车辆路径问题。为了更好地解决带有时间窗和异构车队的车辆路径问题,建立了带有时间窗和异构车队的车辆路径问题的模型,此模型同时考虑了时间窗、异构车队以及车辆数量限制的多重属性,提出一种改进的禁忌搜索算法来解决这一问题,改进的禁忌搜索算法其实质是在原有禁忌搜索算法的基础上加入了保留表,等级成本结构原则和车辆排序准则对其进行了创新。通过在原有算法中加入保留表,并使用等级成本结构的原则,提出了一种新的解决车辆路径问题的算法,这种改进的禁忌搜索算法解决了传统禁忌搜索算法的弊端,不仅可以使用户点在路径上紧密排列,同时还能达到优化运输路线的目的。最后为了演算改进的禁忌搜索算法的有效性,使用具体的案例数据对改进的禁忌搜索算法进行了演算,演算结果证明了这种创新算法在解决带有时间窗和异构车队的车辆路径问题上是有效的。

In order to solve the problem of complex and low independence of traditional tabu search algorithm,we put forward the problem of vehicle routing with time window and heterogeneous fleet on the basis of considering the vehicle routing problem with time window. In order to better solve the problem of vehicle routing with time window and heterogeneous fleet,we established a model of vehicle routing problem with time window and heterogeneous fleet considering the multiple attributes of time window,heterogeneous fleet and vehicle number limit at same time. We also proposed an improved tabu search algorithm to solve this problem. Based on the original tabu search algorithm,the reservation table,the grade cost structure principle and the vehicle sorting criterion are added in the improved tabu search algorithm to innovate it in essence. By adding the reservation table into the original algorithm and using the principle of the grade cost structure,we proposed a new algorithm to solve the vehicle routing problem. This improved tabu search algorithm solveed the shortcomings of the traditional tabu search algorithm,it not only can make the user point in the path closely arranged,but also can optimize transport routes. Finally,to calculate the effectiveness of the improved tabu search algorithm,we used the specific case data to test the calculation result using the improved tabu search algorithm. The result of the calculation proves that this innovative algorithm is effective for solving the problem of vehicle routing with time window and heterogeneous fleet.