License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.56
URN: urn:nbn:de:0030-drops-68262
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6826/
Martin, Christopher S. ;
Salavatipour, Mohammad R.
Approximation Algorithms for Capacitated k-Travelling Repairmen Problems
Abstract
We study variants of the capacitated vehicle routing problem. In the multiple depot capacitated k-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) [Chekuri and Kumar, IEEE-FOCS, 2003; Post and Swamy, ACM-SIAM SODA, 2015] to the capacitated vehicle setting, and while it has been previously studied [Lysgaard and Wohlk, EJOR, 2014; Rivera et al, Comput Optim Appl, 2015], 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 [APPROX, 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, ACM-SIAM SODA, 2015]. With our framework, any improvements to our oracles or our MCG approximation will result in improved approximations to the corresponding k-TRP problem.
BibTeX - Entry
@InProceedings{martin_et_al:LIPIcs:2016:6826,
author = {Christopher S. Martin and Mohammad R. Salavatipour},
title = {{Approximation Algorithms for Capacitated k-Travelling Repairmen Problems}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {56:1--56:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-026-2},
ISSN = {1868-8969},
year = {2016},
volume = {64},
editor = {Seok-Hee Hong},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6826},
URN = {urn:nbn:de:0030-drops-68262},
doi = {10.4230/LIPIcs.ISAAC.2016.56},
annote = {Keywords: approximation, capacitated, latency, group coverage}
}
|
Keywords: |
|
approximation, capacitated, latency, group coverage |
|
Collection: |
|
27th International Symposium on Algorithms and Computation (ISAAC 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
07.12.2016 |
