Browsing by Author "Penna, Puca Huachi Vaz"

Now showing 1 - 20 of 28
  • No Thumbnail Available
    Item
    5th International Conference on Variable Neighborhood Search (ICVNS'17).
    (2018) Coelho, Vitor Nazário; Santos, Haroldo Gambini; Coelho, Igor Machado; Penna, Puca Huachi Vaz; Oliveira, Thays Aparecida de; Souza, Marcone Jamilson Freitas; Sifaleras, Angelo
    This volume presents selected, peer-reviewed, short papers that were accepted for presentation in the 5th International Conference on Variable Neighborhood Search (ICVNS'17) which was held in Ouro Preto, Brazil, during October 2–4, 2017.
  • No Thumbnail Available
    Item
    Um algoritmo heurístico híbrido para minimizar os custos com a antecipação e o atraso da produção em ambientes com janelas de entrega e tempos de preparação dependentes da sequência.
    (Programa de Pós-Graduação em Engenharia Mineral. Departamento de Engenharia de Minas, Escola de Minas, Universidade Federal de Ouro Preto., 2009) Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas
    Este trabalho de dissertação tem seu foco no problema de sequenciamento em uma máquina com penalidades por antecipação e atraso da produção. São considerados tempos de preparação da máquina dependentes da sequência de produção, bem como a existência de janelas de entrega distintas. Para resolução do problema, desenvolveu-se um algoritmo heurístico de três fases. A primeira fase baseada em GRASP e Descida em Vizinhança Variável para a geração da solução inicial, a segunda fase baseada em Busca Tabu para re namento da solução, e por m, a Reconexão por Caminhos como estratégia de pós-otimização, na terceira fase. Para cada sequência gerada pela heurística é utilizado um algoritmo de tempo polinomial para determinar a data ótima de início de processamento de cada tarefa. Os re- sultados computacionais mostraram que houve melhoria em relação a um algoritmo da literatura, tanto com relação à qualidade da solução nal quanto em relação ao desvio médio.
  • No Thumbnail Available
    Item
    Algoritmos heurísticos para o problema de roteamento de unidades móveis de mamografia.
    (2021) Rosa, Otávio Augusto Souza; Souza, Marcone Jamilson Freitas; Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas; Penna, Puca Huachi Vaz; Coelho, Igor Machado; Carvalho, Marco Antonio Moreira de
    Este trabalho introduz o Problema de Roteamento de Unidades Móveis de Mamografia (MMURP). Este problema consiste em roteirizar um conjunto de Unidades Móveis de Mamografia (MMU) para atender a demanda de localidades desprovidas de mamógrafos fixos ou com número insuficiente deles. O objetivo é maximizar a demanda atendida e minimizar a distância total percorrida pelas MMUs. Para tratar o problema, propomos os algoritmos Smart IGS-VND e Smart IGS-RVND, ambos baseados na metaheurística Iterated Greedy Search. Nestes algoritmos, uma solução inicial é gerada por meio de um procedimento de três passos. Para refinar uma solução, usamos os procedimentos Randomized Variable Neighborhood Descent (RVND) e Variable Neighborhood Descent (VND). Para não ficar preso em ótimos locais e explorar diferentes regiões do espaço de soluções do problema, aplicamos um procedimento para destruir a solução atual e outro para construí-la de forma gulosa. Para testar os algoritmos propostos, usamos instâncias com 579 localidades, dois depósitos, até 56 MMUs e 180 km entre dois locais no máximo. Realizamos os testes considerando três cenários diferentes. Esses cenários diferem entre si pelo número de localidades candidatas a serem atendidas, o número de MMUs disponíveis em cada depósito e a capacidade dessas MMUs. Os resultados mostraram que os dois algoritmos encontraram soluções que atendem integralmente a demanda da região estudada. O Smart IGS-VND obteve um melhor desempenho para encontrar um valor alvo de demanda previamente definido. No entanto, quando foram comparadas a distância total percorrida pelas MMUs com a cobertura de exames, o Smart IGS-RVND mostrou ser capaz de encontrar soluções de melhor qualidade, reduzindo a distância total percorrida pelos veículos. No último cenário, apresentamos um plano de serviço mensal para uma MMU, variando de um a doze meses.
  • No Thumbnail Available
    Item
    Algoritmos meta-heurísticos para o problema dial-a-ride.
    (2019) Souza, André Luyde da Silva; Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas; Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas; Santos, André Gustavo dos; Toffolo, Túlio Ângelo Machado
    Este trabalho trata do problema Dial-a-Ride, que consiste em fazer rotas para veículos com a finalidade de transportar pacientes de diferentes locais para realizar exames médicos em unidades de tratamento de saúde. O Dial-a-Ride é uma extensão do Problema de Roteamento de Veículos, possuindo características do Problema de Roteamento de Veículos com Janela de Tempo e do Problema de Roteamento de Veículos com Coleta e Entrega, combinados com restrições relativas aos pacientes. O trabalho considera a forma estática do problema e utiliza dados obtidos da Prefeitura Municipal de Ouro Preto-MG para modelagem e contextualização do problema. Para resolvê-lo, propõe-se dois algoritmos heurísticos, MS-VNS1 e VNS2, ambos baseados na meta-heurística Variable Neighborhood Search (VNS). O primeiro, MSVNS1, é guiado pela meta-heurística Multi-Start tendo como busca local o VNS. O segundo, por sua vez, é guiado apenas pelo VNS. Nos dois algoritmos o método de busca local do VNS é o procedimento heurístico Randomized Variable Neighborhood Descent (RVND), o qual usa os movimentos de realocação, troca e cruzamento para explorar o espaço de soluções do problema. Os resultados computacionais foram obtidos pela aplicação dos algoritmos em um conjunto de instâncias da literatura e comparados com os das melhores soluções desta variante do problema. Apesar de simples, os algoritmos desenvolvidos foram capazes de encontrar a solução ótima para algumas instâncias e soluções de boa qualidade para as demais. Os algoritmos também foram testados em um conjunto de instâncias criadas a partir de dados fornecidos pela Prefeitura Municipal de Ouro Preto-MG. Ambos se mostraram capazes de atender as demandas da cidade de Ouro Preto de forma automatizada, proporcionando ao setor de transporte da prefeitura uma ferramenta que possibilita reduzir os custos com o transporte de pacientes e diminuir a alocação de funcionários para cumprir essa atividade.
  • No Thumbnail Available
    Item
    An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems.
    (2013) Masson, Renaud; Vidal, Thibaut Victor Gaston; Michallet, Julien; Penna, Puca Huachi Vaz; Petrucci, Vinicius; Subramanian, Anand; Dubedout, Hugues
    This paper proposes an efficient Multi-Start Iterated Local Search for Packing Problems (MS-ILS-PPs) metaheuristic for Multi-Capacity Bin Packing Problems (MCBPP) and Machine Reassignment Problems (MRP). The MCBPP is a generalization of the classical bin-packing problem in which the machine (bin) capacity and task (item) sizes are given by multiple (resource) dimensions. The MRP is a challenging and novel optimization problem, aimed at maximizing the usage of available machines by reallocating tasks/processes among those machines in a cost-efficient manner, while fulfilling several capacity, conflict, and dependency-related constraints. The proposed MS-ILS-PP approach relies on simple neighborhoods as well as problem-tailored shaking procedures. We perform computational experiments on MRP benchmark instances containing between 100 and 50,000 processes. Near-optimum multi-resource allocation and scheduling solutions are obtained while meeting specified processing-time requirements (on the order of minutes). In particular, for 9/28 instances with more than 1000 processes, the gap between the solution value and a lower bound measure is smaller than 0.1%. Our optimization method is also applied to solve classical benchmark instances for the MCBPP, yielding the best known solutions and optimum ones in most cases. In addition, several upper bounds for non-solved problems were improved.
  • No Thumbnail Available
    Item
    An iterated local search heuristic for the heterogeneous fleet vehicle routing problem.
    (2013) Penna, Puca Huachi Vaz; Subramanian, Anand; Ochi, Luiz Satoru
    This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP is NP-hard since it is a generalization of the classical Vehicle Routing Problem (VRP), in which clients are served by a heterogeneous fleet of vehicles with distinct capacities and costs. The objective is to design a set of routes in such a way that the sum of the costs is minimized. The proposed algorithm is based on the Iterated Local Search (ILS) metaheuristic which uses a Variable Neighborhood Descent procedure, with a random neighborhood ordering (RVND), in the local search phase. To the best of our knowledge, this is the first ILS approach for the HFVRP. The developed heuristic was tested on well-known benchmark instances involving 20, 50, 75 and 100 customers. These test-problems also include dependent and/or fixed costs according to the vehicle type. The results obtained are quite competitive when compared to other algorithms found in the literature.
  • No Thumbnail Available
    Item
    Bi-objective optimization model for the heterogeneous dynamic dial-a-ride problem with no rejects.
    (2021) Souza, André L. S.; Pinto, Marcella Bernardo; Penna, Puca Huachi Vaz; Pannek, Jürgen; Souza, Marcone Jamilson Freitas
    This work proposes a bi-objective mathematical optimization model and a two-stage heuristic for a real-world application of the heterogeneous Dynamic Dial-a-Ride Problem with no rejects, i.e., a patient transportation system. The problem consists of calculating route plans to meet a set of transportation requests by using a given heterogeneous vehicle fleet. These transportation requests can be either static or dynamic, and all of them must be attended to. In the first stage of the proposed heuristic, the problem’s static part is solved by applying a General Variable neighborhood Search based algorithm. In the second stage, the dynamic requests are dealt with by implementing a simple insertion heuristic. We create different instances based on the real data provided by a Brazilian city’s public health care system and test the proposed approach on them. The analysis of the results shows that the higher the level of dynamism, i.e., the number of urgent requests on each instance, the smaller the objective function value will be in the static part. The results also demonstrate that a higher level of dynamism increases the chance of a time window violation happening. Besides, we use the weighted sum method of the two conflicting objectives to analyze the trade-off between them and create an approximation for the Pareto frontier.
  • No Thumbnail Available
    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, Anand
    The 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.
  • No Thumbnail Available
    Item
    Exact and heuristic approaches to truck–drone delivery problems.
    (2023) Freitas, Júlia Cária de; Penna, Puca Huachi Vaz; Toffolo, Túlio Ângelo Machado
    Collaborative delivery employing drones in last-mile delivery has been an extensively studied topic in recent years. In this paper, it is studied Truck–Drone Delivery Problems (TDDPs) in which a traditional delivery truck is gathered with a drone to cut delivery times and costs. The vehicles work together in a hybrid operation involving one drone launching from a larger vehicle that operates as a mobile depot and a recharging platform. 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 a novel Mixed Integer Programming (MIP) formulation and a heuristic approach to address the problem. The proposed MIP formulation yields better linear relaxation bounds than previously proposed formulations for all instances, and was capable of optimally solving several unsolved instances from the literature. A hybrid heuristic based on the General Variable Neighborhood Search metaheuristic combining Tabu Search concepts is employed to obtain high-quality solutions for large-size instances. The efficiency of the algorithm was evaluated on 1415 benchmark instances from the literature, and over 80% of the best known solutions were improved.
  • No Thumbnail Available
    Item
    Gathering data in wireless sensor networks by drone.
    (2020) Rezende, Josiane da Costa Vieira; Souza, Marcone Jamilson Freitas; Silva, Rone Ilídio da; Souza, Marcone Jamilson Freitas; Teixeira, Fernando Augusto; Coelho, Igor Machado; Ochi, Luiz Satoru; Penna, Puca Huachi Vaz; Coelho, Vitor Nazário; Silva, Rone Ilidio da
    The benefits of using mobile sinks or data mules for data collection in Wireless Sensor Network (WSN) have been studied in several studies. However, most of them consider only the WSN limitations and sensor nodes having no more than one data packet to transmit. This paper considers each sensor node having a relatively larger volume of data stored in its memory. That is, they have several data packets to send to sink. We also consider a drone with hovering capability, such as a quad-copter, as a mobile sink to gather this data. Hence, the mobile collector eventually has to hover to guarantee that all data will be received. Drones, however, have a limited power supply that restricts their flying time. Hence, the drone’s energy cost must also be considered to increase the amount of collected data from the WSN. This work investigates the problem of determining the best drone tour for data gathering in a WSN. We focus on minimizing the overall drone flight time needed to collect all data from the WSN. We propose an algorithm to create a subset of sensor nodes to send data to the drone during its movement and, consequently, reduce its hovering time. The proposed algorithm guarantees that the drone will stay a minimum time inside every sensor node’s radio range. The computational experiments showed that our proposal significantly outperforms the state-of-the-art methods in finding drone tours in this type of scenario.
  • No Thumbnail Available
    Item
    Uma heurística híbrida para minimizar custos com antecipação e atraso do sequenciamento da produção em uma máquina.
    (2012) Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas; Gonçalves, Frederico Augusto de Cezar Almeida; Ochi, Luiz Satoru
    Este trabalho tem seu foco no problema de sequenciamento em uma máquina com penalidades por antecipação e atraso da produção. São considerados tempos de preparação da máquina dependentes da sequência de produção, bem como a existência de janelas de entrega distintas. Para resolução do problema, desenvolveu-se um algoritmo heurístico de 3 fases, nomeado GTSPR. A primeira fase baseada em GRASP é descida em vizinhança variável para a geração da solução inicial, a segunda fase baseada em busca tabu para refinamento da solução, e por fim a reconexão por caminhos como estratégia de pós-otimização, na terceira fase. Para cada sequência gerada pela heurística é utilizado um algoritmo de tempo polinomial para determinar a data ótima de início de processamento de cada tarefa. Os resultados computacionais mostraram que o algoritmo GTSPR supera outros algoritmos da literatura, tanto com relação à qualidade da solução final quanto em relação à variabilidade dessas soluções.
  • No Thumbnail Available
    Item
    Heurísticas matemáticas aplicadas ao problema de carregamento de contêineres.
    (2020) Oliveira, Kelly Márcia de; Toffolo, Túlio Ângelo Machado; Toffolo, Túlio Ângelo Machado; Penna, Puca Huachi Vaz; Silva, Everton Fernandes da
    Este trabalho tem seu foco no Problema de Carregamento de Contêineres (CLP, do inglês Container Loading Problem). Neste problema, deseja-se alocar caixas de forma retangular em contêineres de modo que todas as caixas sejam alocadas e o volume total dos contêineres usados seja o menor possível. Devido ao crescente número de encomendas enviadas mundialmente, há uma demanda por parte das empresas e da sociedade por métodos para alocar caixas em contêineres de forma eficiente. Ao realizar o carregamento de caixas, as seguintes restrições devem ser satisfeitas: todas as caixas devem ser alocadas; caixas não podem se sobrepor dentro de um contêiner; e caixas devem ser alocadas inteiramente dentro da área do contêiner. Este trabalho propõe duas heurísticas matemáticas para o CLP, baseadas em Relax-and-fix e Local Branching. As duas estratégias utilizam métodos construtivos para produzir uma solução inicial e, em seguida, realizam uma busca local utilizando um modelo de programação inteira mista. Embora o Local Branching, assim como o Relax-and-fix, tenha sido capaz de encontrar uma solução até pouco tempo desconhecida para uma instância, resultados indicam que o Relax-and-fix é um método mais promissor, pois é capaz de gerar mais soluções de qualidade, igualando por muitas vezes o melhor resultado conhecido na literatura.
  • No Thumbnail Available
    Item
    Heurísticas matemáticas para o problema de escalonamento em máquinas paralelas não relacionadas com tempo de preparo e sequência dependente.
    (2021) Figueiroa, Guilherme Baumgratz; Toffolo, Túlio Ângelo Machado; Fonseca, George Henrique Godim da; Toffolo, Túlio Ângelo Machado; Fonseca, George Henrique Godim da; Cota, Luciano Perdigão; Penna, Puca Huachi Vaz
    O Problema de Sequenciamento em Máquinas Paralelas Não Relacionadas considera um conjunto de tarefas e um conjunto de máquinas homogêneas ou heterogêneas que trabalham em paralelo. Todas as tarefas do conjunto devem ser processadas, sendo necessário escolher em qual máquina cada tarefa será executada. O objetivo é escalonar as tarefas nas máquinas de forma a minimizar o tempo total necessário para executar todas as tarefas, conhecido como makespan, dado pela máquina com maior tempo de processamento. Este trabalho estuda um caso do problema em que as tarefas são independentes, as máquinas heterogêneas e existe um tempo de preparo para execução de cada tarefa, que pode variar dependendo da sequência das tarefas e da máquina. Os principais modelos matemáticos propostos para o problema foram avaliados utilizando o conjunto de instâncias apresentado por Vallada e Ruiz (2011). Dentre os modelos e métodos analisados, o modelo proposto por Avalos-Rosales et al. (2015) e o algoritmo exato proposto por Fanjul-Peyro et al. (2019) obtiveram os melhores resultados tanto em termos de qualidade de solução quanto em termos de tempo de processamento. Assim, com o intuito de abordar instâncias maiores do problema, este trabalho propõe o uso de heurísticas matemáticas Fix-And-Optimize que utilizando os principais modelos disponíveis na literatura. As metodologias propostas consistem em decompor de forma heurística o problema por meio da fixação de um conjunto de tarefas e máquinas. Cada fixação resulta em um subproblema que pode ser resolvido por um modelo matemático ou método exato. Duas variações do algoritmos foram avaliadas, usando os modelos de Avalos-Rosales et al. (2015) e Fanjul-Peyro et al. (2019). Os resultados computacionais mostram que ambos algoritmos propostos obtêm valores próximos do melhor conhecido na literatura. Foram obtidas, ainda, diversas soluções melhores do que a melhor conhecida até então. Dentre as duas abordagens propostas, o algoritmo que utiliza o método de Fanjul-Peyro et al. (2019) para resolver subproblemas obteve os melhores resultados, sendo capaz de obter soluções melhores do que a melhor da literatura para 338 das 1000 instâncias de grande porte consideradas.
  • No Thumbnail Available
    Item
    A hybrid algorithm for the heterogeneous fleet vehicle routing problem.
    (2012) Subramanian, Anand; Penna, Puca Huachi Vaz; Barboza, Eduardo Uchoa; Ochi, Luiz Satoru
    This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP generalizes the classical Capacitated Vehicle Routing Problem by considering the existence of different vehicle types, with distinct capacities and costs. The objective is to determine the best fleet composition as well as the set of routes that minimize the total costs. The proposed hybrid algorithm is composed by an Iterated Local Search (ILS) based heuristic and a Set Partitioning (SP) formulation. The SP model is solved by means of a Mixed Integer Programming solver that interactively calls the ILS heuristic during its execution. The developed algorithm was tested in benchmark instances with up to 360 customers. The results obtained are quite competitive with those found in the literature and new improved solutions are reported.
  • No Thumbnail Available
    Item
    Hybrid data mining heuristics for the heterogeneous fleet vehicle routing problem.
    (2018) Maia, Marcelo Rodrigues de Holanda; Carvalho, Alexandre Plastino de; Penna, Puca Huachi Vaz
    The vehicle routing problem consists of determining a set of routes for a fleet of vehicles to meet the demands of a given set of customers. The development and improvement of techniques for finding better solutions to this optimization problem have attracted considerable interest since such techniques can yield significant savings in transportation costs. The heterogeneous fleet vehicle routing problem is distinguished by the consideration of a heterogeneous fleet of vehicles, which is a very common scenario in real-world applications, rather than a homogeneous one. Hybrid versions of metaheuristics that incorporate data mining techniques have been applied to solve various optimization problems, with promising results. In this paper, we propose hybrid versions of a multi-start heuristic for the heterogeneous fleet vehicle routing problem based on the Iterated Local Search metaheuristic through the incorporation of data mining techniques. The results obtained in computational experiments show that the proposed hybrid heuristics demonstrate superior performance compared with the original heuristic, reaching better average solution costs with shorter run times.
  • No Thumbnail Available
    Item
    A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet.
    (2019) Penna, Puca Huachi Vaz; Subramanian, Anand; Ochi, Luiz Satoru; Vidal, Thibaut Victor Gaston; Prins, Christian
    We consider a family of rich vehicle routing problems (RVRP) which have the particularity to combine a heterogeneous fleet with other attributes, such as backhauls, multiple depots, split deliveries, site dependency, open routes, duration limits, and time windows. To efficiently solve these problems, we propose a hybrid metaheuristic which combines an iterated local search with variable neighborhood descent, for solution improvement, and a set partitioning formulation, to exploit the memory of the past search. Moreover, we investigate a class of combined neighborhoods which jointly modify the sequences of visits and perform either heuristic or optimal reassignments of vehicles to routes. To the best of our knowledge, this is the first unified approach for a large class of heterogeneous fleet RVRPs, capable of solving more than 12 problem variants. The efficiency of the algorithm is evaluated on 643 well-known benchmark instances, and 71.70% of the best known solutions are either retrieved or improved. Moreover, the proposed metaheuristic, which can be considered as a matheuristic, produces high quality solutions with low standard deviation in comparison with previous methods. Finally, we observe that the use of combined neighborhoods does not lead to significant quality gains. Contrary to intuition, the computational effort seems better spent on more intensive route optimization rather than on more intelligent and frequent fleet re-assignments.
  • No Thumbnail Available
    Item
    A hybrid iterative local search algorithm for the electric fleet size and mix vehicle routing problem with time windows and recharging stations.
    (2016) Penna, Puca Huachi Vaz; Afsar, Hasan Murat; Prins, Christian; Prodhon, Caroline
    As the cities around the world become larger, quality of life of the citizens is more and more threatened due to the traffic congestion, energy consumption, noise disturbance and carbon emissions because of of increasing transport. Electrical vehicles present an opportunity to reduce greenhouse gas emissions. But limited driving range and long recharging times are among the challenges that the research community has to face. This paper proposes an iterative local search algorithm coupled with a set partitioning model to solve The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations. Several types of electrical vehicles with varying driving range, capacity and fixed cost should service a set of customers within their time limits and during their tours each vehicle can be recharged in stations. We show the efficiency and the quality of our method by solving benchmark instances of the Heterogeneous Fleet Electric Vehicle Problems with Time Windows.
  • No Thumbnail Available
    Item
    Large neighborhoods with implicit customer selection for vehicle routing problems with profits.
    (2015) Vidal, Thibaut Victor Gaston; Maculan Filho, Nelson; Ochi, Luiz Satoru; Penna, Puca Huachi Vaz
    We consider several vehicle routing problems (VRP) with profits, which seek to select a subset of customers, each one being associated with a profit, and to design service itineraries. When the sum of profits is maximized under distance constraints, the problem is usually called the team orienteering problem. The capacitated profitable tour problem seeks to maximize profits minus travel costs under capacity constraints. Finally, in the VRP with a private fleet and common carrier, some customers can be delegated to an external carrier subject to a cost. Three families of combined decisions must be taken: customer’s selection, assignment to vehicles, and sequencing of deliveries for each route. We propose a new neighborhood search for these problems, which explores an exponential number of solutions in pseudo-polynomial time. The search is conducted with standard VRP neighborhoods on an exhaustive solution representation, visiting all customers. Since visiting all customers is usually infeasible or suboptimal, an efficient select algorithm, based on resource constrained shortest paths, is repeatedly used on any new route to find the optimal subsequence of visits to customers. The good performance of these neighborhood structures is demonstrated by extensive computational experiments with a local search, an iterated local search, and a hybrid genetic algorithm. Intriguingly, even a local-improvement method to the first local optimum of this neighborhood achieves an average gap of 0.09% on classic team orienteering benchmark instances, rivaling with the current state-of-the-art metaheuristics. Promising research avenues on hybridizations with more standard routing neighborhoods are also open.
  • No Thumbnail Available
    Item
    Localização de mamógrafos : um estudo de caso para novos investimentos em Rondônia.
    (2023) Paiva, Jéssica Natália Miranda; Rosa, Patrick Moreira; Penna, Puca Huachi Vaz; Monteiro, Janne Cavalcante; Lisboa, Maillene Rodrigues; Souza, Marcone Jamilson Freitas
    O acesso a mamografia é diretriz estruturante do cuidado às mulheres no diagnóstico precoce do câncer de mama, devendo estar acessível a 60 km, no máximo, no Brasil. No entanto, essa não é a realidade para parte da população brasileira. Neste trabalho, trata-se o problema de localização de mamógrafos no Sistema Público de Saúde do Estado de Rondônia. O objetivo foi desenvolver dois modelos logísticos de localização baseados no acesso para maximizar a cobertura de exames, minimizar o número de equipamentos a serem adquiridos e a distância do atendimento. Os modelos se diferem pelo atendimento parcial ou total de uma localidade. Foram analisados vários cenários e os resultados mostraram que, com os modelos propostos e a utilização das atuais microrregiões de saúde, as soluções obtidas possibilitam uma distribuição espacial dos mamógrafos mais equilibrada e acessível, com aumento quantitativo e geográfico da cobertura de exames.
  • No Thumbnail Available
    Item
    A mathematical formulation and heuristic algorithms for minimizing the makespan and energy cost under time-of-use electricity price in an unrelated parallel machine scheduling problem.
    (2022) Rego, Marcelo Ferreira; Souza, Marcone Jamilson Freitas; Cota, Luciano Perdigão; Souza, Marcone Jamilson Freitas; Cota, Luciano Perdigão; Penna, Puca Huachi Vaz; Coelho, Igor Machado; Arroyo, José Elias Claudio; Batista, Lucas de Souza
    Em muitos países, o preço da energia varia de acordo com a política time-of-use. Como regra geral, é vantajoso financeiramente para as indústrias planejarem sua produção considerando essa política. Esta tese apresenta um novo problema de sequenciamento de máquinas paralelas não-relacionadas bi-objetivo com tempos de preparação dependentes da sequência, no qual os objetivos são minimizar o makespan e o custo total de energia considerando máquinas com diferentes modos de operação e que o preço da eletricidade segue a política time-of-use. Introduzimos uma formulação de programação linear inteira mista e aplicamos o método da soma ponderada para obter uma fronteira Pareto. Também desenvolvemos métodos de otimização multiobjetivo, baseados no Multi-objective Variable Neighborhood Search com procedimento de intensificação (chamado MOVNS2) e o Non-dominated Sorting Genetic Algorithm II (NSGA-II), para tratar instâncias grandes, com pelo menos 50 tarefas, uma vez que a formulação não pode resolvê-las em um tempo computacional aceitável para a tomada de decisão. Comparamos o desempenho dos algoritmos NSGA-II e MOVNS2 com dois algoritmos de otimização multiobjetivo da literatura, o MOVNS1 e o NSGA-I, em relação às métricas de hipervolume e hierarchical cluster counting (HCC). Os resultados mostraram que os métodos propostos são capazes de encontrar uma boa aproximação para a fronteira Pareto comparado com os resultados do método de soma ponderada em instâncias pequenas, de até 10 tarefas. Quando consideramos apenas as instâncias grandes, o MOVNS2 é superior ao MOVNS1, o NSGA-I e o NSGA-II em relação à métrica de hipervolume. Além disso, o NSGA-II supera os métodos de otimização multiobjetivo NSGA-I, MOVNS1 e MOVNS2 em relaçãoo à métrica HCC. Ambos os resultados apresentam um nível de confiança de 95%. Assim, o MOVNS2 proposto é capaz de encontrar soluções não-dominadas com boa convergência e o NSGA-II com boa diversidade.