Locating Depots for Capacitated Vehicle Routing

Inge Li Gørtz, Viswanath Nagarajan

Research output: Contribution to journalJournal articleResearchpeer-review

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.
Original languageEnglish
JournalNetworks
Volume68
Issue number2
Pages (from-to)94-103
ISSN0028-3045
DOIs
Publication statusPublished - 2016

Keywords

  • Vehicle routing
  • Facility location
  • Approximation algorithms

Fingerprint Dive into the research topics of 'Locating Depots for Capacitated Vehicle Routing'. Together they form a unique fingerprint.

Cite this