Search

Submitted by Gabriel Figueiredo Puerta (gfpuerta@gmail.com) on 2022-09-27T01:03:07Z No. of bitstreams: 1 tese_gabriel_repositorio.pdf: 4000866 bytes, checksum: 720247bc77049b779e0c4c74e95577ea (MD5) Approved for entry into archive by Raiane da Silva Santos (raiane.santos@unesp.br) on 2022-09-27T14:34:22Z (GMT) No. of bitstreams: 1 puerta_gf_dr_ilha.pdf: 4000866 bytes, checksum: 720247bc77049b779e0c4c74e95577ea (MD5) Made available in DSpace on 2022-09-27T14:34:22Z (GMT). No. of bitstreams: 1 puerta_gf_dr_ilha.pdf: 4000866 bytes, checksum: 720247bc77049b779e0c4c74e95577ea (MD5) Previous issue date: 2022-09-08 Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) Neste trabalho são apresentadas três métodos especializados na resolução do problema de restauração de sistemas de distribuição de energia elétrica (PRSDEE). O principal objetivo do problema é a elaboração de uma estratégia que consiga restaurar o maior montante possível de carga que foi afetada pela falta ao mesmo tempo que altere minimamente a topologia do sistema de distribuição. A primeira metodologia proposta no trabalho é um modelo de programação linear inteira-mista (PLIM). A segunda metodologia é um algoritmo baseado na meta-heurística de busca em vizinhança variável (VNS), que possui a vantagem de resolver o problema de restauração como se fosse um problema de reconfiguração. A terceira metodologia proposta é um algoritmo matheurístico híbrido com base no modelo de PLIM e que conta com uma busca em vizinhança variável similar à da meta-heurística VNS. Na literatura do problema de restauração não é possível encontrar abordagens com algoritmos matheurísticos. Os resultados são divididos em três casos de estudos. O primeiro é composto pela simulação de faltas únicas em um sistema de distribuição radial de 53 barras. No segundo caso de estudo são simuladas faltas únicas em um sistema de distribuição de 417 barras. O terceiro caso de estudo incorpora dois testes específicos: faltas múltiplas e contingências em sistemas com presença de geração distribuída. As três metodologias são comparadas com um modelo de programação cônica de segunda ordem inteira-mista (PCSOIM) já conhecido na literatura e os resultados obtidos qualificam a robustez e eficácia dos algoritmos propostos, principalmente o algoritmo matheurístico. This work proposes three specialized methodologies for the resolution of the power system distribution restoration problem. The main goal of the problem is to elaborate a strategy that can restore the maximum possible load amount that was affected by the fault and, at the same time, to minimally change the distribution system’s topology. The first methodology proposed is a mixed-integer linear programming model. The second methodology is an algorithm based on the variable neighborhood search metaheuristic that has the advantage of solving the restoration problem as a reconfiguration problem. The third methodology is a hybrid matheuristic algorithm based on the mixed-integer linear programming model with a variable neighborhood search, similar to the VNS metaheuristic. The numerical results are divided into three different study cases. The first is composed of the simulation of single faults in a 53-bus distribution system. In the second study case, single faults are simulated in a 417-bus distribution system. The third study case incorporates two specific tests: multiple faults and faults in distribution systems with the presence of distributed generation. The three methodologies are compared with a known mixed-integer second-order cone programming model and the obtained results qualify the robustness and efficiency of the proposed algorithms, mainly the matheuristic algorithm. CNPq: 001 FAPESP: 2015/21972-6

