Opzioni di routing

Questa sezione descrive alcune delle opzioni disponibili per il risolutore di routing.

Limiti per le ricerche

I limiti di ricerca fanno terminare il risolutore al raggiungimento di un limite specificato, ad esempio la durata massima o il numero di soluzioni trovate. Puoi impostare una ricerca limite tramite i parametri di ricerca del risolutore. Consulta I limiti di tempo, ad esempio.

La tabella seguente descrive i limiti più comuni per la ricerca.

Nome	Tipo	Predefinito	Descrizione
solution_limit	int64	kint64max	Limitarsi al numero di soluzioni generati durante la ricerca.
time_limit.seconds	int64	kint64max	Limita il tempo in secondi al tempo trascorso : nella ricerca.
lns_time_limit.seconds	int64	100	Limita il tempo in secondi al tempo trascorso tra : la ricerca di completamento di ogni vicino di ricerca locale.

Strategia della prima soluzione

La prima strategia di soluzione è il metodo utilizzato dal risolutore per trovare soluzione. Nella tabella seguente sono elencate le opzioni per first_solution_strategy.

Opzione	Descrizione
AUTOMATIC	Consente al risolutore di individuare la strategia da usare in base alla del modello in fase di risoluzione.
PATH_CHEAPEST_ARC	Partendo da una route "start" collegalo al nodo, nodo che produce il segmento di percorso più economico, quindi estendi il percorso di eseguendo l'iterazione sull'ultimo nodo aggiunto alla route.
PATH_MOST_CONSTRAINED_ARC	Simile a PATH_CHEAPEST_ARC, ma gli archi sono viene valutato con un selettore basato sul confronto che favorisce con arco vincolato. Per assegnare un selettore al modello di routing, utilizza la classe ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY	Simile a PATH_CHEAPEST_ARC, ad eccezione del fatto che i costi dell'arco vengono valutati utilizzando la funzione passata SetFirstSolutionEvaluator()
SAVINGS	Algoritmo di risparmio (Clarke e Wright). Riferimento Clarke, G. & [Nome di persona], J.W. "Programmazione dei veicoli da un deposito centrale a un numero di punti di consegna" , Operations Research, vol. 12, 1964, pp. 568-581.
SWEEP	Algoritmo di sweep (Wren e Holliday). Riferimento Anthony Wren e Alan Holliday - Programmazione dei veicoli tramite computer da uno o più depositi a un numero di punti di consegna operativi Research Quarterly (1970-1977), vol. 23, n. 3 (Set., 1972), pp. 333-344.
CHRISTOFIDES	L'algoritmo di Christofides (in realtà una variante del Algoritmo di Christofides che utilizza una corrispondenza massima anziché un valore massimo il che non garantisce il fattore 3/2 dell'approssimazione su una commerciale di viaggio del sistema metrico). Compatibile con modelli generici di percorsi per veicoli di Estendere una route fino a quando non è possibile inserire nodi al suo interno. Ci riferiamo a Nicos Christofides, l'analisi peggiore di una nuova euristica per il problema del venditore viaggiante, Report 388, Graduate School of Industrial Amministrazione, CMU, 1976.
ALL_UNPERFORMED	Rendi inattivi tutti i nodi. Trova una soluzione solo se i nodi sono opzionali (sono elementi di un vincolo di disgiunzione con un costo di penalità finito).
BEST_INSERTION	Crea una soluzione in modo iterativo inserendo la soluzione più economica il nodo nella posizione più economica. Il costo di inserimento si basa sul prezzo funzione di costo del modello di routing. A partire dal 2/2012, funziona solo su modelli con nodi facoltativi (con costi di penalizzazione limitati).
PARALLEL_CHEAPEST_INSERTION	Crea una soluzione in modo iterativo inserendo il nodo più economico nella posizione più economica. il costo di inserimento si basa su la funzione di costo arco. È più veloce di BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION	Crea una soluzione in modo iterativo inserendo ogni il nodo nella posizione più economica. il costo di inserimento è basato sull'arco funzione di costo. È diverso da PARALLEL_CHEAPEST_INSERTION per nodo selezionato per l'inserimento; qui i nodi sono considerati nel loro ordine per la creazione di contenuti. È più veloce di PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC	Collegare iterativamente due nodi che producono la tratta più economica.
LOCAL_CHEAPEST_ARC	Seleziona il primo nodo con un successore non associato e collegarlo al nodo che produce il segmento di percorso più economico.
FIRST_UNBOUND_MIN_VALUE	Seleziona il primo nodo con un successore non associato e connetterlo al primo nodo disponibile. Equivale al Strategia CHOOSE_FIRST_UNBOUND combinata con ASSIGN_MIN_VALUE (cfr. constraint_solver.h).

Cerca stato

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())

Viene visualizzato 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 correttamente dopo aver chiamato RoutingModel.Solve(), ad eccezione del fatto che non sia stato raggiunto il valore ottimale. Lasciare più tempo consente di migliorare soluzione.
3	ROUTING_FAIL: non è stata trovata alcuna soluzione al problema.
4	ROUTING_FAIL_TIMEOUT: è stato raggiunto il limite di tempo prima di trovare una soluzione.
5	ROUTING_INVALID: il modello, i parametri del modello o i flag non sono validi.
6	ROUTING_INFEASIBLE: il problema è stato dimostrato non fattibile.

Opzioni di ricerca locale

La seguente tabella elenca le opzioni per le strategie di ricerca locale (chiamate anche metaeuristica). Consulta Modifica della strategia di ricerca. per vedere alcuni esempi di impostazione di queste opzioni.

Opzione	Descrizione
AUTOMATIC	Lascia che sia il risolutore a selezionare il metaeuristico.
GREEDY_DESCENT	Accetta il miglioramento (riduzione dei costi) dei vicini di ricerca locale fino a quando viene raggiunto il valore minimo.
GUIDED_LOCAL_SEARCH	Utilizza la ricerca locale guidata per evitare i minimi locali. (cfr. Ricerca locale guidata) questo è generalmente il metaeuristico più efficiente per il calcolo di percorsi dei veicoli.
SIMULATED_ANNEALING	Utilizza l'annealing simulato per sfuggire ai minimi locali (cfr. annealing simulato).
TABU_SEARCH	Utilizza la ricerca tabu per evitare i minimi locali (cfr. Ricerca Tabu).
GENERIC_TABU_SEARCH	Utilizza la ricerca tabu sul valore obiettivo della soluzione per eseguire l'escape dei caratteri locali minimi.

Controllo della propagazione

Nome	Tipo	Predefinito	Descrizione
use_full_propagation	bool	true	Usa i vincoli con la propagazione completa nel modello di routing (anziché solo la propagazione della luce). Completo la propagazione è necessaria solo quando si utilizza la ricerca depth-first o per i modelli che richiedono una forte propagazione per finalizzare il valore di come la codifica one-hot delle variabili categoriche. Se si modifica questa impostazione su true, la ricerca verrà rallentata in nella maggior parte dei casi e aumentare l'utilizzo della memoria in tutti i casi.