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. |