C++ Reference
C++ Reference: Routing
Detailed Description
Filter-based decision builder which builds a solution by using Clarke & Wright's Savings heuristic.
For each pair of nodes, the savings value is the difference between the cost of two routes visiting one node each and one route visiting both nodes. Routes are built sequentially, each route being initialized from the pair with the best avalaible savings value then extended by selecting the nodes with best savings on both ends of the partial route. Cost is based on the arc cost function of the routing model and cost classes are taken into account.
Classes | |
class | SavingsContainer |
struct | SavingsParameters |
struct | VehicleClassEntry |
Public Member Functions | |
SavingsFilteredHeuristic (RoutingModel *model, const RoutingIndexManager *manager, SavingsParameters parameters, const std::vector< LocalSearchFilter * > &filters) | |
~SavingsFilteredHeuristic () override | |
bool | BuildSolutionInternal () override |
Virtual method to redefine how to build a solution. More... | |
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 |
virtual std::string | DebugString () const |
Protected Types | |
typedef std::pair< int64, int64 > | Saving |
Protected Member Functions | |
virtual double | ExtraSavingsMemoryMultiplicativeFactor () const =0 |
virtual void | BuildRoutesFromSavings ()=0 |
int64 | GetVehicleTypeFromSaving (const Saving &saving) const |
Returns the cost class from a saving. More... | |
int64 | GetBeforeNodeFromSaving (const Saving &saving) const |
Returns the "before node" from a saving. More... | |
int64 | GetAfterNodeFromSaving (const Saving &saving) const |
Returns the "after node" from a saving. More... | |
int64 | GetSavingValue (const Saving &saving) const |
Returns the saving value from a saving. More... | |
int | StartNewRouteWithBestVehicleOfType (int type, int64 before_node, int64 after_node) |
Finds the best available vehicle of type "type" to start a new route to serve the arc before_node-->after_node. 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::vector< int > | type_index_of_vehicle_ |
std::vector< std::set< VehicleClassEntry > > | sorted_vehicle_classes_per_type_ |
std::vector< std::deque< int > > | vehicles_per_vehicle_class_ |
std::unique_ptr< SavingsContainer< Saving > > | savings_container_ |
Assignment *const | assignment_ |
Member Typedef Documentation
◆ Saving
Constructor & Destructor Documentation
◆ SavingsFilteredHeuristic()
SavingsFilteredHeuristic | ( | RoutingModel * | model, |
const RoutingIndexManager * | manager, | ||
SavingsParameters | parameters, | ||
const std::vector< LocalSearchFilter * > & | filters | ||
) |
◆ ~SavingsFilteredHeuristic()
|
override |
Member Function Documentation
◆ BuildRoutesFromSavings()
|
protectedpure virtual |
◆ 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.
◆ Contains()
|
inlineprotectedinherited |
◆ DebugString()
|
inlinevirtualinherited |
◆ ExtraSavingsMemoryMultiplicativeFactor()
|
protectedpure virtual |
◆ GetAfterNodeFromSaving()
|
inlineprotected |
◆ GetBeforeNodeFromSaving()
|
inlineprotected |
◆ GetEndChainStart()
|
inlineinherited |
◆ GetSavingValue()
|
inlineprotected |
◆ GetStartChainEnd()
|
inlineinherited |
◆ GetVehicleTypeFromSaving()
|
inlineprotected |
◆ 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 |
◆ StartNewRouteWithBestVehicleOfType()
|
protected |
Finds the best available vehicle of type "type" to start a new route to serve the arc before_node-->after_node.
Since there are different vehicle classes for each vehicle type, each vehicle class having its own capacity constraints, we go through all vehicle types (in each case only studying the first available vehicle) to make sure this Saving is inserted if possible. If possible, the arc is committed to the best vehicle, and the vehicle index is returned. If this arc can't be served by any vehicle of this type, the function returns -1.
◆ 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_
◆ savings_container_
|
protected |
◆ sorted_vehicle_classes_per_type_
|
protected |
◆ type_index_of_vehicle_
◆ vehicles_per_vehicle_class_
|
protected |
The documentation for this class was generated from the following file: