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.

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.

Orientador: Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-06T12:59:52Z (GMT). No. of bitstreams: 1 Sousa_VaniaNobrede_M.pdf: 984501 bytes, checksum: f58d5baf5c8e4dc8e704f4cb9aa47c6b (MD5) Previous issue date: 2006 / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T12:28:53Z (GMT). No. of bitstreams: 1 Lopes_MauroCardoso_M.pdf: 3797752 bytes, checksum: c82bee131ad99d747e42150908135190 (MD5) Previous issue date: 2014 / Resumo: Investigamos uma variante do problema de localização e roteamento com relação de muitos-para-muitos concentradores que consiste em particionar o conjunto de vértices de um grafo em ciclos contendo exatamente um concentrador cada e determinar um ciclo adicional interligando todos os concentradores. Qualquer vértice do grafo pode ser um concentrador; faz parte do problema determinar quais vértices devem ser concentradores. Esse problema tem aplicações práticas relevantes em áreas como transporte urbano e redes de computadores. Desenvolvemos uma heurística baseada em busca local com operações de inserção, remoção e troca de vértices. Soluções iniciais são geradas de maneira aleatória, e suas vizinhanças são exploradas a fim de obter melhores soluções. Além disso, elaboramos um algoritmo exato com estrutura de branch-and-cut para a formulação em Programação Linear Inteira proposta. Restrições de capacidade e eliminação de caminhos são adicionadas como planos de corte, com algoritmos de separação baseados em árvores de corte mínimo e nas componentes conexas de um grafo suporte. Diversos experimentos computacionais mostram a capacidade de resolução do algoritmo exato para instâncias pequenas e da heurística para instâncias pequenas e médias. São comparados também os desempenhos para outras variantes do problema / Abstract: We investigate a variant of the many-to-many hub location-routing problem which consists in partitioning the set of vertices of a graph into cycles containing exactly one hub each and determining an extra cycle interconnecting all hubs. Any vertex of the graph can be a hub; it is part of the problem to determine which vertices should be hubs. This problem has relevant practical applications in areas such as urban transportation and computer networks. A local search based heuristic that considers add/remove and swap operations is developed. Initial solutions can be generated at random, and their neighborhoods are explored in order to get better solutions. Also a branch-and-cut approach that solves an integer formulation is investigated. Capacity and path elimination constraints are added in a cutting plane way, so the separation algorithms are based on the computation of min-cut trees and in the connected components of a support graph. Many computational experiments over several instances adapted from literature show the problem-solving capability of the exact algorithm for small instances and of the heuristic for small to medium-sized instances. We also compare the performance of other variants of the problem / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Spanning tree optimization problems are related to many practical applications. Several of these problems are NP-Hard, which limits the utility of exact methods and can require alternative approaches, like metaheuristics. A common issue for many metaheuristics is the data structure used to represent and manipulate the solutions. A data structure with efficient operations can expand the usefulness of a method by allowing larger instances to be solved in a reasonable amount of time. We propose the 2LETT data structure and uses it to represent spanning trees in two metaheuristics: mutation-based evolutionary algorithms and local search algorithms. The main operation of 2LETT is the exchange of one edge in the represented tree by another one, and it has O(√n) time, where n is the number of vertices in the tree. We conducent qualitative and quantitative evaluations for 2LETT and other structures in the literature. For the main operation of edge exchange in evolutionary algorithms, the computational experiments show that 2LETT has the best performance for trees with more than 10,000 vertices. For local search algorithms, 2LETT is the best option to deal with large trees with large diameters. / Os problemas de otimização de árvores geradoras estão relacionados a muitas aplicações práticas. Vários desses problemas são NP-difícies, o que limita a utilidade de métodos exatos e pode exigir abordagens alternativas, como metaheurísticas. Um questão relevante para muitas metaheurísticas é a estrutura de dados usada para representar e manipular as soluções. Uma estrutura de dados com operações eficientes pode aumentar a utilidade de um método, permitindo que instâncias maiores sejam resolvidas em um período de tempo razoável. Propomos a estrutura de dados 2LETT e a usamos para representar árvores geradoras em duas metaheurísticas: algoritmos evolutivos baseados em mutações e algoritmos de busca local. A operação principal da 2LETT é a troca de uma aresta na árvore representada por outra aresta. Esta operação tem tempo de O(√n), onde n é o número de vértices na árvore. Conduzimos avaliações qualitativas e quantitativas para 2LETT e outras estruturas na literatura. Para a principal operação de troca de arestas em algoritmos evolutivos, os experimentos computacionais mostram que a 2LETT possui o melhor desempenho para árvores com mais de 10.000 vértices. Para algoritmos de busca local, o 2LETT é a melhor opção para lidar com árvores grandes com grandes diâmetros.

