Efficient Approximation of the Capacitated Vehicle Routing Problem in a Metric Space of an Arbitrary Fixed Doubling Dime
- PDF / 395,379 Bytes
- 6 Pages / 612 x 792 pts (letter) Page_size
- 23 Downloads / 177 Views
UTER SCIENCE
Efficient Approximation of the Capacitated Vehicle Routing Problem in a Metric Space of an Arbitrary Fixed Doubling Dimension M. Yu. Khachaya,b,c,* and Yu. Yu. Ogorodnikova,b,** Presented by Academician of the RAS K.V. Rudakov May 25, 2020 Received May 26, 2020; revised June 1, 2020; accepted June 2, 2020
Abstract—In this paper, for the first time, we provide a quasi-polynomial time approximation scheme for the well-known capacitated vehicle routing problem formulated in metric spaces of an arbitrary fixed doubling dimension. Keywords: capacitated vehicle routing problem, metric spaces of a fixed doubling dimension, quasi-polynomial time approximation scheme DOI: 10.1134/S1064562420040080
The Capacitated Vehicle Routing Problem (CVRP) was first considered by Dantzig and Ramser in their classical work [1] and still remains one of the most intensively studied problems in modern combinatorial optimization. It is well known [2] that CVRP is strongly NP-hard (even on the Euclidean plane), fails to be approximated in the general case, and APXcomplete [3, 4] for an arbitrary metric. At the same time, a number of geometric settings of CVRP admit quasi-polynomial and even polynomialtime approximation schemes. Most of the results concerning the efficient approximation of the problem go back to the classical algorithm of Haimovich and Rinnooy Kan [3]. It is well known that this algorithm is a Polynomial Time Approximation Scheme (PTAS) for the CVRP on the plane with a carrying capacity satisfying the constraint q = o(loglog(n)) . In the recent work [5], this result was extended to the case of metric spaces of fixed doubling dimension. Although a generalized Haimovich–Rinnooy Kan approach has led to PTAS schemes in the case of weaker constraints on q [4, 6] and for some generalizations of CVRP [7–9], whether the general instance of the problem admits a polynomial-time approximation a Krasovskii
Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciences, Yekaterinburg, 620219 Russia b Ural Federal University, Yekaterinburg, 620002 Russia c Omsk State Technical University, Omsk, 644050 Russia *e-mail: [email protected] **e-mail: [email protected]
scheme still remains an open question even on the Euclidean plane. The most general result in this area is the algorithm of Das and Mathieu [10] implementing a quasi-polynomial-time approximation scheme for the general setting of CVRP in finite-dimensional Euclidean spaces. In this paper, the Das–Mathieu approach is extended to metric spaces of an arbitrary fixed doubling dimension d > 1. The approximation scheme proposed below has quasi-polynomial time complexity, assuming that q = O(polylog(n)) . A detailed description of the results will be given in forthcoming works.
PROBLEM STATEMENT The CVRP describes a procedure for choosing an optimal plan for satisfying the demand of a geographically distributed network of consumers by delivering them homogeneous goods from a pickup point by a fleet of (identical) vehicles of given carrying capacit
Data Loading...
