Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-02-14T11:00:06Z No. of bitstreams: 1 texto completo.pdf: 1892866 bytes, checksum: 725886f14f97ae6598868af898629ce4 (MD5) / Made available in DSpace on 2017-02-14T11:00:06Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1892866 bytes, checksum: 725886f14f97ae6598868af898629ce4 (MD5) Previous issue date: 2016-06-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Transporte reativo a demanda, na língua inglesa Demand Responsive Transport (DRT) é uma forma de prover transporte, seja para passageiros ou mercadorias, na qual o serviço é ativado sob demanda. Ao contrário dos serviços tradicionais de transporte público, os quais operam por meio de rotas, horários e pontos de atendimento fixos, os serviços DRT operam de formas flexíveis ou semi-flexíveis. Para utilização do serviço, passageiros devem enviar requisições, nas quais informam locais e horários desejados de embarque e desembarque. A partir das requisições, ocorre o processo de roteamento dos veículos e agendamento dos atendimentos. Usuários provenientes de requisições diferentes, mas com características em comum, seja área e/ou momento de atuação do serviço podem ser atendidos simultaneamente pelo mesmo veículo. Devido a esta forma de prover transporte, para alguns pesquisadores do tema, serviços DRT são conside- rados uma forma intermediária de transporte, situada entre os serviços de transporte público (caráter geral e compartilhado) e os táxis (personalizado e individual) e con- tribuem direta e indiretamente na redução de alguns dos principais problemas comuns em centros urbanos, tais como: excesso de veículos nas vias trafegando com baixa ocu- pação, poluição, congestionamentos, exclusão social relacionada ao acesso a meios de transporte público e etc. Neste trabalho, foram propostos modelos de programação linear mista, abordagens multiobjetivo e abordagens heurísticas para otimização de um serviço DRT introduzido na literatura, o qual foi explorado para os casos estático e dinâmico. As abordagens apresentadas foram avaliadas por meio de experimentos computacionais e testes estatísticos sobre conjuntos de instâncias com diferentes carac- terísticas, que indicaram as melhores abordagens para cada situação. / Heuristic approaches to optimizing a demand responsive transport. Ad- viser: André Gustavo dos Santos. Demand responsive transport is a way to provide transportation for passengers or go- ods, in which the service is activated on demand. Unlike traditional public transport services, which operate through fixed routes, schedules and service points, DRT ser- vices operate in flexible or semi-flexible way. In order to use the service, passengers must submit requests, in which they inform the desired local and times of departure and arrival. The routing of vehicles and the scheduling of calls are performed based on those requests. Users from different requests, but with common features like area and/or moment of the service can be served simultaneously by the same vehicle. Due to this way of providing transport, some researchers consider the DRT services an inter- mediate form of transport, situated between public transport services (general purpose and shared) and taxis (custom and individual) and contribute directly and indirectly in reducing some of the major common problems in urban centers, such as: too many vehicles traveling on the roads with low occupancy, pollution, congestion, social exclu- sion related to access to public transportation, etc. In this work, we proposed mixed linear programming models, multi-objective approaches and heuristics approaches for optimization of a DRT service from the literature, which was exploited for the static and dynamic case. The approaches presented were evaluated through computational experiments and statistical tests using sets of instances with different characteristics, showing the best approaches for each situation.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-08-31T12:45:53Z No. of bitstreams: 1 texto completo.pdf: 2856120 bytes, checksum: f1801ace46848b5b50cb84b2a9f19634 (MD5) / Made available in DSpace on 2017-08-31T12:45:53Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2856120 bytes, checksum: f1801ace46848b5b50cb84b2a9f19634 (MD5) Previous issue date: 2017-03-07 / Este trabalho aborda dois problemas de roteamento de veículos de coleta e entrega com restrições de carregamento. Primeiramente foi tratado o Problema de Rotea- mento Duplo de Veículos com Múltiplas Pilhas (Double Vehicle Routing Problem with Multiple Stacks - DVRPMS). Posteriormente foi formulado e proposto o Problema de Roteamento Duplo de Veículos com Múltiplas Pilhas e Demanda Heterogênea (Double Vehicle Routing Problem with Multiple Stacks and Heterogeneous Demand - DVRPMSHD), se referindo a um caso mais realista do DVRPMS, quando os clientes têm demandas múltiplas e heterogêneas, sendo que toda a demanda de um mesmo cliente deve ser transportada por um único veículo. Em ambos os problemas, o objetivo é determinar rotas para uma frota de veículos a fim de atender a demanda de um conjunto de clientes de forma que a distância percorrida pelos veículos seja a mínima possível, respeitando algumas restrições de carregamento impostas pelas pilhas de armazenamento dos veículos. Todos os produtos localizados em uma região de coleta devem ser coletados e depois entregues em uma região de entrega pelos veículos. As regiões de coleta e entrega são largamente separadas, portanto todos os produtos devem ser carregados antes de qualquer descarregamento. O DVRPMS foi abordado principalmente por quatro métodos heurísticos, os quais foram testados em diversas instâncias e comparados aos métodos exatos e heurísticos já existentes na literatura. Os experimentos computacionais mostraram a eficiência dos algorit- mos propostos, obtendo soluções de melhor qualidade que as soluções apresentadas na literatura para a maioria dos casos de teste com baixo tempo computacional. Já o DVRPMSHD foi abordado de forma exata e heurística. Inicialmente, foi desen- volvido um método exato branch-and-price que apresentou maior eficiência quando comparado à formulação matemática também proposta para o problema. O método heurístico superou os resultados alcançados pelo branch-and-price para a maioria das instâncias de teste formuladas. / In this work we address two vehicle routing problems with pickup and delivery and loading constraints. Firstly, this work addresses the Double Vehicle Routing Pro- blem with Multiple Stacks (DVRPMS). Posteriorly we formulate and propose the Double Routing Vehicle Problem with Multiple Stacks and Heterogeneous Demand (DVRPMSHD), referring to a more realistic case of the DVRPMS in which custo- mers have multiple and heterogeneous demands and all demand of a same client must be transported by a single vehicle. In both problems, the objective is to de- termine routes for a fleet of vehicles to meet the demand of a set of customers so that the distance travelled by the vehicles is the minimum possible, respecting some loading constraints imposed by the vehicles’ storage stacks. All products located in a pickup region must be collected and then delivered to a delivery region by vehicles. The pickup and delivery regions are largely separated so that all products must be loaded before any unloading. The DVRPMS was approached mainly by four heuristic methods, which were tested in several instances and compared to the exact and heuristic methods already present in literature. The computational experiments showed the efficiency of the proposed algorithms, obtaining solutions of better quality than those presented in the literature for most of the instances and with low computational time. The DVRPMSHD was approached by an exact method and a heuristic method. Initially, the implemented branch-and-price exact method presented higher efficiency compared to the proposed mathematical formu- lation for the problem. The heuristic method overcame the results achieved by the branch-and-price for most of the created instances.

