Neste trabalho, propõe-se uma metodologia de modelagem para problemas de roteirização de veículos baseada no Problema do Caixeiro Viajante. Mais especificadamente, busca-se tornar o Problema do Caixeiro Viajante com Coletas de Prêmios mais coerente com a realidade do contexto logístico, levando em conta a capacidade operacional da organização e restrições mercadológicas. Para tal, são introduzidos novos elementos como a confiabilidade do caixeiro e restrições de tempo para realizar o roteiro. O modelo consiste, então, em maximizar o lucro obtido através da coleta de prêmios e do custo associado ao roteiro, sujeito a restrições de tempo máximo e confiabilidade mínima aceita ao final do percurso. Esta nova abordagem é modelada e resolvida via Algoritmos Genéticos e é ilustrada através de um estudo de caso