[pt] Este trabalho faz uma recapitulação de algumas técnicas para o dimensionamento de redes de comunicação de dados por comutação de pacotes. Os aspectos do dimensionamento aqui abordados são: a alocação de capacidade e o encaminhamento do tráfego. O emprego de métodos heurísticos no dimensionamento deste tipo de rede mostrou ser possível diminuir o custo da mesma dividindo-se o tráfego de pacotes em classes de prioridade. Neste trabalho é apresentado um método ótimo para a consignação de capacidades em redes com prioridade, que permite julgar a eficiência de diversas técnicas heurísticas. O encaminhamento do tráfego dividido em classes de prioridade também é tratado, se bem que de forma mais supercial. Finalmente é apresentado um algoritmo para a alocação de capacidades e encaminhamento do tráfego simultaneamente, este algoritmo é testado para o caso com uma única classe de prioridade. / [en] The work begins with a rewiew of some Project techniques for packet switching data communication networks. Two aspects of the project are studied: the capacity assignment and the traffic routing. It has already been shown by means of heuristic methods used in the project of this kind of network that it is possible to decrease the cost of the network by dividing the packet traffic into priority classes. In this work we present an optimal method to establish the capacity assignment of networks which are designed to fulfill a priority phylosophy. This method allows evaluation of several heuristic techniques. The traffic routing divided in priority classes is also studied, but in a superficial way. Finally, an algorithm with the aim of attaining the simultaneous capacity and flow assignment is proposed. This algorithm is tested in a sample with only one priority.

[pt] O trabalho propõe um método heurístico para a análise de modelos de redes de filas fechadas, denominado algoritmo linearizado de redes simplificado (ALS), o qual é o resultado de uma simplificação no Algoritmo Linearizador original. O ALS mostrou-se interessante na análise de redes de grande porte (redes com mais de 10 classes de usuários) por apresentar um tempo de processamento bastante pequeno, se comparado com o tempo do Algoritmo Linearizador e de outros algoritmos existentes na literatura. É apresentado também a definição de um método aproximado para a integração dos mecanismos de encaminhamento e controle de fluxo em redes de computadores comutados por pacote. Resultados de simulação mostram que com esse esquema é possível utilizar de uma maneira bastante eficiente os recursos da rede. / [en] This work presents a heuristic method called Simplifield Linearizer Algorithm for analyisis of closed queueing network models. The proposed method from some simplifications introduced in the original Linearizer Algorithm. The Simplified Linearizer Algorithm is quite useful in the analysis of large network (network with more than ten user classes) due to its smaller processing time as compared with the processing time required by the Linearizer Algorithm and others describ in the literature. Also, this work defines an approximate method for the integration of the routing and flow control mechanism in packet switching computer networks. Simulation results shom that this integration scheme improves the efficiency associated with the utilization of the network resources.

Submitted by Haroudo Xavier Filho (haroudo.xavierfo@ufpe.br) on 2016-02-25T17:38:28Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) ppgee_ufpe_tese_danilo_araujo_d56.pdf: 4766595 bytes, checksum: d35136114bc3c8b6116c06920b45e876 (MD5) / Made available in DSpace on 2016-02-25T17:38:28Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) ppgee_ufpe_tese_danilo_araujo_d56.pdf: 4766595 bytes, checksum: d35136114bc3c8b6116c06920b45e876 (MD5) Previous issue date: 2015-07-21 / CNPq / A infraestrutura de transporte para Internet e outros serviços de telecomunicações que exigem elevada taxa de transmissão é constituída basicamente por redes de comunicações ópticas. Em redes com estabelecimento dinâmico de requisições, algumas das requisições podem não ser atendidas devido à indisponibilidade de um caminho óptico, decorrente da ausência de um canal ou de restrições de Qualidade de Transmissão (QoT). A probabilidade de bloqueio de requisições (PB) pode ser usada para medir o desempenho deste tipo de rede. PB pode ser estimada por expressões analíticas ou por simuladores de eventos discretos. Expressões analíticas possuem baixo custo computacional, mas são aplicadas apenas em cenários muito simples. Simuladores facilitam a estimativa de PB em cenários mais complexos, mas apresentam elevado custo computacional, pois exigem um grande número de requisições para uma estimativa precisa. Algoritmos evolucionários foram usados em trabalhos anteriores sobre planejamento de redes, mas eles apresentam elevado custo computacional, pois ativam o estimador de PB diversas durante o processo. Nesta Tese é proposta uma nova abordagem para planejamento de redes baseada em conceitos de Ciência das Redes e de Inteligência Computacional. São propostas novas métricas, um estimador de PB baseado em redes neurais e um novo algoritmo de planejamento que usa o conceito de modelos substitutos. De acordo com os resultados obtidos, o novo método de estimativa de PB possui um tempo até 72 vezes menor do que o obtido por um simulador e o erro de estimativa é da ordem de 104, para uma rede óptica de 18 nós. Diversos cenários de projeto de redes foram analisados e o novo algoritmo de planejamento oferece uma redução do tempo de execução de até 88% sobre as propostas anteriores, baseadas em algoritmos evolucionários e simuladores de rede. / The transport infrastructure for the Internet and other telecommunications services that require high transmission rate is comprised basically of optical communication networks. If networks with dynamic tra c are used, some requests could not be established due to the absence of an optical channel or due to restrictions in the Quality of Transmission (QoT). The blocking probability (BP) can be used to measure the performance of this kind of networks. BP can be estimated by analytical expressions or by discrete event simulators. Analytical expressions provide low computational cost, but they can be used only in very simple scenarios. Simulators facilitate the estimation of BP in more complex scenarios, but they present a high computational cost due to the large number of calls which is necessary to provide an accurate estimation. Evolutionary algorithms were used in previous works about design of optical networks, but they present high computational cost, since they activate the BP estimator several times to plan a single network. This Thesis proposes a new approach to design optical networks based on Network Science and Computational Intelligence. We propose new metrics, a new method to estimate BP based on neural networks and a new planning approach based on surrogate models. From the results, the proposed BP estimator presents a speedup of 72 over a network simulator and presents estimation errors in the order of 104, for an optical network with 18 nodes. Di erent scenarios for optical network design were evaluated and the new proposal o ers a reduction in processing time up to 88% when it is compared with previous approaches, that are based on evolutionary algorithms and network simulators.

