A new approximation algorithm for the capacitated vehicle routing problem on a tree (Q5943821): Difference between revisions

Given a tree \((V,E)\), where \(V\) is a set of \(n\) vertices and \(E\) is a set of edges. Customers are located on the vertices and each customer has a positive demand. Each edge is associated with a nonnegative length. The demands are served by a fleet of identical vehicles with limited capacity starting at a fixed vertex called depot. It is assumed that the demand of a customer is splittable, i.e. it can be served by more than one vehicle. The problem is to find a set of tours beginning at the depot, visiting a subset of customers to serve (partially) their demands, and returning to the depot without violating the capacity constraint and with minimum sum of lengths.