Short food supply chains (SFSCs), defined as involving direct sales or a single intermediary, have been studied from logistical and sustainability perspectives. This study proposes a mixed-integer linear programming (MILP) formulation for the SFSC problem and develops three metaheuristic algorithms—genetic algorithm, simulated annealing, and a hybrid approach—to efficiently solve large-scale instances. A novel chromosome encoding ensures feasibility, and the linear programming problems aid fitness evaluation. Computational experiments on datasets of varying sizes demonstrate the effectiveness of the proposed methods compared to the CPLEX solver, particularly in large-scale settings.