---

Geschrieben von tmp am 03.03.2017 um 13:25:

  Tool zur Lösung eines Graphenproblems gesucht

Hi zusammen!

Folgende Aufgabenstellung:

- es gibt 5 Stationen
- jede Station hat eine unterschiedliche Aufenthaltsdauer
- zwischen den Stationen gibt es einen Weg (mit unterschiedlicher Dauer) zurückzulegen

- es gibt 5 Teams
- jedes Team muss jede Station besuchen (die Reihenfolge spielt keine Rolle)
- pro Station darf nur ein Team vor Ort sein

- es gibt eine finale Station, an der alle Teams möglichst zur selben Zeit eintreffen sollen

Meine Zeit als Informatikstudent ist schon lang vorbei, aber ich weiß, dass es sich um ein Standardproblem handelt, für das es mit Sicherheit Programme zur Ermittlung der Lösung gibt. Könnt ihr mir einen Tipp geben, womit ich das Problem modellieren und lösen kann?

Danke schon mal!

---

Geschrieben von ed209 am 05.03.2017 um 06:12:

 

Waere es nur ein team, dann haettest du es mit dem "Travelling salesman problem" zu tun (die Zeit an den Stationen wuerdest Du schlicht ignorieren, weil die in der Summe immer gleich sind).

Die Variante mit mehreren Teams kenne ich bisher noch nicht. Starten alle teams an derselben Station (dann waere die 1-team pro station regel ja schon gebrochen) oder koennen sie sich eine aussuchen.

Duerfen Teams laenger an einer Station verweilen als noetig?

Gruss,
ED

---

Geschrieben von tmp am 08.03.2017 um 15:27:

 

sie können sich eine station heraussuchen.
und ja, sie dürfen länger verweilen.

nur die gesamtzeit soll minimiert werden

---

Geschrieben von skubidoo09 am 08.04.2017 um 08:25:

  RE: Tool zur Lösung eines Graphenproblems gesucht

Ich empfehle Dir Neo4j als Graphen-basierte Datenbank-Lösung zur einfachen Modellierung des Graphen. Ein Tool zur direkten Berechnung der Lösung kenne ich nicht