Kaktus-Repräsentation der minimalen Schnitte eines Graphen und Anwendung im Branch-and-Cut Ansatz für das TSP

Kaktus-Repräsentation der minimalen Schnitte eines Graphen und Anwendung im Branch-and-Cut Ansatz für das TSP

by Klaus Wenger

Paperback

$45.50
Choose Expedited Shipping at checkout for guaranteed delivery by Thursday, August 29

Overview

Inhaltsangabe:Zusammenfassung:
Diese Diplomarbeit leistet einen Beitrag zur algorithmischen Lösung des Problems des Handelsreisenden (Traveling Salesman Problem, TSP).
Der Handelsreisende sucht eine kürzeste Rundreise durch eine fest gegebene Menge von Städten, wobei die Weglängen zwischen je zwei Städten bekannt sind.
Die Anwendungen des TSPs gehen weit über Fahrtroutenoptimierung hinaus.
Das erfolgreichste Verfahren zur exakten Lösung NP-schwerer diskreter oder kombinatorischer Optimierungsprobleme wie dem TSP ist Branch-and-Cut.
Dieses Verfahren ist eine Kombination aus Branch-and-Bound und dem Schnittebenenverfahren.
Die Diplomarbeit stellt ein Verfahren vor in dem Schnittebenen aus linearen Beschreibungen niedrigdimensionaler TSP Polytope gewonnen werden.
Pionierarbeit in dieser Richtung wurde Mitte der 90er Jahre von Christof und Reinelt geleistet.
Das hier vorgeschlagene Verfahren unterscheidet sich von diesen ersten Experimenten vor allem durch die Art der Dimensionsreduktion.
Hierzu wird die sogenannte Kaktus-Darstellung aller minimalen Schnitte von
TSP Trägergraphen, welche innerhalb des Branch-and-Cut Verfahrens für das TSP anfallen, verwendet.
Ein Schnitt in einem Graph ist eine nichtleere echte Teilmenge der Knotenmenge.
Das Gewicht eines Schnitts ist die Summe der Gewichte der Kanten mit genau einem Endknoten im Schnitt.
Ein minimaler Schnitt ist ein Schnitt minimalen Gewichts.
Die Kaktus-Darstellung der Menge aller minimalen Schnitte eines Graphen kann als Datenstruktur angesehen werden welche die Inklusions- und Überlappungsstruktur der Menge der minimalen Schnitte unter Verwendung von wenig Speicher widerspiegelt.
Sie wurde erstmals Mitte der 70er Jahre von Dinitz et al. vorgeschlagen.
Die Kaktus-Datenstruktur wird verwendet, um TSP Trägergraphen aussichtsreich zu schrumpfen.
Für kleine geschrumpfte Graphen werden Schnittebenen in den linearen Beschreibungen von kleinen TSP Polytopen mittels des quadratischen Zuordnungsproblems (QAP

Product Details

ISBN-13: 9783838678030
Publisher: diplom.de
Publication date: 07/02/2017
Pages: 250
Product dimensions: 5.83(w) x 8.27(h) x 0.57(d)

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews