Suche Algorithmus für TSP mit optionalen Knoten

[Kaspatoo]

Hallo,

ich bereite gerade meine Bachelorarbeit vor und arbeite mich ein wenig in die Thematik ein. Es geht nun grob darum, ein optimales Routing zu finden speziell für E-Cars. Das Kriterium dabei ist die Ladekapazität. Sprich es soll zwar die kostengünstigste (Lohnkosten werden mit berücksichtigt, also der Zeitfaktor) gefunden werden, aber die muss befahrbar sein, sprich das Fahrzeug darf nicht „liegen bleiben“.

Gegeben habe ich eine sogenannte OD-Matrix, mit den bereits kürzesten Wegen zwischen allen Knoten (Start, Ziel, Zwischenziele sowie mögliche Ladestationen). Gesucht wird also nur noch die optimale Reihenfolge (klassisches TSP).
Mein Problem zur Zeit ist die Suche nach einem geeigneten Algorithmus. Denn im Gegensatz zum klassischen TSP stellen die Ladestationen nur optionale Knoten dar. Im besten Falle werden diese natürlich nicht besucht, können aber verwendet werden um lange Strecken zu überbrücken.

Bisher hatte ich nur einen halbwegs brauchbaren Gedanken dazu. Ich würde so vorgehen, dass ich zunächst das TSP mit allen Knoten außer den Ladestationen lösen würde. Die gefundene Route würde ich schrittweise „abfahren“ und den Ladestand beobachten. Ist der Akku leer, begebe ich mich zum letzten Knoten zurück und würde versuchen, die bevorstehende Kante durch das Einfügen eines oder mehreren Beliebigen LadeKnoten zu überbrücken. Wird keine Lösung gefunden, wird die Kante zunächst künstlich verteuert (z.B. 999999). Dies würde aber die Dreiecksgleichung zerstören oder? Jedenfalls würde dann von diesem Knoten ausgehend eine andere Lösung gesucht unter Berücksichtigung der künstlichen Kosten. Würde auch von diesem Knoten ein Schritt zurückgegangen werden, würde die Kante ebenfalls verteuert, die zuvor verteuerten Kanten aber wieder auf ihren normalwert gesetzt (in anderer Reihenfolge müssen Sie ja nicht zum Erliegen führen). So ganz optimal kann dieser Lösungsansatz aber nicht sein und daher bin ich noch nicht zufrieden.

Per Google-Suche habe ich kein passendes Thema gefunden, dass im Prinzip ein TSP mit optionalen Knoten behandelt. Auch finde ich nichts über eine parallele Kantengewichtung. Also dass zum Einen die wirtschaftlichen Kosten minimiert werden müssen und zum Anderen die Stromladung als bool’sche Bedingung mit berücksichtigt wird.

Jetzt habe ich ein wenig Hoffnung, dass ihr mir an dieser Stelle ein wenig weiterhelfen könnt. Vielleicht hat jemand ein paar Ideen oder sogar Stichwörter nach denen ich suchen könnte.

Ich würde mich über alle Antworten sehr freuen.
Danke!

[Moritz_fe1b4f]

Hallo,

Bisher hatte ich nur einen halbwegs brauchbaren Gedanken dazu.
Ich würde so vorgehen, dass ich zunächst das TSP mit allen
Knoten außer den Ladestationen lösen würde. Die gefundene
Route würde ich schrittweise „abfahren“ und den Ladestand
beobachten. Ist der Akku leer, begebe ich mich zum letzten
Knoten zurück und würde versuchen, die bevorstehende Kante
durch das Einfügen eines oder mehreren Beliebigen LadeKnoten
zu überbrücken. Wird keine Lösung gefunden, wird die Kante
zunächst künstlich verteuert (z.B. 999999).

Das hört sich soweit recht vernünftig an.

Ich hätte noch eine andere Idee, keine Ahnung ob die zu vernünftigen Ergebnissen führt.

Du könntest vor der Suche alle Knotenpunkte ablaufen, und alle rausschmeissen, die nicht innerhalb der Reichweite einer Ladestation sind (oder vielleicht innerhalb der halben Reichweite, den man will ja nicht nur zwischen der Autobahn und einer Ladestation hin- und herpendeln). Ebenso müßtests du Kanten in deinem Graph von vornherein entfernen, wenn sie länger als die Reichweite des Autos sind.

