Laden...

Anzahl von Vereinen in 10er Gruppen einteilen, bei denen die Fahrtstrecken möglichst kurz sind?

Erstellt von syl vor 4 Jahren Letzter Beitrag vor 4 Jahren 1.559 Views
S
syl Themenstarter:in
4 Beiträge seit 2019
vor 4 Jahren
Anzahl von Vereinen in 10er Gruppen einteilen, bei denen die Fahrtstrecken möglichst kurz sind?

Hallo zusammen!

Ich arbeite derzeit an einem Programm, welches für einen Sportverband die Vereinseinteilung in regionale Gruppen automatisieren soll. Sprich es soll eine bestimmte Anzahl von Vereinen (bis max. 160) in einzelne 10er Gruppen eingeteilt werden, bei denen die Fahrtstrecken möglichst kurz sind.

Eine Lösung um aus einem Pool von 20 Vereinen zwei "perfekte" Gruppen zu ermitteln habe ich bereits gefunden und sie läuft auch performant. Hier lasse ich alle möglichen Kombinationen einer 10er Gruppe durchlaufen (die zweite Gruppe ergibt sich dann ja automatisch) und ermittle so jene Kombination zweier Gruppen, die zusammen die wenigsten Gesamtkilometer ergeben.

Mein Problem ist, dass ich bei Pools mit mehr als 20 Vereinen keine zufriedenstellende Lösung finde. Folgende Lösungsansätze habe ich bisher versucht:

* Splitten des Pools, indem ich die beiden am weitesten voneinander entfernten Vereine ermittle und ihnen abwechselnd die nächstgelegenen Vereine zuordne. So bekomme ich aus einem 160 Pool zwei 80er -> vier 40er -> acht 20er -> hier kann ich dann meinen ursprünglichen Algorithmus wieder anwenden. Leider werden mit dieser Logik manchmal sich sehr nahe liegende Vereine in unterschiedliche Pools getrennt, speziell wenn sie nicht in der Nähe der beiden Ausgangsvereine liegen.

* bei 40er Pool: suchen der perfekten 10er Gruppe, dann die beste Gruppe aus den übrigen 30 Vereinen etc... nicht brauchbar, weil aufgrund zu vieler möglicher Kombinationen unperformant, außerdem landet in der letzten Gruppe der "Rest" der gar nicht zusammenpasst 😉

Hat jemand Ideen wie man das angehen könnte? Bin für jeden Lösungsansatz dankbar!

Liebe Grüße,
syl

5.657 Beiträge seit 2006
vor 4 Jahren

Im ersten Schritt würde ich einen Brute-Force-Algorithmus schreiben, der alle Kombinationen aller Kombinationen berechnet, und dann die beste auswählt. Da braucht man noch nichts zu optimieren, und da kann man auch nicht viel optimieren. Du mußt alle Entfernungen aller Punkte voneinander berechnen, und dann alle möglichen Gruppen-Kombinationen. Dann bewertest du die Ergebnisse und suchst das beste Ergebnis aus. Die Abstands-Berechnungen an sich sind ja trivial, und wenn die Berchnung aller Kombinationen ein paar Stunden (oder Tage?) dauert, und sie nicht oft neu berechnet werden müssen, reicht das vielleicht schon aus.

Evtl. kann man zumindest Teile der Berechnung auch parallel abarbeiten, um alle verfügbaren Prozessorkerne zu nutzen.

Eine darauf basierende Variante wäre, das initial berechnete Ergebnis aus Ausgangsbasis für eine Neuberechnung zu verwenden, sobald sich die Anzahl oder Lage der Vereine geändert haben. Möglicherweise kann man sich dadurch eine Menge Rechenzeit sparen, da man zumindest Teile der ursprünglichen Berechnung wiederverwenden kann.

Falls das zu lange dauert und deinen Anforderungen nicht genügt, dann brauchst du eine geeignete Heuristik. Schau dir mal die Ansätze zur Lösung des Problems des Handlungsreisenden an. Vielleicht kannst du dich davon inspirieren lassen.

Weeks of programming can save you hours of planning

C
2.121 Beiträge seit 2010
vor 4 Jahren

Dein Problem nennt sich "Travelling Salesman", damit findest du einige Lösungsansätze und auch die Erklärung warum dieses Problem nicht sehr effizient zur optimalsten Lösung kommt.

Wenn du immer genau x Vereine in einer Gruppe haben willst, wird es darauf hinauslaufen dass du zusammenliegende Vereine auseinander reißen musst.
Auch bei deinem Vorschlag (20 Vereine, 10 beste suchen, Rest bildet wieder eine Gruppe) hast du zwar eine optimale Gruppe, aber die andere Gruppe enthält den Rest mit möglicherweise katastrophaler Aufteilung.

Stell dir 20 Vereine vor. 18 davon sehr eng beisammen, der 19. ist 50 km nördlich davon und der 20. 50 km südlich. Wie willst du das machen?

