Minimale Distanz zwischen zwei gewählten Objekten in einem Netzwerk |
| 01.12.2012, 19:58 | manuesi | Auf diesen Beitrag antworten » | ||
| Minimale Distanz zwischen zwei gewählten Objekten in einem Netzwerk Also kurze, vereinfachte Problemschilderung: Ich habe ein Strassennetzwerk bestehend aus n Objekten, jedes Objekt entspricht einem Strassenabschnitt und hat eine definierte Länge L(n). Des Weiteren hat jedes Objekt eine binäre Variable d(n), d(n)=1 heisst im nächsten Zyklus wird der Strassenabschnitt instandgestellt, d(n)=0 heisst der Strassenabschnitt wird so belassen wie er ist. Dazu gibt es mehrere Bedingungen (maximales Budget, maximale Baustellenlänge, minimale Distanz zwischen zwei Baustellen), und das Problem muss mittels branch-and-bound (also linear-programming) lösbar sein, folglich: es lässt sich in matrixform darstellen. Vereinfachend sagen wir mal das Problem beschränke sich auf ein rein serielles netzwerk, z.B. n: 1--2--3--4 L(n): 2--2--2--2 (Zahlen an sich irrelevant) Der Budget-constraint ist trivial, summe[d(n)*C(n)] wenn C(n)=entstehende Kosten beim Objekt n im Falle eines Eingriffs. Die maximale Baustellenlänge ist etwas weniger trivial aber lässt sich als matrix darstellen. Sagen wir maximale Länge ist 5 sähe die matrix folgendermassen aus: |2, 2, 2, 0| = M |0, 2, 2, 2| |d1| = d |d2| |d3| |d4| |5| = l |5| |5| |5| M*d<=l da dies die einzigen Varianten sind wie die maximale Länge überschritten werden kann. Nun füge ich eine weitere Bedingung hinzu, z.B. dass einzelne Baustellen min. 3 auseinander sein müssen. d1=1, d2=1, d3=0, d4=1 wäre eine Lösung die die Maximallängen-Bedingung nicht verletzt, allerdings liegen zwischen der ersten Baustelle und der zweiten nicht 3 Längeneinheiten. Längen die am Rande des Netzwerks liegen unterliegen dieser Bedingung nicht (grenzen sozusagen an einen beliebig langen, Baustellen freien Strassenabschnitt). dazu habe ich zwei Fragen: 1. ist das Problem überhaupt linear lösbar? Lösungen mit if-then Bedingungen hätte ich auch, allerdings sind die nicht mittels branch-and-bound lösbar. 2. falls dieses Problem überhaupt linear lösbar ist, weiss jemand wie sich das anstellen lässt? Meine Ideen: Was mich zur Annahme bringt, dass das Problem linear lösbar ist, ist dass die Bedingung mit der maximalen Baustellenlänge so lösbar ist. Allerdings weiss ich nicht wie sich eine solche Lösbarkeit zeigen lässt, und eine sinnvolle Umsetzung ist mir ehrlich gesagt auch noch nicht eingefallen. Die Anpassung vom kurzen, seriellen Netzwerk auf ein grosses, gemischtes Netzwerk stellt dann wiederum kein Problem dar. Gibt es allenfalls irgendwelche Literatur die in diese Richtung geht und jemand hier kennt? Danke für allfällige Unterstützung... |
||||
| 02.12.2012, 00:04 | Abakus | Auf diesen Beitrag antworten » | ||
| RE: Minimale Distanz zwischen zwei gewählten Objekten in einem Netzwerk Hallo, dein nächster Schritt ist es, zu versuchen die Variablen und Modellgleichungen/-restriktionen aufzustellen. Dabei wird bestimmt vieles klarer. Den Abstand zwischen 2 Baustellen kennst du eigentlich, demzufolge kannst du kodieren, ob diese beiden Baustellen zusammen ausgewählt werden können oder nicht. Dies für alle Baustellen so zu machen, ergibt natürlich einige Möglichkeiten dann. Der Start könnte ein Graphen-Modell sein. Abakus 
|
||||
| 02.12.2012, 11:49 | manuesi | Auf diesen Beitrag antworten » | ||
Also wenn ich das richtig verstehe, meinst du das einführen von weiteren binären Variablen die z.B. angeben ob die Baustelle x mit der nächsten Baustelle verbunden ist oder nicht? also ich schildere sonst kurz mal wie weit ich bin: - jedes Objekt n hat drei Varianten: --- n.0 heisst ich tue nichts --- n.1 ist intervention-type 1 (spielt keine Rolle was das ist) --- n.2 ist intervention-type 2 ---d[n.x]=1 heisst diese Variante wird gewählt, d[n.x]=0 heisst die Variante wird nicht gewählt - jedes Objekt hat eine Länge Ln - jeder Node (also n.x) hat kosten für das Bauen C[n.x] und einen Benefit der daraus resultiert B[n.x] dann ergibt sich einen Kontinuitäts-constraint, der sich als Matrix darstellen lässt. Die Gleichungen wären entsprechend: d[1.0]+d[1.1]+d[1.2] = 1 (d[1.0]+d[1.1]+d[1.2]) - (d[2.0]+d[2.1]+d[2.2]) = 0 etc etc. Objective function: dann nach maximales Budget: dann eine neue binäre Variable y[n] = d[n.1]+d[n.2], sagt folglich: y[n] = 0 keine Baustelle in Objekt n, y[n] = 1 Baustelle in n vorhanden. dann eine riesige Matrix die von jedem möglichen Startpunkt aus die Kilometer solange zusammenzählt bis die Länge > 20 km ist (20 km ist die maximale Länge der Baustellen). sagen wir dieser Matrix M. wenn M*y <= [20] ist keine Baustelle über 20 km lang, wenn M*y an irgendeiner Stelle >20 dann hat es min. eine Baustelle die länger ist. (Ich hoffe das ist verständlich formuliert). Zur Veranschaulichung lass ich grad graphviz code generieren, der die gewählte Lösung darstellt. Das sieht dann (ohne minimale Distanz-Bedingung) z.B. so aus: BILD Der mittlere Punkt ist jeweils .0, also "nichts tun". Daraus kann ich natürlich schon die kürzeste Distanz zwischen zwei Baustellen rauslesen, allerdings ändert die sich natürlich jedes Mal beim optimieren und sollte ja fix als Bedingung eingegliedert sein. Mein Problem ist dass ich im Moment die Anzahl der verknüpften Baustellen nicht bestimmen kann (obwohl ich nicht weiss ob mir das überhaupt weiterhelfen würde), sondern nur die Anzahl Objekte bei denen etwas gemacht wird. |
||||
| 08.12.2012, 14:27 | Abakus | Auf diesen Beitrag antworten » | ||
Du könntest dein Programm für 1, 2, 3.. Baustellen schreiben erstmal. Ich frage mich bei deinem Graphen derzeit, ob es nicht Sinn machen könnte, alle Möglichkeiten einfach brute-force auszuprobieren. Sind das noch zuviele? Abakus
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
