Approximation algorithms for a vehicle routing problem

Sven Krumke (), Sleman Saliba (), Tjark Vredeveld and Stephan Westphal ()

Mathematical Methods of Operations Research, 2008, vol. 68, issue 2, 333-359

Abstract: In this paper we investigate a vehicle routing problem motivated by a real-world application in cooperation with the German Automobile Association (ADAC). The general task is to assign service requests to service units and to plan tours for the units such as to minimize the overall cost. The characteristics of this large-scale problem due to the data volume involve strict real-time requirements. We show that the problem of finding a feasible dispatch for service units starting at their current position and serving at most k requests is NP-complete for each fixed k ≥ 2. We also present a polynomial time (2k − 1)-approximation algorithm, where again k denotes the maximal number of requests served by a single service unit. For the boundary case when k equals the total number |E| of requests (and thus there are no limitations on the tour length), we provide a $${\left(2-\frac{1}{|E|} \right)}$$ -approximation. Finally, we extend our approximation results to include linear and quadratic lateness costs. Copyright Springer-Verlag 2008

Keywords: Vehicle routing; NP-completeness; Approximation algorithms (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-008-0224-y (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:68:y:2008:i:2:p:333-359

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-008-0224-y

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().