Excel-Formel zur Optimierung einer Route, bei der jede Zeile eine andere „Station“ darstellt, die unterschiedliche Aufgaben ausführen kann

Question

Ich war mir nicht sicher, wie ich diese Frage formulieren sollte.

Hier ist ein minimales Beispiel:

• Jane kann A, B, D machen. Sie ist 1 km entfernt.
• Jack kann B, D, F machen. Er ist 1,5 km entfernt.
• Marschall kann E, F, A machen. Er ist 20 km entfernt.
• Polly kann E, D, C machen. Sie ist 10 km entfernt.
• James kann C, F, B machen. Er ist 15 km entfernt.

Das Blatt enthält Zeilen für jede Person und Spalten für jede Aktion, AF.

Ich möchte herausfinden, zu welcher Personenkombination ich gehen muss, um A, C, F mit der Mindestanzahl der besuchten Personen abzuschließen. Wenn zwei Kombinationen gültig sind, möchte ich die mit dem geringsten Abstand.

(Die Lösung für das oben Gesagte ist also Jane und James)

In meiner ersten Zeile habe ich Kontrollkästchen für jede Sache: A, B, C, D, E, F. Ich habe A, C, F ausgewählt.

Welche Formel würde ich verwenden, um die Personen hervorzuheben oder farblich zu kennzeichnen, die ich besuchen sollte? Wenn dies nicht in Excel möglich ist, wie würde ein Algorithmus zur Lösung dieses Problems heißen, damit ich ihn mit einer Programmiersprache implementieren kann?

Answer 1

Es ist fertig!

Konzept

Rohe Gewalt. Berechnen Sie die Streckenentfernung für jede zu besuchende Personenkombination. Ignorieren Sie die Kombinationen, die nicht alle erforderlichen Aufgaben (AF) bieten. Wählen Sie die Route mit der niedrigsten Routenentfernung.

Implementierung

Die Idee ist, eine binäre Darstellung zu verwenden, um die erforderliche Mathematik zu reduzieren. Nehmen wir an, jeder Person wird 1 Bit in einer Ganzzahl zugewiesen, z. B. 1001 bedeutet Besuchsperson 1 und Person 4. Wenn wir also 8 Personen haben, müssen wir 2 ^ 8-1 = 255 Kombinationen von Personen besuchen. Wir werden Kombinationen in Zeilen mit der Nummer 1..255 erstellen.

Jetzt machen wir dasselbe für die zugewiesenen Aufgaben jeder Person. Aufgabe A ist Bit 1, B ist Bit 2 ... usw. Wenn also Person 010 Aufgaben mit einer Aufgabenmaske (TM) von 0101 anbietet, bietet Person 2 A und C und Person 001 mit TM 1000 nur D an.

Wenn wir Personen 011 (001 UND 010) besuchen möchten, sind die kombinierten Aufgaben angeboten

=BITOR("TM for 001", "TM for 010") which will result in TM 1101 (tasks A, C, D)

Die kombinierten Aufgaben, die für alle angeboten werden, sind

=BITOR("TM for 001", BITOR("TM for 010", BITOR("TM for 100",... "TM for 10000000"))))))))

Um zu sagen, welche Aufgaben eine zufällige Kombination von Personen x bietet, müssen wir nur die relevanten TMs zusammenbeißen:

=BITOR("TM for 001" * x0, BITOR("TM for 010" * x1, BITOR("TM for 100" * x2,... "TM for 10000000" * x7))))))))

wobei xi das i-te Bit in x ist

=BITAND(1,BITRSHIFT(x,i))

Ebenso zur Ermittlung der Gesamtentfernung für Personenkombination / Route x

"Person 1 distance" * x0 + "Person 2 distance" * x1 +... "Person 8 distance" * x7

Um nun festzustellen, ob für Personen x mit TM y alle erforderlichen Aufgaben z ausgeführt werden können (dh eine gültige Route):

=IF(BITAND(y,z) = z, "All tasks offered by x", "All tasks cannot be done")

And the distance for valid routes only

=IF(BITAND(y,z) = z, *distance calc above*,"") so invalid routes are blank ""

Berechnen Sie dies nun für jede mögliche Kombination, z. B. (1..255), und suchen Sie die minimale gültige Routenentfernung mit MIN (...) . Suchen Sie dann die beste Route x mit MATCH (MIN (...), Spalte Routenentfernungen , 0) die dieser minimalen Routenentfernung entspricht. Teilen Sie x in die Bits x0 .. x7 auf und verwenden Sie die bedingte Formatierung, um jede Person auf der besten Route hervorzuheben.