# Routing Options

This section describes some of the options for the routing solver.

## 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. See
[Time limits](https://developers.google.com/optimization/routing/routing_tasks#time_limits) for an example.

The following table describes the most common search limits.

| Name | Type | Default | Description |
|---|---|---|---|
| `solution_limit` | int64 | kint64max | Limit to the number of solutions generated during the search. |
| `time_limit.seconds` | int64 | kint64max | Limit in seconds to the time spent : in the search. |
| `lns_time_limit.seconds` | int64 | 100 | Limit in seconds to the time spent in : the completion search for each local search neighbor. |

## First solution strategy

The first solution strategy is the method the solver uses to find an initial
solution. 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, use the method `ArcIsMoreConstrainedThanArc()`. |
| `EVALUATOR_STRATEGY` | Similar to `PATH_CHEAPEST_ARC`, except that arc costs are evaluated using the function passed to `SetFirstSolutionEvaluator()`. |
| `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 salesperson). 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 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 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). |

## Search status

You can return the status of a search using the routing model's `status` method.
Here's the Python code to print the status of a search:

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

This prints an integer with the following meanings:

| Value | Description |
|---|---|
| `0` | `ROUTING_NOT_SOLVED`: Problem not solved yet. |
| `1` | `ROUTING_SUCCESS`: Problem solved successfully. |
| `2` | `ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED`: Problem solved successfully after calling `RoutingModel.Solve()`, except that a local optimum has not been reached. Leaving more time would allow improving the solution. |
| `3` | `ROUTING_FAIL`: No solution found to the problem. |
| `4` | `ROUTING_FAIL_TIMEOUT`: Time limit reached before finding a solution. |
| `5` | `ROUTING_INVALID`: Model, model parameters, or flags are not valid. |
| `6` | `ROUTING_INFEASIBLE`: Problem proven to be infeasible. |

## Local search options

The following table lists the options for local search strategies (also called
**metaheuristics** ).
See [Changing the search strategy](https://developers.google.com/optimization/routing/tsp#search_strategy)
for examples of setting these options.

| 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. [Guided Local Search](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. [Simulated Annealing](http://en.wikipedia.org/wiki/Simulated_annealing)). |
| `TABU_SEARCH` | Uses tabu search to escape local minima (cf. [Tabu Search](http://en.wikipedia.org/wiki/Tabu_search)). |
| `GENERIC_TABU_SEARCH` | Uses tabu search on the objective value of solution to escape local minima. |

## Propagation control

| Name | Type | Default | Description |
|---|---|---|---|
| `use_full_propagation` | bool | true | Use constraints with full propagation in routing model (instead of **light** propagation only). Full 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. |