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 study develops an effective branch-and-price algorithm for this food bank vehicle routing problem. The pricing subproblem is solved, exactly or heuristically, using a specialized labeling type dynamic programming (DP) algorithm. The computational efficacy of this DP approach stems primarily from the inclusion of preprocessing routines that enhance the label extension scheme by iteratively eliminating dominated (partial) solutions. The proposed exact DP algorithm, and five proposed heuristic variants, significantly reduce the computational time associated with the solution of the pricing subproblem. The resulting speedup enables the implementation of a branch-and-price algorithm that greatly outperforms the use of CPLEX over a test-bed of 60 problem instances.