1. Identity statement | |
Reference Type | Thesis or Dissertation (Thesis) |
Site | mtc-m16c.sid.inpe.br |
Holder Code | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
Identifier | 8JMKD3MGP8W/34PGRBS |
Repository | sid.inpe.br/mtc-m18@80/2009/02.16.17.46 |
Last Update | 2019:06.11.17.56.45 (UTC) sergio |
Metadata Repository | sid.inpe.br/mtc-m18@80/2009/02.16.17.46.06 |
Metadata Last Update | 2020:04.28.17.48.23 (UTC) administrator |
Secondary Key | INPE-15744-TDI/1489 |
Citation Key | Almeida:2009:MéHePr |
Title | Métodos heurísticos para o problema de localização de concentradores |
Alternate Title | Heuristic methods for the location problem |
Course | CAP-SPG-INPE-MCT-BR |
Year | 2009 |
Date | 2009-02-27 |
Access Date | 2024, May 18 |
Thesis Type | Dissertação (Mestrado em Computação Aplicada) |
Secondary Type | TDI |
Number of Pages | 112 |
Number of Files | 1 |
Size | 671 KiB |
|
2. Context | |
Author | Almeida, Wesley Gomes de |
Group | CAP-SPG-INPE-MCT-BR |
Committee | Yanasse, Horacio Hideki (presidente) Senne, Edson Luiz França (orientador) Pereira, Marcos Antonio Goldbarg, Marco Cesar |
e-Mail Address | wesgomes2005@gmail.com |
University | Instituto Nacional de Pesquisas Espaciais (INPE) |
City | São José dos Campos |
History (UTC) | 2009-02-16 17:46:06 :: wesgomes2005@gmail.com -> yolanda :: 2009-02-26 19:49:43 :: yolanda -> supervisor :: 2009-05-21 16:46:37 :: supervisor -> yolanda :: 2009-05-21 17:16:43 :: yolanda -> wesgomes2005@gmail.com :: 2009-05-21 21:54:35 :: wesgomes2005@gmail.com -> yolanda :: 2009-06-18 13:27:28 :: yolanda -> administrator :: 2009-07-07 16:14:11 :: administrator -> jefferson :: 2009-07-08 15:16:50 :: jefferson -> camila :: 2009-09-17 15:26:19 :: camila -> viveca@sid.inpe.br :: 2009-09-23 18:28:55 :: viveca@sid.inpe.br -> administrator :: 2018-12-10 16:08:20 :: administrator -> sergio :: 2009 2019-06-11 17:56:46 :: sergio -> administrator :: 2009 2020-04-28 17:48:23 :: administrator -> simone :: 2009 |
|
3. Content and structure | |
Is the master or a copy? | is the master |
Content Stage | completed |
Transferable | 1 |
Keywords | problema de localização de concentradores metaheurística algoritmo genético lista tabu recozimento simulado busca por agrupamentos hub location problem metauristic genetic algorithm tabu list simulated annealing clustering search |
Abstract | O problema de localização de concentradores (hubs) é comumente encontrado em redes de transporte e de telecomunicação. Trata-se de problema de Otimização Combinatória NP-difícil e que ocorre em diversas situações práticas, tais como: no transporte aéreo, nos serviços de entregas postais, nos serviços de atendimento de emergência, no abastecimento de supermercados e de redes de lojas, na localização de antenas de comunicação, dentre muitas outras. A decisão sobre a localização de concentradores e quais os nós da rede serão alocados a cada um destes, depende do número de concentradores necessários, da demanda de cada um dos nós, da capacidade de atendimento dos concentradores, dentre outros fatores. Metaheurísticas têm sido usadas com sucesso para obter soluções em diversos problemas de Otimização Combinatória. No entanto, a construção de algoritmos heurísticos eficientes requer bons mecanismos de intensificação de busca. Neste trabalho estuda-se o problema de localização de concentradores e propõem-se métodos heurísticos que utilizam a busca por agrupamentos, uma técnica de intensificação de busca capaz de identificar as regiões do espaço de busca mais promissoras para a obtenção de boas soluções. São propostos um algoritmo genético (AG) e um algoritmo simulated annealing com lista tabu (SATL). Testes computacionais foram realizados com os algoritmos propostos e com estes algoritmos combinados com a busca por agrupamentos (clustering search). Os testes demonstram que a aplicação da busca por agrupamentos a estes algoritmos permite obter soluções de melhor qualidade e em menor tempo computacional, em relação às soluções obtidas pelos algoritmos AG e SATL isoladamente. ABSTRACT: The hub location problem is commonly found in transport networks and in telecommunications networks. It is a NP-hard Combinatorial Optimization problem that occurs in many practical situations, such as air transport, services of postal deliveries, emergency care services, supplying networks of supermarkets and shops, location of antennas for communication, among many others. The decision about the hubs location and for which hub the other network nodes should be allocated depends of the number of hubs needed, the demand of each node, the service capacity of the hubs, among other factors. Metaheuristcs have been used successfully to obtain solutions to various Combinatorial Optimization problems. However, the construction of efficient heuristics requires good search intensification mechanisms. In this work the hub location problem is studied and heuristic methods are proposed. The proposed methods use the clustering to identify the regions of the search space which are more promising for obtaining good solutions. Two algorithms are proposed: a genetic algorithm (AG) and a simulated annealing with tabu list algorithm (SATL). Computational tests were accomplished with the proposed algorithms and with these algorithms combined with the clustering search. The tests demonstrate that the application of the clustering search to these algorithms allows to obtain solutions of better quality and in smaller computational times, in relation to the solutions obtained by the algorithms AG and SATL separately. |
Area | COMP |
Arrangement | urlib.net > BDMCI > Fonds > Produção pgr ATUAIS > CAP > Métodos heurísticos para... |
doc Directory Content | access |
source Directory Content | @4primeirasPaginas-6.pdf | 21/05/2009 14:01 | 158.7 KiB | Banca_WesleyGomes.pdf | 11/09/2009 09:52 | 18.4 KiB | Dissertacao-Versao-Final.pdf | 11/09/2009 10:05 | 845.1 KiB | publicacao.pdf | 11/09/2009 10:05 | 670.1 KiB | |
agreement Directory Content | |
|
4. Conditions of access and use | |
data URL | http://urlib.net/ibi/8JMKD3MGP8W/34PGRBS |
zipped data URL | http://urlib.net/zip/8JMKD3MGP8W/34PGRBS |
Language | pt |
User Group | administrator camila jefferson viveca@sid.inpe.br wesgomes2005@gmail.com yolanda.souza@mcti.gov.br |
Visibility | shown |
Copyright License | urlib.net/www/2012/11.12.15.10 |
Copy Holder | SID/SCD |
Read Permission | allow from all |
Update Permission | not transferred |
|
5. Allied materials | |
Next Higher Units | 8JMKD3MGPCW/3F2PHGS |
Dissemination | NTRSNASA; BNDEPOSITOLEGAL. |
Host Collection | sid.inpe.br/mtc-m18@80/2008/03.17.15.17 |
|
6. Notes | |
Empty Fields | academicdepartment affiliation archivingpolicy archivist callnumber contenttype creatorhistory descriptionlevel doi electronicmailaddress format isbn issn label lineage mark mirrorrepository nextedition notes number orcid parameterlist parentrepositories previousedition previouslowerunit progress readergroup resumeid rightsholder schedulinginformation secondarydate secondarymark session shorttitle sponsor subject targetfile tertiarymark tertiarytype url versiontype |
|
7. Description control | |
e-Mail (login) | simone |
update | |
|