Método Ótimo e Epsilon-ótimo para Resolução de Problemas de Localização Capacitado
Autores
|
4540 |
3,770
|
|
|
4541 |
3,770
|
Informações:
Publicações do PESC
Será apresentado um método para solucionar o Problema de Localização Capacitado (PLC). O método pode ser utilizado como um método heurístico para problemas operacionais; como um método épsilon-ótimo para problemas de difícil resolução ou com alguma margem de erros no levantamento dos dados; ou ainda como método ótimo. O objetivo é resolver problemas grandes e obter uma solução com qualidade, ou seja, uma solução ótima ou muito próxima dela, em um tempo viável para o problema. Serão examinados testes de redução baseados em técnicas ADD/DROP. Essas técnicas permitem a redução das dimensões do problema. Dois limites inferiores serão utilizados, um baseado em relaxação Lagrangeana e outro na relaxação da restrição de integridade da solução. Serão desenvolvidas heurísticas, como estratégias de ramificação, que utilizam informações do testes de redução e dos limites inferiores. Essas heurísticas permitem que o algoritmo encontre uma solução com qualidade nas primeiras explorações da árvore de busca. A estratégia de busca na árvore é realizada através de uma combinação entre busca em profundidade e busca em largura.
This work presents a method to solve the Capacitated Location Problem. The method can be utilized as a heuristic algorithm for operational problems, as an e-optimal algorithm for difficult problems or as an optimal algorithm. The main objective of the work is to solve big problems and get good solutions, that is, to get optimal or very close solutions of them. Firstly a Transportation method will be development, although it is not the main objective of the work, it is essential for the development of PLC. Transportation problems are utilized in ADD/DROP techniques and to get inferior limits of PLC. Reduction tests will be examined. Those techniques allow the reduction of the problem dimensions. Two lower bounds will be used; one based on Lagrangian relaxation and another in the relaxation of the integer restriction. Heuristics will be developed as ramification strategies. It gets information of reductions tests and limits inferior. Those heuristics allows the algorithm to find a near-optimal solution in the first explorations of the search tree. The exploration strategy, in the search tree, is performed make a merge between depth first search and breath first search.