| 摘要: |
| 目的 克服用启发式算法求解车辆路线问题（VRP）结果精确度不高的缺点。 方法 建立了一种改进型的单场站、 多辆车车辆路径数学模型。 通过对车辆路径问题进行分析， 将用于旅行商问题（TSP）的分枝界定法加以改进， 设计出了一种车辆调度问题的精确算法， 并用计算机对算法进行编程。 用实例加以验证， 对有 1 个中心仓库和 8 个需求点的配送系统进行了优化。 结果 得到含有 3 条线路、总路长为 60 km 的方案， 相对于启发式算法的求解结果（77 km）缩短了 17 km。 结论 运用分支界定法求解VRP的结果更加精确，也容易实现。 |
| 关键词: VRP模型 分枝界定法 路径优化 |
| DOI： |
| 分类号:O224； [U-9] |
| 基金项目:国家级大学生创新创业训练计划项目 (201210489314) |
|
| Research and Application of the Accurate Algorithm of VRP Model Based on Branch and Bound Method |
|
CAO Ping-fang, LI Ling, LI Shi-zhen
|
|
Yangtze University， Jingzhou 434020， China
|
| Abstract: |
| 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. |
| Key words: VRP model Branch and Bound method path optimization |
渝公网安备 50010702501716号