Please read the abstract in the section 00front of this document Copyright 1996, University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. Please cite as follows: Bennett, CE 1999, The interrelated development of social values and the concept of the tragic hero with reference to the works of Arthur Miller, MA dissertation, University of Pretoria, Pretoria, viewed yymmdd < http://upetd.up.ac.za/thesis/available/etd-10102007-115952 / > / Dissertation (MA (English))--University of Pretoria, 2007. / English / unrestricted

Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes. This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements. In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed. We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems. Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.

In this thesis we focus on two NP-hard and intensively studied problems: The travelling salesman problem (TSP), which aims to find a minimum cost tour that visits every node exactly once in a complete weighted graph, and the 2-edge-connected spanning subgraph problem (2ECSS), which aims to find a minimum size 2-edge-connected spanning subgraph in a given graph. TSP and 2ECSS have many real world applications. However, both problems are NP-hard which means it is unlikely that polynomial time algorithms exist to solve them, so methods that return close to optimal solutions are sought. In this thesis we mainly focus on k-approximation algorithms for the two problems, which efficiently return a solution within k times of the optimal solution. For a special case of TSP called graph TSP, using ideas from Momke and Svensson, we present a 25/18-approximation algorithm for a special class of graphs using circulations and T-joins, which improves the previous known best bound of 7/5 for such graphs. Moreover, if the graph does not contain special nodes, our algorithm ensures the ratio of 4/3. For 2ECSS, given any k-edge-connected graph G=(V,E), |V|=n, |E|=m, we present an approximation algorithm that gives a 2-edge-connected spanning subgraph with the number of edges at most n+(m-n)/(k-1)-(k-2)/(k-1) with a novel use of circulations, which improves both the approximation ratio and the simplicity of the proof compared to a result by Huh in 2004.

Companies from multiple branches use as one way to offer their products and services network of sales representatives. This thesis study mainly designing process of such network and process of planning day to day routes of sales representatives with focus on minimizing cost caused by their work. For designing such network set covering problem model and matching problem model were used. For planning sales representatives routes travelling salesman problem, multiple salesperson travelling salesman problem, vehicle routing problem, nearest neighbor heuristic and authors own solution were used. Usage of multicriterial decision making is briefly mentioned as tool for managing such network on examples of equipment selection. As demonstration on real case, data from Tata Global Beverages (Jemča) company were used.

This thesis aims to find an optimal route taken by workers reading gas-meters. The text consists of three parts: the collection of necessary data, the selection and subsequent modification of the heuristic method and the calculation itself. Two techniques of data collection are applied: purchase from a specialised company and calculation based on geographical coordinates. These techniques are compared in the end. The method of the nearest neighbour is used for calculation, after being modified for this particular case. The calculation itself is done by the program named Gas-meters, which was created for the purpose of this thesis. The route potentially used by the gas company workers is then the result of the thesis. Furthermore, the thesis presents specific corporate savings possibly brought by using the presented program.

This thesis aspires to optimize the processes in agriculture and wood-working company and to propose some changes if needed. At first, it is wood-working branch which is analyzed. The intent is to find an optimal route to distribute pallets and afterwards freight the vehicle by sawn wood and return back with. This is some modification of travelling salesman problem with more than one salesman and more centers including the condition that the travelling is dynamic in time and that only selected clients are visited. The agriculture problem is more complicated and complex because the model aims to find an optimal portfolio of diverse animal and vegetal production influenced by many factors and some of them are mentioned below. The agriculture model includes for example the stochastic character of weather and the condition that the herd of cattle should be stable.

The thesis describes the principles of dynamic programming and it's application to concrete problems. (The travelling salesman problem, the knapsack problem, the shortest path priblem,the set covering problem.)

This thesis is continuation of the bachelor thesis "Model of delivery routes and placement logistics centers with opportunities of their optimization". It is about distribution problems and specifically a vehicle routing problem. The aim of this thesis is finding a solution of the vehicle routing problem which will be used repeatedly in the firm. The main task is achieving the lowest costs (total kilometers) with maximum utilization of vehicle capacity; in such conditions that all requirements of logistics centers will be satisfied and maximal capacity of vehicle will be tolerated. For calculation was used a solver Gurobi 6.0.3 in system MPL for Windows 4.2, which won't, however, provide the optimal solution and problem solving takes too long time. Next for calculation was used heuristics insert method and is written by VBA (Visual Basic for Applications) in MS Excel. Finally, there is a comparison of these methods with the original solution of the vehicle routing plan and solution of the bachelor thesis. Then the computational experiment was done, which tested effect to result, if other distribution center (starting point) will be bulit. The computational experiment was consist from heuristic insert method, solver Gurobi and heuristic saving algorithm from bachelor thesis.

