Detailed Description

Definition at line 365 of file routing_search.h.

#include <routing_search.h>

Inheritance diagram for operations_research::CheapestInsertionFilteredHeuristic:

Classes
struct	EvaluatorCache
struct	Seed
struct	SeedQueue
	clang-format off More...
struct	StartEndValue

Public Member Functions
	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
virtual std::string	DebugString () const

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

Protected Attributes
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

◆ CheapestInsertionFilteredHeuristic()

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.

Definition at line 749 of file routing_search.cc.

◆ ~CheapestInsertionFilteredHeuristic()

operations_research::CheapestInsertionFilteredHeuristic::~CheapestInsertionFilteredHeuristic ( )

overridedefault

Member Function Documentation

◆ AddSeedNodeToQueue()

void operations_research::CheapestInsertionFilteredHeuristic::AddSeedNodeToQueue	(	int	node,
		std::vector< StartEndValue > *	start_end_distances,
		SeedQueue *	sq )

protected

clang-format on

Adds a Seed corresponding to the given 'node' to sq.priority_queue, based on the last entry in its 'start_end_distances' (from which it's deleted).

Put the best StartEndValue for this node in the priority queue.

Definition at line 831 of file routing_search.cc.

◆ ComputeStartEndDistanceForVehicles()

std::vector< std::vector< CheapestInsertionFilteredHeuristic::StartEndValue > > operations_research::CheapestInsertionFilteredHeuristic::ComputeStartEndDistanceForVehicles ( absl::Span< const int > vehicles )

protected

Computes and returns the distance of each uninserted node to every vehicle in 'vehicles' as a std::vector<std::vector<StartEndValue>>, start_end_distances_per_node. For each node, start_end_distances_per_node[node] is sorted in decreasing order.

Todo: (user): consider checking search limits.

Sort the distances for the node to all start/ends of available vehicles in decreasing order.

Definition at line 796 of file routing_search.cc.

◆ GetEvaluatorInsertionCostForNodeAtPosition()

int64_t operations_research::CheapestInsertionFilteredHeuristic::GetEvaluatorInsertionCostForNodeAtPosition	(	int64_t	node_to_insert,
		int64_t	insert_after,
		int64_t	insert_before,
		int	vehicle ) const

protected

Returns the cost of inserting 'node_to_insert' between 'insert_after' and 'insert_before' on the 'vehicle' when the evaluator_ is defined, i.e. evaluator_(insert_after-->node) + evaluator_(node-->insert_before)

evaluator_(insert_after-->insert_before).
Todo
(user): Replace 'insert_before' and 'insert_after' by 'predecessor' and 'successor' in the code.

Definition at line 879 of file routing_search.cc.

◆ GetInsertionCostForNodeAtPosition()

std::optional< int64_t > operations_research::CheapestInsertionFilteredHeuristic::GetInsertionCostForNodeAtPosition	(	int64_t	node_to_insert,
		int64_t	insert_after,
		int64_t	insert_before,
		int	vehicle,
		int	hint_weight = 0 )

protected

Same as above, except that when the evaluator_ is not defined, the cost is determined by Evaluate-ing the insertion of the node through the filter manager, returning std::nullopt when the insertion is not feasible.

Definition at line 895 of file routing_search.cc.

◆ GetInsertionCostForPairAtPositions()

std::optional< int64_t > operations_research::CheapestInsertionFilteredHeuristic::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 )

protected

Same as above for the insertion of a pickup/delivery pair at the given positions.

Definition at line 908 of file routing_search.cc.

◆ GetUnperformedValue()

int64_t operations_research::CheapestInsertionFilteredHeuristic::GetUnperformedValue ( int64_t node_to_insert ) const

protected

Returns the cost of unperforming node 'node_to_insert'. Returns kint64max if penalty callback is null or if the node cannot be unperformed.

Definition at line 933 of file routing_search.cc.

◆ HasHintedNext()

bool operations_research::CheapestInsertionFilteredHeuristic::HasHintedNext ( int node ) const

inlineprotected

Definition at line 476 of file routing_search.h.

◆ HasHintedPrev()

bool operations_research::CheapestInsertionFilteredHeuristic::HasHintedPrev ( int node ) const

inlineprotected

Definition at line 480 of file routing_search.h.

◆ InitializeSeedQueue()

void operations_research::CheapestInsertionFilteredHeuristic::InitializeSeedQueue	(	std::vector< std::vector< StartEndValue > > *	start_end_distances_per_node,
		SeedQueue *	sq )

protected

Initializes sq->priority_queue by inserting the best entry corresponding to each node, i.e. the last element of start_end_distances_per_node[node], which is supposed to be sorted in decreasing order.

Definition at line 852 of file routing_search.cc.

◆ InsertBetween()

void operations_research::CheapestInsertionFilteredHeuristic::InsertBetween	(	int64_t	node,
		int64_t	predecessor,
		int64_t	successor,
		int	vehicle = -1 )

protected

Inserts 'node' just after 'predecessor', and just before 'successor' on the route of 'vehicle', resulting in the following subsequence: predecessor -> node -> successor. If 'node' is part of a disjunction, other nodes of the disjunction are made unperformed.

Definition at line 864 of file routing_search.cc.

◆ IsHint()

bool operations_research::CheapestInsertionFilteredHeuristic::IsHint	(	int	node,
		int64_t	next ) const

inlineprotected

Definition at line 484 of file routing_search.h.

Member Data Documentation

◆ evaluator_

std::function<int64_t(int64_t, int64_t, int64_t)> operations_research::CheapestInsertionFilteredHeuristic::evaluator_

protected

Definition at line 488 of file routing_search.h.

◆ evaluator_cache_

std::vector<EvaluatorCache> operations_research::CheapestInsertionFilteredHeuristic::evaluator_cache_

mutableprotected

Todo: (user): Remove mutable if possible.

Definition at line 490 of file routing_search.h.

◆ hint_next_values_

std::vector<int> operations_research::CheapestInsertionFilteredHeuristic::hint_next_values_

protected

Definition at line 492 of file routing_search.h.

◆ hint_prev_values_

std::vector<int> operations_research::CheapestInsertionFilteredHeuristic::hint_prev_values_

protected

Definition at line 493 of file routing_search.h.

◆ penalty_evaluator_

std::function<int64_t(int64_t)> operations_research::CheapestInsertionFilteredHeuristic::penalty_evaluator_

protected

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

Detailed Description

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Constructor & Destructor Documentation

◆ CheapestInsertionFilteredHeuristic()

◆ ~CheapestInsertionFilteredHeuristic()

Member Function Documentation

◆ AddSeedNodeToQueue()

◆ ComputeStartEndDistanceForVehicles()

◆ GetEvaluatorInsertionCostForNodeAtPosition()

◆ GetInsertionCostForNodeAtPosition()

◆ GetInsertionCostForPairAtPositions()

◆ GetUnperformedValue()

◆ HasHintedNext()

◆ HasHintedPrev()

◆ InitializeSeedQueue()

◆ InsertBetween()

◆ IsHint()

Member Data Documentation

◆ evaluator_

◆ evaluator_cache_

◆ hint_next_values_

◆ hint_prev_values_

◆ penalty_evaluator_