OR-Tools  8.2
CheapestInsertionFilteredHeuristicabstract

Detailed Description

Definition at line 3117 of file routing.h.

Classes

struct  StartEndValue
 

Public Member Functions

 CheapestInsertionFilteredHeuristic (RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, std::function< int64(int64)> penalty_evaluator, LocalSearchFilterManager *filter_manager)
 Takes ownership of evaluator. More...
 
 ~CheapestInsertionFilteredHeuristic () override
 
template<class Queue >
void InitializePriorityQueue (std::vector< std::vector< StartEndValue >> *start_end_distances_per_node, Queue *priority_queue)
 
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
 
virtual std::string DebugString () const
 

Protected Types

typedef std::pair< int64, int64ValuedPosition
 
typedef std::pair< StartEndValue, int > Seed
 

Protected Member Functions

std::vector< std::vector< StartEndValue > > ComputeStartEndDistanceForVehicles (const std::vector< int > &vehicles)
 Computes and returns the distance of each uninserted node to every vehicle in "vehicles" as a std::vector<std::vector<StartEndValue>>, start_end_distances_per_node. More...
 
template<class Queue >
void InitializePriorityQueue (std::vector< std::vector< StartEndValue > > *start_end_distances_per_node, Queue *priority_queue)
 Initializes the priority_queue by inserting the best entry corresponding to each node, i.e. More...
 
void InsertBetween (int64 node, int64 predecessor, int64 successor)
 Inserts 'node' just after 'predecessor', and just before 'successor', resulting in the following subsequence: predecessor -> node -> successor. More...
 
void AppendEvaluatedPositionsAfter (int64 node_to_insert, int64 start, int64 next_after_start, int64 vehicle, std::vector< ValuedPosition > *valued_positions)
 Helper method to the ComputeEvaluatorSortedPositions* methods. More...
 
int64 GetInsertionCostForNodeAtPosition (int64 node_to_insert, int64 insert_after, int64 insert_before, int vehicle) const
 Returns the cost of inserting 'node_to_insert' between 'insert_after' and 'insert_before' on the 'vehicle', i.e. More...
 
int64 GetUnperformedValue (int64 node_to_insert) const
 Returns the cost of unperforming node 'node_to_insert'. More...
 
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...
 
virtual bool BuildSolutionInternal ()=0
 Virtual method to redefine how to build a 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

std::function< int64(int64, int64, int64)> evaluator_
 
std::function< int64(int64)> penalty_evaluator_
 
Assignment *const assignment_
 

Member Typedef Documentation

◆ Seed

typedef std::pair<StartEndValue, int> Seed
protected

Definition at line 3137 of file routing.h.

◆ ValuedPosition

typedef std::pair<int64, int64> ValuedPosition
protected

Definition at line 3127 of file routing.h.

Constructor & Destructor Documentation

◆ CheapestInsertionFilteredHeuristic()

CheapestInsertionFilteredHeuristic ( RoutingModel model,
std::function< int64(int64, int64, int64)>  evaluator,
std::function< int64(int64)>  penalty_evaluator,
LocalSearchFilterManager filter_manager 
)

Takes ownership of evaluator.

Definition at line 3131 of file routing_search.cc.

◆ ~CheapestInsertionFilteredHeuristic()

Definition at line 3124 of file routing.h.

Member Function Documentation

◆ AppendEvaluatedPositionsAfter()

void AppendEvaluatedPositionsAfter ( int64  node_to_insert,
int64  start,
int64  next_after_start,
int64  vehicle,
std::vector< ValuedPosition > *  valued_positions 
)
protected

Helper method to the ComputeEvaluatorSortedPositions* methods.

Finds all possible insertion positions of node 'node_to_insert' in the partial route starting at node 'start' and adds them to 'valued_position', a list of unsorted pairs of (cost, position to insert the node).

Definition at line 3199 of file routing_search.cc.

◆ 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()

virtual bool BuildSolutionInternal ( )
protectedpure virtualinherited

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

◆ ComputeStartEndDistanceForVehicles()

std::vector< std::vector< CheapestInsertionFilteredHeuristic::StartEndValue > > ComputeStartEndDistanceForVehicles ( const std::vector< int > &  vehicles)
protected

Computes and returns the distance of each uninserted node to every vehicle in "vehicles" as a std::vector<std::vector<StartEndValue>>, start_end_distances_per_node.

For each node, start_end_distances_per_node[node] is sorted in decreasing order.

Definition at line 3140 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()

◆ GetEndChainStart()

int GetEndChainStart ( int  vehicle) const
inlineinherited

Returns the start of the end chain of vehicle,.

Definition at line 3088 of file routing.h.

◆ GetInsertionCostForNodeAtPosition()

int64 GetInsertionCostForNodeAtPosition ( int64  node_to_insert,
int64  insert_after,
int64  insert_before,
int  vehicle 
) const
protected

Returns the cost of inserting 'node_to_insert' between 'insert_after' and 'insert_before' on the 'vehicle', i.e.

Cost(insert_after-->node) + Cost(node-->insert_before)

  • Cost (insert_after-->insert_before).

Definition at line 3215 of file routing_search.cc.

◆ GetStartChainEnd()

int GetStartChainEnd ( int  vehicle) const
inlineinherited

Returns the end of the start chain of vehicle,.

Definition at line 3086 of file routing.h.

◆ GetUnperformedValue()

int64 GetUnperformedValue ( int64  node_to_insert) const
protected

Returns the cost of unperforming node 'node_to_insert'.

Returns kint64max if penalty callback is null or if the node cannot be unperformed.

Definition at line 3223 of file routing_search.cc.

◆ InitializePriorityQueue() [1/2]

void InitializePriorityQueue ( std::vector< std::vector< StartEndValue > > *  start_end_distances_per_node,
Queue priority_queue 
)
protected

Initializes the priority_queue by inserting the best entry corresponding to each node, i.e.

the last element of start_end_distances_per_node[node], which is supposed to be sorted in decreasing order. Queue is a priority queue containing Seeds.

◆ InitializePriorityQueue() [2/2]

void InitializePriorityQueue ( std::vector< std::vector< StartEndValue >> *  start_end_distances_per_node,
Queue priority_queue 
)

Definition at line 3171 of file routing_search.cc.

◆ InsertBetween()

void InsertBetween ( int64  node,
int64  predecessor,
int64  successor 
)
protected

Inserts 'node' just after 'predecessor', and just before 'successor', resulting in the following subsequence: predecessor -> node -> successor.

If 'node' is part of a disjunction, other nodes of the disjunction are made unperformed.

Definition at line 3191 of file routing_search.cc.

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

◆ evaluator_

std::function<int64(int64, int64, int64)> evaluator_
protected

Definition at line 3184 of file routing.h.

◆ penalty_evaluator_

std::function<int64(int64)> penalty_evaluator_
protected

Definition at line 3185 of file routing.h.


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