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.

Diversos problemas do mundo real estão relacionados ao projeto de redes, tais como projeto de circuitos de energia elétrica, roteamento de veículos, planejamento de redes de telecomunicações e reconstrução filogenética. Em geral, esses problemas podem ser modelados por meio de grafos, que manipulam milhares ou milhões de nós (correspondendo às variáveis de entrada), dificultando a obtenção de soluções em tempo real. O Projeto de uma Rede é um problema combinatório, em que se busca encontrar a rede mais adequada segundo um critério como, por exemplo, menor custo, menor caminho e tempo de percurso. A solução desses problemas é, em geral, computacionalmente complexa. Nesse sentido, metaheurísticas como Algoritmos Evolutivos têm sido amplamente investigadas. Diversas pesquisas mostram que o desempenho de Algoritmos Evolutivos para Problemas de Projetos de Redes pode ser aumentado significativamente por meio de representações mais apropriadas. Este trabalho investiga a paralelização da Representação Nó-Profundidade (RNP) em hardware, com o objetivo de encontrar melhores soluções para Problemas de Projetos de Redes. Para implementar a arquitetura de hardware, denominada de HP-RNP (Hardware Parallelized RNP), foi utilizada a tecnologia de FPGA para explorar o alto grau de paralelismo que essa plataforma pode proporcionar. Os resultados experimentais mostraram que o HP-RNP é capaz de gerar e avaliar novas redes em tempo médio limitado por uma constante (O(1)) / Many problems related to network design can be found in real world applications, such as design of electric circuits, vehicle routing, telecommunication network planning and phylogeny reconstruction. In general, these problems can be modelled using graphs that handle thousands or millions of nodes (input variables), making it hard to obtain solutions in real-time. The Network Design is the combinatorial problem of finding the most suitable network subject to a evaluation criterion as, for example, lower cost, minimal path and time to traverse the network. The solution of those problems is in general computationally complex. Metaheuristics as Evolutionary Algorithms have been widely investigated for such problems. Several researches have shown that the performance of Evolutionary Algorithms for the Network Design Problems can be significantly increased through more appropriated dynamic data structures (encodings). This work investigates the parallelization of Node-Depth Encoding (NDE) in hardware in order to find better solutions for Network Design Problems. To implement the proposed hardware architecture, called HP-NDE (Hardware Parallellized NDE), the FPGA technology was used to explore the high degree of parallelism that such platform can provide. The experimental results have shown that the HP-NDE can generate and evaluate new networks in average time constrained by a constant (O(1))

