Locating depots for capacitated vehicle routing

Locating depots for capacitated vehicle routing

0.00 Avg rating0 Votes
Article ID: iaor20162816
Volume: 68
Issue: 2
Start Page Number: 94
End Page Number: 103
Publication Date: Sep 2016
Journal: Networks
Authors: ,
Keywords: location, networks, combinatorial optimization, heuristics: local search
Abstract:

We study a location‐routing problem in the context of capacitated vehicle routing. The input to the k‐location capacitated vehicle routing problem (k‐LocVRP) consists of a set of demand locations in a metric space and a fleet of k identical vehicles, each of capacity Q. The objective is to locate k depots, one for each vehicle, and compute routes for the vehicles so that all demands are satisfied and the total cost is minimized. Our main result is a constant‐factor approximation algorithm for k‐LocVRP. In obtaining this result, we introduce a common generalization of the k‐median and minimum spanning tree problems (called k median forest), which might be of independent interest. We give a local‐search based ( 3 + ϵ ) ‐approximation algorithm for k median forest, which leads to a ( 12 + ϵ ) ‐approximation algorithm for k‐LocVRP, for any constant ϵ > 0 .

Reviews

Required fields are marked *. Your email address will not be published.