Spelling suggestions: "subject:"metaheuristicas"" "subject:"metaheuristic""
1 |
[pt] ABORDAGEM METAHEURÍSTICA PARA O ROTEAMENTO DE VEÍCULOS ESCOLARES EM ZONA RURAL / [en] METAHEURISTIC APPROACH TO THE SCHOOL BUS ROUTING PROBLEM IN A RURAL AREALETICIA CALDAS DOS SANTOS 28 December 2021 (has links)
[pt] O transporte escolar é fundamental para garantir o acesso e permanência
dos alunos nas escolas públicas, principalmente nas áreas rurais, onde os
estudantes estão localizados em uma grande área com baixa densidade e as
estradas encontram-se em situações precárias. O presente trabalho tem como
objetivo aplicar a metaheurística Iterated Local Search para o roteamento de
13.664 alunos da zona rural do estado do Rio de Janeiro. Para isso, considerouse
o problema de roteamento de veículo escolares, do inglês School Bus Routing
Problem (SBRP), com frota heterogênea e escola única, com o objetivo de
minimizar o custo total considerando as restrições de capacidade dos veículos
e distância máxima de percurso. Para aplicação do método, foram considerados
os dados fornecidos pela Secretaria de Estado de Educação do Rio de Janeiro
(SEEDUC-RJ). Os resultados são apresentados em dois cenários, o primeiro
considera os dados de 79 rotas utilizadas pela SEEDUC-RJ para comparação
dos resultados obtidos com o ILS. O método mostrou uma redução de 40,5 por cento no custo médio das rotas e 46 or cento na quilometragem média por aluno. O segundo
cenário considera o roteamento da totalidade dos alunos, que foram divididos
em 506 instâncias considerando escola e turno. A maior instância roteada
possui 534 alunos. Os resultados consolidados por município são apresentados
e mostram a concentração de municípios com maior custo médio por rota
no noroeste fluminense. A implementação das rotas propostas pode trazer
economia significativa com as despesas relacionadas ao transporte escolar rural,
além de indicar um aumento no nível de serviço para os estudantes, com
redução da quilometragem média por aluno. / [en] School transport is essential to ensure access and permanence of students
in public schools, especially in rural areas, where students are located in
a large area with low density and roads are in precarious conditions. This
work aims to apply the Iterated Local Search metaheuristic to route 13.664
rural students in the state of Rio de Janeiro. For this, we considered the
School Bus Routing Problem (SBRP), with heterogeneous fleet and single
school, in order to minimize the total cost considering the vehicles capacity
constraints and maximum travel distance. To apply the method, the data
provided by Secretaria de Estado de Educação do Rio de Janeiro (SEEDUCRJ)
were considered. The results are presented in two scenarios, the first
considers data from 79 routes used by SEEDUC-RJ to compare the results
obtained with the ILS. The method showed a reduction of 40.5 percent in the
average cost of routes and 46 percent in the average mileage per student. The
second scenario considers the routing of all students, who were divided into
506 instances considering school and shift. The largest routed instance has
534 students. The results consolidated by municipality are presented and show
the concentration of municipalities with the highest average cost per route in
northwestern Rio de Janeiro. The implementation of the proposed routes can
bring significant savings with expenses related to rural school transport, in
addition to indicating an increase in the level of service for students, with a
reduction in the average mileage per student.
|
2 |
[en] RESCHEDULING OF OIL EXPLORATION SUPPORT VESSELS WITHIN A METAHEURISTIC APPROACH / [pt] REPROGRAMAÇÃO DE EMBARCAÇÕES DE APOIO À EXPLORAÇÃO DE PETRÓLEO ATRAVÉS DE UMA ABORDAGEM METAHEURÍSTICAVICTOR ABU-MARRUL CARNEIRO DA CUNHA 09 August 2017 (has links)
[pt] A dissertação aborda um problema real de reprogramação de uma frota de embarcações do tipo PLSV (Pipe Laying Support Vessel), responsáveis pelas interligações de poços petrolíferos submarinos. O cronograma de curto prazo dessas embarcações está sujeito à inúmeras incertezas inerentes às operações realizadas,
acarretando em ociosidade nas embarcações ou postergações na produção de petróleo, que podem resultar em prejuízo de milhões de reais. Uma metaheurística ILS (Iterated Local Search) é proposta para atender a frequente demanda por reprogramações dos PLSVs. O método é composto de uma fase inicial de
viabilização, para tratar potenciais inconsistências nas programações. Na sequência, iterativamente, são realizadas perturbações na solução por meio de movimentos de swap e aplicada uma busca local baseada na vizinhança insert, a fim de fugir de ótimos locais e encontrar soluções que aprimorem o cronograma. Foram feitos experimentos com diferentes parâmetros e critérios do ILS, sendo definidas duas abordagens aplicadas a dez instâncias oriundas de uma programação real de PLSVs. A partir de uma função de avaliação, capaz de medir o impacto operacional na programação, o ILS proporcionou uma melhoria média nos cronogramas acima de 91 por cento, quando comparados aos cronogramas originais. As soluções foram obtidas em um tempo computacional médio de 30 minutos, aderente ao processo da companhia. Em função dos resultados alcançados, o método provou ser uma boa base para uma ferramenta de apoio à decisão para a reprogramação dos PLSVs. / [en] This dissertation addresses a real-life rescheduling problem of a Pipe Laying Support Vessels (PLSVs) fleet, in charge of subsea oil wells interconnections. The short-term schedule of these vessels is subject to uncertainties inherent to its operations, resulting in ships idleness or delays in oil production, which may lead to losses of millions of Brazilian Reais. A method based on the ILS (Iterated Local Search) metaheuristic is proposed to meet the frequent demand of PLSVs rescheduling. The first step of this method aims to find a feasible initial solution from an incoming schedule with potencial inconsistencies. The following steps consists in, iteratively, performing a perturbation on a solution through swap movements and applying a local search based on the insertion neighborhood, in order to escape from local optimal and find better solutions. Extensive preliminary experiments were conducted considering different ILS parameters setups. The two most performing setups were selected and applied to ten instances of a real PLSV schedule. Taking into account an objective function that measures the operational impact on schedules, the ILS provided an average improvement above 91 percent in schedules when compared to the original planning. These solutions were obtained in an average computational time of 30 minutes, which fits in the company process. The obtained results showed that the proposed method might be a basis for a decision support tool for the PLSVs rescheduling problem.
|
3 |
[pt] PLANEJAMENTO DA EXPANSÃO DA TRANSMISSÃO COM CRITÉRIOS DE SEGURANÇA VIA ALGORITMO GENÉTICO ESPECIALIZADO / [en] TRANSMISSION EXPANSION PLANNING WITH SECURITY CRITERIA VIA SPECIALIZED GENETIC ALGORITHMIAMBERG SOUZA DA SILVA 12 January 2021 (has links)
[pt] A solução do problema de planejamento da expansão da transmissão (PET)
tem por objetivo geral identificar reforços a serem construídos na rede de forma a
garantir a adequada interligação entre carga e geração, previstos para um determinado
horizonte de estudo. No processo de solução desse problema, busca-se manter
o equilíbrio ótimo entre os custos envolvidos (investimento e operação) e os
níveis de qualidade e desempenho na operação do sistema reforçado. Nesse sentido,
é proposta nesta dissertação de mestrado uma ferramenta de otimização especializada
para solução do problema PET, a qual é baseada na técnica metaheurística
Algoritmo Genético. A ferramenta proposta, denominada Algoritmo Genético
Especializado (AGE-PET), faz uso de informações heurísticas fundamentadas em
análises atualizadas de fluxo de potência da rede realizadas durante o processo
evolutivo de solução do problema. Essas informações heurísticas são traduzidas
por meio de índices de sensibilidade, os quais são integrados aos operadores genéticos
inerentes à ferramenta, conduzindo a solução do problema na direção de planos
de expansão de boa qualidade. Para análise e validação da metodologia proposta,
é solucionado o problema PET estático de longo prazo, considerando o modelo
linearizado DC com perdas ôhmicas e atendimento do critério de segurança
N-1 para a rede de transmissão. Sistemas elétricos de transmissão com diferentes
características e dimensões, incluindo um subsistema atual da rede interligada
brasileira, são empregados nos estudos realizados. / [en] The main goal in the solution of the transmission expansion planning (TEP)
is to identify reinforcements to be built in the network in order to guarantee the
adequate interconnection between load and electric power generation, both foreseen
for a given future planning horizon. In the process of solving this problem,
the aim is to maintain the optimal balance between the costs involved (investment
and operation) and the levels of quality and performance in the operation of the
reinforced system. Thus, it is proposed in this dissertation a specialized optimization
tool for solving the TEP problem, which is based on the metaheuristic Genetic
Algorithm technique. The proposed tool, called Specialized Genetic Algorithm
(SGA-TEP), makes use of heuristic information based on updated network power
flow analyses carried out during the evolutionary process of solving the problem.
This heuristic information is translated by means of sensitivity indices, which are
integrated with the genetic operators inherent to the tool, leading to the solution of
the problem in the direction of good quality expansion plans. For analysis and
validation of the proposed methodology, the long-term static TEP problem is
solved, considering the linearized DC model with ohmic losses and the compliance
of the N-1 security criterion for the transmission network. Electric transmission
systems with different characteristics and dimensions, including a recent
subsystem of the Brazilian interconnected grid, are used in the case studies.
|
4 |
[pt] PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM MOTORISTAS OCASIONAIS PARA ENTREGAS DE LAST-MILE: UMA ABORDAGEM META-HEURÍSTICA / [en] VEHICLE ROUTING PROBLEM WITH OCCASIONAL DRIVERS FOR E-COMMERCE LAST-MILE DELIVERY: A METAHEURISTIC APPROACHMATHEUS OLIVEIRA MEIRIM 25 September 2023 (has links)
[pt] Nos últimos anos o comércio eletrônico tem se difundido na sociedade e a logística de entrega dos produtos é um dos pilares para que este mercado mantenha o nível de serviço alto e continue sendo vantajoso para o consumidor decidir por realizar a compra pela internet. O presente trabalho se destina a estudar sobre o problema de roteamento de veículos de entrega last-mile para e-commerce e aplicar a metaheurística Iterated Local Search (ILS) visando otimizar o roteamento do trecho last-mile de encomendas realizadas em uma empresa de comércio eletrônico brasileira. Com o objetivo de encontrar rotas de menor custo para as entregas a serem realizadas, este trabalho propõe uma extensão para o Vehcile Routing Problem With Occasional Drivers (VRPOD),considerando frota heterogênea e motoristas ocasionais realizando o transporte de mais de uma entrega. Para a aplicação do método foram utilizados dados fornecidos por uma empresa de e-commerce que foram devidamente anonimizados de forma a não ser possível identificar a empresa e nem os clientes, respeitando os princípios éticos. Foram utilizadas 121 instâncias, sendo a menor com um vértice e a maior com 344. Os resultados do modelo proposto são apresentados em dois cenários, primeiramente considerando que o roteamento é realizado sem a utilização de motoristas ocasionais. O segundo cenário considera a disponibilização de motoristas ocasionais para serem utilizados em algumas rotas. Ambos os cenários foram comparados com as rotas geradas pelo roteador existente hoje na companhia e os resultados preliminares indicam que o sem a utilização de motoristas ocasionais o ILS proposto obtém melhores soluções em 53.72 por cento das instâncias e quando os motoristas ocasionais são incorporados a rota ocorre melhoria em 76.03 por cento das instâncias utilizadas. A utilização de motoristas ocasionais também proporciona uma redução de 10.30 por cento no custo médio de roteamento. / [en] In recent years, e-commerce has become widespread in society, and the
logistics of product delivery is a crucial pillar for this market to maintain
a high level of service and remain advantageous for consumers choosing to
make purchases online. The present work aims to study the problem of last-mile vehicle routing for e-commerce deliveries and apply an Iterated Local
Search (ILS) metaheuristic to optimize the routing of parcels in a Brazilian e-commerce company. With the objective of finding routes with the lowest cost
for the deliveries, this study proposes an extension to the Vehicle Routing
Problem with Occasional Drivers (VRPOD), considering a heterogeneous
fleet and occasional drivers handling multiple deliveries. For the methodology
application, data provided by an e-commerce company are used, and they
are properly anonymized to prevent the identification of the company and
its clients, respecting ethical principles. A total of 121 instances are used,
ranging from the smallest with one vertex to the largest with 344. The results of
the proposed model are presented in two scenarios: firstly, considering routing
without the use of occasional drivers, and secondly, considering the availability
of occasional drivers for some routes. Both scenarios are compared with the
routes generated by the current router used in the company, and preliminary
results indicate that without the use of occasional drivers, the proposed ILS
obtains better solutions in 53.72 percent of the instances, and when occasional drivers
are incorporated into the route, improvements occur in 76.03 percent of the instances.
The utilization of occasional drivers also provides a 10.30 percent reduction in the
average routing cost.
|
Page generated in 0.0613 seconds