Online-Optimization of Large-Scale Vehicle Dispatching Problems

Abstract In this talk we investigate a real-world large scale vehicle routing problem posed by our cooperation partner, the German Automobile Association (ADAC). Service vunits are requested to assist people whose cars break down. Such service requests arrive online. The goal is to route the requests to service vehicles such that low operational costs and good quality of service is provided (soft time windows). Currently, a column generation approach is used to solve the offline problem, in which only known requests are considered. In order to speed up the column generation, we need to start with “good” short routes. We will show that that this problem is NP-hard even for two requests per service unit. Moreover, we present an approximation algorithm with a constant-factor approximation rate even with nonlinear lateness costs for violating the soft time windows.