This paper aims to develop an optimized solution for the Vehicle Routing Problem (VRP), tailored explicitly for Liquid Petroleum Gas (LPG) distribution, with a focus on minimizing transportation costs and enhancing delivery reliability. The critical role of LPG as an essential public infrastructure commodity, widely utilized for cooking and heating, makes its efficient and reliable distribution a significant logistical challenge due to the strict adherence to delivery time windows, heterogeneous fleets, multi-trip scenarios, and intricate loading and unloading requirements. To address these complexities, this study proposes a novel hybrid Particle Swarm Optimization and Genetic Algorithm (HPSOGA) that uniquely integrates multi-trip routing, time windows, and heterogeneous vehicle fleet management into a single optimization framework. The dual-phase optimization strategy leverages the exploratory capability of PSO and the solution-refining power of GA, resulting in high-quality, feasible solutions. Validation against real-world data involving VRP instances with 88 and 40 stations demonstrates the model’s practical impact, achieving reductions of up to 4.56% in transportation costs compared to existing operational routes. This research makes a significant contribution to interdisciplinary domains, including logistics optimization, sustainability, and energy distribution, by offering a robust and scalable model that comprehensively addresses complex, real-world VRP constraints.