C++ Reference
C++ Reference: Routing
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.
Classes | |
struct | GlobalCheapestInsertionParameters |
Public Member Functions | |
GlobalCheapestInsertionFilteredHeuristic (RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, std::function< int64(int64)> penalty_evaluator, const std::vector< LocalSearchFilter * > &filters, 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 |
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... | |
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... | |
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_ |
Member Typedef Documentation
◆ Seed
|
protectedinherited |
◆ ValuedPosition
|
protectedinherited |
Constructor & Destructor Documentation
◆ GlobalCheapestInsertionFilteredHeuristic()
GlobalCheapestInsertionFilteredHeuristic | ( | RoutingModel * | model, |
std::function< int64(int64, int64, int64)> | evaluator, | ||
std::function< int64(int64)> | penalty_evaluator, | ||
const std::vector< LocalSearchFilter * > & | filters, | ||
GlobalCheapestInsertionParameters | parameters | ||
) |
Takes ownership of evaluators.
◆ ~GlobalCheapestInsertionFilteredHeuristic()
|
inlineoverride |
Member Function Documentation
◆ AppendEvaluatedPositionsAfter()
|
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).
◆ BuildSolution()
|
inherited |
Builds a solution.
Returns the resulting assignment if a solution was found, and nullptr otherwise.
◆ BuildSolutionFromRoutes()
|
inherited |
Builds a solution starting from the routes formed by the next accessor.
◆ BuildSolutionInternal()
|
overridevirtual |
Virtual method to redefine how to build a solution.
Implements IntVarFilteredHeuristic.
◆ Commit()
|
protectedinherited |
Commits the modifications to the current solution if these modifications are "filter-feasible", returns false otherwise; in any case discards all modifications.
◆ ComputeStartEndDistanceForVehicles()
|
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.
◆ Contains()
|
inlineprotectedinherited |
◆ DebugString()
|
inlineoverridevirtual |
Reimplemented from IntVarFilteredHeuristic.
◆ GetEndChainStart()
|
inlineinherited |
◆ GetInsertionCostForNodeAtPosition()
|
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).
◆ GetStartChainEnd()
|
inlineinherited |
◆ GetUnperformedValue()
|
protectedinherited |
Returns the cost of unperforming node 'node_to_insert'.
Returns kint64max if penalty callback is null or if the node cannot be unperformed.
◆ InitializePriorityQueue()
|
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.
◆ InsertBetween()
|
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.
◆ MakeDisjunctionNodesUnperformed()
|
inherited |
Make nodes in the same disjunction as 'node' unperformed.
'node' is a variable index corresponding to a node.
◆ MakeUnassignedNodesUnperformed()
|
inherited |
Make all unassigned nodes unperformed.
◆ model()
|
inlineinherited |
◆ number_of_decisions()
|
inlineinherited |
◆ number_of_rejects()
◆ ResetSolution()
|
protectedinherited |
Resets the data members for a new solution.
◆ SetValue()
|
inlineprotectedinherited |
◆ Size()
|
inlineprotectedinherited |
◆ StopSearch()
|
inlineoverrideprotectedvirtualinherited |
Returns true if the search must be stopped.
Reimplemented from IntVarFilteredHeuristic.
◆ SynchronizeFilters()
|
protectedinherited |
Synchronizes filters with an assignment (the current solution).
◆ Value()
|
inlineprotectedinherited |
◆ Var()
|
inlineprotectedinherited |
Member Data Documentation
◆ assignment_
◆ evaluator_
|
protectedinherited |
◆ penalty_evaluator_
|
protectedinherited |
The documentation for this class was generated from the following file: