需求可拆分车辆路径问题的三阶段禁忌算法

需求可拆分车辆路径问题(SDVRP)是一类有待深入研究的车辆路径问题,其求解方法与需求不可拆分的VRP问题有较大的区别.针对该类问题,本文提供了一种新的求解思路——基于双层规划模型的三阶段禁忌算法.首先,将目标函数设定为大TSP路径成本加上切割增加路径成本,构建了SDVRP的双层规划数学模型;然后,根据双层规划的思路设计了三阶段禁忌启发式算法:先求包括车场和所有顾客的大TSP路径,再对大TSP进行切割和拆分,接着对备选方案进行子路径优化;最后,通过实验仿真,将所提出的三阶段禁忌算法与其他算法进行比较,结果表明了所提出的算法可以比较有效地求得需求可拆分车辆路径问题的优化解,是解决需求可拆分车辆路径问题的有效方法.

A three-phase tabu search heuristic for the split delivery vehicle routing problem

The split delivery vehicle routing problem (SDVRP) is a kind of vehicle routing problem need to be further studied. And its solving method is much different with the traditional VRP's. This paper provides a new heuristic to solve the SDVRP called three-phase tabu algorithm, which is based on the bi-level programming model of SDVRP. First, the bi-level programming mathematical model of the SDVRP is given, which set the cost of a big TSP path and the increased cost of cutting and split as the objective function. Then, based on bi-level programming model, a three-phase tabu heuristic algorithm is designed. First phase, a big TSP path including the distribution depot and all the customers is constructed. Second phase, the big TSP is cut and split. And in the third phase, the sub-paths get from the second phase are re-optimization. Finally, through the experimental simulation, the proposed three-stage tabu algorithm compared with other algorithms. And the results showed that the proposed algorithm can really solve the SDVRP effectively. And they also proved that the three-phase tabu algorithm is really a good method of SDVRP.