Das hätte den Vorteil, dass es nur eine einmalige Operation auf deinen Kartendaten ist, und du danach den Standardalgorithmus zum Suchen der Route berechnen kannst.

Wenn du die Möglichkeit hast, würde ich empfehlen, so früh wie möglich mit dem Experimentieren an den Algorithmen anzufangen, sodass du nicht lange welche ausarbeitest, die dann in der Praxis nicht funktionieren.

Grüße,
Moritz

[Peter_TOO]

Hallo Fragewurm,

Du müsstest eigentlich alle möglichen Teilstrecken zwischen den Ladestationen berechnen.
Hinzu kommen noch die Teilstrecken zwischen Start und allen möglichen Ladestationen sowie zwischen allen Ladestationen und Ziel.
Desweiteren würde ich auch noch die Ladezeit berechnen, man muss ja nicht jedesmal eine Vollladung machen, sondern nur die Menge welche für die Teilstrecke benötigt wird.

Mit diesen Angaben kannst du dann jede Teilstrecke gewichten und die günstigste Variante aus dieser Tabelle zusammenstellen.

Wenn die Bedingungen konstant sind, also keine aktuellen Staus, Umweltbedingunen usw. berücksichtigt werden müssen, könnte es Programmtechnisch sogar vorteilhaft sein, diese Tabelle nur einmalig für ein bestimmtes Fahrzeug zu berechnen.
Für eine konkrete Route müssen dann nur noch die Wegen zwischen Start und Ziel zu den möglichen Ladestationen berechnet werden, was Rechenzeit einsparen kann.

Es kann durchaus günstiger sein, zuerst eine Ladestation anzusteuern, welche einem vom Ziel weiter entfernt, weil man dann als nächtes eine optimalere Route zur nächsten Ladestaion fahren kann, welche weit ab von anderen Ladestationen liegt.

Falls direkt am Ziel keine Ladestation liegt, sollte man noch eine entsprechende Reserve im Akku haben, um für den nächsten Trip noch eine anfahren zu können.

Nur so als Anregung, habe das Ganze nur mal auf die Schnelle überdacht, kann also noch (Denk-)Fehler enthalten.

MfG Peter(TOO)

[Hendrik_70c5fb]

Hallo,

eine sehr interessante Frage. Ich glaube, es gibt einen Weg, dein Problem in ein Standard-TSP umzuformen. Beim TSP hast du ja die Formulierung

\min\sum\limits_{i\in V}\sum\limits_{j\in V\setminus{i}}c_{ij}x_{ij}

s.t.

\sum\limits_{i\in V\setminus{j}}=1\ \forall j\in V

\sum\limits_{j\in V\setminus{i}}=1\ \forall i\in V

\sum\limits_{i\in S}\sum\limits_{j\in S\setminus{i}}x_{ij}\leq\mid S\mid-1\ \forall S\subseteq V

x_{ij}\in{0,1}\ \forall i\in V,j\in V

Die erste Bedingung drückt aus, dass jede Stadt von genau einer anderen Stadt aus angefahren wird.
Die zweite Bedingung bedeutet, dass man von jeder Stadt genau eine andere Stadt anfährt.
Die dritte Bedingung ist die sogenannte subtour elimination constraint. Sie verhindert, dass mehrere voneinander getrennte Touren entstehen, die zusammen zwar alle Städte erreichen, von denen jede aber nur einen Teil der Städte abfährt.
Die letzte Bedingung sagt, dass die Strecke von einer Stadt zu einer anderen nur gefahren oder nicht gefahren werden kann.

Nun fasst du mit V alle deine Stationen zusammen, also sowohl die obligatorischen Zwischenstationen als auch die optionalen Ladestationen. Dann definierst du dir die beiden Mengen V_ob und V_op als die Menge der obligatorischen und der optionalen Zwischenstationen. Es gilt dann also

V=V_{ob}\cup V_{op}\text{ mit }V_{ob}\cap V_{op}=\emptyset

Dann ersetzt du die ersten beiden Nebenbedingungen durch

\sum\limits_{j\in V\setminus{i}}x_{ij}=1\ \forall i\in V_{ob}

\sum\limits_{i\in V\setminus{j}}x_{ij}=1\ \forall j\in V_{ob}

\sum\limits_{j\in V\setminus{i}}x_{ij}\leq 1\ \forall i\in V_{op}

\sum\limits_{i\in V\setminus{j}}x_{ij}\leq 1\ \forall j\in V_{op}

Wäre interessant zu erfahren, ob es klappt.
Viel Erfolg!

hendrik

[Kaspatoo]

Hi,

danke für den Ansatz aber ich verstehe nicht recht wie du das gewichten willst.

Denn die ursprüngliche Kantengewichtung kann die Weglänge aber auch die Fahrzdauer sein oder beides, wenn man auch noch die Lohnkosten des Monteurs berücksichtigt. Außerdem können durch Zeitfenster (da Mittags alle zum Essen sind ist es besonders günstig dann ein Update einzufahren anstatt mitten drin) ganz kuriose Reihenfolgen entstehen.

Da kann ich bei der bestehenden Kantengewichtung nicht einfach die Ladung mit reinbringen.

Und wenn es doch geht und ich habe eine Kante die kostet sonst 5 und ich addiere jetzt die Ladung mit 4 hinzu, und habe dahinter eine Kante mit sonst 3 und addiere aber 7 für Ladung hinzu (z.B. weil sehr stark stop & go) dann erhalte ich zufällig eine scheinbar optimale tour mit Ladekosten von 11 obwohl die Kapazität nur 10 ist.

Also durchgeblickt hab noch nicht richtig.
Danke für die Hilfe.

[Peter_TOO]

Hallo Fragewurm,

danke für den Ansatz aber ich verstehe nicht recht wie du das
gewichten willst.

Eine Strecke besteht aus Fahrzeit und benötigter Leistung.
10km Bergstrecke ergeben also unterschiedliche Energieverbräuche abhängig davon ob du den Berg rauf oder runter fahren muss.

Praktisch ist nun aber das „Tanken“ von Akkus etwas anders als das von Akkus.
Das eigentliche Füllen des Tanks mit Benzin ist zeitlich eine lineare Funktion, doppelte Menge Benzin = doppelte Zeit für den Füllvorgang.
Hinzu kommen noch die Zeiten für warten, austeigen, Zapfpistole handeln und bezahlen.

Das Laden von Akkus geht mehr in Richtung einer e-Funktion. Das Laden von 0 auf 50% braucht weniger Zeit als eine Ladung von 50 auf 100%.
(jetzt mal ganz abgesehen davon, dass man einen Akku nicht ganz entladen sollte).
Es macht also keinen Sinn den Akku an jeder Station auf 100% aufzuladen.

Somit können zwei Teilstrecken mit jeweils 50% Ladung schneller sein als eine 100%-Ladung ohne zwischenhalt.

Was auch noch nicht klar ist, ist ob der Monteur arbeiten kann, während das Fahrzeug geladen wird?

Denn die ursprüngliche Kantengewichtung kann die Weglänge aber
auch die Fahrzdauer sein oder beides, wenn man auch noch die
Lohnkosten des Monteurs berücksichtigt. Außerdem können durch
Zeitfenster (da Mittags alle zum Essen sind ist es besonders
günstig dann ein Update einzufahren anstatt mitten drin) ganz
kuriose Reihenfolgen entstehen.

Das ist beim TSP so, das Optimum kann auf den ersten Blick sehr kurios wirken, je nachdem welche Faktoren man wie gewichtet

Da kann ich bei der bestehenden Kantengewichtung nicht einfach
die Ladung mit reinbringen.

Die aktuelle Ladung im Akku muss ausreichen um die Strecke abfahren zu können. Andernfalls musst du zuerst Laden oder eine andere Strecke wählen.

Du hast das Problem ja schon ganz normal bei Fahrtantritt, auch wenn du mit Benzin fährst. Wenn der Tankinhalt nicht bis zur nächsten Tanke reicht, seh ich alt aus.
Notfalls fahren dann viel zur nächsten, teuren, Tanke und tanken da mal für 5€ umd damit zu einer günstigen Tanke zu fahren …

Grundsätzlich muss die Kantengewichtung gar nicht aus einem einzelnen Parameter bestehen.
Bei der Optimierung nach Zeit, könntest du als Gewichtung die Fahrzeit und die nötige Ladezeit einfach zusammenzählen.

MfG Peter(TOO)