O projeto final de Análise e Projeto de Algoritmo (APA) propõe que resolvemos algumas instâncias do problema de roteamento de veículo (VRP) e com isso tivemos que implementar pelo menos uma heurística construtiva, três movimentos de vizinhança e um algoritmo de busca local chamado VND.
Para uma descrição mais detalhada do projeto clique aqui.
- Heurística Construtiva
- Vizinho Mais Próximo
- Vizinho Mais Próximo e uma Busca Local para o TSP da instância e depois fizemos a separação dessa rota para se encaixar com o problema do projeto.
- Como foi implementado depois da entrega do projeto, a saída do programa na função Main() apenas terá o algoritmo do vizinho mais próximo como heurística construtiva.
- Movimentos de Vizinhança.
- Intra-Rotas
- 2-OPT
- Swap
- Uma modificação do 2-OPT
- Intra-Rotas
- Algoritmo de busca local
- VND(Variable Neighborhood Descent).
Antes de testar em sua máquina, verifique se os pacotes/linguagens abaixo estão instalados.
Para executar o projeto basta fazer no terminal
# Clonar o repositorio
git clone [email protected]:italonicacio/APA-Projeto-Final.git
# Abra a pasta do projeto
cd APA-Projeto-Final
# Vá para a pastar src
cd src
# Execute o arquivo main.py
python3 main.pyAo executar o programa ele vai chamar a função main() onde apenas fará a execução do programa quando foi feito para a entrega do projeto.
Para testar a execução do programa com as instâncias da copa basta alterar esse trecho do código de
if __name__ == "__main__":
Main()Para.
if __name__ == "__main__":
MainCup()Observação: A heurística construtiva que faz o uso do TSP para gerar uma rota que será separada em outras rotas para o VRP está com um custo de tempo alto.
Para o uso da heurística construtiva é necessário alterar a chamada da função abaixo de
CreateDataForTable(problem, problem.NearestNeighbor)Para.
CreateDataForTable(problem, problem.HeuristicTest)