Minimizing Latency of Capacitated k-Tours
Minimizing Latency of Capacitated k-Tours
复制标题
最大限度地减少容量 k-Tour 的延迟
DOI：
10.1007/s00453-017-0337-x
复制
发表时间：
2018
期刊：
影响因子：
1.1
通讯作者：
M. Salavatipour
中科院分区：
文献类型：
--
作者：
Christopher S. Martin;M. Salavatipour
我们研究了有能力车辆路径问题的变体。在多车场有能力的维修人员问题（MD-CkTRP）中，我们有一个客户集合，由k辆相同车辆组成的车队中的一辆车在给定的车场提供服务。每个客户端都有一个必须满足的给定需求，每辆车在必须在其原始仓库重新补给之前最多可以携带Q个需求。我们希望以一种遵守约束的方式路由车辆，同时最小化服务客户端所需的平均时间（延迟）。这将多站点k-Travelling修理工问题（dd - ktrp） （Chaudhuri等人在IEEE-FOCS第44期，第36-45页，2003年；Post和Swamy在ACM-SIAM SODA第26期，第512-531页，2015年）推广到有能力的车辆设置，虽然之前已经对其进行了研究（Lysgaard和Wholk在Eur J Oper Res 236(3): 800-810页，2014年），但没有已知的具有证明比例的近似算法。我们对这个一般问题给出一个42.49的近似值，当客户有单位需求时，将这个常数细化为25.49。据我们所知，这是针对具有延迟目标的有能力车辆路径问题的第一个常数因子近似。我们通过开发一个框架来实现这些结果，该框架允许我们解决更广泛的延迟问题，并为该框架中使用的各种定向风格的预言机制作。我们还展示了一个简单的LP舍入算法对于群的最大覆盖问题（MCG）具有更好的近似比，Chekuri和Kumar首先研究了这个问题（逼近，随机化和组合优化，算法和技术，第72-83页，2004），并将其用作我们框架中的子程序。当限制在无能力设置时，我们对MD-CkTRP的近似比率与它最知名的边界相匹配（Post和Swamy在第26届ACM-SIAM SODA， pp 512-531, 2015）。使用我们的框架，对我们的oracle或我们的MCG近似的任何改进都将导致对相应k-TRP问题的改进近似。
We study variants of the capacitated vehicle routing problem. In the multiple depot capacitatedk-travelling repairmen problem (MD-CkTRP), we have a collection of clients to be served by one vehicle in a fleet of k identical vehicles based at given depots. Each client has a given demand that must be satisfied, and each vehicle can carry a total of at most Q demand before it must resupply at its original depot. We wish to route the vehicles in a way that obeys the constraints while minimizing the average time (latency) required to serve a client. This generalizes the Multi-depot k-Travelling Repairman Problem (MD-kTRP) (Chaudhuri et al. in 44th IEEE-FOCS, pp 36–45, 2003; Post and Swamy in 26th ACM-SIAM SODA, pp 512–531, 2015) to the capacitated vehicle setting, and while it has been previously studied (Lysgaard and Wholk in Eur J Oper Res 236(3):800–810, 2014), no approximation algorithm with a proven ratio is known. We give a 42.49-approximation to this general problem, and refine this constant to 25.49 when clients have unit demands. As far as we are aware, these are the first constant-factor approximations for capacitated vehicle routing problems with a latency objective. We achieve these results by developing a framework allowing us to solve a wider range of latency problems, and crafting various orienteering-style oracles for use in this framework. We also show a simple LP rounding algorithm has a better approximation ratio for the maximum coverage problem with groups (MCG), first studied by Chekuri and Kumar (Approximation, randomization, and combinatorial optimization, algorithms and techniques, pp 72–83, 2004), and use it as a subroutine in our framework. Our approximation ratio for MD-CkTRP when restricted to uncapacitated setting matches the best known bound for it (Post and Swamy in 26th ACM-SIAM SODA, pp 512–531, 2015). With our framework, any improvements to our oracles or our MCG approximation will result in improved approximations to the corresponding k-TRP problem.