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

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.

Scheduling problem and shift design problems are well known NP-hard problems within the optimization area. Often time, the two problems are studied individually. In this thesis however, we are looking at the combination of both problems. More specifically, the aim of this thesis is to suggest an optimal scheduling policy given that there are no predefined shifts to begin with. The duration of a shift, along with the start and end time may vary. Thus we have proposed to split the problem into two sub-problems: weekly scheduling problem and daily scheduling problem. As there are no exact solution methods that are feasible, two meta-heuristics method has been employed to solve the sub-problems: Simulated Annealing (SA) and Genetic Algorithm (GA). We have provided proofs of concepts for both methods as well as explored the scalability. This is especially important as the number of employee is expected to grow significantly throughout the year. The results obtained has shown to be promising and can be built upon for further capabilities. / Schemaläggning och skiftdesignsproblem är välkända och välstuderade NP-svåra beslutsproblem inom optimeringsområdet. Oftast så studeras dessa problem enskilt, men i detta arbete så studeras en kombination av båda problemen. Mer specifikt är målet med detta arbete att föreslå ett förnuftigt handlingsätt till att skapa ett veckoschema där skift inte är predefinierade för alla veckor. Starttiden, sluttiden och varaktigheten av ett skift kan förändras från vecka till vecka. Därför har problemet delats upp till två delar: Veckoschemaläggnings- och dagsschemaläggningsproblem. Trots uppdelningen så är båda delproblem för komplexa för att lösas exakt. Därför har två metaheuristiska metoder använts som lösningsmetoder: Simulerad Glödgning och Genetisk Algoritm. I detta arbete bevisas båda lösningsmetoderna till att vara bra nog, och dessutom studeras även skalbarheten av modellen. Detta senare är särskilt viktigt eftersom antal anställda som ska schemaläggas förväntas att öka genomåren. De erhållna resultaten har visat sig vara lovande och bevisligen så kan modellen expanderas med er villkor

SOCIAL INNOVATION AND DESIGN CHALLENGES

Studenten und Konstrukteure mit verschiedener konstruktionsmethodischer Ausbildung wurden bezüglich ihres Vorgehens beim Konstruieren und ihrer Konstruktionsleistungen untersucht. Dabei zeigte sich, dass die Wirkung der Ausbildung für drei Teilleistungen (Konzepte erstellen, Konzepte bewerten, Entwürfe erstellen) verschieden ist. Für die konstruktionsmethodischen Empfehlungen für die frühen Phasen wird eine neue Konzeption vorgeschlagen. Der Einfluss kognitiver Variablen (Arbeitsgedächtnis, heuristische Kompetenz, Interferenz) wurde untersucht.

No description available.

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides. / Many problems in transportation and logistics can be formulated as network design models. They usually require to transport commodities, passengers or data in a network to satisfy a certain demand while minimizing the costs. In this work, we focus on the multicommodity capacited fixed-charge network design problem which consists of opening a subset of the links in the network to satisfy the demand. Each link has a capacity and a fixed cost that is paid if it is opened. The objective is to minimize the fixed costs of the opened links and the transportation costs of the commodities. We present an exact method to solve this problem based on mixed integer programming techniques. Our method is a specialization of the branch-and-bound algorithm, called branch-and-price-and-cut, in which we use column generation and cutting-plane method to solve large-scale instances. We compare our method with CPLEX, currently one of the best solver. Numerical results show that our method is competitive on medium-scale instances and better on large-scale instances.

Le problème de conception de réseaux est un problème qui a été beaucoup étudié dans le domaine de la recherche opérationnelle pour ses caractéristiques, et ses applications dans des nombreux domaines tels que le transport, les communications, et la logistique. Nous nous intéressons en particulier dans ce mémoire à résoudre le problème de conception de réseaux avec coûts fixes et sans capacité, en satisfaisant les demandes de tous les produits tout en minimisant la somme des coûts de transport de ces produits et des coûts fixes de conception du réseau. Ce problème se modélise généralement sous la forme d’un programme linéaire en nombres entiers incluant des variables continues. Pour le résoudre, nous avons appliqué la méthode exacte de Branch-and-Bound basée sur une relaxation linéaire du problème avec un critère d’arrêt, tout en exploitant les méthodes de génération de colonnes et de génération de coupes. Nous avons testé la méthode de Branch-and-Price-and-Cut sur 156 instances divisées en cinq groupes de différentes tailles, et nous l’avons comparée à Cplex, l’un des meilleurs solveurs d’optimisation mathématique, ainsi qu’à la méthode de Branch-and- Cut. Notre méthode est compétitive et plus performante sur les instances de grande taille ayant un grand nombre de produits. / The network design problem has been studied extensively in the field of operational research given its characteristics and applications in many areas such as transportation, communications, and logistics. We are particularly interested in solving the multicommodity uncapacitated fixed-charge network design problem, with the aim of meeting the demands of all the products while minimizing the total cost of transporting commodities and designing the network. This problem is typically modeled as a linear integer program including continuous variables. To solve it, we applied the exact method of Branch-and-bound based on linear relaxation with a stopping criterion, while exploiting the column generation and cutting-plane methods. We tested our Branch-and-Price-and-Cut algorithm on 156 instances divided into five groups of different sizes, and we compared it with Cplex, one of the best mathematical optimization solvers. We compare it also with the Branch-and-Cut method. Numerical results show that our method is competitive and perform better especially on large-scale instances with many commodities.

