Algoritmos para o problema de localizaÃÃo simples baseados nas formulaÃÃes clÃssica e canÃnica / Algorithms to the problem of location based on simple formulations classical and canonical
AUTOR(ES)
FÃbio Carlos Sousa Dias
DATA DE PUBLICAÇÃO
2008
RESUMO
Neste trabalho, estudamos o problema de localizaÃÃo simples (SPLP - Simple Plant Location Problem). Usando a formulaÃÃo matemÃtica clÃssica e uma outra formulaÃÃo proposta recentemente, desenvolvemos vÃrios algoritmos para encontrar limites inferiores e superiores, bem como algoritmos tipo branch-and-bound. Com a formulaÃÃo clÃssica, tais limites sÃo obtidos utilizando o mÃtodo de correÃÃo de dados e critÃrios de dominÃncia entre os custos xos e de transporte. Propomos uma projeÃÃo dessa formulaÃÃo, que se mostrou computacionalmente atrativa. Usando a nova formulaÃÃo propomos e mostramos a corretude de vÃrios procedimentos iterativos que procuram encontrar uma soluÃÃo para o problema, resolvendo uma seqÃÃncia de subproblemas paramÃtricos obtidos com a remoÃÃo de variÃveis e restriÃÃes da formulaÃÃo original. Em cada iteraÃÃo desse processo, podemos gerar limites inferiores e superiores. Aplicamos ainda relaxaÃÃo lagrangeana a essa nova formulaÃÃo para obter outros limites. Analisamos vÃrias possibilidades de relaxaÃÃo das restriÃÃes. Desenvolmento tambÃm algoritmos branch-and-bound baseados em ambas as formulaÃÃes e nos limites obtidos. Avaliamos a e ciÃncia computacional de todos os algoritmos com instÃncias de teste difÃceis, disponÃveis na literatura. Resultados computacionais e comparaÃÃes com outros algoritmos da literatura sÃo reportados.
ASSUNTO(S)
relaxaÃÃo lagrangeana facility location problems problemas de localizaÃÃo de facilidades lagrangean relaxation ciencia da computacao reduÃÃo do tamanho do problema problem reduction
ACESSO AO ARTIGO
http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=2827Documentos Relacionados
- AplicaÃÃo de algoritmos de cobertura ao problema de localizaÃÃo de esquadrÃes de aeronaves de interceptaÃÃo na RegiÃo AmazÃnica.
- AvaliaÃÃo de algoritmos para localizaÃÃo de faltas eletrÃcas
- LocalizaÃÃo de campos em membranas deformadas.
- LocalizaÃÃo baseada em mÃtodo de Monte Carlo e algoritmos genÃticos para robÃtica mÃvel.
- WBG (Whois Based Geolocation): uma estratÃgia para localizaÃÃo geogrÃfica de hosts na Internet