Options de routage

Cette section décrit certaines des options disponibles avec le résolveur de routage.

Limites du nombre de recherches

Les limites de recherche arrêtent le résolveur lorsqu'il atteint une limite spécifiée, telle que la durée maximale ou le nombre de solutions trouvées. Vous pouvez définir une limite de recherche via les paramètres de recherche du résolveur. Pour en savoir plus, consultez Limites de temps.

Le tableau suivant décrit les limites de recherche les plus courantes.

Nom	Type	Par défaut	Description
solution_limit	int64	Kint64Max	Limitez au nombre de solutions générées lors de la recherche.
time_limit.seconds	int64	Kint64Max	Limitez le temps passé en secondes à la recherche.
lns_time_limit.seconds	int64	100	Limite en secondes du temps passé dans : la recherche à effectuer pour chaque voisin local.

Première stratégie de solution

La première stratégie de solution consiste à utiliser une solution permettant de trouver une solution initiale. Le tableau suivant présente les options pour first_solution_strategy.

Option	Description
AUTOMATIC	Il permet au résolveur de détecter la stratégie à utiliser en fonction du modèle résolu.
PATH_CHEAPEST_ARC	À partir d'un nœud de départ "route", connectez-le au nœud qui génère le segment d'itinéraire le moins cher, puis étendez le routage en effectuant une itération sur le dernier nœud ajouté à la route.
PATH_MOST_CONSTRAINED_ARC	Semblable à PATH_CHEAPEST_ARC, mais les arcs sont évalués à l'aide d'un sélecteur basé sur la comparaison qui privilégie l'arc le plus limité. Pour attribuer un sélecteur au modèle de routage, utilisez la méthode ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY	Semblable à PATH_CHEAPEST_ARC, sauf que les coûts d'arc sont évalués à l'aide de la fonction transmise à SetFirstSolutionEvaluator().
SAVINGS	Algorithme épargne (Clarke et Wright). Référencer Clarke, G. et Wright, J.W. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points" , Operations Research, Vol. 12, 1964, p. 568-581.
SWEEP	Algorithme de balayage (Wren et Holliday). Référencer Anthony Wren et Alan Holliday sur l'emploi du temps par ordinateur des véhicules d'un ou de plusieurs dépôts à une recherche opérationnelle trimestrielle (1970-1977), Vol. 23, n° 3 (sept., 1972), p. 333-344.
CHRISTOFIDES	Algorithme Christofides (une variante de l'algorithme Christofides utilisant une correspondance maximale au lieu d'une correspondance maximale, ce qui ne garantit pas le facteur 3/2 de l'approximation sur un commercial de voyages métrique). Fonctionne sur les modèles génériques d'itinéraires des véhicules en étendant un itinéraire jusqu'à ce qu'aucun nœud ne puisse y être inséré. Référence Nicos Christofides, pire analyse d'une nouvelle heuristique pour le problème des voyageurs itinérants, rapport 388, Graduate School of Industrial Administration, CMU, 1976.
ALL_UNPERFORMED	Désactivez tous les nœuds. Elle ne trouve de solution que si les nœuds sont facultatifs (éléments d'une contrainte de disjonction avec un coût fini de pénalité).
BEST_INSERTION	Créez une solution de manière itérative en insérant le nœud le moins cher à sa position la moins chère. Le coût de l'insertion est basé sur la fonction de coût global du modèle de routage. Depuis le 2 janvier 2012, ne fonctionne que sur des modèles avec des nœuds facultatifs (avec des coûts limités en termes de pénalités).
PARALLEL_CHEAPEST_INSERTION	Créez une solution de manière itérative en insérant le nœud le moins cher à son emplacement le moins cher. Le coût de l'insertion est basé sur la fonction de coût de l'arc. est plus rapide que BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION	Créez une solution de manière itérative en insérant chaque nœud à sa position la moins chère. Le coût de l'insertion est basé sur la fonction de coût de l'arc. Diffère de PARALLEL_CHEAPEST_INSERTION par le nœud sélectionné pour l'insertion. Ici, les nœuds sont pris en compte dans l'ordre de leur création. est plus rapide que PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC	Connectez deux nœuds de manière itérative pour produire la section de routage la moins chère.
LOCAL_CHEAPEST_ARC	Sélectionnez le premier nœud avec un successeur non associé et connectez-le au nœud qui génère le segment d'itinéraire le moins cher.
FIRST_UNBOUND_MIN_VALUE	Sélectionnez le premier nœud avec un successeur non associé et connectez-le au premier nœud disponible. Cela équivaut à la stratégie CHOOSE_FIRST_UNBOUND combinée à ASSIGN_MIN_VALUE (cf.constraint_solver.h).

État de la recherche

Vous pouvez renvoyer l'état d'une recherche à l'aide de la méthode status du modèle de routage. Voici le code Python permettant d'afficher l'état d'une recherche:

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

Un entier s'affiche comme suit:

Valeur	Description
0	ROUTING_NOT_SOLVED: problème non résolu.
1	ROUTING_SUCCESS: le problème a bien été résolu.
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: le problème a bien été résolu après avoir appelé RoutingModel.Solve(), sauf qu'aucun indicateur local n'a été atteint. Laisser plus de temps nous permettrait d'améliorer la solution.
3	ROUTING_FAIL: aucune solution n'a été trouvée pour le problème.
4	ROUTING_FAIL_TIMEOUT: délai atteint avant de trouver une solution.
5	ROUTING_INVALID: le modèle, les paramètres de modèle ou les options ne sont pas valides.
6	ROUTING_INFEASIBLE: problème avéré impossible.

Options de recherche à proximité

Le tableau suivant présente les options associées aux stratégies de recherche à proximité (également appelées métaheuristiques). Pour savoir comment définir ces options, consultez Modifier la stratégie de recherche.

Option	Description
AUTOMATIC	Permet au résolveur de sélectionner le métaheuristique.
GREEDY_DESCENT	Accepte les voisins qui effectuent des recherches à proximité (en baisse de coût) jusqu'à ce qu'un minimum local soit atteint.
GUIDED_LOCAL_SEARCH	Permet d'échapper à une minimisation locale en effectuant une recherche locale guidée. (cf. Recherche locale guidée) est généralement le métaheuristique le plus efficace pour calculer l'itinéraire d'un véhicule.
SIMULATED_ANNEALING	Utilise une simulation d'annulage pour échapper les minimums locaux (cf. Simulation d'annulage).
TABU_SEARCH	Utilise la recherche tabu pour échapper les minimums locaux (cf. Recherches tabu).
GENERIC_TABU_SEARCH	Utilise la recherche tabu sur la valeur objectif de la solution pour échapper les minimums locaux.

Contrôle de la propagation

Nom	Type	Par défaut	Description
use_full_propagation	Bool	true	Utilisez des contraintes avec propagation complète dans le modèle de routage (au lieu de la propagation légère uniquement). La propagation complète n'est nécessaire que lors de l'utilisation d'une recherche axée sur la profondeur ou pour les modèles qui nécessitent une forte propagation pour finaliser la valeur des variables secondaires. La définition de ce paramètre sur "true" ralentit la recherche et augmente la consommation de mémoire dans tous les cas.