Locating Depots for Capacitated Vehicle Routing
In typical facility location problems, one wishes to locate centers and connect clients directly to centers at minimum cost. On the other hand, the goal in Vehicle Routing Problems (VRPs) is to compute routes for vehicles originating from a given set of depots. Location routing problems represent an integrated approach, where one wishes to make combined decisions on facility location and vehicle routing. This is a widely researched area in operations research. Most of the papers deal with exact methods or heuristics, without any performance guarantees. In this paper the authors present an approximation algorithm for a location routing problem in context of capacitated vehicle routing.