DANTAS, Allberson Bruno de Oliveira. Uma interface de programação distribuída para aplicações em otimização combinatória. 2011. 86 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2011. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T17:57:51Z No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T12:23:03Z (GMT) No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Made available in DSpace on 2016-07-13T12:23:03Z (GMT). No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) Previous issue date: 2011 / This work was motivated by the need of exploiting the potential of distributed paralelism in combinatorial optimization applications. propose a distributed programming interface, To achieve this goal, we in which we cherish two main requirements: e ciency and reuse. The rst stems from the need of HPC (High applications require maximum possible performance. Performance Computing) Therefore, we specify our interface as an extension of the MPI library, which is assumed to be e cient for distributed applications. The reuse requirement must make compatible two important features: asynchronism and collective operations. Asynchronism must be present at our interface, once most of combinatorial optimization applications have an asynchronous nature. Collective operations are features that should be available in the interface, so that they can be used by applications in their execution. In order reach the reuse requirement, we based this interface on the Event- and Pulse-driven Models of Distributed Computing, once they are asynchronous and allow the incorporation of collective operations. We implemented partially the interface de ned in this work. In order to validate the use of the inteface by combinatorial optimization applications, we selected two applications and implemented them using our interface. They are the Branch-and-Bound technique and the Maximum Stable Set Problem (MSSP). We also provide some experimental results. / Este trabalho foi motivado pela necessidade da exploração do potencial do paralelismo distribuído em aplicações em Otimização Combinatória. Para tanto, propomos uma interface de programação distribuída, na qual prezamos dois requisitos principais: eficiência e reuso. O primeiro advém da necessidade de aplicações de CAD exigirem máximo desempenho possível. Assim sendo, especificamos esta interface como uma extensão da biblioteca MPI, a qual é assumida como eficiente para aplicações distribuídas. O requisito reuso deve tornar compatíveis duas características importantes: assincronismo e operações coletivas. O assincronismo deve estar presente na interface, uma vez que as aplicações em Otimização Combinatória, em sua maioria, possuem uma natureza assíncrona. Operações coletivas são funcionalidades que devem estar disponíveis na interface, de modo que possam ser utilizadas por aplicações em suas execuções. Tendo em vista atender o requisito reuso, baseamos esta interface nos Modelos de Computação Distribuída Dirigidos por Eventos e por Pulsos, pois os mesmos são assíncronos e permitem a incorporação de operações coletivas. Implementamos parcialmente a inteface definida neste trabalho. Tendo em vista validar uso desta inteface por aplicações em Otimização Combinatória, selecionamos duas aplicações e as implementamos utilizando a interface. São elas a técnica Branch-and-Bound e o Problema do Conjunto Independente Máximo (CIM). Fornecemos também alguns resultados experimentais.

