The Maximum Scatter TSP on a Regular Grid : How to Avoid Heat Peaks in Additive Manufacturing

Titelangaben

Stock, Isabella:
The Maximum Scatter TSP on a Regular Grid : How to Avoid Heat Peaks in Additive Manufacturing.
Bayreuth , 2017 . - XI, 157 S.
( Dissertation, 2016 , Universität Bayreuth, Bayreuther Graduiertenschule für Mathematik und Naturwissenschaften - BayNAT )

Volltext

	Format: PDF Name: Stock_Isabella_The_Maximum_Scatter_TSP.pdf Version: Veröffentlichte Version Verfügbar mit der Lizenz Creative Commons BY 4.0: Namensnennung
	Download (10MB)

Abstract

The thesis at hand consists of the extended results of a part of the project CHAMP - Control of Heat in Automatic Model Production. The project was carried out in cooperation between the chairs of business mathematics and mathematics for engineering sciences at the University of Bayreuth as well as Concept Laser GmbH in Lichtenfels and supported by the Oberfrankenstiftung. It deals with the control of a laser and its impact on the deflections in workpieces which are produced with the patented LaserCUSING technology. LaserCUSING is a technology for additive manufacturing which means that one-component metal powder is completely melted. This process is completed layer by layer. The single layers are divided into so-called "islands". The laser - and therefore the melting - proceeds from one island to another. In this work, different island strategies are examined with regard to the deflections of the workpiece. The results are used to find the most appropriate strategy. Thereby the following result is obtained: Despite very different island strategies, our test samples made of austenitic stainless steel showed no significant differences in the deflections. Consequently, short distances between consecutive islands can reduce the length of the laser's route and thus decrease the production time without reducing the quality of the workpiece. If a workpiece is made of a very sensitive material or has a very complex geometry, the amount of possible consecutive islands can be restricted. Testing the adequacy of the different optimization problems for modeling the LaserCUSING process yields several new findings. The Maximum Scatter Traveling Salesman Problem (MSTSP) aims to find a tour through a set of nodes such that the shortest appearing edge is as long as possible. In general, this optimization problem is NP-complete. Regarding the restriction to two-dimensional instances with Euclidean distances, it still remains open whether it is NP hard or not. Starting from a linear-time procedure which computes an optimal solution of the MSTSP for nodes in one line, we develop an algorithm for nodes on a two-dimensional (m x n)-grid with Euclidean distances. It is called Weave(m,n). In combination with further combinatorial solutions of the MSTSP for particular kinds of grid sizes (Bobeven(m,n) and Bobodd(m,n)), we can produce an optimal solution of the MSTSP for most grid sizes; for the remaining cases, we can prove at least an asymptotical optimality of Weave(m,n). For all but four grid sizes, the length of the shortest edge received from our algorithms is at least 80% of the optimal shortest edge. Weave(m,n), Bobeven(m,n) and Bobodd(m,n) can be extended to a three-dimensional grid. For more than half of all possible grid sizes, these extensions yield an optimal solution. For the remaining grid sizes, approximation algorithms can be deduced. At the same time, the new solution of the MSTSP is an asymptotically optimal solution for the "TSP with forbidden neighborhoods" (TSPN) if a particular minimum edge length is chosen. In this optimization problem, the shortest tour through a given set of nodes is required such that the used edges are longer than a minimum length. Weave(m,n), Bobeven(m,n) and Bobodd(m,n) are asymptotically optimal for the TSPN with a specific minimum edge length which equals the length of the shortest edge of the combinatorial algorithm. Furthermore, a more general heuristic LS_MSTSP is developed for the approximation of the MSTSP. It is based on the idea of local search heuristics and the heuristic of Lin and Kernighan. The complexity of LS_MSTSP is O(n^3). For more than 80% of the tested instances, this heuristic computes a solution whose shortest edge has a length of at least 80% of the longest possible shortest edge. A related problem to the MSTSP is the Max-Min 2-Neighbor TSP (MM2NTSP). In this optimization problem two kinds of edges are maximized at the same time: the shortest edge in the tour and the shortest edge between the predecessor and the successor of a node. The computation of a solution is at least as hard as for the MSTSP. LS_MSTSP is adapted to that problem (LS_MM2NTSP) with remaining complexity O(n^3). For more than 30% of the tested instances, LS_MM2NTSP produces a tour whose shortest edge has a length of at least half the length of the longest possible shortest edge. For more general instances than grids, solutions of the MSTSP can be approximated in polynomial time by LS_MSTSP and LS_MM2NTSP. So far, the developed algorithms are not yet applied in the laser melting process, but continue to appear relevant for a reduction of the laser's route with certain minimum distances.

Abstract in weiterer Sprache

