论文标题
提高电容车辆路由的近似值
Improving the Approximation Ratio for Capacitated Vehicle Routing
论文作者
论文摘要
我们为电容车辆路由设计了一种新的近似算法。我们的算法对于一般电容的车辆路由以及单位需求的情况和可分解的变体提供了更好的近似值。我们的结果在任意度量空间中。这是Haimovich和Rinnooy Kan和Altinkemer and Gavish的古典旅行分区算法的首次改进。
We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for the unit-demand case and the splittable variant. Our results hold in arbitrary metric spaces. This is the first improvement upon the classical tour partitioning algorithm by Haimovich and Rinnooy Kan and Altinkemer and Gavish.
