Use Multilevel Graph Partitioning Scheme to solve traveling salesman problem

The traveling salesman problem is although looking very simple problem but it is an important combinatorial problem. In this thesis I have tried to find the shortest distance tour in which each city is visited exactly one time and return to the starting city. I have tried to solve traveling salesman problem using multilevel graph partitioning approach.Although traveling salesman problem itself very difficult as this problem is belong to the NP-Complete problems but I have tried my best to solve this problem using multilevel graph partitioning it also belong to the NP-Complete problems. I have solved this thesis by using the k-mean partitioning algorithm which divides the problem into multiple partitions and solving each partition separately and its solution is used to improve the overall tour by applying Lin Kernighan algorithm on it. Through all this I got optimal solution which proofs that solving traveling salesman problem through graph partition scheme is good for this NP-Problem and through this we can solved this intractable problem within few minutes.Keywords: Graph Partitioning Scheme, Traveling Salesman Problem.

From the road network database to a graph for localization purposes

The problems of finding best facility locations require complete and accurate road network with the corresponding population data in a specific area. However the data obtained in road network databases usually do not fit in this usage. In this paper we propose our procedure of converting the road network database to a road graph which could be used in localization problems. The road network data come from the National road data base in Sweden. The graph derived is cleaned, and reduced to a suitable level for localization problems. The population points are also processed in ordered to match with that graph. The reduction of the graph is done maintaining most of the accuracy for distance measures in the network.

Dialekter och röstigenkänning : Ett röstigenkännings-API:s förmåga att uppfatta svenska dialekters kännetecken och röstkombinationer

Allt eftersom utvecklingen går framåt inom applikationer och system så förändras också sättet på vilket vi interagerar med systemet på. Hittills har navigering och användning av applikationer och system mestadels skett med händerna och då genom mus och tangentbord. På senare tid så har navigering via touch-skärmar och rösten blivit allt mer vanligt. Då man ska styra en applikation med hjälp av rösten är det viktigt att vem som helst kan styra applikationen, oavsett vilken dialekt man har. För att kunna se hur korrekt ett röstigenkännings-API (Application Programming Interface) uppfattar svenska dialekter så initierades denna studie med dokumentstudier om dialekters kännetecken och ljudkombinationer. Dessa kännetecken och ljudkombinationer låg till grund för de ord vi valt ut till att testa API:et med. Varje dialekt fick alltså ett ord uppbyggt för att vara extra svårt för API:et att uppfatta när det uttalades av just den aktuella dialekten. Därefter utvecklades en prototyp, närmare bestämt en android-applikation som fungerade som ett verktyg i datainsamlingen. Då arbetet innehåller en prototyp och en undersökning så valdes Design and Creation Research som forskningsstrategi med datainsamlingsmetoderna dokumentstudier och observationer för att få önskat resultat. Data samlades in via observationer med prototypen som hjälpmedel och med hjälp av dokumentstudier. Det empiriska data som registrerats via observationerna och med hjälp av applikationen påvisade att vissa dialekter var lättare för API:et att uppfatta korrekt. I vissa fall var resultaten väntade då vissa ord uppbyggda av ljudkombinationer i enlighet med teorin skulle uttalas väldigt speciellt av en viss dialekt. Ibland blev det väldigt låga resultat på just dessa ord men i andra fall förvånansvärt höga. Slutsatsen vi drog av detta var att de ord vi valt ut med en baktanke om att de skulle få låga resultat för den speciella dialekten endast visade sig stämma vid två tillfällen. Det var istället det ord innehållande sje- och tje-ljud som enligt teorin var gemensamma kännetecken för alla dialekter som fick lägst resultat överlag.

Influência da temperatura e da presença de H2S no comportamento mecânico e eletroquímico do aço API 5CT grau P110 em água do mar sintética

