OR-Tools  8.2
ChristofidesFilteredHeuristic

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 3805 of file routing.h.

Public Member Functions

 ChristofidesFilteredHeuristic (RoutingModel *model, LocalSearchFilterManager *filter_manager, bool use_minimum_matching)
 
 ~ChristofidesFilteredHeuristic () override
 
bool BuildSolutionInternal () override
 Virtual method to redefine how to build a solution. More...
 
std::string DebugString () const override
 
const AssignmentBuildSolutionFromRoutes (const std::function< int64(int64)> &next_accessor)
 Builds a solution starting from the routes formed by the next accessor. More...
 
RoutingModelmodel () 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 node)
 Make nodes in the same disjunction as 'node' unperformed. More...
 
void MakeUnassignedNodesUnperformed ()
 Make all unassigned nodes unperformed. More...
 
void MakePartiallyPerformedPairsUnperformed ()
 Make all partially performed pickup and delivery pairs unperformed. More...
 
Assignment *const BuildSolution ()
 Builds a solution. More...
 
int64 number_of_decisions () const
 Returns statistics on search, number of decisions sent to filters, number of decisions rejected by filters. More...
 
int64 number_of_rejects () const
 

Protected Member Functions

bool StopSearch () override
 Returns true if the search must be stopped. More...
 
virtual void SetVehicleIndex (int64 node, int vehicle)
 
virtual void ResetVehicleIndices ()
 
bool VehicleIsEmpty (int vehicle) const
 
void ResetSolution ()
 Resets the data members for a new solution. More...
 
bool Commit ()
 Commits the modifications to the current solution if these modifications are "filter-feasible", returns false otherwise; in any case discards all modifications. More...
 
void SetValue (int64 index, int64 value)
 Modifies the current solution by setting the variable of index 'index' to value 'value'. More...
 
int64 Value (int64 index) const
 Returns the value of the variable of index 'index' in the last committed solution. More...
 
bool Contains (int64 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...
 
IntVarVar (int64 index) const
 Returns the variable of index '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,
LocalSearchFilterManager filter_manager,
bool  use_minimum_matching 
)

Definition at line 5973 of file routing_search.cc.

◆ ~ChristofidesFilteredHeuristic()

~ChristofidesFilteredHeuristic ( )
inlineoverride

Definition at line 3810 of file routing.h.

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

◆ BuildSolutionFromRoutes()

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

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

Definition at line 2919 of file routing_search.cc.

◆ BuildSolutionInternal()

bool BuildSolutionInternal ( )
overridevirtual

Virtual method to redefine how to build a solution.

Implements IntVarFilteredHeuristic.

Definition at line 5980 of file routing_search.cc.

◆ Commit()

bool Commit ( )
protectedinherited

Commits the modifications to the current solution if these modifications are "filter-feasible", returns false otherwise; in any case discards all modifications.

Definition at line 2952 of file routing_search.cc.

◆ Contains()

bool Contains ( int64  index) const
inlineprotectedinherited

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

Definition at line 3045 of file routing.h.

◆ DebugString()

std::string DebugString ( ) const
inlineoverridevirtual

Reimplemented from IntVarFilteredHeuristic.

Definition at line 3812 of file routing.h.

◆ GetEndChainStart()

int GetEndChainStart ( int  vehicle) const
inlineinherited

Returns the start of the end chain of vehicle,.

Definition at line 3088 of file routing.h.

◆ GetStartChainEnd()

int GetStartChainEnd ( int  vehicle) const
inlineinherited

Returns the end of the start chain of vehicle,.

Definition at line 3086 of file routing.h.

◆ MakeDisjunctionNodesUnperformed()

void MakeDisjunctionNodesUnperformed ( int64  node)
inherited

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

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

Definition at line 3073 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 3090 of file routing_search.cc.

◆ MakeUnassignedNodesUnperformed()

void MakeUnassignedNodesUnperformed ( )
inherited

Make all unassigned nodes unperformed.

Definition at line 3082 of file routing_search.cc.

◆ model()

RoutingModel* model ( ) const
inlineinherited

Definition at line 3084 of file routing.h.

◆ number_of_decisions()

int64 number_of_decisions ( ) const
inlineinherited

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

Definition at line 3010 of file routing.h.

◆ number_of_rejects()

int64 number_of_rejects ( ) const
inlineinherited

Definition at line 3011 of file routing.h.

◆ ResetSolution()

void ResetSolution ( )
protectedinherited

Resets the data members for a new solution.

Definition at line 2897 of file routing_search.cc.

◆ ResetVehicleIndices()

virtual void ResetVehicleIndices ( )
inlineprotectedvirtualinherited

Definition at line 3103 of file routing.h.

◆ SetValue()

void SetValue ( int64  index,
int64  value 
)
inlineprotectedinherited

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

Definition at line 3030 of file routing.h.

◆ SetVehicleIndex()

virtual void SetVehicleIndex ( int64  node,
int  vehicle 
)
inlineprotectedvirtualinherited

Definition at line 3102 of file routing.h.

◆ Size()

int Size ( ) const
inlineprotectedinherited

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

Definition at line 3050 of file routing.h.

◆ StopSearch()

bool StopSearch ( )
inlineoverrideprotectedvirtualinherited

Returns true if the search must be stopped.

Reimplemented from IntVarFilteredHeuristic.

Definition at line 3101 of file routing.h.

◆ SynchronizeFilters()

void SynchronizeFilters ( )
protectedinherited

Synchronizes filters with an assignment (the current solution).

Definition at line 2980 of file routing_search.cc.

◆ Value()

int64 Value ( int64  index) const
inlineprotectedinherited

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

Definition at line 3041 of file routing.h.

◆ Var()

IntVar* Var ( int64  index) const
inlineprotectedinherited

Returns the variable of index 'index'.

Definition at line 3052 of file routing.h.

◆ VehicleIsEmpty()

bool VehicleIsEmpty ( int  vehicle) const
inlineprotectedinherited

Definition at line 3104 of file routing.h.

Member Data Documentation

◆ assignment_

Assignment* const assignment_
protectedinherited

Definition at line 3056 of file routing.h.


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