Detailed Description

Christofides addition heuristic.

Initially created to solve TSPs, extended to support any model by extending routes as much as possible following the path found by the heuristic, before starting a new route.

Definition at line 1227 of file routing_search.h.

Public Member Functions
	ChristofidesFilteredHeuristic (RoutingModel model, std::function< bool()> stop_search, LocalSearchFilterManager filter_manager, bool use_minimum_matching)

	~ChristofidesFilteredHeuristic () override=default

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

std::string	DebugString () const override

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 Member Functions
bool	StopSearch () override
	Returns true if the search must be stopped. More...

virtual void	SetVehicleIndex (int64_t, int)

virtual void	ResetVehicleIndices ()

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
Assignment *const	assignment_

Constructor & Destructor Documentation

◆ ChristofidesFilteredHeuristic()

ChristofidesFilteredHeuristic	(	RoutingModel *	model,
		std::function< bool()>	stop_search,
		LocalSearchFilterManager *	filter_manager,
		bool	use_minimum_matching
	)

Definition at line 3812 of file routing_search.cc.

◆ ~ChristofidesFilteredHeuristic()

~ChristofidesFilteredHeuristic ( )

overridedefault

Member Function Documentation

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

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

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

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

◆ ResetVehicleIndices()

virtual void ResetVehicleIndices ( )

inlineprotectedvirtualinherited

Definition at line 297 of file routing_search.h.

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

◆ SetVehicleIndex()

virtual void SetVehicleIndex	(	int64_t	,
		int
	)

inlineprotectedvirtualinherited

Definition at line 296 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.

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

Detailed Description

Public Member Functions

Protected Member Functions

Protected Attributes

Constructor & Destructor Documentation

◆ ChristofidesFilteredHeuristic()

◆ ~ChristofidesFilteredHeuristic()

Member Function Documentation

◆ BuildSolution()

◆ BuildSolutionFromRoutes()

◆ BuildSolutionInternal()

◆ Contains()

◆ DebugString()

◆ Evaluate()

◆ GetEndChainStart()

◆ GetStartChainEnd()

◆ HasSecondaryVars()

◆ Initialize()

◆ IsSecondaryVar()

◆ MakeDisjunctionNodesUnperformed()

◆ MakePartiallyPerformedPairsUnperformed()

◆ MakeUnassignedNodesUnperformed()

◆ model()

◆ number_of_decisions()

◆ number_of_rejects()

◆ ResetSolution()

◆ ResetVehicleIndices()

◆ SecondaryVarIndex()

◆ SetValue()

◆ SetVehicleIndex()

◆ Size()

◆ StopSearch()

◆ SynchronizeFilters()

◆ Value()

◆ Var()

◆ VehicleIsEmpty()

Member Data Documentation

◆ assignment_