#include <routing_search.h>

Inheritance diagram for operations_research::CheapestAdditionFilteredHeuristic:

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

	~CheapestAdditionFilteredHeuristic () override=default

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

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

Additional Inherited Members
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.

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 inherited from operations_research::IntVarFilteredHeuristic
Assignment *const	assignment_

Detailed Description

Filtered-base decision builder based on the addition heuristic, extending a path from its start node with the cheapest arc.

Definition at line 1226 of file routing_search.h.

Constructor & Destructor Documentation

◆ CheapestAdditionFilteredHeuristic()

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

CheapestAdditionFilteredHeuristic.

Definition at line 3481 of file routing_search.cc.

◆ ~CheapestAdditionFilteredHeuristic()

operations_research::CheapestAdditionFilteredHeuristic::~CheapestAdditionFilteredHeuristic ( )

overridedefault

Member Function Documentation

◆ BuildSolutionInternal()

bool operations_research::CheapestAdditionFilteredHeuristic::BuildSolutionInternal ( )

overridevirtual

Virtual method to redefine how to build a solution.

To mimic the behavior of PathSelector (cf. search.cc), iterating on routes with partial route at their start first then on routes with largest index.

Neighbors of the node currently being extended.

Extend the route of the current vehicle while it's possible. We can iterate more than once if pickup and delivery pairs have been inserted in the last iteration (see comment below); the new iteration will try to extend the route after the last delivery on the route.

Extend the route until either the end node of the vehicle is reached or no node or node pair can be added. Deliveries in pickup and delivery pairs are added at the same time as pickups, at the end of the route, in reverse order of the pickups. Deliveries are never added alone.

Only add a delivery if one of its pickups has been added already.

Insert "next" after "index", and before "end" if it is not the end already.

Implements operations_research::IntVarFilteredHeuristic.

Definition at line 3486 of file routing_search.cc.

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

ortools/constraint_solver/routing_search.h
ortools/constraint_solver/routing_search.cc