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 405 of file routing_search.h.

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

	~GlobalCheapestInsertionFilteredHeuristic () override=default

bool	BuildSolutionInternal () override
	Virtual method to redefine how to build a solution. More...

std::string	DebugString () const override

template<class Queue >
void	InitializePriorityQueue (std::vector< std::vector< StartEndValue >> start_end_distances_per_node, Queue priority_queue)

const Assignment *	BuildSolutionFromRoutes (const std::function< int64_t(int64_t)> &next_accessor)
	Builds a solution starting from the routes formed by the next accessor. More...

RoutingModel *	model () const

int	GetStartChainEnd (int vehicle) const
	Returns the end of the start chain of vehicle,. More...

int	GetEndChainStart (int vehicle) const
	Returns the start of the end chain of vehicle,. More...

void	MakeDisjunctionNodesUnperformed (int64_t node)
	Make nodes in the same disjunction as 'node' unperformed. More...

bool	MakeUnassignedNodesUnperformed ()
	Make all unassigned nodes unperformed, always returns true. More...

void	MakePartiallyPerformedPairsUnperformed ()
	Make all partially performed pickup and delivery pairs unperformed. More...

Assignment *const	BuildSolution ()
	Builds a solution. More...

int64_t	number_of_decisions () const
	Returns statistics on search, number of decisions sent to filters, number of decisions rejected by filters. More...

int64_t	number_of_rejects () const

Protected Types
typedef std::pair< StartEndValue, int >	Seed

Protected Member Functions
std::vector< std::vector< StartEndValue > >	ComputeStartEndDistanceForVehicles (const std::vector< int > &vehicles)
	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. More...

template<class Queue >
void	InitializePriorityQueue (std::vector< std::vector< StartEndValue > > start_end_distances_per_node, Queue priority_queue)
	Initializes the priority_queue by inserting the best entry corresponding to each node, i.e. More...

void	InsertBetween (int64_t node, int64_t predecessor, int64_t successor, int vehicle=-1)
	Inserts 'node' just after 'predecessor', and just before 'successor' on the route of 'vehicle', resulting in the following subsequence: predecessor -> node -> successor. More...

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)
	Helper method to the ComputeEvaluatorSortedPositions* methods. More...

int64_t	GetInsertionCostForNodeAtPosition (int64_t node_to_insert, int64_t insert_after, int64_t insert_before, int vehicle) const
	Returns the cost of inserting 'node_to_insert' between 'insert_after' and 'insert_before' on the 'vehicle', i.e. More...

int64_t	GetUnperformedValue (int64_t node_to_insert) const
	Returns the cost of unperforming node 'node_to_insert'. More...

bool	StopSearch () override
	Returns true if the search must be stopped. More...

bool	VehicleIsEmpty (int vehicle) const

void	ResetSolution ()
	Resets the data members for a new solution. More...

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

std::optional< int64_t >	Evaluate (bool commit)
	Evaluates the modifications to the current solution. More...

void	SetValue (int64_t index, int64_t value)
	Modifies the current solution by setting the variable of index 'index' to value 'value'. More...

int64_t	Value (int64_t index) const
	Returns the value of the variable of index 'index' in the last committed solution. More...

bool	Contains (int64_t index) const
	Returns true if the variable of index 'index' is in the current solution. More...

int	Size () const
	Returns the number of variables the decision builder is trying to instantiate. More...

IntVar *	Var (int64_t index) const
	Returns the variable of index 'index'. More...

int64_t	SecondaryVarIndex (int64_t index) const
	Returns the index of a secondary var. More...

bool	HasSecondaryVars () const
	Returns true if there are secondary variables. More...

bool	IsSecondaryVar (int64_t index) const
	Returns true if 'index' is a secondary variable index. More...

void	SynchronizeFilters ()
	Synchronizes filters with an assignment (the current solution). More...

Protected Attributes
std::function< int64_t(int64_t, int64_t, int64_t)>	evaluator_

std::function< int64_t(int64_t)>	penalty_evaluator_

Assignment *const	assignment_

Member Typedef Documentation

◆ Seed

typedef std::pair<StartEndValue, int> Seed

protectedinherited

Definition at line 344 of file routing_search.h.

Constructor & Destructor Documentation

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

Definition at line 684 of file routing_search.cc.

◆ ~GlobalCheapestInsertionFilteredHeuristic()

~GlobalCheapestInsertionFilteredHeuristic ( )

overridedefault

Member Function Documentation