DIAS, Fábio Carlos Sousa. Problema de Árvore Geradora Mínima com Restrição de Grau Mínima e Centrais e Terminais Fixos. 2014. 132 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T19:49:19Z No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) / Approved for entry into archive by José Jairo Viana de Sousa (jairo@ufc.br) on 2016-07-14T23:17:13Z (GMT) No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) / Made available in DSpace on 2016-07-14T23:17:13Z (GMT). No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) Previous issue date: 2014 / The Min-Degree Constrained Minimum Spannig Tree - MD-MST is to find a minimum spanning tree of a graph where each vertex is a leaf of the tree or satisfies a constraint of minimum degree. The leaf vertices are called terminals and the others are the central vertices. We define and study a variation of this problem, which we denote MDF-MST, where the terminal and central vertices are fixed. We show that the problem is NP-Hard and is in FPT, parameterized by the number of central vertices. We also identify cases where the problem becomes polynomial. We propose several integer programming formulations for the problem and compare the quality of lower bound generated by their linear relaxations. We propose and teste a Lagrangian Relaxation for the problem, which we also use to define Lagrangian heuristics. We define greedy heuristics, a VND Local search and a VNS heuristic. We present a Benders’s Decomposition. We propose a new general heuristic that combines ingredients from the Benders’s decomposition with subgradient method, which we call subgradient heuristic. We apply this heuristic to the MDF-MST. All these algorithms have been implemented, tested and compared among them and with the CPLEX solver. The computational efficiency of the proposed algorithms, especially the Lagrangian heuristics, is comparable with that of CPLEX, and even better in several cases. Some of these algorithms were adapted for the MD-MST and DC-MST (inthelatter,thedegreeconstraintisofmaximumdegree). Whencomparingthecomputational results with the literature, we conclude that the algorithms are competitive. / O Problema de Árvore Geradora Mínima com Restrição de Grau Mínimo (Min-Degree Constrained Minimum Spannig Tree - MD-MST) consiste em encontrar uma árvore geradora mínima de um grafo onde cada vértice ou é folha da árvore ou satisfaz uma restrição de grau mínimo. Os vértices folhas são chamados terminais e os demais são os centrais. Definimos e estudamos uma variação desse problema, que denotamos MDF-MST, onde os terminais e centrais são definidos a priori. Mostramos que o problema é NP-Difícil e está na Classe FPT, parametrizado pelo número de centrais. Identificamos também casos onde o problema torna-se polinomial. Propomos várias formulações de programação inteira para o problema e comparamos teórica e computacionalmente a qualidade do limite inferior gerado por suas relaxações lineares. Propomos e testamos uma relaxação lagrangeana para o problema, que usamos também para definir heurísticas lagrangenas. Definimos heurísticas gulosas, uma busca VND e uma heurística VNS. Apresentamos uma decomposição de Benders. Propomos uma nova heurística geral que combina ingredientes da decomposição de Benders com método de subgradientes, a qual denominamos Heurística de Subgradientes. Aplicamos tal heurística ao MDF-MST. Todos esses algoritmos foram implementados, testados, comparados entre si e com o solver CPLEX. A eficiência computacional dos algoritmos propostos, especialmente a relaxação lagrangeana, é competitiva com a do CPLEX, e superior em vários casos. Alguns desses algoritmos foram adaptados para o problema MD-MST e seu correlato DC-MST (este último onde a restrição sobre os centrais é de grau máximo). Quando comparamos os resultados computacionais com a literatura.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-05-20T08:41:16Z No. of bitstreams: 1 texto completo.pdf: 1841361 bytes, checksum: 460f1d8d605da4af4e1d8d606edfaa05 (MD5) / Made available in DSpace on 2016-05-20T08:41:16Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1841361 bytes, checksum: 460f1d8d605da4af4e1d8d606edfaa05 (MD5) Previous issue date: 2007-10-26 / O pivô central é um sistema de irrigação de grande porte, que utiliza grandes quantidades de água durante seu funcionamento. A criação de uma escala de funcio- namento para os pivôs centrais que atuam compartilhando um mesmo recurso hídrico é uma solução para reduzir custos com energia elétrica e controlar o consumo de água visando evitar possíveis danos ambientais sem comprometer a eficácia na irrigação. Para encontrar tal solução, um modelo matemático que representa o problema foi criado e validado. Este modelo serviu de base para a construção de algoritmos que geram a escala de funcionamento dos pivôs centrais. Devido ao grau de complexidade do problema, o uso das metaheurísticas Simulated Annealing e GRASP foi adotado na busca de boas soluções em curto espaço de tempo. A aplicação das metaheurís- ticas foi feita de maneira simples, oferecendo a opção de modificar os parâmetros do problema, de acordo com as necessidades encontradas, sendo possível adaptar a forma de execução dos algoritmos à diferentes realidades. Uma interface que utiliza os al- goritmos desenvolvidos foi construída com o objetivo de facilitar a manipulação das informações de entrada e saída do sistema. Os resultados dos testes obtidos com o sistema utilizando ambos os algoritmos geraram soluções que atenderam plenamente a expectativa inicial sendo, inclusive, avaliados por profissionais da área. Além disto, um estudo de caso, utilizando os algoritmos desenvolvidos, foi realizado com base em informações reais do Projeto Colonização Paracatu Entre-Ribeiros, localizado na Bacia do Rio São Francisco, um dos maiores perímetros de irrigação com pivô central da América Latina. / The central pivot is an system of great importance, which uses much water resource during its working. The development of a working scale to the central pivots that act using one same water resource is a solution to reduce costs with electric energy and to control the water consumption being aimed at to avoid possible nature damages, without compromising its eficiency. To find such solution, a mathematical model that represents the problem was created and validated. This model was the base for the construction of algorithms which solving the scale of the central pivots. Due to the complexity of the problem, the use of metaheuristic Simulated Annealing and GRASP was adopted in the searches of good solutions in very small period of time. The application of the metaheuristics made very simply, offering the options to modify the parameters of the execution, in accordance with the found necessities, being possible to adapt the form of execution of the algorithms to the different realities. An interface that uses the algorithms was constructed with the objective to facilitate to the manipulation of the input and output of the system. The obtained results of tests with the system using both the algorithms had generated solutions that had taken care of the initial expectation fully being, also, evaluated for professionals of the area. Moreover, a case study, using the developed algorithms, were carried through with basis of information of the Project Colonização Paracatu Entre-Ribeiros, located in the Basin of the Rio São Francisco, one of the biggest perimeters of irrigation with central pivot of Latin America. / Dissertação antiga

