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.

  • $\begingroup$ This questions feels like it might be too broad (it admits too many answers; a single answer would have to be very long). I think asking about a specific variation on the vehicle routing problem would be more suitable. Also, what research have you done? We expect you to do a significant amount of research before asking here, and to show us in the question what you've tried/done. For instance, I'd recommend you do a literature search (e.g., via careful searching on Google Scholar) to check for work in the literature before asking. You might just answer your own question! $\endgroup$ – D.W. Aug 10 '15 at 3:00
  • $\begingroup$ @D.W. This is quite broad but I don't think it's too broad, especially since it's asking for references to existing research, rather than an in-depth explanation. I think an expert in the field would be able to answer the question in a reasonable amount of time. $\endgroup$ – David Richerby Aug 10 '15 at 7:50
  • $\begingroup$ @D.W. if it admits many answers that would be wonderful, but AFAICT the answer is "no, there aren't." I've gone through several books/survey articles on the VRP and haven't found anything, will try to edit the research in later. $\endgroup$ – djechlin Aug 10 '15 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.