◆ AppendInsertionPositionsAfter()

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
	)

protectedinherited

Helper method to the ComputeEvaluatorSortedPositions* methods.

Finds all possible insertion positions of node 'node_to_insert' in the partial route starting at node 'start' and adds them to 'node_insertions' (no sorting is done). If ignore_cost is true, insertion costs may not be computed.

Definition at line 638 of file routing_search.cc.

◆ BuildSolution()

Assignment *const BuildSolution ( )

inherited

Builds a solution.

Returns the resulting assignment if a solution was found, and nullptr otherwise.

Definition at line 303 of file routing_search.cc.

◆ BuildSolutionFromRoutes()

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

inherited

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

Definition at line 316 of file routing_search.cc.

◆ BuildSolutionInternal()

bool BuildSolutionInternal ( )

overridevirtual

Virtual method to redefine how to build a solution.

Implements IntVarFilteredHeuristic.

Definition at line 734 of file routing_search.cc.

◆ ComputeStartEndDistanceForVehicles()

std::vector< std::vector< CheapestInsertionFilteredHeuristic::StartEndValue > > ComputeStartEndDistanceForVehicles ( const std::vector< int > & vehicles )

protectedinherited

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.

Definition at line 551 of file routing_search.cc.

◆ Contains()

bool Contains ( int64_t index ) const

inlineprotectedinherited

Returns true if the variable of index 'index' is in the current solution.

Definition at line 226 of file routing_search.h.

◆ DebugString()

std::string DebugString ( ) const

inlineoverridevirtual

Reimplemented from IntVarFilteredHeuristic.

Definition at line 441 of file routing_search.h.

◆ Evaluate()

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

protectedinherited

Evaluates the modifications to the current solution.

If these modifications are "filter-feasible" returns their corresponding cost computed by filters. If 'commit' is true, the modifications are committed to the current solution. In any case all modifications to the internal delta are cleared before returning.

Definition at line 353 of file routing_search.cc.

◆ GetEndChainStart()

int GetEndChainStart ( int vehicle ) const

inlineinherited

Returns the start of the end chain of vehicle,.

Definition at line 282 of file routing_search.h.

◆ GetInsertionCostForNodeAtPosition()

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

protectedinherited

Returns the cost of inserting 'node_to_insert' between 'insert_after' and 'insert_before' on the 'vehicle', i.e.

Cost(insert_after-->node) + Cost(node-->insert_before)

Cost (insert_after-->insert_before).

Definition at line 665 of file routing_search.cc.

◆ GetStartChainEnd()

int GetStartChainEnd ( int vehicle ) const

inlineinherited

Returns the end of the start chain of vehicle,.

Definition at line 280 of file routing_search.h.

◆ GetUnperformedValue()

int64_t GetUnperformedValue ( int64_t node_to_insert ) const

protectedinherited

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 674 of file routing_search.cc.

◆ HasSecondaryVars()

bool HasSecondaryVars ( ) const

inlineprotectedinherited

Returns true if there are secondary variables.

Definition at line 240 of file routing_search.h.

◆ Initialize()

virtual void Initialize ( )

inlineprotectedvirtualinherited

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

Reimplemented in LocalCheapestInsertionFilteredHeuristic.

Definition at line 194 of file routing_search.h.

◆ InitializePriorityQueue() [1/2]

void InitializePriorityQueue	(	std::vector< std::vector< StartEndValue > > *	start_end_distances_per_node,
		Queue *	priority_queue
	)

protectedinherited

Initializes the 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. Queue is a priority queue containing Seeds.

◆ InitializePriorityQueue() [2/2]

void InitializePriorityQueue	(	std::vector< std::vector< StartEndValue >> *	start_end_distances_per_node,
		Queue *	priority_queue
	)

inherited

Definition at line 604 of file routing_search.cc.

◆ InsertBetween()

void InsertBetween	(	int64_t	node,
		int64_t	predecessor,
		int64_t	successor,
		int	vehicle = `-1`
	)

protectedinherited

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 624 of file routing_search.cc.

◆ IsSecondaryVar()

bool IsSecondaryVar ( int64_t index ) const

inlineprotectedinherited

Returns true if 'index' is a secondary variable index.

Definition at line 242 of file routing_search.h.

◆ MakeDisjunctionNodesUnperformed()

void MakeDisjunctionNodesUnperformed ( int64_t node )

inherited

Make nodes in the same disjunction as 'node' unperformed.

'node' is a variable index corresponding to a node.

Definition at line 477 of file routing_search.cc.