[pt] Seja G= (V, E) um grafo não-orientado com custos não- negativos em suas arestas e D um conjunto de pares origem - destino. Um 2-caminho entre nós (s,t)é um caminho de s a t formado por , no máximo, 2 arestas. O problema de síntese de redes com 2-caminhos (2PNDP) consiste em encontrar um subconjunto de arestas com custo mínimo que contenha um 2- caminho entre as extremidades dea cada para origem- destino pertencente a D. Apicações deste problema encontram-se no projeto de redes de comunicação, onde caminhos com poucas arestas são desejáveis para garantir alta confiabilidade e pequenos atrasos. A metaheurística GRASP é um processo multipartida para resolver problemas combinatórios, cujas iterações consistem de duas fases, uma fase de construção e outra de busca local. O algoritmo retorna a melhor solução encontrada depois de um número determinado de iterações.Aplica-se a técnica de reconexão por caminhos ao final de cada iteração GRASP para melhorar a qualidade das soluções. Implementações paralelas de metaheurística são muito robustas. A maior parte das implementações paralelas da metaheurística GRASP segue uma estratégia do tipo independente , baseada na distribuição balanceada das iterações pelos processadores. No caso de estratégias colaboradtivas, os processadores trocam e compartilham informações coletadas ao longo da trajetória que cada um deles investiga. Neta tese são desenvolvidas heurísticas seqüenciais e paralelas para 2PNDP. São analisadas variantes e combinações de GRASP e reconexão por caminhos , comparando-se os resultados obtidos pelos algoritmos descritos na literatura. Heurísticas GRASP paralelas com reconexão por caminhos são avaliadas e comparadas para verificar qual o papel que a colaboração entre os processadores desempenha na qualidade das soluções e nos tempos de processamento. Procura-se também estudar a melhor maneira de desenvolver implementações paralelas , para se utilizar da melhor forma possível os recursos computacionais e reduzir conflitos de memória e comunicação. / [en] Let G = ( V, E) be a connected undirected graph , where V is the set of nodes and E denotes the set of edges. A 2- path between nodes (s,t)is a sequence of a most two edges connecting them. Given a non-negative weight function associated with edges of G and a set D of origin- destination pairs of nodes, the 2-path network design problem (2PNDP) consists in finding a minimum weighted subset of edges containing a 2-path between the extremities of every origin-destination pair in D. Applications can be found in the design of communication networks , in which paths with few edges are sought to enforce high reliability and small delays. The GRASP metaheuristic is a multistart process , in which each iteration consists of two phases : construction and local search. The best solution found after a fixed number of iterations is returned. Path- relinking is applied as an attempt to improve the solutions found at the of each GRASP iteration. Parallel implementations of metaheuistics ara very robust. Typical parallelizations of GRASP correspond to multiple-walk independent-thread strategies, based on the balanced distribuiton of the iterations over the processors. In the case of multiple-walk cooperative-thread strategies, the processors exchange and share information collected along the trajectories that they investigate. In this thesis, sequential and parallel heuristics are developed for 2PNDP. Variants and combinations of GRASP with path-relinking are analysed by comparing the results of the proposed algorithms with those obtained by others algoritms described in the literature. Parallel GRASP with pathrelinking heuristcs are compared to investigate the influence of the cooperation among processors in terms of solution quality and processing time. We also explore different strategies to optimize the parallel implementations, to make better use of the computational resources and to reduce communication and memory conflicts.

