Skip to main content

First solution heuristic

The first solution strategy is the algorithm the solver uses to search for an initial (first) solution. This setting can be adjusted in the solver_solver_parameters field when a request is sent. The first_solution_strategy defines the method for generating the solver's initial solution. This starting solution satisfies basic constraints, enabling the solver to begin optimization from a valid state. Selecting an appropriate first solution strategy can significantly accelerate the solution process. Only one first_solution_strategy can be specified in the Stateless API request.

Supported methods​

  • 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 - Manually setting the initial solution routes for all vehicles. This strategy is useful for cascade solutions, where the output of the previous solution is the initial solution for the next. It can also be used for testing purposes, as it can reproduce a specific initial configuration. Advantages: Fast, predictable Disadvantages: The user must provide a valid solution without conflicts. The initial solution given to the solver is the union of all first_solution lists from each vehicle. Nodes not included in any vehicle's first_solution list will be moved to rejected_bookings. Nodes invalid due to other constraints (e.g., label, geofence, capacity, time window) will also be skipped and moved to rejected. Unlike partial_route and partial_route_end, the solver may modify the first_solution during optimization. Nodes in the rejected_bookings list may also be reconsidered and re-used by the solver if a valid solution is found. **Note: If the first_solution has non-empty lists but the first_solution_strategy is not equal to EVALUATOR_STRATEGY, the solver will raise an exception.

  • 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.

  • 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 - is more efficient when logistics problems (when all pickups are located in one geographical location) are modelled as CVRPTW (prebook_cvrptw mode).