This paper characterizes the routing problems arising in distribution of rice-for-the-poor in a district and presents a generic mathematical formulation of vehicle routing problems (VRP) for solving the problems. The proposed generic model, framed as a mixed integer linear programming, is formulated in such a way to encompass three distinct features; namely multiple depots (MD) establishment, multiple trips (MT) transportation, and split delivery (SD) mechanism. This model is implemented for a real-world problem of rice-for-the-poor distribution in the Ponorogo district of Indonesia, involved for deliveries among 3 depots—8, 17, and 23 villages depended on the distribution period—using a fleet of 5 vehicles of homogeneous capacity. Three types of distribution model are identified as MD-MT-VRP, MD-VRP-SD and MD-MT-VRP-SD.