Olá, Simone.
A escolha de se usar o BRKGA  se deve a dois motivos, um deles é que esta metodologia ainda não havia sido utilizada para solução deste problema. O outro é  aproveitar o decodificador para criação de soluções com alta diversidade, explorando melhor o espaço de busca. Na representação que utilizamos cada cliente de uma instância recebe uma chave aleatória entre 0 e 1.  Quando a soluções passam pelo decodificador  as chaves são ordenadas, e os clientes que receberam as menores chaves são visitados primeiramente. 
Temos algumas ideias para melhorar o desempenho em tempo e obter melhores resultados, uma delas é a modificar a forma que o VND é aplicado, a metodologia utilizada neste trabalho utilizou de forma abusiva deste recurso o aplicando em todas gerações em todas soluções resultantes do cruzamento. Então estudar uma maneira condicionada de aplicar o VND de acordo com a necessidade de obter melhoria no decorrer das gerações reduzirá consideravelmente o custo computacional. Outra ideia é a implementação do decodificador no framework do BRKGA proposto por Resende afim de avaliar o desempenho utilizando as estratégias já implementadas. 
Para terminar nós temos todos os resultados ótimos e se tiver interesse estão disponíveis no site da OR-Library. 
Agradeço atenção !