Testes de Redução e Algoritmo Branch and Bound para o Problema de Localização Capacitado
Autores
|
1808 |
3,770
|
|
|
1809 |
3,770
|
Informações:
Publicações do PESC
O problema de localização capacitado com custos lineares de transporte e fixos de instalação é considerado. Primeiro serão examinados testes de redução baseados em técnicas ADD/DROP. Uma função D que permite o balanço do aumento/decréscimo dos custos fixos e variáveis devido à abertura/fechamento de uma facilidade é definida. Existe intervalos para D onde uma decisão ótima de abertura ou fechamento de facilidades deve ser tomada. Na maioria dos casos existe um gap em D onde não existe decisão ótima. A dinâmica de abertura/fechamento de facilidades realimenta a redução do gap, fortalecendo o potencial de novas decisotilde;es ótimas. Ocasionalmente o gap fecha, levando assim a uma solução completa. Um exemplo para este caso é apresentado. De qualquer modo esta situação é muito especial para problemas grandes. Um grande número de facilidades indefinidas reduz o impacto da abertura/fechamento de uma determinada facilidade enfraquecendo o potencial dos procedimentos de ADD/DROP. Esta é a principal idéia para embutir as técnicas de ADD/DROP em um algoritmo branch and bound. A abertura ou fechamento de facilidades obtida pela ramificação na árvore reforça o potencial dos procedimentos de ADD/DROP permitindo que novas decisões possam ser tomadas. De outro lado o uso de ADD/DROP diminui a árvore do branch and bound. O limite inferior é obtido utilizando relaxação lagrangeana. Um limite inferior baseado em relaxação lagrangeana poda as ramificações permitindo novas diminuições na árvore. Resultados computacionais são apresentados.
The capacitated plant location problem with linear transpotation and fixed location costs is considered. First we examine reduction tests based on ADD/DROP procedures. A function D allowing the balance of the increase/decrease of fixed and variable costs due to the opening/closing of plants is defined. There are intervals for D where an optimal decision of opening or closing facilities can be made. In most cases however there is a gap of D where no optimal decision exist. The dynamics of opening/closing facilities feed back to the gap reducing it, thus strengthening the potencial for further optimal decisions. Occasionallly the gap closes thus leading to a complete solution. An example for such a case is presented. However this situation is very rare specially for large problems. A great number of unsettled facilities reduces the impact of opening/closing a certain facility i weakening the potential of ADD/DROP procedures. This is the main idea for embedding ADD/DROP techniques in a branch and bound algorithm. The opening or closing of facilities obtained by branching the tree reinforces the potential strength of the ADD/DROP procedures allowing further decisions to be made. On the other hand the use of ADD/DROP slims the branch and bound tree. A lower bound based on lagrangean relaxation prunes the branches allowing further slimming of the tree. Computational results are presented.