A matheuristic for sustainable logistics for food banks

Sustainable food system is important in many regards including minimizing food waste, decreasing carbon emission and efficient use of natural resources. Food banking operations are significant in achieving a sustainable food system. Motivation of this thesis is derived from three of the Sustainable Development Goals of United Nations, namely "Zero Hunger", "Responsible Consumption and Production" and "Climate Action". In this regard, providing a decision framework that entails approaches to solve routing and allocation problems in food banking operations is aimed by this study. The novel problem of Multi Depot-Periodic Unpaired Pickup and Delivery Vehicle Routing Problem (MD-PUPDVRP) is introduced to mimic day to day supply chain operations of a major player in food banking industry. Involvement of various objectives, including minimizing carbon emissions, fuel costs and unfairness in food distribution, maximizing total amount of rescued food requires dedicated functions to quantify them. For that purpose, a dedicated function for fairness is presented and an adaptation of a carbon emission function is made to transporter type vehicles using empirical data. As solution methodologies, a Mixed Integer Linear Programming (MILP) model is developed. In MILP model, binary variables are used to represent routing scheme, whereas linear variables are utilized to model allocation. A Variable Neighborhood Search (VNS) based matheuristic is implemented to compete with MILP model. In the matheuristic, an exact method called Allocation Subroutine (AS) is used to take advantage of decomposable structure of the problem. To generate upper bounds in a very short amount of time, another exact method called Allocation Upper Bound model (ALUB) is developed. Instances from real life scenarios are created for experimentation along with a set of synthetic instances. It has been observed that the matheuristic performs better than the MILP model for large instances where the number of nodes and number of vehicles are both high. Yet in small scale instances, mathematical model generates near optimal solutions. ALUB provides very close dual bounds to best bounds found by MILP, which enables practical interpretations as well as potential future approaches that utilize dual bound.