Letztendlich kommt die Lösung auf deine Vorgaben an. Wirklich alle Voraussetzungen komplett passend wird ein Wunschtraum bleiben. Willst du lieber manche Gruppen sehr optimal haben und die anderen dürfen notfalls auch schlecht sein? Oder alle etwa gleich? Oder das Ergebnis begründbar haben?
In allen Fällen werden dir die Fahrer vorwerfen du hättest es falsch gemacht 😃

Die Aufteilung in kleinere Grüppchen zunächst ist schon sinnvoll. Wenn du 10-er Gruppen machst, brauchst du nur die sagen wir mal 20 naheliegendsten Vereine ansehen. Oder mehr, oder weniger... je nachdem wie die verteilt sind.

Ich stelle mir gerade eine Landkarte vor auf der die ganzen Orte eingezeichnet sind. Da könnte es sich lohnen die Programmierzeit lieber für eine Überlegung zu investieren, wie man das selbst machen würde. Klingt zwar sehr untechnisch, könnte aber vielleicht schneller sein.
Zumindest versuchen würde ich es, dadurch gewinnst du dann einige Erkenntnisse wie dein Programm vorgehen könnte.

Edit: Brute force mit 160 Vereinen... das könnte dann dauern 😉

S
syl Themenstarter:in
4 Beiträge seit 2019
vor 4 Jahren

Vielen Dank schon mal für Eure Anregungen.

@MrSparkle: Ziemlich genau so wie du es im deinem 1. Absatz beschreibst funktioniert mein Algorithmus bei 20 Vereinen. Das wird aber bereits bei 40 Vereinen zu einer langwierigen Angelegenheit, spätestens bei 80 oder gar 160 Vereinen ist das überhaupt nicht mehr praktikabel.

@chilic: Bei 20 Vereinen kann ich beide Gruppen parallel berechnen und ermittle so die Gesamtdistanz aus beiden Gruppen zusammen. So wird verhindert, dass eine Gruppe viel schlechter aufgeteilt ist als die andere.

Das Travelling Salesman Problem zielt soweit ich weiß darauf ab, die kürzeste Route zum Erreichen aller Standorte zu finden. Das hilft mir hier leider nicht wirklich weiter.

An anderer Stelle habe ich den Tipp zum k-Means-Algorithmus bekommen, der klingt interessant.

5.657 Beiträge seit 2006
vor 4 Jahren

Das Travelling Salesman Problem zielt soweit ich weiß darauf ab, die kürzeste Route zum Erreichen aller Standorte zu finden. Das hilft mir hier leider nicht wirklich weiter.

Ist aber ein ähnliches Problem, da muß man halt ein wenig abstrahieren. Es diente vor allem zur Veranschaulichung, daß man hier Heuristiken einsetzen muß, und man nicht so ohne weiteres DIE eine Lösung finden kann. Der k-Means-Algorithmus ist aber tatsächlich näher an deinem Problem dran.

Da könnte es sich lohnen die Programmierzeit lieber für eine Überlegung zu investieren, wie man das selbst machen würde.

Wenn ich vor dem Problem stünde, würde ich auch lieber ein Tool erstellen, daß mir Vorschläge bereitstellt, und ich die Gruppen dann selbst zusammenklicken kann. Manchmal ist Ortskenntnis und ein bißchen gesunder Menschenverstand besser als eine exakte Lösung.

Weeks of programming can save you hours of planning

6.911 Beiträge seit 2009
vor 4 Jahren

Hallo syl,

k-means sehe ich hier nicht passend, denn die Aufgabe hat mir Clustering nicht viel zu tun.
Das "Problem des Handelsreisenden" ist schon näher dran, v.a. mit dem von MrSparkle erwähnten weiteren Abstraktionsschritt. [Artikel] Simulated Annealing kann als Lösungsverfahren dafür verwendet werden. Bei den "Kosten", welche es ja zu minimieren gilt, baust du noch die regionalen Gruppen mit ein und das wars (zumindest konzeptionell).

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

S
syl Themenstarter:in
4 Beiträge seit 2019
vor 4 Jahren

Wenn ich vor dem Problem stünde, würde ich auch lieber ein Tool erstellen, daß mir Vorschläge bereitstellt, und ich die Gruppen dann selbst zusammenklicken kann. Manchmal ist Ortskenntnis und ein bißchen gesunder Menschenverstand besser als eine exakte Lösung.

Danke, genau so habe ich es jetzt realisiert, macht am meisten Sinn.
Ich benutze einen k-Means++ ähnlichen Ansatz, der vereinfacht gesagt ausgehend von zufälligen Clustermittelpunkten abwechselnd die nähesten Vereine zuordnet und dann für jede Gruppe und jeden Verein den Fahrtaufwand ermittelt.

@gfoidl: wie mir das Problem des Handelsreisenden hier helfen soll kann ich noch immer nicht ganz nachvollziehen. Aber wenn man so will ist meine Logik zur Ermittlung des Fahrtaufwands eine Abstraktion davon.