Submitted by Maicon Juliano Schmidt (maicons) on 2015-03-30T14:40:12Z No. of bitstreams: 1 Fernando Stefano Kozenieski Alves de Oliveira.pdf: 5088719 bytes, checksum: 6c13bcd0bfc3e849a253c6a3d48062df (MD5) / Made available in DSpace on 2015-03-30T14:40:12Z (GMT). No. of bitstreams: 1 Fernando Stefano Kozenieski Alves de Oliveira.pdf: 5088719 bytes, checksum: 6c13bcd0bfc3e849a253c6a3d48062df (MD5) Previous issue date: 2011-07-31 / Nenhuma / O design pode ser caracterizado como uma atividade que trabalha com processos que visam à construção de projetos. Ao longo dos tempos, os designers vêm utilizando ferramentas a fim de auxiliar na resolução desses projetos, fornecendo respostas para problemas de design. Dentro de uma perspectiva estratégica, esses processos muitas vezes são representados em uma etapa denominada Metaprojeto, que pretende refletir sobre o problema de design. Nesse contexto, o presente trabalho apresenta a investigação realizada sobre dois momentos da etapa metaprojetual, dentro de um Workshop de design: o briefing e o contrabriefing. Esse trabalho partiu dos seguintes questionamentos: De que modo o briefing é construído em um processo de projeto de design? Como se dá esse processo, e quem são seus atores? Como representar um briefing? Assim, a pesquisa tem como objetivo compreender o processo de construção e apresentação do briefing, e o contrabriefing como o espaço para um eventual reposicionamento do problema, dentro do Workshop de design. Para atender ao objetivo adotou-se o estudo de caso como metodologia de pesquisa. O estudo constitui na articulação entre o referencial teórico e o trabalho de campo. O referencial teórico abordou como itens: Um novo olhar sobre o design (Design Estratégico); Problema de design; Informação; Briefing. Os estudos de caso foram construídos por meio da observação de quatro Workshops realizados na Escola de Design Unisinos e seus documentos, além de entrevistas com os coordenadores dos mesmos. Os resultados obtidos permitem avaliar a importância que a construção e apresentação do briefing têm sobre o processo de projeto e, principalmente, sobre o resultado projetual. É possível compreender, da mesma maneira, em que tempo e de que modo o contrabriefing pode ser apresentado como uma forma de reposicionar o problema de design. Além disso, evidencia-se a articulação entre teorias comunicacionais e o Design Estratégico a fim de abrir um espaço para reflexões sobre o problema de design. Estabelece-se dessa forma, a importância do Metaprojeto como uma etapa construtiva e reflexiva no processo de projeto de design. / We can characterize design as an activity that works with processes aimed at constructing projects. Over time, designers have used tools that help them accomplish such projects, while providing answers to design problems. From a strategic outlook, such processes are oftentimes represented in a stage called Metaproject, meant to ponder about the given design problem. In this context, this paper presents the investigation carried out with respect to two points during the metaproject stage in a design Workshop: the briefing and the counter-briefing. This paper started from the following questions: how is the briefing constructed in a design project process? How does that process take place, and who are its players? How do we represent a briefing? Hence, the purpose of this study is to understand the process of putting together and presenting the briefing and the counter-briefing as the space where the problem may be occasionally repositioned in the design Workshop. To meet our goal, case studies were adopted as research method. The study makes use of both the theoretical reference and field work. The items addressed by the theoretical reference are: A new outlook on design (Strategic Design); Design problem; Information; Briefing. Case studies were put together by means of attending four Workshops held at the Unisinos Design School and going over their papers, in addition to interviews with the Workshop coordinators. The results obtained allow us to assess how important putting together the briefing and presenting it are for the project process and, particularly, for the project results. Likewise, we are able to understand when and how the counter-briefing can be presented as a way to reposition the design problem. Furthermore, we show the interrelation between communication theories and Strategic Design so that we can make room for discussing the design problem. The importance of the Meta-project is thus established as a constructive, pondering stage in the design project process.

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2017-06-26T14:17:21Z No. of bitstreams: 1 Melissa Merino Lesnovski_.pdf: 6981013 bytes, checksum: 5a4fdef4e856d56ef0f8a2d47fa6bf60 (MD5) / Made available in DSpace on 2017-06-26T14:17:21Z (GMT). No. of bitstreams: 1 Melissa Merino Lesnovski_.pdf: 6981013 bytes, checksum: 5a4fdef4e856d56ef0f8a2d47fa6bf60 (MD5) Previous issue date: 2017-03-16 / Nenhuma / Esta investigação abordou o papel da proposta comercial de serviços de design dentro do contexto de subdeterminação do problema de design, analisando-a como um possível boundary object que media e articula os interesses e relações de atores dentro e fora da organização de design, tanto na etapa comercial quanto ao longo do projeto. O percurso metodológico compreendeu a elaboração de um modelo analítico da jornada da proposta comercial ao longo do projeto, a partir de entrevistas com especialistas, seguido por três estudos de casos onde tal modelo foi aplicado criticamente na análise dos processos, traduções e artefatos de cada situação. Com base nos resultados obtidos, discutiu-se os boundary objects como promotores de abertura e fechamento de perspectivas, as relações da proposta comercial com a cartografia e dispositivos de agência, a controvérsia e a pontualização como o inesperado em relatos e, por fim, o problema de design em um crescente de complexidade. Tais reflexões deram margem para enquadrar a venda de serviços de design por uma perspectiva de acoplamento à complexidade residente na organização, realizada através de um coletivo de boundary objects influenciado pela visão de um agente-cartógrafo comercial. / The present investigation approaches the role of the design services business proposal inside contexts where the design problem is ill-structured, as a possible boundary object that mediates and articulates interests and relationships among actors both inside and outside of the design organization. Methodological procedures involved the elaboration of an analytical model of the business proposal journey throughout the project, based on interviews with specialists, followed by three case studies in which said model was critically applied to analyse processes, translations and artifacts belonging to each situation. Based on the findings of each case study, a discussion has evolved around boundary objects as promoters of opening and closing of perspectives, relationships mediated by the business proposal, cartography of controversies and agency devices, controversy and punctualization as the unexpected in accounts and the design problem in increased complexity settings. These discussions lead to the framing of the design services selling process as a way of coupling with an organization’s resident complexity, enacted through a collective of boundary objects influenced by the vision of a commercial cartographer agent.

