Filter-based heuristic dedicated to routing. More...

#include <routing_search.h>

Inheritance diagram for operations_research::RoutingFilteredHeuristic:

Public Member Functions
	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

virtual std::string	DebugString () const

Protected Member Functions
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.

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

virtual bool	BuildSolutionInternal ()=0
	Virtual method to redefine how to build a 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).

Additional Inherited Members
Protected Attributes inherited from operations_research::IntVarFilteredHeuristic
Assignment *const	assignment_

Detailed Description

Filter-based heuristic dedicated to routing.

Definition at line 271 of file routing_search.h.

Constructor & Destructor Documentation

◆ RoutingFilteredHeuristic()

operations_research::RoutingFilteredHeuristic::RoutingFilteredHeuristic	(	RoutingModel *	model,
		std::function< bool()>	stop_search,
		LocalSearchFilterManager *	filter_manager )

RoutingFilteredHeuristic.

Definition at line 409 of file routing_search.cc.

◆ ~RoutingFilteredHeuristic()

operations_research::RoutingFilteredHeuristic::~RoutingFilteredHeuristic ( )

inlineoverride

Definition at line 276 of file routing_search.h.

Member Function Documentation

◆ BuildSolutionFromRoutes()

Assignment * operations_research::RoutingFilteredHeuristic::BuildSolutionFromRoutes ( const std::function< int64_t(int64_t)> & next_accessor )

Builds a solution starting from the routes formed by the next accessor.

Initialize must be called before the state of the heuristic is changed, in particular before InitializeSolution() and BuildSolutionInternal().

NOTE(b/219043402): The filter manager must first be synchronized with a valid solution that properly connects route starts to route ends in order for future FilterAccept() calls to correctly detect infeasibilities.

Definition at line 318 of file routing_search.cc.

◆ GetEndChainStart()

int operations_research::RoutingFilteredHeuristic::GetEndChainStart ( int vehicle ) const

inline

Returns the start of the end chain of vehicle,.

Definition at line 284 of file routing_search.h.

◆ GetStartChainEnd()

int operations_research::RoutingFilteredHeuristic::GetStartChainEnd ( int vehicle ) const

inline

Returns the end of the start chain of vehicle,.

Definition at line 282 of file routing_search.h.

◆ MakeDisjunctionNodesUnperformed()

void operations_research::RoutingFilteredHeuristic::MakeDisjunctionNodesUnperformed ( int64_t node )

Make nodes in the same disjunction as 'node' unperformed. 'node' is a variable index corresponding to a node.

Definition at line 464 of file routing_search.cc.

◆ MakePartiallyPerformedPairsUnperformed()

void operations_research::RoutingFilteredHeuristic::MakePartiallyPerformedPairsUnperformed ( )

Make all partially performed pickup and delivery pairs unperformed. A pair is partially unperformed if one element of the pair has one of its alternatives performed in the solution and the other has no alternatives in the solution or none performed.

Definition at line 485 of file routing_search.cc.

◆ MakeUnassignedNodesUnperformed()

bool operations_research::RoutingFilteredHeuristic::MakeUnassignedNodesUnperformed ( )

Make all unassigned nodes unperformed, always returns true.

Todo: (user): check that delta_ is empty.

Definition at line 473 of file routing_search.cc.

◆ model()

RoutingModel * operations_research::RoutingFilteredHeuristic::model ( ) const

inline

Definition at line 280 of file routing_search.h.

◆ ResetVehicleIndices()

virtual void operations_research::RoutingFilteredHeuristic::ResetVehicleIndices ( )

inlineprotectedvirtual

Definition at line 299 of file routing_search.h.

◆ SetNext()

void operations_research::RoutingFilteredHeuristic::SetNext	(	int64_t	node,
		int64_t	next,
		int	vehicle )

inlineprotected

Definition at line 303 of file routing_search.h.

◆ SetVehicleIndex()

virtual void operations_research::RoutingFilteredHeuristic::SetVehicleIndex	(	int64_t	,
		int	)

inlineprotectedvirtual

Definition at line 298 of file routing_search.h.

◆ StopSearch()

bool operations_research::RoutingFilteredHeuristic::StopSearch ( )

inlineoverrideprotectedvirtual

Returns true if the search must be stopped.

Reimplemented from operations_research::IntVarFilteredHeuristic.

Definition at line 297 of file routing_search.h.

◆ VehicleIsEmpty()

bool operations_research::RoutingFilteredHeuristic::VehicleIsEmpty ( int vehicle ) const

inlineprotected

Definition at line 300 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

Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ RoutingFilteredHeuristic()

◆ ~RoutingFilteredHeuristic()

Member Function Documentation

◆ BuildSolutionFromRoutes()

◆ GetEndChainStart()

◆ GetStartChainEnd()

◆ MakeDisjunctionNodesUnperformed()

◆ MakePartiallyPerformedPairsUnperformed()

◆ MakeUnassignedNodesUnperformed()

◆ model()

◆ ResetVehicleIndices()

◆ SetNext()

◆ SetVehicleIndex()

◆ StopSearch()

◆ VehicleIsEmpty()