1// Copyright 2010-2021 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6//     http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// Enums used to define routing parameters.
15
16syntax = "proto3";
17
18option java_package = "com.google.ortools.constraintsolver";
19option java_multiple_files = true;
20option csharp_namespace = "Google.OrTools.ConstraintSolver";
21
22package operations_research;
23
24// First solution strategies, used as starting point of local search.
25message FirstSolutionStrategy {
26  enum Value {
27    // See the homonymous value in LocalSearchMetaheuristic.
28    UNSET = 0;
29
30    // Lets the solver detect which strategy to use according to the model being
31    // solved.
32    AUTOMATIC = 15;
33
34    // --- Path addition heuristics ---
35    // Starting from a route "start" node, connect it to the node which produces
36    // the cheapest route segment, then extend the route by iterating on the
37    // last node added to the route.
38    PATH_CHEAPEST_ARC = 3;
39    // Same as PATH_CHEAPEST_ARC, but arcs are evaluated with a comparison-based
40    // selector which will favor the most constrained arc first. To assign a
41    // selector to the routing model, see
42    // RoutingModel::ArcIsMoreConstrainedThanArc() in routing.h for details.
43    PATH_MOST_CONSTRAINED_ARC = 4;
44    // Same as PATH_CHEAPEST_ARC, except that arc costs are evaluated using the
45    // function passed to RoutingModel::SetFirstSolutionEvaluator()
46    // (cf. routing.h).
47    EVALUATOR_STRATEGY = 5;
48    // Savings algorithm (Clarke & Wright).
49    // Reference: Clarke, G. & Wright, J.W.:
50    // "Scheduling of Vehicles from a Central Depot to a Number of Delivery
51    // Points", Operations Research, Vol. 12, 1964, pp. 568-581
52    SAVINGS = 10;
53    // Sweep algorithm (Wren & Holliday).
54    // Reference: Anthony Wren & Alan Holliday: Computer Scheduling of Vehicles
55    // from One or More Depots to a Number of Delivery Points Operational
56    // Research Quarterly (1970-1977),
57    // Vol. 23, No. 3 (Sep., 1972), pp. 333-344
58    SWEEP = 11;
59    // Christofides algorithm (actually a variant of the Christofides algorithm
60    // using a maximal matching instead of a maximum matching, which does
61    // not guarantee the 3/2 factor of the approximation on a metric travelling
62    // salesman). Works on generic vehicle routing models by extending a route
63    // until no nodes can be inserted on it.
64    // Reference: Nicos Christofides, Worst-case analysis of a new heuristic for
65    // the travelling salesman problem, Report 388, Graduate School of
66    // Industrial Administration, CMU, 1976.
67    CHRISTOFIDES = 13;
68
69    // --- Path insertion heuristics ---
70    // Make all nodes inactive. Only finds a solution if nodes are optional (are
71    // element of a disjunction constraint with a finite penalty cost).
72    ALL_UNPERFORMED = 6;
73    // Iteratively build a solution by inserting the cheapest node at its
74    // cheapest position; the cost of insertion is based on the global cost
75    // function of the routing model. As of 2/2012, only works on models with
76    // optional nodes (with finite penalty costs).
77    BEST_INSERTION = 7;
78    // Iteratively build a solution by inserting the cheapest node at its
79    // cheapest position; the cost of insertion is based on the arc cost
80    // function. Is faster than BEST_INSERTION.
81    PARALLEL_CHEAPEST_INSERTION = 8;
82    // Iteratively build a solution by constructing routes sequentially, for
83    // each route inserting the cheapest node at its cheapest position until the
84    // route is completed; the cost of insertion is based on the arc cost
85    // function. Is faster than PARALLEL_CHEAPEST_INSERTION.
86    SEQUENTIAL_CHEAPEST_INSERTION = 14;
87    // Iteratively build a solution by inserting each node at its cheapest
88    // position; the cost of insertion is based on the arc cost function.
89    // Differs from PARALLEL_CHEAPEST_INSERTION by the node selected for
90    // insertion; here nodes are considered in decreasing order of distance to
91    // the start/ends of the routes, i.e. farthest nodes are inserted first.
92    // Is faster than SEQUENTIAL_CHEAPEST_INSERTION.
93    LOCAL_CHEAPEST_INSERTION = 9;
94
95    // --- Variable-based heuristics ---
96    // Iteratively connect two nodes which produce the cheapest route segment.
97    GLOBAL_CHEAPEST_ARC = 1;
98    // Select the first node with an unbound successor and connect it to the
99    // node which produces the cheapest route segment.
100    LOCAL_CHEAPEST_ARC = 2;
101    // Select the first node with an unbound successor and connect it to the
102    // first available node.
103    // This is equivalent to the CHOOSE_FIRST_UNBOUND strategy combined with
104    // ASSIGN_MIN_VALUE (cf. constraint_solver.h).
105    FIRST_UNBOUND_MIN_VALUE = 12;
106  }
107}
108
109// Local search metaheuristics used to guide the search. Apart from greedy
110// descent, they will try to escape local minima.
111message LocalSearchMetaheuristic {
112  enum Value {
113    // Means "not set". If the solver sees that, it'll behave like for
114    // AUTOMATIC. But this value won't override others upon a proto MergeFrom(),
115    // whereas "AUTOMATIC" will.
116    UNSET = 0;
117
118    // Lets the solver select the metaheuristic.
119    AUTOMATIC = 6;
120
121    // Accepts improving (cost-reducing) local search neighbors until a local
122    // minimum is reached.
123    GREEDY_DESCENT = 1;
124    // Uses guided local search to escape local minima
125    // (cf. http://en.wikipedia.org/wiki/Guided_Local_Search); this is generally
126    // the most efficient metaheuristic for vehicle routing.
127    GUIDED_LOCAL_SEARCH = 2;
128    // Uses simulated annealing to escape local minima
129    // (cf. http://en.wikipedia.org/wiki/Simulated_annealing).
130    SIMULATED_ANNEALING = 3;
131    // Uses tabu search to escape local minima
132    // (cf. http://en.wikipedia.org/wiki/Tabu_search).
133    TABU_SEARCH = 4;
134    // Uses tabu search on a list of variables to escape local minima. The list
135    // of variables to use must be provided via the SetTabuVarsCallback
136    // callback.
137    GENERIC_TABU_SEARCH = 5;
138  }
139}
140