Vor dem Hintergrund empirischer Befunde zur Nutzung von CAD-Systemen beim konstruktiven Entwerfen in der Ausbildung sowie der Berufspraxis wird in der vorliegenden Arbeit über eine Befragungsstudie sowie eine laborexperimentelle Studie zur Bewertung des Unterstützungspotentials verschiedenartiger Arbeitsmittel in den frühen Phasen des Entwerfens von technischen Gebilden berichtet. Zu den beim Entwerfen eingesetzten Arbeitsmitteln zählen neben einfachen, aufwandsarmen Werkzeugen wie Papier und Bleistift auch computerisierte Automaten wie z. B. CAD-Systeme. CAD-Systeme sind durch die bereitgestellten Funktionalitäten heutzutage ein wesentliches Arbeitsmittel für den Konstrukteur; die für die außerordentlich komplexen, kostenbestimmenden frühen Entwurfsphasen wichtigen Funktionen werden aber offenbar nur in unzureichendem Maße oder überhaupt nicht zur Verfügung gestellt. Dadurch notwendige Wechsel zwischen analogen und digitalen Arbeitsmitteln müssen bislang manuell durchgeführt werden und haben neben zeitlichen Einbußen in der Regel Fehler und Informationsverluste bei der Übertragung zur Folge. Mit dem LCD-Monitor mit integriertem Graphiktablett WACOM Cintiq 15X, dessen Bedienung sich an den Eigenschaften herkömmlicher Handskizzen orientiert, wird eine durchgängige Nutzung von CAD-Systemen angestrebt. Zunächst wurden diese drei Arbeitsmittel hinsichtlich Ihrer Anforderungen an den Nutzer bei einem Einsatz in den frühen Entwurfsphasen aus tätigkeitspsychologischer Sicht analysiert. In der experimentellen Hauptuntersuchung bearbeiteten drei Versuchsgruppen einer Stichprobe von 66 Studierenden einer ingenieurtechnischen Fakultät dasselbe wissensreiche, praxisnahe Entwurfsproblem unter den experimentellen Bedingungen der Entwurfsentwicklung durch Freihandskizzieren mit Papier und Bleistift, mit digitalem Graphiktablett oder mit Hilfe des Rechnerprogramms AutoCAD. Es erfolgte eine differenzierte Betrachtung des Einflusses dieser verschiedenartigen Arbeitsmittel auf unterschiedliche Variablen der Bereiche ?Ergebnisse?, ?Erleben? und ?Prozess?. Im Ergebnis der Analysen konnte weitestgehend hypothesenkonform gezeigt werden, dass Freihandskizzieren - unabhängig vom Arbeitsmittel - dem Entwerfen mittels CAD in allen betrachteten effektivitäts- und effizienzbestimmenden Kriterien überlegen war. Prozessorientierte Analysen des äußeren Handlungsablaufes sowie handlungsbegleitender mentaler Prozesse gaben erste Hinweise auf mögliche Ursachen dieser Befunde aus handlungspsychologischer Sicht. Dazu war eine Untersuchungsmethodik entwickelt worden, die es erlaubt, begründet auf den ?inneren Verlauf? des Entwerfens zu schließen. Die Ergebnisse konnten in einem weiteren Schritt an einer Problemstellung mit vergleichbarem Schwierigkeitsgrad weitgehend repliziert werden. Aus den Analysen und Resultaten wurden Schlussfolgerungen für die Konstruktionsausbildung und die Gestaltung digitaler Unterstützungssysteme abgeleitet. / Due to its economic importance, engineering design as a demanding and complex problem-solving activity has been the subject of interdisciplinary research of both psychologists and design scientists for several years. In particular, the early stages of problem clarification and conceptual design are of significant interest. The design process can be supported in several different ways, e. g. with simple low-expenditure sketches. Today, high-performance digital tools (e. g. CAD) have become indispensable in product development. But their characteristics hypothetically result in an additional workload of mental capacity and hinder the full and correct establishment of necessary mental problem representations. So design engineers often combine sketches and CAD. In order to avoid a loss of time and information when switching between the different media, the functions of sketches should be implemented into CAD. An approach to realise this is the interactive pen display WACOM Cintiq 15X, which claims to have the same characteristics as paper & pencil together with differing kinds of computer functionalities. Its effectiveness and efficiency has not yet been investigated. This study focuses on the comparison of the three media ?paper & pencil?, ?pen display? and ?AutoCAD? in the early stages of the design process. On the basis of the psychological demands on the user, support potential was analysed by recording variables concerning the results, the subjective experience and the process. The sample was composed of 66 students of the mechanical engineering graduate program at the Dresden University of Technology. Random sampling resulted in three subsamples of 22 subjects each. The research was carried out in a laboratory experimental study, where people work alone on a given design scenario. No significant differences could be found between the two groups designing by freehandsketching with paper & pencil and with pen display. This speaks well for comparable demands of these two media on the user. Subjects who designed with AutoCAD produced solutions with a significant lower quality and communication of the technical information content. They needed significantly more time to develop the solution. These results can be regarded as evidence of the hypothetically discussed demands on the user: current CAD-systems do not take cognitive abilities and limitations into consideration sufficiently as well as ways of intuitive and effort-saving externalisation. Results could be replicated extensively in a study with a design problem of equally difficult requirement structure. Finally, hints for education of engineering design students and essential requirements for digital support tools in the early stages of the design process were derived.

