On the Slot Optimization Problem in On-Line Vehicle Routing

We formally define the SOP and propose an adaptive neighbourhood search heuristic for determining feasible slots for inserting a new customer orders based on a given delivery schedule in real time. Our approach is tailored to the SOP and combines local search techniques with strategies to overcome local minima. In an experimental evaluation, we demonstrate the efficiency of our approach on a variety of benchmark sets.