The Vehicle Routing Problem (VRP) has recently piqued the interest of researchers seeking to improve the efficiency and efficacy of the transportation system in distributing commodities. Many scholars have proposed using a heterogeneous fleet in vehicle routing to minimize distribution costs further. When perishable items need to be distributed at numerous demand points during specific time intervals, the situation becomes more difficult. This paper discusses this variant of VRP and the restriction on accepting products with a minimum stated quality level. This research aims to create and optimize a mathematical model that incorporates the quality issue of a perishable commodity into the distribution process. The given product's worth is decreasing as its quality deteriorates. This problem is mathematically represented as a Mixed Integer Non-Linear Programming Problem (MINLP). A Genetic Algorithm-based heuristic is also recommended due to the computational complexity required in applying the model to solve real-world situations.