OR-Tools  8.2
GlobalCheapestInsertionFilteredHeuristic

Detailed Description

Filter-based decision builder which builds a solution by inserting nodes at their cheapest position on any route; potentially several routes can be built in parallel.

The cost of a position is computed from an arc-based cost callback. The node selected for insertion is the one which minimizes insertion cost. If a non null penalty evaluator is passed, making nodes unperformed is also taken into account with the corresponding penalty cost.

Definition at line 3195 of file routing.h.

Classes

struct  GlobalCheapestInsertionParameters
 
class  NodeEntry
 
class  PairEntry
 

Public Member Functions

 GlobalCheapestInsertionFilteredHeuristic (RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, std::function< int64(int64)> penalty_evaluator, LocalSearchFilterManager *filter_manager, GlobalCheapestInsertionParameters parameters)
 Takes ownership of evaluators. More...
 
 ~GlobalCheapestInsertionFilteredHeuristic () override
 
bool BuildSolutionInternal () override
 Virtual method to redefine how to build a solution. More...
 
std::string DebugString () const 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
 

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

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
protectedinherited

Definition at line 3137 of file routing.h.

◆ ValuedPosition

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

Definition at line 3127 of file routing.h.

Constructor & Destructor Documentation

◆ GlobalCheapestInsertionFilteredHeuristic()

GlobalCheapestInsertionFilteredHeuristic ( RoutingModel model,
std::function< int64(int64, int64, int64)>  evaluator,
std::function< int64(int64)>  penalty_evaluator,
LocalSearchFilterManager filter_manager,
GlobalCheapestInsertionParameters  parameters 
)

Takes ownership of evaluators.

Definition at line 3340 of file routing_search.cc.

◆ ~GlobalCheapestInsertionFilteredHeuristic()

Definition at line 3228 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 
)
protectedinherited

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

bool BuildSolutionInternal ( )
overridevirtual

Virtual method to redefine how to build a solution.

Implements IntVarFilteredHeuristic.

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

◆ ComputeStartEndDistanceForVehicles()

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

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

std::string DebugString ( ) const
inlineoverridevirtual

Reimplemented from IntVarFilteredHeuristic.

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

◆ GetInsertionCostForNodeAtPosition()

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

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
protectedinherited

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 
)
protectedinherited

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 
)
inherited

Definition at line 3171 of file routing_search.cc.

◆ InsertBetween()

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

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.

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

◆ 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_
protectedinherited

Definition at line 3184 of file routing.h.

◆ penalty_evaluator_

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

Definition at line 3185 of file routing.h.


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