Logística/Sistemas de distribuição/Escala de veículos/Algoritmos Branch and Bound para CPEV: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Criou nova página com '=====[http://en.wikipedia.org/wiki/Branch_and_bound <i>Branch and Bound</i>]===== :O método [http://en.wikipedia.org/wiki/Branch_and_bound <i>Branch and Bound</i>] é uma ...' |
Sem resumo de edição |
||
Linha 1:
:O método [http://en.wikipedia.org/wiki/Branch_and_bound <i>Branch and Bound</i>] é 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.
Linha 17:
:Todavia para amostras com maior dimensão, mais complexas ou até para encontrar uma solução mais rapidamente, utilizam-se outros métodos mais eficazes como por exemplo [http://pt.wikipedia.org/wiki/Heur%C3%ADstica_%28computa%C3%A7%C3%A3o%29 heurísticos]. Pois o problema cria árvores muito extensas, o que não torna fácil a sua resolução. ([[Logística/Referências#refbPEVA|AUREN, 2007]])
==
:Abordado inicialmente por <i>A. H. Land</i> e <i>A. G. Doig</i> em 1960, pioneiros nesta temática no artigo [http://www.jstor.org/pss/1910129 <i>"An automatic method of solving discrete programs problems"</i>] no jornal <i>Econometrica</i>, onde apresentaram um algoritmo númerico simples para programação discreta (que continha variáveis discretas, bem como contínuas). Todavia num trabalho em paralelo <i>Murty, Karel e Little</i> (1962), focavam-se num tipo específico de programação discreta.([[Logística/Referências#refbPEVF|BRUSCO, 2005 , p.4 a 6]])
Linha 23:
: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#refbPEVA|AUREN, 2007]])
==
:Recentemente como referido, <i>Fisher</i> introduziu o método [http://www.jstor.org/pss/171617?cookieSet=1 <i>K-Tree</i>], que utiliza um processo diferente de [http://en.wikipedia.org/wiki/Branch_and_bound <i>Branch and Bound</i>]. 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 [http://pt.wikipedia.org/wiki/Otimiza%C3%A7%C3%A3o_combinat%C3%B3ria relaxação lagrangeana ] ([http://en.wikipedia.org/wiki/Lagrangian_relaxation <i>Lagrangian relaxation</i> ] em Inglês), que é a limitação minima do problema [http://www.jstor.org/pss/171617?cookieSet=1 <i>K-Tree</i>]. ([[Logística/Referências#refbPEVB|TOTH e VIGO, 2001]])
Linha 39:
([[Logística/Referências#refbPEVA|AUREN, 2007]])
{{AutoCat}}
| |||