Orientador: Orlando Fontes Lima Júnior / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Civil, Arquitetura e Urbanismo / Made available in DSpace on 2018-08-24T08:54:49Z (GMT). No. of bitstreams: 1 Carvalho_CarolinaCorreade_D.pdf: 5176798 bytes, checksum: 95342f9a296b035e2a6efd2a07ec8e6a (MD5) Previous issue date: 2013 / Resumo: O problema do transporte de produtos refrigerados e congelados é de grande importância e vem sendo cada vez mais estudado. Na cadeia do frio, o controle da temperatura é o fator determinante da qualidade e da validade de produtos alimentícios. Qualquer variação da temperatura fora da faixa padrão especificada ao produto pode levar a danos e perdas. Muitos trabalhos buscam entender o que acontece durante o processo de transporte com a temperatura da carga e do veículo, na qual é possível observar grandes variações deste parâmetro em função dos procedimentos pertencentes ao processo. Alguns elaboram modelos matemáticos que buscam exprimir o comportamento térmico do veículo e da qualidade do alimento em função do tempo decorrido no processo de transporte. Porém, quando se aborda o tema de roteirização de veículo dedicada exclusivamente ao tipo de carga que requer a manutenção adequada da temperatura, nota-se que ainda é uma área em desenvolvimento. Poucos trabalhos fazem uma abordagem de roteirização visando à preservação da qualidade da carga e, consequentemente, a manutenção da temperatura. No geral, modelos de roteirização buscam minimizar as variáveis relacionadas com custos operacionais, quase sempre expressas indiretamente através de medidas de tempo e de distância percorrida pelo veículo. Na sua grande maioria dos estudos, a otimização de problemas de roteirização é obtida com a aplicação de uma heurística do tipo PCV (Problema do Caixeiro Viajante). Entretanto, no processo de roteirização de um veículo envolvendo a distribuição de alimentos refrigerados e congelados, a variável temperatura deve ser incluída neste tipo de modelo, porém com certo cuidado, pois ela não apresenta um comportamento linear durante o percurso. Este cenário exige uma modelagem matemática específica, e obviamente mais complexa que respeite os limites de temperatura específicos ao alimento transportado e, ao mesmo tempo, assemelhe-se a situações reais. Deste modo, o objetivo do trabalho é desenvolver uma metodologia para roteirização dinâmica de veículo que combine o problema da variação da temperatura no transporte de alimento refrigerado e congelado a aspectos logísticos, melhorando assim o cenário atual de perdas e danos deste tipo de mercadoria. Esta metodologia foi aplicada a um cenário hipotético de distribuição utilizando a sequência do PCV. Foi possível constatar que este tipo de sequência, que busca menores distâncias, não consegue garantir as temperaturas ideais da carga transportada. Por outro lado, quando o algoritmo é aplicado novamente buscando soluções de sequências que garantam os índices térmicos e minimizam a distância, soluções ponderadas são obtidas. Além da contribuição acadêmica para a área de roteirização e modelagem dinâmica o presente trabalho visa auxiliar empresas que realizam o transporte e distribuição deste tipo de mercadoria / Abstract: The transportation problem of refrigerated and frozen products is of great importance and is being increasingly studied. In the cold chain, temperature control is determinant of quality and shelf life of food products. Any variation of the temperature product out of range can lead to damage and loss. Many studies seek to understand what happens during the transportation process to load and vehicle temperature, in which is possible observe large variations of that parameter. Some of tham, elaborate mathematical models that express the vehicle thermal behavior and the quality of the food according to elapsed time in the transport process. However, when addressing the issue of routing vehicle dedicated to this type of cargo, we note that it is still a developing area. Few studies make a routing approach in order to preserve the quality of the load and, consequently, the maintenance of temperature. Overall, routing models seek to minimize the variables related to operating costs, often expressed indirectly through measures of time and distance traveled by the vehicle. Mostly, the optimization of routing problems is obtained by applying a heuristic type PCV (TSP). However, in the routing vehicle process involving the distribution of chilled and frozen foods, the temperature variable should be included, but with some atention, since it does not present a linear behavior during the journey. This scenario requires a specific mathematical modeling, and obviously more complex than meets the specific temperature limits to food transported and at the same time, resemble to real situations. Thus, the aim of this work is to develop a methodology for dynamic vehicle routing that combines the problem of temperature variation in the transport of chilled and frozen food with logistics aspects, thus improving the current scenario of loss and damage of this type of products. This methodology was applied to a hypothetical distribution scenario using the sequence of the PCV. It was possible to show that this type of sequence, seeking shorter distances, can not guarantee the cargo optimal temperatures. On the other hand, when the algorithm is applied again looking for solutions that that can ensure thermal indices and minimize the distance, weighted solutions are obtained. Besides contributing to the academic research, the resulting developments will also contribute to the logistic practice, providing the transportation companies with elements to improve the distribution planning and to maintain the temperature limits inside the acceptable levels / Doutorado / Transportes / Doutora em Engenharia Civil

The traveling salesman problem (TSP) has become a classic in the field of combinatorial optimization. Attracting computer scientists and mathematicians, the problem involves finding a minimum cost Hamiltonian cycle in a weighted graph.