![]() |
OR-Tools
8.2
|
Filter-base decision builder which builds a solution by inserting nodes at their cheapest position.
The cost of a position is computed an arc-based cost callback. Node selected for insertion are considered in decreasing order of distance to the start/ends of the routes, i.e. farthest nodes are inserted first.
Public Member Functions | |
LocalCheapestInsertionFilteredHeuristic (RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, LocalSearchFilterManager *filter_manager) | |
Takes ownership of evaluator. More... | |
~LocalCheapestInsertionFilteredHeuristic () 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 Assignment * | BuildSolutionFromRoutes (const std::function< int64(int64)> &next_accessor) |
Builds a solution starting from the routes formed by the next accessor. More... | |
RoutingModel * | model () 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, int64 > | ValuedPosition |
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... | |
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... | |
IntVar * | Var (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_ |
|
protectedinherited |
|
protectedinherited |
LocalCheapestInsertionFilteredHeuristic | ( | RoutingModel * | model, |
std::function< int64(int64, int64, int64)> | evaluator, | ||
LocalSearchFilterManager * | filter_manager | ||
) |
Takes ownership of evaluator.
Definition at line 4636 of file routing_search.cc.
|
inlineoverride |
|
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.
|
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.
|
inherited |
Builds a solution starting from the routes formed by the next accessor.
Definition at line 2919 of file routing_search.cc.
|
overridevirtual |
Virtual method to redefine how to build a solution.
Implements IntVarFilteredHeuristic.
Definition at line 4650 of file routing_search.cc.
|
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.
|
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.
|
inlineprotectedinherited |
|
inlineoverridevirtual |
Reimplemented from IntVarFilteredHeuristic.
|
inlineinherited |
|
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)
Definition at line 3215 of file routing_search.cc.
|
inlineinherited |
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.
|
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.
|
inherited |
Definition at line 3171 of file routing_search.cc.
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.
|
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.
|
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.
|
inherited |
Make all unassigned nodes unperformed.
Definition at line 3082 of file routing_search.cc.
|
inlineinherited |
|
inlineinherited |
|
protectedinherited |
Resets the data members for a new solution.
Definition at line 2897 of file routing_search.cc.
|
inlineprotectedvirtualinherited |
|
inlineprotectedvirtualinherited |
|
inlineprotectedinherited |
|
inlineoverrideprotectedvirtualinherited |
Returns true if the search must be stopped.
Reimplemented from IntVarFilteredHeuristic.
|
protectedinherited |
Synchronizes filters with an assignment (the current solution).
Definition at line 2980 of file routing_search.cc.
|
inlineprotectedinherited |
|
protectedinherited |