C++ Reference

C++ Reference: Routing

SavingsFilteredDecisionBuilderabstract

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.

Definition at line 2997 of file routing.h.

Classes

class  SavingsContainer
 
struct  SavingsParameters
 
struct  VehicleClassEntry
 

Public Member Functions

 SavingsFilteredDecisionBuilder (RoutingModel *model, RoutingIndexManager *manager, SavingsParameters parameters, const std::vector< LocalSearchFilter * > &filters)
 
 ~SavingsFilteredDecisionBuilder () override
 
bool BuildSolution () override
 Virtual method to redefine to build a solution. More...
 
RoutingModelmodel () 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...
 
DecisionNext (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
 
std::string DebugString () const override
 
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 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...
 
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...
 
IntVarVar (int64 index) const
 Returns the variable of index 'index'. 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_
 

Member Typedef Documentation

◆ Saving

typedef std::pair< int64, int64> Saving
protected

Definition at line 3022 of file routing.h.

Constructor & Destructor Documentation

◆ SavingsFilteredDecisionBuilder()

SavingsFilteredDecisionBuilder ( RoutingModel model,
RoutingIndexManager manager,
SavingsParameters  parameters,
const std::vector< LocalSearchFilter * > &  filters 
)

◆ ~SavingsFilteredDecisionBuilder()

Member Function Documentation

◆ Accept()

virtual void Accept ( ModelVisitor *const  visitor) const
virtualinherited

◆ AppendMonitors()

virtual void AppendMonitors ( Solver *const  solver,
std::vector< SearchMonitor * > *const  extras 
)
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.

◆ BuildRoutesFromSavings()

virtual void BuildRoutesFromSavings ( )
protectedpure virtual

◆ BuildSolution()

bool BuildSolution ( )
overridevirtual

Virtual method to redefine to build a solution.

Implements IntVarFilteredDecisionBuilder.

◆ Commit()

bool 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()

bool Contains ( int64  index) const
inlineprotectedinherited

Returns true if the variable of index 'index' is in the current solution.

Definition at line 2561 of file routing.h.

◆ DebugString()

◆ ExtraSavingsMemoryMultiplicativeFactor()

virtual double ExtraSavingsMemoryMultiplicativeFactor ( ) const
protectedpure virtual

◆ GetAfterNodeFromSaving()

int64 GetAfterNodeFromSaving ( const Saving saving) const
inlineprotected

Returns the "after node" from a saving.

Definition at line 3050 of file routing.h.

◆ GetBeforeNodeFromSaving()

int64 GetBeforeNodeFromSaving ( const Saving saving) const
inlineprotected

Returns the "before node" from a saving.

Definition at line 3046 of file routing.h.

◆ GetEndChainStart()

int GetEndChainStart ( int  vehicle) const
inlineinherited

Returns the start of the end chain of vehicle,.

Definition at line 2599 of file routing.h.

◆ GetSavingValue()

int64 GetSavingValue ( const Saving saving) const
inlineprotected

Returns the saving value from a saving.

Definition at line 3054 of file routing.h.

◆ GetStartChainEnd()

int GetStartChainEnd ( int  vehicle) const
inlineinherited

Returns the end of the start chain of vehicle,.

Definition at line 2597 of file routing.h.

◆ GetVehicleTypeFromSaving()

int64 GetVehicleTypeFromSaving ( const Saving saving) const
inlineprotected

Returns the cost class from a saving.

Definition at line 3042 of file routing.h.

◆ MakeDisjunctionNodesUnperformed()

void MakeDisjunctionNodesUnperformed ( int64  node)
inherited

Make nodes in the same disjunction as 'node' unperformed.

'node' is a variable index corresponding to a node.

◆ MakeUnassignedNodesUnperformed()

void MakeUnassignedNodesUnperformed ( )
inherited

Make all unassigned nodes unperformed.

◆ model()

RoutingModel* model ( ) const
inlineinherited

Definition at line 2595 of file routing.h.

◆ Next()

Decision* Next ( Solver s)
overridevirtualinherited

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()

int64 number_of_decisions ( ) const
inlineinherited

Returns statistics on search, number of decisions sent to filters, number of decisions rejected by filters.

Definition at line 2532 of file routing.h.

◆ number_of_rejects()

int64 number_of_rejects ( ) const
inlineinherited

Definition at line 2533 of file routing.h.

◆ SetValue()

void SetValue ( int64  index,
int64  value 
)
inlineprotectedinherited

Modifies the current solution by setting the variable of index 'index' to value 'value'.

Definition at line 2546 of file routing.h.

◆ Size()

int Size ( ) const
inlineprotectedinherited

Returns the number of variables the decision builder is trying to instantiate.

Definition at line 2566 of file routing.h.

◆ StartNewRouteWithBestVehicleOfType()

int StartNewRouteWithBestVehicleOfType ( int  type,
int64  before_node,
int64  after_node 
)
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()

bool StopSearch ( )
inlineoverrideprotectedvirtualinherited

Returns true if the search must be stopped.

Reimplemented from IntVarFilteredDecisionBuilder.

Definition at line 2607 of file routing.h.

◆ Value()

int64 Value ( int64  index) const
inlineprotectedinherited

Returns the value of the variable of index 'index' in the last committed solution.

Definition at line 2557 of file routing.h.

◆ Var()

IntVar* Var ( int64  index) const
inlineprotectedinherited

Returns the variable of index 'index'.

Definition at line 2568 of file routing.h.

Member Data Documentation

◆ savings_container_

std::unique_ptr<SavingsContainer<Saving> > savings_container_
protected

Definition at line 3072 of file routing.h.

◆ sorted_vehicle_classes_per_type_

std::vector<std::set<VehicleClassEntry> > sorted_vehicle_classes_per_type_
protected

Definition at line 3070 of file routing.h.

◆ type_index_of_vehicle_

std::vector<int> type_index_of_vehicle_
protected

Definition at line 3068 of file routing.h.

◆ vehicles_per_vehicle_class_

std::vector<std::deque<int> > vehicles_per_vehicle_class_
protected

Definition at line 3071 of file routing.h.


The documentation for this class was generated from the following file: