Neste trabalho é apresentada uma nova abordagem de algoritmo evolutivo multiobjetivo, denominado MOEA/NSM (do inglês, Multiobjective Evolutionary Algorithm integrating NSGA-II, SPEA2 and MOEA/D features). O algoritmo preserva em geral, características de um algoritmo evolutivo, concentrando qualidades de outras abordagens de sucesso na literatura em uma única abordagem, para que elas trabalhem em conjunto, por meio de subpopulações. O objetivo do estudo foi combinar as principais características dos algoritmos NSGA-II, SPEA2 e MOEA/D, e incluir ainda uma técnica de busca local para melhorar a busca no espaço de objetivos. O algoritmo MOEA/NSM foi comparado às demais abordagens clássicas utilizando 9 datasets para o problema do caixeiro viajante biobjetivo. Além disso, foram realizados experimentos aplicando também a busca local nas abordagens clássicas, resultando em considerável melhora nos resultados para esses algoritmos. A partir das fronteiras de Pareto resultantes dos experimentos, foram aplicadas as métricas de avaliação por Hipervolume, Epsilon (ε), R2, EAF, além do teste de hipótese estatístico Shapiro-Wilk. Os resultados apontaram um melhor desempenho do MOEA/NSM em relação aos demais, mesmo aplicando a busca local nas outras abordagens. Nesse sentido, o MOEA/NSM pode ser considerado um algoritmo que consegue encontrar soluções não denominadas de qualidade, tanto quanto os algoritmos clássicos da literatura. / This work presents a new approach to the multiobjective evolutionary algorithm, called MOEA/NSM (Multiobjective Evolutionary Algorithm integrating NSGA-II, SPEA2 and MOEA/D features). The algorithm preserves, in general, the characteristics of an evolutionary algorithm, concentrating qualities of other approaches of success in the literature in a single approach, so that they work together, through subpopulations. The objective of the study was to combine the main characteristics of the NSGA-II, SPEA2 and MOEA/D algorithms, and also to include a local search technique to improve the objective space search. The MOEA/NSM algorithm was compared to the other classical approaches using 9 datasets for the biobjective traveling salesman problem. In addition, experiments were carried out also applying the local search in the classical approaches, resulting in a considerable improvement in the results for these algorithms. From the Pareto frontiers resulting from experiments, we applied the evaluation metrics by Hypervolume, Epsilon (ε), R2, EAF, in addition to the Shapiro-Wilk statistical hypothesis test. The results showed a better performance of the MOEA/NSM in relation to the others, even applying the local search in the others approaches. In this sense, the MOEA/NSM can be considered an algorithm that is able to find solutions not dominated of quality, as much as the classic algorithms of the literature.

Cette thèse considère le problème consistant à intégrer les décisions de routage et stockage lors de la conception de la chaîne logistique. Le but est de sélectionner des dépôts parmi un ensemble de candidats pour desservir un ensemble de détaillants à l’aide d’une flotte de véhicules de capacité permettant visiter plus d’un détaillant par route. On cherche à déterminer la localisation de ces dépôts et les tournées des véhicules afin de maintenir leurs niveaux optimaux de stocks. La demande chez les détaillants est connue à l’avance. Des applications dans les domaines de la logistique humanitaire et militaire sont envisageables. Pour résoudre le problème, deux matheuristiques sont proposées. Dans la première partie, une méthode coopérative qui combine des méthodes exactes pour le problème de conception de la chaîne logistique et des méthodes heuristiques de routage est présentée. Dans la deuxième partie, une méthode de décomposition utilisant une réformulation de Dantzig-Wolf sur les variables de routage est proposée. L’algorithme intègre les concepts de génération de colonnes, relaxation lagrangienne et recherche locale. Les résultats montrent la capacité des algorithmes à trouver des solutions de bonne qualité et nous estimons de façon empirique l’impact de considérer un modèle intégré au lieu d’utiliser une méthode d’optimisation séquentielle. De plus, les résultats des méthodes présentées sur des sous-problèmes sont aussi étudiés. Ces sont: le problème de localisation-routage, le problème de tournées avec gestion de stocks, et le problème de plus court chemin généralisé / The problem of designing a supply chain including simultaneously routing and inventory management decisions is studied in this thesis. The objective is to select a subset of depots to open, the inventory policies for a 2-echelon system, and the set of routes to perform distribution from the upper echelon to the next using a homogeneous fleet of vehicles over a finite planning horizon. Demand is considered to be known. Applications are found in humanitarian logistics and military logistics. To solve the problem, two matheuristic procedures are developed. On the first part a cooperative algorithm combining exact methods for the supply chain design problem and routing heuristics is presented. On the second part, a partition is proposed using a Dantzig-Wolf reformulation on the routing variables. An hybridization between column generation, Lagrangian relaxation and local search is proposed in this part, put together as a heuristic method. Furthermore, results demonstrate the capability of the algorithms to compute high quality solutions and empirically estimate the improvement in the cost function of the proposed model when compared to a sequential optimization approach. Furthermore, results of the proposed methodologies on benchmark instances for subproblems are studied as well. Those are the capacitated location-routing problem, the inventory-routing problem, and the generalized elementary shortest path problem

Les travaux de cette thèse concernent la résolution d'un problème de planification dans un réseau de distribution à deux échelons intégrant la gestion de stocks de produits périssables, le dimensionnement de lots, des alternatives d'approvisionnement. La livraison s'effectue directement entre un fournisseur et son client, sans tournée avec une flotte homogène de véhicules. Nous proposons un programme linéaire mixte, une heuristique constructive (déterministe) et une heuristique réactive randomisée. Pour certaines instances, le solveur de programme linéaire mixte ne fournit pas une bonne solution réalisable dans la limite de temps définie ou prend beaucoup de temps. Les heuristiques proposées sont rapides mais ne donnent pas de bonnes solutions pour certaines instances. Pour améliorer la qualité des solutions des heuristiques, la descente à voisinage variable (VND), la recherche locale itérative (ILS) et la recherche locale itérative à démarrages multiples (MS-ILS) sont développées.Toutes ces méthodes ont été incluses dans un APS (Advanced Planning System) et sont comparées avec CPLEX sur des instances extraites de bases de données réelles. Un générateur aléatoire d'instances est conçu pour plus de diversité pour les tests. Une relaxation lagrangienne est implémentée pour comparer les solutions des instances, pour lesquelles CPLEX ne fournit pas une bonne solution réalisable dans le temps imparti, avec les autres méthodes. Une heuristique lagrangienne, utilisant la relaxation lagrangienne et une heuristique de réparation, est également développée / This work presents a planning problem in a distribution network incorporating two levels inventory management of perishable products, lot-sizing, multi-sourcing and transport capacity with a homogeneous fleet of vehicles. A mixed integer linear programming (MILP) a greedy heuristic and a reactive randomized heuristic are developed to solve this real planning problem. There are some instances for which the solver CPLEX cannot give a good upper bound within the limited time and for other instances it takes a lot of time to solve MILP. The heuristics are alternatives to the mixed integer linear program to quickly solve some large instances taking into account original and difficult constraints. For some instances the gap between the solutions of the solver (MILP) and the heuristics becomes quite significant. The variable neighborhood descent (VND), the iterated local search (ILS) and the multi-start iterated local search (MS-ILS) are implemented. These methods are included in an APS (Advanced Planning System) and compared with a MILP solver. The instances are derived from actual data or built using a random generator of instances to have wider diversity for computational evaluation. A lagrangian relaxation is developed to compare the solutions of the instances, for which CPLEX cannot give a good upper bound within the limited time, with the other methods (greedy heuristic, VND, ILS and MS-ILS). A lagrangian heuristic is proposed; the solution of lagrangian relaxation is used to build a feasible solution with a repair heuristic

