Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-graduação em Engenharia de Produção / Made available in DSpace on 2012-10-24T18:46:13Z (GMT). No. of bitstreams: 1 264414.pdf: 1891457 bytes, checksum: 127160c37f20ea0b01f38df656a3d580 (MD5) / Neste trabalho são implementadas e analisadas as heurísticas de Teitz e Bart, Busca Tabu e Algoritmo Genético aplicadas ao problema das p-medianas. O objetivo foi avaliar o desempenho dos algoritmos em redes pequenas, médias e grandes levando-se em consideração o valor da solução e o tempo de resolução. Para isso foram realizados testes em 115 problemas gerados aleatoriamente. Os resultados demonstraram bom desempenho dos algoritmos de Busca Tabu e Algoritmo Genético em redes pequenas e médias. Já em problemas de grande porte, o algoritmo de Teitz e Bart modificado forneceu melhores respostas em menor tempo.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção. / Made available in DSpace on 2012-10-19T06:59:24Z (GMT). No. of bitstreams: 0Bitstream added on 2014-09-25T20:03:50Z : No. of bitstreams: 1 189369.pdf: 2212563 bytes, checksum: 221c5745289029bcb70d87e32f435c83 (MD5) / Para o problema das p-medianas foi desenvolvida e implementada uma heurística baseada em algoritmos genéticos, cujos resultados foram equiparáveis aos obtidos em outros métodos, apontados na literatura como mais indicados para a resolução do problema. Em particular, para efeito de validação dos resultados foi implementado o método de substituição de vértices proposto por Teitz e Bart (1968), citado na literatura como o método mais usado e que melhores resultados oferece para o problema das p-medianas.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia de Produção, Florianópolis, 2010 / Made available in DSpace on 2012-10-25T04:16:28Z (GMT). No. of bitstreams: 1 284254.pdf: 811377 bytes, checksum: 8bcc424ed5fdd32a50e501be02fe295e (MD5) / Neste trabalho é proposto um modelo de otimização para o problema de localização de instalações, alocação de demanda e operação de estoque em redes dinâmicas onde parte dos arcos desta rede está sujeita a interrupções que podem ocorrer segundo probabilidades conhecidas, respeitando um processo Markoviano. O modelo é concebido com o objetivo de integrar, numa mesma abordagem, decisões estratégicas (onde localizar) e decisões operacionais (como operar) visando proporcionar a minimização dos custos do sistema, ao mesmo tempo em que se estabelece nível de serviço para atendimento à demanda. Para resolver este modelo é desenvolvida uma estratégia que utiliza programação dinâmica estocástica, simulação, o modelo clássico de lote econômico de compra e uma adaptação do algoritmo heurístico de Teitz & Bart. Tal estratégia é implementada em um programa de computador e testes computacionais são realizados com sucesso em um estudo de caso elaborado a partir de dados hipotéticos. Os resultados obtidos e as análises realizadas demonstram a factibilidade do modelo e a aplicabilidade da estratégia de solução.

Este trabalho visa identificar, a partir de um levantamento de dados dos fluxos de cargas conteinerizadas e custos operacionais de transporte, os locais mais promissores para a instalação de futuros terminais intermodais de carga rodo-ferroviários, com auxílio de um Sistema de Informações Geográficas (TransCAD), objetivando a redução dos custos e otimização das operações logísticas envolvidas na rede de transportes do estado de São Paulo. Simulações são feitas para a instalação de até dez terminais intermodais rodo-ferroviários em pontos estratégicos do interior do Estado, considerando-se duas condições: a primeira com um terminal existente só em Santos e todos os pontos candidatos escolhidos pelo modelo de localização das p-medianas do TransCAD e, a segunda, considerando-se, além de Santos, os oito terminais intermodais já existentes no Estado. Apresenta-se uma análise dos custos de rede e os mapas temáticos de áreas de influência de cada uma das soluções obtidas pelo modelo. Os resultados são comparados com o trabalho de TONDO (1992). Conclui-se que as soluções encontradas através de um novo enfoque de modelagem do problema, são significativamente diferentes daqueles propostos por TONDO (1992). / Based on a data collection of containerized cargo flows and operational transport costs, this study has the objective of identifying promising points to install future road-rail intermodal container terminals, using a Geographic Information System (TransCAD) and the objective function of reducing costs and optimising logistic operations on the transport network of the state of São Paulo. Simulations are presented for the instalation of up to ten road-rail intermodal terminals at strategic locations in the interior of the State, considering two conditions: the first one, with only one terminal placed at the port of Santos and all the candidate points beeing chosen by the p-median location model of TransCAD, and the second one, considering Santos and the other eight existing intermodal terminals in the State. An analysis of the network costs and thematic maps of the influence areas of each solution are presented. The results are compared with the study by TONDO (1992). It is concluded that the solutions obtained by this new modeling focus of the problem, are considerably different from the ones obtained by TONDO (1992).

