PPGCC - Programa de Pós-graduação em Ciência da Computação
URI permanente desta comunidadehttp://www.hml.repositorio.ufop.br/handle/123456789/596
Navegar
6 resultados
Resultados da Pesquisa
Item Exact and heuristic approaches for traveling salesman problems with drones.(2021) Freitas, Júlia Cária de; Penna, Puca Huachi Vaz; Toffolo, Túlio Ângelo Machado; Penna, Puca Huachi Vaz; Toffolo, Túlio Ângelo Machado; Souza, Marcone Jamilson Freitas; Subramanian, AnandThe technological advances concerning drones have encouraged the market to consider drone applications in different areas including last mile delivery. However, limitations due to battery capacity, maximum weight, and legal regulations restrict the effective operational range of drones in many practical applications. To overcome the battery issue, hybrid operations involving one or more drones launching from a larger vehicle have emerged, in which the larger vehicle operates as a mobile depot and a recharging platform. In this dissertation, we describe a routing model that leverage the drone and truck working as a synchronized unit. The Flying Sidekick Traveling Salesman Problem (FSTSP) considers a delivery system composed by a truck and a drone. The drone launches from the truck with a single package to deliver to a customer. Each drone must return to the truck to recharge batteries, pick up another package, and launch again to a new customer location. This work proposes two novel Mixed Integer Programming (MIP) formulations and a heuristic approach to address the problem. The proposed MIP formulations yields better linear relaxation bounds than previously proposed formulations for all instances, and was capable of optimally solving several unsolved instances from the literature. We developed a hybrid heuristic based on the General Variable Neighborhood Search metaheuristic to tackle a generalization of the FSTSP called Multiple Traveling Salesman Problem with Drones, in which multiple trucks and drones are considered as part of the delivery system. The heuristic obtained high-quality solutions for large-size instances. The efficiency of the algorithm was evaluated on 410 benchmark instances from the literature, and over 80% of the best known solutions were improved.Item Mathematical models and heuristic algorithms for routing problems with multiple interacting components.(2021) Chagas, Jonatas Batista Costa das; Souza, Marcone Jamilson Freitas; Santos, André Gustavo dos; Souza, Marcone Jamilson Freitas; Santos, André Gustavo dos; Barboza, Eduardo Uchoa; Arroyo, José Elias Claudio; Vidal, Thibaut Victor Gaston; Toffolo, Túlio Ângelo MachadoMuitos problemas de otimização com aplicações reais têm vários componentes de interação. Cada um deles pode ser um problema pertencente à classe N P-difícil, e eles podem estar em conflito um com o outro, ou seja, a solução ótima para um componente não representa necessariamente uma solução ótima para os outros componentes. Isso pode ser um desafio devido à influência que cada componente tem na qualidade geral da solução. Neste trabalho, foram abordados quatro problemas de roteamento complexos com vários componentes de interação: o Double Vehicle Routing Problem with Multiple Stacks (DVRPMS), o Double Traveling Salesman Problem with Partial Last-InFirst-Out Loading Constraints (DTSPPL), o Traveling Thief Problem (TTP) e Thief Orienteering Problem (ThOP). Enquanto os DVRPMS e TTP já são bem conhecidos na literatura, os DTSPPL e ThOP foram recentemente propostos a fim de introduzir e estudar variantes mais realistas dos DVRPMS e TTP, respectivamente. O DTSPPL foi proposto a partir deste trabalho, enquanto o ThOP foi proposto de forma independente. Neste trabalho são propostos modelos matemáticos e/ou algoritmos heurísticos para a solução desses problemas. Dentre os resultados alcançados, é possível destacar que o modelo matemático proposto para o DVRPMS foi capaz de encontrar inconsistências nos resultados dos algoritmos exatos previamente propostos na literatura. Além disso, conquistamos o primeiro e o segundo lugares em duas recentes competições de otimização combinatória que tinha como objetivo a solução de uma versão bi-objetiva do TTP. Em geral, os resultados alcançados por nossos métodos de soluções mostraram-se melhores do que os apresentados anteriormente na literatura considerando cada problema investigado neste trabalho.Item Conflict graphs in mixed-integer linear programming : preprocessing, heuristics and cutting planes.(2020) Brito, Samuel Souza; Santos, Haroldo Gambini; Santos, Haroldo Gambini; Fonseca, George Henrique Godim da; Mateus, Geraldo Robson; Aragão, Marcus Vinicius Soledade Poggi de; Toffolo, Túlio Ângelo MachadoThis thesis addresses the development of con ict graph-based algorithms for MixedInteger Linear Programming, including: (i) an e cient infrastructure for the construction and manipulation of con ict graphs; (ii) a preprocessing routine based on a clique strengthening scheme that can both reduce the number of constraints and produce stronger formulations; (iii) a clique cut separator capable of obtaining dual bounds at the root node LP relaxation that are 19.65% stronger than those provided by the equivalent cut generator of a state-of-the-art commercial solver, 3.62 times better than those attained by the clique cut separator of the GLPK solver and 4.22 times stronger than the dual bounds obtained by the clique separation routine of the COIN-OR Cut Generation Library; (iv) an odd-cycle cut separator with a new lifting module to produce valid odd-wheel inequalities; (v) two diving heuristics capable of generating integer feasible solutions in restricted execution times. Additionally, we generated a new version of the COIN-OR Branch-and-Cut (CBC) solver by including our con ict graph infrastructure, preprocessing routine and cut separators. The average gap closed by this new version of CBC was up to four times better than its previous version. Moreover, the number of mixed-integer programs solved by CBC in a time limit of three hours was increased by 23.53%.Item Mixed-integer linear programming based approaches for the resource constrained project scheduling problem.(2019) Araujo, Janniele Aparecida Soares; Santos, Haroldo Gambini; Santos, Haroldo Gambini; Barboza, Eduardo Uchoa; Souza, Marcone Jamilson Freitas; Jena, Sanjay Dominik; Toffolo, Túlio Ângelo MachadoResource Constrained Project Scheduling Problems (RCPSPs) without preemption are well-known NP-hard combinatorial optimization problems. A feasible RCPSP solution consists of a time-ordered schedule of jobs with corresponding execution modes, respecting precedence and resources constraints. First, in this thesis, we provide improved upper bounds for many hard instances from the literature by using methods based on Stochastic Local Search (SLS). As the most contribution part of this work, we propose a cutting plane algorithm to separate five different cut families, as well as a new preprocessing routine to strengthen resource-related constraints. New lifted versions of the well-known precedence and cover inequalities are employed. At each iteration, a dense conict graph is built considering feasibility and optimality conditions to separate cliques, odd-holes and strengthened Chvátal-Gomory cuts. The proposed strategies considerably improve the linear relaxation bounds, allowing a state-of-the-art mixed-integer linear programming solver to nd provably optimal solutions for 754 previously open instances of different variants of the RCPSPs, which was not possible using the original linear programming formulations.Item Um algoritmo híbrido para resolução de problemas binários.(2015) Rezende, Josiane da Costa Vieira; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Souza, Sérgio Ricardo deEste trabalho apresenta um método híbrido, denominado HGVPRLB, para resolver problemas lineares binários. O método combina os procedimentos Greedy Randomized Adaptive Search Procedures -- GRASP, Variable Neighborhood Descent -- VND, propagação de restrições, e cortes Local branching. Como em todo algoritmo GRASP, o método HGVPRLB apresenta duas fases, que interagem entre si até que o tempo limite seja atingido. A primeira fase visa a construção de uma solução inicial; a segunda, por sua vez, visa ao refinamento dessa solução construída. Na fase de construção, é utilizado o resolvedor CBC e um procedimento de propagação de restrições, de forma a gerar uma solução inicial para o problema. O resolvedor CBC relaxa as variáveis binárias, isto é, atribui o valor de cada variável no intervalo real [0,1]. O procedimento propagação de restrições possui a finalidade de verificar se existe solução viável ao se fixar uma determinada variável no valor 1. Se esta solução existir, ele poderá retornar, ainda, um conjunto de possíveis fixações das demais variáveis. Na fase de refinamento são utilizados cortes Local branching controlados pelo procedimento VND até que um tempo previamente definido seja atingido. Os cortes Local Branching utilizam um resolvedor de programação linear inteira como uma ferramenta caixa-preta para explorar eficientemente subespaços das soluções do problema. O método desenvolvido foi aplicado a um conjunto de problemas binários da biblioteca MIPLIB 2010 com o intuito de verificar sua capacidade de obter soluções viáveis de qualidade variando-se o tempo de processamento. Os experimentos computacionais realizados mostraram que, quando o tempo de processamento aumenta, o método consegue aumentar tanto o número de soluções viáveis quanto a qualidade delas. Além disso, o método desenvolvido se mostrou superior a outro método da literatura, bem como a dois outros resolvedores de código aberto nesses dois indicadores de avaliação.Item Análise de combinação de classificadores usando uma abordagem multiobjetivo baseada em acurácia e número de classificadores.(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2013) Tinôco, Sandro Luiz Jailson Lopes; Gomes, David MenottiO Sensoriamento Remoto é uma forma de obter informações sobre a Terra a partir do espaço, com a finalidade de melhorar a gestão dos recursos naturais, o uso da terra e a proteção do meio ambiente. Esse campo do conhecimento tem se beneficiado dos diversos avanços tecnológicos dentre os quais pode ser citada a imagem hiperespectral. Este tipo de imagem pode ser composto por centenas de bandas, cada uma delas correspondendo a uma determinada faixa do espectro eletromagnético. Pode-se perceber a riqueza de informação que tal imagem pode fornecer, conduzindo a uma análise mais precisa. No entanto, para tratar esse volume de informações, tanto em qualidade quanto em quantidade, é necessária a utilização de algoritmos e métodos que consigam tirar proveito de toda a informação fornecida. Uma tarefa comum na análise desses dados é a geração de mapas temáticos a partir da classificação da cobertura terrestre. Tradicionalmente, procura-se desenvolver diferentes algoritmos de classificação e depois aquele que apresenta o melhor desempenho, ou seja maior acurácia, é escolhido. Este tipo de metodologia pode acarretar em perdas de importantes informações contidas nos classificadores descartados. Uma forma de se evitar isso, que tem sido bastante estudada e utilizada atualmente, é a combinação de múltiplas abordagens de classificação e a consequente produção de mapas temáticos mais precisos. No presente trabalho, é feita a combinação de doze abordagens de classificação, obtidas usando três representações de dados e quatro algoritmos de aprendizagem diferentes. As representações de dados usadas são a Pixelwise, Extended Morphological Profiles (EMP) e Feature Extraction by Genetic Algorithms (FEGA), que foram classificadas com os algoritmos de aprendizagem Support Vector Machines (SVM) com kernel Radial Basis Function (RBF) e kernel Linear, K-Nearest Neighbor (KNN) e Multilayer Perceptron Neural Network (MLP). O método de combinação proposto é baseado em uma combinação linear ponderada, em que um Programa Linear Inteiro (PLI) encontra os pesos para cada abordagem de classificação utilizada e é denominado Weighted Linear Combination optimized by Integer Linear Programming (WLC-ILP). Para analisar os resultados obtidos, o método proposto foi comparado a outros métodos de combinação como o Weighted Linear Combination optimized by Genetic Algorithm (WLC-GA) e, os tradicionais, como Majority Vote (MV) e Average Rule. O (WLC-ILP) superou os resultados dos métodos (MV) e Average Rule e obteve resultados similares ao (WLC-GA), porém, dez vezes mais rápido que este. Uma questão ainda em aberto está relacionada a quantos e quais classificadores de um conjunto utilizar, de forma a obter uma acurácia mais precisa. Não se sabe ao certo o que faz uma combinação produzir resultados, ainda que não seja sempre garantido, melhores do que um único classificador. Alguns autores apontam a diversidade de um conjunto como fator principal de êxito de um combinador, no entanto, não existe uma definição formal, amplamente aceita do que seja diversidade. Uma vez que é desejável produzir melhores acurácias utilizando o menor número de classificadores possível, um Algoritmo Genético Multiobjetivo apresenta-se como meio adequado para realização desta tarefa.