1 // Copyright 2010-2021 Google LLC 2 // Licensed under the Apache License, Version 2.0 (the "License"); 3 // you may not use this file except in compliance with the License. 4 // You may obtain a copy of the License at 5 // 6 // http://www.apache.org/licenses/LICENSE-2.0 7 // 8 // Unless required by applicable law or agreed to in writing, software 9 // distributed under the License is distributed on an "AS IS" BASIS, 10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 // See the License for the specific language governing permissions and 12 // limitations under the License. 13 14 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_ 15 #define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_ 16 17 #include <sys/types.h> 18 19 #include <algorithm> 20 #include <functional> 21 #include <iterator> 22 #include <memory> 23 #include <set> 24 #include <string> 25 #include <tuple> 26 #include <utility> 27 #include <vector> 28 29 #include "absl/container/flat_hash_set.h" 30 #include "ortools/base/adjustable_priority_queue.h" 31 #include "ortools/base/integral_types.h" 32 #include "ortools/base/logging.h" 33 #include "ortools/base/macros.h" 34 #include "ortools/base/mathutil.h" 35 #include "ortools/constraint_solver/constraint_solver.h" 36 #include "ortools/constraint_solver/constraint_solveri.h" 37 #include "ortools/constraint_solver/routing.h" 38 #include "ortools/constraint_solver/routing_index_manager.h" 39 #include "ortools/util/bitset.h" 40 41 namespace operations_research { 42 43 class IntVarFilteredHeuristic; 44 #ifndef SWIG 45 /// Helper class that manages vehicles. This class is based on the 46 /// RoutingModel::VehicleTypeContainer that sorts and stores vehicles based on 47 /// their "type". 48 class VehicleTypeCurator { 49 public: VehicleTypeCurator(const RoutingModel::VehicleTypeContainer & vehicle_type_container)50 explicit VehicleTypeCurator( 51 const RoutingModel::VehicleTypeContainer& vehicle_type_container) 52 : vehicle_type_container_(&vehicle_type_container) {} 53 NumTypes()54 int NumTypes() const { return vehicle_type_container_->NumTypes(); } 55 Type(int vehicle)56 int Type(int vehicle) const { return vehicle_type_container_->Type(vehicle); } 57 58 /// Resets the vehicles stored, storing only vehicles from the 59 /// vehicle_type_container_ for which store_vehicle() returns true. 60 void Reset(const std::function<bool(int)>& store_vehicle); 61 62 /// Goes through all the currently stored vehicles and removes vehicles for 63 /// which remove_vehicle() returns true. 64 void Update(const std::function<bool(int)>& remove_vehicle); 65 GetLowestFixedCostVehicleOfType(int type)66 int GetLowestFixedCostVehicleOfType(int type) const { 67 DCHECK_LT(type, NumTypes()); 68 const std::set<VehicleClassEntry>& vehicle_classes = 69 sorted_vehicle_classes_per_type_[type]; 70 if (vehicle_classes.empty()) { 71 return -1; 72 } 73 const int vehicle_class = (vehicle_classes.begin())->vehicle_class; 74 DCHECK(!vehicles_per_vehicle_class_[vehicle_class].empty()); 75 return vehicles_per_vehicle_class_[vehicle_class][0]; 76 } 77 ReinjectVehicleOfClass(int vehicle,int vehicle_class,int64_t fixed_cost)78 void ReinjectVehicleOfClass(int vehicle, int vehicle_class, 79 int64_t fixed_cost) { 80 std::vector<int>& vehicles = vehicles_per_vehicle_class_[vehicle_class]; 81 if (vehicles.empty()) { 82 /// Add the vehicle class entry to the set (it was removed when 83 /// vehicles_per_vehicle_class_[vehicle_class] got empty). 84 std::set<VehicleClassEntry>& vehicle_classes = 85 sorted_vehicle_classes_per_type_[Type(vehicle)]; 86 const auto& insertion = 87 vehicle_classes.insert({vehicle_class, fixed_cost}); 88 DCHECK(insertion.second); 89 } 90 vehicles.push_back(vehicle); 91 } 92 93 /// Searches a compatible vehicle of the given type; returns false if none was 94 /// found. 95 bool HasCompatibleVehicleOfType( 96 int type, const std::function<bool(int)>& vehicle_is_compatible) const; 97 /// Searches for the best compatible vehicle of the given type, i.e. the first 98 /// vehicle v of type 'type' for which vehicle_is_compatible(v) returns true. 99 /// If a compatible *vehicle* is found, its index is removed from 100 /// vehicles_per_vehicle_class_ and the function returns {vehicle, -1}. 101 /// If for some *vehicle* 'stop_and_return_vehicle' returns true before a 102 /// compatible vehicle is found, the function simply returns {-1, vehicle}. 103 /// Returns {-1, -1} if no compatible vehicle is found and the stopping 104 /// condition is never met. 105 std::pair<int, int> GetCompatibleVehicleOfType( 106 int type, std::function<bool(int)> vehicle_is_compatible, 107 std::function<bool(int)> stop_and_return_vehicle); 108 109 private: 110 using VehicleClassEntry = 111 RoutingModel::VehicleTypeContainer::VehicleClassEntry; 112 const RoutingModel::VehicleTypeContainer* const vehicle_type_container_; 113 // clang-format off 114 std::vector<std::set<VehicleClassEntry> > sorted_vehicle_classes_per_type_; 115 std::vector<std::vector<int> > vehicles_per_vehicle_class_; 116 // clang-format on 117 }; 118 119 /// Returns the best value for the automatic first solution strategy, based on 120 /// the given model parameters. 121 operations_research::FirstSolutionStrategy::Value 122 AutomaticFirstSolutionStrategy(bool has_pickup_deliveries, 123 bool has_node_precedences, 124 bool has_single_vehicle_node); 125 126 /// Decision builder building a solution using heuristics with local search 127 /// filters to evaluate its feasibility. This is very fast but can eventually 128 /// fail when the solution is restored if filters did not detect all 129 /// infeasiblities. 130 /// More details: 131 /// Using local search filters to build a solution. The approach is pretty 132 /// straight-forward: have a general assignment storing the current solution, 133 /// build delta assignment representing possible extensions to the current 134 /// solution and validate them with filters. 135 /// The tricky bit comes from using the assignment and filter APIs in a way 136 /// which avoids the lazy creation of internal hash_maps between variables 137 /// and indices. 138 139 /// Generic filter-based decision builder using an IntVarFilteredHeuristic. 140 // TODO(user): Eventually move this to the core CP solver library 141 /// when the code is mature enough. 142 class IntVarFilteredDecisionBuilder : public DecisionBuilder { 143 public: 144 explicit IntVarFilteredDecisionBuilder( 145 std::unique_ptr<IntVarFilteredHeuristic> heuristic); 146 ~IntVarFilteredDecisionBuilder()147 ~IntVarFilteredDecisionBuilder() override {} 148 149 Decision* Next(Solver* solver) override; 150 151 std::string DebugString() const override; 152 153 /// Returns statistics from its underlying heuristic. 154 int64_t number_of_decisions() const; 155 int64_t number_of_rejects() const; 156 157 private: 158 const std::unique_ptr<IntVarFilteredHeuristic> heuristic_; 159 }; 160 161 /// Generic filter-based heuristic applied to IntVars. 162 class IntVarFilteredHeuristic { 163 public: 164 IntVarFilteredHeuristic(Solver* solver, const std::vector<IntVar*>& vars, 165 LocalSearchFilterManager* filter_manager); 166 ~IntVarFilteredHeuristic()167 virtual ~IntVarFilteredHeuristic() {} 168 169 /// Builds a solution. Returns the resulting assignment if a solution was 170 /// found, and nullptr otherwise. 171 Assignment* const BuildSolution(); 172 173 /// Returns statistics on search, number of decisions sent to filters, number 174 /// of decisions rejected by filters. number_of_decisions()175 int64_t number_of_decisions() const { return number_of_decisions_; } number_of_rejects()176 int64_t number_of_rejects() const { return number_of_rejects_; } 177 DebugString()178 virtual std::string DebugString() const { return "IntVarFilteredHeuristic"; } 179 180 protected: 181 /// Resets the data members for a new solution. 182 void ResetSolution(); 183 /// Virtual method to initialize the solution. InitializeSolution()184 virtual bool InitializeSolution() { return true; } 185 /// Virtual method to redefine how to build a solution. 186 virtual bool BuildSolutionInternal() = 0; 187 /// Commits the modifications to the current solution if these modifications 188 /// are "filter-feasible", returns false otherwise; in any case discards 189 /// all modifications. 190 bool Commit(); 191 /// Returns true if the search must be stopped. StopSearch()192 virtual bool StopSearch() { return false; } 193 /// Modifies the current solution by setting the variable of index 'index' to 194 /// value 'value'. SetValue(int64_t index,int64_t value)195 void SetValue(int64_t index, int64_t value) { 196 if (!is_in_delta_[index]) { 197 delta_->FastAdd(vars_[index])->SetValue(value); 198 delta_indices_.push_back(index); 199 is_in_delta_[index] = true; 200 } else { 201 delta_->SetValue(vars_[index], value); 202 } 203 } 204 /// Returns the value of the variable of index 'index' in the last committed 205 /// solution. Value(int64_t index)206 int64_t Value(int64_t index) const { 207 return assignment_->IntVarContainer().Element(index).Value(); 208 } 209 /// Returns true if the variable of index 'index' is in the current solution. Contains(int64_t index)210 bool Contains(int64_t index) const { 211 return assignment_->IntVarContainer().Element(index).Var() != nullptr; 212 } 213 /// Returns the number of variables the decision builder is trying to 214 /// instantiate. Size()215 int Size() const { return vars_.size(); } 216 /// Returns the variable of index 'index'. Var(int64_t index)217 IntVar* Var(int64_t index) const { return vars_[index]; } 218 /// Synchronizes filters with an assignment (the current solution). 219 void SynchronizeFilters(); 220 221 Assignment* const assignment_; 222 223 private: 224 /// Checks if filters accept a given modification to the current solution 225 /// (represented by delta). 226 bool FilterAccept(); 227 228 Solver* solver_; 229 const std::vector<IntVar*> vars_; 230 Assignment* const delta_; 231 std::vector<int> delta_indices_; 232 std::vector<bool> is_in_delta_; 233 Assignment* const empty_; 234 LocalSearchFilterManager* filter_manager_; 235 /// Stats on search 236 int64_t number_of_decisions_; 237 int64_t number_of_rejects_; 238 }; 239 240 /// Filter-based heuristic dedicated to routing. 241 class RoutingFilteredHeuristic : public IntVarFilteredHeuristic { 242 public: 243 RoutingFilteredHeuristic(RoutingModel* model, 244 LocalSearchFilterManager* filter_manager); ~RoutingFilteredHeuristic()245 ~RoutingFilteredHeuristic() override {} 246 /// Builds a solution starting from the routes formed by the next accessor. 247 const Assignment* BuildSolutionFromRoutes( 248 const std::function<int64_t(int64_t)>& next_accessor); model()249 RoutingModel* model() const { return model_; } 250 /// Returns the end of the start chain of vehicle, GetStartChainEnd(int vehicle)251 int GetStartChainEnd(int vehicle) const { return start_chain_ends_[vehicle]; } 252 /// Returns the start of the end chain of vehicle, GetEndChainStart(int vehicle)253 int GetEndChainStart(int vehicle) const { return end_chain_starts_[vehicle]; } 254 /// Make nodes in the same disjunction as 'node' unperformed. 'node' is a 255 /// variable index corresponding to a node. 256 void MakeDisjunctionNodesUnperformed(int64_t node); 257 /// Make all unassigned nodes unperformed. 258 void MakeUnassignedNodesUnperformed(); 259 /// Make all partially performed pickup and delivery pairs unperformed. A 260 /// pair is partially unperformed if one element of the pair has one of its 261 /// alternatives performed in the solution and the other has no alternatives 262 /// in the solution or none performed. 263 void MakePartiallyPerformedPairsUnperformed(); 264 265 protected: StopSearch()266 bool StopSearch() override { return model_->CheckLimit(); } SetVehicleIndex(int64_t node,int vehicle)267 virtual void SetVehicleIndex(int64_t node, int vehicle) {} ResetVehicleIndices()268 virtual void ResetVehicleIndices() {} VehicleIsEmpty(int vehicle)269 bool VehicleIsEmpty(int vehicle) const { 270 return Value(model()->Start(vehicle)) == model()->End(vehicle); 271 } 272 273 private: 274 /// Initializes the current solution with empty or partial vehicle routes. 275 bool InitializeSolution() override; 276 277 RoutingModel* const model_; 278 std::vector<int64_t> start_chain_ends_; 279 std::vector<int64_t> end_chain_starts_; 280 }; 281 282 class CheapestInsertionFilteredHeuristic : public RoutingFilteredHeuristic { 283 public: 284 /// Takes ownership of evaluator. 285 CheapestInsertionFilteredHeuristic( 286 RoutingModel* model, 287 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator, 288 std::function<int64_t(int64_t)> penalty_evaluator, 289 LocalSearchFilterManager* filter_manager); ~CheapestInsertionFilteredHeuristic()290 ~CheapestInsertionFilteredHeuristic() override {} 291 292 protected: 293 struct NodeInsertion { 294 int64_t insert_after; 295 int vehicle; 296 int64_t value; 297 298 bool operator<(const NodeInsertion& other) const { 299 return std::tie(value, insert_after, vehicle) < 300 std::tie(other.value, other.insert_after, other.vehicle); 301 } 302 }; 303 struct StartEndValue { 304 int64_t num_allowed_vehicles; 305 int64_t distance; 306 int vehicle; 307 308 bool operator<(const StartEndValue& other) const { 309 return std::tie(num_allowed_vehicles, distance, vehicle) < 310 std::tie(other.num_allowed_vehicles, other.distance, 311 other.vehicle); 312 } 313 }; 314 typedef std::pair<StartEndValue, /*seed_node*/ int> Seed; 315 316 /// Computes and returns the distance of each uninserted node to every vehicle 317 /// in "vehicles" as a std::vector<std::vector<StartEndValue>>, 318 /// start_end_distances_per_node. 319 /// For each node, start_end_distances_per_node[node] is sorted in decreasing 320 /// order. 321 // clang-format off 322 std::vector<std::vector<StartEndValue> > 323 ComputeStartEndDistanceForVehicles(const std::vector<int>& vehicles); 324 325 /// Initializes the priority_queue by inserting the best entry corresponding 326 /// to each node, i.e. the last element of start_end_distances_per_node[node], 327 /// which is supposed to be sorted in decreasing order. 328 /// Queue is a priority queue containing Seeds. 329 template <class Queue> 330 void InitializePriorityQueue( 331 std::vector<std::vector<StartEndValue> >* start_end_distances_per_node, 332 Queue* priority_queue); 333 // clang-format on 334 335 /// Inserts 'node' just after 'predecessor', and just before 'successor', 336 /// resulting in the following subsequence: predecessor -> node -> successor. 337 /// If 'node' is part of a disjunction, other nodes of the disjunction are 338 /// made unperformed. 339 void InsertBetween(int64_t node, int64_t predecessor, int64_t successor); 340 /// Helper method to the ComputeEvaluatorSortedPositions* methods. Finds all 341 /// possible insertion positions of node 'node_to_insert' in the partial route 342 /// starting at node 'start' and adds them to 'node_insertions' (no sorting is 343 /// done). 344 void AppendInsertionPositionsAfter( 345 int64_t node_to_insert, int64_t start, int64_t next_after_start, 346 int vehicle, std::vector<NodeInsertion>* node_insertions); 347 /// Returns the cost of inserting 'node_to_insert' between 'insert_after' and 348 /// 'insert_before' on the 'vehicle', i.e. 349 /// Cost(insert_after-->node) + Cost(node-->insert_before) 350 /// - Cost (insert_after-->insert_before). 351 // TODO(user): Replace 'insert_before' and 'insert_after' by 'predecessor' 352 // and 'successor' in the code. 353 int64_t GetInsertionCostForNodeAtPosition(int64_t node_to_insert, 354 int64_t insert_after, 355 int64_t insert_before, 356 int vehicle) const; 357 /// Returns the cost of unperforming node 'node_to_insert'. Returns kint64max 358 /// if penalty callback is null or if the node cannot be unperformed. 359 int64_t GetUnperformedValue(int64_t node_to_insert) const; 360 361 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator_; 362 std::function<int64_t(int64_t)> penalty_evaluator_; 363 }; 364 365 /// Filter-based decision builder which builds a solution by inserting 366 /// nodes at their cheapest position on any route; potentially several routes 367 /// can be built in parallel. The cost of a position is computed from an 368 /// arc-based cost callback. The node selected for insertion is the one which 369 /// minimizes insertion cost. If a non null penalty evaluator is passed, making 370 /// nodes unperformed is also taken into account with the corresponding penalty 371 /// cost. 372 class GlobalCheapestInsertionFilteredHeuristic 373 : public CheapestInsertionFilteredHeuristic { 374 public: 375 struct GlobalCheapestInsertionParameters { 376 /// Whether the routes are constructed sequentially or in parallel. 377 bool is_sequential; 378 /// The ratio of routes on which to insert farthest nodes as seeds before 379 /// starting the cheapest insertion. 380 double farthest_seeds_ratio; 381 /// If neighbors_ratio < 1 then for each node only this ratio of its 382 /// neighbors leading to the smallest arc costs are considered for 383 /// insertions, with a minimum of 'min_neighbors': 384 /// num_closest_neighbors = max(min_neighbors, neighbors_ratio*N), 385 /// where N is the number of non-start/end nodes in the model. 386 double neighbors_ratio; 387 int64_t min_neighbors; 388 /// If true, only closest neighbors (see neighbors_ratio and min_neighbors) 389 /// are considered as insertion positions during initialization. Otherwise, 390 /// all possible insertion positions are considered. 391 bool use_neighbors_ratio_for_initialization; 392 /// If true, entries are created for making the nodes/pairs unperformed, and 393 /// when the cost of making a node unperformed is lower than all insertions, 394 /// the node/pair will be made unperformed. If false, only entries making 395 /// a node/pair performed are considered. 396 bool add_unperformed_entries; 397 }; 398 399 /// Takes ownership of evaluators. 400 GlobalCheapestInsertionFilteredHeuristic( 401 RoutingModel* model, 402 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator, 403 std::function<int64_t(int64_t)> penalty_evaluator, 404 LocalSearchFilterManager* filter_manager, 405 GlobalCheapestInsertionParameters parameters); ~GlobalCheapestInsertionFilteredHeuristic()406 ~GlobalCheapestInsertionFilteredHeuristic() override {} 407 bool BuildSolutionInternal() override; DebugString()408 std::string DebugString() const override { 409 return "GlobalCheapestInsertionFilteredHeuristic"; 410 } 411 412 private: 413 class NodeEntry; 414 class PairEntry; 415 416 typedef absl::flat_hash_set<PairEntry*> PairEntries; 417 typedef absl::flat_hash_set<NodeEntry*> NodeEntries; 418 419 /// Inserts non-inserted single nodes or pickup/delivery pairs which have a 420 /// visit type in the type requirement graph, i.e. required for or requiring 421 /// another type for insertions. 422 /// These nodes are inserted iff the requirement graph is acyclic, in which 423 /// case nodes are inserted based on the topological order of their type, 424 /// given by the routing model's GetTopologicallySortedVisitTypes() method. 425 bool InsertPairsAndNodesByRequirementTopologicalOrder(); 426 427 /// Inserts non-inserted pickup and delivery pairs. Maintains a priority 428 /// queue of possible pair insertions, which is incrementally updated when a 429 /// pair insertion is committed. Incrementality is obtained by updating pair 430 /// insertion positions on the four newly modified route arcs: after the 431 /// pickup insertion position, after the pickup position, after the delivery 432 /// insertion position and after the delivery position. 433 bool InsertPairs( 434 const std::map<int64_t, std::vector<int>>& pair_indices_by_bucket); 435 436 /// Returns true iff the empty_vehicle_type_curator_ should be used to insert 437 /// nodes/pairs on the given vehicle, i.e. iff the route of the given vehicle 438 /// is empty and 'all_vehicles' is true. 439 bool UseEmptyVehicleTypeCuratorForVehicle(int vehicle, 440 bool all_vehicles = true) { 441 return vehicle >= 0 && VehicleIsEmpty(vehicle) && all_vehicles; 442 } 443 444 /// Tries to insert the pickup/delivery pair on a vehicle of the same type and 445 /// same fixed cost as the pair_entry.vehicle() using the 446 /// empty_vehicle_type_curator_, and updates the pair_entry accordingly if the 447 /// insertion was not possible. 448 /// NOTE: Assumes (DCHECKS) that 449 /// UseEmptyVehicleTypeCuratorForVehicle(pair_entry.vehicle()) is true. 450 bool InsertPairEntryUsingEmptyVehicleTypeCurator( 451 const std::vector<int>& pair_indices, PairEntry* const pair_entry, 452 AdjustablePriorityQueue<PairEntry>* priority_queue, 453 std::vector<PairEntries>* pickup_to_entries, 454 std::vector<PairEntries>* delivery_to_entries); 455 456 /// Inserts non-inserted individual nodes on the given routes (or all routes 457 /// if "vehicles" is an empty vector), by constructing routes in parallel. 458 /// Maintains a priority queue of possible insertions, which is incrementally 459 /// updated when an insertion is committed. 460 /// Incrementality is obtained by updating insertion positions on the two 461 /// newly modified route arcs: after the node insertion position and after the 462 /// node position. 463 bool InsertNodesOnRoutes( 464 const std::map<int64_t, std::vector<int>>& nodes_by_bucket, 465 const absl::flat_hash_set<int>& vehicles); 466 467 /// Tries to insert the node_entry.node_to_insert on a vehicle of the same 468 /// type and same fixed cost as the node_entry.vehicle() using the 469 /// empty_vehicle_type_curator_, and updates the node_entry accordingly if the 470 /// insertion was not possible. 471 /// NOTE: Assumes (DCHECKS) that 472 /// UseEmptyVehicleTypeCuratorForVehicle(node_entry.vehicle(), all_vehicles) 473 /// is true. 474 bool InsertNodeEntryUsingEmptyVehicleTypeCurator( 475 const std::vector<int>& nodes, bool all_vehicles, 476 NodeEntry* const node_entry, 477 AdjustablePriorityQueue<NodeEntry>* priority_queue, 478 std::vector<NodeEntries>* position_to_node_entries); 479 480 /// Inserts non-inserted individual nodes on routes by constructing routes 481 /// sequentially. 482 /// For each new route, the vehicle to use and the first node to insert on it 483 /// are given by calling InsertSeedNode(). The route is then completed with 484 /// other nodes by calling InsertNodesOnRoutes({vehicle}). 485 bool SequentialInsertNodes( 486 const std::map<int64_t, std::vector<int>>& nodes_by_bucket); 487 488 /// Goes through all vehicles in the model to check if they are already used 489 /// (i.e. Value(start) != end) or not. 490 /// Updates the three passed vectors accordingly. 491 void DetectUsedVehicles(std::vector<bool>* is_vehicle_used, 492 std::vector<int>* unused_vehicles, 493 absl::flat_hash_set<int>* used_vehicles); 494 495 /// Inserts the (farthest_seeds_ratio_ * model()->vehicles()) nodes farthest 496 /// from the start/ends of the available vehicle routes as seeds on their 497 /// closest route. 498 void InsertFarthestNodesAsSeeds(); 499 500 /// Inserts a "seed node" based on the given priority_queue of Seeds. 501 /// A "seed" is the node used in order to start a new route. 502 /// If the Seed at the top of the priority queue cannot be inserted, 503 /// (node already inserted in the model, corresponding vehicle already used, 504 /// or unsuccessful Commit()), start_end_distances_per_node is updated and 505 /// used to insert a new entry for that node if necessary (next best vehicle). 506 /// If a seed node is successfully inserted, updates is_vehicle_used and 507 /// returns the vehice of the corresponding route. Returns -1 otherwise. 508 template <class Queue> 509 int InsertSeedNode( 510 std::vector<std::vector<StartEndValue>>* start_end_distances_per_node, 511 Queue* priority_queue, std::vector<bool>* is_vehicle_used); 512 // clang-format on 513 514 /// Initializes the priority queue and the pair entries for the given pair 515 /// indices with the current state of the solution. 516 bool InitializePairPositions( 517 const std::vector<int>& pair_indices, 518 AdjustablePriorityQueue<PairEntry>* priority_queue, 519 std::vector<PairEntries>* pickup_to_entries, 520 std::vector<PairEntries>* delivery_to_entries); 521 /// Adds insertion entries performing the 'pickup' and 'delivery', and updates 522 /// 'priority_queue', pickup_to_entries and delivery_to_entries accordingly. 523 /// Based on gci_params_.use_neighbors_ratio_for_initialization, either all 524 /// contained nodes are considered as insertion positions, or only the 525 /// closest neighbors of 'pickup' and/or 'delivery'. 526 void InitializeInsertionEntriesPerformingPair( 527 int64_t pickup, int64_t delivery, 528 AdjustablePriorityQueue<PairEntry>* priority_queue, 529 std::vector<PairEntries>* pickup_to_entries, 530 std::vector<PairEntries>* delivery_to_entries); 531 /// Performs all the necessary updates after a pickup/delivery pair was 532 /// successfully inserted on the 'vehicle', respectively after 533 /// 'pickup_position' and 'delivery_position'. 534 bool UpdateAfterPairInsertion( 535 const std::vector<int>& pair_indices, int vehicle, int64_t pickup, 536 int64_t pickup_position, int64_t delivery, int64_t delivery_position, 537 AdjustablePriorityQueue<PairEntry>* priority_queue, 538 std::vector<PairEntries>* pickup_to_entries, 539 std::vector<PairEntries>* delivery_to_entries); 540 /// Updates all pair entries inserting a node after node "insert_after" and 541 /// updates the priority queue accordingly. UpdatePairPositions(const std::vector<int> & pair_indices,int vehicle,int64_t insert_after,AdjustablePriorityQueue<PairEntry> * priority_queue,std::vector<PairEntries> * pickup_to_entries,std::vector<PairEntries> * delivery_to_entries)542 bool UpdatePairPositions(const std::vector<int>& pair_indices, int vehicle, 543 int64_t insert_after, 544 AdjustablePriorityQueue<PairEntry>* priority_queue, 545 std::vector<PairEntries>* pickup_to_entries, 546 std::vector<PairEntries>* delivery_to_entries) { 547 return UpdatePickupPositions(pair_indices, vehicle, insert_after, 548 priority_queue, pickup_to_entries, 549 delivery_to_entries) && 550 UpdateDeliveryPositions(pair_indices, vehicle, insert_after, 551 priority_queue, pickup_to_entries, 552 delivery_to_entries); 553 } 554 /// Updates all pair entries inserting their pickup node after node 555 /// "insert_after" and updates the priority queue accordingly. 556 bool UpdatePickupPositions(const std::vector<int>& pair_indices, int vehicle, 557 int64_t pickup_insert_after, 558 AdjustablePriorityQueue<PairEntry>* priority_queue, 559 std::vector<PairEntries>* pickup_to_entries, 560 std::vector<PairEntries>* delivery_to_entries); 561 /// Updates all pair entries inserting their delivery node after node 562 /// "insert_after" and updates the priority queue accordingly. 563 bool UpdateDeliveryPositions( 564 const std::vector<int>& pair_indices, int vehicle, 565 int64_t delivery_insert_after, 566 AdjustablePriorityQueue<PairEntry>* priority_queue, 567 std::vector<PairEntries>* pickup_to_entries, 568 std::vector<PairEntries>* delivery_to_entries); 569 /// Deletes an entry, removing it from the priority queue and the appropriate 570 /// pickup and delivery entry sets. 571 void DeletePairEntry(PairEntry* entry, 572 AdjustablePriorityQueue<PairEntry>* priority_queue, 573 std::vector<PairEntries>* pickup_to_entries, 574 std::vector<PairEntries>* delivery_to_entries); 575 /// Creates a PairEntry corresponding to the insertion of 'pickup' and 576 /// 'delivery' respectively after 'pickup_insert_after' and 577 /// 'delivery_insert_after', and adds it to the 'priority_queue', 578 /// 'pickup_entries' and 'delivery_entries'. 579 void AddPairEntry(int64_t pickup, int64_t pickup_insert_after, 580 int64_t delivery, int64_t delivery_insert_after, 581 int vehicle, 582 AdjustablePriorityQueue<PairEntry>* priority_queue, 583 std::vector<PairEntries>* pickup_entries, 584 std::vector<PairEntries>* delivery_entries) const; 585 /// Updates the pair entry's value and rearranges the priority queue 586 /// accordingly. 587 void UpdatePairEntry( 588 PairEntry* const pair_entry, 589 AdjustablePriorityQueue<PairEntry>* priority_queue) const; 590 /// Computes and returns the insertion value of inserting 'pickup' and 591 /// 'delivery' respectively after 'pickup_insert_after' and 592 /// 'delivery_insert_after' on 'vehicle'. 593 int64_t GetInsertionValueForPairAtPositions(int64_t pickup, 594 int64_t pickup_insert_after, 595 int64_t delivery, 596 int64_t delivery_insert_after, 597 int vehicle) const; 598 599 /// Initializes the priority queue and the node entries with the current state 600 /// of the solution on the given vehicle routes. 601 bool InitializePositions(const std::vector<int>& nodes, 602 const absl::flat_hash_set<int>& vehicles, 603 AdjustablePriorityQueue<NodeEntry>* priority_queue, 604 std::vector<NodeEntries>* position_to_node_entries); 605 /// Adds insertion entries performing 'node', and updates 'priority_queue' and 606 /// position_to_node_entries accordingly. 607 /// Based on gci_params_.use_neighbors_ratio_for_initialization, either all 608 /// contained nodes are considered as insertion positions, or only the 609 /// closest neighbors of 'node'. 610 void InitializeInsertionEntriesPerformingNode( 611 int64_t node, const absl::flat_hash_set<int>& vehicles, 612 AdjustablePriorityQueue<NodeEntry>* priority_queue, 613 std::vector<NodeEntries>* position_to_node_entries); 614 /// Updates all node entries inserting a node after node "insert_after" and 615 /// updates the priority queue accordingly. 616 bool UpdatePositions(const std::vector<int>& nodes, int vehicle, 617 int64_t insert_after, bool all_vehicles, 618 AdjustablePriorityQueue<NodeEntry>* priority_queue, 619 std::vector<NodeEntries>* node_entries); 620 /// Deletes an entry, removing it from the priority queue and the appropriate 621 /// node entry sets. 622 void DeleteNodeEntry(NodeEntry* entry, 623 AdjustablePriorityQueue<NodeEntry>* priority_queue, 624 std::vector<NodeEntries>* node_entries); 625 626 /// Creates a NodeEntry corresponding to the insertion of 'node' after 627 /// 'insert_after' on 'vehicle' and adds it to the 'priority_queue' and 628 /// 'node_entries'. 629 void AddNodeEntry(int64_t node, int64_t insert_after, int vehicle, 630 bool all_vehicles, 631 AdjustablePriorityQueue<NodeEntry>* priority_queue, 632 std::vector<NodeEntries>* node_entries) const; 633 /// Updates the given node_entry's value and rearranges the priority queue 634 /// accordingly. 635 void UpdateNodeEntry( 636 NodeEntry* const node_entry, 637 AdjustablePriorityQueue<NodeEntry>* priority_queue) const; 638 639 /// Computes the neighborhood of all nodes for every cost class, if needed and 640 /// not done already. 641 void ComputeNeighborhoods(); 642 643 /// Returns true iff neighbor_index is in node_index's neighbors list 644 /// corresponding to neighbor_is_pickup and neighbor_is_delivery. 645 bool IsNeighborForCostClass(int cost_class, int64_t node_index, 646 int64_t neighbor_index) const; 647 648 /// Returns the neighbors of the given node for the given cost_class. GetNeighborsOfNodeForCostClass(int cost_class,int64_t node_index)649 const std::vector<int64_t>& GetNeighborsOfNodeForCostClass( 650 int cost_class, int64_t node_index) const { 651 return gci_params_.neighbors_ratio == 1 652 ? all_nodes_ 653 : node_index_to_neighbors_by_cost_class_[node_index][cost_class] 654 ->PositionsSetAtLeastOnce(); 655 } 656 NumNonStartEndNodes()657 int64_t NumNonStartEndNodes() const { 658 return model()->Size() - model()->vehicles(); 659 } 660 NumNeighbors()661 int64_t NumNeighbors() const { 662 return std::max(gci_params_.min_neighbors, 663 MathUtil::FastInt64Round(gci_params_.neighbors_ratio * 664 NumNonStartEndNodes())); 665 } 666 ResetVehicleIndices()667 void ResetVehicleIndices() override { 668 node_index_to_vehicle_.assign(node_index_to_vehicle_.size(), -1); 669 } 670 SetVehicleIndex(int64_t node,int vehicle)671 void SetVehicleIndex(int64_t node, int vehicle) override { 672 DCHECK_LT(node, node_index_to_vehicle_.size()); 673 node_index_to_vehicle_[node] = vehicle; 674 } 675 676 /// Function that verifies node_index_to_vehicle_ is correctly filled for all 677 /// nodes given the current routes. 678 bool CheckVehicleIndices() const; 679 680 /// Returns the bucket of a node. GetBucketOfNode(int node)681 int64_t GetBucketOfNode(int node) const { 682 return model()->VehicleVar(node)->Size(); 683 } 684 685 /// Returns the bucket of a pair of pickup and delivery alternates. GetBucketOfPair(const RoutingModel::IndexPair & index_pair)686 int64_t GetBucketOfPair(const RoutingModel::IndexPair& index_pair) const { 687 int64_t max_pickup_bucket = 0; 688 for (int64_t pickup : index_pair.first) { 689 max_pickup_bucket = std::max(max_pickup_bucket, GetBucketOfNode(pickup)); 690 } 691 int64_t max_delivery_bucket = 0; 692 for (int64_t delivery : index_pair.second) { 693 max_delivery_bucket = 694 std::max(max_delivery_bucket, GetBucketOfNode(delivery)); 695 } 696 return std::min(max_pickup_bucket, max_delivery_bucket); 697 } 698 699 /// Checks if the search should be stopped (time limit reached), and cleans up 700 /// the priority queue if it's the case. 701 template <class T> StopSearchAndCleanup(AdjustablePriorityQueue<T> * priority_queue)702 bool StopSearchAndCleanup(AdjustablePriorityQueue<T>* priority_queue) { 703 if (!StopSearch()) return false; 704 for (T* const entry : *priority_queue->Raw()) { 705 delete entry; 706 } 707 priority_queue->Clear(); 708 return true; 709 } 710 711 GlobalCheapestInsertionParameters gci_params_; 712 /// Stores the vehicle index of each node in the current assignment. 713 std::vector<int> node_index_to_vehicle_; 714 715 // clang-format off 716 std::vector<std::vector<std::unique_ptr<SparseBitset<int64_t> > > > 717 node_index_to_neighbors_by_cost_class_; 718 // clang-format on 719 720 std::unique_ptr<VehicleTypeCurator> empty_vehicle_type_curator_; 721 722 /// When neighbors_ratio is 1, we don't compute the neighborhood matrix 723 /// above, and use the following vector in the code to avoid unnecessary 724 /// computations and decrease the time and space complexities. 725 std::vector<int64_t> all_nodes_; 726 }; 727 728 /// Filter-base decision builder which builds a solution by inserting 729 /// nodes at their cheapest position. The cost of a position is computed 730 /// an arc-based cost callback. Node selected for insertion are considered in 731 /// decreasing order of distance to the start/ends of the routes, i.e. farthest 732 /// nodes are inserted first. 733 class LocalCheapestInsertionFilteredHeuristic 734 : public CheapestInsertionFilteredHeuristic { 735 public: 736 /// Takes ownership of evaluator. 737 LocalCheapestInsertionFilteredHeuristic( 738 RoutingModel* model, 739 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator, 740 LocalSearchFilterManager* filter_manager); ~LocalCheapestInsertionFilteredHeuristic()741 ~LocalCheapestInsertionFilteredHeuristic() override {} 742 bool BuildSolutionInternal() override; DebugString()743 std::string DebugString() const override { 744 return "LocalCheapestInsertionFilteredHeuristic"; 745 } 746 747 private: 748 /// Computes the possible insertion positions of 'node' and sorts them 749 /// according to the current cost evaluator. 750 /// 'node' is a variable index corresponding to a node, 'sorted_insertions' is 751 /// a sorted vector of insertions. 752 void ComputeEvaluatorSortedPositions( 753 int64_t node, std::vector<NodeInsertion>* sorted_insertions); 754 /// Like ComputeEvaluatorSortedPositions, subject to the additional 755 /// restrictions that the node may only be inserted after node 'start' on the 756 /// route. For convenience, this method also needs the node that is right 757 /// after 'start' on the route. 758 void ComputeEvaluatorSortedPositionsOnRouteAfter( 759 int64_t node, int64_t start, int64_t next_after_start, int vehicle, 760 std::vector<NodeInsertion>* sorted_insertions); 761 762 std::vector<std::vector<StartEndValue>> start_end_distances_per_node_; 763 }; 764 765 /// Filtered-base decision builder based on the addition heuristic, extending 766 /// a path from its start node with the cheapest arc. 767 class CheapestAdditionFilteredHeuristic : public RoutingFilteredHeuristic { 768 public: 769 CheapestAdditionFilteredHeuristic(RoutingModel* model, 770 LocalSearchFilterManager* filter_manager); ~CheapestAdditionFilteredHeuristic()771 ~CheapestAdditionFilteredHeuristic() override {} 772 bool BuildSolutionInternal() override; 773 774 private: 775 class PartialRoutesAndLargeVehicleIndicesFirst { 776 public: PartialRoutesAndLargeVehicleIndicesFirst(const CheapestAdditionFilteredHeuristic & builder)777 explicit PartialRoutesAndLargeVehicleIndicesFirst( 778 const CheapestAdditionFilteredHeuristic& builder) 779 : builder_(builder) {} 780 bool operator()(int vehicle1, int vehicle2) const; 781 782 private: 783 const CheapestAdditionFilteredHeuristic& builder_; 784 }; 785 /// Returns a vector of possible next indices of node from an iterator. 786 template <typename Iterator> GetPossibleNextsFromIterator(int64_t node,Iterator start,Iterator end)787 std::vector<int64_t> GetPossibleNextsFromIterator(int64_t node, 788 Iterator start, 789 Iterator end) const { 790 const int size = model()->Size(); 791 std::vector<int64_t> nexts; 792 for (Iterator it = start; it != end; ++it) { 793 const int64_t next = *it; 794 if (next != node && (next >= size || !Contains(next))) { 795 nexts.push_back(next); 796 } 797 } 798 return nexts; 799 } 800 /// Sorts a vector of successors of node. 801 virtual void SortSuccessors(int64_t node, 802 std::vector<int64_t>* successors) = 0; 803 virtual int64_t FindTopSuccessor(int64_t node, 804 const std::vector<int64_t>& successors) = 0; 805 }; 806 807 /// A CheapestAdditionFilteredHeuristic where the notion of 'cheapest arc' 808 /// comes from an arc evaluator. 809 class EvaluatorCheapestAdditionFilteredHeuristic 810 : public CheapestAdditionFilteredHeuristic { 811 public: 812 /// Takes ownership of evaluator. 813 EvaluatorCheapestAdditionFilteredHeuristic( 814 RoutingModel* model, std::function<int64_t(int64_t, int64_t)> evaluator, 815 LocalSearchFilterManager* filter_manager); ~EvaluatorCheapestAdditionFilteredHeuristic()816 ~EvaluatorCheapestAdditionFilteredHeuristic() override {} DebugString()817 std::string DebugString() const override { 818 return "EvaluatorCheapestAdditionFilteredHeuristic"; 819 } 820 821 private: 822 /// Next nodes are sorted according to the current evaluator. 823 void SortSuccessors(int64_t node, std::vector<int64_t>* successors) override; 824 int64_t FindTopSuccessor(int64_t node, 825 const std::vector<int64_t>& successors) override; 826 827 std::function<int64_t(int64_t, int64_t)> evaluator_; 828 }; 829 830 /// A CheapestAdditionFilteredHeuristic where the notion of 'cheapest arc' 831 /// comes from an arc comparator. 832 class ComparatorCheapestAdditionFilteredHeuristic 833 : public CheapestAdditionFilteredHeuristic { 834 public: 835 /// Takes ownership of evaluator. 836 ComparatorCheapestAdditionFilteredHeuristic( 837 RoutingModel* model, Solver::VariableValueComparator comparator, 838 LocalSearchFilterManager* filter_manager); ~ComparatorCheapestAdditionFilteredHeuristic()839 ~ComparatorCheapestAdditionFilteredHeuristic() override {} DebugString()840 std::string DebugString() const override { 841 return "ComparatorCheapestAdditionFilteredHeuristic"; 842 } 843 844 private: 845 /// Next nodes are sorted according to the current comparator. 846 void SortSuccessors(int64_t node, std::vector<int64_t>* successors) override; 847 int64_t FindTopSuccessor(int64_t node, 848 const std::vector<int64_t>& successors) override; 849 850 Solver::VariableValueComparator comparator_; 851 }; 852 853 /// Filter-based decision builder which builds a solution by using 854 /// Clarke & Wright's Savings heuristic. For each pair of nodes, the savings 855 /// value is the difference between the cost of two routes visiting one node 856 /// each and one route visiting both nodes. Routes are built sequentially, each 857 /// route being initialized from the pair with the best available savings value 858 /// then extended by selecting the nodes with best savings on both ends of the 859 /// partial route. Cost is based on the arc cost function of the routing model 860 /// and cost classes are taken into account. 861 class SavingsFilteredHeuristic : public RoutingFilteredHeuristic { 862 public: 863 struct SavingsParameters { 864 /// If neighbors_ratio < 1 then for each node only this ratio of its 865 /// neighbors leading to the smallest arc costs are considered. 866 double neighbors_ratio = 1.0; 867 /// The number of neighbors considered for each node is also adapted so that 868 /// the stored Savings don't use up more than max_memory_usage_bytes bytes. 869 double max_memory_usage_bytes = 6e9; 870 /// If add_reverse_arcs is true, the neighborhood relationships are 871 /// considered symmetrically. 872 bool add_reverse_arcs = false; 873 /// arc_coefficient is a strictly positive parameter indicating the 874 /// coefficient of the arc being considered in the Saving formula. 875 double arc_coefficient = 1.0; 876 }; 877 878 SavingsFilteredHeuristic(RoutingModel* model, SavingsParameters parameters, 879 LocalSearchFilterManager* filter_manager); 880 ~SavingsFilteredHeuristic() override; 881 bool BuildSolutionInternal() override; 882 883 protected: 884 typedef std::pair</*saving*/ int64_t, /*saving index*/ int64_t> Saving; 885 886 template <typename S> 887 class SavingsContainer; 888 889 virtual double ExtraSavingsMemoryMultiplicativeFactor() const = 0; 890 891 virtual void BuildRoutesFromSavings() = 0; 892 893 /// Returns the cost class from a saving. GetVehicleTypeFromSaving(const Saving & saving)894 int64_t GetVehicleTypeFromSaving(const Saving& saving) const { 895 return saving.second / size_squared_; 896 } 897 /// Returns the "before node" from a saving. GetBeforeNodeFromSaving(const Saving & saving)898 int64_t GetBeforeNodeFromSaving(const Saving& saving) const { 899 return (saving.second % size_squared_) / Size(); 900 } 901 /// Returns the "after node" from a saving. GetAfterNodeFromSaving(const Saving & saving)902 int64_t GetAfterNodeFromSaving(const Saving& saving) const { 903 return (saving.second % size_squared_) % Size(); 904 } 905 /// Returns the saving value from a saving. GetSavingValue(const Saving & saving)906 int64_t GetSavingValue(const Saving& saving) const { return saving.first; } 907 908 /// Finds the best available vehicle of type "type" to start a new route to 909 /// serve the arc before_node-->after_node. 910 /// Since there are different vehicle classes for each vehicle type, each 911 /// vehicle class having its own capacity constraints, we go through all 912 /// vehicle types (in each case only studying the first available vehicle) to 913 /// make sure this Saving is inserted if possible. 914 /// If possible, the arc is committed to the best vehicle, and the vehicle 915 /// index is returned. If this arc can't be served by any vehicle of this 916 /// type, the function returns -1. 917 int StartNewRouteWithBestVehicleOfType(int type, int64_t before_node, 918 int64_t after_node); 919 920 // clang-format off 921 std::unique_ptr<SavingsContainer<Saving> > savings_container_; 922 // clang-format on 923 std::unique_ptr<VehicleTypeCurator> vehicle_type_curator_; 924 925 private: 926 /// Used when add_reverse_arcs_ is true. 927 /// Given the vector of adjacency lists of a graph, adds symmetric arcs not 928 /// already in the graph to the adjacencies (i.e. if n1-->n2 is present and 929 /// not n2-->n1, then n1 is added to adjacency_matrix[n2]. 930 // clang-format off 931 void AddSymmetricArcsToAdjacencyLists( 932 std::vector<std::vector<int64_t> >* adjacency_lists); 933 // clang-format on 934 935 /// Computes saving values for node pairs (see MaxNumNeighborsPerNode()) and 936 /// all vehicle types (see ComputeVehicleTypes()). 937 /// The saving index attached to each saving value is an index used to 938 /// store and recover the node pair to which the value is linked (cf. the 939 /// index conversion methods below). 940 /// The computed savings are stored and sorted using the savings_container_. 941 /// Returns false if the computation could not be done within the model's 942 /// time limit. 943 bool ComputeSavings(); 944 /// Builds a saving from a saving value, a vehicle type and two nodes. BuildSaving(int64_t saving,int vehicle_type,int before_node,int after_node)945 Saving BuildSaving(int64_t saving, int vehicle_type, int before_node, 946 int after_node) const { 947 return std::make_pair(saving, vehicle_type * size_squared_ + 948 before_node * Size() + after_node); 949 } 950 951 /// Computes and returns the maximum number of (closest) neighbors to consider 952 /// for each node when computing Savings, based on the neighbors ratio and max 953 /// memory usage specified by the savings_params_. 954 int64_t MaxNumNeighborsPerNode(int num_vehicle_types) const; 955 956 const SavingsParameters savings_params_; 957 int64_t size_squared_; 958 959 friend class SavingsFilteredHeuristicTestPeer; 960 }; 961 962 class SequentialSavingsFilteredHeuristic : public SavingsFilteredHeuristic { 963 public: SequentialSavingsFilteredHeuristic(RoutingModel * model,SavingsParameters parameters,LocalSearchFilterManager * filter_manager)964 SequentialSavingsFilteredHeuristic(RoutingModel* model, 965 SavingsParameters parameters, 966 LocalSearchFilterManager* filter_manager) 967 : SavingsFilteredHeuristic(model, parameters, filter_manager) {} ~SequentialSavingsFilteredHeuristic()968 ~SequentialSavingsFilteredHeuristic() override{}; DebugString()969 std::string DebugString() const override { 970 return "SequentialSavingsFilteredHeuristic"; 971 } 972 973 private: 974 /// Builds routes sequentially. 975 /// Once a Saving is used to start a new route, we extend this route as much 976 /// as possible from both ends by gradually inserting the best Saving at 977 /// either end of the route. 978 void BuildRoutesFromSavings() override; ExtraSavingsMemoryMultiplicativeFactor()979 double ExtraSavingsMemoryMultiplicativeFactor() const override { return 1.0; } 980 }; 981 982 class ParallelSavingsFilteredHeuristic : public SavingsFilteredHeuristic { 983 public: ParallelSavingsFilteredHeuristic(RoutingModel * model,SavingsParameters parameters,LocalSearchFilterManager * filter_manager)984 ParallelSavingsFilteredHeuristic(RoutingModel* model, 985 SavingsParameters parameters, 986 LocalSearchFilterManager* filter_manager) 987 : SavingsFilteredHeuristic(model, parameters, filter_manager) {} ~ParallelSavingsFilteredHeuristic()988 ~ParallelSavingsFilteredHeuristic() override{}; DebugString()989 std::string DebugString() const override { 990 return "ParallelSavingsFilteredHeuristic"; 991 } 992 993 private: 994 /// Goes through the ordered computed Savings to build routes in parallel. 995 /// Given a Saving for a before-->after arc : 996 /// -- If both before and after are uncontained, we start a new route. 997 /// -- If only before is served and is the last node on its route, we try 998 /// adding after at the end of the route. 999 /// -- If only after is served and is first on its route, we try adding before 1000 /// as first node on this route. 1001 /// -- If both nodes are contained and are respectively the last and first 1002 /// nodes on their (different) routes, we merge the routes of the two nodes 1003 /// into one if possible. 1004 void BuildRoutesFromSavings() override; 1005 ExtraSavingsMemoryMultiplicativeFactor()1006 double ExtraSavingsMemoryMultiplicativeFactor() const override { return 2.0; } 1007 1008 /// Merges the routes of first_vehicle and second_vehicle onto the vehicle 1009 /// with lower fixed cost. The routes respectively end at before_node and 1010 /// start at after_node, and are merged into one by adding the arc 1011 /// before_node-->after_node. 1012 void MergeRoutes(int first_vehicle, int second_vehicle, int64_t before_node, 1013 int64_t after_node); 1014 1015 /// First and last non start/end nodes served by each vehicle. 1016 std::vector<int64_t> first_node_on_route_; 1017 std::vector<int64_t> last_node_on_route_; 1018 /// For each first/last node served by a vehicle (besides start/end nodes of 1019 /// vehicle), this vector contains the index of the vehicle serving them. 1020 /// For other (intermediary) nodes, contains -1. 1021 std::vector<int> vehicle_of_first_or_last_node_; 1022 }; 1023 1024 /// Christofides addition heuristic. Initially created to solve TSPs, extended 1025 /// to support any model by extending routes as much as possible following the 1026 /// path found by the heuristic, before starting a new route. 1027 1028 class ChristofidesFilteredHeuristic : public RoutingFilteredHeuristic { 1029 public: 1030 ChristofidesFilteredHeuristic(RoutingModel* model, 1031 LocalSearchFilterManager* filter_manager, 1032 bool use_minimum_matching); ~ChristofidesFilteredHeuristic()1033 ~ChristofidesFilteredHeuristic() override {} 1034 bool BuildSolutionInternal() override; DebugString()1035 std::string DebugString() const override { 1036 return "ChristofidesFilteredHeuristic"; 1037 } 1038 1039 private: 1040 const bool use_minimum_matching_; 1041 }; 1042 1043 /// Class to arrange indices by by their distance and their angles from the 1044 /// depot. Used in the Sweep first solution heuristic. 1045 class SweepArranger { 1046 public: 1047 explicit SweepArranger( 1048 const std::vector<std::pair<int64_t, int64_t>>& points); ~SweepArranger()1049 virtual ~SweepArranger() {} 1050 void ArrangeIndices(std::vector<int64_t>* indices); SetSectors(int sectors)1051 void SetSectors(int sectors) { sectors_ = sectors; } 1052 1053 private: 1054 std::vector<int> coordinates_; 1055 int sectors_; 1056 1057 DISALLOW_COPY_AND_ASSIGN(SweepArranger); 1058 }; 1059 #endif // SWIG 1060 1061 // Returns a DecisionBuilder building a first solution based on the Sweep 1062 // heuristic. Mostly suitable when cost is proportional to distance. 1063 DecisionBuilder* MakeSweepDecisionBuilder(RoutingModel* model, 1064 bool check_assignment); 1065 1066 // Returns a DecisionBuilder making all nodes unperformed. 1067 DecisionBuilder* MakeAllUnperformed(RoutingModel* model); 1068 1069 } // namespace operations_research 1070 1071 #endif // OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_ 1072