FirstSolutionStrategyType Enumeration |
First solution strategy types from https://developers.google.com/optimization/routing/routing_options#first-solution-strategy-options
for use with the platform ORTools service using the IOrTools interface.
Namespace: NetQuarry.Services.OrTools
Assembly: EAP.Core (in EAP.Core.dll) Version: 2.0.0.0 (4.6.8.0)
SyntaxMembers| Member name | Value | Description | |
|---|---|---|---|
| Automatic | 0 | Lets the solver detect which strategy to use according to the model being solved. | |
| GlobalCheapestArc | 1 | Iteratively connect two nodes which produce the cheapest route segment. | |
| LocalCheapestArc | 2 | Select the first node with an unbound successor and connect it to the node which produces the cheapest route segment. | |
| PathCheapestArc | 3 | 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 | 4 | 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(). | |
| EvaluatorStrategy | 5 | Similar to PATH_CHEAPEST_ARC, except that arc costs are evaluated using the function passed to SetFirstSolutionEvaluator(). | |
| AllUnperformed | 6 | Make all nodes inactive. Only finds a solution if nodes are optional (are element of a disjunction constraint with a finite penalty cost). | |
| BestInsertion | 7 | 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 | 8 | 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. | |
| LocalCheapestInsertion | 9 | 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. | |
| Savings | 10 | 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 | 11 | 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. | |
| FirstUnboundMinValue | 12 | 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). | |
| Christofides | 13 | 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. |
See Also