Problemas de projeto de redes (PPRs) são muito importantes uma vez que envolvem uma série de aplicações em áreas da engenharia e ciências. Para solucionar as limitações de algoritmos convencionais para PPRs que envolvem redes complexas do mundo real (em geral modeladas por grafos completos ou mesmo esparsos de larga-escala), heurísticas, como os algoritmos evolutivos (EAs), têm sido investigadas. Trabalhos recentes têm mostrado que estruturas de dados adequadas podem melhorar significativamente o desempenho de EAs para PPRs. Uma dessas estruturas de dados é a representação nó-profundidade (NDE, do inglês Node-depth Encoding). Em geral, a aplicação de EAs com a NDE tem apresentado resultados relevantes para PPRs de larga-escala. Este trabalho investiga o desenvolvimento de uma nova representação, baseada na NDE, chamada representação nó-profundidade-grau (NDDE, do inglês Node-depth-degree Encoding). A NDDE é composta por melhorias nos operadores existentes da NDE e pelo desenvolvimento de novos operadores de reprodução possibilitando a recombinação de soluções. Nesse sentido, desenvolveu-se um operador de recombinação capaz de lidar com grafos não-completos e completos, chamado EHR (do inglês, Evolutionary History Recombination Operator). Foram também desenvolvidos operadores de recombinação que lidam somente com grafos completos, chamados de NOX e NPBX. Tais melhorias tem como objetivo manter relativamente baixa a complexidade computacional dos operadores para aumentar o desempenho de EAs para PPRs de larga-escala. A análise de propriedades de representações mostrou que a NDDE possui redundância, assim, foram propostos mecanismos para evitá-la. Essa análise mostrou também que o EHR possui baixa complexidade de tempo e não possui tendência, além de revelar que o NOX e o NPBX possuem uma tendência para árvores com topologia de estrela. A aplicação de EAs usando a NDDE para PPRs clássicos envolvendo grafos completos, tais como árvore geradora de comunicação ótima, árvore geradora mínima com restrição de grau e uma árvore máxima, mostrou que, quanto maior o tamanho das instâncias do PPR, melhor é o desempenho relativo da técnica em comparação com os resultados obtidos com outros EAs para PPRs da literatura. Além desses problemas, um EA utilizando a NDE com o operador EHR foi aplicado ao PPR do mundo real de reconfiguração de sistemas de distribuição de energia elétrica (envolvendo grafos esparsos). Os resultados mostram que o EHR possibilita reduzir significativamente o tempo de convergência do EA / Network design problems (NDPs) are very important since they involve several applications from areas of Engineering and Sciences. In order to solve the limitations of traditional algorithms for NDPs that involve real world complex networks (in general, modeled by large-scale complete or sparse graphs), heuristics, such as evolutionary algorithms (EAs), have been investigated. Recent researches have shown that appropriate data structures can improve EA performance when applied to NDPs. One of these data structures is the Node-depth Encoding (NDE). In general, the performance of EAs with NDE has presented relevant results for large-scale NDPs. This thesis investigates the development of a new representation, based on NDE, called Node-depth-degree Encoding (NDDE). The NDDE is composed for improvements of the NDE operators and the development of new reproduction operators that enable the recombination of solutions. In this way, we developed a recombination operator to work with both non-complete and complete graphs, called EHR (Evolutionary History Recombination Operator). We also developed two other operators to work only with complete graphs, named NOX and NPBX. These improvements have the advantage of retaining the computational complexity of the operators relatively low in order to improve the EA performance. The analysis of representation properties have shown that NDDE is a redundant representation and, for this reason, we proposed some strategies to avoid it. This analysis also showed that EHR has low running time and it does not have bias, moreover, it revealed that NOX and NPBX have bias to trees like stars. The application of an EA using the NDDE to classic NDPs, such as, optimal communication spanning tree, degree-constraint minimum spanning tree and one-max tree, showed that the larger the instance is, the better the performance will be in comparison whit other EAs applied to NDPs in the literatura. An EA using the NDE with EHR was applied to a real-world NDP of reconfiguration of energy distribution systems. The results showed that EHR significantly decrease the convergence time of the EA

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2008. / Submitted by Kelly Marques (pereira.kelly@gmail.com) on 2009-10-30T19:36:09Z No. of bitstreams: 1 2008_AlexandrePiqueira.pdf: 1919215 bytes, checksum: 870260cb82b8eb38fe69b000d99be69f (MD5) / Approved for entry into archive by Tania Milca Carvalho Malheiros(tania@bce.unb.br) on 2009-11-10T11:11:51Z (GMT) No. of bitstreams: 1 2008_AlexandrePiqueira.pdf: 1919215 bytes, checksum: 870260cb82b8eb38fe69b000d99be69f (MD5) / Made available in DSpace on 2009-11-10T11:11:51Z (GMT). No. of bitstreams: 1 2008_AlexandrePiqueira.pdf: 1919215 bytes, checksum: 870260cb82b8eb38fe69b000d99be69f (MD5) Previous issue date: 2008-10-30 / Redes de transmissão ópticas, de última geração, como a ASON – Automatic Switched Optical Network, proporcionam facilidades de operação, robustez às redes e novos desafios para os projetistas. Projetar redes ópticas de transmissão de dados, capazes de suportar múltiplas falhas com o menor custo possível e utilizando métodos de proteção aplicados em uma topologia em malha, é uma tarefa complexa que requer auxílio computacional. Esta complexidade resulta da análise obrigatória de cada uma das centenas, ou até milhares, de rotas possíveis para se levar demandas de tráfego de cada par “origemdestino”, visando encontrar a melhor distribuição, reduzindo a quantidade de banda a ser provisionada para fins de recuperação de falhas. O modelo de distribuição de tráfego proposto foi baseado em um híbrido entre proteção de caminho, 1:1 ou 1+1, e recuperação de falha através de reroteamento. Conhecido como PRC – Proteção e Restauração Combinadas, quando há uma combinação de falhas que interrompa o tráfego, a restauração de Caminho é acionada para aprovisionar automaticamente uma nova rota entre os nós de origem e de destino. Os resultados das simulações indicam que, para se alcançar valores máximos de recuperação contra duplas falhas, a conectividade entre os nós da rede é o mais importante. Em redes de topologias aleatórias com grau de conectividade médio pouco abaixo de 3, a proteção de caminho apresentou baixa imunidade à dupla falha de enlaces, em torno de 68% a 72%, e baixa reserva de banda, enquanto que a Proteção e Restauração Combinadas apresentam 90-97% de imunidade e reserva de banda cerca de 47% maior que o encontrado anteriormente. Para reduzir a quantidade de banda reservada para recuperação após dupla falha de enlaces, criamos o modelo PRC-RE, Proteção e Restauração Combinadas – Reuso de Enlace, e alcançamos a mesma imunidade do PRC, porém, com reserva de banda entre 16% e 25% maior que a alcançada pela proteção de caminho. _________________________________________________________________________________________ ABSTRACT / The latest generation optical transmission networks, such as ASON - Automatic Switched Optical Network, provide facilities for operation, robustness to networks and new challenges for designers. Designing optical networks for data transmission, capable of supporting multiple failures with minimal cost using methods of protection applied in a mesh topology, is a complex task that requires computer aid. This complexity result from mandatory review of each hundreds or even thousands, of possible routes to take traffic demands of each pair "origin-destination", aimed at finding the best distribution, reducing the amount of bandwidth to be provisioned for failures recover. The traffic distribution model proposed was based on a hybrid between path protection, 1:1 and 1 +1, and failure recovery through rerouting. In PRC - Protection and Restoration Combined, when there is a combination of failures that disrupts traffic, the path restoration process is automatically triggered to supply a new route between the nodes of origin and destination. Simulations results indicate that to achieve maximum recovery from double failures, the connectivity between the nodes of the network is the most important. In Random networks topologies with a degree of connectivity average just under 3, the path protection had low immunity to the double failures of links, around 68% to 72%, and low bandwidth allocation, while the Protection and Restoration Combined have 90-97% of immunity and bandwidth allocation about 47% higher than the previously found. To reduce the amount of bandwidth reserved for recovery after links double failures, created the model PRC-RE, Proteção e Restauração Combinadas – Reuso de Enlace, and achieve the same immunity of the PRC, however, with reservation of bandwidth between 16% and 25 % higher than that achieved by path protection.

