[pt] O Team Orienteering Problem é um problema de roteamento de veículos sobre um grafo com durações associadas aos arcos e prêmios atribuídos à visitação de cada vértice. Neste problema, considera-se que as visitas são realizadas por uma frota com um número fixo de veículos idênticos e que existe uma duração total máxima para as rotas serem finalizadas. Cada vértice pode ser visitado no máximo uma vez, não havendo obrigatoriedade de se visitar todos os vértices, devido à restrição que limita o tempo m´aximo de duração das rotas. O objetivo do problema é maximizar o prêmio total ganho por todas as rotas. Neste trabalho, foram propostas duas abordagens: uma exata e uma heurística. Na abordagem exata, foi desenvolvida uma formulação baseada em arcos e uma formulação estendida na qual cada arco tem um índice extra. Esse índice representa o tempo de partida de um veículo ao percorrer o arco. Através de transformações sobre a formulação estendida, foi obtida uma formulação, cuja relaxação, problema mestre restrito, foi resolvida pela técnica de geração de colunas. O subproblema de geração de colunas foi resolvido por programação dinâmica em tempo pseudo-polinomial. Este algoritmo gera rotas não elementares, que são rotas nas quais subciclos são permitidos. Com o objetivo de eliminar os subciclos das rotas não elementares, uma nova classe de desigualdades denominada min cut foi proposta. Aplicando-se um algoritmo Branch-Cut-and-Price (BCP) foram obtidos alguns novos limites superiores. A abordagem exata obteve resultados competitivos quando comparada ao melhor algoritmo exato já proposto para esse problema. Na abordagem heurística, além de uma vizinhança k-opt, foi explorada também uma busca elipsoidal que adiciona um corte à formulação do algoritmo Branch-Cut-and-Price. Esse novo corte reduz o espa¸co de busca a uma vizinhança em torno de um conjunto de soluções conhecidas. Essa busca é utilizada como um operador de crossover executado em todas as iterações de um algoritmo evolutivo. Essa abordagem converge em um tempo computacional razoável e encontra soluções ótimas ou próximas da ótima para algumas instâncias da literatura. / [en] Team Orienteering Problem is a vehicle routing problem on a graph with durations associated to the arcs and profits assigned to visiting the vertices. In this problem, a fleet with a fixed number of identical vehicles performs the visitations and there is a limited total duration for the routes to be ended up. Each vertex can be visited at most once and the solution does not have the obligation to visit all vertices, due to the constraint that limits the maximum duration of routes. The goal of the problem is to maximize the total profit gathered by all routes. In this work, two approaches have been proposed: an exact and a heuristic one. In the exact approach, we have developed an arc based formulation and an extended formulation where each arc has an extra index. This index represents the departure time of a vehicle using an arc. Through transformations on the extended formulation, we have obtained a formulation, whose relaxation - the restricted master problem - is solved using the column generation technique. A dynamic programming algorithm solves the column generation subproblem in pseudo-polynomial time. This algorithm generates non-elementary routes that allow subcycles. In order to cut off the subcycles, a new class of inequalities called min cut has been proposed.We have applied a Branch-Cut-and-Price (BCP) algorithm. This allowed finding some new upper bounds. The exact approach has achieved competitive results compared to the best exact algorithm has already proposed to this problem. In the heuristic approach, besides a kopt neighborhood, we have also exploited an ellipsoidal search that adds a new cut constraint to the formulation of Branch-Cut-and-Price algorithm. This new cut reduces the space search to a neighborhood around a known set of solutions. This search is used as a crossover operator that runs all iterations of a evolutive algorithm. This approach converges in a reasonable computational time and finds optimal or near optimal solutions for some instances in the literature.

