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.
The objective of the CVRP is to deliver a set of customers with known demands on minimum-cost vehicle routes originating and terminating at a depot, considering there are K vehicles and each of them has a limited capacity Q. All the routes must start and end at the depot. The depot and the customers (or cities) are represented by vertices and the roads between them are represented by edges. Each vertice has a demand. Each edge has a weight, corresponding to the distance between the cities. The depot has a fictional demand of 0. Essentially it comes down to finding out the K routes (one for each vehicle) such that each route does not exceed capacity Q and the total cost (distance) is minimum. I want to use a branch-and-bound strategy, branching on arcs. With this type of branching, an arc (xi, xj) is chosen for branching at a node of the search tree in order to extend a partially completed route (xo, xk, ... ,xi). The alternative branching is to reject arc (xi, xj) as a possible extension of the route. I am also aware I need some relaxation method in order to reach a feasible solution in polynomial time. 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. --Markus --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