Problemas de projeto de redes (PPRs) são muito importantes uma vez que envolvem uma série de aplicações em áreas da engenharia e ciências. Para solucionar as limitações de algoritmos convencionais para PPRs que envolvem redes complexas do mundo real (em geral modeladas por grafos completos ou mesmo esparsos de larga-escala), heurísticas, como os algoritmos evolutivos (EAs), têm sido investigadas. Trabalhos recentes têm mostrado que estruturas de dados adequadas podem melhorar significativamente o desempenho de EAs para PPRs. Uma dessas estruturas de dados é a representação nó-profundidade (NDE, do inglês Node-depth Encoding). Em geral, a aplicação de EAs com a NDE tem apresentado resultados relevantes para PPRs de larga-escala. Este trabalho investiga o desenvolvimento de uma nova representação, baseada na NDE, chamada representação nó-profundidade-grau (NDDE, do inglês Node-depth-degree Encoding). A NDDE é composta por melhorias nos operadores existentes da NDE e pelo desenvolvimento de novos operadores de reprodução possibilitando a recombinação de soluções. Nesse sentido, desenvolveu-se um operador de recombinação capaz de lidar com grafos não-completos e completos, chamado EHR (do inglês, Evolutionary History Recombination Operator). Foram também desenvolvidos operadores de recombinação que lidam somente com grafos completos, chamados de NOX e NPBX. Tais melhorias tem como objetivo manter relativamente baixa a complexidade computacional dos operadores para aumentar o desempenho de EAs para PPRs de larga-escala. A análise de propriedades de representações mostrou que a NDDE possui redundância, assim, foram propostos mecanismos para evitá-la. Essa análise mostrou também que o EHR possui baixa complexidade de tempo e não possui tendência, além de revelar que o NOX e o NPBX possuem uma tendência para árvores com topologia de estrela. A aplicação de EAs usando a NDDE para PPRs clássicos envolvendo grafos completos, tais como árvore geradora de comunicação ótima, árvore geradora mínima com restrição de grau e uma árvore máxima, mostrou que, quanto maior o tamanho das instâncias do PPR, melhor é o desempenho relativo da técnica em comparação com os resultados obtidos com outros EAs para PPRs da literatura. Além desses problemas, um EA utilizando a NDE com o operador EHR foi aplicado ao PPR do mundo real de reconfiguração de sistemas de distribuição de energia elétrica (envolvendo grafos esparsos). Os resultados mostram que o EHR possibilita reduzir significativamente o tempo de convergência do EA / Network design problems (NDPs) are very important since they involve several applications from areas of Engineering and Sciences. In order to solve the limitations of traditional algorithms for NDPs that involve real world complex networks (in general, modeled by large-scale complete or sparse graphs), heuristics, such as evolutionary algorithms (EAs), have been investigated. Recent researches have shown that appropriate data structures can improve EA performance when applied to NDPs. One of these data structures is the Node-depth Encoding (NDE). In general, the performance of EAs with NDE has presented relevant results for large-scale NDPs. This thesis investigates the development of a new representation, based on NDE, called Node-depth-degree Encoding (NDDE). The NDDE is composed for improvements of the NDE operators and the development of new reproduction operators that enable the recombination of solutions. In this way, we developed a recombination operator to work with both non-complete and complete graphs, called EHR (Evolutionary History Recombination Operator). We also developed two other operators to work only with complete graphs, named NOX and NPBX. These improvements have the advantage of retaining the computational complexity of the operators relatively low in order to improve the EA performance. The analysis of representation properties have shown that NDDE is a redundant representation and, for this reason, we proposed some strategies to avoid it. This analysis also showed that EHR has low running time and it does not have bias, moreover, it revealed that NOX and NPBX have bias to trees like stars. The application of an EA using the NDDE to classic NDPs, such as, optimal communication spanning tree, degree-constraint minimum spanning tree and one-max tree, showed that the larger the instance is, the better the performance will be in comparison whit other EAs applied to NDPs in the literatura. An EA using the NDE with EHR was applied to a real-world NDP of reconfiguration of energy distribution systems. The results showed that EHR significantly decrease the convergence time of the EA

