Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T17:08:54Z (GMT). No. of bitstreams: 1 Branchini_RodrigoMoretti_M.pdf: 2342940 bytes, checksum: 5fe2b9116f5e6ab8550773cc1b6c62e6 (MD5) Previous issue date: 2005 / Resumo: O problema de roteamento dinâmico de veículos com janelas de tempo (PRDVJT) decorre do problema de roteamento estático de veículos com janelas de tempo (PRVJT). No problema estático, o objetivo é atender todos os clientes dentro de intervalos de tempo previamente estipulados, respeitando as restrições de capacidade dos veículos e minimizando o número de veículos e a distância percorrida. Neste problema, todos os dados necessários para a definição das rotas são conhecidos a priori. No PRDVJT, algumas informações, por exemplo, a localização e a demanda de alguns clientes, são reveladas dinamicamente ao tomador de decisão, ao mesmo tempo em que os motoristas percorrem seus roteiros. Este trabalho estuda e desenvolve métodos para os problemas PRVJT e PRDVJT. Para o PRVJT são testadas heurísticas construtivas, incluindo a proposta de uma heurística focada na redução do número de rotas, e métodos de busca local e tabu baseados na vizinhança granular. Posteriormente, as heurísticas são adaptadas e aplicadas ao PRDVJT, avaliando-se os benefícios de desvio do destino planejado e de inclusão de estratégias de espera e de posicionamento de veículos. Os testes computacionais do PRDVJT são executados num ambiente de simulação baseado em características práticas levantadas numa pesquisa a campo com empresas de transportes da região de Campinas e São Paulo / Abstract: The dynamic vehicle routing problem with time windows (DVRPTW) originates from the static vehicle routing problem with time windows (VRPTW). The objective of the static problem is to serve a given set of clients within their time window constraints, subject to each vehicle capacity, minimizing the number of vehicles and the distance traveled. In this problem, all data needed to create routes is previously known. In the DVRPTW, some information, for instance, the positioning and demand of some clients, is dynamic revealed for the decision maker at the same time in which the drivers are executing their routes. This work studies and develops methods for the VRPTW and DVRPTW. Constructive heuristics, as well as a suggestion of an heuristic focused on route minimization, are discussed for the VRPTW. Also for the same problem, local and tabu search methods based on the granular neighborhood are tested. Afterward, these heuristics are adapted and applied for the DVRPTW, evaluating the benefits of diversion and waiting and positioning strategies. Computational experiments for the DVRPTW are performed with a simulation environment founded on practical attributes collected during interviews with transportation companies of the Campinas and São Paulo region / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientadores: Vinicius Amaral Armentano, Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-17T11:43:08Z (GMT). No. of bitstreams: 1 Scrich_CintiaRigao_M.pdf: 3723231 bytes, checksum: 483aa81bf811c8aab10a3b008d8a02fa (MD5) Previous issue date: 1992 / Resumo: O problema de dimensionamento de lotes de múltiplos itens com restrição de capacidade consiste na determinação das quantidades a serem produzidas em diferentes períodos de tempo na presença de restrição no recurso disponível. O modelo apresentado neste trabalho considera que a produção de um item em um dado período incorre em um custo fixo e um tempo de preparação. Para a resolução deste problema um método heurístico é desenvolvido. Além disso, é feita uma adaptação das técnicas de Busca Tabu a este método. Experimentos computacionais são apresentados e analisados / Abstract: The multi-item single-level capacitated lot-sizing problem consists in the determination of the amounts being produced in different periods of time in the presence of restriction on the available resources. The model presented in this work considers that the item production implies a setup cost and a setup time. To solve this problem a heuristic method is developed. Besides, an adaptatton of Tabu Search techniques for this method is done. Computational experiments are presented and analysed. / Mestrado / Mestre em Engenharia Elétrica

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2017-08-23T12:56:44Z No. of bitstreams: 1 texto completo.pdf: 993417 bytes, checksum: af46bc7032d180cae6ecae3aaebec7c1 (MD5) / Made available in DSpace on 2017-08-23T12:56:44Z (GMT). No. of bitstreams: 1 texto completo.pdf: 993417 bytes, checksum: af46bc7032d180cae6ecae3aaebec7c1 (MD5) Previous issue date: 2017-03-06 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Em um mundo que, em tempo acelerado, tem-se tornado cada vez mais necessitado em bens consumíveis e não consumíveis, a logística no transporte destes produtos tem sido colocada à prova, sendo uma das etapas mais importantes da relação entre o processo de produção e o usuário final. Cerca de um terço dos custos logísticos desta relação (produção-usuário) são determinados pelo custo de transporte dos bens, tornando essa operação muito importante. Um novo problem surgiu a partir de um entrave encontrado numa situação prática. O Problema do Roteamento de Veículos Duplo com Múltiplas Pilhas (DVRPMS) consiste em um Problema do Caixeiro Viajante com Múltiplas Pilhas (DTSPMS) com múltiplos veículos. Os dois problemas apareceram pela necessidade urgente em otimizar o transporte intermodal em um contexto europeu. Consiste em coletar pedidos em uma região de coleta e carregá-los num conjunto de pilhas dentro de um container, que não deve ser rearranjado por razões de segurança. O container então é levado a região de entrega e os itens são entregues seguindo a política das pilhas, em que os itens do topo, coletados por último, devem ser entregues primeiro. Nesta dissertação, quatro heurísticas baseadas na busca local iterativa (ILS), na descida em vizinhança variável (VND) e no recozimento simulado (SA) são propostas. O problema foi estendido para uma versão onde há uma oferta de itens maior do que a capacidade da frota de veículos. Um método exato é proposto juntamente com outras três heurísticas baseadas no ILS, SA e na busca tabu (TS). Os algoritmos propostos foram testados em experimentos computacionais e análises estatísticas foram feitas com intenção de encontrar a melhor combinação de parâmetros para estas heurísticas. Os resultados encontrados foram bons, tendo encontrado melhores médias que a literatura atual. / In a world, that in a fast pace, has become increasingly needed in consumable and nonconsumable goods, the logistics in the transportation of these products has been put to the test, being one of the most important stages in the relationship between the pro-duction process and the end user. It is said that at least 30% of the costs between the industry and the end user are solely determined by the cost of transportation. A novel problem arose followed by a question that was encountered in a real-life scenario. The Double Routing Vehicle Problem with Multiple Stacks (DVRPMS) consists in a Dou-ble Traveling Salesman Problem with Multiple Stacks (DTSPMS) with multiple vehicles. Both problems appeared for the urgent need of optimizing intermodal transportation in the european context. It consists in gathering costumer inquires from a pickup region and loading them in a set of stacks inside a container that must not be rearranged for security reasons. The container moves to a delivery region and the items gathered must be delivered according the last-in-first-out policy of the stacks. In this work, four heuristics were proposed based on the Iterated Local Search (ILS), Variable Neighborhood Descent and Simulated Annealing (SA) metaheuristics. The DVRPMS was extended to a modi-fied version where the items offered are bigger than the vehicle fleet capacities. An exact model approach is proposed and three other heuristics, based on the ILS, SA and Tabu Search are proposed and tested. The approaches presented in this work were tested by computational experiments and a statistical analysis was made to chose the best com-bination of parameters. Good results were found, providing a better average than the current literature.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-09-09T16:23:31Z No. of bitstreams: 1 texto completo.pdf: 700752 bytes, checksum: d8590a35a9faff6d372adf439ca649d6 (MD5) / Made available in DSpace on 2016-09-09T16:23:31Z (GMT). No. of bitstreams: 1 texto completo.pdf: 700752 bytes, checksum: d8590a35a9faff6d372adf439ca649d6 (MD5) Previous issue date: 2016-02-25 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Nesta dissertação apresentamos métodos gulosos para a seleção de um subconjunto de funções heurísticas de um grande conjunto de possibilidades com o objetivo de reduzir o tempo de execução de algoritmos de busca. Trabalhos anteriores mostraram que a busca pode ser mais rápido se vários bancos de dados padrão menores são usados em vez de um grande banco de dados padrão. Nossos métodos são capazes de selecionar boas heurísticas de um grande conjunto de funções heurísticas para guiar uma A*. Implementamos nosso método em Fast Downward e mostrou empiricamente que produz heurísticas que superam o estado-da-arte de outros planejadores na Competição Internacional de Planejamento. / In this dissertation we present greedy methods for selecting a subset of heuristic functions from a large pool of possibilities with the objective of reducing the running time of search algorithms. Previous works showed that search can be faster if several smaller pattern databases are used instead of one large pattern database. Our methods are able to select good heuristics from a large set of heuristic functions to guide A* search. We implemented our method in Fast Downward and showed empirically that it produces heuristics which outperform the state-of-the-art planners in the International Planning Competition benchmarks. / Autor sem Lattes.

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T08:51:37Z (GMT). No. of bitstreams: 1 Assis_LauraSilvade_M.pdf: 1632808 bytes, checksum: dfd28dc2bbd2bb5fe453a2fb1c2b7b6e (MD5) Previous issue date: 2009 / Resumo: O objetivo desta dissertação é desenvolver uma metodologia eficiente para solucionar o problema de agrupamento capacitado multicritério (PACM), no qual objetos com pesos associados são dados, os quais devem ser particionados em agrupamentos com capacidade limitada. Neste trabalho, o PACM está ambientado em um problema de reagrupamento de lotes urbanos, nos quais devem ser realizadas as leituras dos medidores de energia elétrica por concessionárias de distribuição de energia. A operação de leitura dos medidores é realizada sobre lotes geograficamente definidos e é desempenhada sobre rotas percorridas uma vez por mês pelos leituristas. A motivação deste trabalho é atribuída ao fato de que, com o passar do tempo, o tamanho e o formato dos lotes vão ficando obsoletos, devido a modificações introduzidas na conformação atual, desarranjando o equilíbrio entre os lotes e desatualizando as rotas. Por esse motivo é importante realizar um reagrupamento dos lotes buscando a diminuição dos custos operacionais de leitura, assim como a minimização dos custos e transtornos causados pelas modificações. O método proposto para resolver o problema abordado nesta dissertação é um algoritmo baseado na metaheurística GRASP (Greedy randomized adaptive search procedure). A eficiência do método proposto é testada sobre uma série de instâncias geradas e sobre uma rede real. Os experimentos computacionais demonstram a eficiência do método. / Abstract: The aim of this dissertation is to develop an eficient methodology to solve the multicriteria redistricting capacitated problem (PACM), in which objects with associated weights are given, which must be partitioned into groups with limited capacity. In this work, the PACM is inserted in to a reassignment problem of urban clusters of clients, in which the readings of the eletric energy measurement must be performed by the company of energy distribution. The reading operation is performed over lots geographically defined is performed once a month by the readers. The motivation of this work is due to the fact that the size and shape of the lots become obsolete after some time, due to modifications introduced in the current conformation, desarranging the balance between the lots and outdating the routes. For this reason it is important to achieve a reassignment of the lots trying to decrease the operational costs of reading, as well as minimizing the costs and inconvenience caused by the changes. The proposed method to solve the problem addressed in this dissertation is a algorithm based on GRASP (Greedy randomized adaptive search procedure) metaheuristic. The efectiveness of the proposed method is tested on a large number of generated instances and on a real network. Computational experiments demonstrate the efectiveness of the proposed approach. / Mestrado / Automação / Mestre em Engenharia Elétrica

