DotNet Reference
DotNet Reference
Detailed Description
Container for nested types declared in the FirstSolutionStrategy message type.
Definition at line 160 of file RoutingEnums.pb.cs.
Public Types | |
| enum | Value { Unset = 0, Automatic = 15, PathCheapestArc = 3, PathMostConstrainedArc = 4, EvaluatorStrategy = 5, Savings = 10, Sweep = 11, Christofides = 13, AllUnperformed = 6, BestInsertion = 7, ParallelCheapestInsertion = 8, SequentialCheapestInsertion = 14, LocalCheapestInsertion = 9, GlobalCheapestArc = 1, LocalCheapestArc = 2, FirstUnboundMinValue = 12 } |
Member Enumeration Documentation
◆ Value
|
strong |
| Enumerator | |
|---|---|
| Unset | See the homonymous value in LocalSearchMetaheuristic. |
| Automatic | Lets the solver detect which strategy to use according to the model being solved. |
| PathCheapestArc | — Path addition heuristics — 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. |
| PathMostConstrainedArc | Same as 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. |
| EvaluatorStrategy | Same as PATH_CHEAPEST_ARC, except that arc costs are evaluated using the function passed to RoutingModel::SetFirstSolutionEvaluator() (cf. 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. |
| AllUnperformed | — Path insertion heuristics — Make all nodes inactive. Only finds a solution if nodes are optional (are element of a disjunction constraint with a finite penalty cost). |
| BestInsertion | 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). |
| ParallelCheapestInsertion | 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. |
| SequentialCheapestInsertion | Iteratively build a solution by constructing routes sequentially, for each route inserting the cheapest node at its cheapest position until the route is completed; the cost of insertion is based on the arc cost function. Is faster than PARALLEL_CHEAPEST_INSERTION. |
| LocalCheapestInsertion | 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 decreasing order of distance to the start/ends of the routes, i.e. farthest nodes are inserted first. Is faster than SEQUENTIAL_CHEAPEST_INSERTION. |
| GlobalCheapestArc | — Variable-based heuristics — Iteratively connect two nodes which produce the cheapest route segment. |
| LocalCheapestArc | Select the first node with an unbound successor and connect it to the node which produces the cheapest route segment. |
| FirstUnboundMinValue | 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). |
Definition at line 161 of file RoutingEnums.pb.cs.
The documentation for this class was generated from the following file: