Approximation Schemes for Capacity Vehicle Routing Problems: A Survey

Abstract

The Capacity Vehicle Routing Problem (CVRP) pertains to the combinatorial optimization problem of identifying the optimal route for vehicles with a capacity constraint of k to travel from the depots to customers, which minimizes the total distance traveled. The Capacitated Vehicle Routing Problem (CVRP), which is essential to modelling logistics networks, has drawn a lot of interest in the field of combinatorial optimization. It has been established that the CVRP (Capacitated Vehicle Routing Problem) with a value of k greater than or equal to three exhibits computational complexity that is classified as NP-hard. Furthermore, it has been established that the problem is APXhard. It has been previously established that the solution is not approximatable in a metric space. Furthermore, this constitutes the principal challenge among the array of issues that confront Arora's approximation algorithm. The outstanding matter concerns the presence of a (1+$\epsilon$) PTAS (polynomial time approximation scheme) for the capacity vehicle routing problem in Euclidean space, regardless of the vehicle's capacity. The objective of this manuscript is to furnish a thorough and all-encompassing survey of the research progressions in the domain, encompassing the evolution of the field from its inception to the most recent cutting-edge discoveries. © 2023 IEEE.