Optimierung Transport

Handelsreisender

Da wir bei Eressea nicht mit wenigen sondern mit sehr vielen Einheiten hantieren, stellt sich die Problematik des Handelsreisenden weniger, da Transporte oft nicht mehrere Regionen im Kreis anfahren, sondern Bedarfe eher mit vielen einzelnen Transporten parallel bearbeitet werden.

Optimale Beladung

Für die Beladung eines Transportes mit Waren liegt es nahe das Rucksackproblem anzuwenden. Allerdings läuft man in Eressea dabei schnell in die Falle zu viele gleichartige Gegenstände verladen zu wollen. Optimierungen des Rucksackproblems kommen damit kaum klar.

Ein einfaches Beispiel:

Zu transportieren sind 10 Steine (je 60 GE) und 100 Juwelen (je 1 GE). Es steht jedoch nur 500GE Kapazität zur Verfügung. Ein Stein wird mit einem Wert von 1200 bemessen, ein Juwel mit einem Wert von 50. Da die Juwelen mehr Wert pro GE bieten (50 je GE) laden wir also zuerst alle Juwelen auf:

Wert   = 100 * 50 = 5000 
Ladung = 100 * 1 GE = 100 GE
frei   = 400 GE

Bei 400 GE gelingt es uns also noch 6 Steine aufzuladen, 40 GE bleiben frei.

Wert   = 5000 + 6 * 1200 = 12200
Ladung = 100 GE + 6 * 60 GE = 460 GE
frei   = 40 GE

Versuchen wir es also mit den Steinen zuerst: 8 Steine, dann bleibt noch Platz für 20 Juwelen:

Wert   = 20 * 50 + 8 * 1200 = 10600

Das war offenbar nichts. Aber geht es doch noch irgendwie besser? Ja, 7 Steine und 80 Juwelen scheinen offenbar die Kapazität besser auszunutzen:

Wert   = 80 * 50 + 7 * 1200 = 12400

Der Weg dahin führt z.b. über greedy suche, also das durchsuchen sämtlicher Zustände. In dem Fall also 0 bis 8 Steine und 0 bis 100 Juwelen (manchmal weniger) macht also rund 900 Zustände die zu prüfen wären. Wenn man sich jetzt noch eine 3. oder 4. Ware vorstellt wird schnell klar, so kommen wir nicht zum Ergebnis.

Normalerweise führt hier der schnelle Weg zum Ziel über sogenannte Pareto-optimale Zwischenzustände. Was solche Zwischenzustände sind lässt sich leichter anders rum erklären. Zustände die bei gleicher Beladung weniger Wert sind als ein anderer Zwischenzustand sind nicht Pareto-optimal. Diese braucht man nicht weiter zu verfolgen, da offenbar immer wieder nur nicht Pareto-optimale Zustände erreicht werden können.

Vergleicht man also beispielsweise den Zustand "60 Juwelen" mit "1 Stein" so zeigt sich, das 60 Juwelen offenbar bei gleicher Beladung weit mehr Wert sind. Es lohnt also nicht "1 Stein" weiter zu expandieren. Genau genommen kommt man zu dieser Feststellung bereits wenn man 24 Juwelen expandiert hat.

Problematisch ist diese Art der Optimumsberechnung nun, da offenbar jede Anzahl von Juwelen zwischen 0 und 100 pareto-optimal ist. Schlimmer noch auch jede Kombination aus 1-6 Steinen mit 77 bis 100 Juwelen und 7 Steinen mit 77 bis 80 Juwelen ist pareto-optimal. D.h. trotz Optimierung müssen wir 100 + 6 * 24 + 4 = 248 Zustände von ca. 900 Zuständen expandieren, bis wir uns der gefundenen Lösung sicher sein können - kein schönes Ergebnis.