Made available in DSpace on 2019-03-29T23:32:52Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-12-28 / The goal of Data Mining (DM) as a research area is to provide a set of tasks and algorithms aiming at extracting interesting and useful information from large databases. Among several DM tasks lies that of biclustering, whereby rows and columns of a data matrix are simultaneously grouped based on the similarity of their elements. The main objectives of this work are to provide a thorough comparative assessment on the performance of several multimodal bio-inspired algorithms while coping with biclustering as well as to investigate the potentials of ensemble models induced over biclusters generated by these algorithms, having in mind Bioinformatics problems. After introducing general DM concepts as well as specific concepts related to biclustering, a detailed characterization of the multimodal bio-inspired algorithms and ensemble models investigated here is provided. Experiments have been systematically conducted to evaluate the performance of these algorithms, and the overall results achieved indicate that the ensemble models can usually outperform the multimodal bio-inspired algorithms when applied alone, as evidenced by several efficiency and effectiveness measures and hypothesis tests. Keywords: Data mining, Machine learning, Biclustering, Committee machines, Metaheuristics, Bio-inspired algorithms, Bioinformatics. / A área de Mineração de Dados (MD) fornece um conjunto de tarefas e algoritmos voltados à extração de informações de grandes bases de dados. Entre essas tarefas, temos o agrupamento bidimensional de dados (biclustering), em que linhas e colunas de uma matriz são agrupadas simultaneamente com base na similaridade dos seus elementos. Os objetivos deste trabalho são realizar um estudo comparativo sistemático entre algoritmos bio-inspirados multimodais aplicados à tarefa de agrupamento bidimensional de dados e investigar o desempenho de comitês de biclusters gerados por esses algoritmos, tomando como base problemas de Bioinformática. Após se introduzir conceitos gerais de MD e específicos da tarefa de biclustering, passa-se a discorrer sobre algoritmos bio-inspirados multimodais e sobre modelos de comitês aplicados a essa tarefa. Experimentos conduzidos de forma sistemática avaliam o desempenho dos algoritmos bio-inspirados e de dois arranjos de comitês de biclusters, sendo que os resultados obtidos indicam que, em geral, os comitês obtiveram um desempenho mais satisfatório que os algoritmos multimodais, de acordo com as métricas de avaliação levantadas e testes estatísticos. Palavras-Chave: Mineração de dados, Aprendizado de máquina, Agrupamento bidimensional, Comitês de máquinas, Meta-heurísticas, Algoritmos bio-inspirados, Bioinformática

Made available in DSpace on 2019-03-29T23:33:16Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-07-27 / Hyper-heuristics are an emerging theme in the optimization area which try to address computationally hard problems at a new level of abstraction. Instead of having a single algorithm that is optimized to perform well on a certain class of problems, hyper-heuristics try to balance the advantages and disadvantages of a set of problem specific heuristic algorithms, named low-level heuristics. By combining and parameterizing these heuristics or heuristic components in different ways, hyper-heuristics seek a satisfactory result in a larger set of problem instances. The objectives of this work are to propose a new hyper-heuristic approach inspired by particle swarms and to analyze empirically the utilization and the effectiveness of low-level heuristics during the execution of the proposed hyper-heuristic and of a set of hyper-heuristics proposed by other authors. The novel hyper-heuristic simultaneously explores the heuristic space as well as the solution space by maintaining both a population of heuristics and another of candidate solutions. Computational experiments and statistical tests were used to compare the effectiveness of the hyper-heuristics investigated here, demonstrating that the proposed hyper-heuristic obtained a more satisfactory performance in accordance with the evaluation metrics used. The empirical analysis allowed us to observe the different patterns of usage by the contestant hyper-heuristics of the low-level heuristics available for each problem domain. Keywords: Hyper-heuristics, Metaheuristics, Combinatorial Optimization, Particle Swarm Optimization. / Hiper-heurísticas são um tema emergente na área de otimização e se propõem a resolver problemas computacionalmente difíceis com um novo nível de abstração. Em vez de se ter um único algoritmo otimizado para tratar bem uma certa classe de problemas, elas tentam balancear as vantagens e desvantagens de um conjunto de heurísticas específicas para um domínio de problema, denominadas heurísticas de baixo nível. Combinando e parametrizando essas heurísticas, ou componentes de heurísticas, se busca um resultado satisfatório em um conjunto maior de instâncias de problemas. Os objetivos deste trabalho são propor uma nova abordagem hiper-heurística inspirada em enxame de partículas e analisar empiricamente o uso e a eficácia das heurísticas de baixo nível utilizadas durante a execução da hiper-heurística proposta, bem como de um conjunto de hiper-heurísticas concebidas por outros autores. A hiper-heurística proposta explora concorrentemente o espaço de busca heurístico e o espaço de busca de soluções, lançando mão de uma população de heurísticas e outra de soluções-candidatas. Experimentos computacionais e testes estatísticos foram utilizados para comparar a eficácia das hiper-heurísticas investigadas, demonstrando que a hiper-heurística proposta obteve um desempenho mais satisfatório de acordo com as métricas de avaliação utilizadas. Por outro lado, a análise empírica possibilitou o entendimento dos diferentes padrões de uso, por parte das hiper-heurísticas investigadas, das heurísticas de baixo nível disponíveis para cada domínio de problema. Palavras-Chave: Hiper-heurísticas, Meta-heurísticas, Otimização Combinatória, Otimização por Enxame de Partículas.