Submitted by Douglas Nogueira do Nascimento (douglas.nogueira@unesp.br) on 2022-09-06T02:58:37Z No. of bitstreams: 1 Tese - Douglas Nogueira do Nascimento - Versão Final.pdf: 1680670 bytes, checksum: 207877f0bb2b87f5f826c792a2476702 (MD5) Approved for entry into archive by Lucilene Cordeiro da Silva Messias null (lubiblio@bauru.unesp.br) on 2022-09-06T11:39:31Z (GMT) No. of bitstreams: 1 nascimento_dn_dr_bauru.pdf: 1680670 bytes, checksum: 207877f0bb2b87f5f826c792a2476702 (MD5) Made available in DSpace on 2022-09-06T11:39:31Z (GMT). No. of bitstreams: 1 nascimento_dn_dr_bauru.pdf: 1680670 bytes, checksum: 207877f0bb2b87f5f826c792a2476702 (MD5) Previous issue date: 2022-09-01 Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) O problema de corte de estoque é um problema clássico da área de pesquisa operacional que foi tema de centenas de estudos publicados na literatura científica. Na primeira parte desta tese, é abordada uma variação desse problema, conhecida como problema de corte de estoque bidimensional com sobras aproveitáveis, que consiste em cortar placas retangulares disponíveis em estoque para produzir itens retangulares menores com dimensões e quantidades específicas, de modo a minimizar a perda de material. O planejamento dessa produção é realizado considerando a possibilidade de gerar sobras não demandadas que, caso atendam a critérios predefinidos, retornam ao estoque para serem utilizadas em futuros processos de corte. O aproveitamento de sobras é uma técnica de grande importância prática para muitas empresas, com forte impacto econômico e ambiental, devido à redução no desperdício de matéria-prima. Para resolver este problema, foi proposto um modelo matemático que, simultaneamente, cria padrões de corte e determina suas frequências. Os padrões de corte são criados a partir de uma estratégia que divide a placa cortada em faixas horizontais, nas quais os itens são alocados. Novos tipos de itens também são considerados a partir da combinação dos tipos de itens originais. Esse modelo foi resolvido a partir de um solver exato. Entretanto, devido ao seu alto número de variáveis e restrições, pode se tornar inviável sua resolução para instâncias de médio e grande porte em um tempo computacional aceitável. Nesse contexto, foi desenvolvido um procedimento heurístico que utiliza duas adaptações do modelo para resolver separadamente as tarefas de criar padrões de corte e definir suas frequências. Testes computacionais foram realizados com instâncias da literatura e instâncias geradas aleatoriamente para comparar o desempenho do modelo e da heurística com outros modelos propostos na literatura. Na segunda parte da tese, com o objetivo de aproximar esta pesquisa de aplicações práticas reais, o problema de corte de estoque bidimensional com sobras aproveitáveis foi estudado considerando a incerteza na demanda dos itens. A produção de sobras aproveitáveis e itens visando atender uma demanda variável e aleatória é um problema recorrente nas empresas por conta da imprevisibilidade na ocorrência dos pedidos dos clientes. A resolução desse problema envolve um planejamento complexo, motivando a busca por métodos de solução que auxiliem no processo de tomada de decisão. Para a formulação desse problema, as demandas incertas podem ser aproximadas por um conjunto finito de possíveis cenários. Esta tese contribui com a literatura científica propondo uma matheurística que resolve o problema a partir de três etapas consecutivas e dependentes entre si. Na primeira etapa, um conjunto de padrões de corte, com e sem sobras aproveitáveis, é criado para todos os tipos de placas em estoque e todas as possíveis combinações de itens. Esses padrões de corte são usados na segunda etapa por um framework baseado em algoritmos genéticos que gera um conjunto de cenários de demanda. Na terceira etapa, tanto os padrões quanto os cenários são utilizados por um modelo estocástico que determina a frequência de cada padrão de corte em cada cenário de demanda. Esse modelo estocástico foi resolvido por duas abordagens, um solver exato e uma heurística baseada no método L-shaped, avaliadas utilizando experimentos computacionais com instâncias geradas aleatoriamente. A partir dos resultados obtidos e de uma análise dos efeitos da incerteza na qualidade das soluções, foi possível verificar que a matheurística resolve satisfatoriamente o problema abordado, demonstrando que pode ser uma ferramenta eficiente se aplicada a situações reais. The cutting stock problem is a classic problem in the operational research area that has been the subject of hundreds of studies published in the scientific literature. In the first part of this thesis, a variation of this problem, known as the two-dimensional cutting stock problem with usable leftovers, is addressed, which consists of cutting rectangular plates available in stock to produce smaller rectangular items with specific dimensions and quantities while minimizing the material loss. The planning of this production is carried out considering the possibility of generating unordered leftovers that, if meeting predefined criteria, return to stock to be used in future cutting processes. Usable leftovers is a strategy of great practical importance for many companies, with strong economic and environmental impact, due to the reduction in raw material waste. To solve this problem, a mathematical model that simultaneously creates cutting patterns and determines their frequencies was proposed. The cutting patterns are created by a strategy that divides the cut plate into horizontal strips, in which the items are allocated. New items are also considered from the combination of the original types of items. This model was solved by an exact solver. However, due to its high number of variables and constraints, its resolution for medium and large-sized instances may become impracticable in an acceptable computational time. In this context, a heuristic procedure was developed using two adaptations of the model to solve separately the tasks of creating cutting patterns and defining their frequencies. Computational tests were performed with instances from the literature and randomly generated instances to compare the performance of the model and the heuristic with other models proposed in the literature. In the second part of the thesis, aiming to bring this research closer to real practical applications, the two-dimensional cutting stock problem with usable leftovers was studied considering uncertain items' demand. The production of usable leftovers and items to meet a variable and random demand is a recurring problem in companies due to the unpredictability occurrence of customer orders. Solving this problem involves complex planning, which motivates the search for solution methods that help in the decision-making process. For the formulation of this problem, the uncertain demands can be approximated by a finite set of possible scenarios. This thesis contributes to the scientific literature by proposing a matheuristic that solves the problem in three consecutive and dependent steps. In the first step, a set of cutting patterns, with and without usable leftovers, is created for all types of plates in stock and all possible item combinations. These cutting patterns are used in the second step by a framework based on genetic algorithms that generate a set of demand scenarios. In the third step, both patterns and scenarios are used by a stochastic model that determines the frequency of each cutting pattern in each demand scenario. This stochastic model was solved by two approaches, an exact solver and a heuristic based on the L-shaped method, tested in computational experiments with randomly generated instances. From the obtained results and an analysis of the effects of uncertainty on the quality of solutions, it was possible to verify that the matheuristic satisfactorily solves the addressed problem, demonstrating that it can be an efficient tool if applied to real situations. FAPESP: 2018/16600-0 FAPESP: 2019/25041-8