Esta pesquisa trata do projeto de redes de distribuição de carga parcelada. Mais especificamente são tratados dois tipos de problemas que são comuns no planejamento desse tipo de sistema. O primeiro deles corresponde ao problema estratégico de configuração de redes do tipo hub-and-spoke, consistindo na definição simultânea da quantidade e localização de terminais para consolidação de carga (ou hubs), e na definição da alocação dos terminais aos hubs localizados. Uma vez determinada a configuração da rede, o segundo problema, no nível de decisão tático, corresponde na definição do caminho que cada carga parcelada deve percorrer desde sua origem até alcançar seu terminal de destino, a um mínimo custo, tendo a rede hub-and-spoke como um dado de entrada do problema. Um novo modelo matemático é proposto para representar o problema estratégico de configuração de uma rede hub-and-spoke, possuindo uma menor quantidade de variáveis e restrições, ao se comparar com outros modelos matemáticos comumente utilizados para representar o problema. Esse novo modelo matemático permitiu a obtenção de soluções ótimas para problemas em redes com até 100 terminais, sendo apresentada pela primeira vez a solução ótima para problemas utilizados como benchmark na literatura. Dado que problemas de grande porte ainda continuam muito difíceis de serem resolvidos, são propostas três variantes de uma heurística simples e eficiente utilizando técnicas de multi-início e busca tabu, bem como uma heurística integrada em dois estágios baseada em busca tabu para solução. Experimentos computacionais utilizando dados tradicionalmente utilizados na literatura para solução de problemas de configuração de redes hub-and-spoke (conjuntos de dados CAB e AP), bem como instâncias novas e modificadas, mostraram que a abordagem utilizada para solução do problema possibilitou a obtenção da solução ótima, ou a melhor solução conhecida, para esses problemas em um tempo de processamento muito curto, permitindo assim resolver de forma eficiente problemas de grande porte, nunca antes resolvidos em pesquisas anteriores. O segundo problema foi motivado por uma aplicação prática de uma empresa de transporte rodoviário de cargas parceladas no Brasil. O problema diz respeito ao planejamento de carregamentos a serem realizados em cada terminal, levando-se em consideração cada carga parcelada que precisa ser transportada, definindo o percurso que cada carga deve percorrer até chegar ao seu destino. É proposto um modelo matemático e, dada a dificuldade para se resolver problemas de tamanho como o encontrado na prática, é proposto também um método de solução utilizando metaheurística busca tabu. Experimentos computacionais realizados mostraram que a heurística proposta pôde efetivamente resolver problemas de tamanho como o encontrado na prática. / This research deals with problems related to distribution networks for less-than-truckload (LTL) freight transportation. More specifically, we deal with two relevant problems that arise. The first corresponds to the strategic problem of designing and configuring hub-and-spoke networks in terms of simultaneously determining the optimal number of consolidation terminals (hub) nodes, their locations and the allocation of the other terminals (spokes) to the hubs. . Once the network configuration is determined, the second problem, in the tactical level of decision, corresponds to defining the path that each LTL individual freight needs to follow from its origin to reach its destination terminal, at a minimum cost, having a hub-and-spoke network topology as a data entry to the problem. A new mathematical model is proposed to represent the strategic problem of designing a hub-and-spoke network, with fewer variables and constraints than previous formulations found in the literature This model allowed us to obtain optimal solutions for problems in transportation networks with up to 100 terminals, reporting for the first time the optimal solutions of benchmark problems in the literature. Since this problems still remains too hard to solve for larger instances, we propose we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve it. Computational experiments using typical benchmark problems (CAB and AP data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. The second problem is motivated by a practical application of a LTL transportation company in Brazil. It deals with the planning of loads to be done at each terminal, taking into account each LTL freight that needs to be transported, defining the path that each good needs to follow to reach its destination. A new mathematical model is proposed, and, since real world problems are very hard to solve, a heuristic based on tabu search is also developed. Computational experiments show that our heuristic can effectively solve real-world instances from a trucking company in Brazil.

Esta pesquisa trata do projeto de redes de distribuição de carga parcelada. Mais especificamente são tratados dois tipos de problemas que são comuns no planejamento desse tipo de sistema. O primeiro deles corresponde ao problema estratégico de configuração de redes do tipo hub-and-spoke, consistindo na definição simultânea da quantidade e localização de terminais para consolidação de carga (ou hubs), e na definição da alocação dos terminais aos hubs localizados. Uma vez determinada a configuração da rede, o segundo problema, no nível de decisão tático, corresponde na definição do caminho que cada carga parcelada deve percorrer desde sua origem até alcançar seu terminal de destino, a um mínimo custo, tendo a rede hub-and-spoke como um dado de entrada do problema. Um novo modelo matemático é proposto para representar o problema estratégico de configuração de uma rede hub-and-spoke, possuindo uma menor quantidade de variáveis e restrições, ao se comparar com outros modelos matemáticos comumente utilizados para representar o problema. Esse novo modelo matemático permitiu a obtenção de soluções ótimas para problemas em redes com até 100 terminais, sendo apresentada pela primeira vez a solução ótima para problemas utilizados como benchmark na literatura. Dado que problemas de grande porte ainda continuam muito difíceis de serem resolvidos, são propostas três variantes de uma heurística simples e eficiente utilizando técnicas de multi-início e busca tabu, bem como uma heurística integrada em dois estágios baseada em busca tabu para solução. Experimentos computacionais utilizando dados tradicionalmente utilizados na literatura para solução de problemas de configuração de redes hub-and-spoke (conjuntos de dados CAB e AP), bem como instâncias novas e modificadas, mostraram que a abordagem utilizada para solução do problema possibilitou a obtenção da solução ótima, ou a melhor solução conhecida, para esses problemas em um tempo de processamento muito curto, permitindo assim resolver de forma eficiente problemas de grande porte, nunca antes resolvidos em pesquisas anteriores. O segundo problema foi motivado por uma aplicação prática de uma empresa de transporte rodoviário de cargas parceladas no Brasil. O problema diz respeito ao planejamento de carregamentos a serem realizados em cada terminal, levando-se em consideração cada carga parcelada que precisa ser transportada, definindo o percurso que cada carga deve percorrer até chegar ao seu destino. É proposto um modelo matemático e, dada a dificuldade para se resolver problemas de tamanho como o encontrado na prática, é proposto também um método de solução utilizando metaheurística busca tabu. Experimentos computacionais realizados mostraram que a heurística proposta pôde efetivamente resolver problemas de tamanho como o encontrado na prática. / This research deals with problems related to distribution networks for less-than-truckload (LTL) freight transportation. More specifically, we deal with two relevant problems that arise. The first corresponds to the strategic problem of designing and configuring hub-and-spoke networks in terms of simultaneously determining the optimal number of consolidation terminals (hub) nodes, their locations and the allocation of the other terminals (spokes) to the hubs. . Once the network configuration is determined, the second problem, in the tactical level of decision, corresponds to defining the path that each LTL individual freight needs to follow from its origin to reach its destination terminal, at a minimum cost, having a hub-and-spoke network topology as a data entry to the problem. A new mathematical model is proposed to represent the strategic problem of designing a hub-and-spoke network, with fewer variables and constraints than previous formulations found in the literature This model allowed us to obtain optimal solutions for problems in transportation networks with up to 100 terminals, reporting for the first time the optimal solutions of benchmark problems in the literature. Since this problems still remains too hard to solve for larger instances, we propose we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve it. Computational experiments using typical benchmark problems (CAB and AP data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. The second problem is motivated by a practical application of a LTL transportation company in Brazil. It deals with the planning of loads to be done at each terminal, taking into account each LTL freight that needs to be transported, defining the path that each good needs to follow to reach its destination. A new mathematical model is proposed, and, since real world problems are very hard to solve, a heuristic based on tabu search is also developed. Computational experiments show that our heuristic can effectively solve real-world instances from a trucking company in Brazil.

Nos últimos anos, tem sido evidente a importância dos sistemas de cadastro territorial. Isso tem ocorrido, principalmente, devido à sua crescente função no desenvolvimento econômico, e no gerenciamento ambiental. Dentre os elementos fundamentais de um sistema cadastral, destaca-se o custo do cadastramento, o qual deve ser compatível com a utilidade de cada imóvel cadastrado. Nesse contexto, e considerando as exigências da Lei 10.267, este trabalho demonstra que certas características das redes geodésicas de apoio ao cadastro influenciam determinantemente nos custos do cadastramento dos imóveis rurais e, portanto, que tais características devem ser cuidadosamente consideradas quando da implantação e manutenção de sistemas cadastrais. É introduzido o conceito de operacionalidade, como mais um parâmetro a ser maximizado na elaboração de um novo projeto, ou na análise de uma rede já existente. A determinação dos parâmetros de operacionalidade fundamentou-se na identificação e atribuição de \"pesos\" às características dos vértices, através de uma pesquisa entre profissionais e estudiosos da área, e mediante o envio de dezenas de questionários. Dessa pesquisa foi possível inferir que os atributos relacionados ao acesso, monumentação do vértice, uso de receptores GPS e uso por estação total, têm o mesmo peso, sendo que uma importância menor foi atribuída às facilidades logísticas locais. Ficou demonstrado também que, além dos atributos dos vértices, a densidade da rede também influencia a operacionalidade. Utilizando-se de simulações, e tendo como referência uma região piloto, selecionada dentro do Estado de São Paulo, quantificou-se a influência da densidade que, agregada às características dos vértices, permitiu desenvolver um método para obtenção de um indicador numérico da operacionalidade, o qual denominou-se Índice de Operacionalidade. O trabalho permitiu, ainda, separar as redes em 4 classes de operacionalidade, de acordo com a expectativa de dispêndio de tempo para a implantação de uma base topográfica de apoio aos levantamentos cadastrais de imóveis rurais. / In the last few years, it has been noticeable the importance of territorial cadastre systems. This is happening mainly because of its increasing function in economic development, and in environmental managing. Among the fundamental elements of a cadastre system, the cadastral cost, which must be compatible with the utility of each cadastred land parcel, is emphasized. In this context, and considering the 10.267 Law demands, the present study shows that certain characteristics of reference geodetic networks have influence in a determinant way in the costs of rural cadastre, and for that, these characteristics must be carefully considered when implementing and maintaining cadastral systems. The functionality concept was introduced as one more parameter to be maximized when elaborating a new project, or in the analysis of an already existing network. The determination of functionality elements was based in the identification and attribution of \"weighs\" to the network stations characteristics through an investigation by mailing questionnaires to surveyors and researchers. From this investigation, it was possible to infer that the attributes related to the network stations access, monuments, functionality for GPS and total station surveys have the same weigh, however local logistics facilities have been attributed with less importance. It was also demonstrated that, besides the network stations attributes, the network density also influences the functionality. Using simulations, and having as reference a pilot area, selected within São Paulo state, it was quantified the density influence that, together with the network stations characteristics, allowed the development of a method to obtain a numerical indicator of the functionality, which was called Functionality Index. This study also permitted to separate the networks into 4 classes of functionality, according to the time wasting expectation to establish 2 control points to support cadastral surveys.

Nos últimos anos, tem sido evidente a importância dos sistemas de cadastro territorial. Isso tem ocorrido, principalmente, devido à sua crescente função no desenvolvimento econômico, e no gerenciamento ambiental. Dentre os elementos fundamentais de um sistema cadastral, destaca-se o custo do cadastramento, o qual deve ser compatível com a utilidade de cada imóvel cadastrado. Nesse contexto, e considerando as exigências da Lei 10.267, este trabalho demonstra que certas características das redes geodésicas de apoio ao cadastro influenciam determinantemente nos custos do cadastramento dos imóveis rurais e, portanto, que tais características devem ser cuidadosamente consideradas quando da implantação e manutenção de sistemas cadastrais. É introduzido o conceito de operacionalidade, como mais um parâmetro a ser maximizado na elaboração de um novo projeto, ou na análise de uma rede já existente. A determinação dos parâmetros de operacionalidade fundamentou-se na identificação e atribuição de \"pesos\" às características dos vértices, através de uma pesquisa entre profissionais e estudiosos da área, e mediante o envio de dezenas de questionários. Dessa pesquisa foi possível inferir que os atributos relacionados ao acesso, monumentação do vértice, uso de receptores GPS e uso por estação total, têm o mesmo peso, sendo que uma importância menor foi atribuída às facilidades logísticas locais. Ficou demonstrado também que, além dos atributos dos vértices, a densidade da rede também influencia a operacionalidade. Utilizando-se de simulações, e tendo como referência uma região piloto, selecionada dentro do Estado de São Paulo, quantificou-se a influência da densidade que, agregada às características dos vértices, permitiu desenvolver um método para obtenção de um indicador numérico da operacionalidade, o qual denominou-se Índice de Operacionalidade. O trabalho permitiu, ainda, separar as redes em 4 classes de operacionalidade, de acordo com a expectativa de dispêndio de tempo para a implantação de uma base topográfica de apoio aos levantamentos cadastrais de imóveis rurais. / In the last few years, it has been noticeable the importance of territorial cadastre systems. This is happening mainly because of its increasing function in economic development, and in environmental managing. Among the fundamental elements of a cadastre system, the cadastral cost, which must be compatible with the utility of each cadastred land parcel, is emphasized. In this context, and considering the 10.267 Law demands, the present study shows that certain characteristics of reference geodetic networks have influence in a determinant way in the costs of rural cadastre, and for that, these characteristics must be carefully considered when implementing and maintaining cadastral systems. The functionality concept was introduced as one more parameter to be maximized when elaborating a new project, or in the analysis of an already existing network. The determination of functionality elements was based in the identification and attribution of \"weighs\" to the network stations characteristics through an investigation by mailing questionnaires to surveyors and researchers. From this investigation, it was possible to infer that the attributes related to the network stations access, monuments, functionality for GPS and total station surveys have the same weigh, however local logistics facilities have been attributed with less importance. It was also demonstrated that, besides the network stations attributes, the network density also influences the functionality. Using simulations, and having as reference a pilot area, selected within São Paulo state, it was quantified the density influence that, together with the network stations characteristics, allowed the development of a method to obtain a numerical indicator of the functionality, which was called Functionality Index. This study also permitted to separate the networks into 4 classes of functionality, according to the time wasting expectation to establish 2 control points to support cadastral surveys.