[pt] Construção de vocabulário é uma heurística para problemas de otimização combinatória que propõe identificar porções de boas soluções e recombiná-las de modo a intensificar a busca em regiões do espaço de soluções identificadas como promissoras. A técnica de construção de vocabulário pode ser aplicada de diversas maneiras na resolução de problemas. Para facilitar a implementação e comparação de algoritmos de um mesmo domínio, a tecnologia de frameworks é uma solução que já demonstrou ser muito eficaz. O objetivo deste trabalho é desenvolver um framework para a implementação de heurísticas baseadas em construçao de vocabulário. O desenvolvimento foi fundamentado em extensa revisão bibliográfica sobre a técnica e em boas práticas de engenharia de software, como frameworks orientados a objetos e padrões de projeto. Como um estudo de caso, foram geradas aplicações a partir do framework para a resolução do problema de seqüenciamento da produção de carros, que é um problema combinatório proposto a partir de necessidades reais da indústria / [en] Vocabulary building is a heuristic for solving combinatorial optimization problems, based on the identification of solution fragments which are common to good solutions and on their combination to intensify the search on promising regions of the solution space. This technique can be vastly applied on problem solving. The technology of frameworks is an efficient strategy to facilitate the implementation and comparison of same domain algorithms. The objective of this work is to develop a framework for the implementation of heuristics based on vocabulary building. Its development was based on a wide bibliographic revision about the technique and good software engineering practices, like oriented objects frameworks and design patters. We generated applications of the framework to solve the car sequencing problem, which is a combinatorial problem proposed by real requirements of the industry

Made available in DSpace on 2016-12-23T13:51:54Z (GMT). No. of bitstreams: 1 Cristiane Coutinho Meneguzzi.pdf: 2106158 bytes, checksum: 65c537220893be6e9c9d64b3001fef07 (MD5) Previous issue date: 2011-10-04 / On Forest field, studies in development of forest harvesting and transport still being the most emphasized subject, for being directly responsible for the final cost of wood. However, other different phases are a big potential for studies, as Forest Inventory. Information provided by the Forest Inventory are important for all planning of Forest Enterprise, as it bases any decision making involving forest resources. On this present research, was based on vehicle routing problem for planning this task. The vehicle routing problem and its variants has being largely studied on the last years, mainly for its applicability and efficiency for given solutions resulting in cost and distance reduction. The general objective of the present study is optimize the Inventory Forest planning from a vehicle routing problem and evaluate the importance of this technique on its productivity. Among the factors that influence this productivity, the spatial dispersion , basic feature of forest stands, it is one controllable factor from the use of technique that makes possible matches with planning. Studies shows that this match brings out significant results / Na área florestal, ainda é dada maior ênfase ao desenvolvimento de estudos envolvendo as etapas de colheita e transporte florestal, por serem diretamente responsáveis pelo custo final da madeira. Entretanto, diversas outras etapas possuem grande potencial para estudos, como é o caso do inventário florestal. Informações fornecidas pelo inventário florestal são importantes no planejamento de todo empreendimento florestal, pois subsidiam qualquer tomada de decisão envolvendo recursos florestais. Nesta pesquisa, utilizou-se o modelo de roteamento de veículos (PRV) no planejamento dessa atividade. O PRV e suas variantes vêm sendo amplamente estudados nos últimos anos, principalmente pela sua aplicabilidade e eficiência em gerar soluções apresentando redução de custo e/ou distâncias. O objetivo geral foi otimizar o planejamento da atividade de inventário florestal a partir de um modelo PRV e avaliar a importância do uso desta técnica no rendimento das atividades. Dentre os fatores que influenciam neste rendimento, a dispersão espacial, característica básica dos povoamentos florestais, é um fator controlável a partir do uso de técnicas que possibilitem associá-lo ao planejamento. Estudos mostram que essa associação traz resultados significativos

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Com o passar do tempo, a demanda elétrica de diversas áreas varia tornando necessária a construção de novos geradores elétricos e a expansão da rede de transmissão de energia elétrica. Nesta dissertação, focamos no problema de expansão da rede de transmissão, assumindo que novos geradores estão construídos para suprir as novas demandas. Essa expansão exige altos investimentos que precisam ser cuidadosamente planejados. O problema pode ser modelado como um problema de otimização não linear inteira mista e pertence à classe dos problemas NP-difíceis. Desta forma, uma abordagem heurística pode ser adequada para a sua solução pois pode vir a fornecer boas soluções em tempo computacional aceitável. Esta dissertação se propõe a apresentar um estudo do problema de planejamento da expansão de redes de transmissão de energia elétrica estático e multiestágio. Mostramos o que já existe na literatura para o que é chamado de problema sem redimensionamento e as inovações feitas por nós para o problema com redimensionamento. Quanto aos métodos de solução, utilizamos a metaheurística GRASP para o problema estático e combinamos o GRASP com o procedimento Backward-Forward quando falamos em problema multiestágio. Nesta dissertação comparamos os resultados computacionais obtidos com resultados encontrados na literatura. / At times, the electrical load in diferent areas varies, claiming the construction of new electric generators and the expansion of the electrical transmission network. In this dissertation we focus on the transmission expansion planning problem, assuming that new generators are built to meet the new demands. This expansion requires large investments, which need to be carefully planned. This problem can be modeled as a mixed nonlinear programming problem, considered to be a NP-hard problem. Therefore a heuristic approach may be appropriate for its solution because it might be able to provide good solutions in satisfactory computational time. This dissertation intends to present a study of both the static and multistage transmission expansion planning problem. We present first a review of the most interesting works found in the technical literature. Then, we present metaheuristics for the static and multistage problems with re-design. These etaheuristics extend known algorithms for the problems without re-design. For the static problem, we extend a GRASP procedure and for the multistage problem, we embed the GRASP (or an exact method) into a backward-forward algorithm. We test our algorithms on real-based power transmission networks and compare them to the results found in the litterature.

