Nehmen wir an, ich habe N Taxis und N Kunden, die darauf warten, von den Taxis abgeholt zu werden. Die Ausgangspositionen von Kunden und Taxis sind zufällig / willkürlich.
Nun möchte ich jedem Taxi genau einen Kunden zuordnen.
Die Kunden sind alle stationär, und die Taxis bewegen sich alle mit identischer Geschwindigkeit. Nehmen wir zur Vereinfachung an, dass es keine Hindernisse gibt, und die Taxis können sich in geraden Linien zu den zugewiesenen Kunden bewegen.
Ich möchte jetzt die Zeit minimieren, bis der letzte Kunde sein Taxi betritt.
Gibt es einen Standardalgorithmus, um das zu lösen? Ich habe Zehntausende von Taxis / Kunden. Lösung muss nicht optimal sein, nur "gut".
Das Problem kann fast als das Standard "Zuweisungsproblem" modelliert werden, das mit Hilfe des ungarischen Algorithmus (Kuhn- Munkres-Algorithmus oder Munkres-Zuweisungsalgorithmus). Ich möchte jedoch die Kosten für die kostenintensivste Aufgabe minimieren und nicht die Summe der Kosten der Aufgaben minimieren.
Da du den ungarischen Algorithmus erwähnt hast, denke ich, dass du etwas anderes als die euklidische Entfernung verwenden kannst und dann den ungarischen Algorithmus darauf anwenden kannst. Zum Beispiel, anstatt
zu verwendend = sqrt ((x0 - x1) ^ 2 + (y1 - y0) ^ 2)
verwenden
d = ((x0 - x1) ^ 2 + (y1 - y0) ^ 2) ^ 10
das könnte dazu führen, dass der Algorithmus große Zahlen stark bestraft, was die Länge der maximalen Entfernung einschränken könnte.
EDIT: Dieses Papier "Geometrie hilft bei Engpass-Matching und verwandten Probleme "enthält möglicherweise einen besseren Algorithmus. Ich bin jedoch immer noch dabei, es zu lesen.
Ich bin mir nicht sicher, ob der ungarische Algorithmus für Ihr Problem hier funktioniert. Laut dem Link läuft es in n ^ 3 mal. Das Einstecken von 25.000 als n würde 25.000 ^ 3 = 15.625.000.000.000 ergeben. Das könnte eine Weile dauern.
Da die Lösung nicht optimal sein muss, sollten Sie simuliertes Glühen oder möglicherweise ein genetischer Algorithmus stattdessen. Beide sollten viel schneller sein und dennoch nahezu optimale Lösungen liefern.
Bei Verwendung eines genetischen Algorithmus kann die Fitnessfunktion so gestaltet werden, dass die längste Zeitspanne minimiert wird, die eine Person warten müsste. Aber Sie müssen vorsichtig sein, denn wenn das das einzige Kriterium ist, dann wird die Lösung nicht so gut funktionieren, wenn nur ein Taxi dem am weitesten entfernten Passagier am nächsten ist. Die Fitnessfunktion müsste also auch die anderen Wartezeiten berücksichtigen. Eine Idee, um dies zu lösen, wäre es, das Modell iterativ zu betreiben und den längsten Führerhausausschlag (sowohl Kabine als auch Person) nach jeder Iteration zu entfernen. Aber das für alle 10.000+ Fahrerhäuser / Leute zu tun, könnte zeitaufwändig sein.
Ich glaube nicht, dass ein Taxifahrer oder Manager die Wartezeit für den letzten Kunden in seinem Taxi minimieren würde, um die Summe der Wartezeiten für alle Fahrerhäuser zu minimieren - einfach weil sie insgesamt mehr Geld machen, wenn sie die Summe minimieren der Wartezeiten. Zumindest würde Louie DePalma das nie tun ... Also, ich vermute, dass das wirkliche Problem, das Sie haben, wenig oder nichts mit Taxis zu tun hat ...
Ein "guter" Algorithmus, der Ihr Problem lösen könnte, ist ein Gieriger Algorithmus . Da Taxis und Menschen eine Position haben, können diese Positionen mit einem "zentralen" Punkt in Verbindung gebracht werden. Sortiere die Taxis und die Leute, die abgeholt werden müssen (in Bezug auf das "Zentrum"). Dann beginnen Sie mit der Zuweisung von Taxis, um Personen in Reihenfolge abzuholen. Diese gierige Regel wird sicherstellen, dass Taxis, die dem Zentrum am nächsten sind, die am nächsten zum Zentrum liegenden Personen abholen und die am weitesten entfernten Taxis die am weitesten entfernten Personen abholen.
Ein besserer Weg wäre vielleicht Dynamic Programming , aber ich bin mir nicht sicher und habe auch keine Zeit zu investieren. Ein gutes Tutorial zur dynamischen Programmierung finden Sie hier
Für eine optimale Lösung: Konstruieren Sie einen gewichteten zweiteiligen Graphen mit einem Eckpunkt für jedes Taxi und Kunden und eine Kante von jedem Taxi zu jedem Kunden, dessen Gewicht die Reisezeit ist. Scannen Sie die Kanten in der Reihenfolge des nicht abnehmenden Gewichts, wobei Sie einen maximalen Abgleich des Untergraphen beibehalten, der die bisher gescannten Kanten enthält. Stoppen Sie, wenn der Abgleich perfekt ist.
Tags und Links algorithm combinatorics