Routingoptionen

In diesem Abschnitt werden einige der Optionen für den Routing-Resolver beschrieben.

Suchlimits

Suchlimits beenden den Matherechner nach Erreichen eines bestimmten Limits, z. B. der maximalen Dauer oder der Anzahl der gefundenen Lösungen. Sie können ein Suchlimit über die Suchparameter des Matherechners festlegen. Ein Beispiel finden Sie unter Zeitlimits.

In der folgenden Tabelle werden die gängigsten Suchlimits beschrieben.

Name	Typ	Standard	Beschreibung
solution_limit	int64	kint64max	Beschränke die Anzahl der Lösungen, die während der Suche generiert wurden.
time_limit.seconds	int64	kint64max	Zeitlimit in Sekunden für die Verweildauer in der Suche:
lns_time_limit.seconds	int64	100	Limit in Sekunden auf die Zeit in: der Abschlusssuche für jeden lokalen Suchnachbarn.

Erste Lösungsstrategie

Die erste Lösungsstrategie ist die Methode, mit der der Rechner eine erste Lösung findet. In der folgenden Tabelle sind die Optionen für first_solution_strategy aufgeführt.

Option	Beschreibung
AUTOMATIC	Der Matherechner kann festlegen, welche Strategie gemäß dem zu lösenden Modell verwendet werden soll.
PATH_CHEAPEST_ARC	Verbinden Sie den Knoten von einem „Start“-Knoten aus mit dem Knoten, der das günstigste Routensegment erzeugt. Erweitern Sie anschließend die Route, indem Sie den letzten Knoten hinzufügen, der der Route hinzugefügt wurde.
PATH_MOST_CONSTRAINED_ARC	Ähnlich wie PATH_CHEAPEST_ARC, aber es wird mit einem vergleichsbasierten Selektor bewertet, bei dem der bogenstärkste Bogen zuerst bevorzugt wird. Verwenden Sie die Methode ArcIsMoreConstrainedThanArc(), um dem Routingmodell einen Selektor zuzuweisen.
EVALUATOR_STRATEGY	Ähnlich wie PATH_CHEAPEST_ARC, mit der Ausnahme, dass Lichtbogenkosten mit der Funktion berechnet werden, die an SetFirstSolutionEvaluator() übergeben wird.
SAVINGS	Energiesparalgorithmus (Clarke & Wright) Referenz Clarke, G. und Wright, J.W. "Planung of Vehicles from a Central Depot to a Number of Delivery Points", Operations Research, Vol. 12, 1964, S. 568–581.
SWEEP	Sweep-Algorithmus (Wren & Holliday) Referenz von Anthony Wren und Alan Holliday, Computerplanung von Fahrzeugen von einem oder mehreren Depots zu einer Reihe von Betriebspunkten Operational Research Research Quarterly (1970-1977), Vol. 23, No. 3 (Sep., 1972), S. 333–344.
CHRISTOFIDES	Christofides-Algorithmus (eine Variante des Christtofides-Algorithmus, der eine maximale Übereinstimmung anstatt einer maximalen Übereinstimmung verwendet, die keinen 3/2-Faktor der Näherung für einen Vertriebsmitarbeiter mit Messwerten des Messwerts garantiert). Funktioniert bei generischen Fahrzeugrouting-Modellen, indem eine Route erweitert wird, bis keine Knoten darin eingefügt werden können. Referenz von Nicos Christofides, Worst-Case Analysis of a new heuristic for the Traveling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
ALL_UNPERFORMED	Alle Knoten deaktivieren. Ermittelt eine Lösung nur, wenn Knoten optional sind (ein Element einer Disjunktionseinschränkung mit einem begrenzten Strafkosten).
BEST_INSERTION	Sie können eine Lösung iterativ erstellen, indem Sie den günstigsten Knoten an seiner günstigsten Position einfügen. Die Kosten für das Einfügen hängen von der globalen Kostenfunktion des Routingmodells ab. Ab 2.2012 funktioniert dies nur noch für Modelle mit optionalen Knoten (mit endgültigen Strafkosten).
PARALLEL_CHEAPEST_INSERTION	Sie können eine Lösung iterativ erstellen, indem Sie den kostengünstigsten Knoten an seiner günstigsten Position einfügen. Die Kosten für das Einfügen basieren auf der Arc-Kostenfunktion. Ist schneller als BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION	Erstellen Sie iterativ eine Lösung, indem Sie jeden Knoten an seiner günstigsten Position einfügen. Die Kosten für das Einfügen basieren auf der Bogenbetriebskostenfunktion. Sie unterscheidet sich von PARALLEL_CHEAPEST_INSERTION durch den für den Einfügen ausgewählten Knoten. Hier werden Knoten in ihrer Reihenfolge berücksichtigt. Ist schneller als PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC	Zwei Knoten iterativ verbinden, sodass das kostengünstigste Routensegment erzeugt wird
LOCAL_CHEAPEST_ARC	Wählen Sie den ersten Knoten mit einem ungebundenen Nachfolger aus und verbinden Sie ihn mit dem Knoten, der das kostengünstigste Routensegment erzeugt.
FIRST_UNBOUND_MIN_VALUE	Wählen Sie den ersten Knoten mit einem ungebundenen Nachfolger aus und verbinden Sie ihn mit dem ersten verfügbaren Knoten. Das entspricht der Strategie CHOOSE_FIRST_UNBOUND in Kombination mit ASSIGN_MIN_VALUE (cf.constraint_solver.h).

