Premium
Locating depots for capacitated vehicle routing
Author(s) -
Gørtz Inge Li,
Nagarajan Viswanath
Publication year - 2016
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21683
Subject(s) - vehicle routing problem , routing (electronic design automation) , generalization , context (archaeology) , approximation algorithm , mathematical optimization , metric (unit) , metric space , computer science , facility location problem , set (abstract data type) , constant (computer programming) , tree (set theory) , steiner tree problem , minimum spanning tree , mathematics , combinatorics , algorithm , discrete mathematics , mathematical analysis , computer network , operations management , economics , programming language , paleontology , biology
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 . © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(2), 94–103 2016