摘要：We consider the Euclidean Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). For the long time, approximability of this well-known problem in the class of algorithms with theoretical guarantees was poorly studied. This year, for the case of a single depot, we proposed two approximation algorithms, which are the Efficient Polynomial Time Approximation Schemes (EPTAS) for any fixed given capacityqand the numberpof mutually disjunctive time windows. The former scheme extends the celebrated approach proposed by M. Haimovich and A. Rinnooy Kan and allows the evident parallelization, while the latter one has an improved time complexity bound and the enlarged domain in termsq=q(n)andp=p(n),where it retains polynomial time complexity. In this paper, we announce an extension of these results to the case of multiple depots. So, the first scheme is also EPTAS for any fixed parametersq, p,andm, where m is the number of depots, and remains PTAS forq= o(loglog n) andmp= o(log logn). In other turn, the second one is a PTAS forp3q4=O(logn) and (pq)2logm=O(logn).
关键词：KeywordsCapacitated Vehicle Routing ProblemTime WindowsMultiple DepotsPolynomial Time Approximation Schemes
