基于分枝界定的VRP模型精确算法研究及应用

Research and Application of the Accurate Algorithm of VRP Model Based on Branch and Bound Method

目的克服用启发式算法求解车辆路线问题(VRP)结果精确度不高的缺点。方法建立了一种改进型的单场站、多辆车车辆路径数学模型。通过对车辆路径问题进行分析,将用于旅行商问题(TSP)的分枝界定法加以改进,设计出了一种车辆调度问题的精确算法,并用计算机对算法进行编程。用实例加以验证,对有1个中心仓库和8个需求点的配送系统进行了优化。结果得到含有3条线路、总路长为60 km的方案,相对于启发式算法的求解结果(77 km)缩短了17 km。结论运用分支界定法求解VRP的结果更加精确,也容易实现。

Objective To overcome the drawback of low accuracy of heuristic algorithm in solving VRP. Methods An improved vehicle routing model was built with single depot and multi vehicles. By analyzing the vehicle path problem, this paper improved the Branch and Bound method used in Travelling Salesman Problem and designed an accurate algorithm for the VRP model. Then, the algorithm was programmed by computer. At last, a case of a distribution system with one central warehouse and eight customers was taken as an example to show the effectiveness of the algorithm. Results A solution with 3 lines containing a total road length of 60 km was obtained, which saved 17 km in comparison with the result （77 km） attained using heuristic algorithm. Conclusion Using Branch and Bound method to solve vehicle and routing problem was simple to implement, and the solution was more accurate.