TSP Archive - Blogofant - Elefantisch gut!

In diesem Artikel geht um betriebliche Optimierungsprobleme und Algorithmen. Zudem werden Graphen, Pfade und Kreise wiederholt und die Komplexität besprochen. Zu den Algorithmen wird auf Heuristiken und Approximationsalgorithmen eingegangen, wobei dieses sich hauptsächlich auf das Travelling Salesman Problem (Problem des Handlungsreisenden) sowie das Rucksackproblem konzentrieren. Hier geht es vor allem um die Generierung einer gültigen Tour oder einer gültigen Zusammensetzung des Problems. Weiters gibt es eine Sektion zu möglichen Verbesserungsheuristiken. Komplexität Probleme in der Betriebswirtschaft gelten meist als ziemlich umfangreich sowie komplex. Aus diesem Grund muss mit den Ressourcen sparsam umgegangen werden. Bei Optimierungsproblemen und Algorithmen geht es dabei um eine zeitliche Komponenten (Rechenschritte) sowie eine Speicherkomponente (Speicherzellen). Bedacht werden sollte zudem, dass jeder Speichervorgang einem Rechenschritt (Zeitkomponente) entspricht. Zur Klassifizierung wird dabei auf die O-Notation zurückgegriffen. Beispiel: $latex 2x^{4}+3x^{2}+x$ wird zu $latex 2x^{4}+3x^{4}+x^{4} 6x^{4}$ und somit verhält sich das Problem asymptotisch wie $latex x^{4}$. Dadurch spricht man von einer Ordnung 4 beziehungsweise O(4). Die Zahl "6" ist dabei lediglich eine Konstante. Die Komplexität wird dabei von der Größer der Inputdaten abhängig gemacht. So besitzen a Knoten und b Kanten eine Inputgröße aus der Summe von a + b. Eine ganze Zahl c hingegen entspricht einer Inputgröße von log(c). Unterschieden wird zudem noch in polynomische Algorithmen $latex O(n^{c}$ und exponentielle Algorithmen $latex O(c^{n}$. Graphen, Pfade, Kreise und Spannbäume Vollständige Graphen Ein Graph G(V,E) (näheres über die Definition im Beitrag über Graphen) besteht aus Knoten und Kanten, welche die Knoten verbinden. Ein vollständiger Graph verbindet jeden einzelnen Knoten mit jedem anderen Knoten. Es ist also eine Verbindung zwischen allen einzelnen Knoten auf direktem Weg möglich. Bei N Städten ergibt dies $latex \frac{n*(n-1)}{2}$ bzw. $latex {n}\choose{2}$ Kanten. Dies geht aus der Definition von regulären Graphen (jeder Knoten besitzt die gleiche Anzahl an Kanten) hervor: Erstens ist jeder vollständige Graph ein regulärer Graph und jeder Knoten hat (N-1) Nachbarn. Für eine ungerade Anzahl an N ist ein vollständiger Graph sogar ein Eulscher Graph. Ein Graph ist ein eulscher Graph wenn jeder Knoten eine gerade Anzahl an Nachbarn hat. Pfade Der Pfad beschreibt eine Folge von Knoten, wobei ein Pfad nur existieren kann, wenn Kanten zwischen den Knoten vorhanden sind. Dabei dürfen sich die Knoten wiederholen. Bei einem geschlossenen Pfad entspricht der Ausgangspunkt dem Eingangspunkt, sodass der Startknoten Endknoten. Kreis Ein Kreis ist ein Pfad, wobei jeder Knoten nur einmal besucht werden darf und vorkommt. Dies bedeutet, es darf sich kein Knoten wiederholen - allerdings müssen nicht alle Knoten besucht werden. Ein Hamiltonscher Kreis ist hingegen ein Kreis bei dem alle Knoten besucht werden. Ein vollständiger Graph besitzt dabei immer einen Hamiltonschen Kreis. Spannbaum Ein Spannbaum ist ein Teilgraph eines Graphen. Zudem ist ein Spannbaum kreisfrei und besitzt n-1 Kanten - es gilt somit |E'| |V| - 1. Häufiger wird allerdings der Minimum Spanning Tree (MST, Minimaler Spannbaum) gesucht. Dieser lässt sich durch den Algorithmus von Prim oder Algorithmus von Kruskal bestimmen. Bei einem gewichteten Graphen gilt somit $latex \sum_{e aus E'}W_{e}$ Mehr über Bäume könnt ihr in diesem Beitrag erfahren. TSP - Problem des Handlungsreisenden - Travelling Salesman Ein TSP versucht die kürzeste Tour (jeder Knoten nur einmal besucht) aus n verschiedenen Orten mit paarweisen Distanzen zu generieren. Er gilt dadurch als zentrales und wesentliches Problem der Routenplanung. Zudem löst das TSP das Problem des Hamiltonschen Kreises und gilt als NP schweres Problem. Ein TSP liefert weiters keine Gütegarantie, außer für metrische TSP (z.B. bei Anwendung der Christofides Heuristik). Aus einem gegebenen vollständigen Graphen lässt sich eine TSP generieren. Unvollständige Graphen werden zu vollständigen Graphen erweitert, wobei die eingefügten Kanten (Hilfskanten) ein sehr hohes Gewicht haben (meist "Big" M, unendlich oder MAX). Von einer beliebigen Stadt n gibt es (N-1) mögliche Nachbarstädte. Von dieser wiederum (N-2) Möglichkeiten. Dies bedeutet es gibt bei N Städten (Knoten) insgesamt $latex (n-1)!$ mögliche Touren (asymmetrischer Fall). Oftmals ist das Problem symmetrisch (Hinweg Rückweg und keine Einbahnstraßen), wodurch sich die Anzahl der Touren auf $latex \frac{(n-1)!}{2}$reduziert. Durch die Anzahl der Kanten lässt sich die Komplexität des TSP bestimmen. Der TSP Algorithmus entspricht nach Umwandlung von $latex \frac{n*(n-1)}{2}$ einer Komplexität mittels O-Notation von O(2). Modellierung des TSP: $latex min \sum^{n}_{i1}\sum^{n}_{ j1, j \neq i}d(i,j)*x_{i,j}$ s.t. $latex \sum^{n}_{ j1, j \neq i}x_{i,j} 1\forall i$ s.t. $latex \sum^{n}_{ j1, j \neq i}x_{j,i} 1\forall i$ s.t. $latex \sum_{i \in S}\sum_{ j \ in S, j \neq i}*x_{i,j} \leq |S|-1 \forall S \subset V und |S| > 1$ s.t. $latex x_{i.j} \in (0,1)\ i,j 1, ... , n\ und\ i \neq j$ Es gibt allerdings exponentiell viele Nebenbedingungen, weshalb das Problem zuerst ohne Nebenbedingung 4 gelöst wird. Sollte die Nebenbedingung in der Lösung verletzt sein ( es gibt Subtouren), wird die verletzte Nebenbedingung hinzugefügt und das Problem erneut gelöst. Dies passiert solange iterativ, bis keine Subtouren entstehen. TSP unter Miller, Tucker und Zemlin Die Subtour-Elimination wird durch folgende Nebenbedingung gelöst (bzw. ersetzt Nebenbedingung 4): $latex u_{i} - u_{j} + (n-1)x_{i,j} \leq (n-2) mit 2 \leq i \neq j \leq n$ Metrisches TSP Bei einem metrischen TSP gilt die sogenannte Dreiecksungleichung (auch aus dem Satz des Pythagoras). Diese besagt, dass die Hypotenuse (die direkte Verbindung zwischen zwei Knoten) größer als jeder der beiden Katheten (Umweg über einen Knoten) aber kleiner-gleich der Summe der Katheten sein muss. Dies bedeutet, dass die direkte Verbindung entweder kürzer oder zumindest gleich lang als jene über einen anderen Knoten ist. Beispiele für metrisches TSP sind grafische Travelling Salesman Probleme (2 Dimensional) sowie euklidische TSP Probleme. Ganzzahliges TSP Ein ganzzahliges TSP oder auch lineares Programm besitzt lediglich linearen Terme. Dies bedeutet, dass die Zielfunktion als auch alle Ungleichungen linear sind. Rucksackproblem Bei einem Rucksackproblem kann der normale Greedy Algorithmus (höchster Profit zuerst) versagen. Besser wäre hingegen die Bewertung nach der Effizienz, also das Verhältnis zwischen Profit und Gewicht. Vehicle Routing Aus einem Depot werden Kunden mit einer Anzahl an Fahrzeugen beliefert. Dabei hat jeder Kunde einen gewissen Bedarf an Gütern und jedes Fahrzeug eine Kapazitätsbeschränkung. Gesucht sind Touren, wobei die Gesamtkosten reduziert werden und der Bedarf an Kunden erfüllt ist sowie die Fahrzeuge die Kapazitätsbeschränkung einhalten. Lineare Programmierung und Optimierungsproblem Jedes Optimierungsproblem besteht aus drei Elementen: Entscheidungsvariablen: Variablen, welche wir verändern können (bzw. das Programm)Zielfunktion: beschreibt eine Funktion, welche minimiert oder maximiert werden sollNebenbedingungen: Restriktionen, sodass nicht jede Möglichkeit funktioniert (Restriktion für die Entscheidungsvariablen) Die meisten Anwendungen verlangen zudem eine Nicht-Negativitäts-Beschränkung, sodass nur positive Werte als Ergebnis entstehen können. Zudem haben Fixkosten in der Regel keinen Einfluss auf die Optimierung, sodass die Optimierung mit oder ohne Fixkosten auf das selbe Ergebnis kommt (für das Endergebnis spielen Fixkosten sehr wohl eine Bedeutung). Linearisierung (Absolute) Beträge: $latex |x_{1}+x_{2}-x_{3}| \leq 5$ wird umgeformt in $latex x_{1}+x_{2}-x_{3} \leq 5$$latex -x_{1}-x_{2}+x_{3} \leq 5$ Logische Funktionen: Definierte Anzahl an eingebundenen Entscheidungsvariablen: Falls eine gewisse Anzahl an Entscheidungsvariablen einbezogen werden soll - weder mehr noch weniger. $latex x_{1}+x_{2}+x_{3}+x_{4}2$ Und Funktion: $latex x_{1}$ und $latex x_{2}$ - beide müssen enthalten sein oder keiner darf enthalten sein. $latex x_{1}x_{2}$ Oder Funktionen: $latex x_{1}$ oder $latex x_{2}$ - jedoch nicht beide sind erlaubt. $latex x_{1}+x_{2}\leq 1$ XOR Funktionen: Hierbei muss entweder die eine, die andere oder beide Nebenbedingungen zutreffen. $latex 5x_{1}+x_{2}\geq 10\ or\ 3x_{3}-4x_{4}\leq 8 \ or\ both$ $latex 5x_{1}+x_{2}\geq 10 - M*y_{1}$$latex 3x_{3}-4x_{4}\leq 8 + M*(1-y_{1})$$latex y_{1} \in (0,1)$ Wenn Dann Funktion: Hierbei wird auf eine XOR Funktion zurückgegriffen. Falls die erste Bedingung zutrifft, muss die zweite Bedingung erfüllt werden. Gelöst wird das durch Drehung der IF-Bedingung. $latex 5x_{1}+x_{2}\leq 10\ or\ 3x_{3}-4x_{4}\geq 8$ wird zu $latex 5x_{1}+x_{2}\geq 11\ or\ 3x_{3}-4x_{4}\geq 8 \ or\ both$ Fixkosten: Bestehen aus zwei Möglichkeiten, wobei eine Binärvariable hinzugefügt wird. $latex w_{1} 1,\ wenn\ x_{1} \geq1$$latex w_{1} 0,\ wenn\ x_{1} 0$ Umgesetzt wird die Nebenbedingung folgendermaßen: $latex x_{1} \leq M*w_{1}$ Heuristiken und Approximationsalgorithmen Eine Heuristik versucht in möglichst kurzer Zeit eine gute Lösung zu finden. Hierbei geht es um einen Trade-Off zwischen Zeit sowie Qualität. Je mehr Zeit vorhanden ist, umso höher die Qualität (in der Regel - allerdings kein muss). Approximationsalgorithmen liefern im Gegensatz zu Heuristiken einen Gütequalität. Dies bedeutet, man kennt die maximale Entfernung zur optimalen Lösung. Die wirkliche Entfernung zwischen der Lösung des Approximationsalgorithmus und der Optimallösung bleibt allerdings unbekannt. Die Gütegarantie wird meist als Alpha bezeichnet und ergibt sich aus $latex min \alpha$. In diesem Beitrag gibt es zudem viele weitere Heuristiken und Metaheuristiken. Nearest Neighbour Heuristik beim TSP Von einem beliebigen Startknoten wird gestartet. Es wird immer vom letzt besuchten Knoten (am Anfang der Startknoten) der nächst mögliche noch nicht besuchte Knoten genommen. Diese Vorgehensweise kann beliebig schlecht performen, da am Ende eine sehr weite Strecke (oder bei Einbahnstraßen eine unmögliche Strecke) als Ergebnis herauskommt. Deshalb sollte die Heuristik schlussendlich mit jedem Knoten als Startknoten wiederholt werden. Die Nearest Neighbour Heuristik gehört zu den Greedy Algorithmen. Laufzeit: Wählen eines Knotens: konstant O(1)Füge Knoten zum Pfad hinzu und lösche aus unbesuchten Knoten O(n)Lese Distanz zu Nachbarn aus, (n-1) Nachbarn, finde Minimum O(n)Iteration wird genau (n-1) mal aufgerufen O(1) + n*(O(1) + (O(n) + O(n)) O(n²) Sortieren ist unter anderem auch in O(n log n) möglich. Insertion Heuristik beim TSP Nearest Insertion Heuristik: Kürzeste Kante aller paarweisen Distanzen wird genommen und zur aktuellen Subtour hinzugefügt. Im unteren Beispiel würde somit der Knoten D genommen, da er mit einem Wert von 3 die geringste Distanz aufweist. Liefert eine Güte von 1/2.Farthest Insertion Heurisitk: Zuerst wird der minimale Abstand zwischen den einzelnen Knoten in der Subtour und allen Knoten außerhalb der Subtour berechnet. Im unteren Beispiel ist dies der Wert 4 zum Knoten C, sowie 3 zum Knoten D. Danach wird der größte minimale Abstand genommen. In diesem Fall ist dies die Entfernung 4 zum Knoten C. Dies bedeutet der Knoten C wird zur Subtour hinzugefügt. Bei Farthest Insertion ist keien Güte bekannt. Knoten in Tour (A/B) - Knoten außerhalb (C/D) C D A 4 3 B 7 8 Random Insertion Heuristik: Das hinzufügen der Touren erfolgt rein zufällig. Meist wird zufällig gestartet und anschließend eine Nearest Neighbour Heuristik durchgeführt beziehungsweise umgekehrt. Cheapest Insertion Heuristik: Liefert eine Güte von 1/2. MST Heuristik Eine MST ist immer niedriger als ein TSP, da der Weg der Rundreise zurück fehlt. Der MST lässt sich mit dem Algorithmus von Prim oder Algorithmus von Kruskal berechnen. Eine Möglichkeit von einem MST zum TSP ist es, die MST Kanten zu verdoppelt. Dadurch entsteht ein eulscher Graph. Insgesamt gilt, dass $latex T_{MST} \leq Eulersche Kreis 2*MST \leq 2*Opt^{*}$. Dies dadurch, dass bei einer Tour die Wege direkt gefahren werden können (Dreiecksungleichung). Dies bedeutet, dass eine aus dem MST erhaltene TSP Tour maximal dem doppelten der Optimallösung entspricht. Christofides Heuristik Einen MST findenMinimum Weight Matching zwischen allen Knoten mit ungeraden Grad - deren Anzahl ist gerade wodurch M perfekt istMST und Matchingkanten zu einem eulerschen Graph verbindenEulerschen Kreis konstruieren Mittels Christofides Heuristik für metrische TSP ergibt sich eine $latex \frac{2}{3}$ Approximation. Metaheuristiken Metaheuristiken sind meist problemspezfisch und für unterschiedliche Probleme geeignet. Dabei besitzen sie allerdings keine Gütegarantie. Meist besitzen Metaheuristiken einen Heuristischen Kern auf dessen sie aufbauen. Aufgrund der umfangreichen Thematik über Metaheuristiken, erfahrt ihr hier mehr über Metaheuristiken. Genetische Algorihmen Genetische Algorithmen wählen aus einer Menge verschiedene Elemente und evaluieren diese aufgrund der Kriterien Verschiedenheit und Lösungsgüte (Zielfunktionswert). Dies bedeutet, dass sehr gute Elemente in die Menge kommen als auch sehr verschiedene Elemente. Danach werden diese Elemente miteinander verschmolzen (nach einem vordefinierten frei wählbaren Konzept, hier in blau dargestellt). Um einem lokalen Optima zu entfliehen, erfolgt eine anschließende Mutation (in rot dargestellt). Beispiel: Element A111100000Element B101010101Neu generiert C101000000Mutiert C101001000 Generisch für TSP Tour1 1-2-3-4-5-6-7-8 und Tour2 3-2-4-6-8-1-7-5Zufallszahl 4Tour' 1-2-3-4-6-8-7-5 und Tour'' 3-2-4-6-1-5-7-8 Abbruchkriterium: Anzahl an Generationen, Zeit, letzte Verbesserung nach x Iterationen, x Iterationen, etc. Ant Colony / Ameisenheuristik Jede Kante bekommt eine Konzentration $latex k_{i}$. Die Wahrscheinlichkeit zur Wahl eines Pfades lautet $latex p_{i}\frac{k_{1}}{\sum k_{i}}$. Nach einer Zeit nimmt die Konzentration ab: $latex k_{i} (1-p)*k_{i}$. Bei Benützung des Weges erhöht sich die Konzentration: $latex k_{i} k_{i}+\frac{Q}{Weglaenge}$ Diese Heuristik ist gut geeignet für Routen und Netzwerkprobleme. Tabu Search Die meisten Suchen gelangen in ein lokales Optimum oder lokales Minimum. Gesucht ist aber das globale Maximum oder Minimum oder kurz: das globale Optimum. Aus diesem Grund versucht Tabu Search mit einer Liste verbotene Menge von Zügen zu speichern. Diese Züge dürfen eine gewisse Anzahl an Iterationen nicht wiederholt oder rückgängig gemacht werden. Dadurch werden andere Kombinationen versucht, welche möglicherweise aus lokalen Optima entfliehen. Hei einer Tabu Search darf es auch zu einer Verschlechterung kommen - die beste bisher gefundene Lösung wird allerdings immer abgespeichert. Verbesserungsheuristiken Verbesserungsheuristiken haben die Aufgabe eine bestehende Lösung zu verbessern. So wird beim TSP eine bestehende Tour versucht zu verbessern. First Fit VS Best Fit Bei First Fit wird die erste Verbesserung, welche gefunden wird, genommen und eventuell ein neuer Durchgang gestartet. Bei Best Fit werden zuerst alle Möglichen Kombinationen durchprobiert und anschließend die best-möglichste genommen, wobei erst danach ein neuer Durchgang startet. Dadurch können beide Varianten zu unterschiedlichen Ergebnissen kommen. 2-Opt Ein 2-Opt Verfahren löscht zwei Kanten und fügt zwei neue Kanten ein, sodass wieder eine Tour entsteht. Die Komplexität entspricht dabei der Anzahl an allen Paaren. Es gibt in einer Tour (N-1) Kanten sowie N Knoten. Dies entspricht durch $latex (n-1)*n$ einer Komplexität von O(2). Bei metrischen TSP zählt die Elimination von Überschneidungen durch die Dreiecksungleichung zu Verbesserungen. 3-Opt Bei einem 3-Opt werden zufällig 3 Kanten entnommen. Durch jede Entnahme gibt es 6 neue Möglichkeiten die Tour zusammenzuschließen, ohne dass Subtouren entstehen. Eine 3-Opt Strategie liefert meist Lösungen, welche lediglich 3% vom Optimum entfernt sind. Größere Opt Verfahren werden meist aufgrund der steigenden Komplexität nicht mehr durchgeführt. Or-Opt Eine Or-Opt entspricht einem Mittelweg zwischen einem 3-Opt und einem 2-Opt Verfahren. Suche drei Knoten a, b, cLösche die Kante von Knoten i (Vorgänger) nach a sowie j (Vorgänger) nach cWähle eine Kante zwischen zwei Knoten e und fVerbinde a mit e und c mit f (Tour 1) ODER a mit f und c mit e (Tour 2)

Verschlagwortet: TSP

Betriebliche Optimierungsprobleme und Algorithmen

Logistische Analyse und Begriffe

Baum – Graphen

Werbung / Advertisement

Top Ratings

Werbung / Advertisement

Werbung / Advertisement

Werbung / Advertisement

Werbung / Advertisement

Neueste Beiträge

Werbung / Advertisement

Werbung / Advertisement