Detailed Description

Filter-based decision builder which builds a solution by inserting nodes at their cheapest position. The cost of a position is computed an arc-based cost callback. Node selected for insertion are considered in decreasing order of distance to the start/ends of the routes, i.e. farthest nodes are inserted first.

Definition at line 1134 of file routing_search.h.

#include <routing_search.h>

Inheritance diagram for operations_research::LocalCheapestInsertionFilteredHeuristic:

Public Member Functions
	LocalCheapestInsertionFilteredHeuristic (RoutingModel model, std::function< bool()> stop_search, std::function< int64_t(int64_t, int64_t, int64_t)> evaluator, RoutingSearchParameters::PairInsertionStrategy pair_insertion_strategy, std::vector< RoutingSearchParameters::InsertionSortingProperty > insertion_sorting_properties, LocalSearchFilterManager filter_manager, bool use_first_solution_hint, BinCapacities bin_capacities=nullptr, std::function< bool(const std::vector< RoutingModel::VariableValuePair > &, std::vector< RoutingModel::VariableValuePair > )> optimize_on_insertion=nullptr)
	Takes ownership of evaluator.
	~LocalCheapestInsertionFilteredHeuristic () override=default
bool	BuildSolutionInternal () override
	Virtual method to redefine how to build a solution.
std::string	DebugString () const override
Public Member Functions inherited from operations_research::CheapestInsertionFilteredHeuristic
	CheapestInsertionFilteredHeuristic (RoutingModel model, std::function< bool()> stop_search, std::function< int64_t(int64_t, int64_t, int64_t)> evaluator, std::function< int64_t(int64_t)> penalty_evaluator, LocalSearchFilterManager filter_manager)
	Takes ownership of evaluator.
	~CheapestInsertionFilteredHeuristic () override=default
Public Member Functions inherited from operations_research::RoutingFilteredHeuristic
	RoutingFilteredHeuristic (RoutingModel model, std::function< bool()> stop_search, LocalSearchFilterManager filter_manager)
	RoutingFilteredHeuristic.
	~RoutingFilteredHeuristic () override=default
Assignment *	BuildSolutionFromRoutes (const std::function< int64_t(int64_t)> &next_accessor)
	Builds a solution starting from the routes formed by the next accessor.
RoutingModel *	model () const
int	GetStartChainEnd (int vehicle) const
	Returns the end of the start chain of vehicle,.
int	GetEndChainStart (int vehicle) const
	Returns the start of the end chain of vehicle,.
void	MakeDisjunctionNodesUnperformed (int64_t node)
void	AddUnassignedNodesToEmptyVehicles ()
	Adds all unassigned nodes to empty vehicles.
bool	MakeUnassignedNodesUnperformed ()
	Make all unassigned nodes unperformed, always returns true.
void	MakePartiallyPerformedPairsUnperformed ()
Public Member Functions inherited from operations_research::IntVarFilteredHeuristic
	IntVarFilteredHeuristic (Solver solver, const std::vector< IntVar > &vars, const std::vector< IntVar * > &secondary_vars, LocalSearchFilterManager *filter_manager)
	— First solution heuristics —
virtual	~IntVarFilteredHeuristic ()=default
Assignment *	BuildSolution ()
int64_t	number_of_decisions () const
int64_t	number_of_rejects () const

Protected Member Functions
void	Initialize () override
	Initialize the heuristic; called before starting to build a new solution.
Protected Member Functions inherited from operations_research::CheapestInsertionFilteredHeuristic
std::vector< std::vector< StartEndValue > >	ComputeStartEndDistanceForVehicles (absl::Span< const int > vehicles)
void	InitializeSeedQueue (std::vector< std::vector< StartEndValue > > start_end_distances_per_node, SeedQueue sq)
void	AddSeedNodeToQueue (int node, std::vector< StartEndValue > start_end_distances, SeedQueue sq)
	clang-format on
void	InsertBetween (int64_t node, int64_t predecessor, int64_t successor, int vehicle=-1)
int64_t	GetEvaluatorInsertionCostForNodeAtPosition (int64_t node_to_insert, int64_t insert_after, int64_t insert_before, int vehicle) const
std::optional< int64_t >	GetInsertionCostForNodeAtPosition (int64_t node_to_insert, int64_t insert_after, int64_t insert_before, int vehicle, int hint_weight=0)
std::optional< int64_t >	GetInsertionCostForPairAtPositions (int64_t pickup_to_insert, int64_t pickup_insert_after, int64_t delivery_to_insert, int64_t delivery_insert_after, int vehicle, int hint_weight=0)
int64_t	GetUnperformedValue (int64_t node_to_insert) const
bool	HasHintedNext (int node) const
bool	HasHintedPrev (int node) const
bool	IsHint (int node, int64_t next) const
Protected Member Functions inherited from operations_research::RoutingFilteredHeuristic
bool	StopSearch () override
	Returns true if the search must be stopped.
