Apesar de serem utilizados com sucesso em problemas de roteirização clássicos como o do caixeiro-viajante e o de roteirização de veículos com janelas de tempo, os algoritmos genéticos não apresentavam bons resultados nos problemas de roteirização de veículos sem janelas de tempo. Utilizando-se de uma tendência recente de hibridização de algoritmos genéticos, Prins (2004) elaborou um algoritmo para o problema de roteirização de veículos sem janelas de tempo, monoperíodo, e que obrigatoriamente atenda a todos os clientes cujos resultados, quando aplicado a instâncias de Christofides et al. (1979) e de Golden et al. (1998), são comparáveis aos melhores códigos elaborados com base na busca tabu. Diferentemente da maioria dos algoritmos genéticos apresentados para solução de problemas de roteirização de veículos, no método desenvolvido por Prins (2004) o cromossomo é composto apenas pelos pontos a serem atendidos, não contendo delimitadores de rotas. Estas são definidas a partir de um método de particionamento do cromossomo. Este trabalho implementa o algoritmo descrito por Prins (2004) e propõe a este melhorias em diversas de suas etapas, como inicialização, operação de crossover, operação de mutação, reinicialização e particionamento do cromossomo. As alterações implantadas são aplicadas às instâncias de Christofides et al. (1979) e comparadas com o algoritmo inicial em termos de qualidade de solução e tempo de processamento. Finalmente, é elaborado um algoritmo genético que contempla as alterações que obtiveram resultados positivos. / In the Vehicle Routing Problem (VRP) we seek for a set of minimum-cost vehicle routes for a fleet of identical vehicles, each starting and ending at a depot, such that each customer is visited exactly once and the total demand of any route does not exceed the vehicle capacity. Several families of heuristics have been proposed for the VRP. They can be broadly classified into two main classes: classical heuristics developed between 1960 and 1990, and, more recently, metaheuristics. Among them, tabu search plays an key role, being acknowledged by most authors as the most successful approach for the VRP. In the literature some successful implementations of metaheuristic Genetic Algorithm (GA) can be found for classic routing problems such as the traveling salesman and vehicle routing problems with time windows. However, until recently, the same did not apply for the VRP. In this thesis we develop a genetic algorithm without trip delimiters, and hybridized with a local search procedure, for the solving the VRP, which is based on the work of Prins (2004). At any time, a chromosome can be converted into an optimal VRP solution (subject to chromosome sequence) by means of a splitting procedure, in which the chromosome sequence, representing a giant tour, is partitioned into feasible routes in terms of vehicle capacities. Starting with the procedure originally proposed Prins (2004), we then introduce new improvements in terms of the different components of the GA, aiming to obtain improved solutions. These include how we determine the initial population, different partitioning approaches, alternative reproduction (crossover) processes, a granular tabu mechanism similar to the one proposed by Toth and Vigo (2003 and, finally, in changes in the reinitialization process, aiming to reestablish diversity. Computational experiments are presented, based on the 14 classical Christofides instances for the VRP. The results show that the proposed improved versions of the GA allow us to obtain better solutions when compared to the original approach by Prins (2004).

A crescente necessidade de buscar operações mais eficientes, com menor custo e mais sustentáveis tem feito com que empresas passassem a procurar oportunidades pelas quais estes objetivos pudessem ser atingidos. Na área de transportes encontrou-se na colaboração uma oportunidade para tal. Este trabalho trata o problema de cobertura rotas com cardinalidade restrita (PCRCR), onde empresas que realizam viagens de carga cheia se unem com o objetivo de reduzir o deslocamento vazio de veículos através da formação de ciclos. É chamado de problema de cardinalidade restrita uma vez que limitamos o número de máximo de viagens no ciclo, o que torna este problema NP-Hard. Existem na literatura duas heurísticas (construtivas) e um modelo por programação linear inteira para a solução deste problema. Este trabalho apresenta uma heurística baseada em um método de busca local que reduziu em média 3,19% os melhores resultados apresentados na literatura. Também são apresentados os tempos de execução de cada um dos algoritmos e a importância de escolher de uma boa solução inicial quando se deseja implantar uma Heurística com Busca Local. / The growing need to seek more efficient, lower cost and more sustainable operations has caused industries to seek opportunities in which these objectives could be achieved. In the area of transportation, collaboration is an opportunity for that. This work deals with the cardinality constrained lane covering problem (CCLCP), where companies who uses full truck loads join efforts in order to reduce empty vehicle travel through closed cycle formation. It is known as cardinality constraint problem as the maximum number of trips in the cycle is limited to an integer number, which makes this problem NP-Hard. There are two heuristics in the literature (constructive) and an integer linear programming model for solving this problem. This work presents a heuristic based on a local search method that reduced an average of 3.19% the better results in the literature. It also presents the execution times of each algorithm and the importance of choosing a good initial solution when you want to create a Local Search Heuristic.

Tese de mestrado. Multimédia. Faculdade de Engenharia. Universidade do Porto. 2012

Tese de mestrado integrado. Engenharia Informática e Computação. Faculdade de Engenharia. Universidade do Porto. 2012

Publicación a texto completo no autorizada por el autor / Explica los problemas de balance en línea de producción en una fábrica de calzado. Se aplica la metaheurística búsqueda tabú, encontrados un modelo de distribución de trabajadores a las actividades de producción que logro mejorar la eficiencia en un 75%. Asimismo los reprocesos por fallas tuvieron una reducción del 8.21% obteniéndose con ello un ahorro para la empresa en estudio. Para la implementación de la búsqueda tabú se realizó un programa computacional en visual c++ 2008. / Tesis

Este trabalho trata do comportamento de jovens estudantes de uma escola da rede estadual paulista no que concerne as estratégias e heurísticas observáveis que praticam diante de determinados problemas lógico-matemáticos. Identifica algumas das heurísticas e estratégias clássicas que os educandos praticam e não praticam. A investigação se dá por meio de apresentação de problemas contextualizados que prescindem de conhecimentos matemáticos elaborados, a estudantes do último ano do ensino médio e análise dos processos de resolução deflagrados pelos estudantes na tentativa de resolver os problemas. Também é apresentado subsídio teórico e problemas adequados à reprodução parcial dessa investigação que podem interessar ao professor de matemática da educação básica ou ao pesquisador em resolução de problemas. Por fim, são problematizadas as informações observadas sobre o comportamento intelectual dos educandos no sentido de estabelecer hipóteses sobre as conquistas ou não dos educandos quanto à competência em resolução de problemas. / Este trabalho trata do comportamento de jovens estudantes de uma escola da rede estadual paulista no que concerne as estratégias e heurísticas observáveis que praticam diante de determinados problemas lógico-matemáticos. Identifica algumas das heurísticas e estratégias clássicas que os educandos praticam e não praticam. A investigação se dá por meio de apresentação de problemas contextualizados que prescindem de conhecimentos matemáticos elaborados, a estudantes do último ano do ensino médio e análise dos processos de resolução deflagrados pelos estudantes na tentativa de resolver os problemas. Também é apresentado subsídio teórico e problemas adequados à reprodução parcial dessa investigação que podem interessar ao professor de matemática da educação básica ou ao pesquisador em resolução de problemas. Por fim, são problematizadas as informações observadas sobre o comportamento intelectual dos educandos no sentido de estabelecer hipóteses sobre as conquistas ou não dos educandos quanto à competência em resolução de problemas.

Orientador: José Roberto Sanches Mantovani / Resumo: Neste trabalho é proposto o desenvolvimento de uma ferramenta computacional para o planeja-mento e despacho ótimo de fontes de potência ativa, considerando as incertezas das cargas (le-ve, nominal e pesada) e fontes de energia renováveis não despacháveis através de uma aborda-gem probabilística. O modelo matemático é um problema de programação não linear inteiro misto, multiobjetivo, não convexo e probabilístico na sua forma original sem a necessidade de realizar qualquer tipo de simplificação ou linearização tanto das funções objetivo como das res-trições. Um algoritmo baseado na meta-heurística Non-dominated Sorting Genetic Algorithm (NSGA-II) é proposto para resolver o problema de maneira eficaz. Os resultados obtidos com as simulações realizadas usando a implementação computacional nos sistemas de testes IEEE30 barras e IEEE118 barras mostram a eficiência e robustez da metodologia proposta. / Abstract: This work proposes the development of a computational tool for the planning and optimal dispatch of active power sources, considering the uncertainties of the loads (light, nominal and heavy) and non-dispatchable renewable energy sources through a probabilistic approach. The mathematical model is a multi-objective mixed-integer nonlinear programing problem, that is nonconvex and probabilistic in its original form, without the need to perform any kind of simplification or linearization of both objective functions and constraints. An algorithm based on the Non-dominated Sorting Genetic Algorithm (NSGA-II) meta-heuristic is pro-posed to solve the problem effectively. The results obtained with the simulations performed using the computational implementation in the IEEE30 bus and IEEE118 bus test systems show the efficiency and robustness of the proposed methodology. / Doutor

Esta dissertação propõe e implementa um método para decidir pela melhor alternativa de processar dados (documentos) digitados em computadores instalados em uma rede hierárquica, em que a configuração típica é um computador central e vários minicomputadores instalados em unidades regionais descentralizadas. As principais alternativas são: - realizar a consistência dos documentos de maneire mais centralizada ou distribuída; - realizar os processamentos das unidades regionais na unidade central, de forma seqüencial ou paralela; - transmitir um número maior ou menor de lotes de documentos das unidades regionais para a unidade central de processamento. O campo de soluções é, na realidade, uma função contínua, e por isso forma um vasto conjunto de alternativas, sendo que uma organização deve decidir-se por uma delas, tendo em vista os objetivos e recursos de que dispõe. Na prática, porém, esta escolha organizacional é condicionada por complexos procedimentos operacionais e inúmeros valores dentro do ambiente em que ocorre. Geralmente não é a melhor escolha, mas aquela que resulta da estratégia emergente, estruturada ao longo do tempo, de maneira informal, através de inúmeras intuições e experiências. Como resultado, esseprocesso é muitas vezes lento e complexo demais para ir sendo descoberto pelas poucas experiências que são realizadas na prática. Por isso, este estudo propõe e implementa um método de busca da solução final através de técnicas mais racionais e eficientes, tais como a de simulação e a de heurística. Os seus resultados são analisados e validados, dentro do contexto da administração de sistemas de entrada de dados. A automatização desse processo de escolha permite que uma organização tenha uma melhor compreensão do problema em si e oferece bases para a formação e formulação de políticas e estratégias na sua área de informática. / This dissertation proposes and implementa a method for choosing the best alternative to process data (documents) digitized in computers installed in a hierarchycal network, in which the typical configuration is a central computer and various microcomputers installed in decentralized regional units. The main alternatives are: - To accomplish the consistency of the documents in a more centralized or distributed manner; - To accomplish the processing of the regional units io the central unit, in a sequencial or parailel form; - To transmit a greater or smaller number of batches of documents from the regional units to the central unit of processing. The field of solutions is, in reality, a continuous function. So it forms a vast set of alternatives. An organization should decide for one of them, having in mind the objectives and resources available. In practice, however, this organizational choice is conditioned by complex operational procedures and numerous value judgernents within the environment where it occurs. Usually, it is not the best choice, but that one whic results from an emerging strategy, informally structured through time, and through many intuitiOns and experiments. As a result, this process is often too slow and complex to be discovered in few practical experiments. This study proposes and implements a method for searching the final solution, through more rational and efficient techniques, such as simulation and heuristics. The results are analised and validated, within the context of management of input data systems. The automation of this search process allows an organization to have a better understanding of the problem and offers a basis for policy and strategy formulation in the area of information processing.

El presente trabajo de título tuvo como objetivo diseñar y desarrollar el prototipo de un sistema de apoyo a las decisiones de ruteo marítimo para una empresa proveedora de alimento para salmones. Es posible esquematizar el trabajo enfrentado como un problema de ruteo de buques, con flota heterogénea, ventanas de tiempo suaves, restricciones de accesibilidad y precedencia, en el que además, en algunos casos, es necesario decidir la cantidad a entregar a cada cliente, sujeto a un porcentaje mínimo de su pedido original. Luego, el problema presenta características muy complejas por tratarse de una combinación de distintos problemas NP-hard. Por esta razón, y en consideración a los requerimientos de tiempo para encontrar una solución fijados por la empresa, se abordó el problema mediante un enfoque heurístico, implementando una versión de la heurística GRASP. Para el prototipo se desarrollaron interfaces con el usuario que permiten ingresar los datos de entrada, modificar el valor de los parámetros de la heurística, obtener soluciones, y evaluar modificaciones de manera amigable y expedita. Previamente, fue necesario definir la red que modela las operaciones de transporte marítimo de la empresa, proceso en el cual se desarrolló una metodología que permitió estimar las distancias entre los más de 200 centros de cultivo clientes, tomando en consideración las rutas de navegación efectivamente utilizadas entre ellos. Los resultados obtenidos al utilizar el prototipo con datos de las operaciones reales de la X región durante un horizonte de diez días, muestran una reducción de 7,30% en las millas náuticas recorridas por tonelada transportada. Adicionalmente, se logró un aumento considerable en la calidad de servicio prestado, disminuyendo la cantidad de pedidos programados para ser entregados atrasados en un 65% y eliminando los pedidos despachados incompletos. Por otra parte, la utilización de un horizonte rodante de tres días permitió anticipar las dificultades generadas por pedidos de centros lejanos o infectados por virus, logrando disminuir en un 20% la cantidad de días-barco utilizados para transportar la carga considerada en el horizonte de planificación, mediante una utilización más eficiente de los buques. Los tiempos de resolución para instancias regulares de operación no superaron los 10 minutos, alcanzando 5 minutos en promedio.

Nas últimas décadas, avanços em tecnologias de geração, coleta e armazenamento de dados têm contribuído para aumentar o tamanho dos bancos de dados nas diversas áreas de conhecimento humano. Este aumento verifica-se não somente em relação à quantidade de amostras de dados, mas principalmente em relação à quantidade de características descrevendo cada amostra. A adição de características causa acréscimo de dimensões no espaço matemático, conduzindo ao crescimento exponencial do hipervolume dos dados, problema denominado “maldição da dimensionalidade”. A maldição da dimensionalidade tem sido um problema rotineiro para cientistas que, a fim de compreender e explicar determinados fenômenos, têm se deparado com a necessidade de encontrar estruturas significativas ocultas, de baixa dimensão, dentro de dados de alta dimensão. Este processo denomina-se redução de dimensionalidade dos dados (RDD). Do ponto de vista computacional, a conseqüência natural da RDD é uma diminuição do espaço de busca de hipóteses, melhorando o desempenho e simplificando os resultados da modelagem de conhecimento em sistemas autônomos de aprendizado. Dentre as técnicas utilizadas atualmente em sistemas autônomos de aprendizado, as redes neurais artificiais (RNAs) têm se tornado particularmente atrativas para modelagem de sistemas complexos, principalmente quando a modelagem é difícil ou quando a dinâmica do sistema não permite o controle on-line. Apesar de serem uma poderosa técnica, as RNAs têm seu desempenho afetado pela maldição da dimensionalidade. Quando a dimensão do espaço de entradas é alta, as RNAs podem utilizar boa parte de seus recursos para representar porções irrelevantes do espaço de busca, dificultando o aprendizado. Embora as RNAs, assim como outras técnicas de aprendizado de máquina, consigam identificar características mais informativas para um processo de modelagem, a utilização de técnicas de RDD frequentemente melhora os resultados do processo de aprendizado. Este trabalho propõe um wrapper que implementa um modelo neural de aprimoramento progressivo para RDD em sistemas autônomos de aprendizado supervisionado visando otimizar o processo de modelagem. Para validar o modelo neural de aprimoramento progressivo, foram realizados experimentos com bancos de dados privados e de repositórios públicos de diferentes domínios de conhecimento. A capacidade de generalização dos modelos criados é avaliada por meio de técnicas de validação cruzada. Os resultados obtidos demonstram que o modelo neural de aprimoramento progressivo consegue identificar características mais informativas, permitindo a RDD, e tornando possível criar modelos mais simples e mais precisos. A implementação da abordagem e os experimentos foram realizados no ambiente Matlab, utilizando o toolbox de RNAs. / In recent decades, advances on data generation, collection and storing technologies have contributed to increase databases size in different knowledge areas. This increase is seen not only regarding samples amount, but mainly regarding dimensionality, i.e. the amount of features describing each sample. Features adding causes dimension increasing in mathematical space, leading to an exponential growth of data hypervolume. This problem is called “the curse of dimensionality”. The curse of dimensionality has been a routine problem for scientists, that in order to understand and explain some phenomena, have faced with the demand to find meaningful low dimensional structures hidden in high dimensional search spaces. This process is called data dimensionality reduction (DDR). From computational viewpoint, DDR natural consequence is a reduction of hypothesis search space, improving performance and simplifying the knowledge modeling results in autonomous learning systems. Among currently used techniques in autonomous learning systems, artificial neural networks (ANNs) have becoming particularly attractive to model complex systems, when modeling is hard or when system dynamics does not allow on-line control. Despite ANN being a powerful tool, their performance is affected by the curse of dimensionality. When input space dimension is high, ANNs can use a significant part of their resources to represent irrelevant parts of input space making learning process harder. Although ANNs, and other machine learning techniques, can identify more informative features for a modeling process, DDR techniques often improve learning results. This thesis proposes a wrapper which implements a Progressive Enhancement Neural Model to DDR in supervised autonomous learning systems in order to optimize the modeling process. To validate the proposed approach, experiments were performed with private and public databases, from different knowledge domains. The generalization ability of developed models is evaluated by means of cross validation techniques. Obtained results demonstrate that the proposed approach can identify more informative features, allowing DDR, and becoming possible to create simpler and more accurate models. The implementation of the proposed approach and related experiments were performed in Matlab Environment, using ANNs toolbox.