Verteilungs-/Vergabe-Algorithmus mit abhängigen Score-Werten

Buzzwave

Neues Mitglied
Ich zerbreche mir gerade den Kopf über eine möglichst elegante d.h. möglichst wenig rechenintensive Lösung für ein Vergabeproblem bei dem es Abhängigkeiten zu den zuvor vergebenen Plätzen gibt. Die Problemstellung ist recht spannend und ich fürchte, es gibt auch einfache keine bessere Lösung als mit vielen Neuberechnungen zu leben. Aber vielleicht hat ja noch jemand Spaß daran mit mir zu tüfteln und eine geniale Idee?

Hier die Problemstellung:
Es gibt eine Reihe von Versorgern v_1 bis v_n mit den Kapazitäten vc_1 bis vc_n
Es gibt eine Reihe von Nachfragern n_1 bis n_k mit bekannten Distanzen zu den Versorgern n_i.dist_v(j) und einem Score nscr_1 bis nscr_k
Es ist davon auszugehen, dass jeder Nachfrager nur eine Einheit von den Versorgern nachfragt. Trotzdem reicht die gesamte Kapazität nicht für alle Nachfrager.

Um zu entscheiden, wer zuerst bedient wird bzw. wer leer ausgeht, gibt es den Score-Wert zw. 1,0 und 10,0. In den Score-Wert fließt die Entfernung zum nächsten Versorger mit freier Kapazität mit ein. D.h. wenn man in einem Zuordnungsverfahren Versorger auslastet, kann sich der Score-Wert von noch nicht zugeordneten Nachfragern verändern. Die Neuberechnung des Scorewerts für einen einzelnen Nachfrager ist billig. Allerdings gibt es viele zehn- oder hunderttausend Nachfrager und die Neuberechnung aller Scores ist teuer.

Nennen wir das bis hierher mal (A). Und jetzt noch zwei Varianten:

(B) Die Zuordnung erfolgt nicht nach Entfernung, sondern ein Nachfrager hat 1-7 präferierte Versorger angegeben (mit festgelegter Reihenfolge).

(C) Wenn man die Entfernung aus dem Scorewert herauszieht und stattdessen die Summe des Quotienten Score/Distance über alle Nachfrager die versorgt werden maximiert, erhält man dadurch eine elegantere Lösung mit vergleichbar "gerechter" Verteilung? Als gerecht soll die Berücksichtigung des Score-Werts bezeichnet werden, wobei dieser abnimmt, je weiter der nächste Versorger mit freier Kapazität entfernt ist.


Meine Gedanken zu (A) sehen vor, dass alle Nachfrager in absteigender Reihenfolge ihres Scores auf Versorger-Kapazitäten verteilt werden. Immer wenn ein Versorger ausgelastet ist, muss man in den sauren Apfel beißen und die restlichen neu bewerten und sortieren (teuer).
(B) stellt dabei nur eine kleine Erleichterung dar. Der Scorewert wäre nicht abhängig vom nächsten freien Versorger, sondern vom präferierten. Es müssten nur die Nachfrager neu bewertet werden, deren nächste Präferenz der gerade ausgelastete Versorger ist.
(C) hat in meinen Augen das größte Potential. Die Scores müssten nicht neu bewertet werden. Lösungen für die Problematik findet man sicherlich in der Literatur (Operations Research, Transportproblem,...)


Ein umgekehrtes Vorgehen ist vermutlich schlechter. D.h. für jeden Versorger sucht man die x nächsten Nachfrager und vergibt nach Score i.V.m. Distance. Macht wohl vor allem keinen Sinn, weil ein Nachfragern in der Nähe von mehreren Versorgern sein kann.

Mich interessiert nicht eine ausprogrammierter Code, sondern wie man hier am schlausten eine Algorithmus stricken würde.
Ich freue mich über jeden intelligenten Beitrag zum Thema.
 
Zuletzt bearbeitet:

strußi

Top Contributor
du kannst ja mal anfangen dir Modells mit getter/setter-Methoden zu erstellen

"Versorger"
mit den paramter
-entfernung
lagerbestand
...

und
"Nachfrager"
mit Parameter
Lagerbestand
score
bevorzugte abnehmer
...


und die Objects kannst du dann in eine/mehrere ArrayLists speichern
du frägst dann die Nachfrager ab, wie der status ist.

Grüße
 

Buzzwave

