车辆路径规划问题广泛地存在于现代物流行业中, 该问题属于NP难的组合优化问题. 随着客户需求的多样化、道路限行等因素的影响, 该问题变得更加的复杂, 采用传统的组合优化方法和运筹学方法往往难以求解. 本文对一类常见的带时间窗的车辆路径规划问题进行了研究, 根据时间窗参数来调整客户的优先级, 以减少车辆的等待时间, 由此改进了几个常见的启发式算法, 并对56个常见的车辆路径规划问题进行了测试, 实验结果表明, 改进的节约算法在带容量约束的车辆路径问题中效果较好, 改进的插入法则在带时间窗的车辆路径问题中具有优越性, 另外, 改进的启发式算法在4个测试用例上使用更多车辆时可使总路程优于已知最优值.
The vehicle routing problem (VRP) exists extensively in the modern logistics industry, which is an NP-hard problem in combinatorial optimization. Affected by factors such as diverse customer demand and road traffic restrictions, VRP becomes more complex, and it can hardly be solved by the traditional combinatorial optimization methods and operations research methods. In this study, a common VRP with time windows is studied. The waiting time of vehicles is reduced by the adjustment to the priority of customers according to the parameters of time windows. On this basis, several common heuristic algorithms are improved, and 56 common VRPs are tested. The experimental results reveal that the improved savings algorithm can produce good results for capacitated VRPs, and the improved insertion method has superior performance in VRPs with time windows. In addition, the improved heuristic algorithms can make the total distance better than the known optimal value when using more vehicles on the four test cases.