Die vorliegende Arbeit besteht aus den erweiterten Ergebnissen eines Teils des Projekts CHAMP - Control of Heat in Automatic Model Production. Das Projekt ist eine von der Oberfrankenstiftung geförderte Kooperation der Lehrstühle für Wirtschafts- und Ingenieurmathematik der Universität Bayreuth sowie der Concept Laser GmbH in Lichtenfels. Es befasst sich mit den Auswirkungen der Lasersteuerung auf die Verzüge in Bauteilen, die mit dem patentierten LaserCUSING Verfahren hergestellt werden. LaserCUSING ist eine Technologie zur additiven Fertigung, bei der einkomponentiges Metallpulver vollständig aufgeschmolzen wird. Dies geschieht schichtweise, wobei die einzelnen Schichten in sogenannte "Islands" unterteilt sind. Das Aufschmelzen erfolgt Islandweise. In dieser Arbeit werden die Auswirkungen unterschiedlicher Island-Strategien, das heißt unterschiedlicher Island-Reihenfolgen, auf die Verzüge im Bauteil untersucht, um dadurch die am besten geeignete Strategie zu finden. Dabei wird das folgende Resultat erzielt: Bei unseren Testbauteilen aus einem nichtrostenden, austenitischen Stahl gibt es keine signifikanten Unterschiede bezüglich der Verzüge bei sehr unterschiedlichen Island-Strategien. Folglich können kurze Distanzen zwischen aufeinanderfolgenden Islands die Verfahrwege des Lasers verringern und die Produktionszeit verkürzen ohne dass man einen Verlust der Bauteilqualität hinnehmen muss. Bei empfindlichen Bauteilen kann die Menge von erlaubten Nachfolge-Islands eingeschränkt werden. Bei der Untersuchung, ob verschiedene Optimierungsprobleme zur Modellierung der Problemstellung geeignet sind, werden einige neue Erkenntnisse zum Maximum Scatter Traveling Salesman Problem (MSTSP) gewonnen. Beim MSTSP wird eine Tour durch eine Punktemenge gesucht, in der die kürzeste vorkommende Kante so lang wie möglich ist. Dieses Optimierungsproblem ist im Allgemeinen NP-vollständig. Für die Einschränkung auf den zweidimensionalen Fall mit euklidischen Distanzen ist die Frage der NP-Vollständigkeit noch ungeklärt. Ausgehend von einem Verfahren, das mit linearem Zeitaufwand eine optimale Lösung für das MSTSP für Punkte auf einer Linie ausgibt, entwickeln wir ein Verfahren für Punkte auf einem zweidimensionalen (m x n)-Gitter mit euklidischen Distanzen. Dieses wird mit Weave(m,n) bezeichnet. In Kombination mit zusätzlichen kombinatorischen Lösungen des MSTSP (Bobeven(m,n) und Bobodd(m,n)) für spezielle Arten von Gittern können wir so das MSTSP für die meisten Gittergrößen optimal lösen; für die übrigen Fälle können wir zumindest asymptotische Optimalität zeigen. Bei fast allen Gittergrößen bis auf vier Ausnahmen beträgt die kürzeste Kante aus unseren Verfahren mindestens 80% der Länge der maximalen kürzesten Kante. Auch im dreidimensionalen Gitter können die neuen Verfahren unter Anpassungen an die neue Dimension angewandt werden. Für mehr als die Hälfte aller möglichen Gittergrößen erhält man optimale Lösungen. Für die übrigen Gittergrößen lassen sich Approximationen herleiten. Gleichzeitig ist unsere neue Lösung des MSTSP eine asymptotisch optimale Lösung für das "TSP on grids with forbidden neighborhoods" (TSPN), wenn eine bestimmte minimale Kantenlänge gewählt wird. Bei diesem Optimierungsproblem wird eine kürzeste Tour durch eine gegebene Knotenmenge gesucht, wobei die Mindestkantenlänge zwischen aufeinanderfolgenden Knoten fest vorgegeben ist. Weave(m,n), Bobeven(m,n) und Bobodd(m,n) sind asymptotisch optimal für das TSPN mit einer Mindestkantenlänge, die der Länge der kürzesten Kante des kombinatorischen Algorithmus entspricht. Des Weiteren wird eine allgemeinere Heuristik LS_MSTSP zur Approximation des Maximum Scatter TSP entwickelt. Diese basiert auf der Idee von local search-Heuristiken und der Lin-Kernighan Heuristik. LS_MSTSP hat eine Laufzeitkomplexität von O(n^3). Diese Heuristik findet für über 80% der berechneten Beispielinstanzen eine Lösung mit einer kürzesten Kante von mindestens 80% der Länge der maximalen kürzesten Kante. Ein verwandtes Problem zum MSTSP ist das Max-Min 2-Neighbor TSP. Bei diesem wird neben der kürzesten Kante einer Tour gleichzeitig auch die kürzeste Kante zwischen dem Vorgänger und dem Nachfolger eines Knotens maximiert. Die Berechnung einer Lösung ist mindestens genauso schwer wie beim MSTSP. LS_MSTSP wird für dieses Problem angepasst (LS_MM2NTSP) mit gleichbleibender Komplexität. Bei mehr als 30% der getesteten Instanzen liefert LS_MM2NTSP eine Tour mit einer Mindestkantenlänge, die das 0,5-fache der optimalen Mindestkantenlänge beträgt. Für allgemeinere Instanzen als Gitter kann mit LS_MSTSP und LS_MM2NTSP in Polynomialzeit eine Lösung approximiert werden. Bisher finden die entwickelten Algorithmen noch keine direkte Anwendung im Laserschmelzprozess, allerdings erscheinen sie gerade für eine Verkürzung der Laserwege mit einer Mindestsprungweite des Lasers weiterhin relevant.