Encontrar a estrutura de uma proteína arbitrária é vital para a compreensão da funcionalidade desta proteína. Muitos modelos foram desenvolvidos para a predição em primeiros princípios, entre eles modelos de grades. Em modelos de grades, cada aminoácido ocupa uma posição da grade, com aminoácidos consecutivos ocupando posições adjacentes. Uma possível conformação da proteína é dada por um caminho nesta grade. Em uma grade, temos várias formas de codificar computacionalmente uma seqüência de aminoácidos. O método mais usado é o de coordenadas internas, mas também encontramos na literatura codificações por coordenadas cartesianas e ângulos de torção. Neste trabalho, introduzimos uma nova codificação dos dados para modelos de grades. Nesta codificação, uma proteína com n aminoácidos é configurada como uma seqüência numérica, com valores variando entre 0 e no caso bidimensional e e no caso tridimensional. Nesta grade, os possíveis movimentos para cada aminoácido são intuitivos e correspondem a somar e subtrair 1 e n no caso bidimensional e , e no caso tridimensional. Para exemplificarmos o desenvolvimento desta nova codificação, desenvolvemos um algoritmo genético específico para o problema de predição da estrutura da proteína (PSP). Analisamos o desenvolvimento deste algoritmo em quatro modelos, , , e , e realizamos testes com proteínas encontradas na literatura e no Protein Data Bank. / Finding the structure of an arbitrary protein is vital for the understanding of its functionality. Many models had been developed for the ab initio prediction, and the lattice model is one of these models. Lattice models specify that each amino acid occupies a lattice position, consecutive amino acids occupy adjacent positions and a protein conformation is given by a path in this lattice. We have some forms to codify an amino acid sequence computationally. The main method is the usage of internal coordinates, however we can find in literature codifications using cartesian coordinates and torsion angles. We introduce a new codification of the data for lattice models, in which a protein with amino acids is configured as a numerical sequence in a three-dimensional lattice of size and all the possible movements for each amino acid are intuitive and correspond to add and to subtract , and . With the goal of exemplifying the development of this new codification, we construct a specific genetic algorithm for the protein structure prediction (PSP) problem. We analyze the development of this algorithm in four models, , , e , and tests using found proteins in literature and in the Protein Data Bank are carried out.

