论文标题
带有可变电源的最大营利性路由问题的APX
An APX for the Maximum-Profit Routing Problem with Variable Supply
论文作者
论文摘要
在本文中，我们研究了可变供应（MPRP-VS）的最大营养路由问题。这是最大利润的公共交通路线计划问题的更通用版本，或者只是在\ cite {armaselu-petra}中引入的最大利润路由问题（MPRP）。在此新版本中，在网站$ i $提供的数量$ q_i（t）$是线性增加的$ t $，而不是\ cite {armaselu-petra}，那里的数量是恒定的。我们的主要结果是$ 5.5 \ log {t}（1 +ε）（1 + \ frac {1} {1 + \ \ sqrt {m}}）^2 $近似算法，其中$ t $是最新的时间窗口，$ m $是使用的车辆数量。此外，在某些条件下，我们在\ cite {armaselu-petra}中改进了MPRP算法。
In this paper, we study the Maximum-Profit Routing Problem with Variable Supply (MPRP-VS). This is a more general version of the Maximum-Profit Public Transportation Route Planning Problem, or simply Maximum-Profit Routing Problem (MPRP), introduced in \cite{Armaselu-PETRA}. In this new version, the quantity $q_i(t)$ supplied at site $i$ is linearly increasing in time $t$, as opposed to \cite{Armaselu-PETRA}, where the quantity is constant in time. Our main result is a $5.5 \log{T} (1 + ε) (1 + \frac{1}{1 + \sqrt{m}})^2$ approximation algorithm, where $T$ is the latest time window and $m$ is the number of vehicles used. In addition, we improve upon the MPRP algorithm in \cite{Armaselu-PETRA} under certain conditions.