[pt] Atualmente mais da metade da população mundial mora em cidades. O deslocamento na região urbana, mediante a utilização de transporte público se dificulta devido ao planejamento deficiente das rotas e redes de transporte, longos tempos de viagem, aumento do custo das passagens, dos tempos de espera, etc. Como consequência, a busca de operações mais eficientes no sistema de transporte público urbano tem aumentado visando atender as necessidades de transporte de forma mais sustentável. Após a revisão da literatura relacionada ao problema de desenho de rede de transporte público urbano, foi escolhido o método proposto por Aquino, (1980), aplicável para redes de ônibus urbanos. Por médio da modernização do programa do método escolhido e as melhorias nele, o número de rotas que define a rede conectada diminuiu. O número de transbordos na rede foi minimizado até zera-lo com um menor conjunto de rotas. Análise de indicadores e de rentabilidade das rotas que minimizam o número de transbordo na rede, permite ao planejador ter uma visão geral do comportamento dessas rotas possibilitando tomar decisões mantendo os requerimentos iniciais e o objetivo de estudo. O programa do método desenvolvido, adaptado a uma linguagem moderna, Cmais mais, oferece, tanto ao meio acadêmico quanto ao profissional, uma ferramenta de fácil aplicação para dar solução ao Problema de Desenho de Rede de Transporte Público Urbano. Contribuindo potencialmente ao incremento da eficiência do processo de planejamento e, portanto, à redução de não conformidades do serviço de transporte resultando em economia dos custos para as empresas prestadoras deste serviço. / [en] Nowadays, more than half of the world s population lives in cities. Displacement in the urban area through the use of public transportation is hampered by poor planning of transport routes and networks, long travel times, increased ticket costs and waiting times, etc. As a consequence, the search for more efficient operations in the urban public transport system has increased in order to meet the transport needs in a more sustainable way. After the literature review related to the urban public transport network design problem, the method proposed by Aquino (1980), applicable to urban bus networks, was chosen. By means of the program s modernization of the chosen method and the improvements in it, the number of routes defining the connected network has decreased. The overflow number on the network has been minimized to zero with a smaller set of routes. Analysis of indicators and profitability of the routes that minimize the number of transfer in the network, allows the planner to have an overview of the behavior of these routes allowing to make decisions keeping the initial requirements and the objective of study. The developed method program, adapted to a modern language, C plus plus, offers both an academic and a professional environment an easy application tool to solve the Urban Public Transport Network Design Problem. Potentially contributing to the increase of the efficiency of the planning process and, therefore, to the reduction of nonconformities of the transport service, resulting in cost savings for the companies that provide this service.

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.

