Locating Depots for Capacitated Vehicle Routing

Inge Li Gørtz, Viswanath Nagarajan

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    1 Downloads (Pure)

    Abstract

    We study a location-routing problem in the context of capacitated vehicle routing. The input to k-LocVRP is a set of demand locations in a metric space and a fleet of k 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. To achieve this result, we reduce k-LocVRP to the following generalization of k median, which might be of independent interest. Given a metric (V, d), bound k and parameter ρ ∈ R+, the goal in the k median forest problem is to find S ⊆ V with |S| = k minimizing: E u∈V d(u, S) + ρ · d(MST(V/S) ), where d(u, S) = minw∈S d(u,w) and MST(V/S) is a minimum spanning tree in the graph obtained by contracting S to a single vertex. We give a (3+E)-approximation algorithm for k median forest, which leads to a (12+E)-approximation algorithm for k-LocVRP, for any constant E > 0. The algorithm for k median forest is t-swap local search, and we prove that it has locality gap 3 + 2 t ; this generalizes the corresponding result for k median [3]. Finally we consider the k median forest problem when there is a different (unrelated) cost function c for the MST part, i.e. the objective is Eu∈V d(u, S) + c(MST(V/S) ). We show that the locality gap for this problem is unbounded even under multi-swaps, which contrasts with the c = d case. Nevertheless, we obtain a constant-factor approximation algorithm, using an LP based approach along the lines of [12].
    Original languageEnglish
    Title of host publicationApproximation, Randomization, and Combinatorial Optimization : 14th InternationalWorkshop, APPROX 2011 and 15th InternationalWorkshop, RANDOM 2011 Princeton, NJ, USA, August 17-19, 2011 Proceedings
    Volume6845
    PublisherSpringer
    Publication date2011
    Pages230-241
    ISBN (Print)978-3-642-22934-3
    ISBN (Electronic)978-3-642-22935-0
    DOIs
    Publication statusPublished - 2011
    EventInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and the International Workshop on Randomization and Computation - Princeton, New Jersey, USA
    Duration: 1 Jan 2011 → …
    Conference number: 14 & 15

    Conference

    ConferenceInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and the International Workshop on Randomization and Computation
    Number14 & 15
    CityPrinceton, New Jersey, USA
    Period01/01/2011 → …
    SeriesLecture Notes in Computer Science
    ISSN0302-9743

    Cite this

    Gørtz, I. L., & Nagarajan, V. (2011). Locating Depots for Capacitated Vehicle Routing. In Approximation, Randomization, and Combinatorial Optimization: 14th InternationalWorkshop, APPROX 2011 and 15th InternationalWorkshop, RANDOM 2011 Princeton, NJ, USA, August 17-19, 2011 Proceedings (Vol. 6845, pp. 230-241). Springer. Lecture Notes in Computer Science https://doi.org/10.1007/978-3-642-22935-0_20
    Gørtz, Inge Li ; Nagarajan, Viswanath. / Locating Depots for Capacitated Vehicle Routing. Approximation, Randomization, and Combinatorial Optimization: 14th InternationalWorkshop, APPROX 2011 and 15th InternationalWorkshop, RANDOM 2011 Princeton, NJ, USA, August 17-19, 2011 Proceedings. Vol. 6845 Springer, 2011. pp. 230-241 (Lecture Notes in Computer Science).
    @inproceedings{c853692ab958498d84561ee290944b0f,
    title = "Locating Depots for Capacitated Vehicle Routing",
    abstract = "We study a location-routing problem in the context of capacitated vehicle routing. The input to k-LocVRP is a set of demand locations in a metric space and a fleet of k 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. To achieve this result, we reduce k-LocVRP to the following generalization of k median, which might be of independent interest. Given a metric (V, d), bound k and parameter ρ ∈ R+, the goal in the k median forest problem is to find S ⊆ V with |S| = k minimizing: E u∈V d(u, S) + ρ · d(MST(V/S) ), where d(u, S) = minw∈S d(u,w) and MST(V/S) is a minimum spanning tree in the graph obtained by contracting S to a single vertex. We give a (3+E)-approximation algorithm for k median forest, which leads to a (12+E)-approximation algorithm for k-LocVRP, for any constant E > 0. The algorithm for k median forest is t-swap local search, and we prove that it has locality gap 3 + 2 t ; this generalizes the corresponding result for k median [3]. Finally we consider the k median forest problem when there is a different (unrelated) cost function c for the MST part, i.e. the objective is Eu∈V d(u, S) + c(MST(V/S) ). We show that the locality gap for this problem is unbounded even under multi-swaps, which contrasts with the c = d case. Nevertheless, we obtain a constant-factor approximation algorithm, using an LP based approach along the lines of [12].",
    author = "G{\o}rtz, {Inge Li} and Viswanath Nagarajan",
    year = "2011",
    doi = "10.1007/978-3-642-22935-0_20",
    language = "English",
    isbn = "978-3-642-22934-3",
    volume = "6845",
    pages = "230--241",
    booktitle = "Approximation, Randomization, and Combinatorial Optimization",
    publisher = "Springer",

    }

    Gørtz, IL & Nagarajan, V 2011, Locating Depots for Capacitated Vehicle Routing. in Approximation, Randomization, and Combinatorial Optimization: 14th InternationalWorkshop, APPROX 2011 and 15th InternationalWorkshop, RANDOM 2011 Princeton, NJ, USA, August 17-19, 2011 Proceedings. vol. 6845, Springer, Lecture Notes in Computer Science, pp. 230-241, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and the International Workshop on Randomization and Computation, Princeton, New Jersey, USA, 01/01/2011. https://doi.org/10.1007/978-3-642-22935-0_20

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

    Approximation, Randomization, and Combinatorial Optimization: 14th InternationalWorkshop, APPROX 2011 and 15th InternationalWorkshop, RANDOM 2011 Princeton, NJ, USA, August 17-19, 2011 Proceedings. Vol. 6845 Springer, 2011. p. 230-241 (Lecture Notes in Computer Science).

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    TY - GEN

    T1 - Locating Depots for Capacitated Vehicle Routing

    AU - Gørtz, Inge Li

    AU - Nagarajan, Viswanath

    PY - 2011

    Y1 - 2011

    N2 - We study a location-routing problem in the context of capacitated vehicle routing. The input to k-LocVRP is a set of demand locations in a metric space and a fleet of k 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. To achieve this result, we reduce k-LocVRP to the following generalization of k median, which might be of independent interest. Given a metric (V, d), bound k and parameter ρ ∈ R+, the goal in the k median forest problem is to find S ⊆ V with |S| = k minimizing: E u∈V d(u, S) + ρ · d(MST(V/S) ), where d(u, S) = minw∈S d(u,w) and MST(V/S) is a minimum spanning tree in the graph obtained by contracting S to a single vertex. We give a (3+E)-approximation algorithm for k median forest, which leads to a (12+E)-approximation algorithm for k-LocVRP, for any constant E > 0. The algorithm for k median forest is t-swap local search, and we prove that it has locality gap 3 + 2 t ; this generalizes the corresponding result for k median [3]. Finally we consider the k median forest problem when there is a different (unrelated) cost function c for the MST part, i.e. the objective is Eu∈V d(u, S) + c(MST(V/S) ). We show that the locality gap for this problem is unbounded even under multi-swaps, which contrasts with the c = d case. Nevertheless, we obtain a constant-factor approximation algorithm, using an LP based approach along the lines of [12].

    AB - We study a location-routing problem in the context of capacitated vehicle routing. The input to k-LocVRP is a set of demand locations in a metric space and a fleet of k 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. To achieve this result, we reduce k-LocVRP to the following generalization of k median, which might be of independent interest. Given a metric (V, d), bound k and parameter ρ ∈ R+, the goal in the k median forest problem is to find S ⊆ V with |S| = k minimizing: E u∈V d(u, S) + ρ · d(MST(V/S) ), where d(u, S) = minw∈S d(u,w) and MST(V/S) is a minimum spanning tree in the graph obtained by contracting S to a single vertex. We give a (3+E)-approximation algorithm for k median forest, which leads to a (12+E)-approximation algorithm for k-LocVRP, for any constant E > 0. The algorithm for k median forest is t-swap local search, and we prove that it has locality gap 3 + 2 t ; this generalizes the corresponding result for k median [3]. Finally we consider the k median forest problem when there is a different (unrelated) cost function c for the MST part, i.e. the objective is Eu∈V d(u, S) + c(MST(V/S) ). We show that the locality gap for this problem is unbounded even under multi-swaps, which contrasts with the c = d case. Nevertheless, we obtain a constant-factor approximation algorithm, using an LP based approach along the lines of [12].

    U2 - 10.1007/978-3-642-22935-0_20

    DO - 10.1007/978-3-642-22935-0_20

    M3 - Article in proceedings

    SN - 978-3-642-22934-3

    VL - 6845

    SP - 230

    EP - 241

    BT - Approximation, Randomization, and Combinatorial Optimization

    PB - Springer

    ER -

    Gørtz IL, Nagarajan V. Locating Depots for Capacitated Vehicle Routing. In Approximation, Randomization, and Combinatorial Optimization: 14th InternationalWorkshop, APPROX 2011 and 15th InternationalWorkshop, RANDOM 2011 Princeton, NJ, USA, August 17-19, 2011 Proceedings. Vol. 6845. Springer. 2011. p. 230-241. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-22935-0_20