Logística/Sistemas de distribuição/Escala de veículos/Algoritmos Branch and Bound para CPEV

Origem: Wikilivros, livros abertos por um mundo aberto.

O método 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 assimétrico e restrições quanto à distância do CVRP (DCVRP), estes 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 combinatórias básicas. Tais como, problema de atribuição, shortest spanning tree ou state space relaxation.

Mais recentemente foram propostas abordagens com limites mais sofisticadas, baseadas em relaxações lagrangeanas ou em abordagens aditivas, que aumentou significativamente o tamanho dos problemas que podem ser optimizados com Branch and Bound (Toth et al., 2002c, p. 29).

De acordo com Dorronsoro (2007c) , o método 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 heurísticos.

Recentemente como referido, Fisher introduziu o método K-Tree, que utiliza um processo diferente de Branch and Bound, propondo uma partição por via da fixação da aresta de incidência de subconjuntos seleccionados de clientes agrupados. As limitações laterais são dualizadas para obter uma relaxação lagrangeana, que é o grau mínimo de restrições do problema K-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.

Usando Branch and Bound, inicialmente deve ser analisada toda a amostra de soluções . 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 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 ou tenha um custo igual a ( onde ), então é a nova solução ou é óptima.

Caso contrário, identifica-mos sub-sistemas de , tal que . 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 , substitui-se pela nova solução e continua-se.
  • Em caso de não ser encontrada uma solução para o sub-problema esse é abandonada.
  • 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, somos 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.