Submitted by Jairo Gonzalo Yumbla Romero (jairo.yumbla@unesp.br) on 2021-10-15T23:02:22Z No. of bitstreams: 1 DISSERTAÇÃO JAIRO GONZALO.pdf: 2382327 bytes, checksum: 5e9d8a4f8dc63a9a2c21636482dd2bfb (MD5) Approved for entry into archive by Joao Josue Barbosa (joao.barbosa@unesp.br) on 2021-10-16T13:05:00Z (GMT) No. of bitstreams: 1 yumbla_romero_jg_me_ilha.pdf: 2382327 bytes, checksum: 5e9d8a4f8dc63a9a2c21636482dd2bfb (MD5) Made available in DSpace on 2021-10-16T13:05:00Z (GMT). No. of bitstreams: 1 yumbla_romero_jg_me_ilha.pdf: 2382327 bytes, checksum: 5e9d8a4f8dc63a9a2c21636482dd2bfb (MD5) Previous issue date: 2021-08-26 Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) As redes modernas de distribuição de energia elétrica são redes ativas que possuem recursos energéticos distribuídos desenhados para injetar e armazenar energia de forma estratégica. Para o planejamento da operação de curto prazo deve ser considerada a natureza estocástica das variáveis envolvidas nos modelos matemáticos com vistas a obter resultados realistas e aplicáveis pelas empresas distribuidoras. Neste trabalho é apresentada uma metodologia para solução do problema de reconfiguração de sistemas ativos de distribuição, que possuem geração distribuída renovável fotovoltaica e não renovável, bancos de capacitores e bancos de baterias para o armazenamento de energia. A variabilidade que apresentam as cargas e a geração distribuída fotovoltaica, é analisada através de uma janela de tempo preestabelecida. Essa variabilidade é obtida após o processamento de dados históricos através do método de agrupamento K-means, que permite a criação de cenários representativos com os valores dos parâmetros aleatórios. O problema de reconfiguração, do ponto de vista da programação matemática, é de alta complexidade devido à natureza das variáveis e a não linearidade das restrições. A solução é de natureza computacional complexa para sistemas reais de grande porte mesmo através do uso de softwares comerciais. Para contornar estes problemas e oferecer contribuições ao estado da arte com relação a uma nova técnica de solução, propõe-se uma metodologia que aproveita as características da programação matemática baseada em otimização clássica, na estrutura de um algoritmo metaheurístico, sendo que esta integração de otimização clássica e metas-heurísticas, é conhecida como técnica matheuristica. Neste caso, é usada a linguagem AMPL e o solver CPLEX, para implementar um processo de busca tabu que evolui de maneira iterativa obtendo soluções vizinhas. Para demonstrar a eficiência e escalabilidade desta metodologia, apresenta-se uma comparação entre os resultados fornecidos pelo algoritmo proposto e o uso do solver CPLEX. Os testes são realizados com os sistemas de 69, 136 e 880 barras, encontrados na literatura especializada The modern electrical distribution networks are active systems that have distributed energy resources designed to inject and store energy strategically. In addition, for the short-term operation planning, the stochastic nature of the variables involved in the mathematical models must be considered, with the purpose to obtaining realistic results applicable by the companies. This work presents a methodology to solve the problem of reconfiguration of active distribution systems, equipped with the following photovoltaic and dispatchable distributed generation, capacitor banks and battery banks for energy storage. The variability of loads and distributed photovoltaic generation is analyzed through a pre-established time window. This variability is obtained after processing historical data through the K-means clustering method, which allows the creation of representative scenarios with random parameter values. The reconfiguration problem, from the point of view of mathematical programming, is highly complex due to the mixed nature of the variables and the non-linearity of the constraints. The solution is computationally complex for large real systems even using commercial software. To circumvent these problems and offer contributions to the state of the art regarding a new solution technique, a new methodology is proposed. It takes advantage of the characteristics of mathematical programming based on classical optimization, within of the structure of a metaheuristic algorithm. Thereby, a matheuristic technique is obtained due to the interact of mathematical programming and metaheuristics. In this case, the AMPL language and the CPLEX solver are used to implement a tabu search process that iteratively evolves obtaining neighboring solutions. To demonstrate the efficiency and scalability of this methodology, a comparison between the results provided by the proposed algorithm and the commercial solver CPLEX is presented. The tests are carried out with the 69, 136 and 880 bus systems, found in the specialized literature. CAPES: 001

Dissertação de mestrado em Engenharia de Sistemas, Os projetos de industrialização são projetos considerados fundamentais para a introdução de novos produtos no mercado. Estes projetos representam uma das etapas de maior criação de valor em toda a indústria, o que pode também explicar o crescimento da literatura sobre o tema. Para gerir melhor estes projetos é crucial usar técnicas robustas para a gestão de projetos. Dentro dessas técnicas podemos incluir as técnicas que permitem fazer um melhor uso da capacidade para gerir projetos de industrialização, foco deste trabalho. Assim, o presente trabalho foi realizado como um estudo de caso, realizado na Bosch Car Multimedia, com o intuito de identificar que métodos e técnicas poderiam acrescer melhorias na gestão de capacidades em projetos de industrialização. Do vasto campo de conhecimento existente na gestão projetos, o presente trabalho concentra-se nas áreas de conhecimento de Project Resources Management e Project Schedule Management. O alinhamento destas duas áreas de conhecimento da gestão de projetos resultou numa ferramenta que auxilia na gestão do portfólio de projetos de industrialização, nomeadamente na atribuição dos gestores de projeto aos projetos, tendo em conta a sua capacidade e suas competências. Esta ferramenta utiliza um modelo matemático e uma mateurística para construir os cronogramas do projeto sem que ocorra uma sobre alocação dos gestores dos projetos. Pode verificar que a ferramenta constrói cronogramas num tempo médio de 35,56 segundos em cenários sem due dates e um tempo médio 168,70 segundos em cenários com due dates. Além disso reúne as informações dos projetos e gestores de projetos num dashboard, com o intuito de identificar o nível de aproveitamento da capacidade disponível para gerir o portfólio de projetos., Industrialization projects are projects that are considered crucial for the introduction of new products in the market. These projects represent one of the highest value-creation stages of the entire industry, which can also explain the growing literature on the subject. To better manage these projects it is crucial to use project management robust techniques. Within these techniques we can include techniques that allow to make a better use of the capacity to manage industrialization projects, the focus of this research. Thus, this work was carried out as a case study, conducted at Bosch Car Multimedia, in order to identify which methods and techniques could add improvements in capacity management in industrialization projects. From the vast field of knowledge in project management, this work focused on the Project Resource Management and Project Schedule Management knowledge areas. Aligning these two knowledge areas of project management, resulted in a tool that aims to help in managing the industrialization projects portfolio, in particular in the assignment of project managers to projects, taking into account their capacity and skills. This tool makes use of a mathematical model and a matheuristic to construct time schedules without over-allocation for the project managers. It can be observed that the tool builds time-schedules in an average time of 35.56 seconds in scenarios without due dates and an average time of 168.70 seconds in scenarios with due dates. Also, it gathers information from projects and project managers in a dashboard to identify the capacity utilization rate available to manage the project portfolio.

