The not-for-profit food rescue organizations play a vital role in alleviating hunger in many developing and developed countries. They rescue surplus food from the business sector and re-distribute to welfare agencies supporting different forms of food relief. In practice, the food rescue and delivery problem is dynamic, and changes when the operation of routes is in progress. The supply of food providers is uncertain until observed upon the driver's arrival. Moreover, new pickup requests arrive randomly over time and there is no deterministic nor probabilistic information on their location and supply until they arrive. In such instances, routes must be reconfigured dynamically while executing the current plan. Furthermore, the routing model must consider, the perishability of products, level of fairness in the distribution, etc., in addition to the operational cost, which are highly relevant to the operational policies of food relief logistics. In this study, we define and model an integrated allocation-routing problem that fairly allocates the uncertain surplus food among the welfare agencies with minimum wastage accounting for the perishability of products, and designs effective vehicle routes. We propose and implement a Tabu Search heuristic solution algorithm for this food relief logistics problem. The performance of the proposed approach is first evaluated in static conditions and then the other assumptions and developments are added gradually and the changes are examined. We design and evaluate various test scenarios which comprise different occurrences of the dynamic events to illustrate the efficiency and effectiveness of the proposed approach.