需求可分的车辆路径问题模型与算法

摘要

需求可分的车辆路径问题(SDVRP)无论是从运输距离还是派车数量上,都可进一步优化传统的车辆路径问题.为了降低SDVRP的求解难度,本文在分析最优解性质的基础上,加强模型的约束条件,将原模型转变为等价的改进SDVRP,并在使用蚂蚁算法求解改进SDVRP模型的过程中,采用开发新路径和2-opt相结合的方法,以避免出现迭代停滞的现象.实验表明,算法计算结果稳定,最差解与最好解的偏差仅为1.80％.%Vehicle routing model with split delivery( SDVRP) can optimize further traditional vehicle routing problem in both transportation distance and the number of dispatching vehicle. To reduce the difficulty with the solution to SDVRP, based on analyzing properties of the optimal solution, the original model is transformed to the e-quivalent modified SDVRP through enforcing constraints of the original model. In the process of solving the modified SDVRP model with ant colony algorithm, exploring new routes and 2-opt are combined to avoid premature convergence. The experiments demonstrate that the computing results are stable: The bias between the worst solution and the best solution is only 1.80%.