Accelerating the Clarke-Wright algorithm using GPUs

• Autorzy: Guerriero Francesca , Saccomanno Francesco Paolo

Identyfikatory

DOI

10.2478/candc-2024-0016

• Języki publikacji: EN

Abstrakty

EN

The Capacitated Vehicle Routing Problem (CVRP) is a combinatorial optimization problem that seeks to determine the optimal set of routes for a fleet of vehicles, with limited capacity, to deliver goods to customers while minimizing the total cost. Due to its NP-hard nature, finding exact solutions for the large-scale CVRP instances is computationally intractable. Therefore, heuristics and metaheuristics are widely employed to find approximate optimal solutions. Among these, the Clarke-Wright (CW) algorithm is a popular greedy approach that constructs routes by iteratively merging nodes to minimize transportation costs. This study presents an implementation of the CW algorithm in graphics processing units (GPUs) using the CUDA (Compute Unified Device Architecture) framework. The GPU implementation is compared to its CPU counterpart in terms of execution time and performance. The results demonstrate significant speed-ups achieved by the GPU implementation, particularly for large-scale instances. Performance gains can be attributed to the parallel processing capabilities of GPUs, enabling efficient execution of the algorithm computational steps.

Słowa kluczowe

EN

capacitated vehicle routing problem; CVRP; Clarke-Wright algorithm; GPU computing; CUDA; heuristics

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2024
• Tom: Vol. 53, No. 2
• Strony: 371--383
• Opis fizyczny: Bibliogr. 20 poz., rys., tab.

Twórcy

autor

Guerriero Francesca

• Department of Mechanical, Energy and Management Engineering, University of Calabria, Italy

autor

Saccomanno Francesco Paolo

• Department of Mechanical, Energy and Management Engineering, University of Calabria, Italy

Bibliografia

• Abdelatti, M.F. and Sodhi, M.S. (2020) An improved gpu-accelerated heuristic technique applied to the capacitated vehicle routing problem. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO ’20. Association for Computing Machinery, New York, NY, USA, 663–671.
• Accorsi, L. and Vigo, D. (2021) A fast and scalable heuristic for the solution of large-scale capacitated vehicle routing problems. Transportation Science 55(4), 832–856.
• Arnold, F., Gendreau, M. and Sörensen, K. (2019) Efficiently solving very large-scale routing problems. Computers & Operations Research 107, 32–42.
• Augerat, P., Belenguer, J.M., Benavent, E., Corberan, A., Naddef, D. and Rinaldi, G. (1995) Computational results with a branch and cut code for the capacitated vehicle routing problem. Tech. rep., Research report RR949-M. ARTEMIS-IMAG, France.
• Benaini, A. and Berrajaa, A. (2016) Solving the dynamic vehicle routing problem on gpu. In: 2016 3rd International Conference on Logistics Operations Management (GOL), IEEE, 1–6.
• Benaini, A. and Berrajaa, A. (2018) Genetic algorithm for large dynamic vehicle routing problem on gpu. In: 2018 4th International Conference on Logistics Operations Management (GOL), IEEE, 1–9.
• Benaini, A., Berrajaa, A. and Daoudi, E.M. (2016) Solving the vehicle routing problem on gpu. In: A. El Oualkadi, F. Choubani, A. El Moussati, eds., Proceedings of the Mediterranean Conference on Information & Communication Technologies 2015. Springer International Publishing, Cham, 239–248.
• Benaini, A., Berrajaa, A. and Daoudi, E.M. (2017) Parallel implementation of the multi capacity vrp on gpu. In: A. Rocha, M. Serrhini, C. Felgueiras, eds., Europe and MENA Cooperation Advances in Information and Communication Technologies. Springer International Publishing, Cham, 353–364.
• Borčinová, Z. (2022) Kernel search for the capacitated vehicle routing problem. Applied Sciences 12(22).
• Christofides, N. (1979) Combinatorial Optimization. A Wiley-Interscience publication. Wiley
• Clarke, G. and Wright, J.W. (1964) Scheduling of vehicles from a central depot to a number of delivery points. Operations Research 12(4), 568–581.
• Diego, F.J., Gómez, E.M., Ortega-Mier, M. and García-Sánchez, Á. (2012) Parallel cuda architecture for solving de VRP with ACO. In: S.P. Sethi, M. Bogataj, L. Ros-McDonnell, eds., Industrial Engineering: Innovative Networks. Springer London, London, 385–393.
• Hijma, p., Heldens, S., Sciocco, A., van Werkhoven, B. and Bal, H.E. (2023) Optimization Techniques for GPU Programming. ACM Comput. Surv. 55(11), 1–81.
• Laporte, G. (1992) The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research 59(3), 345–358.
• Liu, F., Lu, C., Gui, L., Zhang, Q., Tong, X. and Yuan, M. (2023) Heuristics for vehicle routing problem: A survey and recent advances. arXiv:https://arxiv.org/abs/2303.04147
• Luong, T.V., Melab, N. and Talbi, E.G. (2013) Gpu computing for parallel local search metaheuristic algorithms. IEEE Transactions on Computers 62(1), 173–185.
• Nurcahyo, R., Irawan, D.A. and Kristanti, F. (2023) The effectiveness of the Clarke & Wright savings algorithm in determining logistics distribution routes (case study pt.xyz). E3S Web of Conferences 426. EDP Sciences.
• Tunnisaki, F. and Sutarman, F. (2023) Clarke and Wright savings algorithm as solutions vehicle routing problem with simultaneous pickup delivery (vrpspd). Journal of Physics: Conference Series 2421(1), 012045.
• Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T. and Subramanian, A. (2017) New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research 257(3), 845–858.
• Yelmewad, P. and Talawar, B. (2021) Parallel version of local search heuristic algorithm to solve capacitated vehicle routing problem. Cluster Computing 24(4), 3671–3692.