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.

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.