Detailed Description

template<bool ignore_path_vars>
class operations_research::PairRelocateOperator< ignore_path_vars >

Operator which moves a pair of nodes to another position where the first node of the pair must be before the second node on the same path. Possible neighbors for the path 1 -> A -> B -> 2 -> 3 (where (1, 3) are first and last nodes of the path and can therefore not be moved, and (A, B) is a pair of nodes): 1 -> [A] -> 2 -> [B] -> 3 1 -> 2 -> [A] -> [B] -> 3 The pair can be moved to another path.

Definition at line 322 of file routing_neighborhoods.h.

#include <routing_neighborhoods.h>

Inheritance diagram for operations_research::PairRelocateOperator< ignore_path_vars >:

Public Member Functions
	PairRelocateOperator (const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)
	~PairRelocateOperator () override=default
bool	MakeNeighbor () override
std::string	DebugString () const override
Public Member Functions inherited from operations_research::PathOperator< ignore_path_vars >
	PathOperator (const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, IterationParameters iteration_parameters)
	Builds an instance of PathOperator from next and path variables.
	PathOperator (const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, int number_of_base_nodes, bool skip_locally_optimal_paths, bool accept_path_end_base, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors)
	~PathOperator () override
void	EnterSearch () override
void	Reset () override
bool	SkipUnchanged (int index) const override
int64_t	Next (int64_t node) const
	Returns the node after node in the current delta.
int64_t	Prev (int64_t node) const
	Returns the node before node in the current delta.
int64_t	Path (int64_t node) const
int	number_of_nexts () const
	Number of next variables.
Public Member Functions inherited from operations_research::IntVarLocalSearchOperator
	IntVarLocalSearchOperator (const std::vector< IntVar * > &vars, bool keep_inverse_values=false)
	~IntVarLocalSearchOperator () override
bool	HoldsDelta () const override
void	Start (const Assignment *assignment) override
virtual bool	IsIncremental () const
int	Size () const
int64_t	Value (int64_t index) const
IntVar *	Var (int64_t index) const
	Returns the variable of given index.
int64_t	OldValue (int64_t index) const
int64_t	PrevValue (int64_t index) const
void	SetValue (int64_t index, int64_t value)
bool	Activated (int64_t index) const
void	Activate (int64_t index)
void	Deactivate (int64_t index)
bool	ApplyChanges (Assignment delta, Assignment deltadelta) const
void	RevertChanges (bool change_was_incremental)
void	AddVars (const std::vector< IntVar * > &vars)
bool	MakeNextNeighbor (Assignment delta, Assignment deltadelta) override
	--— Base operator class for operators manipulating IntVars --—
Public Member Functions inherited from operations_research::LocalSearchOperator
	LocalSearchOperator ()
	~LocalSearchOperator () override
virtual const LocalSearchOperator *	Self () const
virtual bool	HasFragments () const
Public Member Functions inherited from operations_research::BaseObject
	BaseObject ()
	BaseObject (const BaseObject &)=delete
	This type is neither copyable nor movable.
BaseObject &	operator= (const BaseObject &)=delete
virtual	~BaseObject ()=default

Protected Member Functions
bool	OnSamePathAsPreviousBase (int64_t base_index) override
int64_t	GetBaseNodeRestartPosition (int base_index) override
bool	ConsiderAlternatives (int64_t base_index) const override
Protected Member Functions inherited from operations_research::PathOperator< ignore_path_vars >
bool	MakeOneNeighbor () override
	This method should not be overridden. Override MakeNeighbor() instead.
virtual void	OnNodeInitialization ()
virtual void	ResetIncrementalism ()
int64_t	BaseNode (int i) const
	Returns the ith base node of the operator.
int64_t	BaseAlternativeNode (int i) const
	Returns the alternative node for the ith base node.
int64_t	BaseSiblingAlternativeNode (int i) const
	Returns the alternative node for the sibling of the ith base node.
int64_t	StartNode (int i) const
	Returns the start node of the ith base node.
int64_t	EndNode (int i) const
	Returns the end node of the ith base node.
const std::vector< int64_t > &	path_starts () const
	Returns the vector of path start nodes.
int	PathClass (int i) const
	Returns the class of the path of the ith base node.
int	PathClassFromStartNode (int64_t start_node) const
virtual void	SetNextBaseToIncrement (int64_t base_index)
int64_t	OldNext (int64_t node) const
int64_t	PrevNext (int64_t node) const
int64_t	OldPrev (int64_t node) const
int64_t	OldPath (int64_t node) const
int	CurrentNodePathStart (int64_t node) const
int	CurrentNodePathEnd (int64_t node) const
bool	MoveChain (int64_t before_chain, int64_t chain_end, int64_t destination)
bool	ReverseChain (int64_t before_chain, int64_t after_chain, int64_t *chain_last)
bool	SwapNodes (int64_t node1, int64_t node2)
	Swaps the nodes node1 and node2.
bool	MakeActive (int64_t node, int64_t destination)
	Insert the inactive node after destination.
bool	MakeChainInactive (int64_t before_chain, int64_t chain_end)
bool	SwapActiveAndInactive (int64_t active, int64_t inactive)
	Replaces active by inactive in the current path, making active inactive.
bool	SwapActiveAndInactiveChains (absl::Span< const int64_t > active_chain, absl::Span< const int64_t > inactive_chain)
void	SetNext (int64_t from, int64_t to, int64_t path)
	Sets 'to' to be the node after 'from' on the given path.
bool	IsPathEnd (int64_t node) const
bool	IsPathStart (int64_t node) const
	Returns true if node is the first node on the path.
bool	IsInactive (int64_t node) const
	Returns true if node is inactive.
virtual bool	InitPosition () const
void	ResetPosition ()
int	AddAlternativeSet (const std::vector< int64_t > &alternative_set)
template<typename PairType>
void	AddPairAlternativeSets (const std::vector< PairType > &pair_alternative_sets)
int64_t	GetActiveInAlternativeSet (int alternative_index) const
	Returns the active node in the given alternative set.
int64_t	GetActiveAlternativeNode (int node) const
	Returns the active node in the alternative set of the given node.
int	GetSiblingAlternativeIndex (int node) const
	Returns the index of the alternative set of the sibling of node.
int	GetAlternativeIndex (int node) const
	Returns the index of the alternative set of the node.
int64_t	GetActiveAlternativeSibling (int node) const
bool	CheckChainValidity (int64_t before_chain, int64_t chain_end, int64_t exclude) const
bool	HasNeighbors () const
Neighbor	GetNeighborForBaseNode (int64_t base_index) const
Protected Member Functions inherited from operations_research::IntVarLocalSearchOperator
int64_t	InverseValue (int64_t index) const
int64_t	OldInverseValue (int64_t index) const
void	AddToAssignment (IntVar var, int64_t value, bool active, std::vector< int > assignment_indices, int64_t index, Assignment *assignment) const

Additional Inherited Members
Protected Attributes inherited from operations_research::PathOperator< ignore_path_vars >
const int	number_of_nexts_

Constructor & Destructor Documentation

◆ PairRelocateOperator()

template<bool ignore_path_vars>

operations_research::PairRelocateOperator< ignore_path_vars >::PairRelocateOperator	(	const std::vector< IntVar * > &	vars,
		const std::vector< IntVar * > &	secondary_vars,
		std::function< int(int64_t)>	start_empty_path_class,
		const std::vector< PickupDeliveryPair > &	pairs )

Todo: (user): Add a version where a (first_node, second_node) pair are added respectively after first_node_neighbor and second_node_neighbor. This requires a complete restructuring of the code, since we would require scanning neighbors for a non-base node (second_node is an active sibling of first_node).

Definition at line 525 of file routing_neighborhoods.cc.

◆ ~PairRelocateOperator()

template<bool ignore_path_vars>

operations_research::PairRelocateOperator< ignore_path_vars >::~PairRelocateOperator ( )

overridedefault

Member Function Documentation

◆ ConsiderAlternatives()

template<bool ignore_path_vars>

bool operations_research::PairRelocateOperator< ignore_path_vars >::ConsiderAlternatives ( int64_t ) const

inlineoverrideprotectedvirtual

Indicates if alternatives should be considered when iterating over base nodes.

Reimplemented from operations_research::PathOperator< ignore_path_vars >.

Definition at line 340 of file routing_neighborhoods.h.

◆ DebugString()

template<bool ignore_path_vars>

std::string operations_research::PairRelocateOperator< ignore_path_vars >::DebugString ( ) const

inlineoverridevirtual

Reimplemented from operations_research::BaseObject.

Definition at line 331 of file routing_neighborhoods.h.

◆ GetBaseNodeRestartPosition()

template<bool ignore_path_vars>

int64_t operations_research::PairRelocateOperator< ignore_path_vars >::GetBaseNodeRestartPosition ( int base_index )

overrideprotectedvirtual

Returns the index of the node to which the base node of index base_index must be set to when it reaches the end of a path. By default, it is set to the start of the current path. When this method is called, one can only assume that base nodes with indices < base_index have their final position.

Destination node of the second node of a pair must be after the destination node of the first node of a pair.

Reimplemented from operations_research::PathOperator< ignore_path_vars >.

Definition at line 596 of file routing_neighborhoods.cc.

◆ MakeNeighbor()

template<bool ignore_path_vars>

bool operations_research::PairRelocateOperator< ignore_path_vars >::MakeNeighbor ( )

overridevirtual

The second_pair_node -> first_pair_node link is forbidden.

If the current sequence is first_prev -> first_pair_node -> second_pair_node, and both 1st and 2nd are moved both to prev, the result of the move will be first_prev -> first_pair_node -> second_pair_node, which is no move.

Relocation is successful if both moves are feasible and at least one of the nodes moves.

Explicitly calling Prev as second_pair_node might have been moved before first_pair_node.

Swapping alternatives in.

Implements operations_research::PathOperator< ignore_path_vars >.

Definition at line 542 of file routing_neighborhoods.cc.

◆ OnSamePathAsPreviousBase()

template<bool ignore_path_vars>

bool operations_research::PairRelocateOperator< ignore_path_vars >::OnSamePathAsPreviousBase ( int64_t )

inlineoverrideprotectedvirtual

Returns true if a base node has to be on the same path as the "previous" base node (base node of index base_index - 1). Useful to limit neighborhood exploration to nodes on the same path.

Todo: (user): ideally this should be OnSamePath(int64_t node1, int64_t node2); it's currently way more complicated to implement.

Both destination nodes must be on the same path.

Reimplemented from operations_research::PathOperator< ignore_path_vars >.

Definition at line 334 of file routing_neighborhoods.h.

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

ortools/constraint_solver/routing_neighborhoods.h
ortools/constraint_solver/routing_neighborhoods.cc

Detailed Description

Public Member Functions

Protected Member Functions

Additional Inherited Members

Constructor & Destructor Documentation

◆ PairRelocateOperator()

◆ ~PairRelocateOperator()

Member Function Documentation

◆ ConsiderAlternatives()

◆ DebugString()

◆ GetBaseNodeRestartPosition()

◆ MakeNeighbor()

◆ OnSamePathAsPreviousBase()