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.
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: