Opciones de enrutamiento

En esta sección, se describen algunas de las opciones del solucionador de problemas de enrutamiento.

Límites de búsqueda

Los límites de búsqueda finalizan la resolución de problemas después de que alcanza un límite específico, como el tiempo máximo o la cantidad de soluciones encontradas. Puedes establecer una búsqueda límite a través de los parámetros de búsqueda de la resolución. Consulta Límites de tiempo para ver un ejemplo.

En la siguiente tabla, se describen los límites de búsqueda más comunes.

Nombre	Tipo	Predeterminado	Descripción
solution_limit	int64	kint64max	Limitar la cantidad de soluciones generados durante la búsqueda.
time_limit.seconds	int64	kint64max	Límite en segundos del tiempo dedicado : en la búsqueda.
lns_time_limit.seconds	int64	100	Límite en segundos al tiempo dedicado a : la búsqueda de finalización para cada vecino de búsqueda local.

Primera estrategia de solución

La primera estrategia de solución es el método que usa la resolución de problemas para encontrar una de Google Cloud. En la siguiente tabla, se enumeran las opciones para first_solution_strategy.

Opción	Descripción
AUTOMATIC	Permite que el solucionador detecte qué estrategia usar según la que se está resolviendo el modelo.
PATH_CHEAPEST_ARC	Cómo comenzar desde el valor "start" de una ruta nodo, conéctalo a la que produce el tramo de ruta más barato y luego extiende la ruta iterando en el último nodo agregado a la ruta.
PATH_MOST_CONSTRAINED_ARC	Similar a PATH_CHEAPEST_ARC, pero los arcos son evaluado con un selector basado en la comparación que favorecerá lo más arco restringido primero. Para asignar un selector al modelo de enrutamiento, usa el método ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY	Similar a PATH_CHEAPEST_ARC, con la excepción de que el arco cuesta se evalúan con la función que se pasa a SetFirstSolutionEvaluator()
SAVINGS	Algoritmo de ahorro (Clarke y Wright). Referencia: Clarke, G. & Wright, J.W. "Programación de vehículos desde un depósito central hasta varios puntos de entrega" , Operations Research, Vol. 12, 1964, págs. 568-581.
SWEEP	Algoritmo de barrido (Wren y Holliday). Referencias a Anthony Wren y Alan Holliday Programación de vehículos por computadora de uno o más depósitos a varios puntos de entrega Research Quarterly (1970-1977), vol. 23, núm. 3 (septiembre, 1972), págs. 333-344.
CHRISTOFIDES	el algoritmo Christofides (de hecho, una variante del Algoritmo de Christofides mediante una coincidencia máxima en lugar de un valor máximo de coincidencia, lo que no garantiza el factor 3/2 de la aproximación en una un vendedor ambulante de métricas). Funciona en modelos genéricos de rutas de vehículos de extender una ruta hasta que no se puedan insertar nodos en ella. Referencia de Nicos Christofides, el peor análisis de una heurística nueva para the Traveling Salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
ALL_UNPERFORMED	Desactiva todos los nodos. Solo encuentra una solución si los nodos son opcionales (son elementos de una restricción de disyunción con un costo de penalización finito).
BEST_INSERTION	Compila una solución de forma iterativa con la inserción de las ofertas nodo en su posición más económica; el costo de la inserción se basa en el costo la función de costo del modelo de enrutamiento. A partir de 2/2012, solo funciona en modelos con en nodos opcionales (con costos de penalización finitos).
PARALLEL_CHEAPEST_INSERTION	Compila una solución de forma iterativa insertando el el nodo más barato en su posición más barata; el costo de la inserción se basa en la función de arco de costo. Es más rápido que BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION	Compila una solución de forma iterativa insertando cada nodo en su posición más económica; El costo de la inserción se basa en el arco la función de costo. Difiere de PARALLEL_CHEAPEST_INSERTION por el nodo. seleccionados para su inserción aquí, los nodos se consideran en el orden de de la creación de cuentas de servicio. Es más rápido que PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC	Conectan de forma iterativa dos nodos que producen la el segmento de ruta más económico.
LOCAL_CHEAPEST_ARC	Selecciona el primer nodo con un sucesor no vinculado y la conecta al nodo que produce el segmento de ruta más económico.
FIRST_UNBOUND_MIN_VALUE	Selecciona el primer nodo con un sucesor no vinculado y conectarlo al primer nodo disponible. Esto equivale a la Estrategia CHOOSE_FIRST_UNBOUND combinada con ASSIGN_MIN_VALUE (cf. constraint_solver.h).

Estado de búsqueda

Puedes mostrar el estado de una búsqueda con el método status del modelo de enrutamiento. Este es el código de Python para imprimir el estado de una búsqueda:

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

Esto imprime un número entero con los siguientes significados:

Valor	Descripción
0	ROUTING_NOT_SOLVED: Aún no se resolvió el problema.
1	ROUTING_SUCCESS: El problema se resolvió correctamente.
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: Problema resuelto correctamente después de llamar a RoutingModel.Solve(), excepto que una solicitud no se ha alcanzado el valor óptimo. Dejar más tiempo permitiría mejorar la de Google Cloud.
3	ROUTING_FAIL: No se encontró ninguna solución para el problema.
4	ROUTING_FAIL_TIMEOUT: Se alcanzó el límite de tiempo antes de encontrar una solución.
5	ROUTING_INVALID: El modelo, los parámetros del modelo o las marcas no son válidos.
6	ROUTING_INFEASIBLE: El problema es inviable.

Opciones de búsqueda local

La siguiente tabla incluye las opciones para las estrategias de búsqueda local (también denominadas metaheurística). Consulte Cómo cambiar la estrategia de búsqueda. para ver ejemplos de cómo configurar estas opciones.

Opción	Descripción
AUTOMATIC	Permite que el solucionador de problemas seleccione la metaheurística.
GREEDY_DESCENT	Acepta la mejora (reducción de costos) de la búsqueda local de vecinos hasta que un se alcanza el mínimo.
GUIDED_LOCAL_SEARCH	Usa la búsqueda local guiada para escapar de los mínimos locales. (cf. Búsqueda local guiada) esta suele ser la metaheurística más eficiente para la planificación de rutas de vehículos.
SIMULATED_ANNEALING	Utiliza recolectores simulados para escapar de los mínimos locales (cf. Anulación simulada).
TABU_SEARCH	Utiliza la búsqueda tabu para escapar de los mínimos locales (ver Búsqueda Tabu).
GENERIC_TABU_SEARCH	Usa la búsqueda tabu en el valor objetivo de la solución para escapar de lo local mínimo.

Control de propagación

Nombre	Tipo	Predeterminado	Descripción
use_full_propagation	bool	verdadero	Usa restricciones con propagación completa en el modelo de enrutamiento (en lugar de solo en la propagación ligera). Completo la propagación solo es necesaria cuando se usa la búsqueda que prioriza la profundidad o para modelos que requieren una propagación sólida para finalizar el valor de variables. Cambiar esta configuración a verdadero ralentizará la búsqueda en la mayoría de los casos, y aumentar el consumo de memoria en todos los casos.