Parameters for solving the VRP problem
Solver paramters control the underlying solver behaviors and should be used only by experts.
Solver to be used for optimization. dynamic should be used for real time operations (on-demand)
Possible values: [static, dynamic]
staticThe value first_solution_strategy defines the first solution-finding strategy to be used during calculations.
0 = AUTOMATIC
1 = GLOBAL_CHEAPEST_ARC
2 = LOCAL_CHEAPEST_ARC
3 = PATH_CHEAPEST_ARC
4 = PATH_MOST_CONSTRAINED_ARC
5 = EVALUATOR_STRATEGY
6 = ALL_UNPERFORMED
7 = BEST_INSERTION
8 = PARALLEL_CHEAPEST_INSERTION
9 = LOCAL_CHEAPEST_INSERTION
10 = SAVINGS
11 = SWEEP
12 = FIRST_UNBOUND_MIN_VALUE
13 = CHRISTOFIDES
14 = SEQUENTIAL_CHEAPEST_INSERTION
16 = ADJUSTABLE_PARALLEL_CHEAPEST_INSERTION
17 = LOGISTICS_PARALLEL_CHEAPEST_INSERTION
AUTOMATIC Lets the solver detect which strategy to use according to the model being solved. May not always be the best.
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).
SEQUENTIAL_CHEAPEST_INSERTION Strategy implies an incremental first stage, which can be used to speed up the first solution for incremental solver calls. The incremental first stage tries to build the first solution based on a previous successful call to the Solver. For this to work properly, nodes, assigned during the previous API call, should be present in a list of assigned nodes in vehicles.
ADJUSTABLE_PARALLEL_CHEAPEST_INSERTION Strategy implies an incremental first stage, which can be used to speed up the first solution for incremental solver calls. The incremental first stage tries to build the first solution based on a previous successful call to the Solver. For this to work properly, nodes, assigned during the previous API call, should be present in a list of assigned nodes in vehicles.
LOGISTICS_PARALLEL_CHEAPEST_INSERTION Strategy is more efficient when logistics problems (when all pickups are located in one geographical location) are modelled as PDPTW ("prebook" mode).
0Limit to the number of solutions generated during the search.
10000000Flag that enables using local search metaheuristic
falseParameter of the local search procedure.
0.1Flag that enables TSP optimization.
falseLimit in ms to the time spent in the search.
10000000Flag that enables log search.
falseLimit in ms to the time spent in the completion search for each local search neighbor.
1000Savings neighbors ratio
0Enables second phase waypoints optimization for prebook.
falseWaypoints solution limit in second phase.
1000Minimum step by which the solution must be improved in local search.
1Use all local search operators.
falseIf True, the solver should use depth-first search rather than local search to solve the problem.
falseList of additional local search operator names. Currently supported: extended_swap_active that improves solutions when waypoints are used;
logistics_relocate_pair that improves performance when logistics problem is solved in prebook mode.
Possible values: [extended_swap_active, logistics_relocate_pair]
First solution strategies for second stage (Only one of them is used)
Maximum calculation time for second stage in milliseconds
{
"algorithm": "static",
"first_solution_strategy": 0,
"solution_limit": 10000000,
"use_local_search_metaheuristic": false,
"guided_local_search_lambda_coefficient": 0.1,
"use_tsp_opt": false,
"time_limit_ms": 10000000,
"log_search": false,
"lns_time_limit_ms": 1000,
"savings_neighbors_ratio": 0,
"waypoints_optimization_second_phase": false,
"waypoints_solution_limit": 1000,
"optimization_step": 1,
"use_all_local_search_operators": false,
"use_depth_first_search": false,
"use_local_search_operators": [
"extended_swap_active"
],
"first_solution_strategies_second_stage:": [
0
],
"time_limit_ms_second_stage": 0
}