This thesis deals with the applications of graph theory towards the electrical distribution networks that transmit electricity from the generators that produce it and the consumers that use it. Specifically, we establish the substation and bus network as graph theoretical models for this major piece of electrical infrastructure. We also generate substation and bus networks for a wide range of existing data from both synthetic and real grids and show several properties of these graphs, such as density, degeneracy, and planarity. We also motivate future research into the definition of a graph family containing bus and substation networks and the classification of that family as having polynomial expansion.

Esta dissertação trata do problema do projeto de redes de transporte público por ônibus, que consiste em estabelecer as linhas de ônibus a serem operadas e seus respectivos trajetos e frequências. Busca-se determinar uma rede de tal forma a minimizar custos de operadores e usuários, constituindo um problema multiobjetivo. O custo dos operadores é representado tanto pela frota como pela quilometragem total necessária para atender às frequências exigidas; já o custo dos usuários é representado pela soma dos tempos de espera, tempos de viagem dentro do veículo e eventuais penalidades de transferência. Dado tratar-se de um problema multiobjetivo, de natureza combinatória e complexo, é proposto um método de solução baseado na metaheurística Algoritmo Genético. O mesmo baseia-se na construção inicial de um banco de rotas viáveis, e cada solução proposta é formada selecionando-se um subconjunto de rotas deste banco para formar a rede. São aplicadas estratégias de busca por soluções viáveis nos operadores do Algoritmo Genético, devido à grande proporção de indivíduos inviáveis. O modelo é avaliado através de uma instância de teste da literatura e os resultados são comparados com os já obtidos em trabalhos anteriores. A melhor solução encontrada através do método descrito deste trabalho é superior às já reportadas na literatura. Uma análise de sensibilidade foi realizada para avaliar a influência de parâmetros de entrada do modelo na qualidade das soluções. Um Sistema de Visualização foi desenvolvido para representar graficamente as linhas de ônibus e demais variáveis das soluções. Sugere-se, ao final do trabalho, um conjunto de pesquisas futuras associadas à melhoria do modelo. / This dissertation addresses the public transport network design problem, which comprises determining the bus routes, their associated itineraries and frequencies. The network is designed as to minimize operators and users costs, creating a multiobjective problem. Operators costs are represented by the total fleet and mileage necessary to address required frequencies while user costs are represented by the sum of waiting times, in-vehicle travel times and possible transfer penalties. Given the complexity of this combinatorial and multiobjective problem, a solution method, based on the genetic algorithm metaheuristic, is proposed. Initially a database of feasible routes is built, and each proposed solution is formed by selecting a subset of routes from the database to form the network. Feasibility search strategies are applied inside genetic algorithms operators to make up for the large number of unfeasible individuals. The model is evaluated with a small network and the results are compared with those obtained in previous studies. The best solution attained with the present method is superior to previously published results. A sensitivity analysis was conducted to evaluate the influence of different model input parameters on solution quality. A Visualization System was developed to graphically represent the solutions bus lines and other variables. A set of future research ideas, related to the model improvement, are presented at the end of this study.

La tesi descriu dos algorismes relatius al transport públic que actuen en sèrie. El primer genera una xarxa d'autobusos urbans entesa com a un conjunt de línies o be en modifica una de ja existent de forma que minimitzi el temps total de viatge en una ciutat. Es tracta d'un algorisme iteratiu que tracta les línies d'una en una i aquestes al seu torn de nus en nus. El segon algorisme dit d'assignació un cop coneguda la xarxa i la flota d'autobusos minimitza el temps total de viatge per mitja de l'assignació d'autobusos a les línies.

Esta dissertação trata do problema do projeto de redes de transporte público por ônibus, que consiste em estabelecer as linhas de ônibus a serem operadas e seus respectivos trajetos e frequências. Busca-se determinar uma rede de tal forma a minimizar custos de operadores e usuários, constituindo um problema multiobjetivo. O custo dos operadores é representado tanto pela frota como pela quilometragem total necessária para atender às frequências exigidas; já o custo dos usuários é representado pela soma dos tempos de espera, tempos de viagem dentro do veículo e eventuais penalidades de transferência. Dado tratar-se de um problema multiobjetivo, de natureza combinatória e complexo, é proposto um método de solução baseado na metaheurística Algoritmo Genético. O mesmo baseia-se na construção inicial de um banco de rotas viáveis, e cada solução proposta é formada selecionando-se um subconjunto de rotas deste banco para formar a rede. São aplicadas estratégias de busca por soluções viáveis nos operadores do Algoritmo Genético, devido à grande proporção de indivíduos inviáveis. O modelo é avaliado através de uma instância de teste da literatura e os resultados são comparados com os já obtidos em trabalhos anteriores. A melhor solução encontrada através do método descrito deste trabalho é superior às já reportadas na literatura. Uma análise de sensibilidade foi realizada para avaliar a influência de parâmetros de entrada do modelo na qualidade das soluções. Um Sistema de Visualização foi desenvolvido para representar graficamente as linhas de ônibus e demais variáveis das soluções. Sugere-se, ao final do trabalho, um conjunto de pesquisas futuras associadas à melhoria do modelo. / This dissertation addresses the public transport network design problem, which comprises determining the bus routes, their associated itineraries and frequencies. The network is designed as to minimize operators and users costs, creating a multiobjective problem. Operators costs are represented by the total fleet and mileage necessary to address required frequencies while user costs are represented by the sum of waiting times, in-vehicle travel times and possible transfer penalties. Given the complexity of this combinatorial and multiobjective problem, a solution method, based on the genetic algorithm metaheuristic, is proposed. Initially a database of feasible routes is built, and each proposed solution is formed by selecting a subset of routes from the database to form the network. Feasibility search strategies are applied inside genetic algorithms operators to make up for the large number of unfeasible individuals. The model is evaluated with a small network and the results are compared with those obtained in previous studies. The best solution attained with the present method is superior to previously published results. A sensitivity analysis was conducted to evaluate the influence of different model input parameters on solution quality. A Visualization System was developed to graphically represent the solutions bus lines and other variables. A set of future research ideas, related to the model improvement, are presented at the end of this study.

