An Improved Branch-and-Price Algorithm for Solving the Capacitated Vehicle Routing Problem

Yi Qu; Jing Fan

doi:10.6911/WSRJ.202502_11(2).0003

Authors

Yi Qu
Jing Fan

DOI:

https://doi.org/10.6911/WSRJ.202502_11(2).0003

Keywords:

Vehicle Routing Problem; Branch-and-Price Algorithm; Column Generation Algorithm; Simulated Annealing; Local Search; Branch-and-Bound Algorithm.

Abstract

For the capacitated vehicle routing problem, this paper proposes an improved branch-and-price algorithm. This algorithm is based on the Dantzig-Wolfe decomposition principle, which decomposes the complex vehicle routing problem into a master problem and subproblems. The master problem is responsible for selecting the optimal transportation scheme from a set of candidate vehicle routes, while the subproblems generate new transportation schemes according to the feedback from the master problem. A special strategy which integrates hybrid greedy-simulated annealing and local search, is introduced to improve the generated partial routes, and to increase the solution speed. This approach provides higher-quality solutions for the master problem in each iteration. Furthermore, through small-scale and large-scale simulation experiments and comparative analysis, the accuracy and efficiency of the improved branch-and-price algorithm are verified.

Downloads

Download data is not yet available.

References

[1] D.X. Li, Z.C. Gong. On ethical decision-making in algorithm design for autonomous vehicles——Based on meaningful human control [J]. Science and Technology Herald, 2023, 41(07): 47-54.

[2] H.X. Xu, Z.Z. Wu, Y.Y. Liang. Review of research on path planning methods for autonomous vehicles based on reinforcement learning [J]. Computer Application Research, 2023, 40(11): 3211-3217.

[3] Dantzig G B, Ramser J H. The truck dispatching problem [J]. Management science, 1959, 6(1): 80-91.

[4] C.L. Xu, J.K. Hu, Y.F. Huang. Robust Optimization of Express Delivery Network with Uncertain Demand [J]. Computer Engineering and Applications, 2020, 56 (03): 272-278.

[5] K.F. Jin, J. Yan, Y.T. Liang. A Review of the Current State of Research on the Capacitated Vehicle Routing Problems [J]. Gansu Science and Technology, 2022, 51 (10): 52-56+16.

[6] X.F. Chao, X.L. Yang. A Review on the Capacitated Vehicle Routing Problem [J]. Value Engineering, 2012, 31 (05): 16-17.

[7] C.F. Zong, X.L. Yao, X,L. Fu. Path planning of mobile robot based on improved ant colony algorithm[C]//Proc of the 10th Joint International Information Technology and Artificial Intelligence Conference. Piscataway, NJ: lEEE Press, 2022:1106- 1110.

[8] X.G. Yang, N. Xiong, Y. Xiang, et al. Path planning of mobile robot based on adaptive ant colony optimization[C]//Proc of the 47th Annual Conference of the lEEE Industrial Electronics Society. Pisca-taway, NJ: IEEE Press, 2021:1-4.

[9] Y.M. Zhang. Research on robot path planning based on improved genetic algorithm[C]//2022 14th International Conference on Advanced Computational Intelligence (ICACI). IEEE, 2022: 273-277.