Spelling suggestions: "subject:"1inear programming"" "subject:"alinear programming""
21 |
[en] MODELS AND ALGORITHMS FOR THE GENERALIZED ASSIGNMENT PROBLEM (PAG) AND APPLICATIONS / [pt] MODELOS E ALGORITMOS PARA O PROBLEMA DE ALOCAÇÃO GENERALIZADA (PAG) E APLICAÇÕESALEXANDRE ALTOE PIGATTI 17 November 2003 (has links)
[pt] Esta dissertação estuda modelos e algoritmos para o
Problema de Alocação Generalizada (PAG) . A motivação para
este estudo foi uma nova aplicação do PAG: o Problema de
Carregamento de Caminhões (PCC) . A pesquisa desenvolvida
concentra-se no estudo e na proposta de algoritmos
aproximados (metaeurísticas) e exatos para a resolução do
PAG. Os algoritmos aproximados propostos baseiam-se em um
conceito recentemente criado por Fischetti e Lodi (2003),
que utiliza programação matemática inteira para a
exploração eficiente de vizinhanças mais abrangentes. Os
resultados obtidos foram comparáveis aos melhores
conhecidos, com a vantagem de exigir um esforço pequeno de
implementação e um menor tempo de processamento. O
algoritmo exato proposto é um algoritmo de branch-and-cut-
and-price, que tem como ponto de partida o algoritmo
de branch-and-price de Savelsbergh (1997). Técnicas de
estabilização da geração de colunas similares às propostas
por Du Merle, Villeneuve, Desrosiers e Hansen (1999), foram
estudadas no âmbito desta dissertação, que experimenta
com diferentes implementações deste mecanismo. O algoritmo
de branch-andcut-and-price estabilizado demonstrou sua
eficiência ao resolver à otimalidade instâncias que se
encontravam em aberto na literatura. Finalmente,
experiências com PCC permitiram que os códigos
desenvolvidos pudessem ser avaliados em problemas reais. / [en] This dissertation tackles the Generalized Assignment
Problem (PAG), models and algorithms are studied and
proposed. This work was motivated by a real world
application: the Truck Loading Problem (PCC). Research was
done on approximated (metaheuristics) and exact algorithm
for solving the PAG. The approximated algorithms proposed
were based on a recent idea from Fischetti and Lodi (2003).
It uses integer programming to explore wider neighborhoods.
The results were compared to the best known, while
demanding much less implementation effort and using less
cpu time. The exact algorithm proposed is a branch-and-cut-
and-price developed from the branch-and-price algorithm of
Savelsbergh (1997). We used stabilized column generation
techniques similar to the one by Du Merle, Villeneuve,
Desrosiers and Hansen (1999), and devised experiments with
different implementations of this mechanism. The resulting
algorithm proved its efficiency by solving to optimality
open instances from the literature. Finally, experiments
with the PCC turned possible the evaluation of the codes
developed on real problems.
|
22 |
[en] EXACT ALGORITHMS FOR ARC AND NODE ROUTING PROBLEMS / [pt] ALGORITMOS EXATOS PARA PROBLEMAS DE ROTEAMENTO EM ARCOS E EM VÉRTICESRAFAEL MARTINELLI PINTO 19 January 2017 (has links)
[pt] Os problemas de roteamento estão entre os problemas combinatórios mais difíceis de encontrar limites melhores do que os existentes ou de provar novas soluções ótimas. Nesta tese, são abordados o Capacitated
Arc Routing Problem (CARP) e o Generalized Vehicle Routing Problem (GVRP). Em ambos os problemas, existe um conjunto de clientes os quais estão espalhados por um grafo dado, onde cada cliente possui uma demanda que deve ser atendida por exatamente um veículo de um conjunto de veículos idênticos. Os custos de travessia e o vértice de depósito são dados. O objetivo é encontrar rotas que coletam todas as demandas com custo mínimo, sem exceder a capacidade de nenhum veículo. No CARP, os clientes são um subconjunto de arestas, chamadas de arestas requireds, e para o GVRP, cada cliente é um subconjunto de vértices, chamado de grupo, onde cada grupo deve ser atendido visitando-se exatamente um vértice deste grupo. Além disto, vale notar que quando cada grupo possui apenas um vértice, o problema passa a ser o Capacitated Vehicle Routing Problem (CVRP). Primeiramente, são investigados métodos para melhorar os limites inferiores de instâncias de grande porte. É proposta a exploração da velocidade de uma heurística dual ascent para gerar cortes de capacidade. Em seguida, é apresentado um algoritmo de geração de colunas com um pricing eficiente para um tipo especial de rota não-elementar. O pricing proposto combina a técnica Decremental State-Space Relaxation (DSSR) com limites de complemento. Estas técnicas permitem o fortalecimento da regra de dominância entre as rotas, reduzindo drasticamente o número total de rótulos utilizados pela programação dinâmica. Finalmente, um algoritmo de branch-cut-and-price é criado o qual usa a geração de colunas e a separação de cortes previamente apresentadas. Além disto, este branch-cut-and-price é implementado usando strong branching e fixação por custo reduzido. Ao fim de cada parte, são apresentados resultados computacionais os quais avaliam a qualidade dos algoritmos propostos, os quais obtém novos limites inferiores para um grande número de instâncias do CARP e do GVRP. / [en] Routing problems stand among the hardest combinatorial problems to find high quality bounds or to prove new optimal solutions. In this thesis, we tackle the Capacitated Arc Routing Problem (CARP) and the
Generalized Vehicle Routing Problem (GVRP). For both problems, there are a set of customers spread over a given graph, where each customer has a demand which must be serviced by exactly one vehicle from a set of identical vehicles. The traversal costs and a depot vertex are given. The objective is to find routes that collect all the demands, without exceeding the capacity of any vehicle, at minimum cost. For the CARP, the customers are a subset of edges, called the required edges, and for the GVRP, each customer is a subset of vertices, called clusters, where each cluster must be serviced by visiting exactly one vertex of it. Furthermore, it is noteworthy that when every cluster contains just a single vertex, the problem is the Capacitated Vehicle Routing Problem (CVRP). Firstly, we investigate methods to improve lower bounds for large scale instances. We propose to explore the speed of a new dual ascent heuristic to generate capacity cuts. The quality of the cuts found is next improved with a new exact separation which is used in the linear program resolution that follows the dual heuristic. Following, we present a column generation algorithm with an efficient pricing for a special kind of non-elementary routes. The proposed pricing algorithm combines Decremental State-Space Relaxation(DSSR) technique with completion bounds. These techniques allow the strengthening of the domination rule between routes, drastically reducing the total number of labels used during the dynamic programming. Finally, we devise a branch-cut-and-price algorithm which uses the previously presented column generation and cut separation. Moreover, this branch-cutand- price is implemented using strong branching and reduced cost fixing. At the end of each part, we present computational experiments which evaluate the quality of the proposed algorithms and show new best lower bounds for a large number of CARP and GVRP instances.
|
23 |
[pt] MODELO DE LOCALIZAÇÃO-ALOCAÇÃO ÓTIMA DE SERVIDORES: ESTUDO DE CASO NA ANAC / [en] PERSONNEL OPTIMAL LOCATIONALLOCATION MODEL: CASE STUDY AT ANACCHRISTOPHER FEITOSA DA SILVA 19 May 2022 (has links)
[pt] Ao longo dos últimos anos o desenvolvimento da Pesquisa Operacional foi fundamental para o crescimento da indústria aérea. No Brasil, o órgão responsável pela fiscalização da aviação civil é a Agência Nacional de Aviação Civil (ANAC). O objetivo da dissertação é desenvolver um modelo de otimização para localização-alocação de pessoal (servidores) e aplicá-lo à um estudo de caso da ANAC, no contexto de Safety Oversight. Uma revisão sistematizada de literatura foi conduzida para identificar os gaps e soluções recentes na literatura de problemas de facility location. O objetivo descrito foi alcançado e o modelo matemático foi validado pelo Estudo de Caso proposto. O modelo alocou 31 porcento dos servidores da ANAC na Região Sudeste do Brasil, 25 porcento na Região Nordeste, 17 porcento na Região Norte, 17 porcento na Região Sul e 10 porcento na Região Centro-Oeste; reduzindo em 66 porcento a quantidade total de inspetores. Obteve-se ainda uma matriz de distribuição de capacitações por agência da ANAC, de
forma que o tomador de decisão possa analisar o perfil ótimo de habilitações dos funcionários de cada agência. Uma análise de sensibilidade foi conduzida para avaliar a flexibilidade do modelo, que se mostrou eficiente para aplicações em problemas reais. / [en] Over the last years, Research Operations development has become fundamental
for Aviation Industry. In Brazil, the agency responsible for Civil
Aviation inspection is the National Agency of Civil Aviation (ANAC). This
work aims the development of an optimal personnel location-allocation model
and application in a case study at ANAC in Safety Oversight context. One
Literature Review has been done for gaps identification and to find the most
recent solution techniques for facility location problems. The research objective
has been achieved, and the proposed case study has validated the model.
The model located 31 percent of ANAC personnel in Brazilian Southeast Region,
25 percent in Northeast Region, 17 percent in North Region, 17 percent in South Region and 10 percent in Central-West Region; decreasing in 66 percent the total quantity of allocated inspectors. A capacities matrix has been constructed with model results;
decision-makers can analyze the optimal distribution of personnel capacities
in each facility. Finally, a sensitivity analysis has been done to test the model
flexibility, which prove the model is efficient for real problems application.
|
24 |
[en] OPTIMIZATION OF DISTRIBUTION COMPANIES STRATEGY FOR PARTICIPATING IN THE CONTRACT SURPLUS SELLING MECHANISM – MVE: A DECISION UNDER UNCERTAINTY APPROACH / [pt] OTIMIZAÇÃO DA ESTRATÉGIA DE DESCONTRATAÇÃO DAS DISTRIBUIDORAS: UMA ABORDAGEM SOB INCERTEZAMATEUS ALVES CAVALIERE 03 February 2022 (has links)
[pt] No Brasil, as distribuidoras (DisCos) devem suprir seu crescimento de
carga por meio de contratos comercializados em leilões centralizados de Energia
Nova, nos quais são leiloados contratos com entrega 4 anos a frente. No entanto,
projetar a demanda de energia para vários anos à frente é muito desafiador, pois
o consumo de energia é muito dependente da taxa de crescimento da economia,
da possibilidade de surgimento de uma nova solução/tecnologia (geração solar
distribuída) e da migração de consumidores cativos para o mercado livre.
Embora as distribuidoras possam repassar os custos do excedente contratual de até 5 por cento nas tarifas de energia, esse limite tem se mostrado insuficiente
desde que a última crise econômica no Brasil (2015) derrubou as expectativas
de crescimento do consumo, deixando as distribuidoras com um superavit de
contrato enorme. Essa situação tornou-se um problema para as distribuidoras,
uma vez que esses contratos são liquidados no mercado spot, expondo-as ao
preço spot, variável demasiadamente volátil no Brasil, e comprometendo assim
a os seus fluxos de caixa.
Neste contexto, criou-se o Mecanismo de Venda de Excedentes - MVE,
um importante instrumento regulatório para gerenciamento do portfólio das
distribuidoras. Por meio deste mecanismo as distribuidoras são capazes de
vender, em um leilão centralizado, seus excedentes contratuais, reduzindo assim
sua exposição ao mercado spot.
Assim, este trabalho tem como objetivo propor uma metodologia para
otimizar a estratégia das distribuidoras nos processamentos de MVE utilizando
o conceito de Decisão sob Incerteza. Em outras palavras, o modelo indicará
uma estratégia de venda de contratos no MVE, considerando o perfil de aversão
ao risco do agente, avaliando os diferentes custos de oportunidade existentes
neste processo de tomada de decisão. / [en] In Brazil, distribution companies (DisCos) must supply their expected
load growth with contract purchases in centralized New Energy Auctions, in
which commercial operation date – COD of generation projects being sold is
(at least) 4 years ahead. Projecting energy demand for several years ahead is
very challenging as energy consumption is very dependent on economy growth
rate, the possibility of a surge of a new solution/technology (solar distributed
generation) and the migration of captive consumers to the free market, to name
a few.
Even though distribution companies are allowed to pass through the
costs of contract surplus of up to 5 percent in energy tariffs, this threshold was
shown insufficient when the latest economic crisis in Brazil (2015) has knocked
over consumption growth expectations, leaving distribution companies with
huge contract surplus. This situation became a problem for the distribution
companies since these contracts must be settled in the spot market, exposing
them to the spot price, which is very volatile, and compromising their cash
flow.
In this context, the Mecanismo de Venda de Excedentes - MVE was
created, an essential regulatory instrument to help distribution companies
manage their energy portfolio. Through this mechanism, DisCos can sell in
a centralized auction their contracts surplus, reducing their position in the
spot market.
This work aims to propose a methodology to optimize the distribution
companies strategy in the MVE auctions using the theory of the Decision
under Uncertainty. In other words, the model will indicate a strategy to sell
contracts in the MVE, considering the agent s risk aversion profile, evaluating
all the opportunity costs involving in this decision-making.
|
25 |
[en] BRANCH-CUT-AND-PRICE APPROACH FOR PROCESS DISCOVERY / [pt] UMA ABORDAGEM PARA MINERAÇÃO DE PROCESSOS USANDO GERAÇÃO DE COLUNAS E CORTESGEORGES MIRANDA SPYRIDES 28 May 2019 (has links)
[pt] Descoberta de Processo significa determinar um modelo de processo a partir de um registro histórico de eventos de um processo de negócios. Muitos algoritmos de descoberta de processos tentam sintetizar uma rede de Petri que representa o registro localizando locais e arcos que relacionam as classes de eventos. Bergenthum et al (2007) e van der Werf et al. (2008) propõem formulações para este problema descobrir um place de cada vez, em que cada solução básica do conjunto de desigualdades representa um lugar candidato. Propomos uma formulação global de programação inteira que, dado um registro histórico, determina todos os places e arcos que definem uma rede de Petri de uma só vez. Este modelo é uma alternativa a seleção de locais, mas tem um problema de eficiência devido à grande quantidade de variáveis inteiras usadas. Também propomos um método de decomposição para o modelo ILP global para tratar cada place e suas restrições associadas como um subproblema separado. Conseguimos então executar o algoritmo em instâncias sintéticas grandes, o que é inédito para esta classe de mineradores de processo. / [en] Process Discovery amounts to determine a process model from an event log of a business process. Many process discovery algorithms try to synthesize a Petri net representing the log by finding places and arcs
that relate the event classes. Bergenthum et al. (2007) and van der Werf et al. (2008) propose formulations for this problem discover one place at a time, in which each basic solution of the set of inequalities represents a candidate place. We propose a global integer programming formulation that, given a log, determines all places and arcs defining a Petri net. This model simplifies the selection of places but has an efficiency problem due to a large number of integer variables used. We also propose a decomposition method for the global ILP model to treat each place and their associated constraints as a separate sub-problem. We can run the algorithm on large synthetic instances, which is unprecedented for this kind of process miner.
|
26 |
[en] VEHICLE ROUTING PROBLEMS WITH TIME WINDOWS AND EXACT SYNCHRONIZATION CONSTRAINTS / [pt] PROBLEMAS DE ROTEAMENTO DE VEÍCULOS COM JANELAS DE TEMPO E SINCRONIZAÇÃO EXATA DE OPERAÇAOFABIAN ARTURO CASTILLA PENARANDA 29 December 2014 (has links)
[pt] Uma generalização do problema de roteamento de veículos (VRP) presente em aplicações práticas em portos e operações em minas é o objeto desta dissertação. Nesta variante do VRP cada cliente pode demandar diferentes tipos de veículos para cumprir tarefas colaborativamente. Nesta atividade, os veículos podem aguardar o início da operação no local porém, devem iniciar as tarefas ao mesmo tempo. O objetivo é determinar as rotas dos veículos disponíveis de modo a maximizar a soma (ponderada) dos clientes atendidos enquanto a distância total percorrida é minimizada. O caso específico onde todos os clientes são atendidos e a distância total percorrida é minimizada determina o problema central estudado nessa dissertação. Este caso particular pode ser visto como uma generalização direta do, muito estudado e conhecido problema de roteamento, VRP com janelas de tempo (VRPTW) onde a capacidade
dos veículos é suficientemente grande. Esta escolha de um problema mais restrito é justificada por permitir uma clara comparação de sua dificuldade através da sua relação com o VRPTW. A partir da classificação
dos casos de sincronização em problemas de roteamento proposta por (DREXL, 2012), denominamos o problema aqui estudado de Problema de Roteamento de Veículos com Janelas de Tempo e Sincronização exata da Operação (VRPTWEOS). Neste trabalho damos uma definição formal ao VRPTWEOS. Modelos de programação inteira são propostos e analisados. Também apressentamos métodos de resolução baseados na decomposição Dantzig-Wolfe, dos quais são derivados algoritmos exatos e aproximados.
Com o propósito de avaliar a eficiencia desses algoritmos, foi criado um grupo de instancias de teste baseado no benchmark do Solomon para o VRPTW. O método usado para criar o conjunto de instancias de teste é descrito em detalhe. Experimentos computacionais sobre este conjunto de instancias mostraram que o método de resolução proposto é promissor para a resolução do VRPTWEOS. / [en] This dissertation addresses a generalization of the vehicle routing problem (VRP) that arises in real life applications in ports and mine operations. In this VRP variant, each customer may demand different types
of vehicles to perform a task collaboratively. Vehicles are allowed to wait at the locations but they must start operating at the same time. The objective is to route the available vehicles while maximizing the (weighted) sum of served customers and minimizing the total distance traveled. The specific case where all customers must be served while minimizing the total distance traveled is the central problem here studied. This special case can be viewed as a straightforward generalization of, a well known and more specific routing problem, the VRP with time windows (VRTPTW) where the capacity of the vehicles is sufficiently large. We support this narrower scope by stating that it allows a clear comparison of the problem
hardness by its relation to the VRPTW. Sticking to the classification of synchronization in vehicle routing proposed by (DREXL, 2012) we named this problem as the Vehicle Routing Problem with Time Windows and Exact Operation Synchronization (VRPTWEOS). In this work, a formal definition for the VRPTWEOS is provided. Integer programming models for this problem are proposed and analyzed. Furthermore, we propose a solution method based on the Dantzig-Wolfe decomposition for which exact and aproximated resolution algorithms are described. In order to test the performance of those algorithms, a group of benchmark instances for the VRPTWEOS was created on top of the Solomon benchmark for the
VRPTW. The method used to create the benchmark instances is described in detail. Computational experiments over the mentioned set of instances showed that the proposed solution approach is a promising alternative for solving the VRPTWEOS.
|
27 |
[en] EXACT ALGORITHMS FOR THE CAPACITATED VEHICLE ROUTING PROBLEM / [pt] ALGORITMOS EXATOS PARA O PROBLEMA DE ROTEAMENTO DE VEÍCULOS CAPACITADODIEGO GALINDO PECIN 01 April 2015 (has links)
[pt] Os Problemas de Roteamento de Veículos estão entre os problemas combinatoriais mais difíceis de se resolver à otimalidade. Eles foram propostos no final da década de 1950, e desde então eles têm sido amplamente estudados. O interesse deve-se a sua importância prática, bem como da dificuldade de se fornecer algoritmos eficientes para resolvê-los. Esta tese trata principalmente da resolução exata do Problema de Roteamento de Veículos com Capacidades (PRVC). Neste problema, um conjunto de clientes, cada um associado a uma demanda, deve ser atendido por uma frota de veículos. Todos eles têm o mesma capacidade e, inicialmente, estão localizados no mesmo depósito. Uma solução é um conjunto de rotas que começam e terminam no depósito e visitam cada cliente uma única vez. A restrição em uma rota é que a soma das demandas de seus clientes não exceda a capacidade do veículo. O objetivo é encontrar uma solução com um custo mínimo. Os melhores algoritmos exatos para o PRVC desenvolvidos nos últimos dez anos são baseados na combinação de geração de cortes e colunas. Alguns autores utilizaram apenas cortes sobre as variáveis da formulação original, com a finalidade de manter o subproblema de geração de colunas relativamente fácil. Outros puderam reduzir os limites duais utilizando também um número restrito de cortes expressos nas variáveis do problema mestre, parando de incluir tais cortes quando o subproblema tornavase proibitivamente difícil. Uma família eficaz de tais cortes são os Subset Row Cuts. Esta tese apresenta uma técnica para reduzir consideravelmente o impacto que tais cortes causam no subproblema de geração de colunas, permitindo assim que muito mais cortes sejam adicionados. O novo algoritmo Branch-Cut-and-Price proposto também incorpora e combina pela primeira vez vários elementos presentes em trabalhos anteriores, como enumeração de rotas, fixação de variáveis e strong branching. Todas as instâncias usadas em algoritmos exatos, com até 199 clientes, foram resolvidas à otimalidade. Além disso, algumas maiores, com até 360 clientes, apenas consideradas antes em métodos heurísticos, também foram resolvidas. / [en] Vehicle Routing Problems are among the most difficult combinatorial problems to solve to optimality. They were proposed in the late 1950 s and since then have been widely studied. This interest arises from their practical importance, as well as the difficulty of providing efficient algorithms to solve them. This thesis is mainly concerned with the exact resolution of the Capacitated Vehicle Routing Problem (CVRP). In this problem, a set of customers, each one associated to a demand, must be serviced by a
fleet of vehicles. All vehicles have the same (limited) capacity and initially are located in the same central depot. A solution is a set of routes, starting and ending at the depot, that visit every customer exactly once. The only constraint on a route is that the sum of the demands of its customers does not exceed the vehicle capacity. The objective is to find a solution with minimum total cost. The best performing exact algorithms for the CVRP developed in the last 10 years are based in the combination of cut and column generation. Some authors only used cuts expressed over the variables of the original formulation, in order to keep the pricing subproblem relatively easy. Other authors could reduce the duality gaps by also using a restricted number of cuts over the Master LP variables, stopping when the pricing becomes prohibitively hard. A particularly effective family of such cuts are the Subset Row Cuts. This thesis introduces a technique for greatly reducing this impact on the pricing of these cuts, thus allowing much more cuts to be added. The newly proposed Branch-Cut-and-Price algorithm also incorporates and combines for the first time (often in an improved way) several elements found in previous works, like route enumeration, variable fixing and strong branching. All the instances used for benchmarking exact algorithms, with up to 199 customers, were solved to optimality. Moreover, some larger instances with up to 360 customers, only considered before by heuristic methods, were solved too.
|
28 |
[en] NEW HEURISTICS AND AN INTEGER PROGRAMMING APPROACH TO AN INEXACT GRAPH MATCHING PROBLEM / [pt] NOVAS HEURÍSTICAS E UMA ABORDAGEM POR PROGRAMAÇÃO INTEIRA PARA UM PROBLEMA DE CORRESPONDÊNCIA INEXATA DE GRAFOSALEXANDRE ROCHA DUARTE 26 March 2004 (has links)
[pt] Esta dissertação apresenta novos algoritmos aproximados e
uma abordagem exata para a resolução de um problema de
correspondência inexata de grafos. O problema considerado é
o de correspondência entre um grafo representando um modelo
genérico e outro representando dados a serem reconhecidos.
Assumi-se que o grafo dos dados possui mais vértices que o
do modelo. A motivação para o estudo desse problema vem de
problemas de reconhecimento de cenas, que consistem na
caracterização dos objetos envolvidos em uma determinada
cena, assim como das relações existentes entre eles. Uma
aplicação para este problema na área de reconhecimento de
imagens médicas é a de efetuar-se o reconhecimento de
estruturas 3D do cérebro humano, a partir de imagens
obtidas por ressonância magnética. Tais imagens são
previamente processadas por algum método de segmentação
automática e o processo de reconhecimento consiste na busca
da correspondência estrutural entre a imagem e um modelo
genérico, tipicamente definido como um atlas de imagens
médicas. Foram propostos novos algoritmos aproximados, tais
como um algoritmo construtivo guloso aleatorizado, um
procedimento de reconexão de caminhos e um GRASP que
combina estes com uma técnica de busca local. Além disso,
foi proposta uma formulação original do problema como um
problema de programação linear inteira, que permitiu a
resolução de algumas instâncias de forma exata. / [en] This dissertation presents new approximation algorithms and
an exact approach to the solution of an inexact graph
matching problem. The problem consists in finding the best
match between a generic model graph and a graph
representing an image, the latter with more nodes than the
former. The motivation for studying this problem comes from
a scene recognition problem, which consists in
characterizing objects involved in a given scene and the
relationships between them. An application of this problem
appears in the analysis of medical images and consists in
recognizing 3-dimensional structures in the human brain
using images obtained by magnetic resonance. Such images
must be previously processed by an automatic segmentation
method and the recognition process consists in the search
of an structural matching between the image and a generic
model, typically defined as an atlas of medical images.
New heuristics are proposed, such as a greedy randomized
construction algorithm, a path relinking procedure and a
GRASP heuristic that combines them with a local search
technique. Furthermore, an original integer formulation
of the problem based on integer multicommodity flows is
proposed, which makes possible the exact solution of medium-
sized instances.
|
29 |
[en] FREQUENCY PLANNING OPTIMIZATION USING ISOLATION AND COMPATIBILITY MATRICES / [es] OPTIMIZACIÓN DEL PLAN DE FRECUENCIAS DE UNA RED CELULAR POR EL USO DE LAS MATRICES DE AISLAMIENTO Y COMPATIBILIDADE / [pt] OTIMIZAÇÃO DE PLANEJAMENTO DE FREQÜÊNCIA DE UMA REDE CELULAR PELO USO DAS MATRIZES DE ISOLAÇÃO E DE COMPATIBILIDADEROBSON DOMINGOS VIEIRA 21 September 2001 (has links)
[pt] Um algoritmo de alocação de freqüência eficiente deve
considerar aspectos de propagação e detalhes de equipamento
de modo a minimizar a relação a sinal interferência, e
conseqüentemente, aumentar a eficiência do espectro. Essa
dissertação tem o objetivo de propor uma melhor solução
para alocação de freqüência nas rede TDMA e GSM, levando em
consideração os aspectos citados. A abordagem utilizada é
diferente das técnicas de alocação de freqüências usuais,
que são baseadas na distância de reuso. O algoritmo
proposto utiliza uma matriz que representa os aspectos de
propagação (matriz de isolação) e uma matriz que representa
os detalhes do equipamento (matriz de compatibilidade).
A matriz de isolação mostra a relação sinal interferência
que cada célula tem com as outras. Um estudo de como
coletar os dados (seleção da rota no interior do setor) e
de como trabalhar com os dados coletados foram realizados,
objetivando-se ter matriz que melhor caracterizasse a rede
utilizada. A matriz de compatibilidade mostra a distância
em freqüência no qual se devem alocar os canais em uma
mesma célula, células adjacentes e células co-sites. Os
valores de espaçamento entre freqüências, sugeridos nesta
dissertação, são valores práticos e dependem das técnicas
utilizadas no planejamento e do equipamento utilizado em
questão. O problema de alocação foi modelado com um
problema inteiro. Uma heurística (divide and conquer) foi
utilizada para particionar a rede em menores partes, em que
o algoritmo branch and bound foi implementado. O algoritmo
foi testado em duas redes com sessenta e trezentos e
quarenta e oito setores respectivamente. As redes foram
construída levando em consideração os dados topográficos e
morfológicos da cidade de Brasília. / [en] An efficient frequency assignment algorithm should consider
both propagation conditions and equipment details, in order
to minimize the carrier-to-interference ratio (C/I) and, as
a result, to increase spectrum efficiency. This
dissertation proposes a way to obtain a better solution for
frequency assignment in TDMA and GSM networks, taking into
account propagation conditions and equipment details. The
proposed approach is different from usual frequency
assignment techniques based on reuse distance. A frequency
assignment algorithm proposed uses one matrix that
represents the propagation features (isolation matrix) and
another which represents the equipment details
(compatibility matrix). The isolation matrix shows the
signal to interference ratio between any two sectors in
the whole network. A survey to define how to collect the
data ( selection of the route inside the sector) and how to
work with data collected was developed, aiming to obtain the
best matrix representation of the network. The
compatibility matrix shows the frequency distance between
channels in the same sector, adjacent sector and co-site
sectors. The frequency space values used in this matrix
are practical values, which depend upon the technique used
on the planning and on the utilized hardware. The frequency
assignment was formulated as an integer problem. An
heuristic (divide and conquer) was used to split the
network into smaller parts where an exact algorithm branch
and bound was implemented. The algorithm was tested on two
networks with 60 and 348 sectors respectively. The networks
were built having the topographical and morphological data
from Brasilia city. / [es] Un algoritmo eficiente de asignación de frecuencia debe considerar aspectos de propagación y
detalles del equipo de modo tal que se minimize la relación señal-interferencia, y onsecuentemente,
aumente la eficiencia del espectro. Esta disertación tiene como objetivo proponer una solución para
la asignación de frecuencia en las redes TDMA y GSM, considerando los aspectos anteriormente
citados. El enfoque utilizado difiere de las técnicas de asignación de frecuencias usuales, baseadas
en la distancia de reuso. EL algoritmo propuesto utiliza una matriz que representa los aspectos de
propagación (matriz de aislamiento) y una matriz que representa los detalles del equipo (matriz de
compatibilidade). La matriz de aislamiento muestra la relación señal-interferencia que cada célula
tiene con las otras. Se realiza un estudio de como recolectar los datos (selección de la ruta en el
interior del sector) y de como trabajar con los datos recolectados, con el objetivo de obtener la matriz
que mejor caracteriza la red utilizada. La matriz de compatibilidad muestra la distancia en frecuencia
en la cual se deben alocar los canales en una misma célula, células adyacentes y células co-sites. Los
valores de espacio entre frecuencias, sugeridos en esta disertación, son valores prácticos y dependen
de las técnicas utilizadas en el planificación y del equipo utilizado. El problema de asignación fue
modelado como un problema entero. Fue utilizada una heurística (divide and conquer) para
particionar la red en menores partes, donde se implementó el algoritmo branch and bound. EL
algoritmo fue probado en dos redes con sesenta y trezentos y quarenta y oito sectores
respectivamente. Las redes fueron construidas considerando los datos topográficos y morfológicos de
la ciudad de Brasilia.
|
30 |
[pt] ALGORITMO PRICE-AND-CUT COM 3-SRCS E ENUMERAÇÃO DE COLUNAS PARA O PROBLEMA DE ALOCAÇÃO GENERALIZADA / [en] PRICE-AND-CUT ALGORITHM WITH 3-SRCS CUTS AND COLUMN ENUMERATION FOR THE GENERALIZED ASSIGNMENT PROBLEMRAFAEL AZEVEDO MOSCOSO SILVA CRUZ 15 June 2021 (has links)
[pt] Esta dissertação estuda formulações, algoritmos e métodos exatos para resolver instâncias do Problema de Alocação Generalizada (PAG) com uma separação de desigualdades (3, 0.5)-SRC que viabilize a enumeração de colunas. Este trabalho é motivado pela perspectiva de alcançar o estado-da-arte com
resultados competitivos comparáveis às melhores soluções encontradas na literatura por Avella (2010) e Michelon (2012). A pesquisa abrange métodos exatos e heurísticas, com ênfase no estudo que aborda a decomposição de Dantzig-Wolfe, o algoritmo de geração de colunas, a estabilização de colunas
por meio da ponderação de duais proposto por Wentges (1997) e a enumeração de colunas habilitada pela minimização do gap decorrente do algoritmo de price-and-cut. O algoritmo de price-and-cut desenvolvido recorre à geração de colunas (pricing) aliada à separação de (3, 0.5)-SRCs para aumentar o lower bound gerado, assim minimizando o gap. A geração de colunas implementada é inspirada no algoritmo de Savelsbergh (1997); e a separação de (3, 0.5)-SRCs é motivada pelo trabalho de Jepsen (2008) e pelo algoritmo branch-cut-andprice proposto por Poggi e Uchoa (2016) para o CVRP. De acordo com os
experimentos computacionais, as desigualdades adotadas são capazes de reduzir o gap suficientemente para viabilizar a enumeração de colunas em diversas instâncias do PAG com até 200 tarefas e 20 máquinas. O método utilizado obteve resultados compatíveis às melhores soluções conhecidas, enumerando todas as colunas necessárias para cobrir o gap determinado pelo price-and-cut. Esse
resultado incentiva futuras pesquisas para estender a aplicação do algoritmo a instâncias maiores e mais difíceis. / [en] This dissertation deals with formulations, algorithms and exact methods for solving the well-known Generalized Assignment Problem (GAP) through a price-and-cut approach with the separation of (3, 0.5)-SRC inequalities in order to improve column enumeration feasibility and efficiency. This work is
motivated by the perspective of reaching state-of-the-art performance, attaining competitive results which are comparable with the best known solutions found in the literature by Avella (2010) and Michelon (2012). This research was build on exact methods and some heuristics with emphasis on the Dantzig-
Wolfe decomposition, the column generation algorithm, the stabilization through weighted Dantzig-Wolfe decomposition proposed byWentges (1997) and finally the column enumeration motivated by the gap minimization reached through the price-and-cut algorithm. The price-and-cut algorithm proposed here resort to column generation (pricing) combined with the separation of (3, 0.5)-SRC cuts in order to increase the generated lower bound, thus minimizing the attained gap. This column generation algorithm follows the work of Savelsbergh (1997); and the separation of (3, 0.5)-SRCs is formulated by Jepsen (2008) and motivated by the branch-cut-and-price algorithm proposed by Poggi and Uchoa (2016) for the CVRP. According to computational experiments, the adopted inequalities are capable of sufficiently reducing the gap, assuring the feasibility of column enumeration for several GAP instances with up to 200 tasks and 20 machines. This method achieved expressive results, compatible with the best known solutions, enumerating all the necessary columns to cover the gap found by the price-and-cut. Therefore, these results motivate future research towards the extension of the method s applicability to larger and more complex instances.
|
Page generated in 0.5732 seconds