PTAS for the Euclidean Capacitated Vehicle Routing Problem in R^d
PTAS for the Euclidean Capacitated Vehicle Routing Problem in R^d
复制标题
R^d 中欧几里得容量车辆路径问题的 PTAS
DOI：
10.1007/978-3-319-44914-2_16
复制
发表时间：
2016
影响因子：
3.7
通讯作者：
R. Dubinin
中科院分区：
文献类型：
--
作者：
M. Khachay;R. Dubinin
容量限制车辆路径问题是一个著名的组合优化问题，即使在固定维数的欧氏空间中也是NP难的。30年前，在他们著名的论文中，M。Haimovich和A. Rinnoy Kan提出了第一个PTAS的平面单仓库CVRP基于他们的迭代旅游分区启发式。几十年来，这一结果被许多作者扩展到许多有用的修改的问题，考虑到多个仓库，拿起和交付选项，时间窗口的限制等，但据我们所知，几乎没有这些结果超越欧几里德平面。在本文中，我们试图弥合这一差距，并提出了一个EPTAS的欧几里德CVRP为任何固定的尺寸。
Capacitated Vehicle Routing Problem (CVRP) is the well-known combinatorial optimization problem remaining NP-hard even in the Euclidean spaces of fixed dimension. Thirty years ago, in their celebrated paper, M. Haimovich and A. Rinnoy Kan proposed the first PTAS for the Planar Single Depot CVRP based on their Iterated Tour Partition heuristic. For decades, this result was extended by many authors to numerous useful modifications of the problem taking into account multiple depots, pick up and delivery options, time window restrictions, etc. But, to the best of our knowledge, almost none of these results go beyond the Euclidean plane. In this paper, we try to bridge this gap and propose an EPTAS for the Euclidean CVRP for any fixed dimension.