TY - JOUR

T1 - On the approximability of two capacitated vehicle routing problems

AU - Bock, Adrian

AU - Sanità, Laura

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Orienteering

KW - Vehicle routing

UR - http://www.scopus.com/inward/record.url?scp=84879722635&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2013.05.133

DO - 10.1016/j.endm.2013.05.133

M3 - Article

AN - SCOPUS:84879722635

VL - 41

SP - 519

EP - 526

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -