论文标题
改进了具有固定容量的电容车辆路由的近似算法
Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
论文作者
论文摘要
电容的车辆路由问题（CVRP）是组合优化中最广泛研究的问题之一。根据客户的需求，我们区分了CVRP的三种变体：单位需求，可分解且无法确定。在本文中，我们考虑了$ k $ -CVRP的一般指标和一般图表，其中$ k $是车辆容量。对于任何固定的$ k \ geq3 $，这三个版本都是APX-HARD。假设公制TSP的近似值为$ \ frac {3} {2} $。我们提出$（\ frac {5} {2}-θ（\ frac {1} {\ sqrt {k}}））$ - 可分解和单位要求的近似算法，以及一个$（\ frac {5} {2}+\ ln2-θ（\ frac {1} {\ sqrt {k}}））$ - 近似算法的近似算法是无法命中的。当$ k $小于足够大的值时，我们的近似值比以前的结果好，约为$ 1.7 \ times10^7 $。 对于$ k $的少量值，我们设计了独立而优雅的算法，并进一步改进。对于可分割和单位需求的情况，我们将近似值从$ k = 3 $的$ 1.792 $提高到$ 1.500 $，从$ k = 4 $的$ k = 3 $，从1.750美元$ 1.750 $。对于不可扣除的情况，我们将近似值从$ k = 3 $的$ 1.792 $提高到$ 1.500 $，从$ 2.051 $ $ k = 4 $，从$ k = 4 $的$ 1.750 $，从$ 2.249 $到$ 2.157 $ $ k = 5 $。 $ k = 3 $的近似值令人惊讶地达到的值与可分布的情况相同。我们的技术，例如Ex-ITP-经典ITP方法的扩展，也有可能改善其他路由问题的算法。
The Capacitated Vehicle Routing Problem (CVRP) is one of the most extensively studied problems in combinatorial optimization. Based on customer demand, we distinguish three variants of CVRP: unit-demand, splittable, and unsplittable. In this paper, we consider $k$-CVRP in general metrics and on general graphs, where $k$ is the vehicle capacity. All three versions are APX-hard for any fixed $k\geq3$. Assume that the approximation ratio of metric TSP is $\frac{3}{2}$. We present a $(\frac{5}{2}-Θ(\frac{1}{\sqrt{k}}))$-approximation algorithm for the splittable and unit-demand cases, and a $(\frac{5}{2}+\ln2-Θ(\frac{1}{\sqrt{k}}))$-approximation algorithm for the unsplittable case. Our approximation ratio is better than the previous results when $k$ is less than a sufficiently large value, approximately $1.7\times10^7$. For small values of $k$, we design independent and elegant algorithms with further improvements. For the splittable and unit-demand cases, we improve the approximation ratio from $1.792$ to $1.500$ for $k=3$, and from $1.750$ to $1.500$ for $k=4$. For the unsplittable case, we improve the approximation ratio from $1.792$ to $1.500$ for $k=3$, from $2.051$ to $1.750$ for $k=4$, and from $2.249$ to $2.157$ for $k=5$. The approximation ratio for $k=3$ surprisingly achieves the same value as in the splittable case. Our techniques, such as EX-ITP -- an extension of the classic ITP method, have the potential to improve algorithms for other routing problems as well.
