Effective management of public food distribution networks has assumed significance in maintaining the objectives of food security, and cost-effectiveness particularly in the agrarian economy of demand uncertainty and infrastructural bottlenecks. This paper proposes a multi-echelon linear programming approach, integrated with cluster analysis, to optimize the supply chain of paddy in the Food Corporation of India (FCI) in the Sambalpur area of the state of Odisha. The proposed method considers the process of flowing paddy from the millers to the depots, and from depots to the central pool, taking into consideration the associated handling charges of procurement, transportation, milling, and storage. Employing the official data of the FCI for the year 2024-2025, the problem has been identified to arrive at the optimum network of the proposed approach, resulting in the lowest total cost of the network considering the projected demand. A supporting cluster analysis finds a level of heterogeneity for the depots, enabling the grouping of the depots according to efficiency and thus facilitating specific operational intervention. Sensitivity and relative analysis show the performance to strongly vary with demands and to remain relatively insensitive to supplies and costs, with the optimal solution remaining more-or-less unchanged. The results and implications help to address the concerns for increased operational efficiencies, demands, and planning in the public food chains.