O trabalho a seguir apresenta o desenvolvimento e resultados da pesquisa acerca de modelos de estoques para múltiplos fornecedores, baseado na distribuição de peças de manutenção de empresas de tecnologia no Brasil. Em função de características de demandas erráticas, altos custos das peças e demanda por tempos de entrega reduzidos, costuma-se adotar uma estratégia de distribuir peças em diversos centros de estoques por todo território nacional. Entretanto, manter altos estoques em cada uma das localidades do sistema pode trazer custos elevados. Devido às características da demanda, muitas vezes ocorrem faltas de estoques de itens críticos, que são enviados aos locais de demanda por meio de transportes emergenciais de alto custo e prazos de entregas reduzidos. Entretanto, os modelos convencionais de estoques adotados, não consideram as possibilidades de envios emergenciais em suas formulações, fazendo desta solução uma situação não prevista na modelagem e potencialmente não ótima. A presente pesquisa tem por objetivo desenvolver e avaliar os modelos convencionais de estoques para a situação de múltiplos fornecedores considerando custos e prazos de entregas diferentes, como alternativa para os modelos adotados na distribuição de peças de manutenção. Sua aplicação a outros problemas, inclusive ambientes de múltiplos fornecedores independentemente de diferenças de transportes é imediata. A pesquisa abrange sete modelos, sendo três modelos reativos (reposição da base, reposição do máximo e lote fixo) em regimes de revisão periódica e contínua, e um modelo ativo considerando previsão de demanda. Foi utilizada busca local com simulação de eventos discretos para resolver os modelos propostos. / The present work presents research and development of multiple supplier inventory models, based on the service parts logistics in the technology industry. Because of the lumpy demand characteristics, high costs of parts and low delivery time expectations, a strategy to spread parts inventories all over the country was adopted. However, maintaining high inventory in every location of the system can lead to high costs. Because of the demand characteristics critical items can get unavailable in certain location, which are supplied by emergency shipment from supplying locations with high transportation costs and reduced delivery times. However, the conventional inventory models that are used do not consider the possibility of emergency shipments, leading to potential non optimal distribution of parts. The present research aims to develop and evaluate the inventory models considering multiple transportation modals with different lead times and costs, to serve as an alternative to the current inventory models used. The application to other problems, including different suppliers independent of transportation mode, is immediate. The research covers seven different models: three reactive, (s, S), (S-1, S) and (R, Q) in continuous and periodic review, and one demand prediction based model. Local search and discrete events simulation was used to resolve the models.

[pt] Em vários problemas de distribuição e logística, os produtos devem ser coletados em uma origem e entregues em um destino. Exemplos incluem o transporte de pessoas com deficiência, serviços de correio expresso, logística de suprimentos médicos, etc. O problema de roteamento abordado neste trabalho, conhecido como Traveling Salesman Problem with Pickup and Delivery (TSPPD), é da classe de problemas do caixeiro viajante com restrições de precedência. Neste problema, existe um mapeamento um-para-um entre coleta-entrega no qual cada cliente do tipo coleta possui um cliente do tipo entrega associado. Os clientes do tipo entrega somente podem ser visitados posteriormente à coleta associada. O TSPPD é um problema NP-difícil uma vez que generaliza o Traveling Salesman Problem (TSP). O TSP pode ser visto como um caso particular do TSPPD onde cada coleta coincide espacialmente com a respectiva entrega. As variantes com restrições de capacidade, janelas de tempo e diferentes políticas de carregamento têm recebido maior atenção na última década, embora ainda existam significantes avanços a serem realizados em termos de qualidades de soluções na versão básica do problema. Para resolver este problema, propomos um algoritmo meta-heurístico híbrido com vizinhanças largas exploradas eficientemente em O(n2). Nossos experimentos demonstram uma redução significativa no tempo computacional e também melhoria na qualidade de soluções previamente conhecidas na literatura. / [en] In various distribution and logistics issues, products must be collected at one source and delivered to a destination. Examples include disabled people transportation, express mail services, medical supplies logistics, etc. The routing problem addressed by this work, known as Traveling Salesman Problem with Pickup and Delivery (TSPPD), belongs to the class of traveling salesman problems with precedence constraints. In this problem, there is a one-to-one pickup-delivery mapping in which, for each pickuptype client, there is exactly one associated delivery-type client. Delivery clients can only be visited after the associated pickup. Since the TSPPD generalizes the TSP it is also a NP-hard problem, as the TSP is a particular casa of TSPPD where each pickup matches spatially with it s respective delivery. Variants with capacity constraints, time windows and different loading policies have received more attention in the last decade, although there are still significant advances to be made in terms of solution quality for the basic version of the problem. To solve this problem, we propose a hybrid metaheuristic algorithm with large neighborhoods efficiently explored in O(n2). Our experiments demonstrate a significant computational time reduction and also solutions quality improvement compared to the previous works.

Submitted by NATALIA PATINO CARDONA null (npatcar@gmail.com) on 2016-03-15T18:03:52Z No. of bitstreams: 1 Natalia_Patino_Cardona.pdf: 3586616 bytes, checksum: 280eb15150f150a3d1e6d5b25ffb2c20 (MD5) / Approved for entry into archive by Sandra Manzano de Almeida (smanzano@marilia.unesp.br) on 2016-03-15T18:17:50Z (GMT) No. of bitstreams: 1 cardona_np_me_ilha.pdf: 3586616 bytes, checksum: 280eb15150f150a3d1e6d5b25ffb2c20 (MD5) / Made available in DSpace on 2016-03-15T18:17:50Z (GMT). No. of bitstreams: 1 cardona_np_me_ilha.pdf: 3586616 bytes, checksum: 280eb15150f150a3d1e6d5b25ffb2c20 (MD5) Previous issue date: 2016-02-16 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Este trabalho apresenta uma proposta baseada na metodologia multipartida para a resolução do Problema de Reconfiguração de Sistemas de Distribuição de Energia Elétrica, de natureza combinatória e modelado como um problema de Programação Não Linear Inteiro Misto. O objetivo principal deste trabalho é encontrar a topologia radial ótima para minimizar as perdas ativas dos sistemas de distribuição, e para isso é preciso, primeiramente, a resolução de um problema de fluxo de potência para sistemas fracamente malhados onde é calculada a potência aparente do sistema, a qual vai ser utilizada pelo algoritmo de Prim como o peso para a geração das soluções iniciais radiais de boa qualidade. Para implementar a metodologia proposta deve-se desenvolver também um algoritmo de fluxo de potência radial, utilizado para calcular tanto as perdas ativas do sistema (função objetivo do problema), como para verificar a factibilidade das propostas de solução. Nesta primeira etapa é feita uma variação aleatória dos pesos dos ramos, e são resolvidos tantos problemas de fluxo de potência radial quanto soluções aleatórias obtidas, para encontrar soluções de boa qualidade próximas ao ótimo. Finalmente, é feita uma busca local através da troca de ramos como tentativa para encontrar a solução ótima. As soluções obtidas pela metodologia proposta são obtidas através da programação de algoritmos implementados em linguagem C++. Os resultados obtidos mostram a eficiência da aplicação da metodologia, estes resultados foram comparados com os existentes na literatura e os obtidos pela resolução de um modelo de otimização resolvido com o solver comercial CPLEX. / This work presents a proposal based on multi-start methodology for the solution of the distribution network reconfiguration problem, of combinatorial nature and modeled as a mixed-integer nonlinear programming problem. The main objective of this work is to find the optimal radial topology to minimize active power losses in distribution systems. This requires, at first, the resolution of a power flow problem for weakly meshed systems where the apparent power of the system is calculated, which will be used by the Prim algorithm as the weight for generating the radial initial good quality solution. To implement the proposed methodology is also developed a radial power flow algorithm, used to calculate both the active system losses (objective function of the problem) and to verify the feasibility of the proposed solutions. In this first stage is made a random variation of the weights of branches, and there are solved as many radial power flows as random solutions obtained, to find good quality solutions close to optimal. Finally, a local search is made by doing an exchange of branches as an attempt to find the optimal solution. The solutions obtained by the proposed method are acquired by programming algorithms implemented in C ++ language. The results show the effectiveness of the application of the methodology. These results were compared with those in the literature and those obtained by solving an optimization model solved by the commercial solver CPLEX.