The work proposed in this dissertation is the field of combinatorial optimization, which aims to find a solution to these types of problems at a low computational time and effectively. The combinatorial optimization studies a set of discrete solutions, which have a finite number of elements, to find the best viable solution to the problems of this magnitude. One of the main approaches that area is the Traveling Salesman Problem (TSP), mainly due to the size of possible solutions to the problem, so that is intractable computation by exhaustive search methods. Given all these features, this work is to study and develop evolutionary strategies for the resolution of the Problem of Traveling Salesman with Heterogeneous Demands (TSPHD), a variation of the classic TSP. The evolutionary strategies belong to the class of evolutionary computation, and methods of search based on the theory of the evolution of species, where the best individuals compete for survival. The evolutionary strategies differ from other optimization techniques, as the search is conducted in a population of solutions, not a single point. To solve the problem are proposed four evolutionary algorithms, using heuristics techniques and metaheurísticas for its implementation. The results were obtained from tests using instances of low density (low connection), and compared with the exact solution (optimal solution) and other progressive methods in the literature. These results are evaluated on the basis of their quality and time for its implementation. / O trabalho proposto nessa dissertação pertence à área de otimização combinatória, a qual visa encontrar uma solução para esses tipos de problema em um tempo computacional baixo e de forma eficaz. A otimização combinatória estuda um conjunto discreto de soluções, os quais possuem um número finito de elementos, para se poder encontrar a melhor solução viável para os problemas dessa grandeza. Uma das principais abordagens dessa área é o Problema do Caixeiro Viajante (PCV), principalmente devido à dimensão de possíveis soluções para o problema, fazendo com que seja intratável computacionalmente por métodos de buscas exaustivas. Face a todas essas características, este trabalho tem por objetivo estudar e desenvolver estratégias evolutivas para a resolução do Problema do Caixeiro Viajante com Demandas Heterogêneas (PCVDH), uma variação do PCV clássico. As estratégias evolutivas pertencem à classe da computação evolutiva, sendo métodos de busca inspirados na teoria da evolução das espécies, onde os melhores indivíduos competem pela sobrevivência. As estratégias evolutivas diferem das demais técnicas de otimização, pois a busca é realizada em uma população de soluções, não em um único ponto. Para a resolução do problema são propostos quatro algoritmos evolutivos, utilizando técnicas heurísticas e metaheurísticas para sua aplicação. Os resultados foram obtidos com testes utilizando instâncias de baixa densidade (baixa conexão), e comparados com a sua solução exata (solução ótima) e com outros métodos evolutivos encontrados na literatura. Esses resultados são avaliados com base na sua qualidade e tempo decorrido para sua execução.

