EUVIMEDEUVIMED entdecken
Crossref

Improved Approximations for a CVRP with Unsplittable Demands

Zachary Friggstad, Ramin Mousavi, Mirmahdi Rahgoshay, Mohammad R. Salavatipour

Mathematics of Operations Research · 17.10.2025

DOI: 10.1287/moor.2022.0097 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics of Operations Research, online erschienen am 17.10.2025. Verfasst von Zachary Friggstad und 3 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 12 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this paper, we present improved approximation algorithms for the (unsplittable) capacitated vehicle routing problem (CVRP) in general metrics. In the CVRP, we are given a set of points (clients) V together with a depot r in a metric space, with each [Formula: see text] having a demand [Formula: see text] and a vehicle of bounded capacity Q. The goal is to find a minimum cost collection of tours for the vehicle, each starting and ending at the depot, such that each client is visited at least once and the total demands of the clients in each tour are at most Q. In the unsplittable variant we study, the demand of a node must be served entirely by one tour. We present two approximation algorithms for the unsplittable CVRP: a combinatorial [Formula: see text]-approximation, where [Formula: see text] is the approximation factor for the traveling salesman problem, and an approximation algorithm based on linear programming rounding with approximation guarantee [Formula: see text] in [Formula: see text] time. Funding: This work was supported by the Canadian Network for Research and Innovation in Machining Technology and the Natural Sciences and Engineering Research Council of Canada. Z. Friggstad was supported by an NSERC Discovery Grant and a Discovery Grant Accelerator. M. R. Salavatipoura was supported by an NSERC Discovery Grant.

Zitieren

APA

Friggstad, Z., Mousavi, R., Rahgoshay, M., & Salavatipour, M. R. (2025). Improved Approximations for a CVRP with Unsplittable Demands. Mathematics of Operations Research. https://doi.org/10.1287/moor.2022.0097

Vancouver

Friggstad Z, Mousavi R, Rahgoshay M, Salavatipour MR. Improved Approximations for a CVRP with Unsplittable Demands. Mathematics of Operations Research. 2025. doi:10.1287/moor.2022.0097

BibTeX
@article{Friggstad2025,
  author = {Friggstad, Zachary and Mousavi, Ramin and Rahgoshay, Mirmahdi and Salavatipour, Mohammad R.},
  title = {Improved Approximations for a CVRP with Unsplittable Demands},
  journal = {Mathematics of Operations Research},
  year = {2025},
  doi = {10.1287/moor.2022.0097}
}
Kostenlos starten →