Approximation Algorithms for Group Coverage and Vehicle Routing Problems

• Author / Creator

  Martin, Christopher S

• In this thesis, we present approximation algorithms for various NP-hard vehicle routing problems, as well as for a related maximum group coverage problem. Our main contribution is a framework to build good constant-factor approximation algorithms for variants of the multi-depot $k$-travelling repairmen problem (sometimes referred to as the multi-depot minimum latency problem), which has been studied previously. We use our framework to create approximations for several capacitated variants of the problem, for which only heuristic solutions exist currently. Our framework can also be used to approximate the (uncapacitated) multi-depot $k$-travelling repairmen problem; interestingly, the approximation ratio we obtain matches the current-best result for the problem. To achieve these results, we develop a Linear Programming (LP) based approximation algorithm to the maximum coverage with groups problem (or MCG), which is used as a subroutine in our framework. This problem has not received much attention in the literature, as it is mostly used as a subroutine for bigger problems. We use the linear programming relaxation of an integer program, which we first solve using a suitable (approximate) oracle, and then show how to deterministically round the solution to an integer solution without losing too much over the optimal. This also shows the integrality gap of the LP we consider. We finally consider the orienteering problem with time-windows, and a special case called the deadline orienteering problem. Both of these problems have been well-studied, and currently no constant approximation is known for either problem; finding a constant approximation for either one is a big open problem. We present a constant-approximation for a fairly general special case of the deadline orienteering problem that runs in sub-exponential time (which can also be extended to the time-windows version); this gives a strong indication that constant approximations for these problems exist. We also give approximations for various problems related to the deadline orienteering problem, in the hope that they might give more insight into the problem.

• Subjects / Keywords

  • Routing
  • Latency
  • Deadline
  • Coverage
  • Problem
  • Capacitated
  • Approximation
  • Orienteering
  • Algorithm
  • Vehicle
  • Group

• Graduation date

  Fall 2016

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R35D8NP1W

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.