Verfahren für die Berechnung und Abschätzung der Tourenlänge des Handlungsreisendenproblems mit wenigen Orten
- Eines der am intensivsten untersuchten Probleme aus dem Bereich der Optimierung stellt das sogenannte Traveling Salesman Problem (TSP, in deutsch: Handlungsreisendenproblem) dar. Die Aufgabe hinter dem Handlungsreisendenproblem besteht darin, für eine gegebene Anzahl an Orten eine Route zu entwickeln, sodass die Gesamtlänge der Route minimal ist. Zudem darf kein Ort, bis auf den ersten, mehrmals besucht werden. Ziel der vorliegenden Bachelorarbeit ist es, statistische Untersuchungen bezüglich der Tourlänge des TSP in Abhängig der Anzahl der besuchten Städte vorzunehmen, wobei der Fokus auf einer kleinen Anzahl von Städten liegt. Dazu wurde das Problem einerseits numerisch gelöst und die Verteilung der Lösungen analysiert. Für Teilaspekte wurden analytische Lösungen berechnet.
- One of the most intensively studied problems in the area of optimization is the so-called Traveling Salesman Problem (TSP). The task behind the traveling salesman problem is to develop a route for a given number of locations so that the total length of the Route is minimal. Also, no place, except the first one, can be visited several times. The present bachelor thesis aims to carry out statistical investigations regarding the tour length of the TSP in dependence on the number of visited cities, whereby the focus is on a small number of cities. On the one hand, the problem was solved numerically and the distribution of the solutions was analyzed. For some subproblems, analytic solutions were calculated.
| Author: | Christian Blümel |
|---|---|
| URN: | urn:nbn:de:kobv:co1-opus4-50291 |
| DOI: | https://doi.org/10.26127/BTUOpen-5029 |
| ISSN: | 2627-6100 |
| Series (Serial Number): | Cottbus Mathematical Preprints (7, 2019) |
| Editor: | Armin FügenschuhORCiD |
| Document Type: | Bachelor thesis |
| Language: | German |
| Year of Completion: | 2019 |
| Release Date: | 2019/11/15 |
| Tag: | Gemischt-ganzzahlige lineare Optimierung; Handlungsreisendenproblem; Modellierung; Statistik; Verteilungsfunktion Distribution function; Mixed-integer linear optimization; Modeling; Statistics; Traveling Salesman Problem |
| GND Keyword: | Ganzzahlige lineare Optimierung; Travelling-salesman-Problem; Mathematische Modellierung; Verteilungsfunktion |
| Institutes: | Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Ingenieurmathematik und Numerik der Optimierung |
| Licence (German): |  Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International |
