|
O método [[w:EN:Branch and bound| Branch and Bound]] tem vindo a ser dos método mais utilizados nas últimas décadas na resolução de CVRP, bem como as suas variantes mais usuais . Em muitos casos, tal como CVRP [[w:Grafo assimétrico|assimétrico]] e restrições quanto à distância do CVRP (DCVRP), estes [[w:Algoritmo|algoritmos]] são mais eficazes comparando com métodos de soluções exactas. Laport e Nobert no seu trabalho com foco em métodos exactos, desenvolveram uma completa análise aos algoritmos Branch and Bound propostos até 1980. Algoritmos esses, que usavam relaxações [[w:Combinatória|combinatórias]] básicas. Tais como, [[w:EN:Assignment problem|problema de atribuição]], [[w:EN:Minimum spanning tree|''shortest spanning tree'']] ou ''state space relaxation''.
:O método [[w:Branch and bound| Branch and Bound]] abordado por [[Logística/Referências#refbPEVD|Sandia national laboratories]] (1997) e [[Logística/Referências#refbPEVE|Dorronsoro]] (2007) é uma técnica [[w:Algoritmo|algoritmica]], que permite encontrar uma solução óptima de problemas de [[w:Otimização combinatória|optimização]], tem vindo a ser utilizado nos últimos anos na resolução de CPEV simétrico e assimétrico (ACPEV). Mantendo a melhor solução encontrada até até então, ou seja, se a nova solução encontrada for pior que a anterior é abandonada. Por exemplo Imaginando que se pretende fazer uma viagem Lisboa-Porto, em que pela A1 o percurso seriam cerca de 300Km. A próxima solução a procurar terá de ser inferior, caso contrário é abandonada; pois o objectivo é minimizar a distância.
Mais recentemente foram propostas abordagens com limites mais sofisticadas, baseadas em [[w:EN:Lagrangian relaxation|relaxações lagrangeanas]] ou em abordagens aditivas, que aumentou significativamente o tamanho dos problemas que podem ser optimizados com Branch and Bound ([[Logística/Referências#refbPEVD|Toth et al., 2002c, p. 29]]).
*'''Pode também ter aplicação noutras áreas como:'''
** [[w:Problema da mochila| Problema da mochila]],
** [[w:Programação linear| Programação linear]],
** Programação não-linear,
** [[w:Problema do caixeiro viajante| Problema do caixeiro viajante]],
** Problema de atribuição quadrático,
** [[w:Problema de satisfatibilidade booleana| Problema de satisfatibilidade máxima]],
** [[w:Algoritmo do vizinho mais próximo| Busca do vizinho mais próximo]],
** Problema do corte de stock,
De acordo com [[Logística/Referências#refbPEVB|Dorronsoro (2007b)]] , o método [[w:EN:K-tree|''K-tree'']] proposto por Fisher um dos mais utilizados, no que se refere a aproximação exacta (na resolução especifica de CPEV). Conseguiu resolver um problema com 71 clientes, contudo existem problemas com amostras menores, que ainda não têm solução, devido a algumas restrições inerentes. Todavia para amostras com maior dimensão, mais complexas ou até para encontrar uma solução mais rapidamente, devem ser utilizados métodos [[w:Heurística (computação)| heurísticos]].
*'''Respectivamente em Inglês:'''
**[[w:Knapsack problem|<i>Knapsack problem</i>]]
**[[w:Linear programming| <i>Integer programming</i>]]
**[[w:Nonlinear programming| <i>Nonlinear programming</i>]]
**[[w:Travelling salesman problem| <i>Traveling salesman problem</i>]] (TSP)
**[[w:Quadratic assignment problem| <i>Quadratic assignment problem</i>]] (QAP)
**[[w:Maximum satisfiability problem| <i>Maximum satisfiability problem</i>]] (MAX-SAT)
**[[w:Nearest neighbor search| <i>Nearest neighbor search</i>]] (NNS)
**[[w:Cutting stock problem| <i>Cutting stock problem</i>]]
:Recentemente como referido, Fisher introduziu o método <i>''K-Tree </i>'', que utiliza um processo diferente de [[w:Branch and Bound ]]., Propondopropondo uma partição , por via da fixação da bordaaresta de incidência de subconjuntos seleccionados de clientes agrupados. As limitações laterais são dualizadas para obter uma [[w:Otimização combinatória| relaxação lagrangeana ]] ([[w:Lagrangian relaxation| <i>Lagrangian relaxation</i>]] em Inglês), que é ao limitaçãograu mínimamínimo de restrições do problema <i>''K- Tree</i> ([[Logística/Referências#refbPEVB|Toth et al. , 2002]])tree''. ▼
A abordagem ''K-Tree'', pode ser estendida para conter variações realísticas, tais como custos assimétricos, janela de tempo ou frotas não uniformes.
:Todavia para amostras com maior dimensão, mais complexas ou até para encontrar uma solução mais rapidamente ([[Logística/Referências#refbPEVE|Dorronsoro]] (2007) refere, a utilização de outros métodos mais eficazes como por exemplo [[w:Heurística (computação)| heurísticos]]. Pois o problema cria árvores muito extensas, o que não torna fácil a sua resolução.
:Usando Branch and Bound, inicialmente deve ser analisada toda a amostra de soluções <math>\ S</math>. De seguida efectua-se a relaxação do problema, no processamento ou na fase de limitação. Com esta acção estamos a admitir soluções que não se encontram, no espaço <math>\ S</math> de soluções possíveis. A solução dessa relaxação produz um limite inferior ao valor de uma solução óptima. Se a solução de relaxação pertencer a <math>\ S </math> ou tenha um custo igual a <math>\ \hat s </math> ( onde <math>\ \hat s \in S </math> ), então é a nova solução ou <math>\ \hat s </math> é óptima. ▼:Abordado inicialmente por A. H. Land e A. G. Doig em 1960, pioneiros nesta temática no artigo <i>"An automatic method of solving discrete programs problems"</i>] no jornal <i>Econometrica</i>, onde apresentaram um algoritmo numérico simples para programação discreta (que continha variáveis discretas, bem como contínuas). Todavia num trabalho em paralelo Murty, Karel e Little (1962), focavam-se num tipo específico de programação discreta.([[Logística/Referências#refbPEVF|Brusco, 2005 , p.4 a 6]])
:Por forma, o método <i>K-Tree</i> proposto por Fisher um dos mais utilizados, no que se refere a aproximação exacta (na resolução especifica de CPEV).
:Conseguiu resolver um problema com 71 clientes; contudo existem problemas com amostras menores, que ainda não têm solução, devido a algumas restrições inerentes ([[Logística/Referências#refbPEVE|Dorronsoro, 2007]]).
:Caso contrário de acordo com [[Logística/Referências#refbPEVE|Dorronsoro (2007)]] , identifica-mos <math>\ n</math> sub-sistemas de <math>\ S ( S_{1} ,..., S_{n} ) </math>, tal que <math>\ U_{i=1}^n S_{i}=S</math>. Estes sub-sistemas são denominados, sub-problemas que ao serem processados, dão origem a quatro resultados possíveis. ▼▲:Recentemente como referido, Fisher introduziu o método <i>K-Tree</i>, que utiliza um processo diferente de [[w:Branch and Bound]]. Propondo uma partição, por via da fixação da borda de incidência de subconjuntos seleccionados de clientes agrupados. As limitações laterais são dualizadas para obter uma [[w:Otimização combinatória| relaxação lagrangeana]] ([[w:Lagrangian relaxation| <i>Lagrangian relaxation</i>]] em Inglês), que é a limitação mínima do problema <i>K-Tree</i> ([[Logística/Referências#refbPEVB|Toth et al. , 2002]]).
:Assim Fisher refere que inicialmente deve ser analisada toda a amostra de soluções <math>\ S</math>. De seguida efectua-se à relaxação do problema, no processamento ou na fase de limitação. Com esta acção estamos a admitir soluções que não se encontram, no espaço de soluções possíveis.
▲:A solução dessa relaxação produz um limite inferior ao valor de uma solução óptima. Se a solução de relaxação pertencer a <math>\ S</math> ou tenha um custo igual <math>\ \hat s </math> (onde <math>\ \hat s \in S </math>), então a nova solução ou <math>\ \hat s </math> é óptima.
▲:Caso contrário de acordo com [[Logística/Referências#refbPEVE|Dorronsoro (2007)]] , identifica-mos <math>\ n</math> sub-sistemas de <math>\ S ( S_{1} ,..., S_{n} ) </math>, tal que <math>\ U_{i=1}^n S_{i}=S</math>. Estes sub-sistemas são denominados, sub-problemas que ao serem processados, dão origem a quatro resultados possíveis.
*Se for encontrada uma solução melhor que <math>\ \hat s </math>, substitui-se pela nova solução e continua-se.
*Por outro lado compara-se o limite inferior do sub-problema, com o limite global superior, dado pelo melhor valor encontrado até então. Se for maior ou igual que o actual é abandonado.
*Por final se não for possível abandonar o sub-problema, somo forçados a processar e adicionar o sub-problema à lista de candidatos activos. Segue-se este ciclo até não existirem mais candidatos a sub-problemas, nesse ponto a nossa melhor solução é óptima.
{{AutoCat}}
| 