Logística/Sistemas de distribuição/Escala de veículos/Algoritmos Branch and Cut para CPEV: diferenças entre revisões

 

Método de [[w:Otimização combinatória|optimização combinatória]] de resolução de problemas de [[w:Programação inteira|programação linear inteira]], utilizado na resolução do [[w:Problema do caixeiro viajante| problema do caixeiro viajante simétrico]] (PCV), com grande sucesso na obtenção de soluções óptimas com grandes amostras. Contudo não se compara o estudo efectuado nessa temática com o efectuado em CPEV.

 

A denominação [[w:EN:Branch and cut|<i>branch and cut</i>]] foi dada por Padberg e Rinaldi autores que muito contribuíram no desenvolvimento deste [[w:Algoritmo|algoritmo]], já o primeiro código computacional conhecido que conjuga eficazmente [[w:EN:Cutting-plane method|<i>cutting-plane</i>]] e <i>branch and bound</i>, foi elaborado em 1972 por Hong no trabalho <i>"FindCuts"</i>.

Por outro lado, o primeiro grande sucesso computacional na aplicação em PCV, foi dada a conhecer por Padberg e Rinaldi em 1987. Padberg e Rinaldi introduziram novas ideias, como uma rotina de "encolhimento" para acelerar a procura por sub-caminhos desiguais e novas [[w:Heurística (computação)|heurísticas]] para encontrar combinações de desigualdades, bem como desigualdades <i>"click-tree"</i>. Este investigadores deram um grande contributo na evolução do [[w:Algoritmo|algoritmo]], assim como referido em cima outros o fizeram ao longo dos anos ([[Logística/Referências#refbPEVG| Applegate, 2006, p.117 a 124]]).

 

 

Caso o número de restrições de PLI seja pequeno, tal que a relaxação linear possa ser resolvido por PL, deve-se aplicar ''Branch and Bound'' com os limites de PL. Resolvendo primeiro a relaxação linear.