This section describes options for the routing solver.

Many of these options are available only from C++.

## Search limits

Search limits terminate the solver after it reaches a specified limit, such as the maximum length of time, or number of solutions found. You can set a search limit through the solver's search parameters. Here's a Python example that sets a time limit of 30 seconds (30000 milliseconds) for the solver.

search_parameters.time_limit_ms = 30000

Name | Type | Default | Description |
---|---|---|---|

`solution_limit` |
int64 | kint64max | Limit to the number of solutions generated during the search. |

`time_limit_ms` |
int64 | kint64max | Limit in milliseconds to the time spent in the search. |

`routing_lns_time_limit` |
int64 | 100 | Limit in milliseconds to the time spent in the completion search for each local search neighbor. |

## Search control

Name | Type | Default | Description |
---|---|---|---|

`first_solution_strategy` |
string | `AUTOMATIC` |
First solution strategies, used as starting point of local search. See First solution strategy options for a list of available options. |

`optimization_step` |
int64 | 1 | Minimum step by which the solution must be improved in local search. |

### First solution strategy options

Here are a couple of examples that show how to set a first solution strategy in C++ and Python:

- C++:
search_parameters.set_first_solution_strategy(FirstSolutionStrategy::PATH_CHEAPEST_ARC);

- Python:
search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

The following table lists the options for first solution strategy:

Option | Description |
---|---|

`AUTOMATIC` |
Lets the solver detect which strategy to use according to the model being solved. |

`PATH_CHEAPEST_ARC` |
Starting from a route "start" node, connect it to the node which produces the cheapest route segment, then extend the route by iterating on the last node added to the route. |

`PATH_MOST_CONSTRAINED_ARC` |
Similar to `PATH_CHEAPEST_ARC` , but arcs are evaluated with a comparison-based
selector which will favor the most constrained arc first. To assign a
selector to the routing model, see
`RoutingModel::ArcIsMoreConstrainedThanArc()` in routing.h for details. |

`EVALUATOR_STRATEGY` |
Similar to `PATH_CHEAPEST_ARC` , except that arc costs are evaluated using the
function passed to `RoutingModel::SetFirstSolutionEvaluator()`
(see routing.h). |

`SAVINGS` |
Savings algorithm (Clarke & Wright). Reference: Clarke, G. & Wright, J.W.: "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points", Operations Research, Vol. 12, 1964, pp. 568-581. |

`SWEEP` |
Sweep algorithm (Wren & Holliday). Reference: Anthony Wren & Alan Holliday: Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points Operational Research Quarterly (1970-1977), Vol. 23, No. 3 (Sep., 1972), pp. 333-344. |

`CHRISTOFIDES` |
Christofides algorithm (actually a variant of the Christofides algorithm using a maximal matching instead of a maximum matching, which does not guarantee the 3/2 factor of the approximation on a metric travelling salesman). Works on generic vehicle routing models by extending a route until no nodes can be inserted on it. Reference: Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976. |

`ALL_UNPERFORMED` |
Make all nodes inactive. Only finds a solution if nodes are optional (are element of a disjunction constraint with a finite penalty cost). |

`BEST_INSERTION` |
Iteratively build a solution by inserting the cheapest node at its cheapest position; the cost of insertion is based on the global cost function of the routing model. As of 2/2012, only works on models with optional nodes (with finite penalty costs). |

`PARALLEL_CHEAPEST_INSERTION` |
Iteratively build a solution by inserting the cheapest node at its
cheapest position; the cost of insertion is based on the the arc cost
function. Is faster than `BEST_INSERTION` . |

`LOCAL_CHEAPEST_INSERTION` |
Iteratively build a solution by inserting each node at its cheapest
position; the cost of insertion is based on the the arc cost function.
Differs from `PARALLEL_CHEAPEST_INSERTION` by the node selected for
insertion; here nodes are considered in their order of creation. Is
faster than `PARALLEL_CHEAPEST_INSERTION` . |

