Approximation algorithms for a vehicle routing problem |
| |
Authors: | Sven O. Krumke Sleman Saliba Tjark Vredeveld Stephan Westphal |
| |
Affiliation: | (1) University of Kaiserslautern, Paul-Ehrlich-Str. 14, 67653 Kaiserslautern, Germany;(2) Faculty of Economics and Business Administration, Department of Quantitative Economics, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands |
| |
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 -approximation. Finally, we extend our approximation results to include linear and quadratic lateness costs. |
| |
Keywords: | Vehicle routing NP-completeness Approximation algorithms |
本文献已被 SpringerLink 等数据库收录! |
|