Name
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s00186-008-0224-y | Math. Meth. of OR |
Keywords | Field | DocType |
extend our approximation results to include linear and quadratic lateness costs.,publication,vehicle routing problem,polynomial time,np completeness,real time,approximation algorithms,vehicle routing | Discrete mathematics,Approximation algorithm,Mathematical optimization,Vehicle routing problem,Computer science,Quadratic equation,Time complexity | Journal |
Volume | Issue | ISSN |
68 | 2 | 1432-2994 |
Citations | PageRank | References |
2 | 0.40 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sven O. Krumke | 1 | 308 | 36.62 |
| Sleman Saliba | 2 | 5 | 1.47 |
| Tjark Vredeveld | 3 | 230 | 18.76 |
| Stephan Westphal | 4 | 97 | 13.41 |