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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom