Abstract
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.