C++ Reference
C++ Reference: Routing
Detailed Description
Christofides addition heuristic.
Initially created to solve TSPs, extended to support any model by extending routes as much as possible following the path found by the heuristic, before starting a new route.
Public Member Functions | |
| ChristofidesFilteredDecisionBuilder (RoutingModel *model, const std::vector< LocalSearchFilter * > &filters) | |
| ~ChristofidesFilteredDecisionBuilder () override | |
| bool | BuildSolution () override |
| Virtual method to redefine to build a solution. More... | |
| std::string | DebugString () const override |
| 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... | |
| Decision * | Next (Solver *solver) override |
| This is the main method of the decision builder class. 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 void | AppendMonitors (Solver *const solver, std::vector< SearchMonitor * > *const extras) |
| This method will be called at the start of the search. More... | |
| virtual void | Accept (ModelVisitor *const visitor) const |
Protected Member Functions | |
| bool | StopSearch () override |
| Returns true if the search must be stopped. 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... | |
Constructor & Destructor Documentation
◆ ChristofidesFilteredDecisionBuilder()
| ChristofidesFilteredDecisionBuilder | ( | RoutingModel * | model, |
| const std::vector< LocalSearchFilter * > & | filters | ||
| ) |
◆ ~ChristofidesFilteredDecisionBuilder()
|
inlineoverride |
Member Function Documentation
◆ Accept()
|
virtualinherited |
◆ AppendMonitors()
|
virtualinherited |
This method will be called at the start of the search.
It asks the decision builder if it wants to append search monitors to the list of active monitors for this search. Please note there are no checks at this point for duplication.
◆ BuildSolution()
|
overridevirtual |
Virtual method to redefine to build a solution.
Implements IntVarFilteredDecisionBuilder.
◆ Commit()
|
protectedinherited |
Commits the modifications to the current solution if these modifications are "filter-feasible", returns false otherwise; in any case discards all modifications.
◆ Contains()
|
inlineprotectedinherited |
◆ DebugString()
|
inlineoverridevirtual |
Reimplemented from DecisionBuilder.
◆ GetEndChainStart()
|
inlineinherited |
◆ GetStartChainEnd()
|
inlineinherited |
◆ 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 |
◆ Next()
This is the main method of the decision builder class.
It must return a decision (an instance of the class Decision). If it returns nullptr, this means that the decision builder has finished its work.
Implements DecisionBuilder.
◆ number_of_decisions()
|
inlineinherited |
◆ number_of_rejects()
◆ SetValue()
|
inlineprotectedinherited |
◆ Size()
|
inlineprotectedinherited |
◆ StopSearch()
|
inlineoverrideprotectedvirtualinherited |
Returns true if the search must be stopped.
Reimplemented from IntVarFilteredDecisionBuilder.
◆ Value()
|
inlineprotectedinherited |
◆ Var()
|
inlineprotectedinherited |
The documentation for this class was generated from the following file: