Muitas cidades têm sérios problemas de congestionamento relacionados às suas redes de tráfego. Existem diversos trabalhos de otimização discreta que lidam com várias famílias de problemas de otimização de tráfego rodoviário. Os Problemas de Projeto de Rede (NDP) são problemas de otimização para auxiliar a tomada de decisão no planejamento de redes de tráfego considerando diversos fatores. Propomos um novo algoritmo genético para o problema de projeto de redes rodoviárias. Nosso método heurístico tenta encontrar soluções adicionando e removendo pistas ou estradas, considerando um orçamento dado em quilômetros como restrição. Os experimentos são realizados com redes rodoviárias reais obtidas através do OpenStreetMap, e sugerem o melhor conjunto de parâmetros para o algoritmo genético proposto.