This is a somewhat big question since there are many variations on the VRP. The most studied seems to be the capacitated version, the CVRP, but variations considering time windows, backhaul/linehaul, etc. are also studied, and of course characteristics of the graph and number of vehicles matter too. The most general VRP with no capacity constraint and one vehicle is the TSP, which of course can't be approximated within any constant, so neither can the VRP.Is there research on the approximation complexity classes for variations? Such as where the graph is Euclidean, has triangle inequality, is symmetric v asymmetric, CVRP, VRPTW, DVRP, etc.I was specifically looking at the Clarke-Wright savings algorithm for these questions. I haven't found anything on its approximation ratio, and I realized it might be because the entire problem doesn't have approximation ratios.
Does the vehicle routing problem and variations have approximation ratios or a PTAS?
algorithms;approximation;heuristics