#include <routing_search.h>

Inheritance diagram for operations_research::SavingsFilteredHeuristic:

Classes
struct	Saving

class	SavingsContainer

struct	SavingsParameters

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

	~SavingsFilteredHeuristic () override

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

Protected Member Functions
virtual double	ExtraSavingsMemoryMultiplicativeFactor () const =0

virtual void	BuildRoutesFromSavings ()=0

int	StartNewRouteWithBestVehicleOfType (int type, int64_t before_node, int64_t after_node)

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
std::unique_ptr< SavingsContainer< Saving > >	savings_container_
	clang-format off

std::unique_ptr< VehicleTypeCurator >	vehicle_type_curator_
	clang-format on

Protected Attributes inherited from operations_research::IntVarFilteredHeuristic
Assignment *const	assignment_

Friends
class	SavingsFilteredHeuristicTestPeer

Detailed Description

Filter-based decision builder which builds a solution by using Clarke & Wright's Savings heuristic. For each pair of nodes, the savings value is the difference between the cost of two routes visiting one node each and one route visiting both nodes. Routes are built sequentially, each route being initialized from the pair with the best available savings value then extended by selecting the nodes with best savings on both ends of the partial route. Cost is based on the arc cost function of the routing model and cost classes are taken into account.

Definition at line 1323 of file routing_search.h.

Constructor & Destructor Documentation

◆ SavingsFilteredHeuristic()

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

SavingsFilteredHeuristic.

Definition at line 4136 of file routing_search.cc.

◆ ~SavingsFilteredHeuristic()

operations_research::SavingsFilteredHeuristic::~SavingsFilteredHeuristic ( )

overridedefault

Member Function Documentation

◆ BuildRoutesFromSavings()

virtual void operations_research::SavingsFilteredHeuristic::BuildRoutesFromSavings ( )

protectedpure virtual

◆ BuildSolutionInternal()

bool operations_research::SavingsFilteredHeuristic::BuildSolutionInternal ( )

overridevirtual

Virtual method to redefine how to build a solution.

Only store empty vehicles in the vehicle_type_curator_.

Free all the space used to store the Savings in the container.

Implements operations_research::IntVarFilteredHeuristic.

Definition at line 4150 of file routing_search.cc.

◆ ExtraSavingsMemoryMultiplicativeFactor()

virtual double operations_research::SavingsFilteredHeuristic::ExtraSavingsMemoryMultiplicativeFactor ( ) const

protectedpure virtual

◆ StartNewRouteWithBestVehicleOfType()

int operations_research::SavingsFilteredHeuristic::StartNewRouteWithBestVehicleOfType	(	int	type,
		int64_t	before_node,
		int64_t	after_node )

protected

Finds the best available vehicle of type "type" to start a new route to serve the arc before_node-->after_node. Since there are different vehicle classes for each vehicle type, each vehicle class having its own capacity constraints, we go through all vehicle types (in each case only studying the first available vehicle) to make sure this Saving is inserted if possible. If possible, the arc is committed to the best vehicle, and the vehicle index is returned. If this arc can't be served by any vehicle of this type, the function returns -1.

Try to commit the arc on this vehicle.

Definition at line 4169 of file routing_search.cc.

Friends And Related Symbol Documentation

◆ SavingsFilteredHeuristicTestPeer

friend class SavingsFilteredHeuristicTestPeer

friend

Definition at line 1418 of file routing_search.h.

Member Data Documentation

◆ savings_container_

std::unique_ptr<SavingsContainer<Saving> > operations_research::SavingsFilteredHeuristic::savings_container_

protected

clang-format off

Definition at line 1380 of file routing_search.h.

◆ vehicle_type_curator_

std::unique_ptr<VehicleTypeCurator> operations_research::SavingsFilteredHeuristic::vehicle_type_curator_

protected

clang-format on

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

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ SavingsFilteredHeuristic()

◆ ~SavingsFilteredHeuristic()

Member Function Documentation

◆ BuildRoutesFromSavings()

◆ BuildSolutionInternal()

◆ ExtraSavingsMemoryMultiplicativeFactor()

◆ StartNewRouteWithBestVehicleOfType()

Friends And Related Symbol Documentation

◆ SavingsFilteredHeuristicTestPeer

Member Data Documentation

◆ savings_container_

◆ vehicle_type_curator_