virtual void	SetVehicleIndex (int64_t, int)
virtual void	ResetVehicleIndices ()
bool	VehicleIsEmpty (int vehicle) const
void	SetNext (int64_t node, int64_t next, int vehicle)
Protected Member Functions inherited from operations_research::IntVarFilteredHeuristic
void	ResetSolution ()
	Resets the data members for a new solution.
std::optional< int64_t >	Evaluate (bool commit, bool ignore_upper_bound=false, bool update_upper_bound=true)
void	SetValue (int64_t index, int64_t value)
const std::vector< int > &	delta_indices () const
	Returns the indices of the nodes currently in the insertion delta.
int64_t	Value (int64_t index) const
bool	Contains (int64_t index) const
	Returns true if the variable of index 'index' is in the current solution.
IntVar *	Var (int64_t index) const
	Returns the variable of index 'index'.
int64_t	SecondaryVarIndex (int64_t index) const
	Returns the index of a secondary var.
bool	HasSecondaryVars () const
	Returns true if there are secondary variables.
bool	IsSecondaryVar (int64_t index) const
	Returns true if 'index' is a secondary variable index.
void	SynchronizeFilters ()
	Synchronizes filters with an assignment (the current solution).

Additional Inherited Members
Protected Attributes inherited from operations_research::CheapestInsertionFilteredHeuristic
std::function< int64_t(int64_t, int64_t, int64_t)>	evaluator_
std::vector< EvaluatorCache >	evaluator_cache_
std::function< int64_t(int64_t)>	penalty_evaluator_
std::vector< int >	hint_next_values_
std::vector< int >	hint_prev_values_
Protected Attributes inherited from operations_research::IntVarFilteredHeuristic
Assignment *const	assignment_

Constructor & Destructor Documentation

◆ LocalCheapestInsertionFilteredHeuristic()

operations_research::LocalCheapestInsertionFilteredHeuristic::LocalCheapestInsertionFilteredHeuristic	(	RoutingModel *	model,
		std::function< bool()>	stop_search,
		std::function< int64_t(int64_t, int64_t, int64_t)>	evaluator,
		RoutingSearchParameters::PairInsertionStrategy	pair_insertion_strategy,
		std::vector< RoutingSearchParameters::InsertionSortingProperty >	insertion_sorting_properties,
		LocalSearchFilterManager *	filter_manager,
		bool	use_first_solution_hint,
		BinCapacities *	bin_capacities = nullptr,
		std::function< bool(const std::vector< RoutingModel::VariableValuePair > &, std::vector< RoutingModel::VariableValuePair > *)>	optimize_on_insertion = nullptr )

Takes ownership of evaluator.

LocalCheapestInsertionFilteredHeuristic

Todo: (user): Add support for penalty costs.

Definition at line 2510 of file routing_search.cc.

◆ ~LocalCheapestInsertionFilteredHeuristic()

operations_research::LocalCheapestInsertionFilteredHeuristic::~LocalCheapestInsertionFilteredHeuristic ( )

overridedefault

Member Function Documentation

◆ BuildSolutionInternal()

bool operations_research::LocalCheapestInsertionFilteredHeuristic::BuildSolutionInternal ( )

overridevirtual

Virtual method to redefine how to build a solution.

Fill vehicle bins with nodes that are already inserted.

Either both pickup and delivery are already inserted for this pair, or neither are inserted and should be considered as pair. In both cases, the nodes in the pickup/delivery alternatives shouldn't be considered for insertion as single nodes.

Capturing the state of the delta before it gets wiped by Evaluate.

Implements operations_research::IntVarFilteredHeuristic.

Definition at line 3274 of file routing_search.cc.

◆ DebugString()

std::string operations_research::LocalCheapestInsertionFilteredHeuristic::DebugString ( ) const

inlineoverridevirtual

Reimplemented from operations_research::IntVarFilteredHeuristic.

Definition at line 1151 of file routing_search.h.

◆ Initialize()

void operations_research::LocalCheapestInsertionFilteredHeuristic::Initialize ( )

overrideprotectedvirtual

Initialize the heuristic; called before starting to build a new solution.

NOTE(user): Keeping the code in a separate function as opposed to inlining here, to allow for future additions to this function.

Reimplemented from operations_research::IntVarFilteredHeuristic.

Definition at line 2537 of file routing_search.cc.

The documentation for this class was generated from the following files:

ortools/constraint_solver/routing_search.h
ortools/constraint_solver/routing_search.cc