Este trabalho visa identificar, a partir de um levantamento de dados dos fluxos de cargas conteinerizadas e custos operacionais de transporte, os locais mais promissores para a instalação de futuros terminais intermodais de carga rodo-ferroviários, com auxílio de um Sistema de Informações Geográficas (TransCAD), objetivando a redução dos custos e otimização das operações logísticas envolvidas na rede de transportes do estado de São Paulo. Simulações são feitas para a instalação de até dez terminais intermodais rodo-ferroviários em pontos estratégicos do interior do Estado, considerando-se duas condições: a primeira com um terminal existente só em Santos e todos os pontos candidatos escolhidos pelo modelo de localização das p-medianas do TransCAD e, a segunda, considerando-se, além de Santos, os oito terminais intermodais já existentes no Estado. Apresenta-se uma análise dos custos de rede e os mapas temáticos de áreas de influência de cada uma das soluções obtidas pelo modelo. Os resultados são comparados com o trabalho de TONDO (1992). Conclui-se que as soluções encontradas através de um novo enfoque de modelagem do problema, são significativamente diferentes daqueles propostos por TONDO (1992). / Based on a data collection of containerized cargo flows and operational transport costs, this study has the objective of identifying promising points to install future road-rail intermodal container terminals, using a Geographic Information System (TransCAD) and the objective function of reducing costs and optimising logistic operations on the transport network of the state of São Paulo. Simulations are presented for the instalation of up to ten road-rail intermodal terminals at strategic locations in the interior of the State, considering two conditions: the first one, with only one terminal placed at the port of Santos and all the candidate points beeing chosen by the p-median location model of TransCAD, and the second one, considering Santos and the other eight existing intermodal terminals in the State. An analysis of the network costs and thematic maps of the influence areas of each solution are presented. The results are compared with the study by TONDO (1992). It is concluded that the solutions obtained by this new modeling focus of the problem, are considerably different from the ones obtained by TONDO (1992).

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2016-01-05T18:01:11Z No. of bitstreams: 1 EvertonSanti_TESE.pdf: 601652 bytes, checksum: 52767a19768856b40fcce8bb5611ef4b (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2016-01-11T18:20:39Z (GMT) No. of bitstreams: 1 EvertonSanti_TESE.pdf: 601652 bytes, checksum: 52767a19768856b40fcce8bb5611ef4b (MD5) / Made available in DSpace on 2016-01-11T18:20:39Z (GMT). No. of bitstreams: 1 EvertonSanti_TESE.pdf: 601652 bytes, checksum: 52767a19768856b40fcce8bb5611ef4b (MD5) Previous issue date: 2014-11-14 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior - CAPES / Apresenta-se neste trabalho um novo modelo para o Problema das p-Medianas Heterog?neo (PPMH), proposto para recuperar a estrutura de categorias n?o-observadas presente em dados oriundos de uma tarefa de triagem, uma abordagem popular que possibilita entender a percep??o heterog?nea que um grupo de indiv?duos tem em rela??o a um conjunto de produtos ou marcas. Este novo modelo ? chamado Problema das p-Medianas Heterog?neo Livre de Penalidade (PPMHLP), uma vers?o mono-objetivo do problema original, o PPMH. O par?metro principal do modelo PPMH ? tamb?m eliminado, o fator de penalidade. Este par?metro ? respons?vel pela pondera??o dos termos de sua fun??o objetivo. O ajuste do fator de penalidade controla a maneira como o modelo recupera a estrutura de categorias n?o-observadas presente nos dados e depende de um amplo conhecimento do problema. Adicionalmente, duas formula??es complementares para o PPMHLP s?o apresentadas, ambas problemas de programa??o linear inteira mista. A partir destas formula??es adicionais, limitantes inferiores foram obtidos para o PPMHLP. Estes valores foram utilizados para validar um algoritmo de Busca em Vizinhan?a Variada (VNS), proposto para resolver o PPMHLP. Este algoritmo obteve solu??es de boa qualidade para o PPMHLP, resolvendo inst?ncias geradas de forma artificial por meio de uma Simula??o de Monte Carlo e inst?ncias reais, mesmo com recursos computacionais limitados. As estat?sticas analisadas neste trabalho sugerem que o novo algoritmo e modelo, o PPMHLP, pode recuperar de forma mais precisa que o algoritmo e modelo original, o PPMH, a estrutura de categorias n?o-observadas presente nos dados, relacionada ? percep??o heterog?nea dos indiv?duos. Por fim, uma exemplo de aplica??o do PPMHLP ? apresentado, bem como s?o consideradas novas possibilidades para este modelo, estendendo-o a ambientes fuzzy / This work presents a new model for the Heterogeneous p-median Problem (HPM), proposed to recover the hidden category structures present in the data provided by a sorting task procedure, a popular approach to understand heterogeneous individual?s perception of products and brands. This new model is named as the Penalty-free Heterogeneous p-median Problem (PFHPM), a single-objective version of the original problem, the HPM. The main parameter in the HPM is also eliminated, the penalty factor. It is responsible for the weighting of the objective function terms. The adjusting of this parameter controls the way that the model recovers the hidden category structures present in data, and depends on a broad knowledge of the problem. Additionally, two complementary formulations for the PFHPM are shown, both mixed integer linear programming problems. From these additional formulations lower-bounds were obtained for the PFHPM. These values were used to validate a specialized Variable Neighborhood Search (VNS) algorithm, proposed to solve the PFHPM. This algorithm provided good quality solutions for the PFHPM, solving artificial generated instances from a Monte Carlo Simulation and real data instances, even with limited computational resources. Statistical analyses presented in this work suggest that the new algorithm and model, the PFHPM, can recover more accurately the original category structures related to heterogeneous individual?s perceptions than the original model and algorithm, the HPM. Finally, an illustrative application of the PFHPM is presented, as well as some insights about some new possibilities for it, extending the new model to fuzzy environments

[pt] Uma facilidade é qualquer centro que presta serviços a um conjunto de clientes. Pode ser, dentre outros, uma escola, uma fabrica ou um armazém. Problemas de localização de facilidades são problemas de otimização combinatória que tratam da tomada de decisão relativa ao posicionamento destes serviços, que devem otimizar algum critério pré-definido. As medidas que usualmente são utilizadas para quantificar a qualidade de uma solução para esta classe de problemas tem seus cálculos baseados em que clientes são servidos por que facilidade. Uma conseqüência imediata é a forte relação entre os problemas de localização e os problemas de classificação de dados (clusterização). Dentre os problemas de localização de facilidades amplamente estudados esta o problema das p-Medianas (PMNC), objeto de pesquisa desta dissertação. O PMNC tem como objetivo determinar quais p facilidades devem ser abertas com o intuito de minimizar a soma das distancias de cada cliente a facilidade aberta mais próxima do mesmo. O PMNC é classificado como um problema NP - Difícil e é um dos problemas centrais na classificação automática de dados (clusterização). Esta dissertação apresenta algoritmos primais, duais e exatos para tratamento do PMNC, focando no desenvolvimento de algoritmos duais e exatos. Foram implementadas cinco heurísticas construtivas e um método de busca local. Além disto, foram propostos três novos métodos duais e um método exato. Como resultado, analisamos um conjunto de técnicas para o tratamento do problema. A escolha da melhor técnica é fortemente dependente da configuração da instancia tratada. Foi obtido o ótimo para algumas instancias e para as demais a diferença entre o valor dos limites inferior e superior nos melhores casos não ultrapassam 3%. / [en] A facility is any center that offers services to a set of clients. It may be, among others, a school, a factory or a depot. Facility location problems are combinatorial optimization problems that handle decisionmaking in respect to the positioning of those services, optimizing some defined criteria. The measures often used to assess the quality of a solution for this class of problems relate to which clients are served by which facility. An immediate consequence is the strong relationship between location problems and data clustering. One of the widely studied facility location problems is the uncapacited p-median problem (UPM), the main subject of this thesis. Given a set of possible facility locations, the UPM consists in determining a subset of locations at which the facilities shall be established, minimizing the sum of distances from each client to its closest open facility. The UPM belongs to the class of NP-hard problems and is a central problem of data clustering. This thesis presents primal, dual and exact algorithms for approaching the UPM, focusing on the development of dual and exact algorithms. Five constructive heuristics and one local search method were implemented. Furthermore, three new dual methods and one exact method were proposed. The result is the analysis of a set of techniques to solve the problem. The choice of best technique is strongly dependent of the configuration of the treated instance. We obtained the optimum for some instances and for others the difference between the value of the lower and upper bounds in the best cases do not exceed 3%.

Made available in DSpace on 2015-05-08T14:53:37Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 3740949 bytes, checksum: 4b4bb1e725e28d0a9a489835e70b4e60 (MD5) Previous issue date: 2014-02-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Find emergency public services falls into one of the classic optimization problems where points are available for candidates who are chosen, among them, those that optimize the efficiency criteria established, to find a limited number of facilities. The set of candidate sites have great influence on the final solution generated by a model location . In the research, three strategies were used to elect local candidates to position the cars of police : decision of the Security Manager , p-median model and method of clustering k-means. With the support of Geographical Information Systems (GIS ) it was possible to georeference the occurrences of crimes , to visualize the distribution of selected local candidates and identify the presence of hotspots of crime. Aiming to solve the problem of allocating vehicles adopted two approaches : exact and heuristic . Therefore, two hybrid meta - heuristics were implemented - GRASP combined with VND and GRASP with exact model. They obtained same or very approximate solutions of the optimal solution . It was developed a system of spatial decision support based on the solution of the formulation of the problem of locating facilities with restricted coverage and backup coverage. It is a Web tool built with by WebGIS technology / Localizar serviços públicos emergenciais se enquadra em um dos problemas clássicos de otimização onde pontos candidatos são disponibilizados para que sejam escolhidos, dentre eles, aqueles que otimizem o critério de eficiência estabelecido, visando localizar um número limitado de facilidades. O conjunto de locais candidatos tem grande influência sobre a solução final gerada por um modelo de localização. Na pesquisa, foram definidas três estratégias para eleger os locais candidatos ao posicionamento de viaturas policiais: decisão do gestor de segurança, modelo de Pmedianas e método de clusterização k-means. Com apoio de Sistemas de Informação Geográfica (SIG) foi possível georreferenciar as ocorrências de crimes, visualizar a distribuição dos locais candidatos selecionados e identificar a presença de hotspots de crimes. Visando resolver o problema de alocação de viaturas adotou-se duas abordagens: exata e heurística. Para tanto, duas meta-heurísticas híbridas foram implementadas - GRASP combinado com VND e GRASP com modelo exato, as quais obtiveram soluções iguais ou muito aproximadas da solução ótima. Foi desenvolvido um sistema de apoio a decisão espacial baseado na solução da formulação do problema de localização de facilidades com restrições de cobertura e cobertura backup. Trata-se de uma ferramenta WEB construída com base os padrões usados pela tecnologia WebGIS

Made available in DSpace on 2014-12-17T14:52:50Z (GMT). No. of bitstreams: 1 AndreMG_DISSERT.pdf: 2426032 bytes, checksum: 12cecc3ac8e26d885793286de73b6a32 (MD5) Previous issue date: 2010-02-26 / The decrease in crime is one of the core issues that cause concern in society today. This study aims to propose improvements to public safety from the choice of points to the location of police units, ie the points which support the car and the police. For this, three models were developed in order to assist decision making regarding the best placement of these bases. The Model of Police Units Routing has the intention to analyze the current configuration of a given region and develop optimal routes for round preventative. The Model of Allocation and Routing for New Police Units (MARNUP) used the model of facility location called p-median weighted and traveling salesman problem (TSP) combined aiming an ideal setting for regions that do not yet have support points or to assess how far the distribution is present in relation to that found in solution. The Model Redefinition and Routing Unit Police (MRRUP) seek to change the current positioning taking into account the budgetary constraints of the decision maker. To verify the applicability of these models we used data from 602 points to instances of police command that is responsible for the capital city of Natal. The city currently has 31 police units for 36 of these 19 districts and police have some assistance. This reality can lead to higher costs and higher response times for answering emergency calls. The results of the models showed that in an ideal situation it is possible to define a distance of 500 km/round, whereas in this 900 km are covered by approximately round. However, a change from three-point lead reduced to 700 km / round which represents a decrease of 22% in the route. This reduction should help improve response time to emergency care, improving the level of service provided by the increase of solved cases, reducing police shifts and routing preventive patrols / A diminui??o da criminalidade ? uma das quest?es centrais que geram preocupa??o na sociedade atual. O presente estudo objetiva propor melhorias a seguran?a p?blica a partir da escolha de pontos para a localiza??o de unidades policiais, ou seja, dos pontos que servem de apoio ?s viaturas e aos policiais. Para isto, tr?s modelos matem?ticos foram desenvolvidos no intuito de auxiliar a tomada de decis?o com rela??o ao melhor posicionamento destas bases. O Modelo de Roteiriza??o das Unidades Policiais tem como intuito analisar a configura??o atual de determinada regi?o e desenvolver rotas ?timas para a ronda preventiva. O Modelo de Aloca??o e Roteiriza??o de Novas Unidades Policiais (MARNUP) utilizou o modelo de localiza??o de instala??es denominado de p-medianas e o problema do caixeiro viajante (TSP) combinados objetivando uma configura??o ideal para regi?es que ainda n?o possuem pontos de apoio ou para avaliar o qu?o distante est? a distribui??o presente em rela??o ao encontrado na solu??o. O Modelo de Redefini??o e Roteiriza??o de Unidades Policiais (MRRUP) busca a mudan?a do posicionamento atual levando em considera??o as restri??es or?ament?rias do decisor. Para a verifica??o da aplicabilidade destes modelos utilizou-se dados de 602 pontos de ocorr?ncias do Comando de Policiamento da Capital que ? respons?vel pelo munic?pio de Natal. A cidade atualmente possui 31 unidades policiais para 36 bairros e destes 19 possuem algum aux?lio policial. Esta realidade pode gerar custos mais elevados e maiores tempos de resposta para o atendimento de chamadas de emerg?ncias. Os resultados encontrados pelos modelos mostraram que em uma situa??o ideal ? poss?vel delimitar uma dist?ncia percorrida de 500 km, enquanto no presente 900 km s?o percorridos aproximadamente por ronda. Contudo, uma mudan?a de tr?s pontos leva a redu??o para 700 km/ronda o que representa uma diminui??o de 22% no percurso. Esta diminui??o deve ajudar na melhoria do tempo de resposta ao atendimento de emerg?ncias, na melhoria do n?vel de servi?o proporcionada pelo aumento de casos resolvidos, na redu??o dos deslocamentos policiais e no roteamento de rondas preventivas

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The evolution of computer hardware as well as new applications of mathematical programming techniques, efficiently implemented in many commercial solvers, has given rise to new algorithms called hybrid metaheuristic, which have been applied to solve combinatorial problems. This work presents several approaches which try to deal with the hybridization of local search based metaheuristics with exact algorithms to solve two problems of combinatorial optimization. More specifically, the first problem, capacitated p-median problem, the proposed approach considers heuristic elimination of variable of the original mathematical model, that produce solutions of very good quality in a short amount of time, and a combination with an iterative procedure in which only a certain subset of points is considered. As regards the second problem, unrelated parallel machine scheduling with sequence and machine dependent setup time problem of minimizing makespan, is proposed a mathematical model to search the neighborhood of a solution and identify movement sequences to minimize the objective function. In both cases, mathematical models are solved using a commercial solver. Extensive computational experiments are carried out to demonstrate the good performance of the proposed approaches. / A recente evolução dos computadores como também dos métodos exatos oriundos da programação matemática, muitos destes eficientemente implementados em otimizadores comerciais, propiciou o surgimento de novos algoritmos, denominados metaheurísticas híbridas, que têm sido aplicados para resolução de problemas combinatoriais. Este trabalho apresenta abordagens que hibridizam metaheurísticas baseadas em busca local com algoritmos exatos de programação matemática para resolver dois problemas de otimização combinatória. Mais especificamente, para o primeiro problema, o problema das p-medianas capacitado, a proposta considera a eliminação heurística de variáveis do modelo matemático, que permite a obtenção de soluções de boa qualidade em um curto tempo computacional, e a combinação com um procedimento iterativo no qual apenas um determinado subconjunto de pontos é considerado. No que se refere ao segundo problema, programação de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência e da máquina com objetivo de minimizar o tempo de processamento total da máquina com maior carga entre todas (makespan), propõe-se um modelo matemático para varrer a vizinhança de uma solução e identificar sequências de movimentos de tarefas que podem ser aplicadas na respectiva solução de modo a minimizar a função objetivo. Nos dois casos os modelos matemáticos são resolvidos utilizando um otimizador comercial. Extensivos testes computacionais são realizados para demonstrar o bom desempenho das abordagens propostas.