A Segment-Based Formulation and a Matheuristic for the Humanitarian Pickup and Distribution Problem

We present a novel formulation and a matheuristic for a rich humanitarian logistic problem that is motivated by the daily operation of food banks. The problem consists of collecting food donations from suppliers in the food industry and delivering them to food relief agencies that serve individuals in need. This setting requires simultaneous vehicle routing and resource allocation decisions, with the aim of balancing two possibly colliding goals: maximizing the total amount distributed and achieving equity in the allocation. The proposed formulation is based on certain properties satisfied by the optimal solution to the problem and is used within a framework of a broader solution method, which is shown to provide better performance than previously suggested methods. We demonstrate how the new approach can also be extended to the multivehicle counterpart, both with and without time windows.