38#include "absl/algorithm/container.h"
39#include "absl/container/flat_hash_map.h"
40#include "absl/container/flat_hash_set.h"
41#include "absl/flags/flag.h"
42#include "absl/functional/any_invocable.h"
43#include "absl/functional/bind_front.h"
44#include "absl/hash/hash.h"
45#include "absl/log/check.h"
46#include "absl/log/die_if_null.h"
47#include "absl/memory/memory.h"
48#include "absl/status/statusor.h"
49#include "absl/strings/str_cat.h"
50#include "absl/strings/str_format.h"
51#include "absl/strings/string_view.h"
52#include "absl/time/time.h"
53#include "absl/types/span.h"
54#include "google/protobuf/util/message_differencer.h"
93using GraphNodeIndex = int32_t;
94using GraphArcIndex = int32_t;
104 std::string line_prefix)
const {
105 std::string s = absl::StrFormat(
"%stravel_cost_coefficient: %ld", line_prefix,
108 absl::StrAppendFormat(&s,
"\ntransition[%d] {\n%s\n}\n", i,
115 std::string line_prefix)
const {
116 return absl::StrFormat(
126 post_travel_transit_value, line_prefix,
127 compressed_travel_value_lower_bound, line_prefix,
128 travel_value_upper_bound, line_prefix,
129 travel_start_dependent_travel.DebugString(line_prefix + "\t"),
130 line_prefix, travel_compression_cost.DebugString(line_prefix +
"\t"));
134 const Assignment* original_assignment, absl::Duration duration_limit,
135 bool* time_limit_was_reached) {
137 if (original_assignment ==
nullptr)
return nullptr;
138 if (duration_limit <= absl::ZeroDuration()) {
139 if (time_limit_was_reached) *time_limit_was_reached =
true;
140 return original_assignment;
142 if (global_dimension_optimizers_.empty() &&
143 local_dimension_optimizers_.empty()) {
144 return original_assignment;
146 RegularLimit*
const limit = GetOrCreateLimit();
147 limit->UpdateLimits(duration_limit, std::numeric_limits<int64_t>::max(),
148 std::numeric_limits<int64_t>::max(),
149 std::numeric_limits<int64_t>::max());
151 RegularLimit*
const cumulative_limit = GetOrCreateCumulativeLimit();
152 cumulative_limit->UpdateLimits(
153 duration_limit, std::numeric_limits<int64_t>::max(),
154 std::numeric_limits<int64_t>::max(), std::numeric_limits<int64_t>::max());
158 Assignment* packed_assignment = solver_->MakeAssignment();
159 packed_assignment->Add(
Nexts());
164 packed_assignment->Add(resource_vars_[rg_index]);
167 packed_assignment->CopyIntersection(original_assignment);
169 std::vector<DecisionBuilder*> decision_builders;
170 decision_builders.push_back(solver_->MakeRestoreAssignment(preassignment_));
171 decision_builders.push_back(
172 solver_->MakeRestoreAssignment(packed_assignment));
173 for (
auto& [lp_optimizer, mp_optimizer] : local_dimension_optimizers_) {
179 solver_.get(), lp_optimizer.get(), mp_optimizer.get(),
182 for (
auto& [lp_optimizer, mp_optimizer] : global_dimension_optimizers_) {
184 solver_.get(), lp_optimizer.get(), mp_optimizer.get(),
187 decision_builders.push_back(finalizer_variables_->CreateFinalizer());
189 DecisionBuilder* restore_pack_and_finalize =
190 solver_->Compose(decision_builders);
191 solver_->Solve(restore_pack_and_finalize,
192 optimized_dimensions_assignment_collector_, limit);
193 const bool limit_was_reached = limit->Check();
194 if (time_limit_was_reached) *time_limit_was_reached = limit_was_reached;
195 if (optimized_dimensions_assignment_collector_->solution_count() != 1) {
196 if (limit_was_reached) {
197 VLOG(1) <<
"The packing reached the time limit.";
201 LOG(ERROR) <<
"The given assignment is not valid for this model, or"
202 " cannot be packed.";
207 packed_assignment->Copy(original_assignment);
208 packed_assignment->CopyIntersection(
209 optimized_dimensions_assignment_collector_->solution(0));
211 return packed_assignment;
219 return sweep_arranger_.get();
223 const NodeNeighborsParameters& params) {
224 auto [num_neighbors, add_vehicle_starts_to_neighbors,
225 add_vehicle_ends_to_neighbors,
226 only_sort_neighbors_for_partial_neighborhoods] = params;
227 DCHECK_GE(num_neighbors, 0);
229 const int size = routing_model_.Size();
230 const int num_non_start_end_nodes = size - routing_model_.vehicles();
231 const int size_with_vehicle_nodes = size + routing_model_.vehicles();
233 const int max_num_neighbors = std::max(num_non_start_end_nodes - 1, 0);
234 num_neighbors = std::min<int>(max_num_neighbors, num_neighbors);
235 node_index_to_incoming_neighbors_by_cost_class_.clear();
236 node_index_to_outgoing_neighbors_by_cost_class_.clear();
237 node_index_to_outgoing_neighbor_indicator_by_cost_class_.clear();
238 all_incoming_nodes_.clear();
239 all_outgoing_nodes_.clear();
240 full_neighborhood_ = num_neighbors == max_num_neighbors;
241 if (full_neighborhood_ && only_sort_neighbors_for_partial_neighborhoods) {
242 all_incoming_nodes_.reserve(size);
243 all_outgoing_nodes_.reserve(size);
244 for (
int node = 0; node < size_with_vehicle_nodes; node++) {
245 const bool not_start = !routing_model_.IsStart(node);
246 const bool not_end = !routing_model_.IsEnd(node);
247 if (not_start && (not_end || add_vehicle_ends_to_neighbors)) {
248 all_outgoing_nodes_.push_back(node);
250 if (not_end && (not_start || add_vehicle_starts_to_neighbors)) {
251 all_incoming_nodes_.push_back(node);
257 const int num_cost_classes = routing_model_.GetCostClassesCount();
258 node_index_to_incoming_neighbors_by_cost_class_.resize(num_cost_classes);
259 node_index_to_outgoing_neighbors_by_cost_class_.resize(num_cost_classes);
260 node_index_to_outgoing_neighbor_indicator_by_cost_class_.resize(
262 std::vector<std::vector<std::vector<int64_t>>>
263 node_index_to_outgoing_costs_by_cost_class(num_cost_classes);
264 for (
int cc = 0; cc < num_cost_classes; cc++) {
265 if (!routing_model_.HasVehicleWithCostClassIndex(
266 RoutingCostClassIndex(cc))) {
269 node_index_to_incoming_neighbors_by_cost_class_[cc].resize(
270 size_with_vehicle_nodes);
271 node_index_to_outgoing_neighbors_by_cost_class_[cc].resize(size);
272 node_index_to_outgoing_neighbor_indicator_by_cost_class_[cc].resize(size);
273 node_index_to_outgoing_costs_by_cost_class[cc].resize(size);
274 for (
int node = 0; node < size_with_vehicle_nodes; node++) {
275 node_index_to_incoming_neighbors_by_cost_class_[cc][node].reserve(
276 num_neighbors + routing_model_.vehicles());
278 node_index_to_outgoing_neighbors_by_cost_class_[cc][node].reserve(
279 num_neighbors + routing_model_.vehicles());
280 node_index_to_outgoing_neighbor_indicator_by_cost_class_[cc][node]
281 .resize(size_with_vehicle_nodes,
false);
282 node_index_to_outgoing_costs_by_cost_class[cc][node].resize(
283 size_with_vehicle_nodes, -1);
288 std::vector<int> outgoing_neighbors;
289 for (
int cost_class = 0; cost_class < num_cost_classes; cost_class++) {
290 if (!routing_model_.HasVehicleWithCostClassIndex(
291 RoutingCostClassIndex(cost_class))) {
295 std::vector<std::vector<int>>& node_index_to_incoming_neighbors =
296 node_index_to_incoming_neighbors_by_cost_class_[cost_class];
297 std::vector<std::vector<int>>& node_index_to_outgoing_neighbors =
298 node_index_to_outgoing_neighbors_by_cost_class_[cost_class];
299 std::vector<std::vector<bool>>& node_index_to_outgoing_neighbor_indicator =
300 node_index_to_outgoing_neighbor_indicator_by_cost_class_[cost_class];
301 std::vector<std::vector<int64_t>>& node_index_to_outgoing_costs =
302 node_index_to_outgoing_costs_by_cost_class[cost_class];
303 for (
int node_index = 0; node_index < size; ++node_index) {
304 if (routing_model_.IsStart(node_index)) {
310 outgoing_neighbors.clear();
311 outgoing_neighbors.reserve(num_non_start_end_nodes);
312 if (num_neighbors > 0) {
313 std::vector<int64_t>& costs = node_index_to_outgoing_costs[node_index];
314 for (
int after_node = 0; after_node < size; ++after_node) {
315 if (after_node != node_index && !routing_model_.IsStart(after_node)) {
316 costs[after_node] = routing_model_.GetArcCostForClass(
317 node_index, after_node, cost_class);
318 outgoing_neighbors.push_back(after_node);
322 DCHECK_GE(outgoing_neighbors.size(), num_neighbors);
323 std::nth_element(outgoing_neighbors.begin(),
324 outgoing_neighbors.begin() + num_neighbors - 1,
325 outgoing_neighbors.end(), [&costs](
int n1,
int n2) {
326 return std::tie(costs[n1], n1) <
327 std::tie(costs[n2], n2);
329 outgoing_neighbors.resize(num_neighbors);
333 for (
int outgoing_neighbor : outgoing_neighbors) {
334 DCHECK(!routing_model_.IsEnd(outgoing_neighbor) &&
335 !routing_model_.IsStart(outgoing_neighbor));
336 DCHECK(!node_index_to_outgoing_neighbor_indicator[node_index]
337 [outgoing_neighbor]);
338 node_index_to_outgoing_neighbor_indicator[node_index]
339 [outgoing_neighbor] =
true;
340 node_index_to_outgoing_neighbors[node_index].push_back(
343 node_index_to_incoming_neighbors[outgoing_neighbor].push_back(
350 for (
int cost_class = 0; cost_class < num_cost_classes; cost_class++) {
351 if (!routing_model_.HasVehicleWithCostClassIndex(
352 RoutingCostClassIndex(cost_class))) {
356 std::vector<std::vector<int>>& node_index_to_incoming_neighbors =
357 node_index_to_incoming_neighbors_by_cost_class_[cost_class];
358 std::vector<std::vector<int>>& node_index_to_outgoing_neighbors =
359 node_index_to_outgoing_neighbors_by_cost_class_[cost_class];
360 std::vector<std::vector<bool>>& node_index_to_outgoing_neighbor_indicator =
361 node_index_to_outgoing_neighbor_indicator_by_cost_class_[cost_class];
362 std::vector<std::vector<int64_t>>& node_index_to_outgoing_costs =
363 node_index_to_outgoing_costs_by_cost_class[cost_class];
364 for (
int vehicle = 0; vehicle < routing_model_.vehicles(); vehicle++) {
365 const int vehicle_start = routing_model_.Start(vehicle);
366 const int vehicle_end = routing_model_.End(vehicle);
369 DCHECK(!node_index_to_outgoing_neighbor_indicator[vehicle_start]
371 node_index_to_outgoing_neighbor_indicator[vehicle_start][vehicle_end] =
373 if (add_vehicle_starts_to_neighbors) {
374 node_index_to_incoming_neighbors[vehicle_end].push_back(vehicle_start);
376 if (add_vehicle_ends_to_neighbors) {
377 node_index_to_outgoing_neighbors[vehicle_start].push_back(vehicle_end);
379 node_index_to_outgoing_costs[vehicle_start][vehicle_end] =
380 routing_model_.GetArcCostForClass(vehicle_start, vehicle_end,
383 for (
int node_index = 0; node_index < size; ++node_index) {
384 if (routing_model_.IsStart(node_index))
continue;
387 DCHECK(!node_index_to_outgoing_neighbor_indicator[node_index]
389 DCHECK(!node_index_to_outgoing_neighbor_indicator[vehicle_start]
391 node_index_to_outgoing_neighbor_indicator[vehicle_start][node_index] =
393 if (add_vehicle_starts_to_neighbors) {
394 node_index_to_incoming_neighbors[node_index].push_back(vehicle_start);
396 node_index_to_outgoing_neighbors[vehicle_start].push_back(node_index);
397 node_index_to_outgoing_costs[vehicle_start][node_index] =
398 routing_model_.GetArcCostForClass(vehicle_start, node_index,
402 DCHECK(!node_index_to_outgoing_neighbor_indicator[node_index]
404 node_index_to_outgoing_neighbor_indicator[node_index][vehicle_end] =
406 node_index_to_incoming_neighbors[vehicle_end].push_back(node_index);
407 if (add_vehicle_ends_to_neighbors) {
408 node_index_to_outgoing_neighbors[node_index].push_back(vehicle_end);
410 node_index_to_outgoing_costs[node_index][vehicle_end] =
411 routing_model_.GetArcCostForClass(node_index, vehicle_end,
419 for (
int cost_class = 0; cost_class < num_cost_classes; cost_class++) {
420 if (!routing_model_.HasVehicleWithCostClassIndex(
421 RoutingCostClassIndex(cost_class))) {
425 const std::vector<std::vector<int64_t>>& node_index_to_outgoing_costs =
426 node_index_to_outgoing_costs_by_cost_class[cost_class];
427 for (
int node_index = 0; node_index < size_with_vehicle_nodes;
429 std::vector<int>& incoming_node_neighbors =
430 node_index_to_incoming_neighbors_by_cost_class_[cost_class]
433 incoming_node_neighbors,
434 [node_index, size, &node_index_to_outgoing_costs](
int n1,
int n2) {
435 DCHECK_GE(node_index_to_outgoing_costs[n1][node_index], 0);
436 DCHECK_GE(node_index_to_outgoing_costs[n2][node_index], 0);
439 return std::tie(node_index_to_outgoing_costs[n1][node_index], n1) <
440 std::tie(node_index_to_outgoing_costs[n2][node_index], n2);
443 DCHECK(absl::c_adjacent_find(incoming_node_neighbors) ==
444 incoming_node_neighbors.end());
446 if (node_index < size) {
447 std::vector<int>& outgoing_node_neighbors =
448 node_index_to_outgoing_neighbors_by_cost_class_[cost_class]
450 const std::vector<int64_t>& outgoing_costs =
451 node_index_to_outgoing_costs[node_index];
452 absl::c_sort(outgoing_node_neighbors,
453 [&outgoing_costs](
int n1,
int n2) {
454 DCHECK_GE(outgoing_costs[n1], 0);
455 DCHECK_GE(outgoing_costs[n2], 0);
456 return std::tie(outgoing_costs[n1], n1) <
457 std::tie(outgoing_costs[n2], n2);
461 DCHECK(absl::c_adjacent_find(outgoing_node_neighbors) ==
462 outgoing_node_neighbors.end());
468const RoutingModel::NodeNeighborsByCostClass*
470 double neighbors_ratio, int64_t min_neighbors,
double& neighbors_ratio_used,
471 bool add_vehicle_starts_to_neighbors,
bool add_vehicle_ends_to_neighbors,
472 bool only_sort_neighbors_for_partial_neighborhoods) {
473 const int64_t num_non_start_end_nodes =
Size() -
vehicles();
474 neighbors_ratio_used = neighbors_ratio;
475 int num_neighbors = std::max(
478 if (neighbors_ratio == 1 || num_neighbors >= num_non_start_end_nodes - 1) {
479 neighbors_ratio_used = 1;
480 num_neighbors =
Size();
483 {num_neighbors, add_vehicle_starts_to_neighbors,
484 add_vehicle_ends_to_neighbors,
485 only_sort_neighbors_for_partial_neighborhoods});
488const RoutingModel::NodeNeighborsByCostClass*
490 const NodeNeighborsParameters& params) {
491 std::unique_ptr<NodeNeighborsByCostClass>& node_neighbors_by_cost_class =
492 node_neighbors_by_cost_class_per_size_[params];
493 if (node_neighbors_by_cost_class !=
nullptr) {
494 return node_neighbors_by_cost_class.get();
496 node_neighbors_by_cost_class =
497 std::make_unique<NodeNeighborsByCostClass>(
this);
498 node_neighbors_by_cost_class->ComputeNeighbors(params);
499 return node_neighbors_by_cost_class.get();
505template <
class A,
class B>
506static int64_t ReturnZero(A, B) {
525std::unique_ptr<Solver> CreateSolverFromParameters(
527 VLOG(1) <<
"Model parameters:\n" << parameters;
531 return std::make_unique<Solver>(
"Routing", solver_parameters);
536 const RoutingModelParameters& parameters)
537 : solver_(CreateSolverFromParameters(parameters)),
538 nodes_(index_manager.num_nodes()),
539 vehicles_(index_manager.num_vehicles()),
540 max_active_vehicles_(vehicles_),
541 fixed_cost_of_vehicle_(vehicles_, 0),
542 cost_class_index_of_vehicle_(vehicles_, CostClassIndex(-1)),
543 linear_cost_factor_of_vehicle_(vehicles_, 0),
544 quadratic_cost_factor_of_vehicle_(vehicles_, 0),
545 vehicle_amortized_cost_factors_set_(false),
546 vehicle_used_when_empty_(vehicles_, false),
548 costs_are_homogeneous_across_vehicles_(
549 parameters.reduce_vehicle_cost_model()),
550 cache_callbacks_(false),
551 vehicle_class_index_of_vehicle_(vehicles_, VehicleClassIndex(-1)),
552 vehicle_pickup_delivery_policy_(vehicles_, PICKUP_AND_DELIVERY_NO_ORDER),
554 paths_metadata_(index_manager),
555 manager_(index_manager),
557 finalizer_variables_(
std::make_unique<FinalizerVariables>(solver_.get())),
558 interrupt_cp_sat_(false),
559 interrupt_cp_(false) {
561 vehicle_to_transit_cost_.assign(
563 ReturnZero<int64_t, int64_t>,
567 cache_callbacks_ = (nodes_ <= parameters.max_callback_cache_size());
570 start_end_count_ = index_manager.num_unique_depots();
573 const int64_t size =
Size();
574 index_to_pickup_position_.resize(size);
575 index_to_delivery_position_.resize(size);
576 index_to_visit_type_.resize(index_manager.num_indices(),
kUnassigned);
577 index_to_type_policy_.resize(index_manager.num_indices());
579 const std::vector<RoutingIndexManager::NodeIndex>& index_to_node =
580 index_manager.GetIndexToNodeMap();
581 index_to_equivalence_class_.resize(index_manager.num_indices());
582 for (
int i = 0; i < index_to_node.size(); ++i) {
583 index_to_equivalence_class_[i] = index_to_node[i].value();
585 allowed_vehicles_.resize(
Size() + vehicles_);
588void RoutingModel::Initialize() {
589 const int size =
Size();
591 solver_->MakeIntVarArray(size, 0, size + vehicles_ - 1,
"Nexts", &nexts_);
592 solver_->AddConstraint(solver_->MakeAllDifferent(nexts_,
false));
593 index_to_disjunctions_.resize(size + vehicles_);
596 solver_->MakeIntVarArray(size + vehicles_, -1, vehicles_ - 1,
"Vehicles",
599 solver_->MakeBoolVarArray(size,
"Active", &active_);
601 solver_->MakeBoolVarArray(vehicles_,
"ActiveVehicle", &vehicle_active_);
603 solver_->MakeBoolVarArray(vehicles_,
"VehicleCostsConsidered",
604 &vehicle_route_considered_);
606 solver_->MakeBoolVarArray(size + vehicles_,
"IsBoundToEnd",
611 preassignment_ = solver_->MakeAssignment();
618 absl::flat_hash_set<RangeIntToIntFunction*> value_functions_delete;
619 absl::flat_hash_set<RangeMinMaxIndexFunction*> index_functions_delete;
620 for (
const auto& cache_line : state_dependent_transit_evaluators_cache_) {
621 for (
const auto& key_transit : *cache_line) {
622 value_functions_delete.insert(key_transit.second.transit);
623 index_functions_delete.insert(key_transit.second.transit_plus_identity);
632 if (std::all_of(std::cbegin(values), std::cend(values),
633 [](int64_t transit) {
return transit >= 0; })) {
635 }
else if (std::all_of(std::cbegin(values), std::cend(values),
636 [](int64_t transit) {
return transit <= 0; })) {
640 [
this, values = std::move(values)](int64_t i) {
641 return values[manager_.IndexToNode(i).value()];
647 TransitEvaluatorSign sign) {
648 const int index = unary_transit_evaluators_.size();
649 unary_transit_evaluators_.push_back(std::move(callback));
651 [
this, index](
int i,
int ) {
652 return unary_transit_evaluators_[index](i);
658 std::vector<std::vector<int64_t> > values) {
661 bool all_transits_geq_zero =
true;
662 bool all_transits_leq_zero =
true;
663 for (
const std::vector<int64_t>& transit_values : values) {
664 for (
const int64_t value : transit_values) {
665 all_transits_leq_zero &= value <= 0;
666 all_transits_geq_zero &= value >= 0;
668 if (!all_transits_geq_zero && !all_transits_leq_zero)
break;
671 all_transits_geq_zero
676 [
this, values = std::move(values)](int64_t i, int64_t j) {
677 return values[manager_.IndexToNode(i).value()]
678 [manager_.IndexToNode(j).value()];
684 TransitEvaluatorSign sign) {
685 if (cache_callbacks_) {
688 std::vector<int64_t> cache(size * size, 0);
689 bool all_transits_geq_zero =
true;
690 bool all_transits_leq_zero =
true;
691 for (
int i = 0; i < size; ++i) {
692 for (
int j = 0; j < size; ++j) {
693 const int64_t value = callback(i, j);
694 cache[i * size + j] = value;
695 all_transits_geq_zero &= value >= 0;
696 all_transits_leq_zero &= value <= 0;
700 all_transits_geq_zero
704 transit_evaluators_.push_back(
705 [cache = std::move(cache), size](int64_t i, int64_t j) {
706 return cache[
i * size + j];
710 transit_evaluators_.push_back(std::move(callback));
712 if (transit_evaluators_.size() != unary_transit_evaluators_.size()) {
713 DCHECK_EQ(transit_evaluators_.size(), unary_transit_evaluators_.size() + 1);
714 unary_transit_evaluators_.push_back(
nullptr);
716 transit_evaluator_sign_.push_back(sign);
717 return transit_evaluators_.size() - 1;
721 VariableIndexEvaluator2 callback) {
722 state_dependent_transit_evaluators_cache_.push_back(
723 std::make_unique<StateDependentTransitCallbackCache>());
724 StateDependentTransitCallbackCache*
const cache =
725 state_dependent_transit_evaluators_cache_.back().get();
726 state_dependent_transit_evaluators_.push_back(
727 [cache, callback = std::move(callback)](int64_t i, int64_t j) {
728 StateDependentTransit value;
729 if (
gtl::FindCopy(*cache, CacheKey(i, j), &value))
return value;
730 value = callback(i, j);
731 cache->insert({CacheKey(i, j), value});
734 return state_dependent_transit_evaluators_.size() - 1;
738 CumulDependentTransitCallback2 callback) {
739 cumul_dependent_transit_evaluators_.push_back(std::move(callback));
740 return cumul_dependent_transit_evaluators_.size() - 1;
743void RoutingModel::AddNoCycleConstraintInternal() {
744 if (no_cycle_constraint_ ==
nullptr) {
745 no_cycle_constraint_ = solver_->MakeNoCycle(nexts_, active_);
746 solver_->AddConstraint(no_cycle_constraint_);
751 int64_t capacity,
bool fix_start_cumul_to_zero,
752 const std::string& name) {
753 const std::vector<int> evaluator_indices(vehicles_, evaluator_index);
754 std::vector<int64_t> capacities(vehicles_, capacity);
755 return AddDimensionWithCapacityInternal(evaluator_indices, {}, slack_max,
756 std::move(capacities),
757 fix_start_cumul_to_zero, name);
761 const std::vector<int>& evaluator_indices, int64_t slack_max,
762 int64_t capacity,
bool fix_start_cumul_to_zero,
const std::string& name) {
763 std::vector<int64_t> capacities(vehicles_, capacity);
764 return AddDimensionWithCapacityInternal(evaluator_indices, {}, slack_max,
765 std::move(capacities),
766 fix_start_cumul_to_zero, name);
770 int evaluator_index, int64_t slack_max,
771 std::vector<int64_t> vehicle_capacities,
bool fix_start_cumul_to_zero,
772 const std::string& name) {
773 const std::vector<int> evaluator_indices(vehicles_, evaluator_index);
774 return AddDimensionWithCapacityInternal(evaluator_indices, {}, slack_max,
775 std::move(vehicle_capacities),
776 fix_start_cumul_to_zero, name);
780 const std::vector<int>& evaluator_indices, int64_t slack_max,
781 std::vector<int64_t> vehicle_capacities,
bool fix_start_cumul_to_zero,
782 const std::string& name) {
783 return AddDimensionWithCapacityInternal(evaluator_indices, {}, slack_max,
784 std::move(vehicle_capacities),
785 fix_start_cumul_to_zero, name);
789 const std::vector<int>& fixed_evaluator_indices,
790 const std::vector<int>& cumul_dependent_evaluator_indices,
791 int64_t slack_max, std::vector<int64_t> vehicle_capacities,
792 bool fix_start_cumul_to_zero,
const std::string& name) {
793 return AddDimensionWithCapacityInternal(
794 fixed_evaluator_indices, cumul_dependent_evaluator_indices, slack_max,
795 std::move(vehicle_capacities), fix_start_cumul_to_zero, name);
798bool RoutingModel::AddDimensionWithCapacityInternal(
799 const std::vector<int>& evaluator_indices,
800 const std::vector<int>& cumul_dependent_evaluator_indices,
801 int64_t slack_max, std::vector<int64_t> vehicle_capacities,
802 bool fix_start_cumul_to_zero,
const std::string& name) {
803 CHECK_EQ(vehicles_, vehicle_capacities.size());
804 return InitializeDimensionInternal(
805 evaluator_indices, cumul_dependent_evaluator_indices,
807 fix_start_cumul_to_zero,
811bool RoutingModel::InitializeDimensionInternal(
812 const std::vector<int>& evaluator_indices,
813 const std::vector<int>& cumul_dependent_evaluator_indices,
814 const std::vector<int>& state_dependent_evaluator_indices,
815 int64_t slack_max,
bool fix_start_cumul_to_zero,
817 DCHECK(dimension !=
nullptr);
818 DCHECK_EQ(vehicles_, evaluator_indices.size());
819 DCHECK((dimension->base_dimension_ ==
nullptr &&
820 state_dependent_evaluator_indices.empty()) ||
821 vehicles_ == state_dependent_evaluator_indices.size());
823 DCHECK_EQ(dimensions_.size(), dimension->index().value());
824 dimension_name_to_index_[dimension->name()] = dimension->index();
825 dimensions_.push_back(dimension);
826 dimension->Initialize(evaluator_indices, cumul_dependent_evaluator_indices,
827 state_dependent_evaluator_indices, slack_max);
828 solver_->AddConstraint(solver_->MakeDelayedPathCumul(
829 nexts_, active_, dimension->cumuls(), dimension->transits()));
830 if (fix_start_cumul_to_zero) {
831 for (
int i = 0;
i < vehicles_; ++
i) {
832 IntVar*
const start_cumul = dimension->CumulVar(
Start(i));
833 CHECK_EQ(0, start_cumul->Min());
834 start_cumul->SetValue(0);
844 int64_t value, int64_t capacity, int64_t slack_max,
845 bool fix_start_cumul_to_zero,
const std::string& dimension_name) {
849 const int evaluator_index =
851 return std::make_pair(evaluator_index,
853 fix_start_cumul_to_zero, dimension_name));
857 std::vector<int64_t> values, int64_t capacity,
bool fix_start_cumul_to_zero,
858 const std::string& dimension_name) {
860 return std::make_pair(evaluator_index,
862 fix_start_cumul_to_zero, dimension_name));
866 std::vector<std::vector<int64_t>> values, int64_t capacity,
867 bool fix_start_cumul_to_zero,
const std::string& dimension_name) {
869 return std::make_pair(evaluator_index,
871 fix_start_cumul_to_zero, dimension_name));
878class RangeMakeElementExpr :
public BaseIntExpr {
880 RangeMakeElementExpr(
const RangeIntToIntFunction* callback, IntVar* index,
882 : BaseIntExpr(s), callback_(ABSL_DIE_IF_NULL(callback)), index_(index) {
883 CHECK(callback_ !=
nullptr);
884 CHECK(index !=
nullptr);
887 int64_t Min()
const override {
889 const int idx_min = index_->Min();
890 const int idx_max = index_->Max() + 1;
891 return (idx_min < idx_max) ? callback_->RangeMin(idx_min, idx_max)
892 : std::numeric_limits<int64_t>::max();
894 void SetMin(int64_t new_min)
override {
895 const int64_t old_min = Min();
896 const int64_t old_max = Max();
897 if (old_min < new_min && new_min <= old_max) {
898 const int64_t old_idx_min = index_->Min();
899 const int64_t old_idx_max = index_->Max() + 1;
900 if (old_idx_min < old_idx_max) {
901 const int64_t new_idx_min = callback_->RangeFirstInsideInterval(
902 old_idx_min, old_idx_max, new_min, old_max + 1);
903 index_->SetMin(new_idx_min);
904 if (new_idx_min < old_idx_max) {
905 const int64_t new_idx_max = callback_->RangeLastInsideInterval(
906 new_idx_min, old_idx_max, new_min, old_max + 1);
907 index_->SetMax(new_idx_max);
912 int64_t Max()
const override {
914 const int idx_min = index_->Min();
915 const int idx_max = index_->Max() + 1;
916 return (idx_min < idx_max) ? callback_->RangeMax(idx_min, idx_max)
917 : std::numeric_limits<int64_t>::min();
919 void SetMax(int64_t new_max)
override {
920 const int64_t old_min = Min();
921 const int64_t old_max = Max();
922 if (old_min <= new_max && new_max < old_max) {
923 const int64_t old_idx_min = index_->Min();
924 const int64_t old_idx_max = index_->Max() + 1;
925 if (old_idx_min < old_idx_max) {
926 const int64_t new_idx_min = callback_->RangeFirstInsideInterval(
927 old_idx_min, old_idx_max, old_min, new_max + 1);
928 index_->SetMin(new_idx_min);
929 if (new_idx_min < old_idx_max) {
930 const int64_t new_idx_max = callback_->RangeLastInsideInterval(
931 new_idx_min, old_idx_max, old_min, new_max + 1);
932 index_->SetMax(new_idx_max);
937 void WhenRange(Demon* d)
override { index_->WhenRange(d); }
940 const RangeIntToIntFunction*
const callback_;
941 IntVar*
const index_;
947 s->
RevAlloc(
new RangeMakeElementExpr(callback, index, s)));
952 const std::vector<int>& dependent_transits,
953 const RoutingDimension* base_dimension, int64_t slack_max,
954 std::vector<int64_t> vehicle_capacities,
bool fix_start_cumul_to_zero,
955 const std::string& name) {
956 const std::vector<int> pure_transits(vehicles_, 0);
958 pure_transits, dependent_transits, base_dimension, slack_max,
959 std::move(vehicle_capacities), fix_start_cumul_to_zero, name);
964 int64_t vehicle_capacity,
bool fix_start_cumul_to_zero,
965 const std::string& name) {
967 0, transit, dimension, slack_max, vehicle_capacity,
968 fix_start_cumul_to_zero, name);
971bool RoutingModel::AddDimensionDependentDimensionWithVehicleCapacityInternal(
972 const std::vector<int>& pure_transits,
973 const std::vector<int>& dependent_transits,
974 const RoutingDimension* base_dimension, int64_t slack_max,
975 std::vector<int64_t> vehicle_capacities,
bool fix_start_cumul_to_zero,
976 const std::string& name) {
977 CHECK_EQ(vehicles_, vehicle_capacities.size());
979 if (base_dimension ==
nullptr) {
981 name, RoutingDimension::SelfBased());
984 name, base_dimension);
986 return InitializeDimensionInternal(pure_transits,
988 dependent_transits, slack_max,
989 fix_start_cumul_to_zero, new_dimension);
993 int pure_transit,
int dependent_transit,
995 int64_t vehicle_capacity,
bool fix_start_cumul_to_zero,
996 const std::string& name) {
997 std::vector<int> pure_transits(vehicles_, pure_transit);
998 std::vector<int> dependent_transits(vehicles_, dependent_transit);
999 std::vector<int64_t> vehicle_capacities(vehicles_, vehicle_capacity);
1000 return AddDimensionDependentDimensionWithVehicleCapacityInternal(
1001 pure_transits, dependent_transits, base_dimension, slack_max,
1002 std::move(vehicle_capacities), fix_start_cumul_to_zero, name);
1006 const std::function<int64_t(int64_t)>& f, int64_t domain_start,
1007 int64_t domain_end) {
1008 const std::function<int64_t(int64_t)> g = [&f](int64_t x) {
1018 std::vector<std::string> dimension_names;
1019 for (
const auto& dimension_name_index : dimension_name_to_index_) {
1020 dimension_names.push_back(dimension_name_index.first);
1022 std::sort(dimension_names.begin(), dimension_names.end());
1023 return dimension_names;
1028 const int optimizer_index = GetGlobalCumulOptimizerIndex(dimension);
1029 return optimizer_index < 0
1031 : global_dimension_optimizers_[optimizer_index].lp_optimizer.get();
1036 const int optimizer_index = GetGlobalCumulOptimizerIndex(dimension);
1037 return optimizer_index < 0
1039 : global_dimension_optimizers_[optimizer_index].mp_optimizer.get();
1042int RoutingModel::GetGlobalCumulOptimizerIndex(
1043 const RoutingDimension& dimension)
const {
1046 if (dim_index < 0 || dim_index >= global_optimizer_index_.size() ||
1047 global_optimizer_index_[dim_index] < 0) {
1050 const int optimizer_index = global_optimizer_index_[dim_index];
1051 DCHECK_LT(optimizer_index, global_dimension_optimizers_.size());
1052 return optimizer_index;
1057 const int optimizer_index = GetLocalCumulOptimizerIndex(dimension);
1058 return optimizer_index < 0
1060 : local_dimension_optimizers_[optimizer_index].lp_optimizer.get();
1065 const int optimizer_index = GetLocalCumulOptimizerIndex(dimension);
1066 return optimizer_index < 0
1068 : local_dimension_optimizers_[optimizer_index].mp_optimizer.get();
1071int RoutingModel::GetLocalCumulOptimizerIndex(
1072 const RoutingDimension& dimension)
const {
1075 if (dim_index < 0 || dim_index >= local_optimizer_index_.size() ||
1076 local_optimizer_index_[dim_index] < 0) {
1079 const int optimizer_index = local_optimizer_index_[dim_index];
1080 DCHECK_LT(optimizer_index, local_dimension_optimizers_.size());
1081 return optimizer_index;
1085 return dimension_name_to_index_.contains(dimension_name);
1089 absl::string_view dimension_name)
const {
1095 const std::string& dimension_name)
const {
1096 return *dimensions_[
gtl::FindOrDie(dimension_name_to_index_, dimension_name)];
1100 const std::string& dimension_name)
const {
1103 return dimensions_[index];
1114 : start_domain_(
Domain::AllValues()), end_domain_(
Domain::AllValues()) {
1119 : start_domain_(
std::move(start_domain)),
1120 end_domain_(
std::move(end_domain)) {}
1122void ResourceGroup::Resource::SetDimensionAttributes(
1124 DCHECK(attributes_.empty())
1125 <<
"As of 2021/07, each resource can only constrain a single dimension.";
1128 DCHECK(!dimension_attributes_.contains(dimension_index));
1129 const int attribute_index = attributes_.size();
1130 dimension_attributes_[dimension_index] = attribute_index;
1131 if (dimension_index >= dimension_attributes_per_index_.size()) {
1132 dimension_attributes_per_index_.resize(dimension_index.value() + 1);
1134 dimension_attributes_per_index_[dimension_index] = attribute_index;
1135 attributes_.push_back(std::move(attributes));
1140 static const Attributes*
const kAttributes =
new Attributes();
1141 return *kAttributes;
1145 DCHECK_EQ(resource_groups_.size(), resource_vars_.size());
1148 resource_groups_.push_back(absl::WrapUnique(
new ResourceGroup(
this)));
1149 const int rg_index = resource_groups_.back()->Index();
1150 DCHECK_EQ(rg_index, resource_groups_.size() - 1);
1154 resource_vars_.push_back({});
1155 solver_->MakeIntVarArray(
vehicles(), -1, std::numeric_limits<int64_t>::max(),
1156 absl::StrCat(
"Resources[", rg_index,
"]"),
1157 &resource_vars_.back());
1159 return resource_groups_[rg_index].get();
1164 resources_.push_back({std::move(attributes), dimension});
1166 affected_dimension_indices_.insert(dimension->
index());
1168 DCHECK_EQ(affected_dimension_indices_.size(), 1)
1169 <<
"As of 2021/07, each ResourceGroup can only affect a single "
1170 "RoutingDimension at a time.";
1172 return resources_.size() - 1;
1176 DCHECK_LT(vehicle, vehicle_requires_resource_.size());
1177 if (vehicle_requires_resource_[vehicle])
return;
1178 vehicle_requires_resource_[vehicle] =
true;
1179 vehicles_requiring_resource_.push_back(vehicle);
1183struct ResourceClass {
1187 dimension_attributes;
1189 std::vector<bool> assignable_to_vehicle;
1192 friend bool operator==(
const ResourceClass& c1,
const ResourceClass& c2) {
1193 return c1.dimension_attributes == c2.dimension_attributes &&
1194 c1.assignable_to_vehicle == c2.assignable_to_vehicle;
1196 template <
typename H>
1197 friend H AbslHashValue(H h,
const ResourceClass& c) {
1198 return H::combine(std::move(h), c.dimension_attributes,
1199 c.assignable_to_vehicle);
1204void ResourceGroup::ComputeResourceClasses() {
1206 resource_indices_per_class_.clear();
1208 absl::flat_hash_map<ResourceClass, ResourceClassIndex> resource_class_map;
1209 for (
int r = 0; r < resources_.size(); ++r) {
1210 ResourceClass resource_class;
1212 util_intops::StrongVector<DimensionIndex, Attributes>& dim_attributes =
1213 resource_class.dimension_attributes;
1215 for (
const auto& [dim_index, attributes] :
1216 resources_[r].dimension_attributes_) {
1217 dim_attributes[dim_index] = resources_[r].attributes_[attributes];
1220 std::vector<bool>& assignable_to_v = resource_class.assignable_to_vehicle;
1221 assignable_to_v.resize(model_->vehicles_,
false);
1222 for (
int v : vehicles_requiring_resource_) {
1224 model_->ResourceVar(v, index_)->Contains(r);
1227 DCHECK_EQ(resource_indices_per_class_.size(), resource_class_map.size());
1231 &resource_class_map, resource_class, num_resource_classes);
1232 if (resource_class_index == num_resource_classes) {
1234 resource_indices_per_class_.
push_back({});
1236 resource_indices_per_class_[resource_class_index].
push_back(r);
1243 return dimension_resource_group_indices_[dimension->
index()];
1248 int64_t solve_period)
1250 search_parameters_(search_parameters),
1251 solve_period_(solve_period) {
1252 DCHECK(model_ !=
nullptr);
1255 const std::vector<IntVar*> nexts = model_->
Nexts();
1256 container->
Resize(nexts.size());
1257 for (
int i = 0; i < nexts.size(); ++i) {
1258 IntVar* next_var = nexts[i];
1260 var_to_index_[next_var] = i;
1269 const std::vector<RoutingModel::VariableValuePair>& in_state,
1270 std::vector<RoutingModel::VariableValuePair>* out_state) {
1271 if (solve_period_ <= 0)
return false;
1272 if (call_count_ == solve_period_) {
1279 for (
const auto [var, value] : in_state) {
1280 container->MutableElement(var)->SetValue(value);
1282 if (call_count_ != 0)
return false;
1283 absl::flat_hash_set<IntVar*> touched;
1284 const Assignment*
solution = model_->FastSolveFromAssignmentWithParameters(
1285 state_, *search_parameters_,
1287 if (
solution ==
nullptr || touched.empty())
return false;
1288 for (IntVar* var : touched) {
1289 const int index = var_to_index_[var];
1291 out_state->push_back({index, value});
1292 container->MutableElement(index)->SetValue(value);
1298 CHECK_LT(0, vehicles_);
1299 for (
int i = 0; i < vehicles_; ++i) {
1306 CHECK_LT(vehicle, vehicles_);
1307 CHECK_LT(evaluator_index, transit_evaluators_.size());
1308 vehicle_to_transit_cost_[vehicle] = evaluator_index;
1312 for (
int i = 0; i < vehicles_; ++i) {
1318 CHECK_LT(vehicle, vehicles_);
1319 return fixed_cost_of_vehicle_[vehicle];
1323 CHECK_LT(vehicle, vehicles_);
1325 fixed_cost_of_vehicle_[vehicle] = cost;
1329 const std::string& distance,
1330 int64_t cost_per_unit,
1339 const std::string& force,
const std::string& distance, int64_t threshold,
1340 int64_t cost_per_unit_below_threshold,
1341 int64_t cost_per_unit_above_threshold,
int vehicle) {
1342 DCHECK_LE(0, vehicle);
1343 DCHECK_LT(vehicle, vehicles_);
1344 DCHECK_LE(0, threshold);
1345 DCHECK_LE(0, cost_per_unit_below_threshold);
1346 DCHECK_LE(0, cost_per_unit_above_threshold);
1348 if (cost_per_unit_below_threshold == 0 && cost_per_unit_above_threshold == 0)
1351 std::vector<Limit>& energy_costs =
1352 force_distance_to_energy_costs_[std::make_pair(force, distance)];
1353 if (energy_costs.size() < vehicles_) {
1354 energy_costs.resize(vehicles_, {0, 0, 0});
1356 energy_costs[vehicle] = {
1357 .threshold = threshold,
1358 .cost_per_unit_below_threshold = cost_per_unit_below_threshold,
1359 .cost_per_unit_above_threshold = cost_per_unit_above_threshold};
1363 int64_t linear_cost_factor, int64_t quadratic_cost_factor) {
1364 for (
int v = 0; v < vehicles_; v++) {
1371 int64_t linear_cost_factor, int64_t quadratic_cost_factor,
int vehicle) {
1372 CHECK_LT(vehicle, vehicles_);
1373 DCHECK_GE(linear_cost_factor, 0);
1374 DCHECK_GE(quadratic_cost_factor, 0);
1375 if (linear_cost_factor + quadratic_cost_factor > 0) {
1376 vehicle_amortized_cost_factors_set_ =
true;
1378 linear_cost_factor_of_vehicle_[vehicle] = linear_cost_factor;
1379 quadratic_cost_factor_of_vehicle_[vehicle] = quadratic_cost_factor;
1383 absl::AnyInvocable<std::optional<int64_t>(
const std::vector<int64_t>&)>
1385 bool costs_are_homogeneous_across_vehicles) {
1386 costs_are_homogeneous_across_vehicles_ &=
1387 costs_are_homogeneous_across_vehicles;
1388 route_evaluators_.push_back(std::move(route_evaluator));
1391void RoutingModel::FinalizeAllowedVehicles() {
1396 struct TransitBounds {
1397 int64_t min = std::numeric_limits<int64_t>::max();
1398 int64_t max = std::numeric_limits<int64_t>::min();
1400 std::vector<TransitBounds> dimension_bounds(unary_dimensions.size());
1401 for (
int d = 0; d < unary_dimensions.size(); ++d) {
1402 TransitBounds transit_bounds;
1404 for (
const int e : dimension->class_evaluators_) {
1406 DCHECK(evaluator !=
nullptr);
1407 for (
int node = 0; node <
Size(); ++node) {
1409 const int64_t transit = evaluator(node);
1410 const IntVar* slack = dimension->SlackVar(node);
1412 .min = std::min(transit_bounds.min,
CapAdd(transit, slack->Min())),
1413 .max = std::max(transit_bounds.max,
CapAdd(transit, slack->Max()))};
1416 dimension_bounds[d] = transit_bounds;
1421 for (
int vehicle = 0; vehicle < vehicles_; ++vehicle) {
1423 for (
int d = 0; d < unary_dimensions.size(); ++d) {
1426 dim->GetUnaryTransitEvaluator(vehicle);
1427 DCHECK(transit_evaluator !=
nullptr);
1428 const TransitBounds allowed_transits = {
1429 .min =
CapOpp(dim->vehicle_capacities()[vehicle]),
1430 .max = dim->vehicle_capacities()[vehicle],
1434 if (allowed_transits.min <= dimension_bounds[d].min &&
1435 dimension_bounds[d].max <= allowed_transits.max) {
1438 for (
int node = 0; node <
Size(); ++node) {
1440 absl::flat_hash_set<int>& allowed_vehicles = allowed_vehicles_[node];
1446 if (!allowed_vehicles.empty() && !allowed_vehicles.contains(vehicle)) {
1450 const int64_t transit = transit_evaluator(node);
1451 const IntVar* slack_var = dim->SlackVar(node);
1452 if (allowed_transits.min <=
CapAdd(transit, slack_var->Max()) &&
1453 CapAdd(transit, slack_var->Min()) <= allowed_transits.max) {
1457 if (allowed_vehicles.empty()) {
1458 allowed_vehicles.reserve(vehicles_);
1459 for (
int v = 0; v < vehicles_; ++v) allowed_vehicles.insert(v);
1461 allowed_vehicles.erase(vehicle);
1462 if (allowed_vehicles.empty()) {
1467 allowed_vehicles.insert(-1);
1478void RoutingModel::ComputeCostClasses(
1479 const RoutingSearchParameters& ) {
1481 cost_classes_.reserve(vehicles_);
1482 cost_classes_.clear();
1483 cost_class_index_of_vehicle_.assign(vehicles_,
CostClassIndex(-1));
1484 absl::flat_hash_map<CostClass, CostClassIndex> cost_class_map;
1487 cost_classes_.push_back(zero_cost_class);
1488 DCHECK_EQ(cost_classes_[kCostClassIndexOfZeroCost].evaluator_index, 0);
1489 cost_class_map[zero_cost_class] = kCostClassIndexOfZeroCost;
1494 has_vehicle_with_zero_cost_class_ =
false;
1495 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
1496 CostClass cost_class(vehicle_to_transit_cost_[vehicle]);
1500 const int64_t span_coeff =
1501 dimension->vehicle_span_cost_coefficients()[vehicle];
1502 const int64_t slack_coeff =
1503 dimension->vehicle_slack_cost_coefficients()[vehicle];
1504 if (span_coeff == 0 && slack_coeff == 0)
continue;
1505 cost_class.dimension_transit_evaluator_class_and_cost_coefficient
1506 .push_back({dimension->vehicle_to_class(vehicle), span_coeff,
1507 slack_coeff, dimension});
1510 cost_class.dimension_transit_evaluator_class_and_cost_coefficient);
1515 if (cost_class_index == kCostClassIndexOfZeroCost) {
1516 has_vehicle_with_zero_cost_class_ =
true;
1517 }
else if (cost_class_index == num_cost_classes) {
1518 cost_classes_.push_back(std::move(cost_class));
1520 cost_class_index_of_vehicle_[vehicle] = cost_class_index;
1534 costs_are_homogeneous_across_vehicles_ &= has_vehicle_with_zero_cost_class_
1541struct VehicleClass {
1542 using DimensionIndex = RoutingModel::DimensionIndex;
1544 RoutingModel::CostClassIndex cost_class_index;
1548 bool used_when_empty;
1555 int start_equivalence_class;
1556 int end_equivalence_class;
1559 util_intops::StrongVector<DimensionIndex, int64_t> dimension_start_cumuls_min;
1560 util_intops::StrongVector<DimensionIndex, int64_t> dimension_start_cumuls_max;
1561 util_intops::StrongVector<DimensionIndex, int64_t> dimension_end_cumuls_min;
1562 util_intops::StrongVector<DimensionIndex, int64_t> dimension_end_cumuls_max;
1563 util_intops::StrongVector<DimensionIndex, int64_t> dimension_capacities;
1566 util_intops::StrongVector<DimensionIndex, int64_t>
1567 dimension_evaluator_classes;
1570 util_intops::StrongVector<DimensionIndex, int64_t>
1571 cumul_dependent_dimension_evaluator_classes;
1573 uint64_t visitable_nodes_hash;
1576 std::vector<int64_t> group_allowed_resources_hash;
1578 friend bool operator==(
const VehicleClass& c1,
const VehicleClass& c2) {
1579 return c1.cost_class_index == c2.cost_class_index &&
1580 c1.fixed_cost == c2.fixed_cost &&
1581 c1.used_when_empty == c2.used_when_empty &&
1582 c1.start_equivalence_class == c2.start_equivalence_class &&
1583 c1.end_equivalence_class == c2.end_equivalence_class &&
1584 c1.dimension_start_cumuls_min == c2.dimension_start_cumuls_min &&
1585 c1.dimension_start_cumuls_max == c2.dimension_start_cumuls_max &&
1586 c1.dimension_end_cumuls_min == c2.dimension_end_cumuls_min &&
1587 c1.dimension_end_cumuls_max == c2.dimension_end_cumuls_max &&
1588 c1.dimension_capacities == c2.dimension_capacities &&
1589 c1.dimension_evaluator_classes == c2.dimension_evaluator_classes &&
1590 c1.cumul_dependent_dimension_evaluator_classes ==
1591 c2.cumul_dependent_dimension_evaluator_classes &&
1592 c1.visitable_nodes_hash == c2.visitable_nodes_hash &&
1593 c1.group_allowed_resources_hash == c2.group_allowed_resources_hash;
1595 template <
typename H>
1597 return H::combine(std::move(h),
c.cost_class_index,
c.fixed_cost,
1598 c.used_when_empty,
c.start_equivalence_class,
1599 c.end_equivalence_class,
c.dimension_start_cumuls_min,
1600 c.dimension_start_cumuls_max,
c.dimension_end_cumuls_min,
1601 c.dimension_end_cumuls_max,
c.dimension_capacities,
1602 c.dimension_evaluator_classes,
1603 c.cumul_dependent_dimension_evaluator_classes,
1604 c.visitable_nodes_hash,
c.group_allowed_resources_hash);
1610void RoutingModel::ComputeVehicleClasses() {
1612 absl::flat_hash_map<VehicleClass, VehicleClassIndex> vehicle_class_map;
1613 std::vector<bool> node_is_visitable(
Size(),
true);
1614 const auto bool_vec_hash = absl::Hash<std::vector<bool>>();
1615 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
1616 VehicleClass vehicle_class;
1617 vehicle_class.cost_class_index = cost_class_index_of_vehicle_[vehicle];
1618 vehicle_class.fixed_cost = fixed_cost_of_vehicle_[vehicle];
1619 vehicle_class.used_when_empty = vehicle_used_when_empty_[vehicle];
1620 vehicle_class.start_equivalence_class =
1621 index_to_equivalence_class_[
Start(vehicle)];
1622 vehicle_class.end_equivalence_class =
1623 index_to_equivalence_class_[
End(vehicle)];
1625 IntVar*
const start_cumul_var = dimension->cumuls()[
Start(vehicle)];
1626 vehicle_class.dimension_start_cumuls_min.push_back(
1627 start_cumul_var->Min());
1628 vehicle_class.dimension_start_cumuls_max.push_back(
1629 start_cumul_var->Max());
1630 IntVar*
const end_cumul_var = dimension->cumuls()[
End(vehicle)];
1631 vehicle_class.dimension_end_cumuls_min.push_back(end_cumul_var->Min());
1632 vehicle_class.dimension_end_cumuls_max.push_back(end_cumul_var->Max());
1633 vehicle_class.dimension_capacities.push_back(
1634 dimension->vehicle_capacities()[vehicle]);
1635 vehicle_class.dimension_evaluator_classes.push_back(
1636 dimension->vehicle_to_class(vehicle));
1637 vehicle_class.cumul_dependent_dimension_evaluator_classes.push_back(
1638 dimension->vehicle_to_cumul_dependent_class(vehicle));
1640 node_is_visitable.assign(
Size(),
true);
1641 for (
int index = 0; index <
Size(); ++index) {
1642 DCHECK(!
IsEnd(index));
1644 if (!vehicle_vars_[index]->Contains(vehicle) ||
1646 node_is_visitable[index] =
false;
1649 vehicle_class.visitable_nodes_hash = bool_vec_hash(node_is_visitable);
1651 std::vector<int64_t>& allowed_resources_hash =
1652 vehicle_class.group_allowed_resources_hash;
1653 allowed_resources_hash.reserve(resource_groups_.size());
1654 for (
int rg_index = 0; rg_index < resource_groups_.size(); rg_index++) {
1655 const ResourceGroup& resource_group = *resource_groups_[rg_index];
1656 if (!resource_group.VehicleRequiresAResource(vehicle)) {
1657 allowed_resources_hash.push_back(-1);
1660 const std::vector<IntVar*>& resource_vars = resource_vars_[rg_index];
1661 std::vector<bool> resource_allowed_for_vehicle(resource_group.Size(),
1663 for (
int resource = 0; resource < resource_group.Size(); resource++) {
1664 if (!resource_vars[vehicle]->Contains(resource) ||
1665 !resource_group.IsResourceAllowedForVehicle(resource, vehicle)) {
1666 resource_allowed_for_vehicle[resource] =
false;
1669 allowed_resources_hash.push_back(
1670 bool_vec_hash(resource_allowed_for_vehicle));
1672 DCHECK_EQ(allowed_resources_hash.size(), resource_groups_.size());
1676 &vehicle_class_map, vehicle_class, num_vehicle_classes);
1678 num_vehicle_classes_ = vehicle_class_map.size();
1681void RoutingModel::ComputeVehicleTypes() {
1682 const int nodes_squared = nodes_ * nodes_;
1683 std::vector<int>& type_index_of_vehicle =
1684 vehicle_type_container_.type_index_of_vehicle;
1685 std::vector<std::set<VehicleTypeContainer::VehicleClassEntry>>&
1686 sorted_vehicle_classes_per_type =
1687 vehicle_type_container_.sorted_vehicle_classes_per_type;
1688 std::vector<std::deque<int>>& vehicles_per_vehicle_class =
1689 vehicle_type_container_.vehicles_per_vehicle_class;
1691 type_index_of_vehicle.resize(vehicles_);
1692 sorted_vehicle_classes_per_type.clear();
1693 sorted_vehicle_classes_per_type.reserve(vehicles_);
1694 vehicles_per_vehicle_class.clear();
1697 absl::flat_hash_map<int64_t, int> type_to_type_index;
1699 for (
int v = 0; v < vehicles_; v++) {
1700 const int start = manager_.IndexToNode(
Start(v)).value();
1701 const int end = manager_.IndexToNode(
End(v)).value();
1703 const int64_t type = cost_class * nodes_squared + start * nodes_ +
end;
1705 const auto& vehicle_type_added = type_to_type_index.insert(
1706 std::make_pair(type, type_to_type_index.size()));
1708 const int index = vehicle_type_added.first->second;
1714 if (vehicle_type_added.second) {
1716 DCHECK_EQ(sorted_vehicle_classes_per_type.size(), index);
1717 sorted_vehicle_classes_per_type.push_back({class_entry});
1720 DCHECK_LT(index, sorted_vehicle_classes_per_type.size());
1721 sorted_vehicle_classes_per_type[index].insert(class_entry);
1723 vehicles_per_vehicle_class[vehicle_class].push_back(v);
1724 type_index_of_vehicle[v] = index;
1728void RoutingModel::ComputeResourceClasses() {
1729 for (
auto& resource_group : resource_groups_) {
1730 resource_group->ComputeResourceClasses();
1734void RoutingModel::FinalizeVisitTypes() {
1735 single_nodes_of_type_.clear();
1736 single_nodes_of_type_.resize(num_visit_types_);
1737 pair_indices_of_type_.clear();
1738 pair_indices_of_type_.resize(num_visit_types_);
1739 std::vector<absl::flat_hash_set<int>> pair_indices_added_for_type(
1742 const auto& store_pair_index_type = [
this, &pair_indices_added_for_type](
1743 int pair_index,
int visit_type) {
1745 pair_indices_added_for_type[visit_type].insert(pair_index).second) {
1746 pair_indices_of_type_[visit_type].push_back(pair_index);
1750 for (
int index = 0; index < index_to_visit_type_.size(); index++) {
1752 if (visit_type < 0) {
1756 single_nodes_of_type_[visit_type].push_back(index);
1758 store_pair_index_type(index_to_pickup_position_[index].pd_pair_index,
1760 store_pair_index_type(index_to_delivery_position_[index].pd_pair_index,
1765 TopologicallySortVisitTypes();
1766 ComputeVisitTypesConnectedComponents();
1770template <
typename C>
1771std::vector<std::vector<int>> GetTopologicallySortedNodes(
1772 const SparseBitset<>& active_nodes, std::vector<int> node_in_degree,
1773 const std::vector<absl::flat_hash_set<int>>& children,
1774 const C& comparator) {
1775 std::vector<int> current_nodes_with_zero_indegree;
1776 for (
int node : active_nodes.PositionsSetAtLeastOnce()) {
1777 if (node_in_degree[node] == 0) {
1778 current_nodes_with_zero_indegree.push_back(node);
1781 std::vector<std::vector<int>> topologically_sorted_nodes;
1782 int num_nodes_added = 0;
1783 while (!current_nodes_with_zero_indegree.empty()) {
1786 topologically_sorted_nodes.push_back({});
1787 std::vector<int>& topological_group = topologically_sorted_nodes.back();
1788 std::vector<int> next_nodes_with_zero_indegree;
1789 for (
int node : current_nodes_with_zero_indegree) {
1790 topological_group.push_back(node);
1792 for (
int dependent_node : children[node]) {
1793 DCHECK_GT(node_in_degree[dependent_node], 0);
1794 if (--node_in_degree[dependent_node] == 0) {
1795 next_nodes_with_zero_indegree.push_back(dependent_node);
1799 absl::c_sort(topological_group, comparator);
1801 current_nodes_with_zero_indegree.swap(next_nodes_with_zero_indegree);
1804 const int num_active_nodes =
1805 active_nodes.NumberOfSetCallsWithDifferentArguments();
1806 DCHECK_LE(num_nodes_added, num_active_nodes);
1807 if (num_nodes_added < num_active_nodes) {
1809 topologically_sorted_nodes.clear();
1811 return topologically_sorted_nodes;
1815void RoutingModel::ComputeVisitTypesConnectedComponents() {
1819 std::vector<std::vector<int>> graph(num_visit_types_);
1820 for (
int type = 0; type < num_visit_types_; type++) {
1821 for (
const std::vector<absl::flat_hash_set<int>>*
1822 required_type_alternatives :
1826 for (
const absl::flat_hash_set<int>& alternatives :
1827 *required_type_alternatives) {
1828 for (
int required_type : alternatives) {
1829 graph[required_type].push_back(type);
1830 graph[type].push_back(required_type);
1835 const std::vector<int> connected_components =
1837 visit_type_components_.clear();
1838 visit_type_components_.resize(connected_components.size());
1839 for (
int type = 0; type < num_visit_types_; type++) {
1840 visit_type_components_[connected_components[type]].push_back(type);
1844void RoutingModel::TopologicallySortVisitTypes() {
1848 std::vector<std::pair<double, double>> type_requirement_tightness(
1849 num_visit_types_, {0, 0});
1850 std::vector<absl::flat_hash_set<int>> type_to_dependent_types(
1852 SparseBitset<> types_in_requirement_graph(num_visit_types_);
1853 std::vector<int> in_degree(num_visit_types_, 0);
1854 for (
int type = 0; type < num_visit_types_; type++) {
1855 int num_alternative_required_types = 0;
1856 int num_required_sets = 0;
1857 for (
const std::vector<absl::flat_hash_set<int>>*
1858 required_type_alternatives :
1862 for (
const absl::flat_hash_set<int>& alternatives :
1863 *required_type_alternatives) {
1864 types_in_requirement_graph.Set(type);
1865 num_required_sets++;
1866 for (
int required_type : alternatives) {
1867 type_requirement_tightness[required_type].second +=
1868 1.0 / alternatives.size();
1869 types_in_requirement_graph.Set(required_type);
1870 num_alternative_required_types++;
1871 if (type_to_dependent_types[required_type].insert(type).second) {
1877 if (num_alternative_required_types > 0) {
1878 type_requirement_tightness[type].first += 1.0 * num_required_sets *
1880 num_alternative_required_types;
1884 topologically_sorted_visit_types_ = GetTopologicallySortedNodes(
1885 types_in_requirement_graph, std::move(in_degree), type_to_dependent_types,
1893 [&type_requirement_tightness](
int type1,
int type2) {
1894 const auto& tightness1 = type_requirement_tightness[type1];
1895 const auto& tightness2 = type_requirement_tightness[type2];
1896 return tightness1 > tightness2 ||
1897 (tightness1 == tightness2 && type1 < type2);
1901void RoutingModel::FinalizePrecedences() {
1903 if (dimension->GetNodePrecedences().empty())
continue;
1904 std::vector<int> in_degree(
Size(), 0);
1905 SparseBitset<> nodes_in_precedences(
Size());
1906 std::vector<absl::flat_hash_set<int>> successors(
Size());
1907 std::vector<int64_t> node_max_offset(
Size(),
1908 std::numeric_limits<int64_t>::min());
1911 for (
const auto [first_node, second_node, offset, unused] :
1912 dimension->GetNodePrecedences()) {
1913 in_degree[second_node]++;
1914 nodes_in_precedences.Set(first_node);
1915 nodes_in_precedences.Set(second_node);
1916 successors[first_node].insert(second_node);
1917 node_max_offset[first_node] =
1918 std::max(node_max_offset[first_node], offset);
1919 node_max_offset[second_node] =
1920 std::max(node_max_offset[second_node], offset);
1922 topologically_sorted_node_precedences_.push_back(
1923 GetTopologicallySortedNodes(
1924 nodes_in_precedences, std::move(in_degree), successors,
1929 [&node_max_offset](
int node1,
int node2) {
1930 const int64_t offset1 = node_max_offset[node1];
1931 const int64_t offset2 = node_max_offset[node2];
1932 return offset1 > offset2 || (offset1 == offset2 && node1 < node2);
1938 const std::vector<int64_t>& indices, int64_t penalty,
1940 CHECK_GE(max_cardinality, 1);
1941 for (
int i = 0;
i < indices.size(); ++
i) {
1946 disjunctions_.push_back(
1947 {indices, {penalty, max_cardinality, penalty_cost_behavior}});
1948 for (
const int64_t index : indices) {
1949 index_to_disjunctions_[index].push_back(disjunction_index);
1951 return disjunction_index;
1955 for (
const auto& [indices, value] : disjunctions_) {
1956 if (value.penalty ==
kNoPenalty)
return true;
1962 for (
const auto& [indices, value] : disjunctions_) {
1963 if (indices.size() > value.max_cardinality)
return true;
1968std::vector<std::pair<int64_t, int64_t>>
1970 std::vector<std::pair<int64_t, int64_t>> var_index_pairs;
1971 for (
const Disjunction& disjunction : disjunctions_) {
1972 const std::vector<int64_t>& var_indices = disjunction.indices;
1973 if (var_indices.size() != 2)
continue;
1974 const int64_t v0 = var_indices[0];
1975 const int64_t v1 = var_indices[1];
1976 if (index_to_disjunctions_[v0].size() == 1 &&
1977 index_to_disjunctions_[v1].size() == 1) {
1979 var_index_pairs.push_back({std::min(v0, v1), std::max(v0, v1)});
1982 std::sort(var_index_pairs.begin(), var_index_pairs.end());
1983 return var_index_pairs;
1988 for (Disjunction& disjunction : disjunctions_) {
1989 bool has_one_potentially_active_var =
false;
1990 for (
const int64_t var_index : disjunction.indices) {
1992 has_one_potentially_active_var =
true;
1996 if (!has_one_potentially_active_var) {
1997 disjunction.value.max_cardinality = 0;
2003 const std::vector<int64_t>& indices = disjunctions_[disjunction].indices;
2004 const int indices_size = indices.size();
2005 std::vector<IntVar*> disjunction_vars(indices_size);
2006 for (
int i = 0;
i < indices_size; ++
i) {
2007 const int64_t index = indices[
i];
2008 CHECK_LT(index,
Size());
2011 const int64_t max_cardinality =
2012 disjunctions_[disjunction].value.max_cardinality;
2014 IntVar* number_active_vars = solver_->MakeIntVar(0, max_cardinality);
2015 solver_->AddConstraint(
2016 solver_->MakeSumEquality(disjunction_vars, number_active_vars));
2018 const int64_t penalty = disjunctions_[disjunction].value.penalty;
2022 solver_->AddConstraint(
2023 solver_->MakeEquality(number_active_vars, max_cardinality));
2028 disjunctions_[disjunction].value.penalty_cost_behavior;
2029 if (max_cardinality == 1 ||
2031 IntVar* penalize_var = solver_->MakeBoolVar();
2032 solver_->AddConstraint(solver_->MakeIsDifferentCstCt(
2033 number_active_vars, max_cardinality, penalize_var));
2034 return solver_->MakeProd(penalize_var, penalty)->Var();
2036 IntVar* number_no_active_vars = solver_->MakeIntVar(0, max_cardinality);
2037 solver_->AddConstraint(solver_->MakeEquality(
2038 number_no_active_vars,
2039 solver_->MakeDifference(max_cardinality, number_active_vars)));
2040 return solver_->MakeProd(number_no_active_vars, penalty)->Var();
2046 if (!indices.empty()) {
2047 same_vehicle_costs_.push_back(
2048 {.indices = std::move(indices), .value = cost});
2055 auto& allowed_vehicles = allowed_vehicles_[index];
2056 allowed_vehicles.clear();
2058 allowed_vehicles.insert(vehicle);
2063 AddPickupAndDeliverySetsInternal({pickup}, {delivery});
2070 AddPickupAndDeliverySetsInternal(
2073 pickup_delivery_disjunctions_.push_back(
2074 {pickup_disjunction, delivery_disjunction});
2079void RoutingModel::AddPickupAndDeliverySetsInternal(
2080 const std::vector<int64_t>& pickups,
2081 const std::vector<int64_t>& deliveries) {
2082 if (pickups.empty() || deliveries.empty()) {
2085 const int64_t size =
Size();
2086 const int pair_index = pickup_delivery_pairs_.size();
2087 for (
int pickup_index = 0; pickup_index < pickups.size(); pickup_index++) {
2088 const int64_t pickup = pickups[pickup_index];
2089 CHECK_LT(pickup, size);
2092 index_to_pickup_position_[pickup] = {pair_index, pickup_index};
2094 for (
int delivery_index = 0; delivery_index < deliveries.size();
2096 const int64_t delivery = deliveries[delivery_index];
2097 CHECK_LT(delivery, size);
2100 index_to_delivery_position_[delivery] = {pair_index, delivery_index};
2102 pickup_delivery_pairs_.push_back({pickups, deliveries});
2105std::optional<RoutingModel::PickupDeliveryPosition>
2107 CHECK_LT(node_index, index_to_pickup_position_.size());
2108 if (
IsPickup(node_index))
return index_to_pickup_position_[node_index];
2109 return std::nullopt;
2112std::optional<RoutingModel::PickupDeliveryPosition>
2114 CHECK_LT(node_index, index_to_delivery_position_.size());
2115 if (
IsDelivery(node_index))
return index_to_delivery_position_[node_index];
2116 return std::nullopt;
2121 CHECK_LT(vehicle, vehicles_);
2122 vehicle_pickup_delivery_policy_[vehicle] = policy;
2127 CHECK_LT(0, vehicles_);
2128 for (
int i = 0; i < vehicles_; ++i) {
2135 CHECK_LT(vehicle, vehicles_);
2136 return vehicle_pickup_delivery_policy_[vehicle];
2140 int64_t node,
const std::function<
bool(int64_t)>& is_match)
const {
2151 pickup_position.has_value()) {
2152 const int pair_index = pickup_position->pd_pair_index;
2153 for (int64_t delivery_sibling :
2154 pickup_and_delivery_pairs[pair_index].delivery_alternatives) {
2155 if (is_match(delivery_sibling)) {
2156 return delivery_sibling;
2162 delivery_position.has_value()) {
2163 const int pair_index = delivery_position->pd_pair_index;
2164 for (int64_t pickup_sibling :
2165 pickup_and_delivery_pairs[pair_index].pickup_alternatives) {
2166 if (is_match(pickup_sibling)) {
2167 return pickup_sibling;
2172 return std::nullopt;
2177 for (
int i = 0;
i <
Nexts().size(); ++
i) {
2186IntVar* RoutingModel::CreateSameVehicleCost(
int vehicle_index) {
2187 const std::vector<int64_t>& indices =
2188 same_vehicle_costs_[vehicle_index].indices;
2189 CHECK(!indices.empty());
2190 std::vector<IntVar*> vehicle_counts;
2191 solver_->MakeIntVarArray(vehicle_vars_.size() + 1, 0, indices.size() + 1,
2193 std::vector<int64_t> vehicle_values(vehicle_vars_.size() + 1);
2194 for (
int i = 0;
i < vehicle_vars_.size(); ++
i) {
2195 vehicle_values[
i] =
i;
2197 vehicle_values[vehicle_vars_.size()] = -1;
2198 std::vector<IntVar*> vehicle_vars;
2199 vehicle_vars.reserve(indices.size());
2200 for (
const int64_t index : indices) {
2201 vehicle_vars.push_back(vehicle_vars_[index]);
2203 solver_->AddConstraint(solver_->MakeDistribute(vehicle_vars, vehicle_counts));
2204 std::vector<IntVar*> vehicle_used;
2205 for (
int i = 0;
i < vehicle_vars_.size() + 1; ++
i) {
2206 vehicle_used.push_back(
2207 solver_->MakeIsGreaterOrEqualCstVar(vehicle_counts[i], 1));
2209 vehicle_used.push_back(solver_->MakeIntConst(-1));
2211 ->MakeProd(solver_->MakeMax(solver_->MakeSum(vehicle_used), 0),
2212 same_vehicle_costs_[vehicle_index].value)
2217 extra_operators_.push_back(ls_operator);
2226void RoutingModel::AppendHomogeneousArcCosts(
2227 const RoutingSearchParameters& parameters,
int node_index,
2228 std::vector<IntVar*>* cost_elements) {
2229 CHECK(cost_elements !=
nullptr);
2230 const auto arc_cost_evaluator = [
this, node_index](int64_t next_index) {
2233 if (UsesLightPropagation(parameters)) {
2237 IntVar*
const base_cost_var =
2238 solver_->MakeIntVar(0, std::numeric_limits<int64_t>::max());
2239 solver_->AddConstraint(solver_->MakeLightElement(
2240 arc_cost_evaluator, base_cost_var, nexts_[node_index],
2241 [
this]() { return enable_deep_serialization_; }));
2243 solver_->MakeProd(base_cost_var, active_[node_index])->Var();
2244 cost_elements->push_back(var);
2246 IntExpr*
const expr =
2247 solver_->MakeElement(arc_cost_evaluator, nexts_[node_index]);
2248 IntVar*
const var = solver_->MakeProd(expr, active_[node_index])->Var();
2249 cost_elements->push_back(var);
2253void RoutingModel::AppendArcCosts(
const RoutingSearchParameters& parameters,
2255 std::vector<IntVar*>* cost_elements) {
2256 CHECK(cost_elements !=
nullptr);
2257 DCHECK_GT(vehicles_, 0);
2258 if (UsesLightPropagation(parameters)) {
2262 IntVar*
const base_cost_var =
2263 solver_->MakeIntVar(0, std::numeric_limits<int64_t>::max());
2264 solver_->AddConstraint(solver_->MakeLightElement(
2265 [
this, node_index](int64_t
to, int64_t vehicle) {
2266 return GetArcCostForVehicle(node_index, to, vehicle);
2268 base_cost_var, nexts_[node_index], vehicle_vars_[node_index],
2269 [
this]() { return enable_deep_serialization_; }));
2271 solver_->MakeProd(base_cost_var, active_[node_index])->Var();
2272 cost_elements->push_back(var);
2274 IntVar*
const vehicle_class_var =
2277 [
this](int64_t index) {
2278 return SafeGetCostClassInt64OfVehicle(index);
2280 vehicle_vars_[node_index])
2282 IntExpr*
const expr = solver_->MakeElement(
2283 [
this, node_index](int64_t next, int64_t vehicle_class) {
2286 nexts_[node_index], vehicle_class_var);
2287 IntVar*
const var = solver_->MakeProd(expr, active_[node_index])->Var();
2288 cost_elements->push_back(var);
2292int RoutingModel::GetVehicleStartClass(int64_t start_index)
const {
2301 int64_t start_end_index)
const {
2309 int64_t from_index, int64_t to_index)
const {
2310 std::vector<std::pair<int64_t, int64_t>> arcs;
2313 const int64_t start =
Start(vehicle);
2314 if (!
IsEnd(to_index)) {
2315 arcs.push_back({start, to_index});
2317 arcs.push_back({start,
End(vehicle)});
2320 }
else if (
IsEnd(to_index)) {
2322 arcs.push_back({from_index,
End(vehicle)});
2325 arcs.push_back({from_index, to_index});
2330std::string RoutingModel::FindErrorInSearchParametersForModel(
2331 const RoutingSearchParameters& search_parameters)
const {
2333 search_parameters.first_solution_strategy();
2334 if (GetFirstSolutionDecisionBuilder(search_parameters) ==
nullptr) {
2335 return absl::StrCat(
2336 "Undefined first solution strategy: ",
2338 " (int value: ", first_solution_strategy,
")");
2340 if (search_parameters.first_solution_strategy() ==
2343 return "Undefined sweep arranger for ROUTING_SWEEP strategy.";
2348void RoutingModel::QuietCloseModel() {
2359 same_vehicle_components_.SetNumberOfNodes(model->
Size());
2360 same_active_var_components_.SetNumberOfNodes(model->
Size());
2362 RoutingDimension* const dimension = model->GetMutableDimension(name);
2363 const std::vector<IntVar*>& cumuls = dimension->cumuls();
2364 for (int i = 0; i < cumuls.size(); ++i) {
2365 cumul_to_dim_indices_[cumuls[i]] = {dimension, i};
2368 const std::vector<IntVar*>& vehicle_vars = model->
VehicleVars();
2369 for (
int i = 0; i < vehicle_vars.size(); ++i) {
2370 vehicle_var_to_indices_[vehicle_vars[i]] = i;
2372 for (
int i = 0; i < model->
Size(); ++i) {
2373 active_var_to_indices_[model->
ActiveVar(i)] = i;
2375 RegisterInspectors();
2378 void EndVisitModel(
const std::string& )
override {
2379 const std::vector<int> node_to_same_vehicle_component_id =
2380 same_vehicle_components_.GetComponentIds();
2381 model_->InitSameVehicleGroups(
2382 same_vehicle_components_.GetNumberOfComponents());
2383 for (
int node = 0; node < model_->Size(); ++node) {
2384 model_->SetSameVehicleGroup(node,
2385 node_to_same_vehicle_component_id[node]);
2387 const std::vector<int> node_to_same_active_var_component_id =
2388 same_active_var_components_.GetComponentIds();
2389 model_->InitSameActiveVarGroups(
2390 same_active_var_components_.GetNumberOfComponents());
2391 for (
int node = 0; node < model_->Size(); ++node) {
2392 model_->SetSameActiveVarGroup(node,
2393 node_to_same_active_var_component_id[node]);
2398 void EndVisitConstraint(
const std::string& type_name,
2402 void VisitIntegerExpressionArgument(
const std::string& type_name,
2403 IntExpr*
const expr)
override {
2405 [](
const IntExpr*) {})(expr);
2407 void VisitIntegerArrayArgument(
const std::string& arg_name,
2408 const std::vector<int64_t>& values)
override {
2410 [](absl::Span<const int64_t>) {})(values);
2414 using ExprInspector = std::function<void(
const IntExpr*)>;
2415 using ArrayInspector = std::function<void(
const std::vector<int64_t>&)>;
2416 using ConstraintInspector = std::function<void()>;
2418 void RegisterInspectors() {
2419 expr_inspectors_[kExpressionArgument] = [
this](
const IntExpr* expr) {
2422 expr_inspectors_[kLeftArgument] = [
this](
const IntExpr* expr) {
2425 expr_inspectors_[kRightArgument] = [
this](
const IntExpr* expr) {
2428 array_inspectors_[kStartsArgument] =
2429 [
this](
const std::vector<int64_t>& int_array) {
2430 starts_argument_ = int_array;
2432 array_inspectors_[kEndsArgument] =
2433 [
this](
const std::vector<int64_t>& int_array) {
2434 ends_argument_ = int_array;
2436 constraint_inspectors_[kNotMember] = [
this]() {
2437 std::pair<RoutingDimension*, int> dim_index;
2438 if (
gtl::FindCopy(cumul_to_dim_indices_, expr_, &dim_index)) {
2440 const int index = dim_index.second;
2441 dimension->forbidden_intervals_[index].InsertIntervals(starts_argument_,
2443 VLOG(2) << dimension->name() <<
" " << index <<
": "
2444 << dimension->forbidden_intervals_[index].DebugString();
2447 starts_argument_.clear();
2448 ends_argument_.clear();
2450 constraint_inspectors_[kEquality] = [
this]() {
2452 int right_index = 0;
2453 if (
gtl::FindCopy(vehicle_var_to_indices_, left_, &left_index) &&
2454 gtl::FindCopy(vehicle_var_to_indices_, right_, &right_index)) {
2455 VLOG(2) <<
"Vehicle variables for " << left_index <<
" and "
2456 << right_index <<
" are equal.";
2457 same_vehicle_components_.AddEdge(left_index, right_index);
2459 if (
gtl::FindCopy(active_var_to_indices_, left_, &left_index) &&
2460 gtl::FindCopy(active_var_to_indices_, right_, &right_index)) {
2461 VLOG(2) <<
"Active variables for " << left_index <<
" and "
2462 << right_index <<
" are equal.";
2463 same_active_var_components_.AddEdge(left_index, right_index);
2470 std::pair<RoutingDimension*, int> left_index;
2471 std::pair<RoutingDimension*, int> right_index;
2472 if (
gtl::FindCopy(cumul_to_dim_indices_, left_, &left_index) &&
2473 gtl::FindCopy(cumul_to_dim_indices_, right_, &right_index)) {
2475 if (dimension == right_index.first) {
2476 VLOG(2) <<
"For dimension " << dimension->name() <<
", cumul for "
2477 << left_index.second <<
" is less than " << right_index.second
2479 dimension->path_precedence_graph_.AddArc(left_index.second,
2480 right_index.second);
2489 DenseConnectedComponentsFinder same_vehicle_components_;
2490 DenseConnectedComponentsFinder same_active_var_components_;
2491 absl::flat_hash_map<const IntExpr*, std::pair<RoutingDimension*, int>>
2492 cumul_to_dim_indices_;
2493 absl::flat_hash_map<const IntExpr*, int> vehicle_var_to_indices_;
2494 absl::flat_hash_map<const IntExpr*, int> active_var_to_indices_;
2495 absl::flat_hash_map<std::string, ExprInspector> expr_inspectors_;
2496 absl::flat_hash_map<std::string, ArrayInspector> array_inspectors_;
2497 absl::flat_hash_map<std::string, ConstraintInspector> constraint_inspectors_;
2498 const IntExpr* expr_ =
nullptr;
2499 const IntExpr* left_ =
nullptr;
2500 const IntExpr* right_ =
nullptr;
2501 std::vector<int64_t> starts_argument_;
2502 std::vector<int64_t> ends_argument_;
2505void RoutingModel::DetectImplicitPickupAndDeliveries() {
2506 std::vector<int> non_pickup_delivery_nodes;
2507 for (
int node = 0; node <
Size(); ++node) {
2509 non_pickup_delivery_nodes.push_back(node);
2513 std::set<std::pair<int64_t, int64_t>> implicit_pickup_deliveries;
2515 if (dimension->class_evaluators_.size() != 1) {
2520 if (transit ==
nullptr)
continue;
2521 absl::flat_hash_map<int64_t, std::vector<int64_t>> nodes_by_positive_demand;
2522 absl::flat_hash_map<int64_t, std::vector<int64_t>> nodes_by_negative_demand;
2523 for (
int node : non_pickup_delivery_nodes) {
2524 const int64_t demand = transit(node);
2526 nodes_by_positive_demand[demand].push_back(node);
2527 }
else if (demand < 0) {
2528 nodes_by_negative_demand[-demand].push_back(node);
2531 for (
const auto& [demand, positive_nodes] : nodes_by_positive_demand) {
2532 const std::vector<int64_t>*
const negative_nodes =
2534 if (negative_nodes !=
nullptr) {
2535 for (int64_t positive_node : positive_nodes) {
2536 for (int64_t negative_node : *negative_nodes) {
2537 implicit_pickup_deliveries.insert({positive_node, negative_node});
2543 implicit_pickup_delivery_pairs_without_alternatives_.clear();
2544 for (
auto [pickup, delivery] : implicit_pickup_deliveries) {
2545 implicit_pickup_delivery_pairs_without_alternatives_.push_back(
2546 {{pickup}, {delivery}});
2552 if (!parameters.
has_time_limit())
return absl::InfiniteDuration();
2561 if (!error.empty()) {
2563 LOG(ERROR) <<
"Invalid RoutingSearchParameters: " << error;
2567 LOG(WARNING) <<
"Model already closed";
2573 GetOrCreateLimit()->UpdateLimits(
2574 GetTimeLimit(parameters), std::numeric_limits<int64_t>::max(),
2575 std::numeric_limits<int64_t>::max(), parameters.
solution_limit());
2578 dimension->CloseModel(UsesLightPropagation(parameters));
2581 dimension_resource_group_indices_.resize(dimensions_.size());
2582 for (
int rg_index = 0; rg_index < resource_groups_.size(); rg_index++) {
2583 const ResourceGroup& resource_group = *resource_groups_[rg_index];
2584 if (resource_group.GetVehiclesRequiringAResource().empty())
continue;
2586 resource_group.GetAffectedDimensionIndices()) {
2587 dimension_resource_group_indices_[dim_index].push_back(rg_index);
2593 FinalizeAllowedVehicles();
2594 ComputeCostClasses(parameters);
2595 ComputeVehicleClasses();
2596 ComputeVehicleTypes();
2597 ComputeResourceClasses();
2598 FinalizeVisitTypes();
2599 FinalizePrecedences();
2600 vehicle_start_class_callback_ = [
this](int64_t start) {
2601 return GetVehicleStartClass(start);
2604 AddNoCycleConstraintInternal();
2606 const int size =
Size();
2609 for (
int i = 0;
i < vehicles_; ++
i) {
2610 const int64_t start =
Start(i);
2611 const int64_t
end =
End(i);
2612 solver_->AddConstraint(
2613 solver_->MakeEquality(vehicle_vars_[start], solver_->MakeIntConst(i)));
2614 solver_->AddConstraint(
2615 solver_->MakeEquality(vehicle_vars_[
end], solver_->MakeIntConst(i)));
2616 solver_->AddConstraint(
2617 solver_->MakeIsDifferentCstCt(nexts_[start],
end, vehicle_active_[i]));
2618 if (vehicle_used_when_empty_[i]) {
2619 vehicle_route_considered_[
i]->SetMin(1);
2621 solver_->AddConstraint(solver_->MakeEquality(
2622 vehicle_active_[i], vehicle_route_considered_[i]));
2626 for (
int i = 0;
i < allowed_vehicles_.size(); ++
i) {
2627 const auto& allowed_vehicles = allowed_vehicles_[
i];
2628 if (!allowed_vehicles.empty()) {
2630 vehicles.reserve(allowed_vehicles.size() + 1);
2632 for (
int vehicle : allowed_vehicles) {
2640 if (vehicles_ > max_active_vehicles_) {
2641 solver_->AddConstraint(
2642 solver_->MakeSumLessOrEqual(vehicle_active_, max_active_vehicles_));
2645 solver_.get(), dimension->fixed_transits_, active_, vehicle_active_,
2646 dimension->vehicle_capacities_, max_active_vehicles_));
2655 if (vehicles_ > 1) {
2656 std::vector<IntVar*> zero_transit(size, solver_->MakeIntConst(0));
2657 solver_->AddConstraint(solver_->MakeDelayedPathCumul(
2658 nexts_, active_, vehicle_vars_, zero_transit));
2663 for (
int i = 0;
i < size; ++
i) {
2664 const std::vector<DisjunctionIndex>& disjunctions =
2666 bool is_mandatory = disjunctions.empty();
2670 is_mandatory =
true;
2674 if (is_mandatory && active_[i]->Max() != 0) {
2675 active_[
i]->SetValue(1);
2681 const absl::flat_hash_set<VisitTypePolicy>*
const infeasible_policies =
2683 if (infeasible_policies !=
nullptr &&
2684 infeasible_policies->contains(index_to_type_policy_[i])) {
2685 active_[
i]->SetValue(0);
2690 for (
int i = 0;
i < size; ++
i) {
2693 paths_metadata_.Starts()));
2695 solver_->AddConstraint(
2696 solver_->MakeIsDifferentCstCt(nexts_[i], i, active_[i]));
2701 for (
int i = 0;
i < size; ++
i) {
2702 solver_->AddConstraint(
2703 solver_->MakeIsDifferentCstCt(vehicle_vars_[i], -1, active_[i]));
2707 solver_->AddConstraint(
2708 solver_->RevAlloc(
new TypeRegulationsConstraint(*
this)));
2712 for (
int i = 0;
i < vehicles_; ++
i) {
2713 std::vector<int64_t> forbidden_ends;
2714 forbidden_ends.reserve(vehicles_ - 1);
2715 for (
int j = 0; j < vehicles_; ++j) {
2717 forbidden_ends.push_back(
End(j));
2721 solver_.get(), nexts_[
Start(i)], std::move(forbidden_ends)));
2725 for (
const int64_t
end : paths_metadata_.Ends()) {
2726 is_bound_to_end_[
end]->SetValue(1);
2730 std::vector<IntVar*> route_cost_vars;
2731 if (!route_evaluators_.empty()) {
2734 this, route_cost_vars,
2738 std::vector<IntVar*> cost_elements;
2740 if (vehicles_ > 0) {
2741 for (
int node_index = 0; node_index < size; ++node_index) {
2743 AppendHomogeneousArcCosts(parameters, node_index, &cost_elements);
2745 AppendArcCosts(parameters, node_index, &cost_elements);
2748 if (vehicle_amortized_cost_factors_set_) {
2749 std::vector<IntVar*> route_lengths;
2750 solver_->MakeIntVarArray(vehicles_, 0, size, &route_lengths);
2751 solver_->AddConstraint(
2752 solver_->MakeDistribute(vehicle_vars_, route_lengths));
2753 std::vector<IntVar*> vehicle_used;
2754 for (
int i = 0;
i < vehicles_;
i++) {
2756 vehicle_used.push_back(
2757 solver_->MakeIsGreaterCstVar(route_lengths[i], 2));
2760 ->MakeProd(solver_->MakeOpposite(solver_->MakeSquare(
2761 solver_->MakeSum(route_lengths[i], -2))),
2762 quadratic_cost_factor_of_vehicle_[i])
2764 cost_elements.push_back(var);
2766 IntVar*
const vehicle_usage_cost =
2767 solver_->MakeScalProd(vehicle_used, linear_cost_factor_of_vehicle_)
2769 cost_elements.push_back(vehicle_usage_cost);
2774 dimension->SetupGlobalSpanCost(&cost_elements);
2775 dimension->SetupSlackAndDependentTransitCosts();
2776 const std::vector<int64_t>& span_costs =
2777 dimension->vehicle_span_cost_coefficients();
2778 const std::vector<int64_t>& slack_costs =
2779 dimension->vehicle_slack_cost_coefficients();
2780 const std::vector<int64_t>& span_ubs =
2781 dimension->vehicle_span_upper_bounds();
2782 const bool has_span_constraint =
2783 std::any_of(span_costs.begin(), span_costs.end(),
2784 [](int64_t coeff) { return coeff != 0; }) ||
2785 std::any_of(slack_costs.begin(), slack_costs.end(),
2786 [](int64_t coeff) { return coeff != 0; }) ||
2787 std::any_of(span_ubs.begin(), span_ubs.end(),
2789 return value < std::numeric_limits<int64_t>::max();
2791 dimension->HasSoftSpanUpperBounds() ||
2792 dimension->HasQuadraticCostSoftSpanUpperBounds();
2793 if (has_span_constraint) {
2794 std::vector<IntVar*> spans(
vehicles(),
nullptr);
2795 std::vector<IntVar*> total_slacks(
vehicles(),
nullptr);
2797 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2798 if (span_ubs[vehicle] < std::numeric_limits<int64_t>::max()) {
2799 spans[vehicle] = solver_->MakeIntVar(0, span_ubs[vehicle],
"");
2801 if (span_costs[vehicle] != 0 || slack_costs[vehicle] != 0) {
2802 total_slacks[vehicle] = solver_->MakeIntVar(0, span_ubs[vehicle],
"");
2805 if (dimension->HasSoftSpanUpperBounds()) {
2806 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2807 if (spans[vehicle])
continue;
2808 const BoundCost bound_cost =
2809 dimension->GetSoftSpanUpperBoundForVehicle(vehicle);
2810 if (bound_cost.cost == 0)
continue;
2811 spans[vehicle] = solver_->MakeIntVar(0, span_ubs[vehicle]);
2814 if (dimension->HasQuadraticCostSoftSpanUpperBounds()) {
2815 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2816 if (spans[vehicle])
continue;
2817 const BoundCost bound_cost =
2818 dimension->GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);
2819 if (bound_cost.cost == 0)
continue;
2820 spans[vehicle] = solver_->MakeIntVar(0, span_ubs[vehicle]);
2823 solver_->AddConstraint(
2827 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2828 if (!spans[vehicle] && !total_slacks[vehicle])
continue;
2829 if (spans[vehicle]) {
2831 std::numeric_limits<int64_t>::min());
2834 std::numeric_limits<int64_t>::min());
2836 std::numeric_limits<int64_t>::max());
2839 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2840 if (span_costs[vehicle] == 0 && slack_costs[vehicle] == 0)
continue;
2841 DCHECK(total_slacks[vehicle] !=
nullptr);
2842 IntVar*
const slack_amount =
2844 ->MakeProd(vehicle_route_considered_[vehicle],
2845 total_slacks[vehicle])
2847 const int64_t slack_cost_coefficient =
2848 CapAdd(slack_costs[vehicle], span_costs[vehicle]);
2849 IntVar*
const slack_cost =
2850 solver_->MakeProd(slack_amount, slack_cost_coefficient)->Var();
2851 cost_elements.push_back(slack_cost);
2853 slack_cost_coefficient);
2855 if (dimension->HasSoftSpanUpperBounds()) {
2856 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2857 const auto bound_cost =
2858 dimension->GetSoftSpanUpperBoundForVehicle(vehicle);
2859 if (bound_cost.cost == 0 ||
2860 bound_cost.bound == std::numeric_limits<int64_t>::max())
2862 DCHECK(spans[vehicle] !=
nullptr);
2865 IntVar*
const span_violation_amount =
2868 vehicle_route_considered_[vehicle],
2870 solver_->MakeSum(spans[vehicle], -bound_cost.bound),
2873 IntVar*
const span_violation_cost =
2874 solver_->MakeProd(span_violation_amount, bound_cost.cost)->Var();
2875 cost_elements.push_back(span_violation_cost);
2880 if (dimension->HasQuadraticCostSoftSpanUpperBounds()) {
2881 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2882 const auto bound_cost =
2883 dimension->GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);
2884 if (bound_cost.cost == 0 ||
2885 bound_cost.bound == std::numeric_limits<int64_t>::max())
2887 DCHECK(spans[vehicle] !=
nullptr);
2890 IntExpr* max0 = solver_->MakeMax(
2891 solver_->MakeSum(spans[vehicle], -bound_cost.bound), 0);
2892 IntVar*
const squared_span_violation_amount =
2894 ->MakeProd(vehicle_route_considered_[vehicle],
2895 solver_->MakeSquare(max0))
2897 IntVar*
const span_violation_cost =
2898 solver_->MakeProd(squared_span_violation_amount, bound_cost.cost)
2900 cost_elements.push_back(span_violation_cost);
2909 IntVar* penalty_var = CreateDisjunction(i);
2910 if (penalty_var !=
nullptr) {
2911 cost_elements.push_back(penalty_var);
2916 dimension->SetupCumulVarSoftLowerBoundCosts(&cost_elements);
2917 dimension->SetupCumulVarSoftUpperBoundCosts(&cost_elements);
2918 dimension->SetupCumulVarPiecewiseLinearCosts(&cost_elements);
2921 for (
int i = 0;
i < same_vehicle_costs_.size(); ++
i) {
2922 cost_elements.push_back(CreateSameVehicleCost(i));
2925 for (
const auto& [force_distance, costs] : force_distance_to_energy_costs_) {
2926 std::vector<IntVar*> energy_costs(vehicles_,
nullptr);
2928 for (
int v = 0; v < vehicles_; ++v) {
2929 const int64_t cost_ub = costs[v].IsNull() ? 0 :
kint64max;
2930 energy_costs[v] = solver_->MakeIntVar(0, cost_ub);
2931 cost_elements.push_back(energy_costs[v]);
2933 energy_costs[v], std::max(costs[v].cost_per_unit_below_threshold,
2934 costs[v].cost_per_unit_above_threshold));
2939 DCHECK_NE(force_dimension,
nullptr);
2942 DCHECK_NE(distance_dimension,
nullptr);
2943 if (force_dimension ==
nullptr || distance_dimension ==
nullptr)
continue;
2945 Solver::PathEnergyCostConstraintSpecification specification{
2948 .forces = force_dimension->cumuls(),
2949 .distances = distance_dimension->transits(),
2950 .path_energy_costs = costs,
2951 .path_used_when_empty = vehicle_used_when_empty_,
2952 .path_starts = paths_metadata_.Starts(),
2953 .path_ends = paths_metadata_.Ends(),
2954 .costs = std::move(energy_costs),
2957 solver_->AddConstraint(
2958 solver_->MakePathEnergyCostConstraint(std::move(specification)));
2960 for (IntVar* route_cost_var : route_cost_vars) {
2961 cost_elements.push_back(route_cost_var);
2964 cost_ = solver_->MakeSum(cost_elements)->Var();
2965 cost_->set_name(
"Cost");
2968 std::vector<std::pair<int, int>> pickup_delivery_precedences;
2969 for (
const auto& [pickups, deliveries] : pickup_delivery_pairs_) {
2970 DCHECK(!pickups.empty() && !deliveries.empty());
2971 for (
int pickup : pickups) {
2972 for (
int delivery : deliveries) {
2973 pickup_delivery_precedences.emplace_back(pickup, delivery);
2977 std::vector<int> lifo_vehicles;
2978 std::vector<int> fifo_vehicles;
2979 for (
int i = 0;
i < vehicles_; ++
i) {
2980 switch (vehicle_pickup_delivery_policy_[i]) {
2984 lifo_vehicles.push_back(
Start(i));
2987 fifo_vehicles.push_back(
Start(i));
2991 solver_->AddConstraint(solver_->MakePathPrecedenceConstraint(
2992 nexts_, pickup_delivery_precedences, lifo_vehicles, fifo_vehicles));
2995 for (
const auto& disjunctions : ordered_activity_groups_) {
2996 if (disjunctions.size() <= 1)
continue;
2997 IntVar* prev_active_var =
nullptr;
2999 const std::vector<int64_t>& node_indices =
3001 std::vector<IntVar*> active_vars;
3002 active_vars.reserve(node_indices.size());
3003 for (
const int node : node_indices) {
3006 IntVar*
const sum = solver_->MakeSum(active_vars)->Var();
3007 IntVar* active_var = solver_->MakeBoolVar();
3008 solver_->AddConstraint(solver_->MakeIsGreaterOrEqualCstCt(
3010 if (prev_active_var !=
nullptr) {
3011 solver_->AddConstraint(
3012 solver_->MakeLessOrEqual(active_var, prev_active_var));
3014 prev_active_var = active_var;
3019 enable_deep_serialization_ =
false;
3020 std::unique_ptr<RoutingModelInspector> inspector(
3022 solver_->Accept(inspector.get());
3023 enable_deep_serialization_ =
true;
3028 const ReverseArcListGraph<int, int>& graph =
3029 dimension->GetPathPrecedenceGraph();
3030 std::vector<std::pair<int, int>> path_precedences;
3031 for (
const auto tail : graph.AllNodes()) {
3032 for (
const auto head : graph[tail]) {
3033 path_precedences.emplace_back(tail, head);
3036 if (!path_precedences.empty()) {
3037 solver_->AddConstraint(solver_->MakePathTransitPrecedenceConstraint(
3038 nexts_, dimension->transits(), path_precedences));
3042 for (
const auto [first_node, second_node, offset, performed_constraint] :
3043 dimension->GetNodePrecedences()) {
3044 IntExpr*
const nodes_are_selected =
3045 solver_->MakeMin(active_[first_node], active_[second_node]);
3046 IntExpr*
const cumul_difference = solver_->MakeDifference(
3047 dimension->CumulVar(second_node), dimension->CumulVar(first_node));
3048 IntVar*
const cumul_difference_is_ge_offset =
3049 solver_->MakeIsGreaterOrEqualCstVar(cumul_difference, offset);
3052 solver_->AddConstraint(solver_->MakeLessOrEqual(
3053 nodes_are_selected->Var(), cumul_difference_is_ge_offset));
3054 using PerformedConstraint =
3056 switch (performed_constraint) {
3057 case PerformedConstraint::kFirstAndSecondIndependent:
3059 case PerformedConstraint::kSecondImpliesFirst:
3060 solver_->AddConstraint(solver_->MakeGreaterOrEqual(
3061 active_[first_node], active_[second_node]));
3063 case PerformedConstraint::kFirstImpliesSecond:
3064 solver_->AddConstraint(solver_->MakeGreaterOrEqual(
3065 active_[second_node], active_[first_node]));
3067 case PerformedConstraint::kFirstAndSecondEqual:
3068 solver_->AddConstraint(
3069 solver_->MakeEquality(active_[first_node], active_[second_node]));
3074 if (!resource_groups_.empty()) {
3075 DCHECK_EQ(resource_vars_.size(), resource_groups_.size());
3076 for (
int rg = 0; rg < resource_groups_.size(); ++rg) {
3077 const auto& resource_group = resource_groups_[rg];
3078 const int max_resource_index = resource_group->Size() - 1;
3079 std::vector<IntVar*>& vehicle_res_vars = resource_vars_[rg];
3080 for (IntVar* res_var : vehicle_res_vars) {
3081 res_var->SetMax(max_resource_index);
3084 &vehicle_res_vars,
this));
3088 DetectImplicitPickupAndDeliveries();
3091 StoreDimensionCumulOptimizers(parameters);
3096 CreateNeighborhoodOperators(parameters);
3097 CreateFirstSolutionDecisionBuilders(parameters);
3098 monitors_before_setup_ = monitors_.size();
3101 monitors_after_setup_ = monitors_.size();
3102 SetupSearch(parameters);
3106 monitors_.push_back(monitor);
3107 secondary_ls_monitors_.push_back(monitor);
3111 std::function<
void()> callback) {
3113 if (restore_dimension_values_reset_callbacks_.empty()) {
3115 for (
const auto& callback : restore_dimension_values_reset_callbacks_) {
3120 restore_dimension_values_reset_callbacks_.push_back(std::move(callback));
3127 EnterSearchMonitor(Solver* solver, std::function<
void()> callback)
3128 : SearchMonitor(solver), callback_(std::move(callback)) {}
3129 void EnterSearch()
override { callback_(); }
3133 std::function<void()> callback_;
3138 AtSolutionCallbackMonitor(Solver* solver, std::function<
void()> callback,
3139 bool track_unchecked_neighbors)
3140 : SearchMonitor(solver),
3141 callback_(std::move(callback)),
3142 track_unchecked_neighbors_(track_unchecked_neighbors) {}
3143 bool AtSolution()
override {
3148 void Install()
override {
3150 if (track_unchecked_neighbors_) {
3156 std::function<void()> callback_;
3157 const bool track_unchecked_neighbors_;
3162 EnterSearchMonitor*
const monitor = solver_->RevAlloc(
3163 new EnterSearchMonitor(solver_.get(), std::move(callback)));
3168 bool track_unchecked_neighbors) {
3169 AtSolutionCallbackMonitor*
const monitor =
3170 solver_->RevAlloc(
new AtSolutionCallbackMonitor(
3171 solver_.get(), std::move(callback), track_unchecked_neighbors));
3172 at_solution_monitors_.push_back(monitor);
3182 const RoutingSearchParameters& parameters,
3183 std::vector<const Assignment*>* solutions) {
3189 if (!parameters.has_lns_time_limit())
return absl::InfiniteDuration();
3195void MakeAllUnperformedInAssignment(
const RoutingModel* model,
3197 assignment->Clear();
3198 for (
int i = 0;
i < model->Nexts().size(); ++
i) {
3199 if (!model->IsStart(i)) {
3200 assignment->Add(model->NextVar(i))->SetValue(i);
3203 for (
int vehicle = 0; vehicle < model->vehicles(); ++vehicle) {
3204 assignment->Add(model->NextVar(model->Start(vehicle)))
3205 ->SetValue(model->End(vehicle));
3211 bool call_at_solution_monitors) {
3212 tmp_assignment_->CopyIntersection(&assignment);
3213 std::vector<SearchMonitor*> monitors = call_at_solution_monitors
3214 ? at_solution_monitors_
3215 : std::vector<SearchMonitor*>();
3216 monitors.push_back(collect_one_assignment_);
3217 monitors.push_back(GetOrCreateLimit());
3218 solver_->Solve(restore_tmp_assignment_, monitors);
3219 return collect_one_assignment_->solution_count() == 1;
3222bool RoutingModel::AppendAssignmentIfFeasible(
3224 std::vector<std::unique_ptr<Assignment>>* assignments,
3225 bool call_at_solution_monitors) {
3227 assignments->push_back(std::make_unique<Assignment>(solver_.get()));
3228 assignments->back()->Copy(collect_one_assignment_->solution(0));
3235 absl::string_view description,
3236 int64_t solution_cost, int64_t start_time_ms) {
3238 const double cost_scaling_factor = parameters.log_cost_scaling_factor();
3239 const double cost_offset = parameters.log_cost_offset();
3240 const std::string cost_string =
3241 cost_scaling_factor == 1.0 && cost_offset == 0.0
3242 ? absl::StrCat(solution_cost)
3244 "%d (%.8lf)", solution_cost,
3245 cost_scaling_factor * (solution_cost + cost_offset));
3246 LOG(INFO) << absl::StrFormat(
3247 "%s (%s, time = %d ms, memory used = %s)", description, cost_string,
3248 solver_->wall_time() - start_time_ms, memory_str);
3253 std::vector<const Assignment*>* solutions) {
3261 absl::flat_hash_set<IntVar*>* touched) {
3266 LOG(DFATAL) <<
"local_search_metaheuristic value unsupported: "
3270 const int64_t start_time_ms = solver_->wall_time();
3271 QuietCloseModelWithParameters(search_parameters);
3272 UpdateSearchFromParametersIfNeeded(search_parameters);
3276 if (assignment ==
nullptr)
return nullptr;
3278 GetTimeLimit(search_parameters), std::numeric_limits<int64_t>::max(),
3279 std::numeric_limits<int64_t>::max(), search_parameters.
solution_limit());
3280 std::vector<SearchMonitor*> monitors = {metaheuristic_};
3281 if (search_log_ !=
nullptr) monitors.push_back(search_log_);
3284 GetOrCreateLocalSearchFilterManager(search_parameters,
3287 primary_ls_operator_, monitors, limit_, touched);
3288 const absl::Duration elapsed_time =
3289 absl::Milliseconds(solver_->wall_time() - start_time_ms);
3291 if (!check_solution_in_cp ||
3298 if (elapsed_time >= GetTimeLimit(search_parameters)) {
3308 const std::vector<const Assignment*>& assignments,
3310 std::vector<const Assignment*>* solutions) {
3311 const int64_t start_time_ms = solver_->wall_time();
3312 QuietCloseModelWithParameters(parameters);
3313 UpdateSearchFromParametersIfNeeded(parameters);
3314 if (solutions !=
nullptr) solutions->clear();
3321 if (!solver_->CheckConstraint(solver_->MakeTrueConstraint())) {
3326 const bool perform_secondary_ls =
3327 GetTimeLimit(parameters) != absl::InfiniteDuration() &&
3328 parameters.secondary_ls_time_limit_ratio() > 0;
3329 const auto update_time_limits =
3330 [
this, start_time_ms, perform_secondary_ls,
3331 ¶meters](
bool leave_secondary_solve_buffer =
true) {
3332 const absl::Duration elapsed_time =
3333 absl::Milliseconds(solver_->wall_time() - start_time_ms);
3334 const absl::Duration time_left =
3335 GetTimeLimit(parameters) - elapsed_time;
3337 if (time_left < absl::ZeroDuration())
return false;
3339 const absl::Duration secondary_solve_buffer =
3340 !leave_secondary_solve_buffer || !perform_secondary_ls
3341 ? absl::ZeroDuration()
3342 : parameters.secondary_ls_time_limit_ratio() * time_left;
3343 const absl::Duration time_limit = time_left - secondary_solve_buffer;
3344 limit_->UpdateLimits(time_limit, std::numeric_limits<int64_t>::max(),
3345 std::numeric_limits<int64_t>::max(),
3346 parameters.solution_limit());
3347 DCHECK_NE(ls_limit_,
nullptr);
3348 ls_limit_->UpdateLimits(time_limit, std::numeric_limits<int64_t>::max(),
3349 std::numeric_limits<int64_t>::max(), 1);
3352 time_buffer_ = std::min(absl::Seconds(1), time_limit * 0.05);
3355 if (!update_time_limits()) {
3359 lns_limit_->UpdateLimits(
3360 GetLnsTimeLimit(parameters), std::numeric_limits<int64_t>::max(),
3361 std::numeric_limits<int64_t>::max(), std::numeric_limits<int64_t>::max());
3367 const int time_limit_shares = 1 + !global_dimension_optimizers_.empty() +
3368 !local_dimension_optimizers_.empty();
3369 const absl::Duration first_solution_lns_time_limit =
3370 std::max(GetTimeLimit(parameters) / time_limit_shares,
3371 GetLnsTimeLimit(parameters));
3372 first_solution_lns_limit_->UpdateLimits(
3373 first_solution_lns_time_limit, std::numeric_limits<int64_t>::max(),
3374 std::numeric_limits<int64_t>::max(), std::numeric_limits<int64_t>::max());
3376 std::vector<std::unique_ptr<Assignment>> solution_pool;
3377 std::vector<const Assignment*> first_solution_assignments;
3378 for (
const Assignment* assignment : assignments) {
3379 if (assignment !=
nullptr) first_solution_assignments.push_back(assignment);
3381 local_optimum_reached_ =
false;
3384 const auto run_secondary_ls = [
this, perform_secondary_ls,
3385 &update_time_limits]() {
3386 if (collect_assignments_->has_solution() && perform_secondary_ls &&
3387 update_time_limits(
false)) {
3388 assignment_->CopyIntersection(
3389 collect_assignments_->last_solution_or_null());
3390 solver_->Solve(secondary_ls_db_, secondary_ls_monitors_);
3393 if (first_solution_assignments.empty()) {
3394 bool solution_found =
false;
3396 Assignment matching(solver_.get());
3398 if (SolveMatchingModel(&matching, parameters) &&
3399 update_time_limits(
false) &&
3400 AppendAssignmentIfFeasible(matching, &solution_pool)) {
3401 if (parameters.log_search()) {
3402 LogSolution(parameters,
"Min-Cost Flow Solution",
3403 solution_pool.back()->ObjectiveValue(), start_time_ms);
3405 solution_found =
true;
3406 local_optimum_reached_ =
true;
3409 if (!solution_found) {
3412 Assignment unperformed(solver_.get());
3413 MakeAllUnperformedInAssignment(
this, &unperformed);
3414 if (update_time_limits(
false) &&
3415 AppendAssignmentIfFeasible(unperformed, &solution_pool,
false) &&
3416 parameters.log_search()) {
3417 LogSolution(parameters,
"All Unperformed Solution",
3418 solution_pool.back()->ObjectiveValue(), start_time_ms);
3420 local_optimum_reached_ =
false;
3421 if (update_time_limits()) {
3422 solver_->Solve(solve_db_, monitors_);
3427 for (
const Assignment* assignment : first_solution_assignments) {
3428 assignment_->CopyIntersection(assignment);
3429 solver_->Solve(improve_db_, monitors_);
3431 if (collect_assignments_->solution_count() >= 1 ||
3432 !update_time_limits()) {
3436 if (collect_assignments_->solution_count() == 0 && update_time_limits() &&
3438 solver_->Solve(solve_db_, monitors_);
3444 const SolutionCollector*
const solution_collector =
3445 collect_secondary_ls_assignments_->has_solution()
3446 ? collect_secondary_ls_assignments_
3447 : collect_assignments_;
3449 if (update_time_limits(
false) &&
3450 (parameters.use_cp_sat() ==
BOOL_TRUE ||
3451 parameters.use_generalized_cp_sat() ==
BOOL_TRUE ||
3452 (parameters.fallback_to_cp_sat_size_threshold() >=
Size() &&
3453 !solution_collector->has_solution() && solution_pool.empty()))) {
3454 VLOG(1) <<
"Solving with CP-SAT";
3455 Assignment*
const cp_solution = solution_collector->last_solution_or_null();
3456 Assignment sat_solution(solver_.get());
3459 update_time_limits(
false) &&
3460 AppendAssignmentIfFeasible(sat_solution, &solution_pool)) {
3461 if (parameters.log_search()) {
3462 LogSolution(parameters,
"SAT", solution_pool.back()->ObjectiveValue(),
3465 local_optimum_reached_ =
true;
3466 if (sat_solution.HasObjective()) {
3467 objective_lower_bound_ =
3468 std::max(objective_lower_bound_, sat_solution.ObjectiveValue());
3472 VLOG(1) <<
"Objective lower bound: " << objective_lower_bound_;
3473 const absl::Duration elapsed_time =
3474 absl::Milliseconds(solver_->wall_time() - start_time_ms);
3476 if (solution_collector->has_solution() || !solution_pool.empty()) {
3477 status_ = local_optimum_reached_
3479 : RoutingSearchStatus::
3480 ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED;
3481 if (solutions !=
nullptr) {
3482 std::vector<Assignment*> temp_solutions;
3483 for (
int i = 0;
i < solution_collector->solution_count(); ++
i) {
3484 temp_solutions.push_back(
3485 solver_->MakeAssignment(solution_collector->solution(i)));
3487 for (
const auto&
solution : solution_pool) {
3488 if (temp_solutions.empty() ||
3490 temp_solutions.back()->ObjectiveValue()) {
3491 temp_solutions.push_back(solver_->MakeAssignment(
solution.get()));
3496 DCHECK(!temp_solutions.empty());
3497 const int64_t min_objective_value =
3498 temp_solutions.back()->ObjectiveValue();
3500 if (temp_solutions.size() < parameters.number_of_solutions_to_collect() &&
3501 solution_collector != collect_assignments_ &&
3502 collect_assignments_->has_solution()) {
3506 DCHECK_EQ(*collect_assignments_->last_solution_or_null(),
3507 *temp_solutions[0]);
3509 const size_t num_solutions = collect_assignments_->solution_count();
3510 const int num_solutions_to_add = std::min(
3511 parameters.number_of_solutions_to_collect() - solutions->size(),
3513 for (
int i = num_solutions_to_add;
i > 0; --
i) {
3514 solutions->push_back(solver_->MakeAssignment(
3515 collect_assignments_->solution(num_solutions - 1 - i)));
3516 DCHECK_GE(solutions->back()->ObjectiveValue(), min_objective_value);
3521 solutions->insert(solutions->end(), temp_solutions.begin(),
3522 temp_solutions.end());
3523 if (min_objective_value <= objective_lower_bound_) {
3526 return solutions->back();
3528 Assignment* best_assignment = solution_collector->last_solution_or_null();
3529 for (
const auto&
solution : solution_pool) {
3530 if (best_assignment ==
nullptr ||
3531 solution->ObjectiveValue() < best_assignment->ObjectiveValue()) {
3535 if (best_assignment->ObjectiveValue() <= objective_lower_bound_) {
3538 return solver_->MakeAssignment(best_assignment);
3540 if (elapsed_time >= GetTimeLimit(parameters)) {
3551 DCHECK(parameters.use_iterated_local_search());
3557 const int64_t start_time_ms = solver_->wall_time();
3558 QuietCloseModelWithParameters(parameters);
3559 UpdateSearchFromParametersIfNeeded(parameters);
3565 solver_->Solve(solve_db_, monitors_);
3566 int64_t explored_solutions = solver_->solutions();
3568 Assignment* best_solution = collect_assignments_->last_solution_or_null();
3569 if (!best_solution) {
3574 Assignment* last_accepted_solution = solver_->MakeAssignment(best_solution);
3576 LocalSearchFilterManager* filter_manager =
3577 GetOrCreateLocalSearchFilterManager(parameters,
3581 std::mt19937 rnd(0);
3584 parameters,
this, &rnd, last_accepted_solution,
3585 [
this]() {
return CheckLimit(time_buffer_); }, filter_manager);
3589 const auto update_time_limits = [
this, start_time_ms, ¶meters]() {
3590 const absl::Duration elapsed_time =
3591 absl::Milliseconds(solver_->wall_time() - start_time_ms);
3592 const absl::Duration time_left = GetTimeLimit(parameters) - elapsed_time;
3593 if (time_left < absl::ZeroDuration()) {
3596 limit_->UpdateLimits(time_left, std::numeric_limits<int64_t>::max(),
3597 std::numeric_limits<int64_t>::max(),
3598 parameters.solution_limit());
3599 DCHECK_NE(ls_limit_,
nullptr);
3600 ls_limit_->UpdateLimits(time_left, std::numeric_limits<int64_t>::max(),
3601 std::numeric_limits<int64_t>::max(), 1);
3604 time_buffer_ = std::min(absl::Seconds(1), time_left * 0.05);
3608 const IteratedLocalSearchParameters& ils_parameters =
3609 parameters.iterated_local_search_parameters();
3611 const absl::Duration final_duration =
3612 !parameters.has_time_limit()
3613 ? absl::InfiniteDuration()
3616 NeighborAcceptanceCriterion::SearchState final_search_state = {
3617 final_duration, parameters.solution_limit()};
3619 std::unique_ptr<NeighborAcceptanceCriterion> reference_acceptance_criterion =
3621 *
this, ils_parameters.reference_solution_acceptance_strategy(),
3622 final_search_state, &rnd);
3624 std::unique_ptr<NeighborAcceptanceCriterion> best_acceptance_criterion =
3626 *
this, ils_parameters.best_solution_acceptance_strategy(),
3627 final_search_state, &rnd);
3629 const bool improve_perturbed_solution =
3630 ils_parameters.improve_perturbed_solution();
3632 while (update_time_limits() &&
3633 explored_solutions < parameters.solution_limit()) {
3634 solver_->Solve(perturbation_db, monitors_);
3635 explored_solutions += solver_->solutions();
3637 Assignment* neighbor_solution =
3638 collect_assignments_->last_solution_or_null();
3639 if (!neighbor_solution) {
3643 if (improve_perturbed_solution && update_time_limits()) {
3644 assignment_->CopyIntersection(neighbor_solution);
3646 solver_->Solve(improve_db_, monitors_);
3647 explored_solutions += solver_->solutions();
3649 neighbor_solution = collect_assignments_->last_solution_or_null();
3650 if (!neighbor_solution) {
3655 absl::Duration elapsed_time =
3656 absl::Milliseconds(solver_->wall_time() - start_time_ms);
3658 if (best_acceptance_criterion->Accept({elapsed_time, explored_solutions},
3659 neighbor_solution, best_solution)) {
3660 best_solution->CopyIntersection(neighbor_solution);
3663 if (reference_acceptance_criterion->Accept(
3664 {elapsed_time, explored_solutions}, neighbor_solution,
3665 last_accepted_solution)) {
3669 last_accepted_solution->CopyIntersection(neighbor_solution);
3673 return best_solution;
3679 const int size =
Size();
3680 DCHECK_EQ(size, source_model->Size());
3681 CHECK_EQ(target_assignment->solver(), solver_.get());
3685 source_model->Nexts());
3687 std::vector<IntVar*> source_vars(size + size + vehicles_);
3688 std::vector<IntVar*> target_vars(size + size + vehicles_);
3689 for (
int index = 0; index < size; index++) {
3690 source_vars[index] = source_model->NextVar(index);
3691 target_vars[index] =
NextVar(index);
3693 for (
int index = 0; index < size + vehicles_; index++) {
3694 source_vars[size + index] = source_model->VehicleVar(index);
3695 target_vars[size + index] =
VehicleVar(index);
3698 source_assignment, source_vars);
3701 target_assignment->AddObjective(cost_);
3705 SubSolverStatistics stats;
3708 stats.set_num_cp_sat_calls_in_lp_scheduling(
3726 LOG(WARNING) <<
"Non-closed model not supported.";
3730 LOG(WARNING) <<
"Non-homogeneous vehicle costs not supported";
3733 if (!disjunctions_.empty()) {
3735 <<
"Node disjunction constraints or optional nodes not supported.";
3738 const int num_nodes =
Size() + vehicles_;
3739 Graph graph(2 * num_nodes, num_nodes * num_nodes);
3744 for (
int tail = 0; tail <
Size(); ++tail) {
3745 std::unique_ptr<IntVarIterator> iterator(
3746 nexts_[tail]->MakeDomainIterator(
false));
3756 const GraphArcIndex arc = graph.
AddArc(tail, num_nodes + head);
3764 for (
int tail =
Size(); tail < num_nodes; ++tail) {
3765 const GraphArcIndex arc =
3770 return linear_sum_assignment.
GetCost();
3775bool RoutingModel::RouteCanBeUsedByVehicle(
const Assignment& assignment,
3776 int start_index,
int vehicle)
const {
3778 IsStart(start_index) ?
Next(assignment, start_index) : start_index;
3779 while (!
IsEnd(current_index)) {
3781 if (!vehicle_var->
Contains(vehicle)) {
3784 const int next_index =
Next(assignment, current_index);
3785 CHECK_NE(next_index, current_index) <<
"Inactive node inside a route";
3786 current_index = next_index;
3791bool RoutingModel::ReplaceUnusedVehicle(
3792 int unused_vehicle,
int active_vehicle,
3793 Assignment*
const compact_assignment)
const {
3794 CHECK(compact_assignment !=
nullptr);
3798 const int unused_vehicle_start =
Start(unused_vehicle);
3799 IntVar*
const unused_vehicle_start_var =
NextVar(unused_vehicle_start);
3800 const int unused_vehicle_end =
End(unused_vehicle);
3801 const int active_vehicle_start =
Start(active_vehicle);
3802 const int active_vehicle_end =
End(active_vehicle);
3803 IntVar*
const active_vehicle_start_var =
NextVar(active_vehicle_start);
3804 const int active_vehicle_next =
3805 compact_assignment->Value(active_vehicle_start_var);
3806 compact_assignment->SetValue(unused_vehicle_start_var, active_vehicle_next);
3807 compact_assignment->SetValue(active_vehicle_start_var,
End(active_vehicle));
3810 int current_index = active_vehicle_next;
3811 while (!
IsEnd(current_index)) {
3812 IntVar*
const vehicle_var =
VehicleVar(current_index);
3813 compact_assignment->SetValue(vehicle_var, unused_vehicle);
3814 const int next_index =
Next(*compact_assignment, current_index);
3815 if (
IsEnd(next_index)) {
3816 IntVar*
const last_next_var =
NextVar(current_index);
3817 compact_assignment->SetValue(last_next_var,
End(unused_vehicle));
3819 current_index = next_index;
3824 const std::vector<IntVar*>& transit_variables = dimension->transits();
3825 IntVar*
const unused_vehicle_transit_var =
3826 transit_variables[unused_vehicle_start];
3827 IntVar*
const active_vehicle_transit_var =
3828 transit_variables[active_vehicle_start];
3829 const bool contains_unused_vehicle_transit_var =
3830 compact_assignment->Contains(unused_vehicle_transit_var);
3831 const bool contains_active_vehicle_transit_var =
3832 compact_assignment->Contains(active_vehicle_transit_var);
3833 if (contains_unused_vehicle_transit_var !=
3834 contains_active_vehicle_transit_var) {
3836 LOG(INFO) <<
"The assignment contains transit variable for dimension '"
3837 << dimension->name() <<
"' for some vehicles, but not for all";
3840 if (contains_unused_vehicle_transit_var) {
3841 const int64_t old_unused_vehicle_transit =
3842 compact_assignment->Value(unused_vehicle_transit_var);
3843 const int64_t old_active_vehicle_transit =
3844 compact_assignment->Value(active_vehicle_transit_var);
3845 compact_assignment->SetValue(unused_vehicle_transit_var,
3846 old_active_vehicle_transit);
3847 compact_assignment->SetValue(active_vehicle_transit_var,
3848 old_unused_vehicle_transit);
3852 const std::vector<IntVar*>& cumul_variables = dimension->cumuls();
3853 IntVar*
const unused_vehicle_cumul_var =
3854 cumul_variables[unused_vehicle_end];
3855 IntVar*
const active_vehicle_cumul_var =
3856 cumul_variables[active_vehicle_end];
3857 const int64_t old_unused_vehicle_cumul =
3858 compact_assignment->Value(unused_vehicle_cumul_var);
3859 const int64_t old_active_vehicle_cumul =
3860 compact_assignment->Value(active_vehicle_cumul_var);
3861 compact_assignment->SetValue(unused_vehicle_cumul_var,
3862 old_active_vehicle_cumul);
3863 compact_assignment->SetValue(active_vehicle_cumul_var,
3864 old_unused_vehicle_cumul);
3871 return CompactAssignmentInternal(assignment,
false);
3875 const Assignment& assignment)
const {
3876 return CompactAssignmentInternal(assignment,
true);
3879Assignment* RoutingModel::CompactAssignmentInternal(
3880 const Assignment& assignment,
bool check_compact_assignment)
const {
3881 CHECK_EQ(assignment.solver(), solver_.get());
3884 <<
"The costs are not homogeneous, routes cannot be rearranged";
3888 std::unique_ptr<Assignment> compact_assignment(
new Assignment(&assignment));
3889 for (
int vehicle = 0; vehicle < vehicles_ - 1; ++vehicle) {
3893 const int vehicle_start =
Start(vehicle);
3894 const int vehicle_end =
End(vehicle);
3896 int swap_vehicle = vehicles_ - 1;
3897 bool has_more_vehicles_with_route =
false;
3898 for (; swap_vehicle > vehicle; --swap_vehicle) {
3905 has_more_vehicles_with_route =
true;
3906 const int swap_vehicle_start =
Start(swap_vehicle);
3907 const int swap_vehicle_end =
End(swap_vehicle);
3908 if (manager_.IndexToNode(vehicle_start) !=
3909 manager_.IndexToNode(swap_vehicle_start) ||
3910 manager_.IndexToNode(vehicle_end) !=
3911 manager_.IndexToNode(swap_vehicle_end)) {
3916 if (RouteCanBeUsedByVehicle(*compact_assignment, swap_vehicle_start,
3922 if (swap_vehicle == vehicle) {
3923 if (has_more_vehicles_with_route) {
3927 LOG(INFO) <<
"No vehicle that can be swapped with " << vehicle
3934 if (!ReplaceUnusedVehicle(vehicle, swap_vehicle,
3935 compact_assignment.get())) {
3940 if (check_compact_assignment &&
3941 !solver_->CheckAssignment(compact_assignment.get())) {
3943 LOG(WARNING) <<
"The compacted assignment is not a valid solution";
3946 return compact_assignment.release();
3949int RoutingModel::FindNextActive(
int index,
3950 absl::Span<const int64_t> indices)
const {
3953 const int size = indices.size();
3954 while (index < size &&
ActiveVar(indices[index])->Max() == 0) {
3963 CHECK_EQ(vehicles_, 1);
3964 preassignment_->
Clear();
3965 IntVar* next_var =
nullptr;
3966 int lock_index = FindNextActive(-1, locks);
3967 const int size = locks.size();
3968 if (lock_index < size) {
3969 next_var =
NextVar(locks[lock_index]);
3970 preassignment_->
Add(next_var);
3971 for (lock_index = FindNextActive(lock_index, locks); lock_index < size;
3972 lock_index = FindNextActive(lock_index, locks)) {
3973 preassignment_->
SetValue(next_var, locks[lock_index]);
3975 preassignment_->Add(next_var);
3982 const std::vector<std::vector<int64_t>>& locks,
bool close_routes) {
3983 preassignment_->Clear();
3990 GetFilteredFirstSolutionDecisionBuilderOrNull(parameters);
3998 GetFilteredFirstSolutionDecisionBuilderOrNull(parameters);
4004 if (collect_assignments_->
solution_count() == 1 && assignment_ !=
nullptr) {
4005 assignment_->CopyIntersection(collect_assignments_->solution(0));
4006 return assignment_->Save(file_name);
4014 CHECK(assignment_ !=
nullptr);
4015 if (assignment_->Load(file_name)) {
4016 return DoRestoreAssignment();
4023 CHECK(assignment_ !=
nullptr);
4025 return DoRestoreAssignment();
4028Assignment* RoutingModel::DoRestoreAssignment() {
4032 solver_->Solve(restore_assignment_, monitors_);
4033 if (collect_assignments_->solution_count() == 1) {
4035 return collect_assignments_->solution(0);
4044 const std::vector<std::vector<int64_t>>& routes,
4045 bool ignore_inactive_indices,
bool close_routes,
4047 CHECK(assignment !=
nullptr);
4049 LOG(ERROR) <<
"The model is not closed yet";
4052 const int num_routes = routes.size();
4053 if (num_routes > vehicles_) {
4054 LOG(ERROR) <<
"The number of vehicles in the assignment (" << routes.size()
4055 <<
") is greater than the number of vehicles in the model ("
4056 << vehicles_ <<
")";
4060 absl::flat_hash_set<int> visited_indices;
4062 for (
int vehicle = 0; vehicle < num_routes; ++vehicle) {
4063 const std::vector<int64_t>& route = routes[vehicle];
4064 int from_index =
Start(vehicle);
4065 std::pair<absl::flat_hash_set<int>::iterator,
bool> insert_result =
4066 visited_indices.insert(from_index);
4067 if (!insert_result.second) {
4068 LOG(ERROR) <<
"Index " << from_index <<
" (start node for vehicle "
4069 << vehicle <<
") was already used";
4073 for (
const int64_t to_index : route) {
4074 if (to_index < 0 || to_index >=
Size()) {
4075 LOG(ERROR) <<
"Invalid index: " << to_index;
4079 IntVar*
const active_var =
ActiveVar(to_index);
4080 if (active_var->Max() == 0) {
4081 if (ignore_inactive_indices) {
4084 LOG(ERROR) <<
"Index " << to_index <<
" is not active";
4089 insert_result = visited_indices.insert(to_index);
4090 if (!insert_result.second) {
4091 LOG(ERROR) <<
"Index " << to_index <<
" is used multiple times";
4095 const IntVar*
const vehicle_var =
VehicleVar(to_index);
4096 if (!vehicle_var->Contains(vehicle)) {
4097 LOG(ERROR) <<
"Vehicle " << vehicle <<
" is not allowed at index "
4102 IntVar*
const from_var =
NextVar(from_index);
4103 if (!assignment->Contains(from_var)) {
4104 assignment->Add(from_var);
4106 assignment->SetValue(from_var, to_index);
4108 from_index = to_index;
4112 IntVar*
const last_var =
NextVar(from_index);
4113 if (!assignment->Contains(last_var)) {
4114 assignment->Add(last_var);
4116 assignment->SetValue(last_var,
End(vehicle));
4121 for (
int vehicle = num_routes; vehicle < vehicles_; ++vehicle) {
4122 const int start_index =
Start(vehicle);
4125 std::pair<absl::flat_hash_set<int>::iterator,
bool> insert_result =
4126 visited_indices.insert(start_index);
4127 if (!insert_result.second) {
4128 LOG(ERROR) <<
"Index " << start_index <<
" is used multiple times";
4132 IntVar*
const start_var =
NextVar(start_index);
4133 if (!assignment->Contains(start_var)) {
4134 assignment->Add(start_var);
4136 assignment->SetValue(start_var,
End(vehicle));
4142 for (
int index = 0; index <
Size(); ++index) {
4143 if (!visited_indices.contains(index)) {
4144 IntVar*
const next_var =
NextVar(index);
4145 if (!assignment->Contains(next_var)) {
4146 assignment->Add(next_var);
4148 assignment->SetValue(next_var, index);
4157 const std::vector<std::vector<int64_t>>& routes,
4158 bool ignore_inactive_indices) {
4166 return DoRestoreAssignment();
4170 const Assignment& assignment,
4171 std::vector<std::vector<int64_t>>*
const routes)
const {
4173 CHECK(routes !=
nullptr);
4175 const int model_size =
Size();
4176 routes->resize(vehicles_);
4177 for (
int vehicle = 0; vehicle < vehicles_; ++vehicle) {
4178 std::vector<int64_t>*
const vehicle_route = &routes->at(vehicle);
4179 vehicle_route->clear();
4181 int num_visited_indices = 0;
4182 const int first_index =
Start(vehicle);
4183 const IntVar*
const first_var =
NextVar(first_index);
4184 CHECK(assignment.Contains(first_var));
4185 CHECK(assignment.Bound(first_var));
4186 int current_index = assignment.Value(first_var);
4187 while (!
IsEnd(current_index)) {
4188 vehicle_route->push_back(current_index);
4190 const IntVar*
const next_var =
NextVar(current_index);
4191 CHECK(assignment.Contains(next_var));
4192 CHECK(assignment.Bound(next_var));
4193 current_index = assignment.Value(next_var);
4195 ++num_visited_indices;
4196 CHECK_LE(num_visited_indices, model_size)
4197 <<
"The assignment contains a cycle";
4205 std::vector<std::vector<int64_t>> route_indices(
vehicles());
4206 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
4207 if (!assignment.Bound(
NextVar(vehicle))) {
4208 LOG(DFATAL) <<
"GetRoutesFromAssignment() called on incomplete solution:"
4209 <<
" NextVar(" << vehicle <<
") is unbound.";
4212 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
4213 int64_t index =
Start(vehicle);
4214 route_indices[vehicle].push_back(index);
4215 while (!
IsEnd(index)) {
4216 index = assignment.Value(
NextVar(index));
4217 route_indices[vehicle].push_back(index);
4220 return route_indices;
4224int64_t RoutingModel::GetArcCostForClassInternal(
4225 int64_t from_index, int64_t to_index,
4226 CostClassIndex cost_class_index)
const {
4228 DCHECK_GE(cost_class_index, 0);
4229 DCHECK_LT(cost_class_index, cost_classes_.size());
4230 CostCacheElement*
const cache = &cost_cache_[from_index];
4232 if (cache->index ==
static_cast<int>(to_index) &&
4233 cache->cost_class_index == cost_class_index) {
4237 const CostClass& cost_class = cost_classes_[cost_class_index];
4238 const auto& evaluator = transit_evaluators_[cost_class.evaluator_index];
4240 cost =
CapAdd(evaluator(from_index, to_index),
4241 GetDimensionTransitCostSum(from_index, to_index, cost_class));
4242 }
else if (!
IsEnd(to_index)) {
4246 evaluator(from_index, to_index),
4247 CapAdd(GetDimensionTransitCostSum(from_index, to_index, cost_class),
4252 if (vehicle_used_when_empty_[
VehicleIndex(from_index)]) {
4254 CapAdd(evaluator(from_index, to_index),
4255 GetDimensionTransitCostSum(from_index, to_index, cost_class));
4260 *cache = {
static_cast<int>(to_index), cost_class_index, cost};
4264std::function<int64_t(int64_t, int64_t, int64_t)>
4265RoutingModel::GetLocalSearchArcCostCallback(
4268 .use_guided_local_search_penalties_in_local_search_operators()
4270 &RoutingModel::GetArcCostWithGuidedLocalSearchPenalties,
4275std::function<int64_t(int64_t, int64_t)>
4276RoutingModel::GetLocalSearchHomogeneousArcCostCallback(
4279 .use_guided_local_search_penalties_in_local_search_operators()
4282 GetHomogeneousArcCostWithGuidedLocalSearchPenalties,
4288 int vehicle)
const {
4289 CHECK_GE(vehicle, 0);
4290 CHECK_LT(vehicle, vehicles_);
4291 CHECK_EQ(solver_.get(), assignment.
solver());
4293 CHECK(assignment.
Contains(start_var));
4298 CHECK_EQ(solver_.get(), assignment.
solver());
4300 CHECK(assignment.
Contains(next_var));
4301 CHECK(assignment.
Bound(next_var));
4302 return assignment.
Value(next_var);
4306 int64_t vehicle)
const {
4307 if (from_index != to_index && vehicle >= 0) {
4308 return GetArcCostForClassInternal(from_index, to_index,
4316 int64_t from_index, int64_t to_index,
4317 int64_t cost_class_index)
const {
4318 if (from_index != to_index) {
4319 return GetArcCostForClassInternal(from_index, to_index,
4327 int64_t to_index)
const {
4331 if (!is_bound_to_end_ct_added_.Switched()) {
4334 std::vector<IntVar*> zero_transit(
Size(), solver_->MakeIntConst(0));
4335 solver_->AddConstraint(solver_->MakeDelayedPathCumul(
4336 nexts_, active_, is_bound_to_end_, zero_transit));
4337 is_bound_to_end_ct_added_.Switch(solver_.get());
4339 if (is_bound_to_end_[to_index]->Min() == 1)
4340 return std::numeric_limits<int64_t>::max();
4345int64_t RoutingModel::GetDimensionTransitCostSum(
4346 int64_t i, int64_t j,
const CostClass& cost_class)
const {
4348 for ([[maybe_unused]]
const auto [transit_evaluator_class,
4349 span_cost_coefficient,
4350 unused_slack_cost_coefficient, dimension] :
4351 cost_class.dimension_transit_evaluator_class_and_cost_coefficient) {
4352 DCHECK_GE(span_cost_coefficient, 0);
4353 if (span_cost_coefficient == 0)
continue;
4355 i, j, transit_evaluator_class)),
4372 const bool mandatory1 = active_[to1]->Min() == 1;
4373 const bool mandatory2 = active_[to2]->Min() == 1;
4375 if (mandatory1 != mandatory2)
return mandatory1;
4378 IntVar*
const src_vehicle_var =
VehicleVar(from);
4382 const int64_t src_vehicle = src_vehicle_var->Max();
4383 if (src_vehicle_var->Bound()) {
4384 IntVar*
const to1_vehicle_var =
VehicleVar(to1);
4385 IntVar*
const to2_vehicle_var =
VehicleVar(to2);
4390 mandatory1 ? to1_vehicle_var->Bound() : (to1_vehicle_var->Size() <= 2);
4392 mandatory2 ? to2_vehicle_var->Bound() : (to2_vehicle_var->Size() <= 2);
4395 if (bound1 != bound2)
return bound1;
4398 const int64_t vehicle1 = to1_vehicle_var->Max();
4399 const int64_t vehicle2 = to2_vehicle_var->Max();
4402 if ((vehicle1 == src_vehicle) != (vehicle2 == src_vehicle)) {
4403 return vehicle1 == src_vehicle;
4408 if (vehicle1 != src_vehicle)
return to1 < to2;
4419 const std::vector<IntVar*>& cumul_vars =
4421 IntVar*
const dim1 = cumul_vars[to1];
4422 IntVar*
const dim2 = cumul_vars[to2];
4425 if (dim1->Max() != dim2->Max())
return dim1->Max() < dim2->Max();
4434 const int64_t cost_class_index =
4435 SafeGetCostClassInt64OfVehicle(src_vehicle);
4436 const int64_t cost1 =
4439 const int64_t cost2 =
4442 if (cost1 != cost2)
return cost1 < cost2;
4449 if (num_vehicles1 != num_vehicles2)
return num_vehicles1 < num_vehicles2;
4457 VisitTypePolicy policy) {
4458 CHECK_LT(index, index_to_visit_type_.size());
4459 DCHECK_EQ(index_to_visit_type_.size(), index_to_type_policy_.size());
4460 index_to_visit_type_[index] = type;
4461 index_to_type_policy_[index] = policy;
4462 num_visit_types_ = std::max(num_visit_types_, type + 1);
4466 CHECK_LT(index, index_to_visit_type_.size());
4467 return index_to_visit_type_[index];
4471 DCHECK_LT(type, single_nodes_of_type_.size());
4472 return single_nodes_of_type_[type];
4476 DCHECK_LT(type, pair_indices_of_type_.size());
4477 return pair_indices_of_type_[type];
4481 int64_t index)
const {
4482 CHECK_LT(index, index_to_type_policy_.size());
4483 return index_to_type_policy_[index];
4487 DCHECK_LT(std::max(type1, type2), num_visit_types_);
4488 if (hard_incompatible_types_per_type_index_.size() < num_visit_types_) {
4489 hard_incompatible_types_per_type_index_.resize(num_visit_types_);
4492 hard_incompatible_types_per_type_index_[type1].insert(type2);
4493 hard_incompatible_types_per_type_index_[type2].insert(type1);
4497 DCHECK_LT(std::max(type1, type2), num_visit_types_);
4498 if (temporal_incompatible_types_per_type_index_.size() < num_visit_types_) {
4499 temporal_incompatible_types_per_type_index_.resize(num_visit_types_);
4502 temporal_incompatible_types_per_type_index_[type1].insert(type2);
4503 temporal_incompatible_types_per_type_index_[type2].insert(type1);
4506const absl::flat_hash_set<int>&
4510 DCHECK_LT(type, num_visit_types_);
4511 return type < hard_incompatible_types_per_type_index_.size()
4512 ? hard_incompatible_types_per_type_index_[type]
4513 : empty_incompatibility_set_;
4516const absl::flat_hash_set<int>&
4520 DCHECK_LT(type, num_visit_types_);
4521 return type < temporal_incompatible_types_per_type_index_.size()
4522 ? temporal_incompatible_types_per_type_index_[type]
4523 : empty_incompatibility_set_;
4529 int dependent_type, absl::flat_hash_set<int> required_type_alternatives) {
4530 DCHECK_LT(dependent_type, num_visit_types_);
4532 if (required_type_alternatives.empty()) {
4536 absl::flat_hash_set<VisitTypePolicy>& infeasible_policies =
4537 trivially_infeasible_visit_types_to_policies_[dependent_type];
4544 if (same_vehicle_required_type_alternatives_per_type_index_.size() <
4546 same_vehicle_required_type_alternatives_per_type_index_.resize(
4549 same_vehicle_required_type_alternatives_per_type_index_[dependent_type]
4550 .push_back(std::move(required_type_alternatives));
4554 int dependent_type, absl::flat_hash_set<int> required_type_alternatives) {
4555 DCHECK_LT(dependent_type, num_visit_types_);
4557 if (required_type_alternatives.empty()) {
4561 absl::flat_hash_set<VisitTypePolicy>& infeasible_policies =
4562 trivially_infeasible_visit_types_to_policies_[dependent_type];
4568 if (required_type_alternatives_when_adding_type_index_.size() <
4570 required_type_alternatives_when_adding_type_index_.resize(num_visit_types_);
4572 required_type_alternatives_when_adding_type_index_[dependent_type].push_back(
4573 std::move(required_type_alternatives));
4577 int dependent_type, absl::flat_hash_set<int> required_type_alternatives) {
4578 DCHECK_LT(dependent_type, num_visit_types_);
4580 if (required_type_alternatives.empty()) {
4584 absl::flat_hash_set<VisitTypePolicy>& infeasible_policies =
4585 trivially_infeasible_visit_types_to_policies_[dependent_type];
4592 if (required_type_alternatives_when_removing_type_index_.size() <
4594 required_type_alternatives_when_removing_type_index_.resize(
4597 required_type_alternatives_when_removing_type_index_[dependent_type]
4598 .push_back(std::move(required_type_alternatives));
4601const std::vector<absl::flat_hash_set<int>>&
4605 DCHECK_LT(type, num_visit_types_);
4606 return type < same_vehicle_required_type_alternatives_per_type_index_.size()
4607 ? same_vehicle_required_type_alternatives_per_type_index_[type]
4608 : empty_required_type_alternatives_;
4611const std::vector<absl::flat_hash_set<int>>&
4615 DCHECK_LT(type, num_visit_types_);
4616 return type < required_type_alternatives_when_adding_type_index_.size()
4617 ? required_type_alternatives_when_adding_type_index_[type]
4618 : empty_required_type_alternatives_;
4621const std::vector<absl::flat_hash_set<int>>&
4625 DCHECK_LT(type, num_visit_types_);
4626 return type < required_type_alternatives_when_removing_type_index_.size()
4627 ? required_type_alternatives_when_removing_type_index_[type]
4628 : empty_required_type_alternatives_;
4636 int64_t var_index)
const {
4637 if (active_[var_index]->Min() == 1)
4638 return std::numeric_limits<int64_t>::max();
4639 const std::vector<DisjunctionIndex>& disjunction_indices =
4641 if (disjunction_indices.size() != 1)
return default_value;
4646 return std::max(int64_t{0}, disjunctions_[disjunction_index].value.penalty);
4650 const Assignment& solution_assignment,
4651 const std::string& dimension_to_print)
const {
4652 for (
int i = 0; i <
Size(); ++i) {
4653 if (!solution_assignment.Bound(
NextVar(i))) {
4655 <<
"DebugOutputVehicleSchedules() called on incomplete solution:"
4656 <<
" NextVar(" << i <<
") is unbound.";
4661 absl::flat_hash_set<std::string> dimension_names;
4662 if (dimension_to_print.empty()) {
4664 dimension_names.insert(all_dimension_names.begin(),
4665 all_dimension_names.end());
4667 dimension_names.insert(dimension_to_print);
4669 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
4670 int empty_vehicle_range_start = vehicle;
4675 if (empty_vehicle_range_start != vehicle) {
4676 if (empty_vehicle_range_start == vehicle - 1) {
4677 absl::StrAppendFormat(&output,
"Vehicle %d: empty",
4678 empty_vehicle_range_start);
4680 absl::StrAppendFormat(&output,
"Vehicles %d-%d: empty",
4681 empty_vehicle_range_start, vehicle - 1);
4683 output.append(
"\n");
4686 absl::StrAppendFormat(&output,
"Vehicle %d:", vehicle);
4687 int64_t index =
Start(vehicle);
4689 const IntVar* vehicle_var =
VehicleVar(index);
4690 absl::StrAppendFormat(&output,
"%d Vehicle(%d) ", index,
4691 solution_assignment.Value(vehicle_var));
4693 if (dimension_names.contains(dimension->name())) {
4694 const IntVar*
const var = dimension->CumulVar(index);
4695 absl::StrAppendFormat(&output,
"%s(%d..%d) ", dimension->name(),
4696 solution_assignment.Min(var),
4697 solution_assignment.Max(var));
4700 if (
IsEnd(index))
break;
4701 index = solution_assignment.Value(
NextVar(index));
4702 if (
IsEnd(index)) output.append(
"Route end ");
4704 output.append(
"\n");
4707 output.append(
"Unperformed nodes: ");
4708 bool has_unperformed =
false;
4709 for (
int i = 0;
i <
Size(); ++
i) {
4711 solution_assignment.Value(
NextVar(i)) == i) {
4712 absl::StrAppendFormat(&output,
"%d ", i);
4713 has_unperformed =
true;
4716 if (!has_unperformed) output.append(
"None");
4717 output.append(
"\n");
4722std::vector<std::vector<std::pair<int64_t, int64_t>>>
4725 std::vector<std::vector<std::pair<int64_t, int64_t>>> cumul_bounds(
4727 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
4729 LOG(DFATAL) <<
"GetCumulBounds() called on incomplete solution:"
4730 <<
" NextVar(" << vehicle <<
") is unbound.";
4734 for (
int vehicle_id = 0; vehicle_id <
vehicles(); ++vehicle_id) {
4735 int64_t index =
Start(vehicle_id);
4736 IntVar* dim_var = dimension.
CumulVar(index);
4737 cumul_bounds[vehicle_id].emplace_back(solution_assignment.
Min(dim_var),
4738 solution_assignment.
Max(dim_var));
4739 while (!
IsEnd(index)) {
4741 IntVar* dim_var = dimension.
CumulVar(index);
4742 cumul_bounds[vehicle_id].emplace_back(solution_assignment.
Min(dim_var),
4743 solution_assignment.
Max(dim_var));
4746 return cumul_bounds;
4750Assignment* RoutingModel::GetOrCreateAssignment() {
4751 if (assignment_ ==
nullptr) {
4752 assignment_ = solver_->MakeAssignment();
4753 assignment_->Add(nexts_);
4755 assignment_->Add(vehicle_vars_);
4757 assignment_->AddObjective(cost_);
4762Assignment* RoutingModel::GetOrCreateTmpAssignment() {
4763 if (tmp_assignment_ ==
nullptr) {
4764 tmp_assignment_ = solver_->MakeAssignment();
4765 tmp_assignment_->Add(nexts_);
4767 return tmp_assignment_;
4771 if (limit_ ==
nullptr) {
4772 limit_ = solver_->MakeLimit(
4773 absl::InfiniteDuration(), std::numeric_limits<int64_t>::max(),
4774 std::numeric_limits<int64_t>::max(),
4775 std::numeric_limits<int64_t>::max(),
true);
4780RegularLimit* RoutingModel::GetOrCreateCumulativeLimit() {
4781 if (cumulative_limit_ ==
nullptr) {
4782 cumulative_limit_ = solver_->MakeLimit(
4783 absl::InfiniteDuration(), std::numeric_limits<int64_t>::max(),
4784 std::numeric_limits<int64_t>::max(),
4785 std::numeric_limits<int64_t>::max(),
true,
4788 return cumulative_limit_;
4791RegularLimit* RoutingModel::GetOrCreateLocalSearchLimit() {
4792 if (ls_limit_ ==
nullptr) {
4793 ls_limit_ = solver_->MakeLimit(absl::InfiniteDuration(),
4794 std::numeric_limits<int64_t>::max(),
4795 std::numeric_limits<int64_t>::max(),
4801RegularLimit* RoutingModel::GetOrCreateLargeNeighborhoodSearchLimit() {
4802 if (lns_limit_ ==
nullptr) {
4803 lns_limit_ = solver_->MakeLimit(
4804 absl::InfiniteDuration(), std::numeric_limits<int64_t>::max(),
4805 std::numeric_limits<int64_t>::max(),
4806 std::numeric_limits<int64_t>::max(),
false);
4812RoutingModel::GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit() {
4813 if (first_solution_lns_limit_ ==
nullptr) {
4814 first_solution_lns_limit_ = solver_->MakeLimit(
4815 absl::InfiniteDuration(), std::numeric_limits<int64_t>::max(),
4816 std::numeric_limits<int64_t>::max(),
4817 std::numeric_limits<int64_t>::max(),
false);
4819 return first_solution_lns_limit_;
4823 auto get_vehicle_vars = [
this]() {
4827 LocalSearchOperator* insertion_operator =
MakeActive(
4828 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_);
4829 if (!pickup_delivery_pairs_.empty()) {
4830 insertion_operator = solver_->ConcatenateOperators(
4832 vehicle_start_class_callback_, pickup_delivery_pairs_),
4833 insertion_operator});
4835 if (!implicit_pickup_delivery_pairs_without_alternatives_.empty()) {
4836 insertion_operator = solver_->ConcatenateOperators(
4838 vehicle_start_class_callback_,
4839 implicit_pickup_delivery_pairs_without_alternatives_),
4840 insertion_operator});
4842 return insertion_operator;
4846 auto get_vehicle_vars = [
this]() {
4850 LocalSearchOperator* make_inactive_operator =
MakeInactive(
4851 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_);
4852 if (!pickup_delivery_pairs_.empty()) {
4853 make_inactive_operator = solver_->ConcatenateOperators(
4855 vehicle_start_class_callback_,
4856 pickup_delivery_pairs_),
4857 make_inactive_operator});
4859 return make_inactive_operator;
4862void RoutingModel::CreateNeighborhoodOperators(
4870 double neighbors_ratio_used = 1;
4873 parameters.ls_operator_neighbors_ratio(),
4874 parameters.ls_operator_min_neighbors(), neighbors_ratio_used,
4877 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors;
4878 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors;
4879 if (neighbors_ratio_used != 1) {
4880 get_incoming_neighbors = [neighbors_by_cost_class,
this](
4882 int64_t start) ->
const std::vector<int>& {
4884 return neighbors_by_cost_class->GetIncomingNeighborsOfNodeForCostClass(
4887 get_outgoing_neighbors = [neighbors_by_cost_class,
this](
4889 int64_t start) ->
const std::vector<int>& {
4890 DCHECK(!
IsEnd(node));
4891 return neighbors_by_cost_class->GetOutgoingNeighborsOfNodeForCostClass(
4896 local_search_operators_.clear();
4897 local_search_operators_.resize(LOCAL_SEARCH_OPERATOR_COUNTER,
nullptr);
4901 std::pair<RoutingLocalSearchOperator, Solver::LocalSearchOperators>>
4906 for (
const auto [type, op] : operator_by_type) {
4907 local_search_operators_[type] =
4909 ? solver_->MakeOperator(nexts_, op)
4910 : solver_->MakeOperator(nexts_, vehicle_vars_, op);
4915 const std::vector<std::pair<RoutingLocalSearchOperator,
4917 operator_by_type = {{LIN_KERNIGHAN,
Solver::LK},
4920 for (
const auto [type, op] : operator_by_type) {
4921 auto arc_cost = GetLocalSearchArcCostCallback(parameters);
4922 local_search_operators_[type] =
4924 ? solver_->MakeOperator(nexts_, std::move(arc_cost), op)
4925 : solver_->MakeOperator(nexts_, vehicle_vars_,
4926 std::move(arc_cost), op);
4930 auto get_vehicle_vars = [
this]() {
4937 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_,
4938 get_incoming_neighbors, get_outgoing_neighbors);
4940 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_,
4941 get_incoming_neighbors, get_outgoing_neighbors);
4942 local_search_operators_[CROSS] =
MakeCross(
4943 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_,
4944 get_incoming_neighbors, get_outgoing_neighbors);
4945 local_search_operators_[TWO_OPT] =
MakeTwoOpt(
4946 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_,
4947 get_incoming_neighbors, get_outgoing_neighbors);
4949 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_);
4951 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_);
4953 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_);
4954 local_search_operators_[EXCHANGE_PATH_START_ENDS_AND_MAKE_ACTIVE] =
4957 vehicle_start_class_callback_);
4959 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_);
4961 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_);
4963 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_,
4964 parameters.max_swap_active_chain_size());
4966 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_);
4967 std::vector<std::vector<int64_t>> alternative_sets(disjunctions_.size());
4968 for (
const RoutingModel::Disjunction& disjunction : disjunctions_) {
4972 if (disjunction.value.max_cardinality == 1 &&
4973 disjunction.indices.size() > 1) {
4974 alternative_sets.push_back(disjunction.indices);
4977 local_search_operators_[SHORTEST_PATH_SWAP_ACTIVE] =
4979 solver_.get(), nexts_, get_vehicle_vars(),
4980 vehicle_start_class_callback_, alternative_sets,
4981 GetLocalSearchHomogeneousArcCostCallback(parameters));
4984 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_,
4985 alternative_sets, GetLocalSearchHomogeneousArcCostCallback(parameters));
4988 local_search_operators_[MAKE_ACTIVE] = CreateInsertionOperator();
4989 local_search_operators_[MAKE_INACTIVE] = CreateMakeInactiveOperator();
4990 local_search_operators_[RELOCATE_PAIR] =
4992 vehicle_start_class_callback_, pickup_delivery_pairs_);
4993 std::vector<LocalSearchOperator*> light_relocate_pair_operators;
4995 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_,
4996 get_incoming_neighbors, get_outgoing_neighbors, pickup_delivery_pairs_,
4997 [
this](int64_t start) {
4998 return vehicle_pickup_delivery_policy_[
VehicleIndex(start)] ==
5002 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_,
5003 get_incoming_neighbors, get_outgoing_neighbors, pickup_delivery_pairs_));
5004 local_search_operators_[LIGHT_RELOCATE_PAIR] =
5005 solver_->ConcatenateOperators(light_relocate_pair_operators);
5006 local_search_operators_[EXCHANGE_PAIR] = solver_->ConcatenateOperators(
5008 vehicle_start_class_callback_, get_incoming_neighbors,
5009 get_outgoing_neighbors, pickup_delivery_pairs_),
5010 solver_->RevAlloc(
new SwapIndexPairOperator(nexts_, get_vehicle_vars(),
5011 pickup_delivery_pairs_))});
5013 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_,
5014 pickup_delivery_pairs_);
5016 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_,
5017 get_incoming_neighbors, get_outgoing_neighbors,
5018 GetLocalSearchHomogeneousArcCostCallback(parameters));
5019 local_search_operators_[NODE_PAIR_SWAP] = solver_->ConcatenateOperators(
5021 vehicle_start_class_callback_,
5022 pickup_delivery_pairs_),
5024 vehicle_start_class_callback_,
5025 pickup_delivery_pairs_),
5027 vehicle_start_class_callback_,
5028 pickup_delivery_pairs_)});
5030 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_,
5031 get_incoming_neighbors, get_outgoing_neighbors, pickup_delivery_pairs_);
5033 solver_.get(), nexts_, get_vehicle_vars(), vehicle_start_class_callback_,
5034 get_incoming_neighbors, get_outgoing_neighbors, pickup_delivery_pairs_);
5036 const auto arc_cost_for_path_start =
5037 [
this, arc_cost_getter = GetLocalSearchArcCostCallback(parameters)](
5038 int64_t before_node, int64_t after_node, int64_t start_index) {
5040 const int64_t arc_cost =
5041 arc_cost_getter(before_node, after_node, vehicle);
5042 return (before_node != start_index ||
IsEnd(after_node))
5046 local_search_operators_[RELOCATE_EXPENSIVE_CHAIN] =
5048 solver_.get(), nexts_, get_vehicle_vars(),
5049 vehicle_start_class_callback_,
5050 parameters.relocate_expensive_chain_num_arcs_to_consider(),
5051 arc_cost_for_path_start);
5054 const auto make_global_cheapest_insertion_filtered_heuristic =
5055 [
this, ¶meters]() {
5056 return std::make_unique<GlobalCheapestInsertionFilteredHeuristic>(
5057 this, [
this]() {
return CheckLimit(time_buffer_); },
5058 GetLocalSearchArcCostCallback(parameters),
5060 GetOrCreateLocalSearchFilterManager(
5063 parameters.global_cheapest_insertion_ls_operator_parameters(),
5066 const auto make_local_cheapest_insertion_filtered_heuristic =
5067 [
this, ¶meters]() {
5068 const LocalCheapestInsertionParameters& lci_params =
5069 parameters.local_cheapest_insertion_parameters();
5070 return std::make_unique<LocalCheapestInsertionFilteredHeuristic>(
5071 this, [
this]() {
return CheckLimit(time_buffer_); },
5072 GetLocalSearchArcCostCallback(parameters), lci_params,
5073 GetOrCreateLocalSearchFilterManager(
5076 false, bin_capacities_.get());
5078 local_search_operators_[GLOBAL_CHEAPEST_INSERTION_VISIT_TYPES_LNS] =
5079 solver_->RevAlloc(
new RelocateVisitTypeOperator(
5080 make_global_cheapest_insertion_filtered_heuristic()));
5081 local_search_operators_[LOCAL_CHEAPEST_INSERTION_VISIT_TYPES_LNS] =
5082 solver_->RevAlloc(
new RelocateVisitTypeOperator(
5083 make_local_cheapest_insertion_filtered_heuristic()));
5084 local_search_operators_[GLOBAL_CHEAPEST_INSERTION_CLOSE_NODES_LNS] =
5085 solver_->RevAlloc(
new FilteredHeuristicCloseNodesLNSOperator(
5086 make_global_cheapest_insertion_filtered_heuristic(),
5087 parameters.heuristic_close_nodes_lns_num_nodes()));
5089 local_search_operators_[LOCAL_CHEAPEST_INSERTION_CLOSE_NODES_LNS] =
5090 solver_->RevAlloc(
new FilteredHeuristicCloseNodesLNSOperator(
5091 make_local_cheapest_insertion_filtered_heuristic(),
5092 parameters.heuristic_close_nodes_lns_num_nodes()));
5094 local_search_operators_[GLOBAL_CHEAPEST_INSERTION_PATH_LNS] =
5095 solver_->RevAlloc(
new FilteredHeuristicPathLNSOperator(
5096 make_global_cheapest_insertion_filtered_heuristic()));
5098 local_search_operators_[LOCAL_CHEAPEST_INSERTION_PATH_LNS] =
5099 solver_->RevAlloc(
new FilteredHeuristicPathLNSOperator(
5100 make_local_cheapest_insertion_filtered_heuristic()));
5102 local_search_operators_
5103 [RELOCATE_PATH_GLOBAL_CHEAPEST_INSERTION_INSERT_UNPERFORMED] =
5105 new RelocatePathAndHeuristicInsertUnperformedOperator(
5106 make_global_cheapest_insertion_filtered_heuristic()));
5108 local_search_operators_[GLOBAL_CHEAPEST_INSERTION_EXPENSIVE_CHAIN_LNS] =
5109 solver_->RevAlloc(
new FilteredHeuristicExpensiveChainLNSOperator(
5110 make_global_cheapest_insertion_filtered_heuristic(),
5111 parameters.heuristic_expensive_chain_lns_num_arcs_to_consider(),
5112 arc_cost_for_path_start));
5114 local_search_operators_[LOCAL_CHEAPEST_INSERTION_EXPENSIVE_CHAIN_LNS] =
5115 solver_->RevAlloc(
new FilteredHeuristicExpensiveChainLNSOperator(
5116 make_local_cheapest_insertion_filtered_heuristic(),
5117 parameters.heuristic_expensive_chain_lns_num_arcs_to_consider(),
5118 arc_cost_for_path_start));
5121#define CP_ROUTING_PUSH_OPERATOR(operator_type, operator_method) \
5122 if (operators_to_consider.contains(operator_type) && \
5123 search_parameters.local_search_operators().use_##operator_method() == \
5125 operators.push_back(local_search_operators_[operator_type]); \
5130 const std::vector<LocalSearchOperator*>& operators)
const {
5131 if (search_parameters.use_multi_armed_bandit_concatenate_operators()) {
5132 return solver_->MultiArmedBanditConcatenateOperators(
5135 .multi_armed_bandit_compound_operator_memory_coefficient(),
5137 .multi_armed_bandit_compound_operator_exploration_coefficient(),
5140 return solver_->ConcatenateOperators(operators);
5145 const absl::flat_hash_set<RoutingLocalSearchOperator>&
5146 operators_to_consider)
const {
5147 std::vector<LocalSearchOperator*> operator_groups;
5148 std::vector<LocalSearchOperator*> operators = extra_operators_;
5149 if (!pickup_delivery_pairs_.empty()) {
5153 if (search_parameters.local_search_operators().use_relocate_pair() ==
5162 if (vehicles_ > 1) {
5173 if (!pickup_delivery_pairs_.empty() ||
5174 search_parameters.local_search_operators().use_relocate_neighbors() ==
5176 operators.push_back(local_search_operators_[RELOCATE_NEIGHBORS]);
5179 search_parameters.local_search_metaheuristic();
5181 local_search_metaheuristic !=
5183 local_search_metaheuristic !=
5190 size_t max_alternative_set_size = 0;
5191 for (
const RoutingModel::Disjunction& disjunction : disjunctions_) {
5192 max_alternative_set_size =
5193 std::max(max_alternative_set_size, disjunction.indices.size());
5195 if (!disjunctions_.empty()) {
5203 relocate_and_make_active);
5205 relocate_and_make_active);
5208 exchange_and_make_active);
5210 exchange_path_start_ends_and_make_active);
5215 if (max_alternative_set_size > 1) {
5217 shortest_path_swap_active);
5221 LocalSearchOperator* main_operator_group =
5222 ConcatenateOperators(search_parameters, operators);
5237 global_cheapest_insertion_path_lns);
5239 local_cheapest_insertion_path_lns);
5241 RELOCATE_PATH_GLOBAL_CHEAPEST_INSERTION_INSERT_UNPERFORMED,
5242 relocate_path_global_cheapest_insertion_insert_unperformed);
5251 LocalSearchOperator* path_lns_operator_group =
5252 ConcatenateOperators(search_parameters, operators);
5253 operators.assign({main_operator_group, path_lns_operator_group});
5254 main_operator_group = ConcatenateOperators(search_parameters, operators);
5257 operators.assign({main_operator_group});
5259 global_cheapest_insertion_expensive_chain_lns);
5261 local_cheapest_insertion_expensive_chain_lns);
5262 main_operator_group = ConcatenateOperators(search_parameters, operators);
5264 operators.assign({main_operator_group});
5266 global_cheapest_insertion_close_nodes_lns);
5268 local_cheapest_insertion_close_nodes_lns);
5269 operator_groups.push_back(ConcatenateOperators(search_parameters, operators));
5271 operators.assign({main_operator_group});
5273 global_cheapest_insertion_visit_types_lns);
5275 local_cheapest_insertion_visit_types_lns);
5276 operator_groups.push_back(ConcatenateOperators(search_parameters, operators));
5281 local_search_metaheuristic !=
5283 local_search_metaheuristic !=
5288 local_search_metaheuristic !=
5290 local_search_metaheuristic !=
5296 if (!disjunctions_.empty()) {
5299 operator_groups.push_back(ConcatenateOperators(search_parameters, operators));
5301 return solver_->ConcatenateOperators(operator_groups);
5304#undef CP_ROUTING_PUSH_OPERATOR
5308void ConvertVectorInt64ToVectorInt(absl::Span<const int64_t>
input,
5309 std::vector<int>* output) {
5310 const int n =
input.size();
5312 int* data = output->data();
5313 for (
int i = 0;
i < n; ++
i) {
5314 const int element =
static_cast<int>(
input[
i]);
5315 DCHECK_EQ(
input[i],
static_cast<int64_t
>(element));
5322std::vector<LocalSearchFilterManager::FilterEvent>
5323RoutingModel::CreateLocalSearchFilters(
5336 std::vector<LocalSearchFilterManager::FilterEvent> filter_events;
5340 if (options.filter_objective && vehicle_amortized_cost_factors_set_) {
5341 filter_events.push_back(
5348 if (options.filter_objective) {
5350 LocalSearchFilter* sum = solver_->MakeSumObjectiveFilter(
5354 filter_events.push_back({sum, kAccept, priority});
5356 LocalSearchFilter* sum = solver_->MakeSumObjectiveFilter(
5357 nexts_, vehicle_vars_,
5358 [
this](int64_t i, int64_t j, int64_t k) {
5362 filter_events.push_back({sum, kAccept, priority});
5365 const PathState* path_state_reference =
nullptr;
5367 std::vector<int> path_starts;
5368 std::vector<int> path_ends;
5369 ConvertVectorInt64ToVectorInt(paths_metadata_.Starts(), &path_starts);
5370 ConvertVectorInt64ToVectorInt(paths_metadata_.Ends(), &path_ends);
5371 auto path_state = std::make_unique<PathState>(
5372 Size() +
vehicles(), std::move(path_starts), std::move(path_ends));
5373 path_state_reference = path_state.get();
5374 filter_events.push_back(
5381 filter_events.push_back(
5382 {solver_->MakeVariableDomainFilter(), kAccept, priority});
5384 if (vehicles_ > max_active_vehicles_) {
5385 filter_events.push_back(
5389 bool has_same_activity_constraints =
false;
5390 for (
int node = 0; node <
Size(); ++node) {
5392 has_same_activity_constraints =
true;
5396 if (has_same_activity_constraints) {
5397 filter_events.push_back(
5401 filter_events.push_back(
5405 if (!disjunctions_.empty()) {
5408 filter_events.push_back(
5410 kAccept, priority});
5413 if (!same_vehicle_costs_.empty()) {
5414 if (options.filter_objective) {
5415 filter_events.push_back(
5424 filter_events.push_back(
5432 const int first_lightweight_index = filter_events.size();
5435 for (
int e = first_lightweight_index; e < filter_events.size(); ++e) {
5436 filter_events[e].priority = priority;
5444 if (!pickup_delivery_pairs_.empty()) {
5446 *
this, path_state_reference, pickup_delivery_pairs_,
5447 vehicle_pickup_delivery_policy_);
5448 filter_events.push_back({filter, kRelax, priority});
5449 filter_events.push_back({filter, kAccept, priority});
5451 if (options.filter_objective) {
5452 const int num_vehicles =
vehicles();
5453 for (
const auto& [force_distance, energy_costs] :
5454 force_distance_to_energy_costs_) {
5455 const auto& [force, distance] = force_distance;
5457 DCHECK_NE(force_dimension,
nullptr);
5458 if (force_dimension ==
nullptr)
continue;
5459 std::vector<int64_t> force_start_min(num_vehicles);
5460 std::vector<int64_t> force_end_min(num_vehicles);
5461 std::vector<int> force_class(num_vehicles);
5462 std::vector<
const std::function<int64_t(int64_t)>*> force_evaluators;
5463 for (
int v = 0; v < num_vehicles; ++v) {
5464 force_start_min[v] = force_dimension->GetCumulVarMin(
Start(v));
5465 force_end_min[v] = force_dimension->GetCumulVarMin(
End(v));
5466 const int c = force_dimension->vehicle_to_class(v);
5468 if (c >= force_evaluators.size()) {
5469 force_evaluators.resize(c + 1,
nullptr);
5471 if (force_evaluators[c] ==
nullptr) {
5472 force_evaluators[
c] = &(force_dimension->GetUnaryTransitEvaluator(v));
5473 DCHECK(force_evaluators[c] !=
nullptr);
5474 if (force_evaluators[c] ==
nullptr)
continue;
5479 DCHECK_NE(distance_dimension,
nullptr);
5480 if (distance_dimension ==
nullptr)
continue;
5481 std::vector<int> distance_class(num_vehicles);
5482 std::vector<
const std::function<int64_t(int64_t, int64_t)>*>
5483 distance_evaluators;
5484 for (
int v = 0; v < num_vehicles; ++v) {
5485 const int c = distance_dimension->vehicle_to_class(v);
5486 distance_class[v] =
c;
5487 if (c >= distance_evaluators.size())
5488 distance_evaluators.resize(c + 1,
nullptr);
5489 if (distance_evaluators[c] ==
nullptr) {
5490 distance_evaluators[
c] =
5491 &(distance_dimension->GetBinaryTransitEvaluator(v));
5494 std::vector<PathEnergyCostChecker::EnergyCost> path_energy_costs;
5495 for (
const auto& limit : energy_costs) {
5496 path_energy_costs.push_back({
5497 .threshold = limit.threshold,
5498 .cost_per_unit_below_threshold =
5499 limit.cost_per_unit_below_threshold,
5500 .cost_per_unit_above_threshold =
5501 limit.cost_per_unit_above_threshold,
5504 auto checker = std::make_unique<PathEnergyCostChecker>(
5505 path_state_reference, std::move(force_start_min),
5506 std::move(force_end_min), std::move(force_class),
5507 std::move(force_evaluators), std::move(distance_class),
5508 std::move(distance_evaluators), std::move(path_energy_costs),
5509 vehicle_used_when_empty_);
5510 filter_events.push_back(
5512 absl::StrCat(force_dimension->name(),
5513 distance_dimension->name())),
5514 kAccept, priority});
5520 filter_events.push_back(
5526 const int first_dimension_filter_index = filter_events.size();
5529 false, &filter_events);
5530 int max_priority = priority;
5531 for (
int e = first_dimension_filter_index; e < filter_events.size(); ++e) {
5532 filter_events[e].priority += priority;
5533 max_priority = std::max(max_priority, filter_events[e].priority);
5535 priority = max_priority;
5538 if (!route_evaluators_.empty()) {
5540 filter_events.push_back(
5544 if (!extra_filters_.empty()) {
5546 for (
const auto& event : extra_filters_) {
5547 filter_events.push_back({
event.filter,
event.event_type, priority});
5551 if (options.filter_with_cp_solver) {
5555 return filter_events;
5560 LocalSearchFilterManager* local_search_filter_manager =
5562 if (local_search_filter_manager ==
nullptr) {
5563 local_search_filter_manager =
5565 CreateLocalSearchFilters(parameters, options)));
5566 local_search_filter_managers_[options] = local_search_filter_manager;
5568 return local_search_filter_manager;
5572 const std::vector<RoutingDimension*>& dimensions,
5574 const int num_vehicles = paths_metadata.NumPaths();
5575 auto bin_capacities = std::make_unique<BinCapacities>(num_vehicles);
5576 std::vector<BinCapacities::LoadLimit> load_limits;
5584 load_limits.assign(num_vehicles, {.max_load =
kint64max,
5586 .cost_above_soft_max_load = 0});
5587 for (
int vehicle = 0; vehicle < num_vehicles; ++vehicle) {
5597 int64_t min_node = paths_metadata.Starts()[vehicle];
5598 int64_t max_node = paths_metadata.Ends()[vehicle];
5600 std::swap(min_node, max_node);
5602 const int64_t load_min =
5603 std::max<int64_t>(0, dimension->
CumulVar(min_node)->
Min());
5604 const int64_t load_max =
5607 load_limits[vehicle].max_load =
CapSub(load_max, load_min);
5609 load_limits[vehicle].soft_max_load =
5611 load_limits[vehicle].cost_above_soft_max_load =
5615 bin_capacities->AddDimension(
5616 [dimension](
int node,
int vehicle) {
5621 if (bin_capacities->NumDimensions() == 0) bin_capacities.reset(
nullptr);
5622 return bin_capacities;
5627 for (
int vehicle = 0; vehicle < dimension.model()->vehicles(); vehicle++) {
5628 if (!dimension.AreVehicleTransitsPositive(vehicle)) {
5636void RoutingModel::StoreDimensionCumulOptimizers(
5638 Assignment* optimized_dimensions_collector_assignment =
5639 solver_->MakeAssignment();
5640 optimized_dimensions_collector_assignment->AddObjective(
CostVar());
5641 const int num_dimensions = dimensions_.size();
5642 local_optimizer_index_.resize(num_dimensions, -1);
5643 global_optimizer_index_.resize(num_dimensions, -1);
5644 if (parameters.disable_scheduling_beware_this_may_degrade_performance()) {
5649 DCHECK_EQ(dimension->model(),
this);
5650 const int num_resource_groups =
5652 bool needs_optimizer =
false;
5653 if (dimension->global_span_cost_coefficient() > 0 ||
5654 !dimension->GetNodePrecedences().empty() || num_resource_groups > 1) {
5656 needs_optimizer =
true;
5657 global_optimizer_index_[dim] = global_dimension_optimizers_.size();
5658 global_dimension_optimizers_.push_back(
5659 {std::make_unique<GlobalDimensionCumulOptimizer>(
5660 dimension, parameters.continuous_scheduling_solver(),
5662 std::make_unique<GlobalDimensionCumulOptimizer>(
5663 dimension, parameters.mixed_integer_scheduling_solver(),
5665 if (!AllTransitsPositive(*dimension)) {
5666 dimension->SetOffsetForGlobalOptimizer(0);
5669 vehicles() == 0 ? 0 : std::numeric_limits<int64_t>::max();
5670 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
5671 DCHECK_GE(dimension->CumulVar(
Start(vehicle))->Min(), 0);
5673 std::min(offset, dimension->CumulVar(
Start(vehicle))->Min() - 1);
5675 if (dimension->HasBreakConstraints()) {
5676 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
5677 for (
const IntervalVar* br :
5678 dimension->GetBreakIntervalsOfVehicle(vehicle)) {
5679 offset = std::min(offset,
CapSub(br->StartMin(), 1));
5684 dimension->SetOffsetForGlobalOptimizer(std::max(
Zero(), offset));
5688 bool has_span_cost =
false;
5689 bool has_span_limit =
false;
5690 std::vector<int64_t> vehicle_offsets(
vehicles());
5691 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
5692 if (dimension->GetSpanCostCoefficientForVehicle(vehicle) > 0) {
5693 has_span_cost =
true;
5695 if (dimension->GetSpanUpperBoundForVehicle(vehicle) <
5696 std::numeric_limits<int64_t>::max()) {
5697 has_span_limit =
true;
5699 DCHECK_GE(dimension->CumulVar(
Start(vehicle))->Min(), 0);
5701 if (dimension->AreVehicleTransitsPositive(vehicle)) {
5702 offset =
CapSub(dimension->CumulVar(
Start(vehicle))->Min(), 1);
5703 if (dimension->HasBreakConstraints()) {
5704 for (
const IntervalVar* br :
5705 dimension->GetBreakIntervalsOfVehicle(vehicle)) {
5706 offset = std::min(offset,
CapSub(br->StartMin(), 1));
5710 vehicle_offsets[vehicle] = std::max<int64_t>(0, offset);
5712 bool has_soft_lower_bound =
false;
5713 bool has_soft_upper_bound =
false;
5714 for (
int i = 0;
i < dimension->cumuls().size(); ++
i) {
5715 if (dimension->HasCumulVarSoftLowerBound(i)) {
5716 has_soft_lower_bound =
true;
5718 if (dimension->HasCumulVarSoftUpperBound(i)) {
5719 has_soft_upper_bound =
true;
5722 int num_linear_constraints = 0;
5723 if (has_span_cost) ++num_linear_constraints;
5724 if (has_span_limit) ++num_linear_constraints;
5725 if (dimension->HasSoftSpanUpperBounds()) ++num_linear_constraints;
5726 if (dimension->HasQuadraticCostSoftSpanUpperBounds()) {
5727 ++num_linear_constraints;
5729 if (has_soft_lower_bound) ++num_linear_constraints;
5730 if (has_soft_upper_bound) ++num_linear_constraints;
5731 if (dimension->HasBreakConstraints()) ++num_linear_constraints;
5732 if (num_resource_groups > 0 || num_linear_constraints >= 2) {
5733 needs_optimizer =
true;
5734 dimension->SetVehicleOffsetsForLocalOptimizer(std::move(vehicle_offsets));
5735 local_optimizer_index_[dim] = local_dimension_optimizers_.size();
5736 local_dimension_optimizers_.push_back(
5737 {std::make_unique<LocalDimensionCumulOptimizer>(
5738 dimension, parameters.continuous_scheduling_solver(),
5740 std::make_unique<LocalDimensionCumulOptimizer>(
5741 dimension, parameters.mixed_integer_scheduling_solver(),
5744 if (needs_optimizer) {
5745 optimized_dimensions_collector_assignment->Add(dimension->cumuls());
5753 for (IntVar*
const extra_var : extra_vars_) {
5754 optimized_dimensions_collector_assignment->Add(extra_var);
5756 for (IntervalVar*
const extra_interval : extra_intervals_) {
5757 optimized_dimensions_collector_assignment->Add(extra_interval);
5760 optimized_dimensions_assignment_collector_ =
5761 solver_->MakeFirstSolutionCollector(
5762 optimized_dimensions_collector_assignment);
5767 std::vector<RoutingDimension*> dimensions;
5769 bool has_soft_or_span_cost =
false;
5770 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
5771 if (dimension->GetSpanCostCoefficientForVehicle(vehicle) > 0) {
5772 has_soft_or_span_cost =
true;
5776 if (!has_soft_or_span_cost) {
5777 for (
int i = 0;
i < dimension->cumuls().size(); ++
i) {
5778 if (dimension->HasCumulVarSoftUpperBound(i) ||
5779 dimension->HasCumulVarSoftLowerBound(i)) {
5780 has_soft_or_span_cost =
true;
5785 if (has_soft_or_span_cost) dimensions.push_back(dimension);
5791 std::vector<RoutingDimension*> unary_dimensions;
5793 if (dim->IsUnary()) {
5794 unary_dimensions.push_back(dim);
5797 return unary_dimensions;
5800std::vector<const RoutingDimension*>
5803 std::vector<const RoutingDimension*> global_optimizer_dimensions;
5804 for (
auto& [lp_optimizer, mp_optimizer] : global_dimension_optimizers_) {
5805 DCHECK_NE(lp_optimizer.get(),
nullptr);
5806 DCHECK_NE(mp_optimizer.get(),
nullptr);
5807 global_optimizer_dimensions.push_back(lp_optimizer->dimension());
5809 return global_optimizer_dimensions;
5812std::vector<const RoutingDimension*>
5815 std::vector<const RoutingDimension*> local_optimizer_dimensions;
5816 for (
auto& [lp_optimizer, mp_optimizer] : local_dimension_optimizers_) {
5817 DCHECK_NE(lp_optimizer.get(),
nullptr);
5818 DCHECK_NE(mp_optimizer.get(),
nullptr);
5819 local_optimizer_dimensions.push_back(lp_optimizer->dimension());
5821 return local_optimizer_dimensions;
5825 const RoutingSearchParameters& parameters)
const {
5831 if (parameters.local_search_metaheuristic() ==
5833 parameters.local_search_metaheuristic() ==
5848 std::vector<DecisionBuilder*> decision_builders;
5849 decision_builders.push_back(solver_->MakePhase(
5856 decision_builders.push_back(
5859 const bool can_use_dimension_cumul_optimizers =
5860 !parameters.disable_scheduling_beware_this_may_degrade_performance();
5861 DCHECK(local_dimension_optimizers_.empty() ||
5862 can_use_dimension_cumul_optimizers);
5863 for (
auto& [lp_optimizer, mp_optimizer] : local_dimension_optimizers_) {
5871 solver_.get(), lp_optimizer.get(), mp_optimizer.get()));
5874 DCHECK(global_dimension_optimizers_.empty() ||
5875 can_use_dimension_cumul_optimizers);
5876 for (
auto& [lp_optimizer, mp_optimizer] : global_dimension_optimizers_) {
5878 solver_.get(), lp_optimizer.get(), mp_optimizer.get()));
5880 decision_builders.push_back(finalizer_variables_->CreateFinalizer());
5882 return solver_->Compose(decision_builders);
5885void RoutingModel::CreateFirstSolutionDecisionBuilders(
5887 first_solution_decision_builders_.resize(
5889 first_solution_filtered_decision_builders_.resize(
5891 DecisionBuilder*
const finalize_solution =
5892 CreateSolutionFinalizer(search_parameters);
5894 first_solution_decision_builders_
5897 first_solution_decision_builders_
5900 [
this](int64_t i, int64_t j) {
5913 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
5914 first_solution_filtered_decision_builders_
5916 CreateIntVarFilteredDecisionBuilder<
5917 EvaluatorCheapestAdditionFilteredHeuristic>(
5919 GetOrCreateLocalSearchFilterManager(
5920 search_parameters, {
false,
5922 first_solution_decision_builders_
5924 solver_->Try(first_solution_filtered_decision_builders_
5926 first_solution_decision_builders_
5935 first_solution_decision_builders_
5938 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
5939 first_solution_filtered_decision_builders_
5941 CreateIntVarFilteredDecisionBuilder<
5942 ComparatorCheapestAdditionFilteredHeuristic>(
5944 GetOrCreateLocalSearchFilterManager(
5945 search_parameters, {
false,
5947 first_solution_decision_builders_
5949 first_solution_filtered_decision_builders_
5951 first_solution_decision_builders_
5955 if (first_solution_evaluator_ !=
nullptr) {
5956 first_solution_decision_builders_
5960 first_solution_decision_builders_
5967 RegularLimit*
const ls_limit = solver_->MakeLimit(
5968 GetTimeLimit(search_parameters), std::numeric_limits<int64_t>::max(),
5969 std::numeric_limits<int64_t>::max(), std::numeric_limits<int64_t>::max(),
5971 DecisionBuilder*
const finalize = solver_->MakeSolveOnce(
5972 finalize_solution, GetOrCreateLargeNeighborhoodSearchLimit());
5973 LocalSearchPhaseParameters*
const insertion_parameters =
5974 solver_->MakeLocalSearchPhaseParameters(
5975 nullptr, CreateInsertionOperator(), finalize, ls_limit,
5976 GetOrCreateLocalSearchFilterManager(
5979 std::vector<IntVar*> decision_vars = nexts_;
5981 decision_vars.insert(decision_vars.end(), vehicle_vars_.begin(),
5982 vehicle_vars_.end());
5984 const int64_t optimization_step = std::max(
5988 solver_->MakeNestedOptimize(
5990 insertion_parameters),
5991 GetOrCreateAssignment(),
false, optimization_step);
5993 solver_->Compose(first_solution_decision_builders_
5998 for (
bool is_sequential : {
false,
true}) {
6003 first_solution_filtered_decision_builders_[first_solution_strategy] =
6004 CreateIntVarFilteredDecisionBuilder<
6005 GlobalCheapestInsertionFilteredHeuristic>(
6006 [
this](int64_t
i, int64_t j, int64_t vehicle) {
6010 GetOrCreateLocalSearchFilterManager(
6011 search_parameters, {
false,
6014 .global_cheapest_insertion_first_solution_parameters(),
6016 IntVarFilteredDecisionBuilder*
const strong_gci =
6017 CreateIntVarFilteredDecisionBuilder<
6018 GlobalCheapestInsertionFilteredHeuristic>(
6019 [
this](int64_t
i, int64_t j, int64_t vehicle) {
6023 GetOrCreateLocalSearchFilterManager(
6024 search_parameters, {
false,
6027 .global_cheapest_insertion_first_solution_parameters(),
6029 first_solution_decision_builders_[first_solution_strategy] = solver_->Try(
6030 first_solution_filtered_decision_builders_[first_solution_strategy],
6031 solver_->Try(strong_gci, first_solution_decision_builders_
6036 std::function<bool(
const std::vector<VariableValuePair>&,
6037 std::vector<VariableValuePair>*)>
6038 optimize_on_insertion;
6039 if (secondary_model_ !=
nullptr) {
6040 secondary_model_->QuietCloseModelWithParameters(secondary_parameters_);
6041 secondary_optimizer_ = std::make_unique<SecondaryOptimizer>(
6042 secondary_model_, &secondary_parameters_,
6043 search_parameters.first_solution_optimization_period());
6045 secondary_optimizer_.get());
6047 const LocalCheapestInsertionParameters& lci_params =
6048 search_parameters.local_cheapest_insertion_parameters();
6049 first_solution_filtered_decision_builders_
6051 CreateIntVarFilteredDecisionBuilder<
6052 LocalCheapestInsertionFilteredHeuristic>(
6053 [
this](int64_t
i, int64_t j, int64_t vehicle) {
6057 GetOrCreateLocalSearchFilterManager(
6058 search_parameters, {
false,
6060 true, bin_capacities_.get(),
6061 optimize_on_insertion);
6062 IntVarFilteredDecisionBuilder*
const strong_lci =
6063 CreateIntVarFilteredDecisionBuilder<
6064 LocalCheapestInsertionFilteredHeuristic>(
6065 [
this](int64_t
i, int64_t j, int64_t vehicle) {
6069 GetOrCreateLocalSearchFilterManager(search_parameters,
6072 true, bin_capacities_.get(),
6073 optimize_on_insertion);
6074 first_solution_decision_builders_
6076 first_solution_filtered_decision_builders_
6078 solver_->Try(strong_lci,
6079 first_solution_decision_builders_
6083 const LocalCheapestInsertionParameters& lcci_params =
6084 search_parameters.local_cheapest_cost_insertion_parameters();
6085 first_solution_filtered_decision_builders_
6087 CreateIntVarFilteredDecisionBuilder<
6088 LocalCheapestInsertionFilteredHeuristic>(
6089 nullptr, lcci_params,
6090 GetOrCreateLocalSearchFilterManager(
6091 search_parameters, {
true,
6093 true, bin_capacities_.get(),
6094 optimize_on_insertion);
6095 IntVarFilteredDecisionBuilder*
const strong_lcci =
6096 CreateIntVarFilteredDecisionBuilder<
6097 LocalCheapestInsertionFilteredHeuristic>(
6098 nullptr, lcci_params,
6099 GetOrCreateLocalSearchFilterManager(search_parameters,
6102 true, bin_capacities_.get(),
6103 optimize_on_insertion);
6104 first_solution_decision_builders_
6106 first_solution_filtered_decision_builders_
6108 solver_->Try(strong_lcci,
6109 first_solution_decision_builders_
6113 LocalSearchFilterManager* filter_manager =
nullptr;
6114 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
6115 filter_manager = GetOrCreateLocalSearchFilterManager(
6120 IntVarFilteredDecisionBuilder* parallel_savings_db =
6121 CreateIntVarFilteredDecisionBuilder<ParallelSavingsFilteredHeuristic>(
6122 search_parameters.savings_parameters(), filter_manager);
6123 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
6124 first_solution_filtered_decision_builders_
6130 parallel_savings_db,
6131 CreateIntVarFilteredDecisionBuilder<ParallelSavingsFilteredHeuristic>(
6132 search_parameters.savings_parameters(),
6133 GetOrCreateLocalSearchFilterManager(
6134 search_parameters, {
false,
6137 IntVarFilteredDecisionBuilder* sequential_savings_db =
6138 CreateIntVarFilteredDecisionBuilder<SequentialSavingsFilteredHeuristic>(
6139 search_parameters.savings_parameters(), filter_manager);
6140 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
6142 sequential_savings_db;
6147 sequential_savings_db,
6148 CreateIntVarFilteredDecisionBuilder<
6149 SequentialSavingsFilteredHeuristic>(
6150 search_parameters.savings_parameters(),
6151 GetOrCreateLocalSearchFilterManager(
6152 search_parameters, {
false,
6165 CreateIntVarFilteredDecisionBuilder<ChristofidesFilteredHeuristic>(
6166 GetOrCreateLocalSearchFilterManager(
6167 search_parameters, {
false,
6169 search_parameters.christofides_use_minimum_matching());
6171 const bool has_precedences = std::any_of(
6172 dimensions_.begin(), dimensions_.end(),
6174 bool has_single_vehicle_node =
false;
6175 for (
int node = 0; node <
Size(); node++) {
6176 if (!
IsStart(node) && !
IsEnd(node) && allowed_vehicles_[node].size() == 1) {
6177 has_single_vehicle_node =
true;
6181 automatic_first_solution_strategy_ =
6183 has_precedences, has_single_vehicle_node);
6185 first_solution_decision_builders_[automatic_first_solution_strategy_];
6194 if (first_solution_decision_builders_[strategy] ==
nullptr ||
6198 const std::string strategy_name =
6200 const std::string& log_tag = search_parameters.log_tag();
6201 if (!log_tag.empty() && log_tag != strategy_name) {
6202 first_solution_decision_builders_[strategy]->set_name(absl::StrFormat(
6203 "%s / %s", strategy_name, search_parameters.log_tag()));
6205 first_solution_decision_builders_[strategy]->set_name(strategy_name);
6213 search_parameters.first_solution_strategy();
6214 if (first_solution_strategy < first_solution_decision_builders_.size()) {
6215 return first_solution_decision_builders_[first_solution_strategy];
6222RoutingModel::GetFilteredFirstSolutionDecisionBuilderOrNull(
6225 search_parameters.first_solution_strategy();
6226 return first_solution_filtered_decision_builders_[first_solution_strategy];
6229template <
typename Heuristic,
typename... Args>
6231RoutingModel::CreateIntVarFilteredDecisionBuilder(
const Args&... args) {
6232 return solver_->RevAlloc(
6233 new IntVarFilteredDecisionBuilder(std::make_unique<Heuristic>(
6234 this, [
this]() {
return CheckLimit(time_buffer_); }, args...)));
6239 SearchLimit* lns_limit = GetOrCreateLargeNeighborhoodSearchLimit();
6240 absl::flat_hash_set<RoutingLocalSearchOperator> operators_to_consider;
6241 LocalSearchOperator* ls_operator =
nullptr;
6243 if (secondary_ls_operator_ ==
nullptr) {
6244 operators_to_consider = {TWO_OPT,
6248 MAKE_CHAIN_INACTIVE,
6249 SHORTEST_PATH_SWAP_ACTIVE,
6250 SHORTEST_PATH_TWO_OPT};
6251 secondary_ls_operator_ =
6252 GetNeighborhoodOperators(search_parameters, operators_to_consider);
6254 ls_operator = secondary_ls_operator_;
6256 if (primary_ls_operator_ ==
nullptr) {
6258 for (
int op = 0; op < LOCAL_SEARCH_OPERATOR_COUNTER; ++op) {
6259 operators_to_consider.insert(RoutingLocalSearchOperator(op));
6261 primary_ls_operator_ =
6262 GetNeighborhoodOperators(search_parameters, operators_to_consider);
6264 ls_operator = primary_ls_operator_;
6266 return solver_->MakeLocalSearchPhaseParameters(
6268 solver_->MakeSolveOnce(CreateSolutionFinalizer(search_parameters),
6270 GetOrCreateLocalSearchLimit(),
6271 GetOrCreateLocalSearchFilterManager(
6276DecisionBuilder* RoutingModel::CreatePrimaryLocalSearchDecisionBuilder(
6278 const int size =
Size();
6279 DecisionBuilder* first_solution =
6280 GetFirstSolutionDecisionBuilder(search_parameters);
6281 LocalSearchPhaseParameters*
const parameters =
6282 CreateLocalSearchParameters(search_parameters,
false);
6283 SearchLimit* first_solution_lns_limit =
6284 GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit();
6285 DecisionBuilder*
const first_solution_sub_decision_builder =
6286 solver_->MakeSolveOnce(CreateSolutionFinalizer(search_parameters),
6287 first_solution_lns_limit);
6289 return solver_->MakeLocalSearchPhase(nexts_, first_solution,
6290 first_solution_sub_decision_builder,
6293 const int all_size = size + size + vehicles_;
6294 std::vector<IntVar*> all_vars(all_size);
6295 for (
int i = 0;
i < size; ++
i) {
6296 all_vars[
i] = nexts_[
i];
6298 for (
int i = size;
i < all_size; ++
i) {
6299 all_vars[
i] = vehicle_vars_[
i - size];
6301 return solver_->MakeLocalSearchPhase(all_vars, first_solution,
6302 first_solution_sub_decision_builder,
6306void RoutingModel::SetupDecisionBuilders(
6308 if (search_parameters.use_depth_first_search()) {
6309 SearchLimit* first_lns_limit =
6310 GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit();
6311 solve_db_ = solver_->Compose(
6312 GetFirstSolutionDecisionBuilder(search_parameters),
6313 solver_->MakeSolveOnce(CreateSolutionFinalizer(search_parameters),
6316 solve_db_ = CreatePrimaryLocalSearchDecisionBuilder(search_parameters);
6318 CHECK(preassignment_ !=
nullptr);
6319 DecisionBuilder* restore_preassignment =
6320 solver_->MakeRestoreAssignment(preassignment_);
6321 solve_db_ = solver_->Compose(restore_preassignment, solve_db_);
6324 solver_->Compose(restore_preassignment,
6325 solver_->MakeLocalSearchPhase(
6326 GetOrCreateAssignment(),
6327 CreateLocalSearchParameters(
6328 search_parameters,
false)));
6330 secondary_ls_db_ = solver_->MakeLocalSearchPhase(
6331 GetOrCreateAssignment(),
6332 CreateLocalSearchParameters(search_parameters,
true));
6333 secondary_ls_db_ = solver_->Compose(restore_preassignment, secondary_ls_db_);
6335 restore_assignment_ =
6336 solver_->Compose(solver_->MakeRestoreAssignment(GetOrCreateAssignment()),
6337 CreateSolutionFinalizer(search_parameters));
6338 restore_tmp_assignment_ = solver_->Compose(
6339 restore_preassignment,
6340 solver_->MakeRestoreAssignment(GetOrCreateTmpAssignment()),
6341 CreateSolutionFinalizer(search_parameters));
6344void RoutingModel::SetupMetaheuristics(
6346 BaseObjectiveMonitor* optimize =
nullptr;
6347 const auto build_metaheuristic = [
this, &search_parameters](
6350 BaseObjectiveMonitor* optimize =
nullptr;
6353 bool limit_too_long = !search_parameters.has_time_limit() &&
6354 search_parameters.solution_limit() ==
6355 std::numeric_limits<int64_t>::max();
6356 const int64_t optimization_step = std::max(
6359 switch (metaheuristic) {
6361 std::function<std::vector<std::pair<int64_t, int64_t>>(int64_t,
6363 same_class_arc_getter;
6364 if (search_parameters
6365 .guided_local_search_penalize_with_vehicle_classes()) {
6366 same_class_arc_getter =
6370 optimize = solver_->MakeGuidedLocalSearch(
6373 optimization_step, nexts_,
6374 search_parameters.guided_local_search_lambda_coefficient(),
6375 std::move(same_class_arc_getter),
6377 .guided_local_search_reset_penalties_on_new_best_solution());
6379 optimize = solver_->MakeGuidedLocalSearch(
6381 [
this](int64_t i, int64_t j, int64_t k) {
6384 optimization_step, nexts_, vehicle_vars_,
6385 search_parameters.guided_local_search_lambda_coefficient(),
6386 std::move(same_class_arc_getter),
6388 .guided_local_search_reset_penalties_on_new_best_solution());
6393 optimize = solver_->MakeSimulatedAnnealing(
false, cost_,
6394 optimization_step, 100);
6397 optimize = solver_->MakeTabuSearch(
false, cost_, optimization_step,
6398 nexts_, 10, 10, .8);
6401 std::vector<operations_research::IntVar*> tabu_vars;
6402 if (tabu_var_callback_) {
6403 tabu_vars = tabu_var_callback_(
this);
6405 tabu_vars.push_back(cost_);
6407 optimize = solver_->MakeGenericTabuSearch(
6408 false, cost_, optimization_step, tabu_vars, 100);
6412 limit_too_long =
false;
6413 OptimizeVar*
const minimize =
6414 solver_->MakeMinimize(cost_, optimization_step);
6415 optimize = minimize;
6416 minimize->SetOnOptimalFoundcallback([
this](int64_t value) {
6417 objective_lower_bound_ = std::max(objective_lower_bound_, value);
6420 if (limit_too_long) {
6422 <<
" specified without sane timeout: solve may run forever.";
6426 if (!search_parameters.local_search_metaheuristics().empty()) {
6427 std::vector<BaseObjectiveMonitor*> metaheuristics;
6428 for (
int i = 0;
i < search_parameters.local_search_metaheuristics_size();
6430 metaheuristics.push_back(build_metaheuristic(
6431 search_parameters.local_search_metaheuristics(i)));
6433 optimize = solver_->MakeRoundRobinCompoundObjectiveMonitor(
6435 search_parameters.num_max_local_optima_before_metaheuristic_switch());
6438 build_metaheuristic(search_parameters.local_search_metaheuristic());
6440 metaheuristic_ = optimize;
6441 monitors_.push_back(optimize);
6442 secondary_ls_monitors_.push_back(optimize);
6446 tabu_var_callback_ = std::move(tabu_var_callback);
6449void RoutingModel::SetupAssignmentCollector(
6451 Assignment* full_assignment = solver_->MakeAssignment();
6453 full_assignment->Add(dimension->cumuls());
6455 for (IntVar*
const extra_var : extra_vars_) {
6456 full_assignment->Add(extra_var);
6458 for (IntervalVar*
const extra_interval : extra_intervals_) {
6459 full_assignment->Add(extra_interval);
6461 full_assignment->Add(nexts_);
6462 full_assignment->Add(active_);
6463 full_assignment->Add(vehicle_vars_);
6464 full_assignment->AddObjective(cost_);
6466 collect_assignments_ = solver_->MakeNBestValueSolutionCollector(
6467 full_assignment, search_parameters.number_of_solutions_to_collect(),
6469 collect_secondary_ls_assignments_ = solver_->MakeNBestValueSolutionCollector(
6470 full_assignment, search_parameters.number_of_solutions_to_collect(),
6472 collect_one_assignment_ =
6473 solver_->MakeFirstSolutionCollector(full_assignment);
6474 monitors_.push_back(collect_assignments_);
6475 secondary_ls_monitors_.push_back(collect_secondary_ls_assignments_);
6478void RoutingModel::SetupTrace(
6480 if (search_parameters.log_search()) {
6481 Solver::SearchLogParameters search_log_parameters;
6482 search_log_parameters.branch_period = 10000;
6483 search_log_parameters.objective =
nullptr;
6484 search_log_parameters.variables = {cost_};
6485 search_log_parameters.scaling_factors = {
6486 search_parameters.log_cost_scaling_factor()};
6487 search_log_parameters.offsets = {search_parameters.log_cost_offset()};
6488 if (!search_parameters.log_tag().empty()) {
6489 const std::string& tag = search_parameters.log_tag();
6490 search_log_parameters.display_callback = [tag]() {
return tag; };
6492 search_log_parameters.display_callback =
nullptr;
6494 search_log_parameters.display_on_new_solutions_only =
false;
6495 search_log_ = solver_->MakeSearchLog(search_log_parameters);
6496 monitors_.push_back(search_log_);
6497 secondary_ls_monitors_.push_back(
6498 solver_->MakeSearchLog(std::move(search_log_parameters)));
6502void RoutingModel::SetupImprovementLimit(
6504 if (!search_parameters.has_improvement_limit_parameters())
return;
6506 SearchMonitor*
const improvement_limit = solver_->MakeImprovementLimit(
6507 cost_,
false, search_parameters.log_cost_scaling_factor(),
6508 search_parameters.log_cost_offset(),
6509 search_parameters.improvement_limit_parameters()
6510 .improvement_rate_coefficient(),
6511 search_parameters.improvement_limit_parameters()
6512 .improvement_rate_solutions_distance());
6513 monitors_.push_back(improvement_limit);
6514 secondary_ls_monitors_.push_back(improvement_limit);
6519template <
typename EndInitialPropagationCallback,
typename LocalOptimumCallback>
6522 LocalOptimumWatcher(
6524 EndInitialPropagationCallback end_initial_propagation_callback,
6525 LocalOptimumCallback local_optimum_callback)
6526 : SearchMonitor(solver),
6527 end_initial_propagation_callback_(
6528 std::move(end_initial_propagation_callback)),
6529 local_optimum_callback_(std::move(local_optimum_callback)) {}
6530 void Install()
override {
6534 void EndInitialPropagation()
override { end_initial_propagation_callback_(); }
6535 bool AtLocalOptimum()
override {
6536 local_optimum_callback_();
6541 EndInitialPropagationCallback end_initial_propagation_callback_;
6542 LocalOptimumCallback local_optimum_callback_;
6545template <
typename EndInitialPropagationCallback,
typename LocalOptimumCallback>
6548 EndInitialPropagationCallback end_initial_propagation_callback,
6549 LocalOptimumCallback local_optimum_callback) {
6550 return solver->RevAlloc(
new LocalOptimumWatcher<EndInitialPropagationCallback,
6551 LocalOptimumCallback>(
6552 solver, std::move(end_initial_propagation_callback),
6553 std::move(local_optimum_callback)));
6558void RoutingModel::SetupSearchMonitors(
6560 std::vector<SearchMonitor*> old_monitors = monitors_;
6562 for (
int i = 0;
i < monitors_before_setup_; ++
i) {
6563 monitors_.push_back(old_monitors[i]);
6565 monitors_.push_back(GetOrCreateLimit());
6566 monitors_.push_back(MakeLocalOptimumWatcher(
6569 objective_lower_bound_ =
6570 std::max(objective_lower_bound_,
CostVar()->Min());
6572 [
this]() { local_optimum_reached_ =
true; }));
6573 monitors_.push_back(
6574 solver_->MakeCustomLimit([
this]() ->
bool { return interrupt_cp_; }));
6576 secondary_ls_monitors_ = monitors_;
6578 SetupImprovementLimit(search_parameters);
6579 SetupMetaheuristics(search_parameters);
6580 SetupAssignmentCollector(search_parameters);
6581 SetupTrace(search_parameters);
6582 int new_monitors_after_setup = monitors_.size();
6583 for (
int i = monitors_after_setup_;
i < old_monitors.size(); ++
i) {
6584 monitors_.push_back(old_monitors[i]);
6586 monitors_after_setup_ = new_monitors_after_setup;
6589bool RoutingModel::UsesLightPropagation(
6600 finalizer_variables_->AddWeightedVariableTarget(var, target, cost);
6605 finalizer_variables_->AddWeightedVariableTarget(var,
kint64min, cost);
6610 finalizer_variables_->AddWeightedVariableTarget(var,
kint64max, cost);
6614 finalizer_variables_->AddVariableTarget(var, target);
6618 finalizer_variables_->AddVariableTarget(var,
kint64max);
6622 finalizer_variables_->AddVariableTarget(var,
kint64min);
6625void RoutingModel::SetupSearch(
6627 const std::string error =
6628 FindErrorInSearchParametersForModel(search_parameters);
6629 if (!error.empty()) {
6631 LOG(ERROR) <<
"Invalid RoutingSearchParameters for this model: " << error;
6634 SetupDecisionBuilders(search_parameters);
6635 SetupSearchMonitors(search_parameters);
6636 search_parameters_ = search_parameters;
6639void RoutingModel::UpdateSearchFromParametersIfNeeded(
6643 if (!google::protobuf::util::MessageDifferencer::Equivalent(
6644 search_parameters_, search_parameters)) {
6647 if (!error.empty()) {
6649 LOG(ERROR) <<
"Invalid RoutingSearchParameters: " << error;
6651 SetupSearch(search_parameters);
6654 VLOG(1) <<
"Search parameters:\n" << search_parameters;
6658 extra_vars_.push_back(var);
6662 extra_intervals_.push_back(interval);
6670 std::vector<int64_t> vehicle_capacities,
6671 const std::string& name,
6673 : vehicle_capacities_(std::move(vehicle_capacities)),
6674 base_dimension_(base_dimension),
6675 global_span_cost_coefficient_(0),
6677 index_(model->dimensions_.size()),
6679 global_optimizer_offset_(0) {
6680 CHECK(model !=
nullptr);
6681 vehicle_span_upper_bounds_.assign(model->vehicles(),
6682 std::numeric_limits<int64_t>::max());
6683 vehicle_span_cost_coefficients_.assign(model->vehicles(), 0);
6684 vehicle_slack_cost_coefficients_.assign(model->vehicles(), 0);
6688 std::vector<int64_t> vehicle_capacities,
6689 const std::string& name, SelfBased)
6693 cumul_var_piecewise_linear_cost_.clear();
6696void RoutingDimension::Initialize(
6697 absl::Span<const int> transit_evaluators,
6698 absl::Span<const int> cumul_dependent_transit_evaluators,
6699 absl::Span<const int> state_dependent_transit_evaluators,
6700 int64_t slack_max) {
6702 InitializeTransits(transit_evaluators, cumul_dependent_transit_evaluators,
6703 state_dependent_transit_evaluators, slack_max);
6706void RoutingDimension::InitializeCumuls() {
6707 Solver*
const solver = model_->solver();
6708 const int size = model_->Size() + model_->vehicles();
6709 const auto capacity_range = std::minmax_element(vehicle_capacities_.begin(),
6710 vehicle_capacities_.end());
6711 const int64_t min_capacity = *capacity_range.first;
6712 CHECK_GE(min_capacity, 0);
6713 const int64_t max_capacity = *capacity_range.second;
6714 solver->MakeIntVarArray(size, 0, max_capacity, name_, &cumuls_);
6716 for (
int v = 0; v < model_->vehicles(); v++) {
6717 const int64_t vehicle_capacity = vehicle_capacities_[v];
6718 cumuls_[model_->Start(v)]->SetMax(vehicle_capacity);
6719 cumuls_[model_->End(v)]->SetMax(vehicle_capacity);
6722 forbidden_intervals_.resize(size);
6723 capacity_vars_.clear();
6724 if (min_capacity != max_capacity) {
6725 solver->MakeIntVarArray(size, 0, std::numeric_limits<int64_t>::max(),
6727 for (
int i = 0;
i < size; ++
i) {
6728 IntVar*
const capacity_var = capacity_vars_[
i];
6729 if (i < model_->Size()) {
6730 IntVar*
const capacity_active = solver->MakeBoolVar();
6731 solver->AddConstraint(
6732 solver->MakeLessOrEqual(model_->ActiveVar(i), capacity_active));
6733 solver->AddConstraint(solver->MakeIsLessOrEqualCt(
6734 cumuls_[i], capacity_var, capacity_active));
6736 solver->AddConstraint(
6737 solver->MakeLessOrEqual(cumuls_[i], capacity_var));
6744void ComputeTransitClasses(absl::Span<const int> evaluator_indices,
6745 std::vector<int>* class_evaluators,
6746 std::vector<int>* vehicle_to_class) {
6747 CHECK(class_evaluators !=
nullptr);
6748 CHECK(vehicle_to_class !=
nullptr);
6749 class_evaluators->clear();
6750 vehicle_to_class->resize(evaluator_indices.size(), -1);
6751 absl::flat_hash_map<int, int64_t> evaluator_to_class;
6752 for (
int i = 0;
i < evaluator_indices.size(); ++
i) {
6753 const int evaluator_index = evaluator_indices[
i];
6754 const int new_class = class_evaluators->size();
6755 const int evaluator_class =
6757 if (evaluator_class == new_class) {
6758 class_evaluators->push_back(evaluator_index);
6760 (*vehicle_to_class)[
i] = evaluator_class;
6765void RoutingDimension::InitializeTransitVariables(int64_t slack_max) {
6766 CHECK(!class_evaluators_.empty());
6767 CHECK(base_dimension_ ==
nullptr ||
6768 !state_dependent_class_evaluators_.empty());
6770 Solver*
const solver = model_->solver();
6771 const int size = model_->Size();
6774 return (0 <=
index &&
index < state_dependent_vehicle_to_class_.size())
6775 ? state_dependent_vehicle_to_class_[
index]
6776 : state_dependent_class_evaluators_.size();
6778 const std::string slack_name = name_ +
" slack";
6779 const std::string transit_name = name_ +
" fixed transit";
6781 bool are_all_evaluators_positive =
true;
6782 for (
int class_evaluator : class_evaluators_) {
6783 if (
model()->transit_evaluator_sign_[class_evaluator] !=
6785 are_all_evaluators_positive =
false;
6789 const bool is_unary =
IsUnary();
6790 for (int64_t i = 0;
i < size; ++
i) {
6791 int64_t min_fixed_transit = std::numeric_limits<int64_t>::max();
6793 for (
int evaluator_index : class_evaluators_) {
6794 const auto& unary_transit_callback =
6795 model_->UnaryTransitCallbackOrNull(evaluator_index);
6796 DCHECK(unary_transit_callback !=
nullptr);
6798 std::min(min_fixed_transit, unary_transit_callback(i));
6801 fixed_transits_[
i] = solver->MakeIntVar(
6802 is_unary ? min_fixed_transit
6803 : are_all_evaluators_positive ? int64_t{0}
6804 : std::numeric_limits<int64_t>::min(),
6805 std::numeric_limits<int64_t>::max(), absl::StrCat(transit_name, i));
6807 if (base_dimension_ !=
nullptr) {
6808 if (state_dependent_class_evaluators_.size() == 1) {
6809 std::vector<IntVar*> transition_variables(cumuls_.size(),
nullptr);
6810 for (int64_t j = 0; j < cumuls_.size(); ++j) {
6811 transition_variables[j] =
6812 MakeRangeMakeElementExpr(
6814 ->StateDependentTransitCallback(
6815 state_dependent_class_evaluators_[0])(i, j)
6817 base_dimension_->CumulVar(i), solver)
6820 dependent_transits_[
i] =
6821 solver->MakeElement(transition_variables, model_->NextVar(i))
6824 IntVar*
const vehicle_class_var =
6826 ->MakeElement(dependent_vehicle_class_function,
6827 model_->VehicleVar(i))
6829 std::vector<IntVar*> transit_for_vehicle;
6830 transit_for_vehicle.reserve(state_dependent_class_evaluators_.size() +
6832 for (
int evaluator : state_dependent_class_evaluators_) {
6833 std::vector<IntVar*> transition_variables(cumuls_.size(),
nullptr);
6834 for (int64_t j = 0; j < cumuls_.size(); ++j) {
6835 transition_variables[j] =
6836 MakeRangeMakeElementExpr(
6837 model_->StateDependentTransitCallback(evaluator)(i, j)
6839 base_dimension_->CumulVar(i), solver)
6842 transit_for_vehicle.push_back(
6843 solver->MakeElement(transition_variables, model_->NextVar(i))
6846 transit_for_vehicle.push_back(solver->MakeIntConst(0));
6847 dependent_transits_[
i] =
6848 solver->MakeElement(transit_for_vehicle, vehicle_class_var)->Var();
6851 dependent_transits_[
i] = solver->MakeIntConst(0);
6855 IntExpr* transit_expr = fixed_transits_[
i];
6856 if (dependent_transits_[i]->Min() != 0 ||
6857 dependent_transits_[i]->Max() != 0) {
6858 transit_expr = solver->MakeSum(transit_expr, dependent_transits_[i]);
6861 if (slack_max == 0) {
6862 slacks_[
i] = solver->MakeIntConst(0);
6865 solver->MakeIntVar(0, slack_max, absl::StrCat(slack_name, i));
6866 transit_expr = solver->MakeSum(slacks_[i], transit_expr);
6868 transits_[
i] = transit_expr->Var();
6872void RoutingDimension::InitializeTransits(
6873 absl::Span<const int> transit_evaluators,
6874 absl::Span<const int> cumul_dependent_transit_evaluators,
6875 absl::Span<const int> state_dependent_transit_evaluators,
6876 int64_t slack_max) {
6877 CHECK_EQ(model_->vehicles(), transit_evaluators.size());
6878 CHECK(base_dimension_ ==
nullptr ||
6879 model_->vehicles() == state_dependent_transit_evaluators.size());
6880 const int size = model_->Size();
6881 transits_.resize(size,
nullptr);
6882 fixed_transits_.resize(size,
nullptr);
6883 slacks_.resize(size,
nullptr);
6884 dependent_transits_.resize(size,
nullptr);
6885 ComputeTransitClasses(transit_evaluators, &class_evaluators_,
6886 &vehicle_to_class_);
6887 ComputeTransitClasses(cumul_dependent_transit_evaluators,
6888 &cumul_dependent_class_evaluators_,
6889 &vehicle_to_cumul_dependent_class_);
6890 if (base_dimension_ !=
nullptr) {
6891 ComputeTransitClasses(state_dependent_transit_evaluators,
6892 &state_dependent_class_evaluators_,
6893 &state_dependent_vehicle_to_class_);
6896 InitializeTransitVariables(slack_max);
6902 std::vector<int64_t>* values) {
6903 const int num_nodes = path.size();
6904 values->resize(num_nodes - 1);
6905 for (
int i = 0; i < num_nodes - 1; ++i) {
6906 (*values)[i] = evaluator(path[i], path[i + 1]);
6911 : model_(model), occurrences_of_type_(model.GetNumberOfVisitTypes()) {}
6914 int vehicle,
const std::function<int64_t(int64_t)>& next_accessor) {
6921 for (
int pos = 0; pos < current_route_visits_.size(); pos++) {
6922 const int64_t current_visit = current_route_visits_[pos];
6923 const int type =
model_.GetVisitType(current_visit);
6929 DCHECK_LT(type, occurrences_of_type_.size());
6930 int& num_type_added = occurrences_of_type_[type].num_type_added_to_vehicle;
6931 int& num_type_removed =
6932 occurrences_of_type_[type].num_type_removed_from_vehicle;
6933 DCHECK_LE(num_type_removed, num_type_added);
6935 num_type_removed == num_type_added) {
6945 if (policy == VisitTypePolicy::TYPE_ADDED_TO_VEHICLE ||
6946 policy == VisitTypePolicy::TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED) {
6949 if (policy == VisitTypePolicy::TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED ||
6950 policy == VisitTypePolicy::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
6958 int vehicle,
const std::function<int64_t(int64_t)>& next_accessor) {
6961 std::fill(occurrences_of_type_.begin(), occurrences_of_type_.end(),
6962 TypeRegulationsChecker::TypePolicyOccurrence());
6967 current_route_visits_.clear();
6968 for (int64_t current =
model_.Start(vehicle); !
model_.IsEnd(current);
6969 current = next_accessor(current)) {
6970 const int type =
model_.GetVisitType(current);
6971 if (type >= 0 &&
model_.GetVisitTypePolicy(current) ==
6972 VisitTypePolicy::TYPE_ON_VEHICLE_UP_TO_VISIT) {
6973 occurrences_of_type_[type].position_of_last_type_on_vehicle_up_to_visit =
6974 current_route_visits_.size();
6976 current_route_visits_.push_back(current);
6996 const RoutingModel& model,
bool check_hard_incompatibilities)
6998 check_hard_incompatibilities_(check_hard_incompatibilities) {}
7002 (check_hard_incompatibilities_ &&
7011bool TypeIncompatibilityChecker::CheckTypeRegulations(
int type,
7012 VisitTypePolicy policy,
7014 if (policy == VisitTypePolicy::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
7019 for (
int incompatible_type :
7020 model_.GetTemporalTypeIncompatibilitiesOfType(type)) {
7025 if (check_hard_incompatibilities_) {
7026 for (
int incompatible_type :
7027 model_.GetHardTypeIncompatibilitiesOfType(type)) {
7037 return model_.HasTemporalTypeRequirements() ||
7038 model_.HasSameVehicleTypeRequirements();
7041bool TypeRequirementChecker::CheckRequiredTypesCurrentlyOnRoute(
7042 absl::Span<
const absl::flat_hash_set<int>> required_type_alternatives,
7044 for (
const absl::flat_hash_set<int>& requirement_alternatives :
7045 required_type_alternatives) {
7046 bool has_one_of_alternatives =
false;
7047 for (
int type_alternative : requirement_alternatives) {
7049 has_one_of_alternatives =
true;
7053 if (!has_one_of_alternatives) {
7060bool TypeRequirementChecker::CheckTypeRegulations(
int type,
7061 VisitTypePolicy policy,
7065 if (!CheckRequiredTypesCurrentlyOnRoute(
7066 model_.GetRequiredTypeAlternativesWhenAddingType(type), pos)) {
7071 if (!CheckRequiredTypesCurrentlyOnRoute(
7072 model_.GetRequiredTypeAlternativesWhenRemovingType(type), pos)) {
7077 !
model_.GetSameVehicleRequiredTypeAlternativesOfType(type).empty()) {
7078 types_with_same_vehicle_requirements_on_route_.insert(type);
7084 for (
int type : types_with_same_vehicle_requirements_on_route_) {
7085 for (
const absl::flat_hash_set<int>& requirement_alternatives :
7086 model_.GetSameVehicleRequiredTypeAlternativesOfType(type)) {
7087 bool has_one_of_alternatives =
false;
7088 for (
const int type_alternative : requirement_alternatives) {
7090 has_one_of_alternatives =
true;
7094 if (!has_one_of_alternatives) {
7105 incompatibility_checker_(model,
true),
7106 requirement_checker_(model),
7107 vehicle_demons_(model.vehicles()) {}
7109void TypeRegulationsConstraint::PropagateNodeRegulations(
int node) {
7110 DCHECK_LT(node, model_.Size());
7111 if (!model_.VehicleVar(node)->Bound() || !model_.NextVar(node)->Bound()) {
7115 const int vehicle = model_.VehicleVar(node)->Min();
7116 if (vehicle < 0)
return;
7117 DCHECK(vehicle_demons_[vehicle] !=
nullptr);
7121void TypeRegulationsConstraint::CheckRegulationsOnVehicle(
int vehicle) {
7122 const auto next_accessor = [
this, vehicle](int64_t node) {
7123 if (model_.NextVar(node)->Bound()) {
7124 return model_.NextVar(node)->Value();
7127 return model_.End(vehicle);
7129 if (!incompatibility_checker_.
CheckVehicle(vehicle, next_accessor) ||
7130 !requirement_checker_.
CheckVehicle(vehicle, next_accessor)) {
7136 for (
int vehicle = 0; vehicle < model_.vehicles(); vehicle++) {
7138 solver(),
this, &TypeRegulationsConstraint::CheckRegulationsOnVehicle,
7139 "CheckRegulationsOnVehicle", vehicle);
7141 for (
int node = 0; node < model_.Size(); node++) {
7143 solver(),
this, &TypeRegulationsConstraint::PropagateNodeRegulations,
7144 "PropagateNodeRegulations", node);
7145 model_.NextVar(node)->WhenBound(node_demon);
7146 model_.VehicleVar(node)->WhenBound(node_demon);
7151 for (
int vehicle = 0; vehicle < model_.
vehicles(); vehicle++) {
7152 CheckRegulationsOnVehicle(vehicle);
7156void RoutingDimension::CloseModel(
bool use_light_propagation) {
7157 Solver*
const solver = model_->solver();
7158 const auto capacity_lambda = [
this](int64_t vehicle) {
7159 return vehicle >= 0 ? vehicle_capacities_[vehicle]
7160 : std::numeric_limits<int64_t>::max();
7162 for (
int i = 0;
i < capacity_vars_.size(); ++
i) {
7163 IntVar*
const vehicle_var = model_->VehicleVar(i);
7164 IntVar*
const capacity_var = capacity_vars_[
i];
7165 if (use_light_propagation) {
7166 solver->AddConstraint(solver->MakeLightElement(
7167 capacity_lambda, capacity_var, vehicle_var,
7168 [
this]() { return model_->enable_deep_serialization_; }));
7170 solver->AddConstraint(solver->MakeEquality(
7172 solver->MakeElement(capacity_lambda, vehicle_var)->Var()));
7175 for (
int i = 0;
i < fixed_transits_.size(); ++
i) {
7176 IntVar*
const next_var = model_->NextVar(i);
7177 IntVar*
const fixed_transit = fixed_transits_[
i];
7178 const auto transit_vehicle_evaluator = [
this,
i](int64_t
to,
7179 int64_t eval_index) {
7182 if (use_light_propagation) {
7183 if (class_evaluators_.size() == 1) {
7184 const int class_evaluator_index = class_evaluators_[0];
7185 const auto& unary_callback =
7186 model_->UnaryTransitCallbackOrNull(class_evaluator_index);
7187 if (unary_callback ==
nullptr) {
7188 solver->AddConstraint(solver->MakeLightElement(
7189 [
this, i](int64_t
to) {
7190 return model_->TransitCallback(class_evaluators_[0])(i, to);
7192 fixed_transit, next_var,
7193 [
this]() { return model_->enable_deep_serialization_; }));
7195 fixed_transit->SetValue(unary_callback(i));
7198 solver->AddConstraint(solver->MakeLightElement(
7199 transit_vehicle_evaluator, fixed_transit, next_var,
7200 model_->VehicleVar(i),
7201 [
this]() { return model_->enable_deep_serialization_; }));
7204 if (class_evaluators_.size() == 1) {
7205 const int class_evaluator_index = class_evaluators_[0];
7206 const auto& unary_callback =
7207 model_->UnaryTransitCallbackOrNull(class_evaluator_index);
7208 if (unary_callback ==
nullptr) {
7209 solver->AddConstraint(solver->MakeEquality(
7210 fixed_transit, solver
7212 [
this, i](int64_t
to) {
7213 return model_->TransitCallback(
7214 class_evaluators_[0])(i, to);
7219 fixed_transit->SetValue(unary_callback(i));
7222 solver->AddConstraint(solver->MakeEquality(
7223 fixed_transit, solver
7224 ->MakeElement(transit_vehicle_evaluator,
7225 next_var, model_->VehicleVar(i))
7231 solver->AddConstraint(
7235 for (
int v = 0; v < model_->vehicles(); ++v) {
7237 const int num_breaks = breaks.size();
7241 for (
int b = 1;
b < num_breaks; ++
b) {
7242 Constraint* precedence = solver->MakeIntervalVarRelation(
7244 solver->AddConstraint(precedence);
7248 for (
IntVar* cumul : cumuls_) {
7249 model_->AddVariableMinimizedByFinalizer(cumul);
7255 int64_t vehicle)
const {
7261 for (
const int evaluator_index : class_evaluators_) {
7262 if (
model()->transit_evaluator_sign_[evaluator_index] !=
7271 int64_t index, int64_t min_value, int64_t max_value)
const {
7272 SortedDisjointIntervalList allowed;
7273 const SortedDisjointIntervalList& forbidden = forbidden_intervals_[
index];
7274 IntVar*
const cumul_var = cumuls_[
index];
7275 const int64_t min = std::max(min_value, cumul_var->Min());
7276 const int64_t max = std::min(max_value, cumul_var->Max());
7277 int64_t next_start = min;
7279 forbidden.FirstIntervalGreaterOrEqual(min);
7280 interval != forbidden.end(); ++interval) {
7281 if (next_start > max)
break;
7282 if (next_start < interval->start) {
7283 allowed.InsertInterval(next_start,
CapSub(interval->start, 1));
7285 next_start =
CapAdd(interval->end, 1);
7287 if (next_start <= max) {
7288 allowed.InsertInterval(next_start, max);
7295 CHECK_GE(vehicle, 0);
7296 CHECK_LT(vehicle, vehicle_span_upper_bounds_.size());
7297 CHECK_GE(upper_bound, 0);
7298 vehicle_span_upper_bounds_[vehicle] = upper_bound;
7303 CHECK_GE(vehicle, 0);
7304 CHECK_LT(vehicle, vehicle_span_cost_coefficients_.size());
7305 CHECK_GE(coefficient, 0);
7306 vehicle_span_cost_coefficients_[vehicle] = coefficient;
7310 int64_t coefficient) {
7311 CHECK_GE(coefficient, 0);
7312 vehicle_span_cost_coefficients_.assign(model_->vehicles(), coefficient);
7316 CHECK_GE(coefficient, 0);
7317 global_span_cost_coefficient_ = coefficient;
7322 CHECK_GE(vehicle, 0);
7323 CHECK_LT(vehicle, vehicle_slack_cost_coefficients_.size());
7324 CHECK_GE(coefficient, 0);
7325 vehicle_slack_cost_coefficients_[vehicle] = coefficient;
7328 int64_t coefficient) {
7329 CHECK_GE(coefficient, 0);
7330 vehicle_slack_cost_coefficients_.assign(model_->
vehicles(), coefficient);
7334 int64_t index,
const PiecewiseLinearFunction& cost) {
7335 if (!cost.IsNonDecreasing()) {
7336 LOG(WARNING) <<
"Only non-decreasing cost functions are supported.";
7339 if (cost.Value(0) < 0) {
7340 LOG(WARNING) <<
"Only positive cost functions are supported.";
7343 if (
index >= cumul_var_piecewise_linear_cost_.size()) {
7344 cumul_var_piecewise_linear_cost_.resize(
index + 1);
7346 PiecewiseLinearCost& piecewise_linear_cost =
7347 cumul_var_piecewise_linear_cost_[
index];
7348 piecewise_linear_cost.var = cumuls_[
index];
7349 piecewise_linear_cost.cost = std::make_unique<PiecewiseLinearFunction>(cost);
7353 return (
index < cumul_var_piecewise_linear_cost_.size() &&
7354 cumul_var_piecewise_linear_cost_[
index].var !=
nullptr);
7358 int64_t index)
const {
7359 if (
index < cumul_var_piecewise_linear_cost_.size() &&
7360 cumul_var_piecewise_linear_cost_[
index].var !=
nullptr) {
7361 return cumul_var_piecewise_linear_cost_[
index].cost.get();
7369 Solver*
const solver = model->solver();
7370 if (model->IsStart(index) || model->IsEnd(index)) {
7371 const int vehicle = model->VehicleIndex(index);
7372 DCHECK_GE(vehicle, 0);
7373 return solver->MakeProd(expr, model->VehicleRouteConsideredVar(vehicle))
7376 return solver->
MakeProd(expr, model->ActiveVar(index))->
Var();
7380void RoutingDimension::SetupCumulVarPiecewiseLinearCosts(
7381 std::vector<IntVar*>* cost_elements)
const {
7382 CHECK(cost_elements !=
nullptr);
7383 Solver*
const solver = model_->solver();
7384 for (
int i = 0;
i < cumul_var_piecewise_linear_cost_.size(); ++
i) {
7385 const PiecewiseLinearCost& piecewise_linear_cost =
7386 cumul_var_piecewise_linear_cost_[
i];
7387 if (piecewise_linear_cost.var !=
nullptr) {
7388 IntExpr*
const expr = solver->MakePiecewiseLinearExpr(
7389 piecewise_linear_cost.var, *piecewise_linear_cost.cost);
7390 IntVar* cost_var = BuildVarFromExprAndIndexActiveState(model_, expr, i);
7391 cost_elements->push_back(cost_var);
7394 model_->AddWeightedVariableMinimizedByFinalizer(cost_var, 0);
7400 int64_t upper_bound,
7401 int64_t coefficient) {
7402 if (
index >= cumul_var_soft_upper_bound_.size()) {
7403 cumul_var_soft_upper_bound_.resize(
index + 1, {
nullptr, 0, 0});
7405 cumul_var_soft_upper_bound_[
index] = {cumuls_[
index], upper_bound,
7410 return (
index < cumul_var_soft_upper_bound_.size() &&
7411 cumul_var_soft_upper_bound_[
index].var !=
nullptr);
7415 if (
index < cumul_var_soft_upper_bound_.size() &&
7416 cumul_var_soft_upper_bound_[
index].var !=
nullptr) {
7417 return cumul_var_soft_upper_bound_[
index].bound;
7419 return cumuls_[
index]->Max();
7423 int64_t index)
const {
7424 if (
index < cumul_var_soft_upper_bound_.size() &&
7425 cumul_var_soft_upper_bound_[
index].var !=
nullptr) {
7426 return cumul_var_soft_upper_bound_[
index].coefficient;
7431void RoutingDimension::SetupCumulVarSoftUpperBoundCosts(
7432 std::vector<IntVar*>* cost_elements)
const {
7433 CHECK(cost_elements !=
nullptr);
7434 Solver*
const solver = model_->solver();
7435 for (
int i = 0;
i < cumul_var_soft_upper_bound_.size(); ++
i) {
7436 const SoftBound& soft_bound = cumul_var_soft_upper_bound_[
i];
7437 if (soft_bound.var !=
nullptr) {
7438 IntExpr*
const expr = solver->MakeSemiContinuousExpr(
7439 solver->MakeSum(soft_bound.var, -soft_bound.bound), 0,
7440 soft_bound.coefficient);
7441 IntVar* cost_var = BuildVarFromExprAndIndexActiveState(model_, expr, i);
7442 cost_elements->push_back(cost_var);
7445 model_->AddWeightedVariableMinimizedByFinalizer(cost_var,
7446 soft_bound.coefficient);
7452 int64_t lower_bound,
7453 int64_t coefficient) {
7454 if (
index >= cumul_var_soft_lower_bound_.size()) {
7455 cumul_var_soft_lower_bound_.resize(
index + 1, {
nullptr, 0, 0});
7457 cumul_var_soft_lower_bound_[
index] = {cumuls_[
index], lower_bound,
7462 return (
index < cumul_var_soft_lower_bound_.size() &&
7463 cumul_var_soft_lower_bound_[
index].var !=
nullptr);
7467 if (
index < cumul_var_soft_lower_bound_.size() &&
7468 cumul_var_soft_lower_bound_[
index].var !=
nullptr) {
7469 return cumul_var_soft_lower_bound_[
index].bound;
7471 return cumuls_[
index]->Min();
7475 int64_t index)
const {
7476 if (
index < cumul_var_soft_lower_bound_.size() &&
7477 cumul_var_soft_lower_bound_[
index].var !=
nullptr) {
7478 return cumul_var_soft_lower_bound_[
index].coefficient;
7483void RoutingDimension::SetupCumulVarSoftLowerBoundCosts(
7484 std::vector<IntVar*>* cost_elements)
const {
7485 CHECK(cost_elements !=
nullptr);
7486 Solver*
const solver = model_->solver();
7487 for (
int i = 0;
i < cumul_var_soft_lower_bound_.size(); ++
i) {
7488 const SoftBound& soft_bound = cumul_var_soft_lower_bound_[
i];
7489 if (soft_bound.var !=
nullptr) {
7490 IntExpr*
const expr = solver->MakeSemiContinuousExpr(
7491 solver->MakeDifference(soft_bound.bound, soft_bound.var), 0,
7492 soft_bound.coefficient);
7493 IntVar* cost_var = BuildVarFromExprAndIndexActiveState(model_, expr, i);
7494 cost_elements->push_back(cost_var);
7497 model_->AddWeightedVariableMinimizedByFinalizer(cost_var,
7498 soft_bound.coefficient);
7503void RoutingDimension::SetupGlobalSpanCost(
7504 std::vector<IntVar*>* cost_elements)
const {
7505 CHECK(cost_elements !=
nullptr);
7506 Solver*
const solver = model_->solver();
7507 if (global_span_cost_coefficient_ != 0) {
7508 std::vector<IntVar*> end_cumuls;
7509 for (
int i = 0;
i < model_->vehicles(); ++
i) {
7510 end_cumuls.push_back(solver
7511 ->MakeProd(model_->vehicle_route_considered_[i],
7512 cumuls_[model_->End(i)])
7515 IntVar*
const max_end_cumul = solver->MakeMax(end_cumuls)->Var();
7516 model_->AddWeightedVariableMinimizedByFinalizer(
7517 max_end_cumul, global_span_cost_coefficient_);
7518 std::vector<IntVar*> start_cumuls;
7519 for (
int i = 0;
i < model_->vehicles(); ++
i) {
7520 IntVar* global_span_cost_start_cumul =
7521 solver->MakeIntVar(0, std::numeric_limits<int64_t>::max());
7522 solver->AddConstraint(solver->MakeIfThenElseCt(
7523 model_->vehicle_route_considered_[i], cumuls_[model_->Start(i)],
7524 max_end_cumul, global_span_cost_start_cumul));
7525 start_cumuls.push_back(global_span_cost_start_cumul);
7527 IntVar*
const min_start_cumul = solver->MakeMin(start_cumuls)->Var();
7528 model_->AddWeightedVariableMaximizedByFinalizer(
7529 min_start_cumul, global_span_cost_coefficient_);
7533 if (model_->vehicles() == 1) {
7534 for (
int var_index = 0; var_index < model_->Size(); ++var_index) {
7535 model_->AddWeightedVariableMinimizedByFinalizer(
7536 slacks_[var_index], global_span_cost_coefficient_);
7537 cost_elements->push_back(
7540 model_->vehicle_route_considered_[0],
7543 solver->MakeSum(transits_[var_index],
7544 dependent_transits_[var_index]),
7545 global_span_cost_coefficient_),
7546 model_->ActiveVar(var_index)))
7550 IntVar*
const end_range =
7551 solver->MakeDifference(max_end_cumul, min_start_cumul)->Var();
7552 end_range->SetMin(0);
7553 cost_elements->push_back(
7554 solver->MakeProd(end_range, global_span_cost_coefficient_)->Var());
7560 std::vector<IntervalVar*> breaks,
int vehicle,
7561 std::vector<int64_t> node_visit_transits) {
7562 if (breaks.empty())
return;
7564 [node_visit_transits = std::move(node_visit_transits)](
7565 int64_t from, int64_t ) {
return node_visit_transits[from]; },
7571 std::vector<IntervalVar*> breaks,
int vehicle,
7572 std::vector<int64_t> node_visit_transits,
7573 std::function<int64_t(int64_t, int64_t)> delays) {
7574 if (breaks.empty())
return;
7576 [node_visit_transits = std::move(node_visit_transits)](
7577 int64_t from, int64_t ) {
return node_visit_transits[from]; },
7586 std::vector<IntervalVar*> breaks,
int vehicle,
int pre_travel_evaluator,
7587 int post_travel_evaluator) {
7588 DCHECK_LE(0, vehicle);
7589 DCHECK_LT(vehicle, model_->
vehicles());
7590 if (breaks.empty())
return;
7592 vehicle_break_intervals_[vehicle] = std::move(breaks);
7593 vehicle_pre_travel_evaluators_[vehicle] = pre_travel_evaluator;
7594 vehicle_post_travel_evaluators_[vehicle] = post_travel_evaluator;
7596 for (
IntervalVar*
const interval : vehicle_break_intervals_[vehicle]) {
7598 if (interval->MayBePerformed() && !interval->MustBePerformed()) {
7602 std::numeric_limits<int64_t>::min());
7604 std::numeric_limits<int64_t>::min());
7608 model_->AddVariableTargetToFinalizer(
CumulVar(model_->End(vehicle)),
7609 std::numeric_limits<int64_t>::min());
7610 model_->AddVariableTargetToFinalizer(
CumulVar(model_->Start(vehicle)),
7611 std::numeric_limits<int64_t>::max());
7615 DCHECK(!break_constraints_are_initialized_);
7616 const int num_vehicles = model_->
vehicles();
7617 vehicle_break_intervals_.resize(num_vehicles);
7618 vehicle_pre_travel_evaluators_.resize(num_vehicles, -1);
7619 vehicle_post_travel_evaluators_.resize(num_vehicles, -1);
7620 vehicle_break_distance_duration_.resize(num_vehicles);
7621 break_constraints_are_initialized_ =
true;
7625 return break_constraints_are_initialized_;
7629 int vehicle)
const {
7630 DCHECK_LE(0, vehicle);
7631 DCHECK_LT(vehicle, vehicle_break_intervals_.size());
7632 return vehicle_break_intervals_[vehicle];
7636 DCHECK_LE(0, vehicle);
7637 DCHECK_LT(vehicle, vehicle_pre_travel_evaluators_.size());
7638 return vehicle_pre_travel_evaluators_[vehicle];
7642 DCHECK_LE(0, vehicle);
7643 DCHECK_LT(vehicle, vehicle_post_travel_evaluators_.size());
7644 return vehicle_post_travel_evaluators_[vehicle];
7650 DCHECK_LE(0, vehicle);
7651 DCHECK_LT(vehicle, model_->
vehicles());
7653 vehicle_break_distance_duration_[vehicle].emplace_back(distance, duration);
7656 model_->AddVariableTargetToFinalizer(
CumulVar(model_->End(vehicle)),
7657 std::numeric_limits<int64_t>::min());
7658 model_->AddVariableTargetToFinalizer(
CumulVar(model_->Start(vehicle)),
7659 std::numeric_limits<int64_t>::max());
7662const std::vector<std::pair<int64_t, int64_t>>&
7664 DCHECK_LE(0, vehicle);
7665 DCHECK_LT(vehicle, vehicle_break_distance_duration_.size());
7666 return vehicle_break_distance_duration_[vehicle];
7670 PickupToDeliveryLimitFunction limit_function,
int pair_index) {
7671 CHECK_GE(pair_index, 0);
7672 if (pair_index >= pickup_to_delivery_limits_per_pair_index_.size()) {
7673 pickup_to_delivery_limits_per_pair_index_.resize(pair_index + 1);
7675 pickup_to_delivery_limits_per_pair_index_[pair_index] =
7676 std::move(limit_function);
7680 return !pickup_to_delivery_limits_per_pair_index_.empty();
7684 int pair_index,
int pickup_alternative_index,
7685 int delivery_alternative_index)
const {
7686 DCHECK_GE(pair_index, 0);
7688 if (pair_index >= pickup_to_delivery_limits_per_pair_index_.size()) {
7689 return std::numeric_limits<int64_t>::max();
7692 pickup_to_delivery_limits_per_pair_index_[pair_index];
7693 if (!pickup_to_delivery_limit_function) {
7695 return std::numeric_limits<int64_t>::max();
7697 DCHECK_GE(pickup_alternative_index, 0);
7698 DCHECK_GE(delivery_alternative_index, 0);
7699 return pickup_to_delivery_limit_function(pickup_alternative_index,
7700 delivery_alternative_index);
7703void RoutingDimension::SetupSlackAndDependentTransitCosts()
const {
7704 if (model_->vehicles() == 0)
return;
7706 if (absl::c_all_of(vehicle_span_cost_coefficients_,
7707 [](int64_t c) {
return c == 0; }) &&
7708 absl::c_all_of(vehicle_slack_cost_coefficients_,
7709 [](int64_t c) {
return c == 0; })) {
7721 std::vector<const RoutingDimension*> dimensions_with_relevant_slacks = {
this};
7724 dimensions_with_relevant_slacks.back()->base_dimension_;
7725 if (next ==
nullptr || next == dimensions_with_relevant_slacks.back()) {
7728 dimensions_with_relevant_slacks.push_back(next);
7731 for (
auto it = dimensions_with_relevant_slacks.rbegin();
7732 it != dimensions_with_relevant_slacks.rend(); ++it) {
7733 for (
int i = 0;
i < model_->vehicles(); ++
i) {
7734 model_->AddVariableTargetToFinalizer((*it)->cumuls_[model_->End(i)],
7735 std::numeric_limits<int64_t>::min());
7736 model_->AddVariableTargetToFinalizer((*it)->cumuls_[model_->Start(i)],
7737 std::numeric_limits<int64_t>::max());
7739 for (IntVar*
const slack : (*it)->slacks_) {
7740 model_->AddVariableTargetToFinalizer(slack,
7741 std::numeric_limits<int64_t>::min());
E * AddAtPosition(V *var, int position)
int64_t Value(const IntVar *var) const
IntContainer * MutableIntVarContainer()
int64_t Max(const IntVar *var) const
int64_t Min(const IntVar *var) const
bool Contains(const IntVar *var) const
void SetValue(const IntVar *var, int64_t value)
IntVarElement * Add(IntVar *var)
AssignmentContainer< IntVar, IntVarElement > IntContainer
bool Bound(const IntVar *var) const
void CopyIntersection(const Assignment *assignment)
void AddObjective(IntVar *const v)
static constexpr Value PATH_MOST_CONSTRAINED_ARC
static constexpr Value PARALLEL_SAVINGS
FirstSolutionStrategy_Value Value
static const ::std::string & Value_Name(T value)
static constexpr Value UNSET
static constexpr Value LOCAL_CHEAPEST_INSERTION
static constexpr Value AUTOMATIC
static constexpr Value SEQUENTIAL_CHEAPEST_INSERTION
static constexpr Value PATH_CHEAPEST_ARC
static constexpr Value CHRISTOFIDES
static constexpr Value LOCAL_CHEAPEST_ARC
static constexpr Value LOCAL_CHEAPEST_COST_INSERTION
static constexpr Value FIRST_UNBOUND_MIN_VALUE
static constexpr Value EVALUATOR_STRATEGY
static constexpr Value SWEEP
static constexpr Value BEST_INSERTION
static constexpr Value ALL_UNPERFORMED
static constexpr Value GLOBAL_CHEAPEST_ARC
static constexpr Value SAVINGS
static constexpr Value PARALLEL_CHEAPEST_INSERTION
virtual int64_t Min() const =0
virtual IntVar * Var()=0
Creates a variable from the expression.
virtual int64_t Max() const =0
Generic filter-based decision builder using an IntVarFilteredHeuristic.
int64_t number_of_rejects() const
int64_t number_of_decisions() const
Returns statistics from its underlying heuristic.
virtual bool Contains(int64_t v) const =0
virtual uint64_t Size() const =0
This method returns the number of values in the domain of the variable.
void SetArcCost(ArcIndex arc, CostValue cost)
CostValue GetCost() const
The base class for all local search operators.
static IntOut SafeRound(FloatIn x)
void EnqueueDelayedDemon(Demon *const d)
void UpdateLimits(absl::Duration time, int64_t branches, int64_t failures, int64_t solutions)
void SetCumulVarSoftUpperBound(int64_t index, int64_t upper_bound, int64_t coefficient)
bool HasBreakConstraints() const
Returns true if any break interval or break distance was defined.
int64_t GetCumulVarSoftUpperBoundCoefficient(int64_t index) const
int64_t GetTransitValue(int64_t from_index, int64_t to_index, int64_t vehicle) const
bool HasPickupToDeliveryLimits() const
const std::vector< operations_research::IntVar * > & cumuls() const
int64_t GetPickupToDeliveryLimitForPair(int pair_index, int pickup_alternative_index, int delivery_alternative_index) const
void SetSpanCostCoefficientForAllVehicles(int64_t coefficient)
RoutingModel::TransitEvaluatorSign GetTransitEvaluatorSign(int vehicle) const
int64_t GetCumulVarSoftUpperBound(int64_t index) const
void SetSpanUpperBoundForVehicle(int64_t upper_bound, int vehicle)
void SetBreakIntervalsOfVehicle(std::vector< IntervalVar * > breaks, int vehicle, int pre_travel_evaluator, int post_travel_evaluator)
void SetSlackCostCoefficientForAllVehicles(int64_t coefficient)
const std::vector< IntervalVar * > & GetBreakIntervalsOfVehicle(int vehicle) const
Returns the break intervals set by SetBreakIntervalsOfVehicle().
bool HasCumulVarSoftUpperBound(int64_t index) const
void SetCumulVarSoftLowerBound(int64_t index, int64_t lower_bound, int64_t coefficient)
void SetPickupToDeliveryLimitFunctionForPair(PickupToDeliveryLimitFunction limit_function, int pair_index)
bool HasCumulVarPiecewiseLinearCost(int64_t index) const
int64_t GetCumulVarSoftLowerBound(int64_t index) const
bool IsUnary() const
Returns true iff all transit evaluators for this dimension are unary.
int GetPostTravelEvaluatorOfVehicle(int vehicle) const
RoutingModel * model() const
Returns the model on which the dimension was created.
SortedDisjointIntervalList GetAllowedIntervalsInRange(int64_t index, int64_t min_value, int64_t max_value) const
Returns allowed intervals for a given node in a given interval.
const RoutingModel::TransitCallback1 & GetUnaryTransitEvaluator(int vehicle) const
const PiecewiseLinearFunction * GetCumulVarPiecewiseLinearCost(int64_t index) const
operations_research::RoutingDimensionIndex index() const
Returns the index of the dimension in the model.
const RoutingModel::TransitCallback2 & transit_evaluator(int vehicle) const
bool HasCumulVarSoftLowerBound(int64_t index) const
const std::vector< int64_t > & vehicle_capacities() const
Returns the capacities for all vehicles.
std::function< int64_t(int, int)> PickupToDeliveryLimitFunction
RoutingDimension(const RoutingDimension &)=delete
operations_research::IntVar * CumulVar(int64_t index) const
void SetBreakDistanceDurationOfVehicle(int64_t distance, int64_t duration, int vehicle)
int64_t GetCumulVarSoftLowerBoundCoefficient(int64_t index) const
void SetCumulVarPiecewiseLinearCost(int64_t index, const PiecewiseLinearFunction &cost)
bool AllTransitEvaluatorSignsAreUnknown() const
void SetSlackCostCoefficientForVehicle(int64_t coefficient, int vehicle)
const std::vector< std::pair< int64_t, int64_t > > & GetBreakDistanceDurationOfVehicle(int vehicle) const
int GetPreTravelEvaluatorOfVehicle(int vehicle) const
!defined(SWIGPYTHON)
void SetGlobalSpanCostCoefficient(int64_t coefficient)
void SetSpanCostCoefficientForVehicle(int64_t coefficient, int vehicle)
Manager for any NodeIndex <-> variable index conversion.
const ::operations_research::ConstraintSolverParameters & solver_parameters() const
bool has_solver_parameters() const
static const char kRemoveValues[]
static const char kLightElement[]
Constraint types.
static const char kLightElement2[]
void ComputeNeighbors(const NodeNeighborsParameters ¶ms)
Attributes for a dimension.
int AddResource(Attributes attributes, const RoutingDimension *dimension)
bool IsResourceAllowedForVehicle(int resource, int vehicle) const
void NotifyVehicleRequiresAResource(int vehicle)
SecondaryOptimizer(RoutingModel *model, RoutingSearchParameters *search_parameters, int64_t solve_period)
bool Solve(const std::vector< RoutingModel::VariableValuePair > &in_state, std::vector< RoutingModel::VariableValuePair > *out_state)
friend class RoutingModelInspector
int RegisterUnaryTransitVector(std::vector< int64_t > values)
void SetPathEnergyCostOfVehicle(const std::string &force, const std::string &distance, int64_t cost_per_unit, int vehicle)
bool HasHardTypeIncompatibilities() const
void AddPickupAndDeliverySets(DisjunctionIndex pickup_disjunction, DisjunctionIndex delivery_disjunction)
int64_t Size() const
Returns the number of next variables in the model.
void AddSameVehicleRequiredTypeAlternatives(int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
int64_t Next(const operations_research::Assignment &assignment, int64_t index) const
bool HasLocalCumulOptimizer(const RoutingDimension &dimension) const
bool ApplyLocksToAllVehicles(const std::vector< std::vector< int64_t > > &locks, bool close_routes)
void AddHardTypeIncompatibility(int type1, int type2)
void AddWeightedVariableMaximizedByFinalizer(operations_research::IntVar *var, int64_t cost)
void SetPickupAndDeliveryPolicyOfAllVehicles(PickupAndDeliveryPolicy policy)
bool HasTemporalTypeRequirements() const
operations_research::IntVar * ApplyLocks(absl::Span< const int64_t > locks)
std::pair< int, bool > AddConstantDimensionWithSlack(int64_t value, int64_t capacity, int64_t slack_max, bool fix_start_cumul_to_zero, const std::string &name)
RoutingModel(const RoutingIndexManager &index_manager)
CostClassIndex GetCostClassIndexOfVehicle(int64_t vehicle) const
Get the cost class index of the given vehicle.
void SetVisitType(int64_t index, int type, VisitTypePolicy type_policy)
bool HasMaxCardinalityConstrainedDisjunctions() const
std::optional< PickupDeliveryPosition > GetPickupPosition(int64_t node_index) const
Returns the pickup and delivery positions where the node is a pickup.
void IgnoreDisjunctionsAlreadyForcedToZero()
int GetVisitType(int64_t index) const
std::vector< RoutingDimension * > GetUnaryDimensions() const
Returns dimensions for which all transit evaluators are unary.
int RegisterUnaryTransitCallback(TransitCallback1 callback, TransitEvaluatorSign sign=kTransitEvaluatorSignUnknown)
void SetPickupAndDeliveryPolicyOfVehicle(PickupAndDeliveryPolicy policy, int vehicle)
bool AreRoutesInterdependent(const RoutingSearchParameters ¶meters) const
bool HasTemporalTypeIncompatibilities() const
const operations_research::Assignment * SolveWithIteratedLocalSearch(const RoutingSearchParameters &search_parameters)
int64_t GetNumberOfDecisionsInFirstSolution(const RoutingSearchParameters &search_parameters) const
int64_t Start(int vehicle) const
const operations_research::Assignment * PackCumulsOfOptimizerDimensionsFromAssignment(const operations_research::Assignment *original_assignment, absl::Duration duration_limit, bool *time_limit_was_reached=nullptr)
std::optional< int64_t > GetFirstMatchingPickupDeliverySibling(int64_t node, const std::function< bool(int64_t)> &is_match) const
const VehicleTypeContainer & GetVehicleTypeContainer() const
RoutingDisjunctionIndex DisjunctionIndex
void AddSearchMonitor(SearchMonitor *monitor)
Adds a search monitor to the search used to solve the routing model.
operations_research::IntVar * ActiveVar(int64_t index) const
Returns the active variable of the node corresponding to index.
int64_t GetArcCostForClass(int64_t from_index, int64_t to_index, int64_t cost_class_index) const
void SetAssignmentFromOtherModelAssignment(operations_research::Assignment *target_assignment, const RoutingModel *source_model, const operations_research::Assignment *source_assignment)
const operations_research::Assignment * Solve(const operations_research::Assignment *assignment=nullptr)
void SetAmortizedCostFactorsOfVehicle(int64_t linear_cost_factor, int64_t quadratic_cost_factor, int vehicle)
Sets the linear and quadratic cost factor of the given vehicle.
operations_research::IntVar * NextVar(int64_t index) const
void AddIntervalToAssignment(IntervalVar *interval)
bool CostsAreHomogeneousAcrossVehicles() const
Whether costs are homogeneous across all vehicles.
DisjunctionIndex AddDisjunction(const std::vector< int64_t > &indices, int64_t penalty=kNoPenalty, int64_t max_cardinality=1, PenaltyCostBehavior penalty_cost_behavior=PenaltyCostBehavior::PENALIZE_ONCE)
Adds a disjunction constraint on the indices.
int64_t GetDisjunctionPenalty(DisjunctionIndex index) const
Returns the penalty of the node disjunction of index 'index'.
int64_t End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
operations_research::Assignment * CompactAssignment(const operations_research::Assignment &assignment) const
operations_research::Assignment * CompactAndCheckAssignment(const operations_research::Assignment &assignment) const
void AddVariableMinimizedByFinalizer(operations_research::IntVar *var)
int RegisterCumulDependentTransitCallback(CumulDependentTransitCallback2 callback)
const std::vector< int > & GetPairIndicesOfType(int type) const
static const DimensionIndex kNoDimension
int GetVehicleClassesCount() const
Returns the number of different vehicle classes in the model.
const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenRemovingType(int type) const
Returns the set of requirement alternatives when removing the given type.
RoutingTransitCallback2 TransitCallback2
@ TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED
@ TYPE_ON_VEHICLE_UP_TO_VISIT
@ ADDED_TYPE_REMOVED_FROM_VEHICLE
@ TYPE_ADDED_TO_VEHICLE
When visited, the number of types 'T' on the vehicle increases by one.
void AddLocalSearchOperator(LocalSearchOperator *ls_operator)
bool AddDimensionWithVehicleTransitAndCapacity(const std::vector< int > &evaluator_indices, int64_t slack_max, std::vector< int64_t > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
int GetCostClassesCount() const
Returns the number of different cost classes in the model.
GlobalDimensionCumulOptimizer * GetMutableGlobalCumulLPOptimizer(const RoutingDimension &dimension) const
const std::vector< PickupDeliveryPair > & GetPickupAndDeliveryPairs() const
Returns pickup and delivery pairs currently in the model.
void AddToAssignment(operations_research::IntVar *var)
Adds an extra variable to the vehicle routing assignment.
const std::string & GetPrimaryConstrainedDimension() const
Get the primary constrained dimension, or an empty string if it is unset.
VehicleClassIndex GetVehicleClassIndexOfVehicle(int64_t vehicle) const
bool HasTypeRegulations() const
friend class RoutingDimension
bool IsMatchingModel() const
Returns true if a vehicle/node matching problem is detected.
void AddPickupAndDelivery(int64_t pickup, int64_t delivery)
GlobalDimensionCumulOptimizer * GetMutableGlobalCumulMPOptimizer(const RoutingDimension &dimension) const
const std::vector< RoutingDimension * > & GetDimensions() const
Returns all dimensions of the model.
const absl::flat_hash_set< int > & GetTemporalTypeIncompatibilitiesOfType(int type) const
const absl::flat_hash_set< int > & GetHardTypeIncompatibilitiesOfType(int type) const
Returns visit types incompatible with a given type.
void SetAmortizedCostFactorsOfAllVehicles(int64_t linear_cost_factor, int64_t quadratic_cost_factor)
Sets the linear and quadratic cost factor of all vehicles.
void CloseModelWithParameters(const RoutingSearchParameters &search_parameters)
const operations_research::Assignment * SolveFromAssignmentsWithParameters(const std::vector< const operations_research::Assignment * > &assignments, const RoutingSearchParameters &search_parameters, std::vector< const operations_research::Assignment * > *solutions=nullptr)
operations_research::Assignment * RestoreAssignment(const operations_research::Assignment &solution)
void AddRequiredTypeAlternativesWhenAddingType(int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
RoutingDimensionIndex DimensionIndex
static RoutingModel::StateDependentTransit MakeStateDependentTransit(const std::function< int64_t(int64_t)> &f, int64_t domain_start, int64_t domain_end)
Creates a cached StateDependentTransit from an std::function.
int RegisterTransitMatrix(std::vector< std::vector< int64_t > > values)
const NodeNeighborsByCostClass * GetOrCreateNodeNeighborsByCostClass(double neighbors_ratio, int64_t min_neighbors, double &neighbors_ratio_used, bool add_vehicle_starts_to_neighbors=true, bool add_vehicle_ends_to_neighbors=false, bool only_sort_neighbors_for_partial_neighborhoods=true)
int64_t UnperformedPenaltyOrValue(int64_t default_value, int64_t var_index) const
bool AddDimensionDependentDimensionWithVehicleCapacity(const std::vector< int > &pure_transits, const std::vector< int > &dependent_transits, const RoutingDimension *base_dimension, int64_t slack_max, std::vector< int64_t > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
int64_t GetNumberOfRejectsInFirstSolution(const RoutingSearchParameters &search_parameters) const
const operations_research::Assignment * SolveWithParameters(const RoutingSearchParameters &search_parameters, std::vector< const operations_research::Assignment * > *solutions=nullptr)
void SetFixedCostOfAllVehicles(int64_t cost)
bool IsStart(int64_t index) const
Returns true if 'index' represents the first node of a route.
bool IsPickup(int64_t node_index) const
Returns whether the node is a pickup (resp. delivery).
const std::vector< std::vector< DisjunctionIndex > > & GetOrderedActivityGroups() const
Returns all ordered activity groups.
int64_t UnperformedPenalty(int64_t var_index) const
LocalDimensionCumulOptimizer * GetMutableLocalCumulMPOptimizer(const RoutingDimension &dimension) const
const std::vector< absl::flat_hash_set< int > > & GetSameVehicleRequiredTypeAlternativesOfType(int type) const
bool IsEnd(int64_t index) const
Returns true if 'index' represents the last node of a route.
bool IsDelivery(int64_t node_index) const
const std::vector< int64_t > & GetDisjunctionNodeIndices(DisjunctionIndex index) const
int vehicles() const
Returns the number of vehicle routes in the model.
void AddWeightedVariableMinimizedByFinalizer(operations_research::IntVar *var, int64_t cost)
const std::vector< operations_research::IntVar * > & VehicleVars() const
void SetAllowedVehiclesForIndex(absl::Span< const int > vehicles, int64_t index)
static const int64_t kNoPenalty
Constant used to express a hard constraint instead of a soft penalty.
const std::vector< int > & GetDimensionResourceGroupIndices(const RoutingDimension *dimension) const
RoutingResourceClassIndex ResourceClassIndex
const operations_research::Assignment * FastSolveFromAssignmentWithParameters(const operations_research::Assignment *assignment, const RoutingSearchParameters &search_parameters, bool check_solution_in_cp, absl::flat_hash_set< operations_research::IntVar * > *touched=nullptr)
int64_t GetArcCostForFirstSolution(int64_t from_index, int64_t to_index) const
const std::vector< int > & GetSameVehicleIndicesOfIndex(int node) const
Returns variable indices of nodes constrained to be on the same route.
int64_t ComputeLowerBound()
std::vector< std::pair< int64_t, int64_t > > GetPerfectBinaryDisjunctions() const
int64_t GetHomogeneousCost(int64_t from_index, int64_t to_index) const
std::pair< int, bool > AddVectorDimension(std::vector< int64_t > values, int64_t capacity, bool fix_start_cumul_to_zero, const std::string &name)
bool AddDimension(int evaluator_index, int64_t slack_max, int64_t capacity, bool fix_start_cumul_to_zero, const std::string &name)
Model creation.
bool CheckLimit(absl::Duration offset=absl::ZeroDuration())
void SetArcCostEvaluatorOfVehicle(int evaluator_index, int vehicle)
Sets the cost function for a given vehicle route.
void SetFixedCostOfVehicle(int64_t cost, int vehicle)
Sets the fixed cost of one vehicle route.
bool CheckIfAssignmentIsFeasible(const operations_research::Assignment &assignment, bool call_at_solution_monitors)
Checks if an assignment is feasible.
void AssignmentToRoutes(const operations_research::Assignment &assignment, std::vector< std::vector< int64_t > > *routes) const
VisitTypePolicy GetVisitTypePolicy(int64_t index) const
ResourceGroup * AddResourceGroup()
Adds a resource group to the routing model and returns a pointer to it.
std::optional< PickupDeliveryPosition > GetDeliveryPosition(int64_t node_index) const
Returns the pickup and delivery positions where the node is a delivery.
operations_research::IntVar * CostVar() const
Returns the global cost variable which is being minimized.
bool RoutesToAssignment(const std::vector< std::vector< int64_t > > &routes, bool ignore_inactive_indices, bool close_routes, operations_research::Assignment *assignment) const
const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenAddingType(int type) const
Returns the set of requirement alternatives when adding the given type.
const operations_research::Assignment * SolveFromAssignmentWithParameters(const operations_research::Assignment *assignment, const RoutingSearchParameters &search_parameters, std::vector< const operations_research::Assignment * > *solutions=nullptr)
const TransitCallback1 & UnaryTransitCallbackOrNull(int callback_index) const
bool WriteAssignment(const std::string &file_name) const
int64_t GetArcCostForVehicle(int64_t from_index, int64_t to_index, int64_t vehicle) const
std::vector< std::string > GetAllDimensionNames() const
Outputs the names of all dimensions added to the routing engine.
bool HasMandatoryDisjunctions() const
bool ArcIsMoreConstrainedThanArc(int64_t from, int64_t to1, int64_t to2)
bool AddDimensionWithVehicleCapacity(int evaluator_index, int64_t slack_max, std::vector< int64_t > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
operations_research::Assignment * ReadAssignmentFromRoutes(const std::vector< std::vector< int64_t > > &routes, bool ignore_inactive_indices)
static const DisjunctionIndex kNoDisjunction
bool HasGlobalCumulOptimizer(const RoutingDimension &dimension) const
Returns whether the given dimension has global/local cumul optimizers.
std::string DebugOutputAssignment(const operations_research::Assignment &solution_assignment, const std::string &dimension_to_print) const
RoutingDimension * GetMutableDimension(const std::string &dimension_name) const
PickupAndDeliveryPolicy
Types of precedence policy applied to pickup and delivery pairs.
@ PICKUP_AND_DELIVERY_NO_ORDER
Any precedence is accepted.
@ PICKUP_AND_DELIVERY_FIFO
Deliveries must be performed in the same order as pickups.
@ PICKUP_AND_DELIVERY_LIFO
Deliveries must be performed in reverse order of pickups.
SweepArranger * sweep_arranger() const
Returns the sweep arranger to be used by routing heuristics.
operations_research::Assignment * ReadAssignment(const std::string &file_name)
int GetNumOfSingletonNodes() const
int64_t GetFixedCostOfVehicle(int vehicle) const
const std::deque< int > & GetVehiclesOfSameClass(int64_t start_end_index) const
LocalDimensionCumulOptimizer * GetMutableLocalCumulLPOptimizer(const RoutingDimension &dimension) const
std::pair< int, bool > AddMatrixDimension(std::vector< std::vector< int64_t > > values, int64_t capacity, bool fix_start_cumul_to_zero, const std::string &name)
void SetArcCostEvaluatorOfAllVehicles(int evaluator_index)
void SetPathEnergyCostsOfVehicle(const std::string &force, const std::string &distance, int64_t threshold, int64_t cost_per_unit_below_threshold, int64_t cost_per_unit_above_threshold, int vehicle)
void AddVariableTargetToFinalizer(operations_research::IntVar *var, int64_t target)
std::vector< RoutingDimension * > GetDimensionsWithSoftOrSpanCosts() const
Returns dimensions with soft or vehicle span costs.
std::vector< std::vector< int64_t > > GetRoutesFromAssignment(const operations_research::Assignment &assignment)
void SetTabuVarsCallback(GetTabuVarsCallback tabu_var_callback)
operations_research::IntVar * VehicleVar(int64_t index) const
bool IsVehicleAllowedForIndex(int vehicle, int64_t index) const
Returns true if a vehicle is allowed to visit a given node.
bool HasDimension(absl::string_view dimension_name) const
Returns true if a dimension exists for a given dimension name.
const RoutingDimension & GetDimensionOrDie(const std::string &dimension_name) const
Returns a dimension from its name. Dies if the dimension does not exist.
void AddRouteConstraint(absl::AnyInvocable< std::optional< int64_t >(const std::vector< int64_t > &)> route_evaluator, bool costs_are_homogeneous_across_vehicles=false)
PickupAndDeliveryPolicy GetPickupAndDeliveryPolicyOfVehicle(int vehicle) const
void AddVariableMaximizedByFinalizer(operations_research::IntVar *var)
bool AddDimensionWithCumulDependentVehicleTransitAndCapacity(const std::vector< int > &fixed_evaluator_indices, const std::vector< int > &cumul_dependent_evaluator_indices, int64_t slack_max, std::vector< int64_t > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
void AddRestoreDimensionValuesResetCallback(std::function< void()> callback)
int RegisterStateDependentTransitCallback(VariableIndexEvaluator2 callback)
RoutingTransitCallback1 TransitCallback1
const std::vector< DisjunctionIndex > & GetDisjunctionIndices(int64_t index) const
Returns the indices of the disjunctions to which an index belongs.
bool HasSameVehicleTypeRequirements() const
void AddEnterSearchCallback(std::function< void()> callback)
bool IsVehicleUsed(const operations_research::Assignment &assignment, int vehicle) const
Returns true if the route of 'vehicle' is non empty in 'assignment'.
const std::vector< operations_research::IntVar * > & Nexts() const
void SetSweepArranger(SweepArranger *sweep_arranger)
void AddAtSolutionCallback(std::function< void()> callback, bool track_unchecked_neighbors=false)
int RegisterTransitCallback(TransitCallback2 callback, TransitEvaluatorSign sign=kTransitEvaluatorSignUnknown)
std::vector< const RoutingDimension * > GetDimensionsWithGlobalCumulOptimizers() const
Returns the dimensions which have [global|local]_dimension_optimizers_.
void AddRequiredTypeAlternativesWhenRemovingType(int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
const std::vector< int > & GetSingleNodesOfType(int type) const
std::vector< std::vector< std::pair< int64_t, int64_t > > > GetCumulBounds(const operations_research::Assignment &solution_assignment, const RoutingDimension &dimension)
bool AddDimensionWithVehicleTransits(const std::vector< int > &evaluator_indices, int64_t slack_max, int64_t capacity, bool fix_start_cumul_to_zero, const std::string &name)
RoutingVehicleClassIndex VehicleClassIndex
operations_research::SubSolverStatistics GetSubSolverStatistics() const
Returns detailed search statistics.
std::vector< std::pair< int64_t, int64_t > > GetSameVehicleClassArcs(int64_t from_index, int64_t to_index) const
void AddWeightedVariableTargetToFinalizer(operations_research::IntVar *var, int64_t target, int64_t cost)
TransitEvaluatorSign
Represents the sign of values returned by a transit evaluator.
@ kTransitEvaluatorSignPositiveOrZero
@ kTransitEvaluatorSignNegativeOrZero
@ kTransitEvaluatorSignUnknown
void AddSoftSameVehicleConstraint(std::vector< int64_t > indices, int64_t cost)
int64_t GetDisjunctionMaxCardinality(DisjunctionIndex index) const
std::optional< int64_t > GetRouteCost(const std::vector< int64_t > &route) const
std::vector< const RoutingDimension * > GetDimensionsWithLocalCumulOptimizers() const
int VehicleIndex(int64_t index) const
void AddTemporalTypeIncompatibility(int type1, int type2)
RoutingCostClassIndex CostClassIndex
bool use_depth_first_search() const
::operations_research::LocalSearchMetaheuristic_Value local_search_metaheuristic() const
const ::google::protobuf::Duration & time_limit() const
bool use_full_propagation() const
::int64_t solution_limit() const
bool has_time_limit() const
::operations_research::FirstSolutionStrategy_Value first_solution_strategy() const
static constexpr Value ROUTING_FAIL
static constexpr Value ROUTING_NOT_SOLVED
static constexpr Value ROUTING_FAIL_TIMEOUT
static constexpr Value ROUTING_OPTIMAL
static constexpr Value ROUTING_INVALID
static constexpr Value ROUTING_INFEASIBLE
static constexpr Value ROUTING_SUCCESS
A search monitor is a simple set of callbacks to monitor all search events.
virtual bool AtLocalOptimum()
int solution_count() const
Returns how many solutions were stored during the search.
static ConstraintSolverParameters DefaultSolverParameters()
Create a ConstraintSolverParameters proto with all the default values.
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
Assignment * RunUncheckedLocalSearch(const Assignment *initial_solution, LocalSearchFilterManager *filter_manager, LocalSearchOperator *ls_operator, const std::vector< SearchMonitor * > &monitors, RegularLimit *limit, absl::flat_hash_set< IntVar * > *touched=nullptr)
std::function< int64_t(int64_t)> IndexEvaluator1
Callback typedefs.
IntExpr * RegisterIntExpr(IntExpr *expr)
Registers a new IntExpr and wraps it inside a TraceIntExpr if necessary.
@ LE
Move is accepted when the current objective value <= objective.Max.
std::function< int64_t(int64_t, int64_t)> IndexEvaluator2
@ kAcceptUncheckedNeighbor
@ STARTS_AFTER_END
t1 starts after t2 end, i.e. Start(t1) >= End(t2) + delay.
Assignment * MakeAssignment()
This method creates an empty assignment.
EvaluatorLocalSearchOperators
void MakeIntVarArray(int var_count, int64_t vmin, int64_t vmax, const std::string &name, std::vector< IntVar * > *vars)
std::function< bool(int64_t, int64_t, int64_t)> VariableValueComparator
@ ASSIGN_MIN_VALUE
Selects the min value of the selected variable.
IntExpr * MakeProd(IntExpr *left, IntExpr *right)
left * right
IntVar * MakeIntConst(int64_t val, const std::string &name)
IntConst will create a constant expression.
void AddConstraint(Constraint *c)
Adds the constraint 'c' to the model.
@ CHOOSE_STATIC_GLOBAL_BEST
IntervalSet::iterator Iterator
void set_num_glop_calls_in_lp_scheduling(::int64_t value)
TypeIncompatibilityChecker(const RoutingModel &model, bool check_hard_incompatibilities)
TypeRegulationsChecker(const RoutingModel &model)
virtual bool HasRegulationsToCheck() const =0
void InitializeCheck(int vehicle, const std::function< int64_t(int64_t)> &next_accessor)
const RoutingModel & model_
bool CheckVehicle(int vehicle, const std::function< int64_t(int64_t)> &next_accessor)
bool TypeOccursOnRoute(int type) const
virtual void OnInitializeCheck()
RoutingModel::VisitTypePolicy VisitTypePolicy
virtual bool CheckTypeRegulations(int type, VisitTypePolicy policy, int pos)=0
bool TypeCurrentlyOnRoute(int type, int pos) const
virtual bool FinalizeCheck() const
void InitialPropagate() override
TypeRegulationsConstraint(const RoutingModel &model)
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
void push_back(const value_type &val)
void resize(size_type new_size)
bool operator==(const ProtoEnumIterator< E > &a, const ProtoEnumIterator< E > &b)
const Collection::value_type::second_type FindPtrOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
void STLDeleteElements(T *container)
Collection::value_type::second_type & LookupOrInsert(Collection *const collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
const Collection::value_type::second_type * FindOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
const MapUtilMappedT< Collection > & FindWithDefault(const Collection &collection, const KeyType &key, const MapUtilMappedT< Collection > &value)
H AbslHashValue(H h, std::shared_ptr< Variable > i)
LocalSearchOperator * MakePairNodeSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)
constexpr FirstSolutionStrategy_Value FirstSolutionStrategy_Value_Value_MAX
LocalSearchOperator * MakeExtendedSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— ExtendedSwapActive --—
LinearRange operator==(const LinearExpr &lhs, const LinearExpr &rhs)
LocalSearchFilter * MakePickupDeliveryFilter(const RoutingModel &routing_model, const PathState *path_state, absl::Span< const PickupDeliveryPair > pairs, const std::vector< RoutingModel::PickupAndDeliveryPolicy > &vehicle_policies)
IntVarLocalSearchFilter * MakeVehicleAmortizedCostFilter(const RoutingModel &routing_model)
Returns a filter computing vehicle amortized costs.
DecisionBuilder * MakeAllUnperformed(RoutingModel *model)
int64_t CapAdd(int64_t x, int64_t y)
LocalSearchOperator * MakeExchangeSubtrip(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, absl::Span< const PickupDeliveryPair > pairs)
IntVarLocalSearchFilter * MakeRouteConstraintFilter(const RoutingModel &routing_model)
Returns a filter tracking route constraints.
LocalSearchOperator * MakePairActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)
void CapAddTo(int64_t x, int64_t *y)
LocalSearchOperator * MakeLightPairRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, const std::vector< PickupDeliveryPair > &pairs, std::function< bool(int64_t)> force_lifo)
LocalSearchOperator * MakePairExchangeRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)
FirstSolutionStrategy::Value AutomaticFirstSolutionStrategy(bool has_pickup_deliveries, bool has_node_precedences, bool has_single_vehicle_node)
LocalSearchOperator * MakeCross(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— Cross --—
IntVarLocalSearchFilter * MakeSameVehicleCostFilter(const RoutingModel &routing_model)
Returns a filter computing same vehicle costs.
constexpr FirstSolutionStrategy_Value FirstSolutionStrategy_Value_Value_MIN
IntVarLocalSearchFilter * MakeMaxActiveVehiclesFilter(const RoutingModel &routing_model)
Returns a filter ensuring that max active vehicles constraints are enforced.
void AppendLightWeightDimensionFilters(const PathState *path_state, const std::vector< RoutingDimension * > &dimensions, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
LocalSearchOperator * MakeSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— SwapActive --—
LocalSearchOperator * ExchangeAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
RangeIntToIntFunction * MakeCachedIntToIntFunction(const std::function< int64_t(int64_t)> &f, int64_t domain_start, int64_t domain_end)
LocalSearchOperator * MakeGroupPairAndRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, const std::vector< PickupDeliveryPair > &pairs)
IntVarLocalSearchFilter * MakeNodeDisjunctionFilter(const RoutingModel &routing_model, bool filter_cost)
Returns a filter ensuring that node disjunction constraints are enforced.
LocalSearchOperator * MakeExchange(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— Exchange --—
void AcceptUncheckedNeighbor(Search *search)
LocalSearchOperator * MakePairInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)
int64_t CapSub(int64_t x, int64_t y)
BlossomGraph::CostValue CostValue
LocalSearchOperator * MakeActiveAndRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeActiveAndRelocate --—
LocalSearchFilter * MakePathEnergyCostFilter(Solver *solver, std::unique_ptr< PathEnergyCostChecker > checker, absl::string_view dimension_name)
LocalSearchOperator * MakePairRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)
DecisionBuilder * MakeRestoreDimensionValuesForUnchangedRoutes(RoutingModel *model)
LocalSearchOperator * MakeSwapActiveToShortestPath(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::vector< std::vector< int64_t > > alternative_sets, RoutingTransitCallback2 arc_evaluator)
LocalSearchOperator * MakeRelocateExpensiveChain(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, int num_arcs_to_consider, std::function< int64_t(int64_t, int64_t, int64_t)> arc_cost_for_path_start)
Constraint * MakeGlobalVehicleBreaksConstraint(Solver *solver, const RoutingDimension *dimension)
LocalSearchFilter * MakePathStateFilter(Solver *solver, std::unique_ptr< PathState > path_state, const std::vector< IntVar * > &nexts)
ClosedInterval::Iterator end(ClosedInterval interval)
LocalSearchOperator * MakeRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr, int64_t chain_length=1LL, bool single_path=false, const std::string &name="Relocate")
--— Relocate --—
LocalSearchOperator * MakeIndexPairSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)
LocalSearchOperator * RelocateAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
-— RelocateAndMakeActive --—
IntVarLocalSearchFilter * MakeCPFeasibilityFilter(RoutingModel *routing_model)
Returns a filter checking the current solution using CP propagation.
LocalSearchOperator * MakeInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeInactive --—
Constraint * MakePathSpansAndTotalSlacks(const RoutingDimension *dimension, std::vector< IntVar * > spans, std::vector< IntVar * > total_slacks)
DecisionBuilder * MakeSetCumulsFromGlobalDimensionCosts(Solver *solver, GlobalDimensionCumulOptimizer *global_optimizer, GlobalDimensionCumulOptimizer *global_mp_optimizer, bool optimize_and_pack, std::vector< RoutingModel::RouteDimensionTravelInfo > dimension_travel_info_per_route)
Variant based on global optimizers, handling all routes together.
LocalSearchOperator * MakeTwoOpt(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— 2Opt --—
int64_t One()
This method returns 1.
LocalSearchOperator * MakeChainInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeChainInactive --—
IntVarLocalSearchFilter * MakeOrderedActivityGroupFilter(const RoutingModel &routing_model)
RoutingModelParameters DefaultRoutingModelParameters()
DecisionBuilder * MakeSetCumulsFromLocalDimensionCosts(Solver *solver, LocalDimensionCumulOptimizer *lp_optimizer, LocalDimensionCumulOptimizer *mp_optimizer, bool optimize_and_pack, std::vector< RoutingModel::RouteDimensionTravelInfo > dimension_travel_info_per_route)
int64_t CapProd(int64_t x, int64_t y)
constexpr int FirstSolutionStrategy_Value_Value_ARRAYSIZE
LocalSearchOperator * MakeRelocateSubtrip(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, absl::Span< const PickupDeliveryPair > pairs)
const ::std::string & FirstSolutionStrategy_Value_Name(T value)
Constraint * MakeResourceConstraint(const RoutingModel::ResourceGroup *resource_group, const std::vector< IntVar * > *vehicle_resource_vars, RoutingModel *model)
LocalSearchFilter * MakeVehicleVarFilter(const RoutingModel &routing_model, const PathState *path_state)
Returns a filter checking that vehicle variable domains are respected.
static const int kUnassigned
bool SolveModelWithSat(RoutingModel *model, RoutingSearchStats *search_stats, const RoutingSearchParameters &search_parameters, const operations_research::Assignment *initial_solution, operations_research::Assignment *solution)
RangeMinMaxIndexFunction * MakeCachedRangeMinMaxIndexFunction(const std::function< int64_t(int64_t)> &f, int64_t domain_start, int64_t domain_end)
void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters ¶meters, bool filter_objective_cost, bool use_chain_cumul_filter, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
int64_t CapAbs(int64_t v)
LocalSearchOperator * ExchangePathStartEndsAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
DecisionBuilder * MakeSweepDecisionBuilder(RoutingModel *model, bool check_assignment)
std::string MemoryUsage()
Demon * MakeDelayedConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
LocalSearchOperator * MakeSwapActiveChain(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, int max_chain_size)
--— SwapActiveChain --—
Constraint * MakeRouteConstraint(RoutingModel *model, std::vector< IntVar * > route_cost_vars, std::function< std::optional< int64_t >(const std::vector< int64_t > &)> route_evaluator)
util::ReverseArcStaticGraph Graph
std::unique_ptr< BinCapacities > MakeBinCapacities(const std::vector< RoutingDimension * > &dimensions, const PathsMetadata &paths_metadata)
IntVarLocalSearchFilter * MakeTypeRegulationsFilter(const RoutingModel &routing_model)
Returns a filter ensuring type regulation constraints are enforced.
LocalSearchOperator * MakeTwoOptWithShortestPath(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::vector< std::vector< int64_t > > alternative_sets, RoutingTransitCallback2 arc_evaluator)
LocalSearchOperator * MakeRelocateNeighbors(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, RoutingTransitCallback2 arc_evaluator)
IntVarLocalSearchFilter * MakeActiveNodeGroupFilter(const RoutingModel &routing_model)
RoutingSearchParameters DefaultRoutingSearchParameters()
LocalSearchOperator * MakePairExchange(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, const std::vector< PickupDeliveryPair > &pairs)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
std::string FindErrorInRoutingSearchParameters(const RoutingSearchParameters &search_parameters)
Constraint * MakeDifferentFromValues(Solver *solver, IntVar *var, std::vector< int64_t > values)
void SetAssignmentFromAssignment(Assignment *target_assignment, const std::vector< IntVar * > &target_vars, const Assignment *source_assignment, const std::vector< IntVar * > &source_vars)
NOLINT.
void FillPathEvaluation(absl::Span< const int64_t > path, const RoutingModel::TransitCallback2 &evaluator, std::vector< int64_t > *values)
FirstSolutionStrategy_Value
std::unique_ptr< NeighborAcceptanceCriterion > MakeNeighborAcceptanceCriterion(const RoutingModel &model, const AcceptanceStrategy &acceptance_strategy, const NeighborAcceptanceCriterion::SearchState &final_search_state, std::mt19937 *rnd)
Constraint * MakeNumActiveVehiclesCapacityConstraint(Solver *solver, std::vector< IntVar * > transit_vars, std::vector< IntVar * > active_vars, std::vector< IntVar * > vehicle_active_vars, std::vector< int64_t > vehicle_capacities, int max_active_vehicles, bool enforce_active_vehicles)
int64_t CapOpp(int64_t v)
DecisionBuilder * MakePerturbationDecisionBuilder(const RoutingSearchParameters ¶meters, RoutingModel *model, std::mt19937 *rnd, const Assignment *assignment, std::function< bool()> stop_search, LocalSearchFilterManager *filter_manager)
LocalSearchOperator * MakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— MakeActive --—
inline ::absl::StatusOr< absl::Duration > DecodeGoogleApiProto(const google::protobuf::Duration &proto)
std::vector< int > GetConnectedComponents(int num_nodes, const UndirectedGraph &graph)
trees with all degrees equal to
static int input(yyscan_t yyscanner)
#define CP_ROUTING_PUSH_OPERATOR(operator_type, operator_method)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64_t pre_travel_transit_value
std::string DebugString(std::string line_prefix="") const
std::vector< TransitionInfo > transition_info
int64_t travel_cost_coefficient
The cost per unit of travel for this vehicle.
std::string DebugString(std::string line_prefix="") const
std::vector< std::deque< int > > vehicles_per_vehicle_class
int64_t num_cp_sat_calls_in_lp_scheduling
int64_t num_min_cost_flow_calls
int64_t num_glop_calls_in_lp_scheduling
int position_of_last_type_on_vehicle_up_to_visit
int num_type_added_to_vehicle
int num_type_removed_from_vehicle
static const int64_t kint64max
static const int64_t kint64min