Made available in DSpace on 2016-06-02T19:53:31Z (GMT). No. of bitstreams: 1 LUGO_Pedro_2013.pdf: 2147400 bytes, checksum: a0c7948826b7f243c447b99fd96c3388 (MD5) Previous issue date: 2013-09-12 / Financiadora de Estudos e Projetos / This research studies the hybrid flowshop scheduling problem. In this production configuration, we have a set of jobs that has to be processed in a set of stages. At every stage we have a set of parallel machines available to process the jobs. All jobs have to be processed following the same production flow, from the first to the last stage. Every job has to be processed on one machine at each stage and each machine can process at most one job at a time. Some constraints commonly found in real production systems as unrelated parallel machines, limited buffers, sequence-dependent setup times (both anticipatory and non-anticipatory), machine eligibility, transportation times and release times for machines are also taken into account. The optimization criterion is the makespan, whose minimization is related to the efficient use of production resources. A mixed integer programming model is proposed and solved by the commercial solver CPLEX. The computational evaluation results indicate that the model is suitable just to solve instances up to nine jobs and five stages. Therefore, to solve larger instances (50-100 jobs), several heuristics and an iterated local search (ILS) algorithm are proposed and evaluated computationally. The results indicate that the ILS is able to obtain good quality solutions in short computation times. / Este trabalho estuda o problema de programação da produção em sistemas Flowshop híbrido. Nesta configuração de produção há um conjunto de tarefas que deve ser processado em um conjunto de estações, nas quais um determinado número de máquinas paralelas encontra-se disponível para o processamento das tarefas. Todas as tarefas devem ser processadas seguindo o mesmo fluxo de produção, desde a primeira até a última estação. Cada tarefa deve ser processada em uma máquina de cada estação e cada máquina pode processar, no máximo, uma tarefa por vez. Algumas restrições comumente encontradas em sistemas de produção reais, como máquinas paralelas não relacionadas, buffers limitados, tempos de preparação dependentes da sequência (antecipatórios e não antecipatórios), elegibilidade de máquinas, tempos de transporte e tempos de liberação das máquinas, também são consideradas. O critério de otimização é o makespan, cuja minimização está diretamente relacionada com a utilização eficiente dos recursos de produção. Um modelo de programação inteira mista é proposto e resolvido através do solver comercial CPLEX. Os resultados da avaliação computacional indicam que o modelo é viável somente para resolver instâncias de até nove tarefas e cinco estações. Desta forma, para resolver instâncias de maior tamanho (50-100 tarefas), várias heurísticas e uma meta-heurística de busca local iterada (ILS, Iterated Local Search) são propostas e avaliadas computacionalmente. Os resultados indicam que o ILS é capaz de obter soluções de boa qualidade em curtos tempos computacionais.

Orientador: Rubén Augusto Romero Lázaro / Resumo: Este trabalho apresenta uma proposta baseada na metodologia multipartida para a resolução do Problema de Reconfiguração de Sistemas de Distribuição de Energia Elétrica, de natureza combinatória e modelado como um problema de Programação Não Linear Inteiro Misto. O objetivo principal deste trabalho é encontrar a topologia radial ótima para minimizar as perdas ativas dos sistemas de distribuição, e para isso é preciso, primeiramente, a resolução de um problema de fluxo de potência para sistemas fracamente malhados onde é calculada a potência aparente do sistema, a qual vai ser utilizada pelo algoritmo de Prim como o peso para a geração das soluções iniciais radiais de boa qualidade. Para implementar a metodologia proposta deve-se desenvolver também um algoritmo de fluxo de potência radial, utilizado para calcular tanto as perdas ativas do sistema (função objetivo do problema), como para verificar a factibilidade das propostas de solução. Nesta primeira etapa é feita uma variação aleatória dos pesos dos ramos, e são resolvidos tantos problemas de fluxo de potência radial quanto soluções aleatórias obtidas, para encontrar soluções de boa qualidade próximas ao ótimo. Finalmente, é feita uma busca local através da troca de ramos como tentativa para encontrar a solução ótima. As soluções obtidas pela metodologia proposta são obtidas através da programação de algoritmos implementados em linguagem C++. Os resultados obtidos mostram a eficiência da aplicação da metodologia, estes resul... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This work presents a proposal based on multi-start methodology for the solution of the distribution network reconfiguration problem, of combinatorial nature and modeled as a mixed-integer nonlinear programming problem. The main objective of this work is to find the optimal radial topology to minimize active power losses in distribution systems. This requires, at first, the resolution of a power flow problem for weakly meshed systems where the apparent power of the system is calculated, which will be used by the Prim algorithm as the weight for generating the radial initial good quality solution. To implement the proposed methodology is also developed a radial power flow algorithm, used to calculate both the active system losses (objective function of the problem) and to verify the feasibility of the proposed solutions. In this first stage is made a random variation of the weights of branches, and there are solved as many radial power flows as random solutions obtained, to find good quality solutions close to optimal. Finally, a local search is made by doing an exchange of branches as an attempt to find the optimal solution. The solutions obtained by the proposed method are acquired by programming algorithms implemented in C ++ language. The results show the effectiveness of the application of the methodology. These results were compared with those in the literature and those obtained by solving an optimization model solved by the commercial solver CPLEX. / Mestre