Ứng dụng phương pháp khởi đầu nâng cao nhằm nâng cao hiệu quả giải quyết bài toán định tuyến
Tóm tắt: 157
| 
PDF: 95 
##plugins.themes.academic_pro.article.main##
Author
Từ khóa:
Bài toán định tuyến
phân nhánh và chặn
học máy
khởi đầu nâng cao
tìm kiếm lân cận gần nhất
Tóm tắt
Nghiên cứu này tập trung vào giải quyết bài toán định tuyến tại một công ty giao chặng cuối ở Việt Nam. Phương pháp được đề xuất sử dụng một kỹ thuật trong học máy – Tìm kiếm lân cận gần nhất (Nearest Neighbor Search) – để xác định lời giải phù hợp nhất từ các bài toán tương tự đã biết, làm cơ sở tìm kiếm tối ưu trong giải thuật phân nhánh và chặn. Đầu tiên, học máy được sử dụng để phân tích và khai thác bộ dữ liệu gồm 500 bài toán đã giải làm cơ sở đối chiếu nhằm tìm kiếm lời giải gần nhất cho bài toán mới. Lời giải này được cung cấp cho phần mềm tối ưu như gợi ý ban đầu. Thực nghiệm cho thấy thuật toán có thể xác định lời giải cho bài toán tương tự chỉ trong vài mili giây. Đối với các bài toán mới, phương pháp đề xuất giúp tiết kiệm thời gian giải so với giải thuật phân nhánh và chặn truyền thống. Những kết quả này cho thấy thuật toán đề xuất có hiệu quả cao và tính ứng dụng tốt trong giải quyết các bài toán thực tiễn.
Tài liệu tham khảo
-
[1] C. K. Heng, A. N. Zhang, P. S. Tan, and Y.-S. Ong, "Multi-objective heterogeneous capacitated vehicle routing problem with time windows and simultaneous pickup and delivery for urban last mile logistics", in Proc. the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems, vol. 1, 2015: Springer, pp. 129-140.
[2] K. V. Tiwari and S. K. Sharma, "An optimization model for vehicle routing problem in last-mile delivery", Expert Systems with Applications, vol. 222, p. 119789, 2023.
[3] Z. Nourmohammadi, B. Hu, D. Rey, and M. Saberi, "A data-driven preference learning approach for multi-objective vehicle routing problems in last-mile delivery", Transportation Research Part C: Emerging Technologies, vol. 174, p. 105101, 2025.
[4] İ. İlhan, "An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem", Swarm and Evolutionary Computation, vol. 64, p. 100911, 2021.
[5] C. E. Gounaris, W. Wiesemann, and C. A. Floudas, "The robust capacitated vehicle routing problem under demand uncertainty", Operations Research, vol. 61, no. 3, pp. 677-693, 2013.
[6] Z. Borcinova, "Two models of the capacitated vehicle routing problem", Croatian Operational Research Review, vol. 8, pp. 463-469, 2017.
[7] T. K. Ralphs, L. Kopman, W. R. Pulleyblank, and L. E. Trotter, "On the capacitated vehicle routing problem", Mathematical Programming, vol. 94, pp. 343-359, 2003.
[8] R. I. Muslem and M. K. Nasution, "Algorithms and Approaches for the Vehicle Routing Problem with Pickup and Delivery (VRPPD): A Survey", in Proc. 2024 Ninth International Conference on Informatics and Computing (ICIC), 2024: IEEE, pp. 1-5.
[9] G. D. Konstantakopoulos, S. P. Gayialis, and E. P. Kechagias, "Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification", Operational Research, vol. 22, no. 3, pp. 2033-2062, 2022.
[10] F. Yang and F. Tao, "A bi-objective optimization VRP model for cold chain logistics: Enhancing cost efficiency and customer satisfaction", IEEE Access, vol. 11, pp. 127043-127056, 2023.
[11] S. Pan, V. Giannikas, Y. Han, E. Grover-Silva, and B. Qiao, "Using customer-related data to enhance e-grocery home delivery", Industrial Management & Data Systems, vol. 117, no. 9, pp. 1917-1933, 2017.
[12] J. Fitzpatrick, D. Ajwani, and P. Carroll, "A scalable learning approach for the capacitated vehicle routing problem", Computers & Operations Research, vol. 171, p. 106787, 2024.
[13] G. B. Dantzig and J. H. Ramser, "The truck dispatching problem", Management Science, vol. 6, no. 1, pp. 80-91, 1959.
[14] A. M. Altabeeb, A. M. Mohsen, L. Abualigah, and A. Ghallab, "Solving capacitated vehicle routing problem using cooperative firefly algorithm", Applied Soft Computing, vol. 108, p. 107403, 2021.
[15] J. Chi, S. He, and R. Song, "Solving capacitated vehicle routing problem with three-dimensional loading and relocation constraints", Computers & Operations Research, vol. 173, p. 106864, 2025.
[16] J. Luo and C. Li, "An efficient encoder-decoder network for the capacitated vehicle routing problem", Expert Systems with Applications, vol. 278, p. 127311, 2025.
[17] Y. Hao, Z. Chen, X. Sun, and L. Tong, "Planning of truck platooning for road-network capacitated vehicle routing problem", Transportation Research Part E: Logistics and Transportation Review, vol. 194, p. 103898, 2025.
[18] J. Li, R. Liu, and R. Wang, "Handling dynamic capacitated vehicle routing problems based on adaptive genetic algorithm with elastic strategy", Swarm and Evolutionary Computation, vol. 86, p. 101529, 2024.
[19] N. A. Kyriakakis, I. Sevastopoulos, M. Marinaki, and Y. Marinakis, "A hybrid Tabu search–Variable neighborhood descent algorithm for the cumulative capacitated vehicle routing problem with time windows in humanitarian applications", Computers & Industrial Engineering, vol. 164, p. 107868, 2022.
[20] M. Karimi-Mamaghan, M. Mohammadi, P. Meyer, A. M. Karimi-Mamaghan, and E.-G. Talbi, "Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art", European Journal of Operational Research, vol. 296, no. 2, pp. 393-422, 2022.
[21] S. Voigt, "A review and ranking of operators in adaptive large neighborhood search for vehicle routing problems", European Journal of Operational Research, vol. 322, no. 2, pp. 357-375, 2025.
[22] F. Alesiani, G. Ermis, and K. Gkiotsalitis, "Constrained clustering for the capacitated vehicle routing problem (CC-CVRP)", Applied Artificial Intelligence, vol. 36, no. 1, p. 1995658, 2022.
[23] F. Alkaabneh, A. Diabat, and H. O. Gao, "Benders decomposition for the inventory vehicle routing problem with perishable products and environmental costs", Computers & Operations Research, vol. 113, p. 104751, 2020.
[24] M. M. Aguayo, F. N. Avilés, S. C. Sarin, and C. Archetti, "The vehicle routing problem with transfers", Computers & Operations Research, vol. 177, p. 106980, 2025.
[25] W. Najy, C. Archetti, and A. Diabat, "Collaborative truck-and-drone delivery for inventory-routing problems", Transportation Research Part C: Emerging Technologies, vol. 146, p. 103791, 2023.
[26] A. Fragkogios, Y. Qiu, G. K. Saharidis, and P. M. Pardalos, "An accelerated benders decomposition algorithm for the solution of the multi-trip time-dependent vehicle routing problem with time windows", European Journal of Operational Research, vol. 317, no. 2, pp. 500-514, 2024.
[27] S. Irnich, P. Toth, and D. Vigo, "Chapter 1: The family of vehicle routing problems", in Vehicle Routing: Problems, Methods, and Applications, Second Edition: SIAM, 2014, pp. 1-33.
[28] P. Indyk and R. Motwani, "Approximate nearest neighbors: towards removing the curse of dimensionality", in Proc. the thirtieth annual ACM symposium on Theory of Computing, 1998, pp. 604-613.
[29] E. B. Edis and I. Ozkarahan, "A combined integer/constraint programming approach to a resource-constrained parallel machine scheduling problem with machine eligibility restrictions", Engineering Optimization, vol. 43, no. 2, pp. 135-157, 2011.
[30] S. M. Pour, J. H. Drake, L. S. Ejlertsen, K. M. Rasmussen, and E. K. Burke, "A hybrid constraint programming/mixed integer programming framework for the preventive signaling maintenance crew scheduling problem", European Journal of Operational Research, vol. 269, no. 1, pp. 341-352, 2018.
[31] G.-H. Chen, J.-C. Jong, and A. F.-W. Han, "Applying constraint programming and integer programming to solve the crew scheduling problem for railroad systems: Model formulation and a case study", Transportation Research Record, vol. 2676, no. 1, pp. 408-420, 2022.
[32] C. Blum, "Construct, merge, solve and adapt: Application to the minimum global domination problem", TOP, pp. 1-21, 2024.
[33] F. Ornelas, A. Santiago, J. A. Castan Rocha, S. Ibarra Martínez, and A. H. García, "Warm Starting Integer Programming for the Internet SHopping Optimization Problem with Multiple Item Units (ISHOP-U)", in Artificial Intelligence in Prescriptive Analytics: Innovations in Decision Analysis, Intelligent Optimization, and Data-Driven Decisions, 2024, pp. 153-170.
[34] A. Etminaniesfahani, H. Gu, L. M. Naeni, and A. Salehipour, "An efficient relax-and-solve method for the multi-mode resource constrained project scheduling problem", Annals of Operations Research, vol. 338, no. 1, pp. 41-68, 2024.
[35] W. Murray and H. Shek, "A local relaxation method for the cardinality constrained portfolio optimization problem", Computational Optimization and Applications, vol. 53, pp. 681-709, 2012.
[36] E. John and E. A. Yıldırım, "Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension", Computational Optimization and Applications, vol. 41, no. 2, pp. 151-183, 2008.
Xem thêm
##plugins.themes.academic_pro.article.sidebar##
Đã Xuất bản
Sep 30, 2025
Download
Cách trích dẫn
Duy, N. D., L. K. Kien, và P. G. Bao. “Ứng dụng phương pháp khởi đầu nâng Cao nhằm nâng Cao hiệu Quả giải quyết bài toán định tuyến”. Tạp Chí Khoa học Và Công nghệ - Đại học Đà Nẵng, vol 23, số p.h 9A, Tháng Chín 2025, tr 9-15, doi:10.31130/ud-jst.2025.23(9A).360E.
