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

Cite this

Gørtz, Inge Li ; Nagarajan, Viswanath . / Locating Depots for Capacitated Vehicle Routing. In: Networks. 2016 ; Vol. 68, No. 2. pp. 94-103.
@article{26878a1b7c9545b08f307065f5cefd0f,
title = "Locating Depots for Capacitated Vehicle Routing",
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.",
keywords = "Vehicle routing, Facility location, Approximation algorithms",
author = "G{\o}rtz, {Inge Li} and Viswanath Nagarajan",
year = "2016",
doi = "10.1002/net.21683",
language = "English",
volume = "68",
pages = "94--103",
journal = "Networks",
issn = "0028-3045",
publisher = "JohnWiley & Sons, Inc.",
number = "2",

}

Locating Depots for Capacitated Vehicle Routing. / Gørtz, Inge Li; Nagarajan, Viswanath .

In: Networks, Vol. 68, No. 2, 2016, p. 94-103.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - Locating Depots for Capacitated Vehicle Routing

AU - Gørtz, Inge Li

AU - Nagarajan, Viswanath

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Vehicle routing

KW - Facility location

KW - Approximation algorithms

U2 - 10.1002/net.21683

DO - 10.1002/net.21683

M3 - Journal article

VL - 68

SP - 94

EP - 103

JO - Networks

JF - Networks

SN - 0028-3045

IS - 2

ER -