Equipamentos de mina operam em extensas regiões geográficas em complexos mineradores de grande porte. Por conta da limitação de locomoção de alguns destes equipamentos, como escavadeiras e perfuratrizes, é necessário realizar o abastecimento de combustível, de lubrificação e de água nos seus locais de operação. Este abastecimento é realizado por meio de caminhões tanque com infraestrutura de abastecimento, chamados comboios. Devido à natureza combinatória do problema, sabe-se que não é possível gerar uma boa rota de maneira manual para instâncias reais. Para resolver este problema pretende-se explorar métodos exatos e heurísticos. Os métodos propostos serão validados utilizando dados reais das minas. Após a validação, pretende-se transformar os métodos desenvolvidos em sistemas de suporte à decisão para apoiar no planejamento dos comboios.