El problema de ruteo vehicular combinado con el manejo de inventario es un tema complejo reconocido en su tratamiento por la literatura científica. En este trabajo se presenta un problema de este tipo con la particularidad que tiene como objetivo la optimización del indicador tráfico de carga, así como un modelo y procedimiento matemático para la resolución de este problema en una entidad comercializadora de combustibles de la región oriental de Cuba. Para ello se utilizaron métodos heurísticos combinados, de descomposición y reducción, integrados con programación lineal binaria, para la determinación del ruteo vehicular hacia los clientes. Todo ello para simplificar el problema y ofrecer una solución satisfactoria basada en el cumplimiento de niveles de inventarios de acuerdo a un nivel de cobertura planificado y el uso racional de los vehículos. Finalmente, se probó en un caso de estudio basado en una situación real operativa de la empresa en cuestión.