Efficient approximation of the metric CVRP in spaces of fixed doubling dimension

Michael Khachay (), Yuri Ogorodnikov () and Daniel Khachay ()
Additional contact information
Michael Khachay: Krasovsky Institute of Mathematics and Mechanics
Yuri Ogorodnikov: Krasovsky Institute of Mathematics and Mechanics
Daniel Khachay: KEDGE Business School

Journal of Global Optimization, 2021, vol. 80, issue 3, No 8, 679-710

Abstract: Abstract The capacitated vehicle routing problem (CVRP) is the well-known combinatorial optimization problem having numerous practically important applications. CVRP is strongly NP-hard (even on the Euclidean plane), hard to approximate in general case and APX-complete for an arbitrary metric. Meanwhile, for the geometric settings of the problem, there are known a number of quasi-polynomial and even polynomial time approximation schemes. Among these results, the well-known QPTAS proposed by Das and Mathieu appears to be the most general. In this paper, we propose the first extension of this scheme to a more wide class of metric spaces. Actually, we show that the metric CVRP has a QPTAS any time when the problem is set up in the metric space of any fixed doubling dimension $$d>1$$ d > 1 and the capacity does not exceed $$\mathrm {polylog}{(n)}$$ polylog ( n ) .

Keywords: Capacitated vehicle routing problem; Fixed doubling dimension; Quasi-polynomial time approximation scheme (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-020-00990-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:80:y:2021:i:3:d:10.1007_s10898-020-00990-0

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-020-00990-0

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().