The bounded split delivery vehicle routing problem with grid network distances

The authors consider a relaxation of the generic vehicle routing problem, whereby the delivery to a customer can be split between more than one vehicle. The possibility of attaching restrictions on the size of, and number of splits in, any split delivery is investigated. A construction heuristic, which makes use of certain structural features of the problem, is developed. Heuristics which assign specific splitting costs for each customer are also given, and the results of a computational study reported. For all the present heuristic implementations the authors use grid network distances, which resemble a realistic road map layout.