Vehicle routing is an important and active research topic in computer science and operations research. In this paper, we give some approximation results for two well-known capacitated vehicle routing problems.Our first result concerns the Capacitated Orienteering problem in Euclidean graphs. We are here given an Euclidean graph G, where each node has a profit value and a demand value, starting and end nodes s, t, a length bound D and a capacity bound C. The goal is to find an s-t-path of length at most D that collects maximum profit from nodes whose total demand does not exceed the capacity bound C. We give a PTAS for this problem, extending the corresponding known result given by Chen and Har-Peled [Chen, K., and S. Har-Peled, The Euclidean orienteering problem revisited. SIAM Journal on Computing, 2007] for the uncapacitated version.Our second result concerns the School Bus problem with regret minimization, where we are given a general metric graph, and the task is to design the routes for a given set of buses of limited capacity to transport a set of children to a school, while minimizing a certain regret threshold. Under the standard hypothesis P≠. NP, we show that this problem cannot be approximated.
- Approximation algorithms
- Vehicle routing