Neues Mitglied
Nein, ich programmiere das nicht. Wenn überhaupt, werde ich das auch nicht selbst coden, sondern nur die Vorgaben machen.
Mich interessieren auch nicht die Klassen, Getter und Setter etc. Wie man das handwerklich programmieren würde, ist auch klar. Ich bin nur gerade an Vorüberlegungen und die Frage stellt sich nach dem besten, elegantesten Rechenweg. Ich vermute der führt über einen Scorewert ohne Entfernung und den Quotienten aus (C) und entsprechen das Maximierungsproblem.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Tarrew Threading - Unregelmäßige Lock-Vergabe Allgemeine Java-Themen 0
schegga_B AES-Algorithmus in javax.crypto Allgemeine Java-Themen 3
M Laufzeit des Prim Algorithmus Allgemeine Java-Themen 3
O Newton Algorithmus Java Allgemeine Java-Themen 1
CptK Backpropagation Algorithmus Allgemeine Java-Themen 6
N Google Authenticator Algorithmus (SHA1) Allgemeine Java-Themen 1
gotzi242 Schatzsuche mithilfe eines O(log n) Algorithmus Allgemeine Java-Themen 2
Zrebna Quicksort-Algorithmus - zufälliges Pivot wählen Allgemeine Java-Themen 6
L Klassen Algorithmus für das folgende Problem entwickeln? Allgemeine Java-Themen 30
B Algorithmus Warteschlange Ringpuffer wirklich fehlerfrei Allgemeine Java-Themen 8
M Probleme mit Negamax-Algorithmus Allgemeine Java-Themen 29
F Q - Learning Algorithmus Bug Allgemeine Java-Themen 4
M Salesman Problem - Bruteforce Algorithmus Allgemeine Java-Themen 23
M Minmax Algorithmus Verständnisproblem Allgemeine Java-Themen 2
H Rundreise frage (Algorithmus) Allgemeine Java-Themen 18
F KMP-Algorithmus Allgemeine Java-Themen 9
S Algorithmus welcher True-Werte in einem Array findet und auswertet. Allgemeine Java-Themen 5
U Methoden Algorithmus MergeSort String [ ] array sortieren programmieren Allgemeine Java-Themen 17
P MinMax Algorithmus Allgemeine Java-Themen 0
J Abhängigkeit zwischen Rechenzeit und Speicherbedarf in einen Algorithmus Allgemeine Java-Themen 7
K Djikstra-Algorithmus Allgemeine Java-Themen 1
T Minimax/Alphabeta Algorithmus hängt sich auf (?) Allgemeine Java-Themen 2
M Algorithmus zum Zahlen einteilen Allgemeine Java-Themen 8
O Best Practice Hilfe bei Algorithmus gesucht Allgemeine Java-Themen 10
S Algorithmus um Objekte auf einer Flaeche mit gleichem Abstand anzuordnen..? Allgemeine Java-Themen 20
S Rucksackproblem und genetischer Algorithmus Allgemeine Java-Themen 9
L Abbruch des Algorithmus Allgemeine Java-Themen 8
D Input/Output Ausgleichen chemischer Reaktionsgleichungen mit dem Gauß-Algorithmus Allgemeine Java-Themen 2
Messoras A*-Algorithmus integrieren Allgemeine Java-Themen 3
S Buchscan 3D Dewarp Algorithmus - Ansätze Allgemeine Java-Themen 1
Androbin "Shunting Yard"-Algorithmus Allgemeine Java-Themen 6
B Algorithmus - Project Euler Problem 18 Allgemeine Java-Themen 2
N Algorithmus zum bewerten von mathematischen Funktionen Allgemeine Java-Themen 11
O Algorithmus Optimierung Allgemeine Java-Themen 3
Joew0815 Algorithmus - Zahlenfolge in 4 ähnliche Teile aufteilen Allgemeine Java-Themen 0
O Tag Cloud Algorithmus Idee gesucht Allgemeine Java-Themen 2
A Implementierung eines Algorithmus (Farthest Insertion zur Lösung des TSP) in O(n²) Allgemeine Java-Themen 2
C Eclipse Probleme bei selbst erstelltem Algorithmus Allgemeine Java-Themen 2
H Graph-Algorithmus gesucht Allgemeine Java-Themen 21
N Algorithmus durch Workflow Allgemeine Java-Themen 7
M tree-based diff Algorithmus (Code-Vergleiche) Allgemeine Java-Themen 3
S Uhrzeit Algorithmus sale Allgemeine Java-Themen 11
N A*-Algorithmus Allgemeine Java-Themen 5
A Suche Algorithmus zum Erstellen eines planaren Graphen Allgemeine Java-Themen 5
F Methoden Algorithmus zur Gegnerfindung (Turnier) Allgemeine Java-Themen 9
T Algorithmus Graph Allgemeine Java-Themen 10
J Algorithmus gesucht (Stringtransformation) Allgemeine Java-Themen 4
B Algorithmus Krankenhausbelegung Allgemeine Java-Themen 17
S Algorithmus von Dijkstra Allgemeine Java-Themen 2
alex_fairytail OOP Banknoten Algorithmus Teil 2 Allgemeine Java-Themen 13
2 ArrayList aktualisieren Algorithmus Allgemeine Java-Themen 11
alex_fairytail Methoden Banknoten Algorithmus Allgemeine Java-Themen 10
R Codehinweise: Algorithmus Größenvergleich von n Zahlen Allgemeine Java-Themen 5
SuperSeppel13 WTF?! Algorithmus-Geschwindigkeitstest Allgemeine Java-Themen 2
L Algorithmus für kürzesten Weg mit Wegpunkten Allgemeine Java-Themen 21
C Algorithmus Problem in Minesweeper Allgemeine Java-Themen 5
S Algorithmus um Labyrinth zu erzeugen Allgemeine Java-Themen 6
V Problem mit A* Pathfinder-Algorithmus Allgemeine Java-Themen 2
S Algorithmus um nächst folgende Primzahl zu berechnen Allgemeine Java-Themen 7
S Algorithmus Problem. Rechtecke effizient auf Spielfeld anordnen. Allgemeine Java-Themen 7
C Algorithmus-Hilfe Allgemeine Java-Themen 20
J Algorithmus Längenkombinationen? Allgemeine Java-Themen 7
M Kombinationen über rekursiven Algorithmus berechnen? Allgemeine Java-Themen 10
L Algorithmus für Poker-Hände Allgemeine Java-Themen 7
chik 2 return werte für Greedy-Algorithmus (gelöst) Allgemeine Java-Themen 3
D Abstruse Probleme mit eigenem replace Algorithmus Allgemeine Java-Themen 11
P RC4 Algorithmus Allgemeine Java-Themen 3
D RSA Verfahren - Erweiterter Euklidischer Algorithmus Allgemeine Java-Themen 4
C IBAN und Bic Validieren (Algorithmus) Allgemeine Java-Themen 10
P Problem mit A*-Algorithmus Allgemeine Java-Themen 12
M Wörter Algorithmus Allgemeine Java-Themen 7
M Algorithmus für automatische Zeilenumbrüche Allgemeine Java-Themen 12
K Postleitzahlen Algorithmus Allgemeine Java-Themen 12
G Problem mit Algorithmus Allgemeine Java-Themen 3
T Hilfe bei einem Algorithmus Allgemeine Java-Themen 2
S Stemming-Algorithmus gesucht (z.B. Porter) Allgemeine Java-Themen 2
RoliMG präfix zu infix algorithmus Allgemeine Java-Themen 6
Z A*-Algorithmus - Probleme mit offener/geschlossener Liste Allgemeine Java-Themen 7
S Javaimplementierung des MD5 Algorithmus Allgemeine Java-Themen 2
E Container-Pack-Algorithmus Allgemeine Java-Themen 4
G k nearest neighbor algorithmus Allgemeine Java-Themen 7
C HASH Algorithmus 2 Strings ergeben das Selbe. Allgemeine Java-Themen 2
P Page Rank Algorithmus implementieren Allgemeine Java-Themen 7
T Problem RSA-Algorithmus in Java? Allgemeine Java-Themen 2
minzel Hash-Algorithmus Allgemeine Java-Themen 9
Y komprimierung mittels Huffman-Algorithmus, bit-shifting. Allgemeine Java-Themen 2
K Algorithmus Allgemeine Java-Themen 10
C Algorithmus für Array Allgemeine Java-Themen 9
I Verschlüsselung mit Pwd. - User soll Algorithmus wählen Allgemeine Java-Themen 4
J fällt euch ein Algorithmus ein? Allgemeine Java-Themen 4
S Algorithmus für Sudoku Allgemeine Java-Themen 17
N Euklidischer Algorithmus in Java und keine Terminierung. Allgemeine Java-Themen 7
F Algorithmus für Sortierung gesucht Allgemeine Java-Themen 15
T Algorithmus verbessern Allgemeine Java-Themen 10
U Suche Algorithmus zur bestimmung des längsten Wegs Allgemeine Java-Themen 3
U Ford-Fulkerson Algorithmus gesucht Allgemeine Java-Themen 1
U Dijkstra Algorithmus gesucht Allgemeine Java-Themen 4
D Algorithmus für die Erkennung fehlerhafter Eingaben Allgemeine Java-Themen 4
I hash-algorithmus Allgemeine Java-Themen 9

Ähnliche Java Themen

Neue Themen


Oben