Tese de mestrado integrado. Engenharia Electrotécnica e de Computadores (Major Energia). Faculdade de Engenharia. Universidade do Porto. 2010

Made available in DSpace on 2013-08-07T18:42:45Z (GMT). No. of bitstreams: 1 000418219-Texto+Completo-0.pdf: 4033858 bytes, checksum: 2661cfd90512a0fe826582c0489e6ce1 (MD5) Previous issue date: 2009 / MPSoCs are multi-processor systems integrated in a single chip. They are a trend in VLSI circuit design, since they minimize the design productivity crisis represented by the gap between the silicon technol-ogy and the actual SoC design capacity. Examples of MPSoCs include those proposed by Intel and Tilera, composed by 80 and 64 processing elements respectively. MPSoCs may employ NoCs to integrate several processors, memories, as well as specific hardware cores. NoCs may be used to replace busses, due to their ad-vantages of higher scalability and communication parallelism. The target architecture of the present work is a NoC-based heterogeneous MPSoC supporting hard-ware task execution through embedded reconfigurable logic, together with software tasks executed by pro-grammable processors. One of the processors of the target architecture, named manager processor, is respon-sible for system resources management, task scheduling, task mapping, and configuration control. Task map-ping defines the placement of a new task into the system. Most works in literature propose static mapping techniques defined at design time, where all application tasks are mapped simultaneously. This static map-ping is not appropriate for dynamic workloads scenarios. Since applications running in MPSoCs may con-tain a varying number of tasks, and since their number may exceed the available resources, task mapping at run-time is necessary. Such task mapping method is named dynamic task mapping. The present work investigates the performance of heuristics for dynamic task mapping, targeting NoC congestion minimization. Tasks are mapped on demand, according to the communication requests and the load in NoC channels. The implemented algorithms employ a greedy approach, where tasks are indivi-dually mapped. The mapping decision is based on local information, considering the communication con-straints of the requested task. The algorithm used as the reference mapping strategy in experiments maps a task into the first free resource available. Four congestion-aware mapping heuristics are proposed. Through the experiments employing RTL abstraction level modeling, it is possible to observe reductions of 31% in channel load distribution, 15% in average latency, and 87% in congestion level. These results demonstrate the efficiency of proposed heuristics. / MPSoCs são sistemas multiprocessados integrados na forma de um SoC. Eles são tendência no projeto de circuitos VLSI, pois minimizam a crise de produtividade de projeto, representada pelo descompasso entre a capacidade da tecnologia do silício e a capacidade atual de projeto de SoCs. Cita-se como exemplo de MPSoCs os propostos pela Intel e pela Tilera, compostos respectivamente por 80 e 64 núcleos de processa-mento. MPSoCs podem empregar NoCs para integrar diversos processadores, memórias, bem como núcleos de hardware específicos. O uso de NoCs deve-se a suas vantagens em relação a barramentos, entre as quais maior escalabilidade e paralelismo na comunicação. A arquitetura alvo do presente trabalho consiste em um MPSoC heterogêneo, com utilização de NoC como meio interconexão entre os elementos de processamento, suportando a execução de tarefas de hardware via lógica reconfigurável, e a execução de tarefas de software via processadores. Um dos processadores da arquitetura alvo, denominado processador gerente, é responsável por: gerência da ocupação dos recursos do sistema, escalonamento, mapeamento, e configuração de tarefas. O mapeamento de tarefas define a posição de uma dada tarefa no sistema. A maioria dos trabalhos encontrados na literatura propõe técnicas de mapeamento estático, definido em tempo de projeto, no qual todas as tarefas de uma dada aplicação são mapeadas simultaneamente. Este mapeamento estático não é adequado para cenários com carga dinâmica de tarefas. Dado que aplicações executando em um MPSoC podem possuir um número variável de tarefas, e que tal número pode exceder os recursos disponíveis, é necessário realizar o mapeamento de tarefas em tempo de execução, mapeamento este denominado de mapeamento dinâmico.O presente trabalho investiga o desempenho de heurísticas para mapeamento dinâmico de tarefas, com o objetivo de minimizar congestionamentos em NoCs. As tarefas são mapeadas sob demanda, de acordo com as requisições de comunicação e com a ocupação dos canais da NoC. Os algoritmos implementados aplicam estratégias gulosas, onde as tarefas são mapeadas uma por vez. Para isso, a decisão é baseada na informação local da aplicação, apenas relacionada à tarefa requisitada. O algoritmo utilizado como referência nos experimentos mapeia uma dada tarefa no primeiro recurso livre encontrado. Quatro heurísticas congestion-aware são propostas. Através de experimentos realizados com base na modelagem do sistema no nível RTL, pode-se observar redução de 31% na carga nos canais da NoC, de 15% na latência média, e de até 87% no nível médio de congestionamento. Tais resultados demonstram a eficiência das heurísticas propostas.

