Zuordnungsproblem für mehrere Tage

Ich habe ein Problem, das auf ein Zuordnungsproblem reduziert werden kann. (In einer früheren Frage habe ich herausgefunden, wie das geht.)

Das heißt, wir haben eine Menge von Agenten und eine Menge von Aufgaben sowie eine Kostenfunktion . Wir müssen einen Auftrag finden, damit die Gesamtkosten minimal sind.$A$$T$$c(i,j)$

Der ungarische Algorithmus kann in mindestens eine optimale Lösung finden . Was für mich gut klingt.$O(n^4)$

Mein neues Problem ist: Es gibt eine bestimmte Anzahl von Tagen. Ich muss das Zuweisungsproblem für jeden Tag lösen, damit jede Aufgabe jeden Tag erledigt wird und kein Agent dieselbe Aufgabe zweimal erledigt .

Was ich versucht habe: Wir könnten den ungarischen Algorithmus für jeden Tag separat ausführen und die Anzahl der möglichen Kombinationen basierend auf dem Ergebnis des vorherigen Tages begrenzen. Dies würde uns jedoch in späteren Tagen in Schwierigkeiten bringen, wo es höchstwahrscheinlich unmöglich sein wird, eine praktikable Lösung zu finden.

Eine andere Idee ist es, die lokale Suche irgendwie zu integrieren, um Entscheidungen zu ändern, die am Vortag getroffen wurden. Aber ich denke, wir können uns nicht darauf verlassen.

Die Problemfälle, denen ich mich stellen muss, liegen irgendwo in der Nähe von . Die Kostenmatrix hat viele gleiche Werte (zB meistens 1 oder unendlich, nur einige 2 oder 3). Während des ungarischen Algorithmus gibt es also viel Platz, um verschiedene optimale Lösungen für einen einzelnen Tag zu erstellen.$|A| = |T| = 500$$C(i,j)$

Ich würde mich freuen, einige Ideen oder Ratschläge zu hören, wie man eine gute Lösung für das Problem findet. Danke im Voraus.

In der Polynomzeit gibt es einen Weg dorthin. Ich skizziere den Algorithmus (in umgekehrter Reihenfolge ... mache zuerst Schritt 2 und Schritt 1 Sekunde).

1. Wenn wir eine Menge von Agenten-Aufgaben-Paaren so dass jede Aufgabe in genau Paaren ist, jeder Agent in genau Paaren und kein Paar mehr als einmal erscheint, dann können wir Zuordnungen finden, die decken zusammen diese Agent-Task-Paare ab. Dazu verwenden wir wiederholt einen maximalen zweigliedrigen Übereinstimmungsalgorithmus, um eine perfekte Übereinstimmung im entsprechenden zweigliedrigen Diagramm zu finden, und entfernen diese Zuordnung aus dem Diagramm. Halls Heiratsatz garantiert, dass wir dies tun können.$nk$$(i,j)$$k$$k$$k$$nk$

2. Wir können den minimalen Kostensatz von Agent-Task-Paaren wie in Schritt 1 unter Verwendung des Min-Cost-Flows finden. Stellen Sie sich ein Netzwerk mit einer Quelle , einer Senke und Knoten für jeden der Agenten und jede der Aufgaben vor. Verbinden Sie die Quelle mit jedem Agenten mit einer Kapazitätskante und kosten . Verbinden Sie jede Aufgabe mit einer Kante der Kapazität mit der Spüle und kosten Sie . Verbinden Sie nun den Agenten mit der Aufgabe mit einer Kante der Kapazität und den Kosten$nk$$s$$t$$k$$0$$k$$0$$i$$j$$1$$c(i,j)$. Der Mindestkostenfluss in diesem Netzwerk ist garantiert ganzheitlich (da alle Kapazitäten ganzzahlig sind und es einen Satz gibt, der besagt, dass dies einen optimalen integralen Mindestkostenfluss impliziert), also der Ablauf an jedem Rand der Agentenaufgabe ist oder . Die Kanten mit Fluss bilden die Paarmenge in Schritt 1.$0$$1$$(i,j)$$1$

Es gibt viele Algorithmen, die den Min-Cost-Flow lösen können . Es ist ein Sonderfall der linearen Programmierung. Für Ihr Größenproblem sollte der von mir skizzierte Algorithmus nicht nur polynomisch sein, sondern auch praktisch.