Abordamos un problema de enrutamiento de inventario que surge en una empresa productora de oxígeno líquido. Se deben tomar decisiones para el transporte eficiente del producto desde las fuentes hasta los destinos mediante una flota heterogénea de camiones. Este problema combinatorio se ha planteado como una minimización restringida, cuya función objetivo es el cociente del costo operativo dividido por la cantidad total de producto entregado. El costo operativo proviene de las distancias recorridas, el salario de los conductores y el alojamiento nocturno de los conductores. Las restricciones incluyen ventanas de tiempo para los conductores y destinos, niveles de seguridad de inventario, límites inferiores para la cantidad de producto entregado a los destinos y tiempos máximos de conducción. Para aproximar la solución óptima de este desafiante problema, desarrollamos un algoritmo heurístico que primero encuentra una solución factible y luego la mejora de forma iterativa combinando el criterio de Metropolis con la búsqueda local. Nuestros resultados son competitivos con las mejores propuestas en la literatura.