Status der Suche

Sie können den Status einer Suche mit der Methode status des Routingmodells zurückgeben. So sieht der Python-Code aus, um den Status einer Suche auszugeben:

print("Solver status: ", solver.status())

Dadurch wird eine Ganzzahl mit der folgenden Bedeutung ausgegeben:

Wert	Beschreibung
0	ROUTING_NOT_SOLVED: Das Problem wurde noch nicht gelöst.
1	ROUTING_SUCCESS: Das Problem wurde behoben.
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: Problem wurde nach dem Aufrufen von RoutingModel.Solve() erfolgreich gelöst, es sei denn, eine lokale Optimierung wurde nicht erreicht. Mehr Zeit bedeutet, die Lösung zu verbessern.
3	ROUTING_FAIL: Für das Problem wurde keine Lösung gefunden.
4	ROUTING_FAIL_TIMEOUT: Zeitlimit wurde erreicht, bevor eine Lösung gefunden wird.
5	ROUTING_INVALID: Modell, Modellparameter oder Flags sind ungültig.
6	ROUTING_INFEASIBLE: Das Problem ist nicht umsetzbar.

Lokale Suchoptionen

In der folgenden Tabelle sind die Optionen für lokale Suchstrategien (auch Metaphysik genannt) aufgeführt. Beispiele für das Festlegen dieser Optionen finden Sie unter Suchstrategie ändern.

Option	Beschreibung
AUTOMATIC	Der Matherechner kann das Metaheurismus auswählen.
GREEDY_DESCENT	Akzeptiert Verbesserungen (Kostenreduzierung) für lokale Nachbarn, bis ein lokaler Mindestbetrag erreicht wird.
GUIDED_LOCAL_SEARCH	Mithilfe der geführten lokalen Suche entkommen lokale Minima. (siehe Geführte lokale Suche) In der Regel ist dies die effektivste Metaheurismus für die Routenführung.
SIMULATED_ANNEALING	Zum Simulieren von lokalen Minima wird die simulierte Beleuchtung verwendet (siehe Simulierte Abfolge).
TABU_SEARCH	Mithilfe der Tabu-Suche kann eine lokale Minima maskiert werden (siehe Tabu-Suche).
GENERIC_TABU_SEARCH	Verwendet Tabu-Suche zum Zielwert der Lösung, um lokale Minima zu maskieren.

Vermehrung der Vermehrung

Name	Typ	Standard	Beschreibung
use_full_propagation	bool	true	Verwenden Sie Einschränkungen mit vollständiger Weitergabe im Routingmodell statt nur einfache Weitergabe. Eine vollständige Weitergabe ist nur erforderlich, wenn die Tiefensuche verwendet wird oder bei Modellen, die eine starke Weiterverteilung erfordern, um den Wert von sekundären Variablen zu vervollständigen. Durch das Ändern dieser Einstellung auf „true“ wird die Suche in den meisten Fällen verlangsamt und der Arbeitsspeicherverbrauch in allen Fällen erhöht.