[pt] Este trabalho faz reflexões sobre como é possível avançar na melhoria do gerenciamento de transporte, especificamente em relação às decisões mais operacionais, como a roteirização, através de métodos heurísticos simples e já difundidos na literatura. Utilizando um estudo de caso, é possível apresentar os benefícios da mudança de um método empírico de roteirização, totalmente baseado nos conhecimentos tácitos, para a aplicação de um método de criação de áreas de entregas e definição de rotas fixas de forma empírica. Além desta análise, o trabalho também apresenta a aplicação de um método dinâmico de roteirização utilizando o método de Clarke e Wright. Da comparação dos resultados obtidos surgem sugestões de criação de rotinas e ferramentas para aplicação do método, de forma consistente e definitiva, na operação da empresa do estudo de caso. / [en] In this research some considerations are made about the possibility of improving making the transportation management, specifically in operations decisions, like routing vehicles, using simple and well known heuristic methods mentioned in the literature. Using a case study, it is possible to show the benefits of changing an empirical routing method based on implicit knowledge towards an empirical application using fixed routes. In additional, is applied a dynamic routing method: the Clarke and Wright`s Method. Results are compared, and after that are recommended routine and tools development to use this application method, consistent and emphatically, in the company case study operation.

[pt] Uma família de programas pode degenerar devido a mudanças não planejadas e, consequentemente, tendem a prejudicar a manutenção dos membros da família. Esta degeneração é frequentemente causada pelo código de uma característica (feature) da família que é modificada individualmente em cada membro sem considerar outros membros da família. Em casos extremos, o código da família é completamente ou parcialmente replicado e individualmente modificado por diversos membros em evolução. Assim, à medida que uma família evolui, pode não ser mais possível identificar e classificar os elementos de código implementando as características comuns e variáveis. Uma das atividades iminentes para resolver esses problemas é a recuperação sensível à história de características da família. Este processo de recuperação inclui a análise histórica de cada membro da família a fim de identificar e classificar os elementos de implementação (e.g. métodos, atributos) de acordo com a sua natureza de variabilidade. Os trabalhos existentes falham em analisar a evolução dos membros de uma família com o objetivo de recuperar os elementos de implementação das características. Além disso, as técnicas existentes para a análise de características não são efetivas, pois elas apenas levam em consideração a história de um único membro por vez. Em resumo, as contribuições desta tese são divididas em três partes: (i) um catálogo de incompatibilidades de mapeamento para guiar engenheiros de software na corretude e completude de seus mapeamentos de características. Este catálogo é útil para garantir uma melhor eficácia do processo de recuperação durante a análise dos mapeamentos; (ii) um conjunto de cinco heurísticas para a expansão automática de mapeamentos de características ao longo do histórico da família de programas. Essas heurísticas são baseadas na análise histórica multi-dimensional da família e no catálogo de incompatibilidades de mapeamentos; e (iii) um conjunto de heurísticas sensíveis a história para classificar os elementos de implementação de cada característica da família de acordo com seu grau de variabilidade. / [en] A program family might degenerate due to unplanned changes in its implementation, thus hindering the maintenance of family members. This degeneration is often induced by feature code of the program family that is changed individually in each member without considering other family members. In extreme cases, the program family code is fully or partially replicated and individually changed across several evolving members. Hence, as a family evolves over time, it might no longer be possible to identify and classify the implementation elements realizing common and variable features. One of the imminent activities to address these problems is the history-sensitive recovery of program family s features. This recovery process encompasses the historical analysis of each family member in order to identify and classify the implementation elements (i.e. methods, attributes) according to their variability nature. Existing work fails to analyse the evolution of the family members with the goal of recovering features implementation elements. Additionally, existing techniques for feature analysis are not effective as they only take into consideration the history of a single member product. In summary, the contributions of this thesis are threefold: (i) a catalogue of mapping mismatches to guide software engineers in promoting the correctness and completeness of their feature mappings. This catalogue is useful to ensure a better effectiveness of the recovery process during the mapping analysis; (ii) a suite of five heuristics for the automatic expansion of feature mappings throughout the program family history. Those heuristics rely on both the multi-dimensional historical analysis of program families and the catalogue of mapping mismatches; and (iii) a suite of history-sensitive heuristics for classifying the implementation elements realizing each family feature according to their variability degree.

[pt] Esta tese define os problemas das p-medianas conectadas e o de localização de facilidades não-capacitadas conectadas. Possíveis aplicações incluem problemas de planejamento regional e o projeto de redes de telecomunicações ou de transporte. Para o primeiro problema, duas formulações de programação linear inteira são apresentadas e comparadas. Um destes modelos é adaptado para o segundo problema. Para o problema das p-medianas conectadas, algoritmos aproximados são desenvolvidos. Uma estratégia de busca local híbrida é proposta. Para acelerar as iterações do algoritmo de busca local, idéias como circularidade, melhoria iterativa e o descarte de vizinhos são incorporadas. Heurísticas GRASP e VNS são desenvolvidas incluindo a utilização de um filtro com o objetivo de diminuir os tempos de processamento e do procedimento de reconexão por caminhos com o objetivo de melhorar a qualidade das soluções encontradas. Diversos testes são realizados comparando-se esses algoritmos. Os resultados mostraram a necessidade de se executar um passo adicional de pós-otimização às heurísticas GRASP e VNS propostas. / [en] In this work, the connected p-median and the connected facility location problems are defined. Applications arise in regional planning, design of telecommunications and transportation networks. For the first problem, two integer linear programming formulations are proposed. Adaptations are made in one of these formulations and are used to model the second problem. Approximation algorithms to solve the connected p-median problem are developed. A hybrid local search strategy is proposed. In order to speed up the local search iterations, ideas as circularity, first- improving strategy and discard neighbors are incorporated. A GRASP algorithm and a VNS heuristic are also proposed. A filter is used to reduce the computational time required and a path-relinking is applied to improve the results found. Computational experiments to compare the algorithms are reported. To improve these results, it is applied a post-optimization step to the GRASP and VNS heuristics.

[pt] Nesta tese faz-se uma extensa revisão bibliográfica sobre o problema de Steiner na métrica retilínea, destacando-se a aplicação do mesmo no projeto de VLSI. São descritas em detalhes várias heurísticas existentes na literatura para as quais estudam-se a complexidade computacional e a qualidade das soluções obtidas. Além disso, são estabelecidos novos resultados relativos ao comportamento de pior caso destas heurísticas. Propõe-se, ainda, duas novas heurísticas para o problema de Steiner na métrica retilínea para as quais são estudadas a complexidade computacional e a qualidade da solução, inclusive com a análise do pior caso. Uma grande quantidade de testes computacionais permitiu a realização de uma comparação do desempenho das diversas heurísticas implementadas, concluindo-se que uma das novas heurísticas propostas fornece, em média, soluções melhores do que aquelas fornecidas pelas demais heurísticas conhecidas na literatura. / [en] In this dissertation we present a survey about the Steiner problem in the rectilinear metric, illustrating its applications to the VLSI desing. A large number of heurístics already described in literature is studied in details. Moreover, we study the complexity of these heuristics and the quality of their solutions. New results concerning their worst case behavior are stated. We also propose two new heuristics for thew Steiner problem in the rectilinear metric, for which we study the complexity and the quality of the solutions, including the worst case analysis. A large nember of computational experiments was conducted and allowed the comparison of the performances of the heuristics implemented. We conclude from these experiments that, in the average, the solutions obtained by one of the new heuristics are better than the solutions obtained by those alreafy available in the literature.

[pt] A principal contribuição desta tese consiste no desenvolvimento de uma heurística híbrida, robusta e eficiente, para o problema de empacotamento unidimensional. A heurística proposta utiliza os seguintes componentes: limites inferiores e superiores do número de caixas; reduções; abordagem dual para a obtenção de soluções iniciais; heurísticas para redistribuição dos pesos; e busca tabu. O outro objetivo desta tese é a aplicação desta heurística para a solução do problema de escalonamento em processadores paralelos idênticos. São apresentados resultados computacionais obtidos sobre centenas de problemas testes da literatura. / [en] We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several components: lower and upper bounds; reductions, construction of initial solutions by reference to the dual problem;heuristics for load redistribution based on dominance, differencing, and unbalancing; and tabu search. We also investigate the application of this hybrid heuristic to the problem of task scheduling on identical parallel processors. Computational results on hundreds of benchmark test problem are presented.

[pt] Nos últimos anos, considerável debate tem ocorrido a respeito do tema gerência de mobilidade, face à necessidade de se fazer uso judicioso dos recursos de sinalização destinados para esse fim no âmbito de sistemas de comunicação móvel celular e de sistemas de comunicação pessoal (PCS). Dentre as estratégias de gerência de mobilidade, destaca-se a utilização do conceito de áreas de registro, amplamente empregadas a partir dos sistemas de 2a. geração, e permitindo reduzir o consumo de recursos devido a atualizações de localização. Outro conceito, o de áreas de paging, tem também se tornado bastante difundido, propiciando a economia de recursos gastos na procura de terminais móveis por ocasião de tentativas de completamento de chamadas para estes terminais. Este trabalho inicia-se com discussão a respeito de modelos de mobilidade empregados no estudo de problemas e técnicas da área de comunicações móveis. Dentre tais modelos, destacam- se no contexto do trabalho o modelo baseado em fluxo de fluídos e o modelo gravitacional. O problema de particionamento em áreas de localização (LAPP) é então tratado como um problema de particionamento de grafos, cuja elevada complexidade enseja a utilização de heurísticas capazes de propiciar a obtenção de soluções próximas da ótima. As heurísticas propostas destinam-se ao caso mais comum, em que áreas de localização são coincidentes com áreas de paging. Com base em metodologia utilizada para o LAPP, são propostas soluções para um outro problema, o ISHMP (Inter-Switch Handover Minimization Problem), cuja importância se prende não só ao elevado consumo de recursos mas também aos atrasos impostos pelo sistema aos usuários quando estes trocam de área de Mobile Switching Center. Assim, reduzir ao máximo a ocorrência de tais eventos é vantajoso tanto do ponto de vista do usuário quanto do sistema. As heurísticas propostas são essencialmente as mesmas para ambos os problemas, e mostram superioridade em termos de qualidade das soluções obtidas quando comparadas com propostas de outros autores, através de casos-padrão publicados na literatura e de testbed construído especialmente para a comparação. Apresenta-se ainda discussão a respeito de modelos de mobilidade empregados no estudo de problemas e técnicas da área de comunicações móveis. Dentre tais modelos, destacam- se o modelo baseado em fluxo de fluidos e o modelo gravitacional. O trabalho apresenta também estudo relativo às cargas de sinalização que ocorrem tnato na rede fixa (incluindo o tráfego de consultas e atualizações sobre as bases de dados) quanto na interface aérea. No apêndice, considerando o grafo que modela a rede celular, apresenta-se comprovação formal da conversão de pesos de nós e de arestas em novos pesos de arestas, permitindo o tratamento dos dois problemas de particionamento aqui abordados como problemas de edgepartitioning puros. / [en] In the past few years there hás been considerable debate over the question of mobility management in móbile cellular communication networks, due to the need of using the signaling system resources in a careful way. Among the strategies of location management, the utilization of registration areas has been difunded since the emergence of the second generation mobile communication systems, allowing to reduce the resource consumption due to location updates. Another concept, named paging areas, has also been extensively employed, allowing to save resources utilized localization of mobile terminals during the call setup for mobile stations. Initially, the Location Area Partitioning Problem (LAPP) is treated as a graph partitioning problem, largely recognized as NP-complete ([GARE 79], [LENG 90]) and leading to the utilization of heuristics, able to produce good sub-optimal solutions. The heuristics are proposed to solve the more usual case, where location areas are coincident with paging areas, and the frequency spectrum (radio resources). With the same methodology, another problem, named Inter- Switch Handover Minimization Problem (ISHMP), is adequately solved, being its relevance due to the elevated system resource consumption and to the severe delays imposed to users when their Mobile Switching Centers are changed. Thus, the diminution of the occurrence of such events id advantageous from both the user`s and the system`s points of view. The heuristics are eddentially the same for the two problems, and it is shown the superiority of the quality of the quality of the obtained solutions, when comparing them with other published results. The work also presents discussion about mobility models employed in the study of problems and techniques in the mobile communications area. Among such models, the fluid flow and the gravitational models are highlighted. A study concerning to the signaling load imposed to the fixed network (including queries and location update traffic over databases) and to the air interface is presented. Finally, starting from the average rate of mobile terminated calls and from a previously defined user impatience threshold, a new proposal for the definition of the optimal number of cells per paging area is presented.

[pt] Neste trabalho é proposta uma metodologia de processamento da imagem associada a uma rede neural de perceptrons multicamadas, que é capaz de segmentar e reconhecer caracteres manuscritos cursivos. Esta técnica é robusta quanto à mudança na escala e translação dos caracteres, ligeiras variações na forma do caracter e ruído provocado pro tremores na mão do escritor. Pode ainda tornar-se robusta quanto à rotação, dependendo da escolha dos Descritores de Fourier. O método aproveita a existência de características geométricas e topológicas ou padrões de linhas. Estes componentes são fundamentais na construção da letra. São descritos pré-processamentos, que produzem os esqueletos dos caracteres, tais como algoritmos de afinamento e alisamento heurístico, filtragem zonal para atenuação de retas horizontais e verticais, detecção de contornos, extração heurística de características e a computação dos Descritores de Fourier representantes dos padrões de linha formadores dos caracteres. Após sua extração, as características são combinadas à entrada da rede neural de modo que cada combinação é reconhecida como pertencente a um determinado caracter. Para completar, os resultados do reconhecimento são combinados de modo a eliminar a interseção de classes proveniente das combinações comuns a vários caracteres. Esta metodologia procura a segmentação e o reconhecimento da forma de caracteres manuscritos, sem utilizar qualquer análise de contexto, o que naturalmente pode aumentar sua eficiência. / [en] This work introduces an image processing methodology that, associated with a multi-level neural network of perceptrons, is able to isolate and recognize cursive handwritten characters. The character isolation technique makes use of fundamental geometric and topological aspectos of the characters. The work describe procedures to extract the characters skeletons, such as thinning and smoothing heuristic algorithms, zoned filtering to attenuate horizontal and vertical lines, contour detection, heuristic extraction of characteristics and the computation of Fourier Descriptors representing the line patterns, that compose the characters. After character extraction, its combined characteristics are presented to a neural network in order to allow recognition (identification). Finally, the results of the character identification are combined to avoid classification intersections, due to common aspects in a number of characters. The introduced methodology concerns only with the segmentation and form identification of the characters. It does not adress any context analysis.

[pt] A importância do planejamento em logística ferroviária cresce a cada dia devido ao alto custo dos investimentos para o aumento da sua capacidade. Entretanto, planejar é uma atividade que exige uma representação suficientemente precisa da realidade estudada. Neste contexto, os modelos de programação matemática apresentam-se cada vez mais adequados. Isto decorre dos recentes avanços nos algoritmos e computadores disponíveis para sua resolução. Esta dissertação apresenta modelos e algoritmos para o planejamento ferroviário tático e estratégico, isto é feito estudando o Problema de Planejamento de Atendimento (PPA). Primeiramente este problema é considerado assumindo que toda a estrutura ferroviária está definida: a malha, a tração e os vagões disponíveis, os pátios para carga, descarga e transbordo, suas respectivas taxas de carga e descarga e as demandas previstas. Em seguida, a questão adicional de determinar os pátios onde paradas podem ser efetuadas é considerada. Finalmente, em uma terceira etapa, introduz-se a capacidade de se analisar os efeitos do congestionamento de trechos da malha e seu impacto nos tempos de circulação e na capacidade da estrutura logística. Modelos são apresentados para cada um dos níveis de complexidade do PPA. Algoritmos exatos e heurísticos e técnicas de pré- processamento, foram desenvolvidos para os tratamentos dos casos obtidos. Em todos os casos, foi possível resolver de maneira ótima ou quase ótima em tempo razoável, tanto em termos acadêmicos, como para a utilização prática. Resultados computacionais sobre um amplo conjunto de instâncias reais são apresentados. / [en] Planning in Railway Logistic is an activity with growing importance. This is due to the high costs of investment to increase the railway capacity. Nevertheless, planning in this context is a cumbersome task, since a precise representation is necessary to consider most relevant points in this activity. Mathematical programming is becoming one of the best ways derive precise representations and to solve them. This is due to the recent advances on algorithms and computers used in the resolution of mathematical programming problems. This dissertation presents models and algorithms for tactical and strategical railway planning what is done by studying a demand planning problem (PPA). First, this problem is considered assuming that all the railway structure is defined: the network, the locomotives and wagons available, the yards for loading and unloading with their respective rates, and the forecast of demands. Next, the question of deciding the yards to stop is considered. Finally, in a third step, the effect of congestion in parts of the network is introduced to the models. This allows analyzing the variation in the travel times and its consequence in the logistic structure capacity. Models are presented for all cases of the PPA. Exact and heuristic algorithms, as well as pre-processing techniques, are described for the problem resolution. In all cases, the resulting approach allowed to solve the problems optimally or quasioptimally in a reasonable computing time. Computational results are presented on a wide set of real world instances.

[pt] Construção de vocabulário é uma heurística para problemas de otimização combinatória que propõe identificar porções de boas soluções e recombiná-las de modo a intensificar a busca em regiões do espaço de soluções identificadas como promissoras. A técnica de construção de vocabulário pode ser aplicada de diversas maneiras na resolução de problemas. Para facilitar a implementação e comparação de algoritmos de um mesmo domínio, a tecnologia de frameworks é uma solução que já demonstrou ser muito eficaz. O objetivo deste trabalho é desenvolver um framework para a implementação de heurísticas baseadas em construçao de vocabulário. O desenvolvimento foi fundamentado em extensa revisão bibliográfica sobre a técnica e em boas práticas de engenharia de software, como frameworks orientados a objetos e padrões de projeto. Como um estudo de caso, foram geradas aplicações a partir do framework para a resolução do problema de seqüenciamento da produção de carros, que é um problema combinatório proposto a partir de necessidades reais da indústria / [en] Vocabulary building is a heuristic for solving combinatorial optimization problems, based on the identification of solution fragments which are common to good solutions and on their combination to intensify the search on promising regions of the solution space. This technique can be vastly applied on problem solving. The technology of frameworks is an efficient strategy to facilitate the implementation and comparison of same domain algorithms. The objective of this work is to develop a framework for the implementation of heuristics based on vocabulary building. Its development was based on a wide bibliographic revision about the technique and good software engineering practices, like oriented objects frameworks and design patters. We generated applications of the framework to solve the car sequencing problem, which is a combinatorial problem proposed by real requirements of the industry