C++ Reference
C++ Reference: Routing
Detailed Description
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, const std::vector< LocalSearchFilter * > &filters) | |
| 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 |
| 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... | |
| virtual void | SetVehicleIndex (int64 node, int vehicle) |
| virtual void | ResetVehicleIndices () |
| 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
◆ LocalCheapestInsertionFilteredHeuristic()
| LocalCheapestInsertionFilteredHeuristic | ( | RoutingModel * | model, |
| std::function< int64(int64, int64, int64)> | evaluator, | ||
| const std::vector< LocalSearchFilter * > & | filters | ||
| ) |
Takes ownership of evaluator.
◆ ~LocalCheapestInsertionFilteredHeuristic()
|
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.
◆ ResetVehicleIndices()
|
inlineprotectedvirtualinherited |
◆ SetValue()
|
inlineprotectedinherited |
◆ SetVehicleIndex()
|
inlineprotectedvirtualinherited |
◆ 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: