On the approximability of two capacitated vehicle routing problems

Adrian Bock, Laura Sanità

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)


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.

Originele taal-2Engels
Pagina's (van-tot)519-526
Aantal pagina's8
TijdschriftElectronic Notes in Discrete Mathematics
StatusGepubliceerd - 2013
Extern gepubliceerdJa


Duik in de onderzoeksthema's van 'On the approximability of two capacitated vehicle routing problems'. Samen vormen ze een unieke vingerafdruk.

Citeer dit