Este documento examina un problema de enrutamiento de barcos con recogida y entrega y ventanas de tiempo para el transporte marítimo de petróleo, motivado por las actividades de producción y logística de una empresa petrolera que opera en la costa brasileña. Los costos de transporte desde plataformas en alta mar hasta terminales costeras son un tema importante en la búsqueda de la excelencia operativa en la industria del petróleo, involucrando operaciones que demandan sistemas de soporte de decisiones ágiles y efectivos. Este documento presenta un enfoque de optimización para abordar este problema, basado en un modelo de programación entera mixta (MIP) y una aplicación novedosa y exploratoria de dos heurísticas MIP a medida, basadas en procedimientos de relajación y fijación y descomposición temporal. El modelo minimiza los costos de combustible de una flota heterogénea de petroleros y los costos relacionados con contratos de flete. El modelo también considera restricciones específicas de la empresa para el transporte de petróleo en alta mar. Se presentan experimentos computacionales basados en los modelos matemáticos y las heurísticas MIP relacionadas para un conjunto de datos reales proporcionados por la empresa, que confirman el potencial de los métodos basados en optimización para encontrar buenas soluciones para problemas de tamaños moderados.