Options de routage

Cette section décrit certaines des options disponibles pour la solution de routage.

Limites de recherche

Les limites de recherche arrêtent le résolveur lorsqu'il atteint une limite spécifiée, par exemple la durée maximale ou le nombre de solutions trouvées. Vous pouvez définir une recherche via les paramètres de recherche du résolveur. Voir Consultez les limites de temps pour obtenir un exemple.

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

Nom Type Par défaut Description
solution_limit int64 kint64max Limiter au nombre de solutions générées lors de la recherche.
time_limit.seconds int64 kint64max Limitez la durée en secondes au temps passé : dans la recherche.
lns_time_limit.seconds int64 100 Limitez la durée en secondes au temps passé en : la recherche complète pour chaque voisin de recherche à proximité.

Stratégie de première solution

La première stratégie de solution est la méthode utilisée par le résolveur pour trouver une solution. Le tableau suivant répertorie les options pour first_solution_strategy.

Option Description
AUTOMATIC Permet au résolveur de détecter la stratégie à utiliser en fonction en cours de résolution.
PATH_CHEAPEST_ARC Partir d'un "départ" d'itinéraire du nœud, connectez-le au nœud qui produit le segment d'itinéraire le moins cher, puis prolongez l'itinéraire de l’itération sur le dernier nœud ajouté à la route.
PATH_MOST_CONSTRAINED_ARC Semblable à PATH_CHEAPEST_ARC, à la différence que les arcs évalué à l'aide d'un sélecteur basé sur la comparaison, qui favorise un arc contraint. Pour attribuer un sélecteur au modèle de routage, utilisez le ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY Semblable à PATH_CHEAPEST_ARC, à la différence que le coût d'arc sont évaluées à l'aide de la fonction transmise SetFirstSolutionEvaluator()
SAVINGS Algorithme d'économies (Clarke &Wright). Référence Clarke, G. & Wright, J.W. "Planification de véhicules d'un dépôt central vers un certain nombre de points de livraison" , Operations Research, Vol. 12, 1964, p. 568 à 581.
SWEEP Algorithme de balayage (Wren et Holliday). Références à Anthony Wren & Alan Holliday Planification de véhicules par ordinateur d'un ou plusieurs dépôts à plusieurs points de livraison opérationnels Étude trimestrielle (1970-1977), vol. 23, n° 3 (sept., 1972), p. 333-344.
CHRISTOFIDES l'algorithme de Christofides (il s'agit en fait d'une variante du 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 une "Commercial itinérant". Fonctionne sur les modèles d'itinéraires de véhicules génériques qui prolonge une route jusqu'à ce qu'aucun nœud ne puisse y être inséré. Référence à Nicos Christofides, analyse du pire des cas d'une nouvelle heuristique pour le problème du vendeur itinérant, Rapport 388, Graduate School of Industrial Administration, CMU, 1976.
ALL_UNPERFORMED Rendre tous les nœuds inactifs. Ne trouve une solution que si les nœuds sont facultatifs (ils font partie d'une contrainte de disjonction avec un coût de pénalité fini).
BEST_INSERTION Créez une solution de manière itérative en insérant le modèle le moins cher à sa position la moins chère ; le coût de l'insertion est basé sur et la fonction de coût du modèle de routage. Depuis le 02/2012, ne fonctionne que sur les modèles des nœuds facultatifs (avec des coûts de pénalité finis).
PARALLEL_CHEAPEST_INSERTION Créez une solution de manière itérative en insérant la méthode nœud le moins cher à sa position la moins chère ; le coût de l'insertion 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 à sa position la moins chère ; le coût de l'insertion est basé sur l'arc fonction de coût. Diffère de PARALLEL_CHEAPEST_INSERTION selon le nœud sélectionné pour l'insertion ; Ici, les nœuds sont considérés dans l'ordre création. est plus rapide que PARALLEL_CHEAPEST_INSERTION ;
GLOBAL_CHEAPEST_ARC connecter de manière itérative deux nœuds qui produisent le segment d'itinéraire le moins cher.
LOCAL_CHEAPEST_ARC Sélectionnez le premier nœud avec un successeur illimité et le connecter au nœud qui produit le segment d'itinéraire le moins cher.
FIRST_UNBOUND_MIN_VALUE Sélectionner le premier nœud avec un successeur non associé et le connecter au premier nœud disponible. Cela équivaut à Stratégie CHOOSE_FIRST_UNBOUND combinée à ASSIGN_MIN_VALUE (voir contrainte_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 nombre entier s'affiche avec les significations suivantes:

Valeur Description
0 ROUTING_NOT_SOLVED: problème pas encore résolu.
1 ROUTING_SUCCESS: le problème a bien été résolu.
2 ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: problème résolu après l'appel de RoutingModel.Solve(), sauf qu'une requête locale l'optimum n'a pas été atteint. En laissant plus de temps, vous améliorerez solution.
3 ROUTING_FAIL: aucune solution au problème trouvée.
4 ROUTING_FAIL_TIMEOUT: limite de temps atteinte 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 qui s'est avéré irréalisable

Options de recherche à proximité

Le tableau suivant répertorie les options des stratégies de recherche locale (également appelées métaheuristiques). Consultez la section Modifier la stratégie de recherche. pour obtenir des exemples de configuration de ces options.

Option Description
AUTOMATIC Permet au résolveur de sélectionner la métaheuristique.
GREEDY_DESCENT Accepte l'amélioration (réduisant les coûts) de la recherche à proximité minimum est atteint.
GUIDED_LOCAL_SEARCH Utilise une recherche locale guidée pour échapper aux minimums locaux. (cf. Recherche à proximité guidée) il s'agit généralement de la métaheuristique la plus efficace pour le routage des véhicules.
SIMULATED_ANNEALING Utilise un recuits simulé pour échapper aux minimums locaux (cf. Recuit simulé).
TABU_SEARCH Utilise la recherche tabou pour échapper les minimums locaux (cf. Tabu Search).
GENERIC_TABU_SEARCH Utilise la recherche tabu sur la valeur d'objectif de la solution pour échapper l'attribut local minimum.

Contrôle de la propagation

Nom Type Par défaut Description
use_full_propagation Bool true Utiliser des contraintes avec une propagation complète dans le modèle de routage (au lieu de la propagation légère uniquement). Plein écran la propagation n'est nécessaire que lors de l'utilisation de la recherche axée sur la profondeur ou pour des modèles qui nécessitent une forte propagation pour finaliser la valeur variables. Si vous définissez ce paramètre sur "true", la recherche sera ralentie dans la plupart des cas et d’augmenter la consommation de mémoire dans tous les cas.