Made available in DSpace on 2013-08-07T18:43:25Z (GMT). No. of bitstreams: 1 000445541-Texto+Completo-0.pdf: 1627180 bytes, checksum: 184a4b2054d700b987b074f0fcdf3122 (MD5) Previous issue date: 2011 / The definitory context is part of a text or utterance that provides information about a concept based on its use. The extraction of definitions from texts is an important task in various applications. Several papers present this feature as an aid in the construction of ontologies, in the development of material for aid in translation, in question answering systems, in creation of glossaries, dictionaries, among others. Thus, this study proposes set of heuristics to make the automatic extraction of potentially definitory contexts contained in Portuguese texts. The results of these heuristics were evaluated by terminologists and obtained 35. 1 % F-measure when applied in a General Geology corpus and 51. 7 % F-measure when applied in a General Chemistry corpus, reducing in both more than 50%of the amount of contexts to be examined by a specialist compared with the contexts extraction through a concordancer. / O contexto definitório é a parte de um texto ou de um enunciado que fornece informação sobre um conceito, com base em seu uso. A extração de contextos definitórios a partir de textos é uma tarefa importante em várias aplicações. Diversos trabalhos usam este recurso como auxílio na construção de ontologias, no desenvolvimento de material de auxílio à tradução, na elaboração de sistemas de perguntas e respostas, na criação de glossários, dicionários, entre outros. Nesse sentido, este trabalho propõe um conjunto de heurísticas para fazer a extração automática de contextos potencialmente definitórios em textos de língua portuguesa. Os resultados dessas heurísticas foram avaliados por terminólogos. Os resultados mostram 35,1% de F-measure quando o conjunto de heuristicas foi aplicado a um corpus de Geologia Geral e 51,7% de F-measure quando aplicado a um corpus de Química Geral. Isso proporcionou uma redução, em ambos os corpus, de mais de 50% da quantidade de contextos para serem analisados pelo especialista, comparando-se com a extração de contextos em um concordanciador.