Submitted by EDUARDO BATISTA DE MORAES BARBOSA null (ebmb@yahoo.com) on 2016-07-22T20:43:38Z No. of bitstreams: 1 Thesis-Full.pdf: 4249671 bytes, checksum: 293e98d71cda47dab135797fedb06e6f (MD5) / Approved for entry into archive by Ana Paula Grisoto (grisotoana@reitoria.unesp.br) on 2016-07-25T17:18:40Z (GMT) No. of bitstreams: 1 barbosa_ebm_dr_guara.pdf: 4249671 bytes, checksum: 293e98d71cda47dab135797fedb06e6f (MD5) / Made available in DSpace on 2016-07-25T17:18:40Z (GMT). No. of bitstreams: 1 barbosa_ebm_dr_guara.pdf: 4249671 bytes, checksum: 293e98d71cda47dab135797fedb06e6f (MD5) Previous issue date: 2016-07-01 / A configuração de parâmetros de algoritmos, em especial, das meta-heurísticas, nem sempre é trivial e, frequentemente, é realizada ad hoc de acordo com o problema sob análise. A fim de resolver o problema de sintonização de meta-heurísticas, a presente pesquisa propõe uma metodologia que combina o uso de técnicas estatísticas robustas (ex.: Planejamento de Experimentos) e métodos eficientes de Inteligência Artificial (ex.: Algoritmos de Corrida). A ideia central desta metodologia é um método heurístico, denominado Algoritmo de Corrida Orientada por Heurística (HORA), capaz de explorar o espaço de busca para perseguir diferentes alternativas na vizinhança de uma configuração de parâmetros promissora e encontrar sistematicamente boas configurações candidatas para diferentes algoritmos. Em síntese, o método HORA concentra as buscas sobre configurações candidatas promissoras, criadas dinamicamente em um processo iterativo, e utiliza uma técnica estatística robusta para avaliar as diferentes alternativas e descartar aquelas de qualidade inferior, assim que reunir evidências estatísticas suficientes contra elas. A partir dos resultados de diversos estudos computacionais, em que diferentes meta-heurísticas foram aplicadas sobre dois problemas clássicos de otimização combinatória, apresentam-se evidências estatísticas que as sintonizações obtidas pelo HORA são competitivas em relação ao método de Corrida e seu tempo no processo de sintonização é amplamente vantajoso. Em um estudo complementar, um algoritmo já bem configurado da literatura foi sintonizado por meio da metodologia proposta e os resultados da nova sintonização foram comparados com a literatura. Os resultados demonstram que a sintonização obtida pelo HORA pode encontrar soluções de melhor qualidade em relação à sintonização original. Portanto, a partir dos resultados apresentados nesta pesquisa conclui-se que a metodologia para sintonização de meta-heurísticas por meio do método HORA é uma abordagem promissora que pode ser aplicada sobre diferentes meta-heurísticas para resolução de uma diversidade de problemas de otimização. / The fine-tuning of the algorithms parameters, specially, of the meta-heuristics, it is not always trivial and often is performed by ad hoc methods according to the problem under analysis. In order to solve the problem of tuning metaheuristics, this research proposes a methodology combining statistical robust techniques (e.g.: Design of Experiments) and efficient methods from Artificial Intelligence (e.g.: Racing Algorithms). The key idea of this methodology is a heuristic method, called Heuristic Oriented Racing Algorithm (HORA), which explores the search space looking for alternatives near of a promising candidate and consistently finds good candidates configuration for different algorithms. Briefly, HORA focuses its searches over the promising candidates configuration, dynamically created in an iterative process, and employs a robust statistical method to evaluate and discarding them, as soon as gather enough statistical evidence against them. The results of several studies, where different metaheuristics were applied to solve two classical combinatorial optimization problems, present statistical evidences that the settings obtained by HORA are competitive to the Racing Algorithms and its time in the fine-tuning process is widely advantageous. In a complementary study, an already well setting algorithm from the literature was tuned by means of the proposed methodology and the new settings were compared with the literature. The results show that the fine-tuning from HORA can find better quality solutions than the original ones. Therefore, from the results presented in this study it is concluded that the methodology for fine-tuning of metaheuristics by means of HORA is a promising approach, which can be applied on different metaheuristics to solve a diversity of optimization problems.