Made available in DSpace on 2016-06-02T19:51:37Z (GMT). No. of bitstreams: 1 2212.pdf: 1886443 bytes, checksum: bddd5428751623f23f36b7a2f2f3442c (MD5) Previous issue date: 2008-12-15 / Universidade Federal de Minas Gerais / In recent years, several studies have been revising static distribution models used by companies in order to incorporate intrinsic dynamic features of transport operations. Thanks to new technologies such as global positioning systems and wireless communications, vehicle routes elaborated in the beginning of the planning horizon can be altered in real time in order to serve new requests, avoid traffic jams, or find alternatives when some of the fleet vehicles are late or broke. In this way, realistic solutions of better quality are expected to be obtained from the company´s point of view (smaller costs) as well as from the customers´ (better service level). The main objective of this work is to analyze the impacts resulting from the incorporation of dynamic vehicle routing and scheduling in service production systems where the due dates for service is a prioritary issue. Specifically, we tackled the Dynamic Vehicle Routing Problem, where route plans are elaborated in a planning horizon. Initially, the definition and characteristics of dynamic problems are presented along with a review of some of the main contributions in the literature. We propose a heuristic based on Pureza and Laporte´s algorithm (2008) in order to obtain routes in real time. The relative impact of the heuristic application to other methods is analyzed by means of a set of generated instances from the data supplied by a drink company in São Paulo State. / Nos últimos anos, um crescente número de estudos científicos vem revisando modelos estáticos de distribuição adotados por empresas a fim de incorporar o dinamismo intrínseco às operações envolvidas. Esta tendência se deve principalmente aos avanços tecnológicos na área de geo-referenciamento, os quais permitem que rotas elaboradas no início do horizonte de planejamento sejam alteradas em tempo real a fim de atender novas requisições de clientes, evitar congestionamentos de tráfego, ou ainda, encontrar alternativas na ocorrência de veículos atrasados ou quebrados. Desta forma, espera-se obter soluções realistas de maior qualidade tanto do ponto de vista da empresa (menores custos) como dos clientes (melhor nível de serviço). Este trabalho tem como objetivo principal analisar o impacto decorrente da incorporação de métodos de roteamento dinâmico de veículos em ambientes de prestação de serviço onde o prazo de atendimento é o objetivo prioritário. Especificamente, é tratado o Problema de Roteamento de Veículos Dinâmico, onde planos de rotas são elaborados ao longo de um horizonte de planejamento. Inicialmente, a definição e características de problemas dinâmicos são apresentadas, juntamente com uma revisão de algumas das principais contribuições da literatura. É proposta, então, uma heurística baseada no algoritmo de Pureza e Laporte (2008) para elaboração de rotas em tempo real. O impacto da aplicação da heurística é analisado frente a outros métodos, utilizando-se um conjunto de instâncias geradas a partir de dados fornecidos por uma empresa do setor de bebidas do interior do estado de São Paulo.