The main objective of the electric power utility is the uninterrupted supply of energy, however, this is not always possible due to the actions of nature, or even from equipment or human failures. These interruptions are called emergency orders, which must be serviced by repair crew in order to restore normal operation of the electrical system. Given a set of emergency orders, the operations center must find a crew scheduling in order to attend all orders and minimize the total cost of service. Before the system repair step, the restoration step is performed, in order to supply the de-energized loads belonging to the healthy parts of the network. One of the ways to supply them is through distributed generation (DG), such as solar and wind, with high penetration in the electric system in recent years, operating in islanded mode. The island operation plays an important role in the restoration step of the electric power system, as it allows to reduce the total interruption time. It allows analyzing the impact of customer cost, with interrupted power supply, depending on the time of day, varying with the capacity of the DG generation curve and the load curve. In this way, this work proposes a new matheuristic for emergency response for the emergency orders scheduling problem (EOSP) of the electric distribution systems, considering unforeseen islanding. The model has the objective of minimizing the total attendance cost, being for this model the costs of energy not supplied and those related to the penalties, associated to the importance of consumers. The matheuristic will serve as a management tool for decision-makers to determine an appropriate scheduling strategy. In this work the computational implementation of the proposed model is presented, with the realization of two case studies in the IEEE 33-bus system, modified with DGs insertion. Computational results show the effectiveness of the model developed by reducing the total attendance cost in relation to the case without islanding and the feasibility for applications in other distribution systems. A concessionária de energia tem como objetivo principal o suprimento ininterrupto de energia, porém isto nem sempre é possível devido às ações da natureza, ou ainda, oriundas de falhas de equipamentos ou humanas. Essas interrupções são chamadas de ordens emergenciais, devendo ser atendidas por equipes de reparo de modo a restaurar a operação normal do sistema elétrico. Dado um conjunto de ordens emergenciais, o centro de operações deve encontrar um agendamento das equipes de forma a atender todas as ordens e minimizar o custo total de atendimento. Antes da etapa de reparo do sistema têm-se a etapa de restauração, visando atender as cargas desenergizadas pertencentes aos trechos saudáveis da rede. Uma das formas de atendê-las é através do suprimento por geração distribuída (GD), como solar e eólica, com grande penetração no sistema elétrico nos últimos anos, operando de forma ilhada. A operação ilhada desempenha um papel importante na fase de restauração do sistema elétrico, pois permite reduzir o tempo total de interrupção. Ela permite analisar o impacto do custo dos consumidores, com fornecimento de energia interrompido, em função do período do dia, variando com a capacidade da curva de geração GD e da curva de carga. Neste sentido, este trabalho propõe uma heurística matemática para resposta emergencial para o problema de agendamento de ordens emergenciais (PAOE) dos sistemas de distribuição de energia elétrica, considerando ilhamento imprevisto com GD. O modelo tem como objetivo a minimização do custo total de atendimento, sendo para isso modelados os custos da energia não suprida e os relacionados às penalidades, associadas à importância dos consumidores. A heurística matemática servirá como uma ferramenta gerencial para que os tomadores de decisão determinem uma estratégia de agendamento apropriada. Neste trabalho apresenta-se ainda a implementação computacional do modelo proposto, com a realização de dois estudos de caso no sistema IEEE 33-barras modificado com a inserção de GDs. Resultados computacionais mostram a eficácia do modelo desenvolvido ao reduzir o custo total do atendimento em relação ao caso sem ilhamento e a praticabilidade para aplicações em outros sistemas de distribuição.

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O Problema do Brigadista em Grafos (FFP do inglês The Firefighter Problem é um modelo determinístico e em tempo discreto para simular a propagação e contenção de incêndios em grafos. Ele pode ser descrito da seguinte forma. Na entrada, é dado um inteiro D representando a quantidade de brigadistas disponíveis, um grafo não direcionado e não ponderado G = (V,E) e um subconjunto de vértices B de V, os focos de incêndio. Então, inicia-se nos elementos de B um processo iterativo de propagação e contenção de fogo através dos vértices de G, em rodadas discretas, o qual termina quando não existem mais vértices que possam ser queimados, ou seja, quando o fogo está contido. O objetivo ao resolver o FFP é maximizar o número de vértices não queimados quando o fogo é contido, com a restrição de que no máximo D vértices podem ser protegidos contra o fogo por rodada. Aplicações práticas do FFP, além da obtenção de estratégias para minimização de danos causados por incêndios, podem ser encontradas em áreas como controle de doenças e segurança em redes. O FFP é NP-difícil e métodos heurísticos para lidar com o problema foram relatados previamente na literatura. Nessa dissertação, primeiramente, apresentamos melhorias feitas na primeira formulação PLI proposta para o FFP através de técnicas de preprocessamento e agregação de restrições. Em seguida, descrevemos novas heurísticas gulosas e introduzimos uma nova matheurística para o FFP, uma abordagem que se baseia na interoperação entre meta-heurísticas e programação matemática. Experimentos foram conduzidos em um benchmark público tanto para configuração de parâmetros quanto para análise de desempenho, através de comparação dos resultados obtidos com aqueles publicados anteriormente. Com respeito às modificações no modelo PLI, um speedup de aproximadamente 2 em média foi alcançado. Observamos que as modificações feitas podem levar a geração de soluções infactíveis, mas conseguimos demonstrar que é possível tornar tais soluções factíveis em tempo polinomial. Em referência às heurísticas, essas foram executadas seguindo uma metodologia para construir uma solução na qual escolhas gulosas aleatorizadas são realizadas para selecionar quais vértices serão defendidos, de acordo com conceitos introduzidos na meta-heurística GRASP. Comparando essas heurísticas com as que foram propostas por trabalhos anteriores, observamos que duas das nossas estão entre as cinco melhores na maioria dos casos. Com relação à matheurística, através de uma análise estatística rigorosa, verificamos que existe diferença estatisticamente significativa entre nossa estratégia e as demais, ao mesmo tempo que nossa matheurística conseguiu resultados melhores na maioria das instâncias Abstract: The firefighter problem (FFP) is a deterministic discrete-time model for the spread and containment of fire on a graph. Such problem is described as follows. As its inputs, there is an integer D representing the number of available firefighters, an undirected and unweighted graph G=(V, E) and a subset of vertices B of V, the fire outbreaks. Then, an iterative process of fire propagation and containment through the vertices of G is started at the ones from B. This process ends when there are no more vertices to be burnt, that is, the fire is contained. The goal when solving the FFP is to maximize the number of vertices that are not burned when the fire is contained, with the constraint that at most D vertices can be protected against the fire per iteration. Practical applications of the FFP, besides obtaining strategies to minimize the damage caused by fire, can be found in areas such as disease control and network security. The FFP is NP-hard and heuristic methods to tackle the problem were proposed earlier in the literature. In this dissertation, firstly we present modifications made on the first ILP model proposed to the FFP through techniques of preprocessing and constraint aggregation. Moreover, we describe new greedy heuristics and also we introduce a novel matheuristic to the FFP, an approach based on the interoperation between metaheuristics and mathematical programming. A series of computational experiments were conducted on a public benchmark both for parameter tuning and to compare our results with those obtained previously. In respect to the modifications on the ILP model, a speedup of 2 in average was obtained. While constraint aggregation can lead to infeasible solutions, we prove that the latter can be converted to feasible ones in linear time. Regarding the heuristics, they were executed following a methodology to construct a solution in which greedy randomized choices are made to select which vertices should be defended, according to concepts introduced by the GRASP metaheuristic. Comparing these heuristics with the ones proposed by previous works, we observe that two of ours are between the five best ones in general. In relation to the matheuristic, through rigorous statistical analysis, we were able to verify that there is a statistically significant difference between our strategy and the remaining ones, while our matheuristic had better results on the majority of the instances Mestrado Ciência da Computação Mestre em Ciência da Computação CNPQ 133728/2016-1

Orientador: Fábio Luiz Usberti Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O problema do caixeiro viajante euclidiano (Traveling Salesman Problem - TSP) do ponto de vista geométrico tem por objetivo encontrar um polígono simples sobre um dado conjunto de vértices cujo perímetro é mínimo. É possível derivar o problema de modo que o objetivo seja encontrar um polígono simples cuja área interna seja máxima: tal problema é conhecido como Poligonização de Área Máxima (Maximum Area Polygonization - MAXAP). O MAXAP é um problema de otimização combinatória NP-difícil com aplicações práticas em segmentos como reconhecimento de padrões, reconstrução de imagens, clusterização e robótica. Este trabalho propõe novas metodologias de solução e formulações matemáticas para o MAXAP, visando a implementação de algoritmos para metodologias exata, aproximada e heurística, bem como um estudo computacional para avaliar o desempenho das metodologias para o conjunto de instâncias desenvolvido. São propostos neste trabalho dois modelos matemáticos de programação linear inteira, duas heurísticas construtivas, uma metaheurística GRASP e uma matheuristic aplicada sobre um dos modelos matemáticos. Experimentos computacionais foram executados para comparar as metodologias propostas entre si e com um algoritmo 1/2-aproximado da literatura. Análises comparativas de desempenho foram realizadas sobre os resultados obtidos mostrando que o GRASP obteve o melhor desempenho no critério de qualidade das soluções. As heurísticas construtivas propostas por sua vez obtiveram um desempenho superior sobre o algoritmo aproximado. Finalmente, os modelos matemáticos propostos mostram a dificuldade de resolver de maneira exata o MAXAP, encontrando soluções ótimas em uma hora somente para as instâncias de 10 pontos, em um conjunto de instâncias de até 100 pontos Abstract: The Traveling Salesman Problem (TSP) from a geometric point of view aims to find a simple polygon with minimum perimeter. It is possible to derive the problem so that the objective is to find a simple polygon whose enclosed area is maximum, such problem is known as Maximum Area Polygonization (MAXAP). The MAXAP is an NP-hard combinatorial optimization problem with practical applications in segments such as pattern recognition, image reconstruction, clustering and robotics. This work proposes new solution methodologies and mathematical formulations for MAXAP, aiming the implementation of algorithms for exact, approximate and heuristic solutions, as well as a computational study to evaluate the performance of the methodologies for a benchmark set of instances. Two mathematical models based on integer linear programming are proposed. In addition, two constructive heuristics, a GRASP metaheuristic, and a matheuristic are proposed for the solution of larger instances. Computacional experiments were conducted to compare the proposed methodologies among themselves and a 1/2-approximation algorithm from literature. Comparative perfomance analysis were made on the results showing that the GRASP outperformed all other approaches with respect to solution quality. The constructive heuristics, on the other hand, outperformed the literature 1/2-approximation algorithm. Finally, the proposed mathematical models have shown the hardness of exact solution for the MAXAP, finding optimal solutions in one hour only for the 10-vertices instances in a set of instances with 10, 25, 50 and 100 vertices Mestrado Ciência da Computação Mestre em Ciência da Computação CAPES FAEPEX

O Problema de Balanceamento e Sequenciamento de Linhas de Montagem com Tempos de Setup dependentes da Sequência (SUALBSP, em inglês Setup Assembly Line Balancing and Scheduling) envolve a atribuição de tarefas às estações de trabalho e o sequenciamento destas tarefas dentro da estação à qual foi atribuída. Trabalhos anteriores propuseram soluções heurísticas com excelentes resultados, porém o uso de métodos exatos, por meio de algum resolvedor de Programação Inteira Mista, tem apresentado desempenhos decepcionantes, pois contém um subproblema NP-hard em todas as estações. Enquanto o modelo de Scholl, Boysen e Fliedner (2013) minimiza prioritariamente o número de estações, o modelo proposto neste trabalho parte da premissa que este é um dado definido. A partir de uma estimativa inicial de número de estações, processa-se o modelo com o objetivo de distribuir as tarefas e minimizar o tempo total de estação, que é o segundo objetivo do modelo original. Se este processamento for infactível, incrementa-se o número de estações em uma unidade e reprocessa-se o modelo até se encontrar um resultado factível. Experimentos computacionais em 101 instâncias de dados confirmam o bom desempenho da abordagem proposta, sem qualquer prejuízo à qualidade da solução. Portanto, os resultados apresentados demonstram que há espaço para estudos futuros a partir do uso de matheurísticas. The Setup Assembly Line Balancing and Scheduling Problem (SUALBSP) involves the assigning of tasks to workstations and the sequencing of these tasks within the station to which they are assigned. Previous work has proposed heuristic solutions with excellent results, but the use of exact methods, by some Mixed-Integer Programming solver, has shown disappointing performance, because it contains an NP-hard sub problems in every station. While the model proposed by Scholl, Boysen and Fliedner (2013) primarily minimizes the numbers of stations, our model assumes it as a parameter. From an initial estimate of the number of stations, we process the model for allocating tasks and minimize station times, which is the second objective of the original model. If this processing is infeasible, we increase the number of stations by one unit and we reprocess the model to find a feasible result. Computational experiments in 101 instances of data set confirm the good performance of the proposed approach, without harming the quality of the solution. Therefore, the results show that there are opportunities for future studies based on the use of matheuristics.

This dissertation deals with the Pollution-Routing Problem (PRP), a Vehicle Routing Problem (VRP) with environmental considerations, recently introduced in the literature by Bekta ¸s e Laporte (2011). The objective is to minimize operational and environmental costs while respecting route-load constraints and service time windows. Costs are based on driver wages and fuel consumption, which depends on many factors, such as travel distance and vehicle load. Vehicle speeds are additional decision variables of the problem which complement routing decisions. They impact the total cost, the travel times between the locations, and thus the set of feasible routes. We propose a hybrid method that combines a local search-based metaheuristic with an exact approach and a recursive speed-optimization algorithm. Moreover, two other green VRP variants, the Fuel Consumption VRP (FCVRP) and the Energy Minimizing VRP (EMVRP), are addressed. The results obtained compare very favorably with those found in the literature, and many new improved solutions are reported. Conselho Nacional de Desenvolvimento Científico e Tecnológico Esta dissertação lida com o Pollution-Routing Problem (PRP), i.e. um Problema de Roteamento de Veículos (PRV) com considerações ambientais, recentemente introduzido na literatura por Bekta¸s e Laporte (2011). O objetivo consiste na minimização dos custos operacionais e ambientais, respeitando as restrições de carga dos veículos e janelas de tempo dos clientes. O custo é baseado no salário dos motoristas e no consumo de combustível, que depende de diversos fatores, como distância percorrida e carga transportada. As velocidades dos veículos são variáveis de decisão adicionais que complementam as decisões de roteamento. Tais velocidades interferem diretamente no custo total, nos tempos de viagem, bem como no conjunto de rotas viáveis. Uma abordagem híbrida que combina uma metaheurística baseada em busca local com uma abordagem exata e um algoritmo recursivo para otimizar as velocidades é proposta para solucionar o problema. Além do PRP, outras duas variantes do PRV com considerações ambientais são tratadas: o PRV considerando consumo de combustível e o PRV com minimização de energia. Os resultados obtidos se mostraram bastante favoráveis quando comparados com os melhores da literatura, e diversas soluções melhoradas são reportadas.

Mestrado em Decisão Económica e Empresarial Trata-se do estudo de um problema de otimização de rotas nos arcos definido num grafo misto. As ligações podem ser tarefas, caso em que requerem serviço, ou apenas constar para assegurar a definição das rotas. Cada ligação tem associado um custo em vazio e, se for tarefa, um custo de serviço e procura. O serviço é efetuado por uma frota homogénea de veículos com uma dada capacidade. Pretende-se determinar um conjunto de rotas, a iniciar e terminar no depósito, compatíveis com a capacidade dos veículos, que assegurem a execução de todas as tarefas com um custo total mínimo. O problema, conhecido pela designação de MCARP (Mixed Capacitated Arc Routing Problem), é comprovadamente NP-difícil. Uma aplicação prática deste problema é a recolha de resíduos sólidos urbanos. A motivação para este trabalho surgiu no âmbito da otimização de rotas para a recolha de resíduos sólidos urbanos no Município do Seixal. Com o objetivo de determinar soluções admissíveis, apresenta-se uma matheurística em que se alia a resolução de dois modelos compactos a regras heurísticas para a fixação de serviços. Esta pode ser decomposta em três fases: (I) resolução do modelo agregado; (II) afetação de serviços a veículos; (III) resolução do modelo válido no problema de menor dimensão resultante de (II). O desempenho da matheurística foi avaliado com um conjunto de instâncias habitualmente utilizado para testar heurísticas para o MCARP. Os resultados não foram os mais animadores, pois as instâncias de maior dimensão que simulam casos reais permanecem com um tempo computacional elevado. This project is regarding a study of a routes optimization problem in the arcs of a mixed graph. The connections may be tasks, in which case require service, or just to be included to ensure the definition of the routes. Each link has an associated deadheaded cost, and, if it is a task, it has a service cost and a demand. The service is performed by a homogeneous fleet of vehicles with a given capacity. It is intended to determine a set of routes, starting and ending in the depot, consistent with the capacity of the vehicles that perform all tasks at a minimum total cost. The problem, known by the designation of MCARP (Mixed Capacitated Arc Routing Problem), is proven to be NP-hard. A practical application of this problem is the collection of household solid waste. The motivation for this dissertation is the route optimization for the collection of solid waste in the Seixal Municipality. In order to determine feasible solutions, a matheuristic is presented in which we combine the resolution of two compact models with heuristic rules for services setting. This method can be decomposed into three stages: (I) resolution of the aggregate model; (II) allocation of services to vehicles, (III) resolution of the valid model in the problem of smallest dimension resulting from (II). The matheuristic performance was evaluated with a set of instances normally used to test MCARP heuristics. The results on the larger instances, that simulate real cases, remain with a high computational time.