`GLOBAL_CHEAPEST_ARC` |
Iteratively connect two nodes which produce the cheapest route segment. |

`LOCAL_CHEAPEST_ARC` |
Select the first node with an unbound successor and connect it to the node which produces the cheapest route segment. |

`FIRST_UNBOUND_MIN_VALUE` |
Select the first node with an unbound successor and connect it to the
first available node.
This is equivalent to the `CHOOSE_FIRST_UNBOUND` strategy combined with
`ASSIGN_MIN_VALUE` (cf. constraint_solver.h). |

## First solution heuristics

Name | Type | Default | Description |
---|---|---|---|

savings_route_shape_parameter | double | 1.0 | Coefficient of the added arc in the savings definition. Varying this parameter may provide heuristic solutions which are closer to the optimal solution than otherwise obtained via the traditional algorithm where it is equal to 1. |

savings_filter_neighbors | int64 | 0 | Limit the number of neighbors considered for each node in the savings first solution heuristic. |

savings_filter_radius | int64 | 0 | Limit the distance up to which a neighbor is considered for each node in the savings first solution heuristic. |

sweep_sectors | int64 | 1 | The number of sectors the space is divided before it is sweeped by the ray. |

## First solution heuristics

Name | Type | Default | Description |
---|---|---|---|

savings_route_shape_parameter | double | 1.0 | Coefficient of the added arc in the savings definition. Varying this parameter may provide heuristic solutions which are closer to the optimal solution than otherwise obtained via the traditional algorithm where it is equal to 1. |

savings_filter_neighbors | int64 | 0 | Limit the number of neighbors considered for each node in the savings first solution heuristic. |

savings_filter_radius | int64 | 0 | Limit the distance up to which a neighbor is considered for each node in the savings first solution heuristic. |

sweep_sectors | int64 | 1 | The number of sectors the space is divided before it is sweeped by the ray. |

## Local search options

The following options set local search strategies. See the description of
`LocalSearchMetaheuristic()`

in
`routing_enums.proto`

on GitHub for details.

Name | Type | Default | Description |
---|---|---|---|

guided_local_search | bool | false | Use guided local search. See Guided local search options for a list of available options. |

`guided_local_search_lambda_coefficient` |
double | 0.1 | Lambda coefficient used to penalize arc costs when `GUIDED_LOCAL_SEARCH` is
used. |

### Guided local search options

Here are a couple of examples that show how to set guided local search options in C++ and Python:

- C++:
search_parameters.set_local_search_metaheuristic(FirstSolutionStrategy::PATH_CHEAPEST_ARC);

- Python:
search_parameters.local_search_metaheuristic = ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

Option | Description |
---|---|

`AUTOMATIC` |
Lets the solver select the metaheuristic. |

`GREEDY_DESCENT` |
Accepts improving (cost-reducing) local search neighbors until a local minimum is reached. |

`GUIDED_LOCAL_SEARCH` |
Uses guided local search to escape local minima (cf. http://en.wikipedia.org/wiki/Guided_Local_Search); this is generally the most efficient metaheuristic for vehicle routing. |

`SIMULATED_ANNEALING` |
Uses simulated annealing to escape local minima (cf. http://en.wikipedia.org/wiki/Simulated_annealing). |

`TABU_SEARCH` |
Uses tabu search to escape local minima (cf. http://en.wikipedia.org/wiki/Tabu_search). |

`OBJECTIVE_TABU_SEARCH` |
Uses tabu search on the objective value of solution to escape local minima |

## Propagation control

Name | Type | Default | Description |
---|---|---|---|

`use_light_propagation` |
bool | true | Use constraints with light propagation in routing model. Extra propagation is only necessary when using depth-first search or for models which require strong propagation to finalize the value of secondary variables. Changing this setting to true will slow down the search in most cases and increase memory consumption in all cases. |