A multi-start optimization-based heuristic for a food bank distribution problem

We investigate a variant of the vehicle routing-allocation problem that arises in the distribution of pallets of goods by a food bank to a network of relatively distant nonprofit organizations. Vehicles are routed to selected intermediate delivery sites to which the nonprofit organizations travel to collect their demand. The logistical cost is shared, and the objective is to minimize a weighted average of the food bank vehicle routing cost and the travel cost of the nonprofit organizations. This paper develops an efficient multi-start heuristic that iteratively constructs the initial solutions to this problem and subsequently explores their neighborhoods via local improvement and perturbation schemes. In our experience, the proposed heuristic substantially outperforms alternative optimization-based heuristics in the literature in terms of the solution quality and computational efficiency and yields solutions with an optimality gap often below 0.5%.