Tese (doutorado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2007. / Submitted by Larissa Ferreira dos Angelos (ferreirangelos@gmail.com) on 2009-12-22T18:47:27Z No. of bitstreams: 1 2007_MaxwellDiogenesBandeiradeMelo.PDF: 1367153 bytes, checksum: 730c589fb22b9faa5de16d3540a94af9 (MD5) / Approved for entry into archive by Daniel Ribeiro(daniel@bce.unb.br) on 2009-12-22T22:28:18Z (GMT) No. of bitstreams: 1 2007_MaxwellDiogenesBandeiradeMelo.PDF: 1367153 bytes, checksum: 730c589fb22b9faa5de16d3540a94af9 (MD5) / Made available in DSpace on 2009-12-22T22:28:18Z (GMT). No. of bitstreams: 1 2007_MaxwellDiogenesBandeiradeMelo.PDF: 1367153 bytes, checksum: 730c589fb22b9faa5de16d3540a94af9 (MD5) Previous issue date: 2007-05-02 / O objetivo deste trabalho é o desenvolvimento de uma técnica para a melhoria de curvas de temperatura medidas com cateteres Swan-Ganz, que melhoram o desempenho de técnicas desenvolvidas anteriormente. Nesta tese de doutorado, breves discussões sobre a fisiologia do sistema cardiovascular e sobre os métodos baseados em termodiluição são apresentadas. Em seguida, uma revisão bibliográfica apresenta os trabalhos anteriores que usaram operações de deconvolução para melhorar sinais de termodiluição. Para fundamentar o uso da técnica de termodiluição, um capítulo apresenta experimentos para a caracterização da resposta temporal do sensor embutido no cateter que é usado na medida de temperatura. O capítulo principal desta tese apresenta um novo método iterativo para a realização de deconvolução cega do sinal de termodiluição, que é baseada em um procedimento no domínio do tempo. Um grande número de simulações computacionais mostrou que o método funciona bem para freqüências cardíacas inferiores a 170 batimentos por minuto, para frações de ejeção menores que 0,7, e apresenta erros significativos fora desses limites. O método foi testado em dois simuladores mecânicos pulsáteis do sistema cardiovascular, e os resultados mostraram uma boa precisão do método, com um erro médio de 8,9%. O método proposto apresentou desempenho superior ao desempenho dos métodos anteriores, pois foi obtida uma resposta mais rápida, e os resultados independem da estimativa inicial para a resposta do sensor. _________________________________________________________________________________ ABSTRACT / The objective of this work is the development of a technique for the improvement of temperature curves measured by Swan-Ganz catheters, which improves the performance of previously developed techniques. In this dissertation, brief discussions on the physiology of the cardiovascular system and on the thermodilution-based method are presented. Later, a literature review summarizes the previous works that used deconvolution operations for improving thermodilution signals. In order to lay the foundation for the deconvolution technique, we present experiments for characterizing the time response of the sensor embedded in the catheter that is used for temperature measurement. The main chapter in this dissertation presents a new iterative method for performing the blind deconvolution of the thermodilution signal, which is based on a timedomain approach. A great number of computational simulations shows that the method works well for cardiac frequencies up to 170 beats per minute, and for ejection fractions that are smaller than 0,7, and have a significant error outside these boundaries. The method is then tested with data obtained in a mechanical pulsatile simulator of the cardiovascular system, and the results show a good precision of the method, with a mean error of 8,9%. The proposed method improved the performance of the previously reported methods, since it had a faster response, and the results are independent on the initial estimate for the sensor response.

Esta dissertação trata do planejamento do abastecimento de última milha em centros urbanos, propondo métodos para agrupar pedidos de clientes em programação de entregas. Neste estudo, é considerado que o frete pago ao transportador em uma rota é definido pela distância direta do ponto de entrega mais distante do depósito em contraposição à distância total da rota que é usual na literatura sobre problemas de roteirização de veículos. Além disso, também são consideradas categorias, conjunto de produtos similares, que não podem ser transportadas juntas por não serem compatíveis entre si. O objetivo do problema proposto é determinar o agrupamento e sequenciamento de pedidos em roteiros de veículos de acordo com as características operacionais descritas acima, utilizando uma frota homogênea de veículos capacitados que parte de um depósito, de tal forma que toda a demanda seja atendida com o menor frete possível. Para resolução desse problema são propostas uma formulação matemática para obtenção de soluções exatas e a implementação da heurística \"Multi Start Perturbation Tabu\" (MSPT) que é composta das metaheurísticas \"Greedy Randomized Adaptive Search Procedure\" (GRASP), \"Tabu Search\" (TS) e \"Iterated Local Search\" (ILS) para obtenção de soluções heurísticas. Os resultados experimentais indicam que a MSPT é competitiva com os resultados do método exato com até 5 horas de processamento utilizando os recursos computacionais de alto desempenho do Laboratório de Computação Científica Avançada (LCCA) da Universidade de São Paulo. / This dissertation addresses the planning of the last mile supply in urban centers and proposes methods to group customer orders into shipments. In this study, freight paid to the carrier on a route is defined as the direct distance from the point of delivery that is furthest from the depot as opposed to be defined as the total distance of the route which is commonly found in the literature on vehicle routing problems. In addition, it is also considered categories, a set of similar products, which cannot be transported together because they are not compatible with each other. The objective of the proposed problem is to determine the grouping and sequencing of orders into vehicle shipments according to the operational characteristics described above, using a homogeneous fleet of capacitated vehicles that is located in a depot, in such a way that all the demand is delivered with the lowest freight possible. To solve this problem, it is proposed a mathematical formulation to obtain exact solutions and the implementation of the Multi Start Perturbation Tabu (MSPT) heuristic that is composed of the Greedy Randomized Adaptive Search Procedure (GRASP), Tabu Search (TS) and \"Iterated Local Search\" (ILS) for heuristic solutions. Finally, the experimental results indicate that the MSPT is competitive with the outcomes of the exact method with up to 5 hours of processing using the high performance computational resources of the Advanced Scientific Computation Laboratory (LCCA) of the University of São Paulo (USP).

Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas. / Min-max relations are central objects in combinatorial optimization. They basically state that, in a given structure, the optimum value of a certain minimization problem equals the optimum value of a different, maximization problem. Relations of this kind provide good characterizations and polyhedral descriptions to several important problems and, moreover, they often come with efficient algorithms for the corresponding problems. Usually, such efficient algorithms are obtained naturally from the constructive proofs involved; even when that is not the case, these relations reveal enough of the combinatorial structure of the problem, leading to the development of efficient algorithms. The main focus of this dissertation is the study of these relations in graphs. Our emphasis is on directed graphs. We present Edmonds and Giles\' powerful polyhedral framework concerning submodular flows, as well as Frank\'s algorithm for a special case of this framework: the Lucchesi-Younger Theorem. We also derive several min-max relations about packing connectors, starting with Edmonds\' Disjoint Branchings Theorem and ending with Feofiloff-Younger and Schrijver\'s Disjoint Dijoins Theorem. We further derive some classical min-max relations on matchings, T-joins and S-paths. To this end, we use a theorem due to Frank, Tardos, and Sebö and a general framework due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour. Throughout the text, we illustrate several recurrent themes, such as the use of tools from polyhedral combinatorics, the uncrossing technique, the use of submodular functions, matroids and exchange properties, as well as some results involving forbidden substructures.