14 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_NEIGHBORHOODS_H_
15 #define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_NEIGHBORHOODS_H_
17 #include "absl/container/flat_hash_set.h"
50 const std::vector<IntVar*>& vars,
51 const std::vector<IntVar*>& secondary_vars,
52 std::function<
int(
int64)> start_empty_path_class,
57 std::string
DebugString()
const override {
return "RelocateNeighbors"; }
66 bool MoveChainAndRepair(
int64 before_chain,
int64 chain_end,
107 const std::vector<IntVar*>& secondary_vars,
108 std::function<
int(
int64)> start_empty_path_class,
112 std::string
DebugString()
const override {
return "MakePairActive"; }
129 void OnNodeInitialization()
override;
130 int FindNextInactivePair(
int pair_index)
const;
131 bool ContainsActiveNodes(
const std::vector<int64>& nodes)
const;
134 int inactive_pair_first_index_;
135 int inactive_pair_second_index_;
143 const std::vector<IntVar*>& secondary_vars,
144 std::function<
int(
int64)> start_empty_path_class,
148 std::string
DebugString()
const override {
return "MakePairInActive"; }
162 const std::vector<IntVar*>& secondary_vars,
163 std::function<
int(
int64)> start_empty_path_class,
168 std::string
DebugString()
const override {
return "PairRelocateOperator"; }
173 return base_index == kPairSecondNodeDestination;
178 return base_index == kPairFirstNode;
182 bool RestartAtPathStartOnSynchronize()
override {
return true; }
184 static constexpr
int kPairFirstNode = 0;
185 static constexpr
int kPairFirstNodeDestination = 1;
186 static constexpr
int kPairSecondNodeDestination = 2;
192 const std::vector<IntVar*>& secondary_vars,
193 std::function<
int(
int64)> start_empty_path_class,
199 return "LightPairRelocateOperator";
212 const std::vector<IntVar*>& secondary_vars,
213 std::function<
int(
int64)> start_empty_path_class,
218 std::string
DebugString()
const override {
return "PairExchangeOperator"; }
221 bool RestartAtPathStartOnSynchronize()
override {
return true; }
222 bool ConsiderAlternatives(
int64 base_index)
const override {
return true; }
223 bool GetPreviousAndSibling(
int64 node,
int64* previous,
int64* sibling,
224 int64* sibling_previous)
const;
243 const std::vector<IntVar*>& secondary_vars,
244 std::function<
int(
int64)> start_empty_path_class,
250 return "PairExchangeRelocateOperator";
258 bool RestartAtPathStartOnSynchronize()
override {
return true; }
259 bool GetPreviousAndSibling(
int64 node,
int64* previous,
int64* sibling,
260 int64* sibling_previous)
const;
261 bool MoveNode(
int pair,
int node,
int64 nodes[2][2],
int64 dest[2][2],
263 bool LoadAndCheckDest(
int pair,
int node,
int64 base_node,
int64 nodes[2][2],
264 int64 dest[2][2])
const;
266 static constexpr
int kFirstPairFirstNode = 0;
267 static constexpr
int kSecondPairFirstNode = 1;
268 static constexpr
int kFirstPairFirstNodeDestination = 2;
269 static constexpr
int kFirstPairSecondNodeDestination = 3;
270 static constexpr
int kSecondPairFirstNodeDestination = 4;
271 static constexpr
int kSecondPairSecondNodeDestination = 5;
287 const std::vector<IntVar*>& path_vars,
288 std::function<
int(
int64)> start_empty_path_class,
294 std::string
DebugString()
const override {
return "SwapIndexPairOperator"; }
299 bool UpdateActiveNodes();
304 if (!ignore_path_vars_) {
306 SetValue(from + number_of_nexts_, path);
315 int64 second_active_;
316 std::vector<int64> prevs_;
317 const int number_of_nexts_;
318 const bool ignore_path_vars_;
326 const std::vector<IntVar*>& secondary_vars,
327 std::function<
int(
int64)> start_empty_path_class,
334 return "IndexPairSwapActiveOperator";
338 void OnNodeInitialization()
override;
350 std::unique_ptr<RoutingFilteredHeuristic> heuristic,
351 bool keep_inverse_values =
false);
362 std::string heuristic_name = heuristic_->DebugString();
363 const int erase_pos = heuristic_name.find(
"FilteredHeuristic");
364 if (erase_pos != std::string::npos) {
365 const int expected_name_size = heuristic_name.size() - 17;
366 heuristic_name.erase(erase_pos);
369 DCHECK_EQ(heuristic_name.size(), expected_name_size);
371 return heuristic_name;
382 bool MakeOneNeighbor()
override;
383 bool MakeChangesAndInsertNodes();
387 const std::unique_ptr<RoutingFilteredHeuristic> heuristic_;
388 const bool consider_vehicle_vars_;
397 std::unique_ptr<RoutingFilteredHeuristic> heuristic);
401 return absl::StrCat(
"HeuristicPathLNS(",
HeuristicName(),
")");
405 void OnStart()
override;
407 bool IncrementPosition()
override;
408 bool CurrentRouteIsEmpty()
const;
409 void IncrementCurrentRouteToNextNonEmpty();
411 std::function<
int64(
int64)> SetupNextAccessorForNeighbor()
override;
425 std::unique_ptr<RoutingFilteredHeuristic> heuristic);
429 return absl::StrCat(
"RelocatePathAndHeuristicInsertUnperformed(",
434 void OnStart()
override;
436 bool IncrementPosition()
override;
437 bool IncrementRoutes();
439 std::function<
int64(
int64)> SetupNextAccessorForNeighbor()
override;
441 int route_to_relocate_index_;
442 int last_route_to_relocate_index_;
443 int empty_route_index_;
444 int last_empty_route_index_;
445 std::vector<int> routes_to_relocate_;
446 std::vector<int> empty_routes_;
447 std::vector<int64> last_node_on_route_;
448 bool has_unperformed_nodes_;
459 std::unique_ptr<RoutingFilteredHeuristic> heuristic,
460 int num_arcs_to_consider,
465 return absl::StrCat(
"HeuristicExpensiveChainLNS(",
HeuristicName(),
")");
469 void OnStart()
override;
471 bool IncrementPosition()
override;
472 bool IncrementRoute();
473 bool IncrementCurrentArcIndices();
474 bool FindMostExpensiveChainsOnRemainingRoutes();
476 std::function<
int64(
int64)> SetupNextAccessorForNeighbor()
override;
481 const int num_arcs_to_consider_;
482 std::vector<std::pair<int64, int>> most_expensive_arc_starts_and_ranks_;
486 current_expensive_arc_indices_;
489 arc_cost_for_route_start_;
501 std::unique_ptr<RoutingFilteredHeuristic> heuristic,
int num_close_nodes);
505 return absl::StrCat(
"HeuristicCloseNodesLNS(",
HeuristicName(),
")");
509 void OnStart()
override;
511 bool IncrementPosition()
override;
513 std::function<
int64(
int64)> SetupNextAccessorForNeighbor()
override;
515 void RemoveNode(
int64 node);
516 void RemoveNodeAndActiveSibling(
int64 node);
518 bool IsActive(
int64 node)
const {
526 return changed_prevs_[node] ? new_prevs_[node] :
InverseValue(node);
530 return changed_nexts_[node] ? new_nexts_[node] :
Value(node);
533 std::vector<int64> GetActiveSiblings(
int64 node)
const;
535 const std::vector<std::pair<std::vector<int64>, std::vector<int64>>>&
536 pickup_delivery_pairs_;
542 std::vector<std::vector<int64>> close_nodes_;
544 std::vector<int64> new_nexts_;
545 SparseBitset<> changed_nexts_;
546 std::vector<int64> new_prevs_;
547 SparseBitset<> changed_prevs_;
560 const std::vector<IntVar*>& vars,
561 const std::vector<IntVar*>& secondary_vars,
562 std::function<
int(
int64)> start_empty_path_class,
563 int num_arcs_to_consider,
569 std::string
DebugString()
const override {
return "RelocateExpensiveChain"; }
572 void OnNodeInitialization()
override;
573 void IncrementCurrentPath();
574 bool IncrementCurrentArcIndices();
578 bool FindMostExpensiveChainsOnRemainingPaths();
580 int num_arcs_to_consider_;
582 std::vector<std::pair<int64, int>> most_expensive_arc_starts_and_ranks_;
586 current_expensive_arc_indices_;
589 arc_cost_for_path_start_;
593 bool has_non_empty_paths_to_explore_;
603 template <
bool swap_first>
607 const std::vector<IntVar*>& secondary_vars,
608 std::function<
int(
int64)> start_empty_path_class,
615 return "PairNodeSwapActiveOperator";
632 void OnNodeInitialization()
override;
641 template <
bool swap_first>
643 const std::vector<IntVar*>& vars,
644 const std::vector<IntVar*>& secondary_vars,
645 std::function<
int(
int64)> start_empty_path_class,
648 std::move(start_empty_path_class)),
650 pairs_(index_pairs) {}
652 template <
bool swap_first>
656 if (base_index == 0 || StartNode(base_index) != StartNode(base_index - 1)) {
657 return StartNode(base_index);
659 return BaseNode(base_index - 1);
663 template <
bool swap_first>
665 for (
int i = 0; i < pairs_.size(); ++i) {
666 if (IsInactive(pairs_[i].first[0]) && IsInactive(pairs_[i].second[0])) {
671 inactive_pair_ = pairs_.size();
674 template <
bool swap_first>
677 while (inactive_pair_ < pairs_.size()) {
678 if (!IsInactive(pairs_[inactive_pair_].first[0]) ||
679 !IsInactive(pairs_[inactive_pair_].second[0]) ||
690 template <
bool swap_first>
692 const int64 base = BaseNode(0);
693 if (IsPathEnd(base)) {
696 const int64 pair_first = pairs_[inactive_pair_].first[0];
697 const int64 pair_second = pairs_[inactive_pair_].second[0];
699 return MakeActive(pair_second, BaseNode(1)) &&
700 MakeActive(pair_first, base) &&
701 MakeChainInactive(pair_first, Next(pair_first));
703 return MakeActive(pair_second, BaseNode(1)) &&
704 MakeActive(pair_first, base) &&
705 MakeChainInactive(pair_second, Next(pair_second));
723 const std::vector<IntVar*>& secondary_vars,
724 std::function<
int(
int64)> start_empty_path_class,
727 std::string
DebugString()
const override {
return "RelocateSubtrip"; }
732 bool RelocateSubTripFromPickup(
int64 chain_first_node,
int64 insertion_node);
734 bool RelocateSubTripFromDelivery(
int64 chain_last_node,
int64 insertion_node);
735 std::vector<bool> is_pickup_node_;
736 std::vector<bool> is_delivery_node_;
737 std::vector<int> pair_of_node_;
741 std::vector<bool> opened_pairs_bitset_;
743 std::vector<int64> rejected_nodes_;
744 std::vector<int64> subtrip_nodes_;
750 const std::vector<IntVar*>& secondary_vars,
751 std::function<
int(
int64)> start_empty_path_class,
754 std::string
DebugString()
const override {
return "ExchangeSubtrip"; }
766 bool ExtractChainsAndCheckCanonical(
int64 base_node,
767 std::vector<int64>* rejects,
768 std::vector<int64>* subtrip);
774 bool ExtractChainsFromPickup(
int64 base_node, std::vector<int64>* rejects,
775 std::vector<int64>* subtrip);
781 bool ExtractChainsFromDelivery(
int64 base_node, std::vector<int64>* rejects,
782 std::vector<int64>* subtrip);
783 void SetPath(
const std::vector<int64>& path,
int path_id);
786 std::vector<bool> is_pickup_node_;
787 std::vector<bool> is_delivery_node_;
788 std::vector<int> pair_of_node_;
790 std::vector<bool> opened_pairs_set_;
792 std::vector<int64> rejects0_;
793 std::vector<int64> subtrip0_;
794 std::vector<int64> rejects1_;
795 std::vector<int64> subtrip1_;
796 std::vector<int64> path0_;
797 std::vector<int64> path1_;
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
An Assignment is a variable -> domains mapping, used to report solutions to the user.
bool MakeNeighbor() override
ExchangeSubtrip(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &pairs)
std::string DebugString() const override
Filtered heuristic LNS operator, where the destruction phase consists of removing a node and the 'num...
~FilteredHeuristicCloseNodesLNSOperator() override
FilteredHeuristicCloseNodesLNSOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic, int num_close_nodes)
std::string DebugString() const override
Similar to the heuristic path LNS above, but instead of removing one route entirely,...
FilteredHeuristicExpensiveChainLNSOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic, int num_arcs_to_consider, std::function< int64(int64, int64, int64)> arc_cost_for_route_start)
~FilteredHeuristicExpensiveChainLNSOperator() override
std::string DebugString() const override
Class of operators using a RoutingFilteredHeuristic to insert unperformed nodes after changes have be...
~FilteredHeuristicLocalSearchOperator() override
FilteredHeuristicLocalSearchOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic, bool keep_inverse_values=false)
virtual std::function< int64(int64)> SetupNextAccessorForNeighbor()=0
Virtual method to return the next_accessor to be passed to the heuristic to build a new solution.
virtual bool IncrementPosition()=0
std::string HeuristicName() const
SparseBitset removed_nodes_
Keeps track of removed nodes when making a neighbor.
const RoutingModel & model_
LNS-like operator based on a filtered first solution heuristic to rebuild the solution,...
FilteredHeuristicPathLNSOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic)
std::string DebugString() const override
~FilteredHeuristicPathLNSOperator() override
Operator which inserts inactive nodes into a path and makes a pair of active nodes inactive.
bool MakeNeighbor() override
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
IndexPairSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
~IndexPairSwapActiveOperator() override
std::string DebugString() const override
Specialization of LocalSearchOperator built from an array of IntVars which specifies the scope of the...
int64 InverseValue(int64 index) const
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
bool MakeNeighbor() override
~LightPairRelocateOperator() override
LightPairRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
std::string DebugString() const override
Pair-based neighborhood operators, designed to move nodes by pairs (pairs are static and given).
bool MakeNeighbor() override
~MakePairActiveOperator() override
bool RestartAtPathStartOnSynchronize() override
Required to ensure that after synchronization the operator is in a state compatible with GetBaseNodeR...
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
MakePairActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &pairs)
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
std::string DebugString() const override
Operator which makes pairs of active nodes inactive.
MakePairInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
bool MakeNeighbor() override
std::string DebugString() const override
Relocate neighborhood which moves chains of neighbors.
bool MakeNeighbor() override
MakeRelocateNeighborsOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, RoutingTransitCallback2 arc_evaluator)
~MakeRelocateNeighborsOperator() override
std::string DebugString() const override
Operator which exchanges the position of two pairs; for both pairs the first node of the pair must be...
bool MakeNeighbor() override
PairExchangeOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
~PairExchangeOperator() override
std::string DebugString() const override
Operator which exchanges the paths of two pairs (path have to be different).
bool MakeNeighbor() override
~PairExchangeRelocateOperator() override
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
PairExchangeRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
std::string DebugString() const override
Operator which inserts pairs of inactive nodes into a path and makes an active node inactive.
bool MakeNeighbor() override
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
~PairNodeSwapActiveOperator() override
bool RestartAtPathStartOnSynchronize() override
Required to ensure that after synchronization the operator is in a state compatible with GetBaseNodeR...
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
PairNodeSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
std::string DebugString() const override
Operator which moves a pair of nodes to another position where the first node of the pair must be bef...
bool MakeNeighbor() override
~PairRelocateOperator() override
PairRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
bool ConsiderAlternatives(int64 base_index) const override
Indicates if alternatives should be considered when iterating over base nodes.
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
std::string DebugString() const override
Base class of the local search operators dedicated to path modifications (a path is a set of nodes li...
bool MakeNeighbor() override
RelocateExpensiveChain(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, int num_arcs_to_consider, std::function< int64(int64, int64, int64)> arc_cost_for_path_start)
~RelocateExpensiveChain() override
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
std::string DebugString() const override
Tries to move subtrips after an insertion node.
bool MakeNeighbor() override
RelocateSubtrip(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &pairs)
std::string DebugString() const override
int64 Size() const
Returns the number of next variables in the model.
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
Operator which iterates through each alternative of a set of pairs.
void OnStart() override
Called by Start() after synchronizing the operator with the current assignment.
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
~SwapIndexPairOperator() override
SwapIndexPairOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &path_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
std::string DebugString() const override
const int64 & Value(int64 index) const
Returns the value in the current assignment of the variable of given index.
void SetValue(int64 index, const int64 &value)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::function< int64(int64, int64)> RoutingTransitCallback2
std::vector< RoutingIndexPair > RoutingIndexPairs