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

O método Branch and Cut tem sido extremamente bem sucedido na pesquisa das soluções óptimas para grandes amostras de um problema semelhante, o problema do caixeiro viajante Simétrico (STSP). Contudo a sua aplicação no VRP não é tão extensa como no problema do caixeiro viajante (Toth et al. 2002d, p. 53).

Este método consiste na relaxação linear de programação linear inteira (PLI) é a programação linear (PL) obtida de PLI deixando cair a condição de que todas as variáveis têm de ser inteiras. Assim o valor óptimo $\ z_{PL}$ da relaxação (o caso mínimo) é o limite inferior do valor óptimo $\ z_{PLI}$ de PLI, ou seja, $\ z_{PL}\leq z_{PLI}$.

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. Se a solução óptima $\ x^{*}$ for inteira, terminamos. Caso contrário escolhe-se uma variável $\ x_{e}^{*}$ com valor fraccionário e construindo-se dois novos PL. No primeiro adiciona-se um limite superior a $\ x_{e}$, enquanto no segundo conjunto adiciona-se um limite inferior em $\ x_{e}$ (onde $\ x_{e}$ seja o valor maior inteiro não superior ou inferior a $\ x_{e}$). Daí executa-se Branch and Bound, onde os limites são dados pelos valores das soluções óptimas PL associados aos nós da árvore de procura.

Quando o número de restrições lineares de PLI é grande de mais ou quando a relaxação linear é fortalecida pela adição de desigualdades válidas, então não pode ser utilizado para resolução PL no sistema de restrições. Devendo ser utilizada a técnica cutting plane (Toth et al. 2002d, p. 55).

Branch and cut tem obtido sucesso na resolução de problemas, todavia caso os seus componentes sejam "fracos", pode originar soluções pouco eficazes. São sintoma disso:

• (1) Não ter um bom algoritmo para realizar a fase cutting phase.

• (2) O número de iterações de Cutting phase é elevado.

• (3) O PL torna-se impossível devido ao tamanho.

• (4) A árvore gerada por branching torna-se muito grande para ser resolvida em pouco tempo.

Para (2) não há solução, porém para (1) como referido não é essencial que a solução de PL seja óptima, podendo-se avançar para a fase de branching mesmo que a solução de PL não seja exacta. O problema (3) pode ser evitado, eliminando restrições inactivas. Caso nos deparemos com o problema (4), que é um problema central, pois a maioria dos erros acontece devido a esta situação. A única solução possível é fortalecer a relaxação linear. Ou seja, adicionar desigualdades lineares que sejam satisfeitas por todas as soluções. Estas desigualdades desnecessárias na formulação inteira, forçam o valor da solução da relaxação linear a aproximar-se do valor da solução óptima de PLI (Toth et al. 2002d, p. 57).