Opciones de enrutamiento

En esta sección, se describen algunas de las opciones para la resolución de problemas de enrutamiento.

Límites de búsqueda

Los límites de búsqueda finalizan la resolución una vez que se alcanza un límite especificado, como la cantidad máxima de tiempo o la cantidad de soluciones encontradas. Puedes establecer un límite de búsqueda a través de los parámetros de búsqueda del solucionador. 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	Predeterminada	Descripción
solution_limit	int64	kint64max	Limita la cantidad de soluciones generadas durante la búsqueda.
time_limit.seconds	int64	kint64max	Limitar en segundos al tiempo dedicado: en la búsqueda.
lns_time_limit.seconds	int64	100	Limitar 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 el agente de resolución usa para encontrar una solución inicial. En la siguiente tabla, se enumeran las opciones para first_solution_strategy.

Opción	Descripción
AUTOMATIC	Permite que el agente de resolución detecte qué estrategia usar según el modelo que se resuelve.
PATH_CHEAPEST_ARC	Comenzando por un nodo de "inicio" de la ruta, conéctalo al nodo que produce el segmento de ruta más económico 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 se evalúan con un selector basado en comparaciones que favorecerá primero al arco más restringido. Para asignar un selector al modelo de enrutamiento, usa el método ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY	Es similar a PATH_CHEAPEST_ARC, excepto que los costos de arco se evalúan mediante la función que se pasa a SetFirstSolutionEvaluator().
SAVINGS	Algoritmo de ahorro (Clarke y Wright). Referencia Clarke, G. & Wright, J.W. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points" (Programación de vehículos desde un depósito central hasta la cantidad de puntos de entrega), Investigación de Operaciones, Vol. 12, 1964, pp. 568-581.
SWEEP	Algoritmo de barrido (Wren y Holliday). Referencia de Anthony Wren y Alan Holliday Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points Operatingal Operatingal Quarterly (1970-1977), Vol. 23, No. 3 (1 de septiembre de 1972), pp. 333-344.
CHRISTOFIDES	Algoritmo de Christofides (en realidad, una variante del algoritmo Christofides que usa una coincidencia máxima en lugar de una coincidencia máxima, lo que no garantiza el factor de 3/2 de la aproximación en un vendedor que viaja viajando en las métricas). Extienden una ruta hasta que no se pueden insertar nodos en los modelos de enrutamiento de vehículos genéricos. Referencia: Nicos Christofides, análisis de los peores casos de una nueva heurística para el problema del vendedor viajero, informe 388, Graduate School of Industrial Management, CMU, 1976.
ALL_UNPERFORMED	Inhabilita todos los nodos. Solo se 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	Para compilar una solución de forma iterativa, inserta el nodo más económico en su posición más económica. El costo de inserción se basa en la función de costo global del modelo de enrutamiento. A partir de 2/2012, solo funciona en modelos con nodos opcionales (con costos de penalización finitos).
PARALLEL_CHEAPEST_INSERTION	Para compilar una solución de forma iterativa, inserta el nodo más económico en su posición más económica. El costo de inserción se basa en la función de costo de arco. Es más rápida 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 inserción se basa en la función de costo de arco. difiere del PARALLEL_CHEAPEST_INSERTION por el nodo seleccionado para la inserción; aquí, los nodos se consideran en su orden de creación. Es más rápida que PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC	Conecta de manera iterativa dos nodos que producen el segmento de ruta más económico.
LOCAL_CHEAPEST_ARC	Selecciona el primer nodo con un sucesor no vinculado y conéctalo 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 conéctalo al primer nodo disponible. Esto equivale a la estrategia CHOOSE_FIRST_UNBOUND combinada con ASSIGN_MIN_VALUE (cf. constraint_solver.h).

Estado de la búsqueda

Puedes mostrar el estado de una búsqueda con el método status del modelo de enrutamiento. A continuación, se muestra 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: Se resolvió correctamente el problema.
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: Se resolvió correctamente el problema después de llamar a RoutingModel.Solve(), excepto que no se alcanzó un óptimo local. Dedicar más tiempo permitiría mejorar la solución.
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: Se demostró que el problema es inviable.

Opciones de búsqueda local

En la siguiente tabla, se muestran las opciones de las estrategias de búsqueda local (también denominadas metaheurísticas). Consulta Cómo cambiar la estrategia de búsqueda para ver ejemplos sobre cómo configurar estas opciones.

Opción	Descripción
AUTOMATIC	Permite que el solucionador seleccione la metaheurística.
GREEDY_DESCENT	Se aceptan mejoras (reducción de costos) de los vecinos de la búsqueda local hasta que se alcanza un mínimo local.
GUIDED_LOCAL_SEARCH	Usa la búsqueda local guiada para escapar de los mínimos locales. (consulta la Búsqueda local guiada). Por lo general, es la metaheurística más eficiente para el enrutamiento de vehículos.
SIMULATED_ANNEALING	Utiliza un recolector simulado para escapar mínimos locales (consulta Simulación de reposición).
TABU_SEARCH	Usa la búsqueda Tabu para escapar de los mínimos locales (consulta Búsqueda de Tabu).
GENERIC_TABU_SEARCH	Usa la búsqueda tabú en el valor objetivo de la solución para escapar los mínimos locales.

Control de propagación

Nombre	Tipo	Predeterminada	Descripción
use_full_propagation	bool	true	Usa restricciones con la propagación completa en el modelo de enrutamiento (en lugar de solo la propagación ligera). La propagación completa solo es necesaria cuando se usa la búsqueda centrada en la profundidad o para modelos que requieren una propagación sólida para finalizar el valor de las variables secundarias. 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.