#include <routing_search.h>

Inheritance diagram for operations_research::GlobalCheapestInsertionFilteredHeuristic:

Classes
struct	GlobalCheapestInsertionParameters

class	NodeEntryQueue

Public Member Functions
	GlobalCheapestInsertionFilteredHeuristic (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, GlobalCheapestInsertionParameters parameters)
	Takes ownership of evaluators.

	~GlobalCheapestInsertionFilteredHeuristic () override

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

Public Member Functions inherited from operations_research::RoutingFilteredHeuristic
	RoutingFilteredHeuristic (RoutingModel model, std::function< bool()> stop_search, LocalSearchFilterManager filter_manager)
	RoutingFilteredHeuristic.

	~RoutingFilteredHeuristic () override

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)

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 ()

Assignment *	BuildSolution ()

int64_t	number_of_decisions () const

int64_t	number_of_rejects () const

Additional Inherited Members
Protected Member Functions inherited from operations_research::CheapestInsertionFilteredHeuristic
std::vector< std::vector< StartEndValue > >	ComputeStartEndDistanceForVehicles (const std::vector< 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)

void	AppendInsertionPositionsAfter (int64_t node_to_insert, int64_t start, int64_t next_after_start, int vehicle, bool ignore_cost, std::vector< NodeInsertion > *node_insertions)

int64_t	GetInsertionCostForNodeAtPosition (int64_t node_to_insert, int64_t insert_after, int64_t insert_before, int vehicle) const

int64_t	GetUnperformedValue (int64_t node_to_insert) const

Protected Member Functions inherited from operations_research::RoutingFilteredHeuristic
bool	StopSearch () override
	Returns true if the search must be stopped.

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.

virtual void	Initialize ()
	Initialize the heuristic; called before starting to build a new solution.

std::optional< int64_t >	Evaluate (bool commit)

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

Protected Attributes inherited from operations_research::CheapestInsertionFilteredHeuristic
std::function< int64_t(int64_t, int64_t, int64_t)>	evaluator_

std::function< int64_t(int64_t)>	penalty_evaluator_

Protected Attributes inherited from operations_research::IntVarFilteredHeuristic
Assignment *const	assignment_

Detailed Description

Filter-based decision builder which builds a solution by inserting nodes at their cheapest position on any route; potentially several routes can be built in parallel. The cost of a position is computed from an arc-based cost callback. The node selected for insertion is the one which minimizes insertion cost. If a non null penalty evaluator is passed, making nodes unperformed is also taken into account with the corresponding penalty cost.

Definition at line 440 of file routing_search.h.

Constructor & Destructor Documentation

◆ GlobalCheapestInsertionFilteredHeuristic()

operations_research::GlobalCheapestInsertionFilteredHeuristic::GlobalCheapestInsertionFilteredHeuristic	(	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,
		GlobalCheapestInsertionParameters	parameters )

Takes ownership of evaluators.

GlobalCheapestInsertionFilteredHeuristic.

Definition at line 701 of file routing_search.cc.

◆ ~GlobalCheapestInsertionFilteredHeuristic()

operations_research::GlobalCheapestInsertionFilteredHeuristic::~GlobalCheapestInsertionFilteredHeuristic ( )

inlineoverride

Definition at line 474 of file routing_search.h.

Member Function Documentation

◆ BuildSolutionInternal()

bool operations_research::GlobalCheapestInsertionFilteredHeuristic::BuildSolutionInternal ( )

overridevirtual

Virtual method to redefine how to build a solution.

Get neighbors.

Store all empty vehicles in the empty_vehicle_type_curator_.

Insert partially inserted pairs.

Todo: (user): Adapt the pair insertions to also support seed and sequential insertion.

Implements operations_research::IntVarFilteredHeuristic.

Definition at line 741 of file routing_search.cc.

◆ DebugString()

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

inlineoverridevirtual

Reimplemented from operations_research::IntVarFilteredHeuristic.

Definition at line 476 of file routing_search.h.

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

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

Classes

Public Member Functions