Made available in DSpace on 2016-06-02T19:52:13Z (GMT). No. of bitstreams: 1 DissJMRB.pdf: 944400 bytes, checksum: b37a0f175baab577681e6785f305edee (MD5) Previous issue date: 2005-06-23 / This project consists in the refinement of the tabu search adaptive approach HTSA (PUREZA, 1996) and the analysis of its performance when applied to the classical Vehicle Routing Problem and to the Vehicle Routing Problem with Time Windows. HTSA promotes the integration of intensification and diversification strategies through the systematic variation of the values of selected tabu parameters, mostly based on the analysis of search trajectory patterns. The development of new implementations based on tabu search (GLOVER, 1989; GLOVER & LAGUNA, 1997) is an interesting avenue of research since tabu search has offered new marks on solution quality in routing problems, usually outperforming other methods. The results obtained with the application of HTSA approach to a set of classical routing instances and to a set of routing with times windows instances indicate quality solutions within reasonable computational times when compared to the results provided by competitive methods in the literature. / O corrente projeto tem como objetivo o refinamento da abordagem adaptativa de busca tabu HTSA (PUREZA, 1996) e a verificação de seu desempenho quando aplicada ao Problema de Roteirização de Veículos clássico e ao Problema de Roteirização com Janelas de Tempo. A abordagem HTSA tem como objetivo a integração de estratégias de intensificação e diversificação, consistindo na variação sistemática de valores de parâmetros tabu selecionados e apoiada principalmente na análise de padrões da trajetória da busca. O desenvolvimento de novas abordagens baseadas na meta-heurística busca tabu (GLOVER, 1989; GLOVER & LAGUNA, 1997) é uma linha de pesquisa interessante uma vez que a busca tabu tem oferecido novas marcas em qualidade da solução em problemas de Roteirização de veículos e suas variantes, geralmente superando outros métodos. Os resultados obtidos com a aplicação da abordagem HTSA a instâncias de roteirização de veículos clássicas e com janela de tempo indicam soluções de qualidade em tempos computacionais razoáveis quando comparadas aos resultados de métodos competitivos da literatura.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Com o passar do tempo, a demanda elétrica de diversas áreas varia tornando necessária a construção de novos geradores elétricos e a expansão da rede de transmissão de energia elétrica. Nesta dissertação, focamos no problema de expansão da rede de transmissão, assumindo que novos geradores estão construídos para suprir as novas demandas. Essa expansão exige altos investimentos que precisam ser cuidadosamente planejados. O problema pode ser modelado como um problema de otimização não linear inteira mista e pertence à classe dos problemas NP-difíceis. Desta forma, uma abordagem heurística pode ser adequada para a sua solução pois pode vir a fornecer boas soluções em tempo computacional aceitável. Esta dissertação se propõe a apresentar um estudo do problema de planejamento da expansão de redes de transmissão de energia elétrica estático e multiestágio. Mostramos o que já existe na literatura para o que é chamado de problema sem redimensionamento e as inovações feitas por nós para o problema com redimensionamento. Quanto aos métodos de solução, utilizamos a metaheurística GRASP para o problema estático e combinamos o GRASP com o procedimento Backward-Forward quando falamos em problema multiestágio. Nesta dissertação comparamos os resultados computacionais obtidos com resultados encontrados na literatura. / At times, the electrical load in diferent areas varies, claiming the construction of new electric generators and the expansion of the electrical transmission network. In this dissertation we focus on the transmission expansion planning problem, assuming that new generators are built to meet the new demands. This expansion requires large investments, which need to be carefully planned. This problem can be modeled as a mixed nonlinear programming problem, considered to be a NP-hard problem. Therefore a heuristic approach may be appropriate for its solution because it might be able to provide good solutions in satisfactory computational time. This dissertation intends to present a study of both the static and multistage transmission expansion planning problem. We present first a review of the most interesting works found in the technical literature. Then, we present metaheuristics for the static and multistage problems with re-design. These etaheuristics extend known algorithms for the problems without re-design. For the static problem, we extend a GRASP procedure and for the multistage problem, we embed the GRASP (or an exact method) into a backward-forward algorithm. We test our algorithms on real-based power transmission networks and compare them to the results found in the litterature.