The split delivery vehicle scheduling problem with time windows and grid network distances

We consider an extension of the Split Delivery Vehicle Routing Problem, whereby customers may have a time window for their delivery. A construction heuristic is developed which uses a look-ahead approach to solve the Split Delivery Vehicle Scheduling Problem with Time Windows. Two improvement heuristics are also described: one attempts to move customers between routes, while the other exchanges customers between routes. All three heuristics are implemented on a specifically developed data set and on some standard problems from the literature. Our heuristic implementations also consider the possibility of multiple time windows, grid network distances, non-linear delivery time functions and bounds on the size of any split deliveries.