Allerdings bietet sich eine andere Optimierung an. Wir können die verwendeten Transportmengen einschränken. Da sich Juwelen so lange lohnen wie sie zusammen eine ganz Anzahl Steine ergeben, liegt die Juwelenzahl zwischen 60 und 100. Die Juwelen können jedoch nie die komplette Kapazität belegen, weshalb mindestens 6 Steine und maximal 8 mitgenommen werden können. Damit reduziert sich die Suche auf 41*3 oder mit Pareto-optimalen Zwischenzuständen auf 41 + 24 + 4 = 69 Zustände.

Achtung: Priorisiert man die Waren, statt sie zu bewerten, dann lässt sich diese Art der Packung eher nicht anwenden. Dann gilt: Höchste Priorität zuerst ...

Multiwegfindung

Bei der Transportplanung kann es aber durchaus vorkommen, dass ein Transport bereits etwas Ladung und dementsprechend eine Zielregion hat. Es steht aber auf dem Transport noch Kapazität bereit, die durch andere Waren belegt werden könnten. Einfache Möglichkeiten liegen nun darin nur Waren mitzugeben, die in den Zwischenpunkten der Route gebraucht werden. Fortgeschrittene Techniken laden Waren auf, die dadurch dem Ziel ein Stück näher kommen.

Möglich scheint mir aber auch eine Anpassung der Route, dahingehend, dass bei gleicher Dauer zum ersten Ziel eine Route gesucht wird, die gleichzeitig möglichst nah oder sogar über die Region des 2. Zieles führt. Ebenso denkbar ist die Optimierung der Route, das diese über "Umschlagplätze" läuft, um sicherzustellen, dass die Waren für das 2. Ziel dann auch einen Transport in der Gabelregion finden.

Wie also könnte eine solche Multiwegfindung laufen? Die Runden bis zur Ankunft bei Ziel 1 sind bekannt. Es kommen also nur Routen in Frage, die nicht länger dauern. Das erfährt man jedoch erst wenn eine Route gefunden wurde. Die minimale Entfernung zum Ziel 2 ist also zweites Kriterium bei der Routenbewertung und lässt die Routenberechnung ein wenig mehr "greedy" werden, da nun alle Regionen die im Kriterium 1 den gleichen Wert ergeben auf den 2. Wert getestet werden müssen. Glücklicherweise liefert auch hier die Schätzfunktion gute Dienste.

gleichwertige Ziele

Sind mehrere Ziele gleichwertig, konkurrieren diese natürlich ab einem bestimmten Punkt um die weitere Route. Bis dahin kann man die Route prima auf das Minimum aus beiden Routen optimieren, d.h. man fährt zur näheren Region, und lädt die Waren für die andere Region ab, wenn man möglichst nah dran ist.

Fügt man jedoch mehr und mehr Ziele hinzu, so wird aus dem Transport tatsächlich ein lokaler "Handelsreisender". Ob und wann es sich lohnt hier tatsächlich eine kleine Rundreise zu machen, habe ich noch nicht näher betrachtet. Sicher gibt es aber solche Grenze.

Umschlagplätze

Die Multiwegfindung kann man sich aber auch wesentlich vereinfachen. Definiert man ausreichend Umschlagplätze, so kann man die Transporte anweisen bei Routen über einer Woche als Zwischenpunkte immer Umschlagplätze anzulaufen, oder dies zumindest dann zu tun, wenn eine Kapazitätsgrenze unterschritten ist, oder der Umschlagplatz keinen Umweg bedeutet.

Das Transportsystem der ehemaligen EWG hatte sich diesem Umstand implizit zueigen gemacht, indem es hierarchisch organisiert war. Umschlagplätze sind dort Regionen die untergeordnete Regionen haben. Die Hierarchie bedeutet allerdings oft Umwege. Ob solch ein System gut funktioniert, hängt dann auch von der Topologie der Insel ab. Vor allem Inseln die Ringe bilden, eignen sich wenig für ein streng hierarchisches Transportsystem.