Abstract: The capacitated vehicle routing problem(CVRP)is a classical combinatorial optimization problem, which generally minimizes the number of vehicles and distance discovered by vehicles. The average loading rate of vehicles is important when it is used to evaluate logistics level in the actual logistics distribution, and is directly affected by the customer’s demand quantity. This paper proves that the average loading rate of vehicles is ρ ∈(50%; 100%], and the more the consumers with demand quantity exceed and be close to 0.5Q, the lower the average loading rate is. A 4-stage algorithm is proposed based on Savings, Lin-Kernighan and Large Neighborhood Algorithm to solve CVRP and to identify the conclusion. Finally, the 60 CVRP instances with big demand are devised based on the 20 Golden CVRP benchmark instances (the number of consumers is from 200 to 483). Then we use the 4-stage algorithm to solve the 60 instances. The experimental results indicate that the theory analysis is scientific and reasonable, and the 4-stage algorithm is efficient and competitive in comparison with the previous heuristics. The average deviation of the solutions obtained with the 4-stage algorithm from the Bestknown solutions is only 0.92%.

Key words: vehicle routing problem, average loading rate, 4-stage algorithm

摘要： 在城市物流配送中,租用车型的选择与车辆平均装载率具有密切的关系。然而,在带能力约束的车辆路径问题(Capacitated Vehicle Routing Problem, CVRP)中, 假设配送车辆装载量为事先已知。在实际物流配送中, 很多配送车辆为租用, 因此需要确定租用的车型大小。本文基于CVRP问题,假设配送车辆载量Q为变量,以车辆平均装载率为优化目标构建了数学模型. 通过数学推导证明了,派送车辆的平均装载率ρ的理论区间为(50%, 100%]。分析得出结论:当顾客需求数据中需求数据大于且接近0.5倍载量Q的越多,车辆平均装载率越低。为了验证分析结论的正确性, 分别设计一个求解CVRP问题的多阶段算法和具有大需求量的CVRP问题算例. 通过求解算例表明:本文理论分析的正确性, 其中四阶段算法的求解结果与当前已知最优解平均偏差仅为0.92%,达到优秀算法水平。

关键词: 车辆路径问题, 平均装载率, 四阶段算法