Algoritmo Branch-and-Bound e Aplicação ao Problema do Caixeiro Viajante

Abstract

O objetivo deste trabalho foi estudar e apresentar o Algoritmo Branch-and-Bound (B&B), que é um algoritmo exato, para buscar soluções em problemas de Programação Linear Inteira Mista (PIM). realizamos testes numéricos utilizando o algoritmo (B&B) no clássico problema do caixeiro viajante. Alguns aspectos justificam o estudo de problemas PIM. Um deles refere-se ao requisito de que muitas vezes esses problemas implicam em maior complexidade computacional. Outro aspecto é que este tipo de problema aparece em situações reais, como, por exemplo, alocação de pessoas, máquinas e veículos.