◆ MakePartiallyPerformedPairsUnperformed()

void MakePartiallyPerformedPairsUnperformed ( )

inherited

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 499 of file routing_search.cc.

◆ MakeUnassignedNodesUnperformed()

bool MakeUnassignedNodesUnperformed ( )

inherited

Make all unassigned nodes unperformed, always returns true.

Definition at line 486 of file routing_search.cc.

◆ model()

RoutingModel* model ( ) const

inlineinherited

Definition at line 278 of file routing_search.h.

◆ number_of_decisions()

int64_t number_of_decisions ( ) const

inlineinherited

Returns statistics on search, number of decisions sent to filters, number of decisions rejected by filters.

Definition at line 185 of file routing_search.h.

◆ number_of_rejects()

int64_t number_of_rejects ( ) const

inlineinherited

Definition at line 186 of file routing_search.h.

◆ ResetSolution()

void ResetSolution ( )

protectedinherited

Resets the data members for a new solution.

Definition at line 293 of file routing_search.cc.

◆ SecondaryVarIndex()

int64_t SecondaryVarIndex ( int64_t index ) const

inlineprotectedinherited

Returns the index of a secondary var.

Definition at line 235 of file routing_search.h.

◆ SetValue()

void SetValue	(	int64_t	index,
		int64_t	value
	)

inlineprotectedinherited

Modifies the current solution by setting the variable of index 'index' to value 'value'.

Definition at line 211 of file routing_search.h.

◆ Size()

int Size ( ) const

inlineprotectedinherited

Returns the number of variables the decision builder is trying to instantiate.

Definition at line 231 of file routing_search.h.

◆ StopSearch()

bool StopSearch ( )

inlineoverrideprotectedvirtualinherited

Returns true if the search must be stopped.

Reimplemented from IntVarFilteredHeuristic.

Definition at line 295 of file routing_search.h.

◆ SynchronizeFilters()

void SynchronizeFilters ( )

protectedinherited

Synchronizes filters with an assignment (the current solution).

Definition at line 396 of file routing_search.cc.

◆ Value()

int64_t Value ( int64_t index ) const

inlineprotectedinherited

Returns the value of the variable of index 'index' in the last committed solution.

Definition at line 222 of file routing_search.h.

◆ Var()

IntVar* Var ( int64_t index ) const

inlineprotectedinherited

Returns the variable of index 'index'.

Definition at line 233 of file routing_search.h.

◆ VehicleIsEmpty()

bool VehicleIsEmpty ( int vehicle ) const

inlineprotectedinherited

Definition at line 298 of file routing_search.h.

Member Data Documentation

◆ assignment_

Assignment* const assignment_

protectedinherited

Definition at line 246 of file routing_search.h.

◆ evaluator_

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

protectedinherited

Definition at line 394 of file routing_search.h.

◆ penalty_evaluator_

std::function<int64_t(int64_t)> penalty_evaluator_

protectedinherited

Definition at line 395 of file routing_search.h.

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

Detailed Description

Classes

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Member Typedef Documentation

◆ Seed

Constructor & Destructor Documentation

◆ GlobalCheapestInsertionFilteredHeuristic()

◆ ~GlobalCheapestInsertionFilteredHeuristic()

Member Function Documentation

◆ AppendInsertionPositionsAfter()

◆ BuildSolution()

◆ BuildSolutionFromRoutes()

◆ BuildSolutionInternal()

◆ ComputeStartEndDistanceForVehicles()

◆ Contains()

◆ DebugString()

◆ Evaluate()

◆ GetEndChainStart()

◆ GetInsertionCostForNodeAtPosition()

◆ GetStartChainEnd()

◆ GetUnperformedValue()

◆ HasSecondaryVars()

◆ Initialize()

◆ InitializePriorityQueue() [1/2]

◆ InitializePriorityQueue() [2/2]

◆ InsertBetween()

◆ IsSecondaryVar()

◆ MakeDisjunctionNodesUnperformed()

◆ MakePartiallyPerformedPairsUnperformed()

◆ MakeUnassignedNodesUnperformed()

◆ model()

◆ number_of_decisions()

◆ number_of_rejects()

◆ ResetSolution()

◆ SecondaryVarIndex()

◆ SetValue()

◆ Size()

◆ StopSearch()

◆ SynchronizeFilters()

◆ Value()

◆ Var()

◆ VehicleIsEmpty()

Member Data Documentation

◆ assignment_

◆ evaluator_

◆ penalty_evaluator_