Diversos problemas do mundo real estão relacionados ao projeto de redes, tais como projeto de circuitos de energia elétrica, roteamento de veículos, planejamento de redes de telecomunicações e reconstrução filogenética. Em geral, esses problemas podem ser modelados por meio de grafos, que manipulam milhares ou milhões de nós (correspondendo às variáveis de entrada), dificultando a obtenção de soluções em tempo real. O Projeto de uma Rede é um problema combinatório, em que se busca encontrar a rede mais adequada segundo um critério como, por exemplo, menor custo, menor caminho e tempo de percurso. A solução desses problemas é, em geral, computacionalmente complexa. Nesse sentido, metaheurísticas como Algoritmos Evolutivos têm sido amplamente investigadas. Diversas pesquisas mostram que o desempenho de Algoritmos Evolutivos para Problemas de Projetos de Redes pode ser aumentado significativamente por meio de representações mais apropriadas. Este trabalho investiga a paralelização da Representação Nó-Profundidade (RNP) em hardware, com o objetivo de encontrar melhores soluções para Problemas de Projetos de Redes. Para implementar a arquitetura de hardware, denominada de HP-RNP (Hardware Parallelized RNP), foi utilizada a tecnologia de FPGA para explorar o alto grau de paralelismo que essa plataforma pode proporcionar. Os resultados experimentais mostraram que o HP-RNP é capaz de gerar e avaliar novas redes em tempo médio limitado por uma constante (O(1)) / Many problems related to network design can be found in real world applications, such as design of electric circuits, vehicle routing, telecommunication network planning and phylogeny reconstruction. In general, these problems can be modelled using graphs that handle thousands or millions of nodes (input variables), making it hard to obtain solutions in real-time. The Network Design is the combinatorial problem of finding the most suitable network subject to a evaluation criterion as, for example, lower cost, minimal path and time to traverse the network. The solution of those problems is in general computationally complex. Metaheuristics as Evolutionary Algorithms have been widely investigated for such problems. Several researches have shown that the performance of Evolutionary Algorithms for the Network Design Problems can be significantly increased through more appropriated dynamic data structures (encodings). This work investigates the parallelization of Node-Depth Encoding (NDE) in hardware in order to find better solutions for Network Design Problems. To implement the proposed hardware architecture, called HP-NDE (Hardware Parallellized NDE), the FPGA technology was used to explore the high degree of parallelism that such platform can provide. The experimental results have shown that the HP-NDE can generate and evaluate new networks in average time constrained by a constant (O(1))

The public transport system in South Africa is in a precarious state, capturing no more than 50% of the passenger market. The three public transport modes that are currently utilized—train, bus, and minibus-taxi—are competing for market share instead of complementing one another. Furthermore, most public transport networks have not been properly redesigned over the past three decades. Improvements were initiated reactively in the past: transit stops and routes were added or removed from the network when demand fluctuated. This reactive process has diminished the confidence of commuters in the public transport networks, forcing commuters to use private transport. A proactive redesign method is needed—one that includes all the modes of public transport, and anticipates an increase in demand and rapid development in geographic areas, while ensuring good accessibility to the network. Current network design models do not include multiple modes of public transport, and are based on the geographical layout of developed cities and their particularities, which makes them unsuitable for the South African environment with its unique land use disparities. This dissertation proposes a multimodal network design model that is capable of designing real world and large scale networks for the South African metropolitan areas. The City of Tshwane Metropolitan Municipality (CTMM) transport network area was used to develop and test the model, which consists of four components. The Geographic Information System (GIS) component has a central role in storing, manipulating, and exchanging the geographic data within the model. For the GIS the appropriate input data is identified, and a design for the geo-database is proposed. The Population Generation Algorithm (PGA) component translates the demographic data into point data representing the transit demand in the study area. The Bus Stop Placement Algorithm (BSPA) component is a metaheuristic that searches for near-optimal solutions for the placement of bus stops in the study area. A novel solution approach proposed in this dissertation uses geographic data of commuters to evaluate the bus stop placement in the study area. The Multimodal Network Design Algorithm (MNDA) component also employs a metaheuristic, enabling the design of near-optimal multimodal networks. The addition of multiple modes to the Transit Network Design Problem (TNDP) is also a novel and significant contribution. The two metaheuristic components are first tested on a test network, and subjected to a comprehensive sensitivity analysis. After identifying suitable parameter values and algorithm settings, the components are applied to the entire CTMM. / Dissertation (MSc)--University of Pretoria, 2009. / Industrial and Systems Engineering / unrestricted