Em situações concretas de entrega de gêneros alimentícios a hospitais, mercados e restaurantes, o gestor de transportes se depara com clientes que não restringem o horário das entregas, outros que exigem a entrega em determinado intervalo de tempo, e outros que limitam a entrega a horários fora de seus picos de demanda. Aparentemente ausente na literatura, as janelas de tempo negativas são apresentadas e discutidas, os ajustes necessários à sua inserção na formulação matemática do problema de roteamento são realizados; e uma solução heurística, utilizando algoritmo genético, é proposta. Testes comparativos com os resultados praticados por uma empresa mostraram a eficiência e aplicabilidade do modelo proposto.