No description available.

A utilização de eletrônica embarcada na agricultura tem crescido rapidamente, tornando necessária a utilização de diversos módulos a bordo da máquina (trator e implemento). Considerando-se os impactos relacionados a esta tendência, alternativas tecnológicas devem ser geradas e devidamente exploradas, especialmente sobre os sistemas de controle e o cabeamento requeridos. As arquiteturas eletro-eletrônicas devem garantir o mínimo de custo de implementação e tempo de manutenção. Os sistemas de controle devem operar maximizando a disponibilidade das informações, o que implica a necessidade de troca de dados entre estes diversos sistemas de controle e, portanto, a existência de um protocolo de comunicação serial internacionalmente padronizado. Neste contexto, este trabalho aborda os diversos protocolos de comunicação serial - como o RS232, o RS485 e o CAN (Controller Area Network) - e as suas normas específicas, voltadas às aplicações agrícolas, como a ISO11783 e a DIN 9684, comparando-as. Dessa análise resulta a indicação da ISO11783, norma baseada no protocolo CAN, como a mais interessante para as aplicações agrícolas. Essa norma é estudada em detalhes, o que permite a criação de um roteiro de estudo e implementação do referido protocolo. Finalmente, é desenvolvida uma aplicação deste protocolo, considerando-se uma rede de comunicação de dados de um Monitor de Semeadora, a fim de demonstrar sua aplicação prática. / The use of on-board electronics in agriculture has grown quickly, requiring many electronic modules on-board machines (tractor and implement). Considering the trend related impacts, alternative technologies should be developed and used properly, especially on control systems and on the required wiring harness. Electro-electronic architectures should provide minimum implementation cost and maintenance related time. Control systems should operate maximizing the availability of information that implies on the necessity of data exchange among these variety of control systems and also, on the existence of an international standardized serial communication protocol. Considering that, this documentation covers many serial communication protocols - as RS232, RS485 and CAN (Controller Area Network) - and the agricultural applications related standards as ISO11783 and DIN 9684, comparing them. This analysis results in the indication of ISO11783, a CAN Bus based standard, as the most interesting to agricultural applications. This standard is analyzed in details, making possible the development of a protocol related study and implementation guideline. Finally, a protocol related application is developed for a Planter Monitor implement bus network, looking forward to demonstrating an ISO11783 real implementation.

A utilização de eletrônica embarcada na agricultura tem crescido rapidamente, tornando necessária a utilização de diversos módulos a bordo da máquina (trator e implemento). Considerando-se os impactos relacionados a esta tendência, alternativas tecnológicas devem ser geradas e devidamente exploradas, especialmente sobre os sistemas de controle e o cabeamento requeridos. As arquiteturas eletro-eletrônicas devem garantir o mínimo de custo de implementação e tempo de manutenção. Os sistemas de controle devem operar maximizando a disponibilidade das informações, o que implica a necessidade de troca de dados entre estes diversos sistemas de controle e, portanto, a existência de um protocolo de comunicação serial internacionalmente padronizado. Neste contexto, este trabalho aborda os diversos protocolos de comunicação serial - como o RS232, o RS485 e o CAN (Controller Area Network) - e as suas normas específicas, voltadas às aplicações agrícolas, como a ISO11783 e a DIN 9684, comparando-as. Dessa análise resulta a indicação da ISO11783, norma baseada no protocolo CAN, como a mais interessante para as aplicações agrícolas. Essa norma é estudada em detalhes, o que permite a criação de um roteiro de estudo e implementação do referido protocolo. Finalmente, é desenvolvida uma aplicação deste protocolo, considerando-se uma rede de comunicação de dados de um Monitor de Semeadora, a fim de demonstrar sua aplicação prática. / The use of on-board electronics in agriculture has grown quickly, requiring many electronic modules on-board machines (tractor and implement). Considering the trend related impacts, alternative technologies should be developed and used properly, especially on control systems and on the required wiring harness. Electro-electronic architectures should provide minimum implementation cost and maintenance related time. Control systems should operate maximizing the availability of information that implies on the necessity of data exchange among these variety of control systems and also, on the existence of an international standardized serial communication protocol. Considering that, this documentation covers many serial communication protocols - as RS232, RS485 and CAN (Controller Area Network) - and the agricultural applications related standards as ISO11783 and DIN 9684, comparing them. This analysis results in the indication of ISO11783, a CAN Bus based standard, as the most interesting to agricultural applications. This standard is analyzed in details, making possible the development of a protocol related study and implementation guideline. Finally, a protocol related application is developed for a Planter Monitor implement bus network, looking forward to demonstrating an ISO11783 real implementation.