Opzioni di routing

In questa sezione vengono descritte alcune opzioni del risolutore di percorsi.

Limiti di ricerca

I limiti di ricerca determinano una soluzione il risolutore dopo aver raggiunto un limite specifico, ad esempio la durata massima o il numero di soluzioni trovate. Puoi impostare un limite di ricerca tramite i parametri di ricerca del risolutore. Per un esempio, consulta Limiti di tempo.

La tabella seguente descrive i limiti di ricerca più comuni.

Nome	Tipo	Predefinito	Descrizione
solution_limit	int64	kint64max	Limita al numero di soluzioni generate durante la ricerca.
time_limit.seconds	int64	kint64max	Limite in secondi per il tempo trascorso: nella ricerca.
lns_time_limit.seconds	int64	100	Limite in secondi al tempo trascorso su: la ricerca di completamento per ogni vicino ricercatore locale.

Strategia per la prima soluzione

La prima strategia per le soluzioni è il metodo utilizzato dal risolutore per trovare una soluzione iniziale. La seguente tabella elenca le opzioni per first_solution_strategy.

Opzione	Descrizione
AUTOMATIC	Consente al risolutore di rilevare la strategia da utilizzare in base al modello risolto.
PATH_CHEAPEST_ARC	Partendo da un nodo di inizio route, collegalo al nodo che produce il segmento di route più economico, quindi estendi la route eseguendo l'iterazione sull'ultimo nodo aggiunto alla route.
PATH_MOST_CONSTRAINED_ARC	Analogamente a PATH_CHEAPEST_ARC, ma gli archi vengono valutati con un selettore basato su confronto, che favorirà per primo l'arco più limitato. Per assegnare un selettore al modello di routing, utilizza il metodo ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY	Simile a PATH_CHEAPEST_ARC, tranne per il fatto che i costi dell'arco vengono valutati utilizzando la funzione trasmessa a SetFirstSolutionEvaluator().
SAVINGS	Algoritmo di risparmio (Clarke e Wright). Riferimento Clarke, G. & Wright, J.W. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Point", Research Research, Vol. 12, 1964, pp. 568-581.
SWEEP	Algoritmo Sweep (Wren & Holliday). Fare riferimento ad Anthony Wren e Alan Holliday Pianificazione computerizzata dei veicoli da uno o più depositi a un certo numero di punti di consegna Ricerca operativa trimestrale (1970-1977), Vol. 23, n. 3 (sett., 1972), pp. 333-344.
CHRISTOFIDES	Algoritmo Christofides (in realtà una variante dell'algoritmo Christofides che utilizza una corrispondenza massima anziché una corrispondenza massima, che non garantisce il fattore 3/2 dell'approssimazione di un commerciale viaggiatore della metrica). Funziona con i modelli di routing generici dei veicoli estendendo un percorso finché non è possibile inserire nodi. Riferimento a Nicos Christofides, analisi peggiore di una nuova euristica per il problema del venditore di viaggi, Report 388, Graduate School of Industrial Administration, CMU, 1976.
ALL_UNPERFORMED	Rendi inattivi tutti i nodi. Trova una soluzione solo se i nodi sono facoltativi (sono elementi di un vincolo di disgiunzione con un costo della sanzione limitato).
BEST_INSERTION	Crea una soluzione in modo iterativo inserendo il nodo più economico nella posizione più economica. Il costo di inserzione si basa sulla funzione di costo globale del modello di routing. A partire dal 2/2012, funziona solo su modelli con nodi facoltativi (con costi di sanzione limitati).
PARALLEL_CHEAPEST_INSERTION	Crea una soluzione in modo iterativo inserendo il nodo più economico nella posizione più economica; il costo di inserzione si basa sulla funzione di costo dell'arco. È più veloce di BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION	Crea una soluzione in modo iterativo inserendo ogni nodo nella posizione più economica; il costo di inserzione si basa sulla funzione di costo dell'arco. Differenza da PARALLEL_CHEAPEST_INSERTION per il nodo selezionato per l'inserimento; qui i nodi sono considerati nel loro ordine di creazione. È più veloce di PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC	Collega in modo iterativo due nodi che generano il segmento di percorso più economico.
LOCAL_CHEAPEST_ARC	Seleziona il primo nodo con un successore non associato e collegalo al nodo che produce il segmento di route più economico.
FIRST_UNBOUND_MIN_VALUE	Seleziona il primo nodo con un successore non associato e collegalo al primo nodo disponibile. Equivale alla strategia CHOOSE_FIRST_UNBOUND combinata con ASSIGN_MIN_VALUE (cfr. constraint_solver.h).

Stato ricerca

Puoi restituire lo stato di una ricerca utilizzando il metodo status del modello di routing. Ecco il codice Python per stampare lo stato di una ricerca:

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

Verrà stampato un numero intero con i seguenti significati:

Valore	Descrizione
0	ROUTING_NOT_SOLVED: problema non ancora risolto.
1	ROUTING_SUCCESS: problema risolto.
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: problema risolto dopo aver chiamato RoutingModel.Solve(), tranne per il fatto che non è stato raggiunto un obiettivo locale. Lasciando più tempo sarebbe possibile migliorare la soluzione.
3	ROUTING_FAIL: non è stata trovata alcuna soluzione al problema.
4	ROUTING_FAIL_TIMEOUT: limite di tempo raggiunto prima di trovare una soluzione.
5	ROUTING_INVALID: modello, parametri o flag modello non validi.
6	ROUTING_INFEASIBLE: problema dimostrato impossibili.

Opzioni di ricerca locale

La tabella seguente elenca le opzioni per le strategie di ricerca locale (chiamate anche metaeuristiche). Consulta Modificare la strategia di ricerca per alcuni esempi di impostazione di queste opzioni.

Opzione	Descrizione
AUTOMATIC	Consente al risolutore di selezionare la metaeuristica.
GREEDY_DESCENT	Accetta di migliorare (ridurre i costi) i vicini di ricerca locali fino al raggiungimento di un minimo locale.
GUIDED_LOCAL_SEARCH	Utilizza la ricerca locale guidata per eseguire l'escape dei minimi locali. (cfr. Ricerca locale guidata). In genere, si tratta della metaeuristica più efficiente per gli itinerari in auto.
SIMULATED_ANNEALING	Utilizza la ricottura simulata per evitare i minimi locali (cfr. ricordatura simulata).
TABU_SEARCH	Utilizza la ricerca tabu per eseguire l'escape dei valori minimi locali (cfr. Ricerca Tabu).
GENERIC_TABU_SEARCH	Utilizza la ricerca tabu sul valore obiettivo della soluzione per evitare i minimi locali.

Controllo della propagazione

Nome	Tipo	Predefinito	Descrizione
use_full_propagation	bool	true	Utilizza vincoli con propagazione completa nel modello di routing (anziché solo la propagazione light). La propagazione completa è necessaria solo quando si utilizza la ricerca incentrata sulla profondità o per i modelli che richiedono una propagazione elevata per finalizzare il valore delle variabili secondarie. Se imposti questa opzione su True, la ricerca verrà rallentata nella maggior parte dei casi e verrà aumentato il consumo di memoria in tutti i casi.