Submitted by Maicon Juliano Schmidt (maicons) on 2015-06-11T19:24:34Z No. of bitstreams: 1 Débora de Oliveira Lemos Rocha de Souza.pdf: 11262812 bytes, checksum: 1afc26309c47e8dc71f1c5e88aae7409 (MD5) / Made available in DSpace on 2015-06-11T19:24:34Z (GMT). No. of bitstreams: 1 Débora de Oliveira Lemos Rocha de Souza.pdf: 11262812 bytes, checksum: 1afc26309c47e8dc71f1c5e88aae7409 (MD5) Previous issue date: 2015-03-27 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / FAPERGS - Fundação de Amparo à Pesquisa do Estado do Rio Grande do Sul / Algumas ações do processo projetual se restringem aos pensamentos dos designers, gerando uma dificuldade para compreender o processo e torná-lo explícito. As pesquisas nessa área tentam transpor essas limitações, buscando perceber o modo como os designers resolvem os problemas para aprimorar a sua atuação. Esses problemas são caracterizados como mal-estruturados e podem ser vistos de diferentes perspectivas, gerando respostas distintas. O conceito de coevolução percebe a resolução de problemas de forma evolutiva: à medida que compreende-se um pouco mais o problema, as respostas tornam-se mais aprimoradas. Esta dissertação tem como objetivo geral compreender a coevolução do problema de design. Para isso, realizou-se uma pesquisa exploratória em um workshop em design, coletando as informações por meio de grupos focais e do registro, em vídeo, do processo realizado pelos participantes. A técnica utilizada para analisar as informações coletadas nos grupos focais e nos vídeos foi a análise de conteúdo, com algumas adaptações necessárias à pesquisa realizada. Na análise, percebeu-se que a coevolução é influenciada: 1) pela formulação inicial do problema que funciona como uma força motora, impulsionando o processo de resolução do problema; 2) pela forma como as equipes se articulam, levando-se em conta o modo como os integrantes desempenham diferentes papeis e estabelecem um ritmo de resolução do problema de acordo com experiências anteriores que trazem para o projeto; 3) pelos questionamentos em relação ao problema ou à solução, caracterizando-se como uma das estratégias utilizadas pelos designers para avançar no espaço-problema ou no espaço-solução. Concluiu-se, assim, que não só o espaço-problema e o espaço-solução se modificam no percurso do projeto de forma a provocar uma evolução mútua, mas os diversos fatores que envolvem o processo projetual também influenciam na coevolução do problema de design. / Some actions in the design process are restricted to the designers’ thoughts, what may cause some difficulties in understanding the process itself and making it explicit. Studies in this area attempt to overcome these limitations by looking into the way designers solve problems to improve their performance. These problems are usually characterized as ill-structured and can be seen from different perspectives, leading to distinct answers. The concept of co-evolution regards problem resolution in an evolutive manner: as the problem is better understood, the answers become more refined. The overall objective of this work is to understand the co-evolution of the design problem. In order to do this, an exploratory research was conducted within a design workshop, where data was collected by means of both focal groups and videos recording the participants’ process. The technique used to analyse all this data was Content Analysis, with some necessary adaptations to the context of the present research. In the analysis, it was possible to observe that co-evolution is influenced by: 1) the initial formulation of the problem that works as a driving force, boosting the problem resolution process; 2) the way the groups manage themselves, taking into consideration the manner in which different members play distinct roles and establish a problem resolution pace based on previous experiences they bring to the project; and 3) inquiries related to the problem or the solution, which can be regarded as one of the strategies used by designers to move forward into the problem space or the solution space. In conclusion, all these observations lead to the understanding that not only the problem space and the solution space modify themselves in the course of the project, triggering mutual evolution, but the diverse aspects involved in the design context also have some influence on the co-evolution of the design problem.