markus_swartz wrote: > Hi, > > I´m trying to write some code in order to find a good approximation to > the solution of a Capacitated Vehicle Routing Problem (similar to the > Multiple Traveling Salesman Problem). I am aware that´s an NP-hard > problem. > > Does anybody have an idea of what relaxation could be used in this > case? I wish to keep the program as simple as possible. Additionaly, > what would be the best criteria to choose the next arc to be > included/excluded when branching? Does anybody have an idea (draft) of > how to implement this algorithm? > > I´d appreciate any help or pointers.
Disclaimer: I'm no expert in this problem. I'd expect to use branch techniques when trying to find an optimum. I probably wouldn't use that to much when looking for a good fast heuristic. I'd expect GLS/FLS to be easy to implement and to work well. See http://cswww.essex.ac.uk/staff/voudcx/doc/phd_pdf.zip HTH --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---