o presente trabalho teve por objetivo estudar o comportamento de um aço de alta resistência e baixa liga (com amostras de composição aproximada de 0,4% C, 0,6% Cr e 0,4% Mo), da classe API scr PIlO, utilizado na perfuração de petróleo offshore, frente a processos de fragilização causados pelo meio. Água do mar sintética foi utilizada como meio, com intuito de padronizar, em laboratório, as condições a que o material fica submetido na prática. Buscou-se avaliar e comparar o comportamento mecânico do material pela modificação dos parâmetros: temperatura, potencial aplicado ao material, e o efeito da presença ou ausência de H2S na solução. Para isso, foram realizados ensaios de tração pelo método de baixa taxa de deformação (da ordem de 10-6S-I), obtendo-se as curvas tensão x deformação nas diferentes situações ensaiadas, comparadas com as obtidas em óleo mineral. Análises fratográficas também foram utilizadas como forma de caracterizar os processos de fragilização. Além disso, estudou-se o comportamento eletroquímico do material nas diferentes condições através de ensaios de polarização potenciostáticos. Com isso, pode-se determinar quais as condições mais danosas e de maior risco para a utilização do material e em quais delas o seu uso é seguro. O aço estudado apresentou-se susceptível a processos de fragilização e todos os parâmetros analisados mostraram-se importantes no estudo desses processos.

Determinação da pressão de colapso em tubos API 5L X56 aplicando o método R6

O presente trabalho tem como objetivo determinar a pressão de colapso de tubos API 5L X56 de parede fina com trincas longitudinais internas e externas submetidas a pressão interna. Foi utilizado o método R6 conforme a norma BS7910:1999 e a Análise por Elementos Finitos. Foram feitos ensaios de tração e de caracterização da tenacidade do material utilizado por integral J, assim como o modelamento por Elementos Finitos do tubo e a aplicação dos “Failure Assessment Diagram” FAD para determinar a pressão de colapso. Verificou-se que para trincas internas a pressão de colapso é levemente maior que em trincas externas. Isto é mais acentuado para trincas com uma profundidade maior que a metade da parede do tubo. As predições da pressão de colapso em função do tamanho da trinca do método R6 em comparação com alguns resultados experimentais mostraram uma precisão satisfatória, porem em alguns casos não conservadora.

Estudo da susceptibilidade à corrosão sob tensão e à corrosão : fadiga do aço API X65 aspergido termicamente utilizado em componentes offshore

Aços de alta resistência mecânica, aspergidos termicamente, são os materiais mais adequados para garantir o bom desempenho de certos componentes de plataformas offshore, expostos a situações severas de carregamento em água do mar. A literatura apresenta vários estudos relativos ao efeito combinado entre esforços mecânicos e o meio agressivo, em aços de alta resistência, entretanto, poucos avaliam o desempenho desses aços aspergidos metalicamente. A susceptibilidade à corrosão sob tensão e à corrosão-fadiga, de um aço de alta resistência mecânica aspergido termicamente, empregado em componentes de plataformas offshore, foi avaliada mediante as técnicas de ensaio de tração com baixa taxa de deformação, ensaio de fadiga por flexão em três pontos e metalografia da fratura. Os ensaios foram realizados em água do mar sintética ao potencial de corrosão e à um potencial catódico, utilizando-se amostras de aço revestidas termicamente com zinco e alumínio pelo processo de aspersão com plasma spray. O comportamento de amostras ensaiadas ao ar foi usado como parâmetro para avaliação do desempenho do aço em água do mar. Os resultados obtidos indicam que o aço revestido é susceptível à corrosão sob tensão e à corrosão fadiga em água do mar, sendo que o mecanismo de fragilização envolve a ruptura prematura dos revestimentos e a participação do hidrogênio.

Desenvolvimento de ensaios de corrosão-fadiga para juntas soldadas de aço API 5L X60

Este trabalho tem por objetivo desenvolver um equipamento de ensaios para avaliar a vida de juntas soldadas, provenientes de tubulações para extração de petróleo, submetidas à corrosão-fadiga. Para atingir este objetivo foi estudado em que condições de corrosãofadiga uma tubulação esta exposta em alto mar sendo então definidos os parâmetros mais relevantes para serem reproduzidos em laboratório em corpos de prova menores. Nesta etapa foram definidos quais seriam os parâmetros de ensaio que o equipamento deveria atender. O equipamento foi construído para ensaiar uma junta soldada circunferencial por flexão a quatro pontos através de um sistema hidráulico com controle de carga com uma freqüência de 0,2 Hz e razão de carregamento, R=0,1. Para validar o equipamento foi usado um corpo de prova instrumentado com extensômetros resistivos para comparar o a carga calculada com a experimental e determinar se o nível de carregamento se mantêm constante ao longo dos ensaios. Foi levantada uma curva de fadiga com o equipamento desenvolvido e comparada com uma curva de fadiga feita ao ar do mesmo material em uma máquina servo hidráulica MTS.