On the approximability of two capacitated vehicle routing problems

Adrian Bock, Laura Sanità

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)519-526
Number of pages8
JournalElectronic Notes in Discrete Mathematics
Volume41
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • Approximation algorithms
  • Orienteering
  • Vehicle routing

Fingerprint Dive into the research topics of 'On the approximability of two capacitated vehicle routing problems'. Together they form a unique fingerprint.

  • Cite this