Approximation of a Real-World Vehicle Dispatching Problem

In: International Conference on Operations Research. 2006

Authors

• Sven O. Krumke
• Sleman Saliba
• Tjark Vredeveld
• Stephan Westphal

Abstract

In this paper we investigate a real-world large-scale vehicle dispatching<br>problem with strict real-time requirements, posed by our cooperation partner, the German Automobile Association (ADAC). Service units starting at their current positions are to serve at most a given number of requests without returning to their homepositions. 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 NPcomplete even for k = 2. We also present a polynomial time (2k - 1)-approximation algorithm, here again k denotes the maximal number of requests served by a single service unit. If k equals the total number of requests, we provide a (2 - 1/k)-approximation which works similar to the Double-Tree-Algorithm for the metric TSP. Finally, we extend the approximation algorithm to include linear and quadratic lateness costs, which are of interest with respect to the application at ADAC.

BibTeX

 
@InProceedings{ KrumkeEtAl:ApproximationDispatching, 
   title = { Approximation of a Real-World Vehicle Dispatching Problem }, 
   author = { Sven O. Krumke and Sleman Saliba and Tjark Vredeveld and Stephan Westphal },   
   booktitle = { International Conference on Operations Research },              
   year = 2006, 
} 

---

This publication belongs to the project DeNDeMA.