0 Daumen
430 Aufrufe

Aufgabe:

Ich habe eine Art des "Traveling Salesman Problems" vorliegen, bei welchem bestimmte Routen jedoch fest definiert sind, sprich es gibt Kanten, welche bereits vordefiniert sind und nicht "optimiert" werden dürfen, z.B. wenn eine Ware von A nach B muss lautet die Kante (a,b). Die Wege zu A bzw. von B weg zu den weiteren fixen Kanten oder anderen Punkten sind jedoch variabel. Die Skizze hier soll es nochmal verdeutlichen:

Logik_TSP.png


Zur Erklärung: die Routen in gelb sind feste Routen, welche nicht verändert werden können. Sehr wohl können jedoch die Wege zwischen den Routen optimiert werden, sodass am Ende die gefahrene Distanz (und weitere Parameter, auf welche hier jetzt nicht weiter eingegangen wird) minimal sind.

Das Ganze wird als Graph dargestellt. Die Menge ist definiert als: \( A=\left\{(i, j) \in V \times V: a_{i}+t_{i j} \leq b_{j}, i, j \neq o\right\} \)


Problem/Ansatz:

Wie kann ich die Menge darstellen um die fixierten Routen (i,j) als zwingende Voraussetzung zu definieren bzw. die Auswahlmöglichkeit auf die Routen zwischen den Anfangs- und Endpunkten zu beschränken?

Avatar von

1 Antwort

0 Daumen

Ich würde die gelben Kanten zu einem Knoten schrumpfen.

Avatar von 45 k

Aber jede Kante besteht doch aus zwei Knoten (Anfangsknoten und Endknoten)? Wie würdest du daraus einen Knoten machen?

Wenn Du mitteilen würdest, wie die Aufgabe / Problemstellung konkret lautet, dann kann sicher jemand vorzeigen, wie das konkret funktioniert.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community