myCSharp.de - DIE C# und .NET Community
Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 
 | Suche | FAQ

» Hauptmenü
myCSharp.de
» Startseite
» Forum
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Suche
» Regeln
» Wie poste ich richtig?
» Forum-FAQ

Mitglieder
» Liste / Suche
» Wer ist wo online?

Ressourcen
» openbook: Visual C#
» openbook: OO
» Microsoft Docs

Team
» Kontakt
» Übersicht
» Wir über uns

» myCSharp.de Diskussionsforum
Du befindest Dich hier: Community-Index » Diskussionsforum » Entwicklung » Rund um die Programmierung » Anzahl von Vereinen in 10er Gruppen einteilen, bei denen die Fahrtstrecken möglichst kurz sind?
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | Thema zu Favoriten hinzufügen

Antwort erstellen
Zum Ende der Seite springen  

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

 
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
syl syl ist männlich
myCSharp.de-Mitglied

Dabei seit: 07.12.2019
Beiträge: 4
Entwicklungsumgebung: Visual Studio Community 2019


syl ist offline

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

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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
Neuer Beitrag 07.12.2019 20:07 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
MrSparkle MrSparkle ist männlich
myCSharp.de-Team

avatar-2159.gif


Dabei seit: 16.05.2006
Beiträge: 5.398
Herkunft: Leipzig


MrSparkle ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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.
Neuer Beitrag 08.12.2019 17:12 Beiträge des Benutzers | zu Buddylist hinzufügen
chilic
myCSharp.de-Poweruser/ Experte

Dabei seit: 12.02.2010
Beiträge: 2.036


chilic ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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 ;-)

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von chilic am 08.12.2019 17:21.

Neuer Beitrag 08.12.2019 17:20 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
syl syl ist männlich
myCSharp.de-Mitglied

Dabei seit: 07.12.2019
Beiträge: 4
Entwicklungsumgebung: Visual Studio Community 2019

Themenstarter Thema begonnen von syl

syl ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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.
Neuer Beitrag 08.12.2019 17:48 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
MrSparkle MrSparkle ist männlich
myCSharp.de-Team

avatar-2159.gif


Dabei seit: 16.05.2006
Beiträge: 5.398
Herkunft: Leipzig


MrSparkle ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Zitat von syl:
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.

Zitat von chilic:
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.
Neuer Beitrag 08.12.2019 18:52 Beiträge des Benutzers | zu Buddylist hinzufügen
gfoidl gfoidl ist männlich
myCSharp.de-Team

avatar-2894.jpg


Dabei seit: 07.06.2009
Beiträge: 6.653
Entwicklungsumgebung: VS 2019
Herkunft: Waidring


gfoidl ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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ü
Neuer Beitrag 10.12.2019 11:56 Beiträge des Benutzers | zu Buddylist hinzufügen
syl syl ist männlich
myCSharp.de-Mitglied

Dabei seit: 07.12.2019
Beiträge: 4
Entwicklungsumgebung: Visual Studio Community 2019

Themenstarter Thema begonnen von syl

syl ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Zitat von MrSparkle:
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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von syl am 14.12.2019 18:19.

Neuer Beitrag 14.12.2019 18:18 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Baumstruktur | Brettstruktur       | Top 
myCSharp.de | Forum Der Startbeitrag ist älter als 6 Monate.
Der letzte Beitrag ist älter als 6 Monate.
Antwort erstellen


© Copyright 2003-2020 myCSharp.de-Team | Impressum | Datenschutz | Alle Rechte vorbehalten. | Dieses Portal verwendet zum korrekten Betrieb Cookies. 02.07.2020 08:08