18 #include "absl/container/flat_hash_set.h"
19 #include "absl/time/time.h"
32 glop::GlopParameters GetGlopParametersForLocalLP() {
39 glop::GlopParameters GetGlopParametersForGlobalLP() {
45 bool GetCumulBoundsWithOffset(
const RoutingDimension& dimension,
48 DCHECK(lower_bound !=
nullptr);
49 DCHECK(upper_bound !=
nullptr);
51 const IntVar& cumul_var = *dimension.CumulVar(node_index);
52 *upper_bound = cumul_var.Max();
53 if (*upper_bound < cumul_offset) {
57 const int64 first_after_offset =
58 std::max(dimension.GetFirstPossibleGreaterOrEqualValueForNode(
59 node_index, cumul_offset),
62 *lower_bound =
CapSub(first_after_offset, cumul_offset);
68 *upper_bound =
CapSub(*upper_bound, cumul_offset);
73 int64 GetFirstPossibleValueForCumulWithOffset(
const RoutingDimension& dimension,
75 int64 lower_bound_without_offset,
78 dimension.GetFirstPossibleGreaterOrEqualValueForNode(
79 node_index,
CapAdd(lower_bound_without_offset, cumul_offset)),
83 int64 GetLastPossibleValueForCumulWithOffset(
const RoutingDimension& dimension,
85 int64 upper_bound_without_offset,
88 dimension.GetLastPossibleLessOrEqualValueForNode(
89 node_index,
CapAdd(upper_bound_without_offset, cumul_offset)),
98 void StoreVisitedPickupDeliveryPairsOnRoute(
99 const RoutingDimension& dimension,
int vehicle,
100 const std::function<
int64(
int64)>& next_accessor,
101 std::vector<int>* visited_pairs,
102 std::vector<std::pair<int64, int64>>*
103 visited_pickup_delivery_indices_for_pair) {
105 DCHECK_EQ(visited_pickup_delivery_indices_for_pair->size(),
106 dimension.model()->GetPickupAndDeliveryPairs().size());
107 DCHECK(std::all_of(visited_pickup_delivery_indices_for_pair->begin(),
108 visited_pickup_delivery_indices_for_pair->end(),
109 [](std::pair<int64, int64> p) {
110 return p.first == -1 && p.second == -1;
112 visited_pairs->clear();
113 if (!dimension.HasPickupToDeliveryLimits()) {
116 const RoutingModel&
model = *dimension.model();
119 while (!
model.IsEnd(node_index)) {
120 const std::vector<std::pair<int, int>>& pickup_index_pairs =
121 model.GetPickupIndexPairs(node_index);
122 const std::vector<std::pair<int, int>>& delivery_index_pairs =
123 model.GetDeliveryIndexPairs(node_index);
124 if (!pickup_index_pairs.empty()) {
127 DCHECK(delivery_index_pairs.empty());
129 (*visited_pickup_delivery_indices_for_pair)[pickup_index_pairs[0].first]
131 visited_pairs->push_back(pickup_index_pairs[0].first);
132 }
else if (!delivery_index_pairs.empty()) {
136 DCHECK_EQ(delivery_index_pairs.size(), 1);
137 const int pair_index = delivery_index_pairs[0].first;
138 std::pair<int64, int64>& pickup_delivery_index =
139 (*visited_pickup_delivery_indices_for_pair)[pair_index];
140 if (pickup_delivery_index.first < 0) {
143 node_index = next_accessor(node_index);
146 pickup_delivery_index.second = node_index;
148 node_index = next_accessor(node_index);
156 RoutingSearchParameters::SchedulingSolver solver_type)
157 : optimizer_core_(dimension, false) {
161 solver_.resize(vehicles);
162 switch (solver_type) {
163 case RoutingSearchParameters::GLOP: {
164 const glop::GlopParameters
parameters = GetGlopParametersForLocalLP();
165 for (
int vehicle = 0; vehicle < vehicles; ++vehicle) {
166 solver_[vehicle] = absl::make_unique<RoutingGlopWrapper>(
parameters);
170 case RoutingSearchParameters::CP_SAT: {
171 for (
int vehicle = 0; vehicle < vehicles; ++vehicle) {
172 solver_[vehicle] = absl::make_unique<RoutingCPSatWrapper>();
177 LOG(DFATAL) <<
"Unrecognized solver type: " << solver_type;
182 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
183 int64* optimal_cost) {
185 solver_[vehicle].get(),
nullptr,
186 nullptr, optimal_cost,
nullptr);
191 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
192 int64* optimal_cost_without_transits) {
194 int64 transit_cost = 0;
196 vehicle, next_accessor, solver_[vehicle].get(),
nullptr,
nullptr, &
cost,
199 optimal_cost_without_transits !=
nullptr) {
200 *optimal_cost_without_transits =
CapSub(
cost, transit_cost);
206 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
207 std::vector<int64>* optimal_cumuls, std::vector<int64>* optimal_breaks) {
209 vehicle, next_accessor, solver_[vehicle].get(), optimal_cumuls,
210 optimal_breaks,
nullptr,
nullptr);
215 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
216 std::vector<int64>* packed_cumuls, std::vector<int64>* packed_breaks) {
218 vehicle, next_accessor, solver_[vehicle].get(), packed_cumuls,
222 const int CumulBoundsPropagator::kNoParent = -2;
223 const int CumulBoundsPropagator::kParentToBePropagated = -1;
226 : dimension_(*dimension), num_nodes_(2 * dimension->cumuls().size()) {
227 outgoing_arcs_.resize(num_nodes_);
228 node_in_queue_.resize(num_nodes_,
false);
229 tree_parent_node_of_.resize(num_nodes_, kNoParent);
230 propagated_bounds_.resize(num_nodes_);
231 visited_pickup_delivery_indices_for_pair_.resize(
235 void CumulBoundsPropagator::AddArcs(
int first_index,
int second_index,
238 outgoing_arcs_[PositiveNode(first_index)].push_back(
239 {PositiveNode(second_index), offset});
240 AddNodeToQueue(PositiveNode(first_index));
242 outgoing_arcs_[NegativeNode(second_index)].push_back(
243 {NegativeNode(first_index), offset});
244 AddNodeToQueue(NegativeNode(second_index));
247 bool CumulBoundsPropagator::InitializeArcsAndBounds(
248 const std::function<
int64(
int64)>& next_accessor,
int64 cumul_offset) {
249 propagated_bounds_.assign(num_nodes_,
kint64min);
251 for (std::vector<ArcInfo>& arcs : outgoing_arcs_) {
255 RoutingModel*
const model = dimension_.
model();
258 for (
int vehicle = 0; vehicle <
model->vehicles(); vehicle++) {
262 int node =
model->Start(vehicle);
264 int64 cumul_lb, cumul_ub;
265 if (!GetCumulBoundsWithOffset(dimension_, node, cumul_offset, &cumul_lb,
274 if (
model->IsEnd(node)) {
278 const int next = next_accessor(node);
279 const int64 transit = transit_accessor(node,
next);
280 const IntVar& slack_var = *dimension_.
SlackVar(node);
283 AddArcs(node,
next,
CapAdd(transit, slack_var.Min()));
286 AddArcs(
next, node,
CapSub(-slack_var.Max(), transit));
295 AddArcs(
model->End(vehicle),
model->Start(vehicle), -span_ub);
299 std::vector<int> visited_pairs;
300 StoreVisitedPickupDeliveryPairsOnRoute(
301 dimension_, vehicle, next_accessor, &visited_pairs,
302 &visited_pickup_delivery_indices_for_pair_);
303 for (
int pair_index : visited_pairs) {
304 const int64 pickup_index =
305 visited_pickup_delivery_indices_for_pair_[pair_index].first;
306 const int64 delivery_index =
307 visited_pickup_delivery_indices_for_pair_[pair_index].second;
308 visited_pickup_delivery_indices_for_pair_[pair_index] = {-1, -1};
311 if (delivery_index < 0) {
317 pair_index,
model->GetPickupIndexPairs(pickup_index)[0].second,
318 model->GetDeliveryIndexPairs(delivery_index)[0].second);
321 AddArcs(delivery_index, pickup_index, -limit);
326 for (
const RoutingDimension::NodePrecedence& precedence :
328 const int first_index = precedence.first_node;
329 const int second_index = precedence.second_node;
335 AddArcs(first_index, second_index, precedence.offset);
341 bool CumulBoundsPropagator::UpdateCurrentLowerBoundOfNode(
int node,
344 const int cumul_var_index = node / 2;
346 if (node == PositiveNode(cumul_var_index)) {
348 propagated_bounds_[node] = GetFirstPossibleValueForCumulWithOffset(
349 dimension_, cumul_var_index, new_lb, offset);
353 propagated_bounds_[node] =
354 CapSub(0, GetLastPossibleValueForCumulWithOffset(
355 dimension_, cumul_var_index, new_ub, offset));
359 const int64 cumul_lower_bound =
360 propagated_bounds_[PositiveNode(cumul_var_index)];
362 const int64 negated_cumul_upper_bound =
363 propagated_bounds_[NegativeNode(cumul_var_index)];
365 return CapAdd(negated_cumul_upper_bound, cumul_lower_bound) <= 0;
368 bool CumulBoundsPropagator::DisassembleSubtree(
int source,
int target) {
369 tmp_dfs_stack_.clear();
370 tmp_dfs_stack_.push_back(source);
371 while (!tmp_dfs_stack_.empty()) {
372 const int tail = tmp_dfs_stack_.back();
373 tmp_dfs_stack_.pop_back();
374 for (
const ArcInfo& arc : outgoing_arcs_[
tail]) {
375 const int child_node = arc.head;
376 if (tree_parent_node_of_[child_node] !=
tail)
continue;
377 if (child_node == target)
return false;
378 tree_parent_node_of_[child_node] = kParentToBePropagated;
379 tmp_dfs_stack_.push_back(child_node);
386 const std::function<
int64(
int64)>& next_accessor,
int64 cumul_offset) {
387 tree_parent_node_of_.assign(num_nodes_, kNoParent);
388 DCHECK(std::none_of(node_in_queue_.begin(), node_in_queue_.end(),
389 [](
bool b) { return b; }));
390 DCHECK(bf_queue_.empty());
392 if (!InitializeArcsAndBounds(next_accessor, cumul_offset)) {
393 return CleanupAndReturnFalse();
396 std::vector<int64>& current_lb = propagated_bounds_;
399 while (!bf_queue_.empty()) {
400 const int node = bf_queue_.front();
401 bf_queue_.pop_front();
402 node_in_queue_[node] =
false;
404 if (tree_parent_node_of_[node] == kParentToBePropagated) {
410 const int64 lower_bound = current_lb[node];
411 for (
const ArcInfo& arc : outgoing_arcs_[node]) {
416 :
CapAdd(lower_bound, arc.offset);
418 const int head_node = arc.head;
419 if (induced_lb <= current_lb[head_node]) {
424 if (!UpdateCurrentLowerBoundOfNode(head_node, induced_lb, cumul_offset) ||
425 !DisassembleSubtree(head_node, node)) {
428 return CleanupAndReturnFalse();
431 tree_parent_node_of_[head_node] = node;
432 AddNodeToQueue(head_node);
440 : dimension_(dimension),
441 visited_pickup_delivery_indices_for_pair_(
442 dimension->
model()->GetPickupAndDeliveryPairs().size(), {-1, -1}) {
443 if (use_precedence_propagator) {
444 propagator_ = absl::make_unique<CumulBoundsPropagator>(dimension);
451 vehicle_to_all_break_variables_offset_.reserve(num_vehicles);
452 int num_break_vars = 0;
453 for (
int vehicle = 0; vehicle < num_vehicles; ++vehicle) {
454 vehicle_to_all_break_variables_offset_.push_back(num_break_vars);
456 num_break_vars += 2 * intervals.size();
458 all_break_variables_.resize(num_break_vars, -1);
463 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
465 std::vector<int64>* break_values,
int64*
cost,
int64* transit_cost,
467 InitOptimizer(solver);
470 DCHECK(propagator_ ==
nullptr);
473 const bool optimize_vehicle_costs =
474 (cumul_values !=
nullptr ||
cost !=
nullptr) &&
475 (!
model->IsEnd(next_accessor(
model->Start(vehicle))) ||
476 model->AreEmptyRouteCostsConsideredForVehicle(vehicle));
477 const int64 cumul_offset =
479 int64 cost_offset = 0;
480 if (!SetRouteCumulConstraints(vehicle, next_accessor, cumul_offset,
481 optimize_vehicle_costs, solver, transit_cost,
491 SetValuesFromLP(current_route_cumul_variables_, cumul_offset, solver,
493 SetValuesFromLP(current_route_break_variables_, cumul_offset, solver,
495 if (
cost !=
nullptr) {
506 const std::function<
int64(
int64)>& next_accessor,
508 std::vector<int64>* break_values,
int64*
cost,
int64* transit_cost,
510 InitOptimizer(solver);
514 const bool optimize_costs = (cumul_values !=
nullptr) || (
cost !=
nullptr);
515 bool has_vehicles_being_optimized =
false;
519 if (propagator_ !=
nullptr &&
520 !propagator_->PropagateCumulBounds(next_accessor, cumul_offset)) {
524 int64 total_transit_cost = 0;
525 int64 total_cost_offset = 0;
527 for (
int vehicle = 0; vehicle <
model->vehicles(); vehicle++) {
528 int64 route_transit_cost = 0;
529 int64 route_cost_offset = 0;
530 const bool optimize_vehicle_costs =
532 (!
model->IsEnd(next_accessor(
model->Start(vehicle))) ||
533 model->AreEmptyRouteCostsConsideredForVehicle(vehicle));
534 if (!SetRouteCumulConstraints(vehicle, next_accessor, cumul_offset,
535 optimize_vehicle_costs, solver,
536 &route_transit_cost, &route_cost_offset)) {
539 total_transit_cost =
CapAdd(total_transit_cost, route_transit_cost);
540 total_cost_offset =
CapAdd(total_cost_offset, route_cost_offset);
541 has_vehicles_being_optimized |= optimize_vehicle_costs;
543 if (transit_cost !=
nullptr) {
544 *transit_cost = total_transit_cost;
547 SetGlobalConstraints(has_vehicles_being_optimized, solver);
554 SetValuesFromLP(index_to_cumul_variable_, cumul_offset, solver, cumul_values);
555 SetValuesFromLP(all_break_variables_, cumul_offset, solver, break_values);
557 if (
cost !=
nullptr) {
568 const std::function<
int64(
int64)>& next_accessor,
570 std::vector<int64>* break_values) {
574 if (!
Optimize(next_accessor, solver,
575 nullptr,
nullptr, &
cost,
581 std::iota(vehicles.begin(), vehicles.end(), 0);
582 if (PackRoutes(std::move(vehicles), solver) ==
587 SetValuesFromLP(index_to_cumul_variable_, global_offset, solver,
589 SetValuesFromLP(all_break_variables_, global_offset, solver, break_values);
596 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
598 std::vector<int64>* break_values) {
613 const int64 local_offset =
615 SetValuesFromLP(current_route_cumul_variables_, local_offset, solver,
617 SetValuesFromLP(current_route_break_variables_, local_offset, solver,
639 const int objective_ct =
642 for (
int variable = 0; variable < solver->
NumVariables(); variable++) {
649 for (
int vehicle : vehicles) {
651 index_to_cumul_variable_[
model->End(vehicle)], 1);
662 for (
int vehicle : vehicles) {
663 const int end_cumul_var = index_to_cumul_variable_[
model->End(vehicle)];
671 index_to_cumul_variable_[
model->Start(vehicle)], -1);
676 void DimensionCumulOptimizerCore::InitOptimizer(
677 RoutingLinearSolverWrapper* solver) {
679 index_to_cumul_variable_.assign(dimension_->
cumuls().size(), -1);
680 max_end_cumul_ = solver->CreateNewPositiveVariable();
681 min_start_cumul_ = solver->CreateNewPositiveVariable();
684 bool DimensionCumulOptimizerCore::ComputeRouteCumulBounds(
685 const std::vector<int64>& route,
const std::vector<int64>& fixed_transits,
686 int64 cumul_offset) {
687 const int route_size = route.size();
688 current_route_min_cumuls_.resize(route_size);
689 current_route_max_cumuls_.resize(route_size);
690 if (propagator_ !=
nullptr) {
691 for (
int pos = 0; pos < route_size; pos++) {
692 const int64 node = route[pos];
693 current_route_min_cumuls_[pos] = propagator_->CumulMin(node);
694 DCHECK_GE(current_route_min_cumuls_[pos], 0);
695 current_route_max_cumuls_[pos] = propagator_->CumulMax(node);
696 DCHECK_GE(current_route_max_cumuls_[pos], current_route_min_cumuls_[pos]);
702 for (
int pos = 0; pos < route_size; ++pos) {
703 if (!GetCumulBoundsWithOffset(*dimension_, route[pos], cumul_offset,
704 ¤t_route_min_cumuls_[pos],
705 ¤t_route_max_cumuls_[pos])) {
712 for (
int pos = 1; pos < route_size; ++pos) {
714 current_route_min_cumuls_[pos] =
std::max(
715 current_route_min_cumuls_[pos],
717 CapAdd(current_route_min_cumuls_[pos - 1], fixed_transits[pos - 1]),
719 current_route_min_cumuls_[pos] = GetFirstPossibleValueForCumulWithOffset(
720 *dimension_, route[pos], current_route_min_cumuls_[pos], cumul_offset);
721 if (current_route_min_cumuls_[pos] > current_route_max_cumuls_[pos]) {
726 for (
int pos = route_size - 2; pos >= 0; --pos) {
729 if (current_route_max_cumuls_[pos + 1] <
kint64max) {
731 current_route_max_cumuls_[pos] =
std::min(
732 current_route_max_cumuls_[pos],
734 CapSub(current_route_max_cumuls_[pos + 1], fixed_transits[pos]),
736 current_route_max_cumuls_[pos] = GetLastPossibleValueForCumulWithOffset(
737 *dimension_, route[pos], current_route_max_cumuls_[pos],
739 if (current_route_max_cumuls_[pos] < current_route_min_cumuls_[pos]) {
747 bool DimensionCumulOptimizerCore::SetRouteCumulConstraints(
748 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
749 int64 cumul_offset,
bool optimize_costs, RoutingLinearSolverWrapper* solver,
750 int64* route_transit_cost,
int64* route_cost_offset) {
751 RoutingModel*
const model = dimension_->
model();
753 std::vector<int64> path;
755 int node =
model->Start(vehicle);
756 path.push_back(node);
757 while (!
model->IsEnd(node)) {
758 node = next_accessor(node);
759 path.push_back(node);
763 const int path_size = path.size();
765 std::vector<int64> fixed_transit(path_size - 1);
769 for (
int pos = 1; pos < path_size; ++pos) {
770 fixed_transit[pos - 1] = transit_accessor(path[pos - 1], path[pos]);
774 if (!ComputeRouteCumulBounds(path, fixed_transit, cumul_offset)) {
780 std::vector<int>& lp_cumuls = current_route_cumul_variables_;
781 lp_cumuls.assign(path_size, -1);
782 for (
int pos = 0; pos < path_size; ++pos) {
783 const int lp_cumul = solver->CreateNewPositiveVariable();
784 index_to_cumul_variable_[path[pos]] = lp_cumul;
785 lp_cumuls[pos] = lp_cumul;
786 if (!solver->SetVariableBounds(lp_cumul, current_route_min_cumuls_[pos],
787 current_route_max_cumuls_[pos])) {
790 const SortedDisjointIntervalList& forbidden =
792 if (forbidden.NumIntervals() > 0) {
793 std::vector<int64> starts;
794 std::vector<int64> ends;
795 for (
const ClosedInterval
interval :
797 path[pos],
CapAdd(current_route_min_cumuls_[pos], cumul_offset),
798 CapAdd(current_route_max_cumuls_[pos], cumul_offset))) {
802 solver->SetVariableDisjointBounds(lp_cumul, starts, ends);
806 std::vector<int> lp_slacks(path_size - 1, -1);
807 for (
int pos = 0; pos < path_size - 1; ++pos) {
808 const IntVar* cp_slack = dimension_->
SlackVar(path[pos]);
809 lp_slacks[pos] = solver->CreateNewPositiveVariable();
810 if (!solver->SetVariableBounds(lp_slacks[pos], cp_slack->Min(),
820 for (
int pos = 0; pos < path_size - 1; ++pos) {
822 solver->CreateNewConstraint(fixed_transit[pos], fixed_transit[pos]);
823 solver->SetCoefficient(
ct, lp_cumuls[pos + 1], 1);
824 solver->SetCoefficient(
ct, lp_cumuls[pos], -1);
825 solver->SetCoefficient(
ct, lp_slacks[pos], -1);
827 if (route_cost_offset !=
nullptr) *route_cost_offset = 0;
828 if (optimize_costs) {
830 for (
int pos = 0; pos < path_size; ++pos) {
834 if (
coef == 0)
continue;
836 if (
bound < cumul_offset && route_cost_offset !=
nullptr) {
838 *route_cost_offset =
CapAdd(*route_cost_offset,
842 if (current_route_max_cumuls_[pos] <=
bound) {
846 const int soft_ub_diff = solver->CreateNewPositiveVariable();
847 solver->SetObjectiveCoefficient(soft_ub_diff,
coef);
850 solver->SetCoefficient(
ct, lp_cumuls[pos], 1);
851 solver->SetCoefficient(
ct, soft_ub_diff, -1);
854 for (
int pos = 0; pos < path_size; ++pos) {
858 if (
coef == 0)
continue;
862 if (current_route_min_cumuls_[pos] >=
bound) {
866 const int soft_lb_diff = solver->CreateNewPositiveVariable();
867 solver->SetObjectiveCoefficient(soft_lb_diff,
coef);
870 solver->SetCoefficient(
ct, lp_cumuls[pos], 1);
871 solver->SetCoefficient(
ct, soft_lb_diff, 1);
875 std::vector<int> visited_pairs;
876 StoreVisitedPickupDeliveryPairsOnRoute(
877 *dimension_, vehicle, next_accessor, &visited_pairs,
878 &visited_pickup_delivery_indices_for_pair_);
879 for (
int pair_index : visited_pairs) {
880 const int64 pickup_index =
881 visited_pickup_delivery_indices_for_pair_[pair_index].first;
882 const int64 delivery_index =
883 visited_pickup_delivery_indices_for_pair_[pair_index].second;
884 visited_pickup_delivery_indices_for_pair_[pair_index] = {-1, -1};
887 if (delivery_index < 0) {
893 pair_index,
model->GetPickupIndexPairs(pickup_index)[0].second,
894 model->GetDeliveryIndexPairs(delivery_index)[0].second);
897 const int ct = solver->CreateNewConstraint(
kint64min, limit);
898 solver->SetCoefficient(
ct, index_to_cumul_variable_[delivery_index], 1);
899 solver->SetCoefficient(
ct, index_to_cumul_variable_[pickup_index], -1);
907 const int ct = solver->CreateNewConstraint(
kint64min, span_bound);
908 solver->SetCoefficient(
ct, lp_cumuls.back(), 1);
909 solver->SetCoefficient(
ct, lp_cumuls.front(), -1);
912 const int64 span_cost_coef =
914 if (optimize_costs && span_cost_coef > 0) {
915 solver->SetObjectiveCoefficient(lp_cumuls.back(), span_cost_coef);
916 solver->SetObjectiveCoefficient(lp_cumuls.front(), -span_cost_coef);
920 SimpleBoundCosts::BoundCost bound_cost =
922 if (bound_cost.bound <
kint64max && bound_cost.cost > 0) {
923 const int span_violation = solver->CreateNewPositiveVariable();
925 const int violation =
926 solver->CreateNewConstraint(
kint64min, bound_cost.bound);
927 solver->SetCoefficient(violation, lp_cumuls.back(), 1.0);
928 solver->SetCoefficient(violation, lp_cumuls.front(), -1.0);
929 solver->SetCoefficient(violation, span_violation, -1.0);
931 solver->SetObjectiveCoefficient(span_violation, bound_cost.cost);
937 int ct = solver->CreateNewConstraint(
kint64min, 0);
938 solver->SetCoefficient(
ct, min_start_cumul_, 1);
939 solver->SetCoefficient(
ct, lp_cumuls.front(), -1);
942 solver->SetCoefficient(
ct, max_end_cumul_, 1);
943 solver->SetCoefficient(
ct, lp_cumuls.back(), -1);
946 if (route_transit_cost !=
nullptr) {
947 if (optimize_costs && span_cost_coef > 0) {
948 const int64 total_fixed_transit = std::accumulate(
949 fixed_transit.begin(), fixed_transit.end(), 0,
CapAdd);
950 *route_transit_cost =
CapProd(total_fixed_transit, span_cost_coef);
952 *route_transit_cost = 0;
960 current_route_break_variables_.clear();
962 const std::vector<IntervalVar*>& breaks =
964 const int num_breaks = breaks.size();
968 if (num_breaks == 0) {
970 for (
const auto& distance_duration :
973 std::min(maximum_route_span, distance_duration.first);
976 const int ct = solver->CreateNewConstraint(
kint64min, maximum_route_span);
977 solver->SetCoefficient(
ct, lp_cumuls.back(), 1);
978 solver->SetCoefficient(
ct, lp_cumuls.front(), -1);
985 std::vector<int64> pre_travel(path_size - 1, 0);
986 std::vector<int64> post_travel(path_size - 1, 0);
988 const int pre_travel_index =
990 if (pre_travel_index != -1) {
994 const int post_travel_index =
996 if (post_travel_index != -1) {
1005 std::vector<int> lp_break_start;
1006 std::vector<int> lp_break_duration;
1007 std::vector<int> lp_break_end;
1008 if (solver->IsCPSATSolver()) {
1009 lp_break_start.resize(num_breaks, -1);
1010 lp_break_duration.resize(num_breaks, -1);
1011 lp_break_end.resize(num_breaks, -1);
1014 std::vector<int> slack_exact_lower_bound_ct(path_size - 1, -1);
1015 std::vector<int> slack_linear_lower_bound_ct(path_size - 1, -1);
1017 const int64 vehicle_start_min = current_route_min_cumuls_.front();
1018 const int64 vehicle_start_max = current_route_max_cumuls_.front();
1019 const int64 vehicle_end_min = current_route_min_cumuls_.back();
1020 const int64 vehicle_end_max = current_route_max_cumuls_.back();
1021 const int all_break_variables_offset =
1022 vehicle_to_all_break_variables_offset_[vehicle];
1023 for (
int br = 0; br < num_breaks; ++br) {
1024 const IntervalVar& break_var = *breaks[br];
1025 if (!break_var.MustBePerformed())
continue;
1026 const int64 break_start_min =
CapSub(break_var.StartMin(), cumul_offset);
1027 const int64 break_start_max =
CapSub(break_var.StartMax(), cumul_offset);
1028 const int64 break_end_min =
CapSub(break_var.EndMin(), cumul_offset);
1029 const int64 break_end_max =
CapSub(break_var.EndMax(), cumul_offset);
1030 const int64 break_duration_min = break_var.DurationMin();
1031 const int64 break_duration_max = break_var.DurationMax();
1034 if (solver->IsCPSATSolver()) {
1035 if (break_end_max <= vehicle_start_min ||
1036 vehicle_end_max <= break_start_min) {
1037 all_break_variables_[all_break_variables_offset + 2 * br] = -1;
1038 all_break_variables_[all_break_variables_offset + 2 * br + 1] = -1;
1039 current_route_break_variables_.push_back(-1);
1040 current_route_break_variables_.push_back(-1);
1043 lp_break_start[br] =
1044 solver->AddVariable(break_start_min, break_start_max);
1045 lp_break_end[br] = solver->AddVariable(break_end_min, break_end_max);
1046 lp_break_duration[br] =
1047 solver->AddVariable(break_duration_min, break_duration_max);
1049 solver->AddLinearConstraint(0, 0,
1050 {{lp_break_end[br], 1},
1051 {lp_break_start[br], -1},
1052 {lp_break_duration[br], -1}});
1054 all_break_variables_[all_break_variables_offset + 2 * br] =
1056 all_break_variables_[all_break_variables_offset + 2 * br + 1] =
1058 current_route_break_variables_.push_back(lp_break_start[br]);
1059 current_route_break_variables_.push_back(lp_break_end[br]);
1061 if (break_end_min <= vehicle_start_max ||
1062 vehicle_end_min <= break_start_max) {
1070 const int break_in_one_slack_ct = solver->CreateNewConstraint(1, 1);
1072 if (solver->IsCPSATSolver()) {
1074 if (break_end_min <= vehicle_start_max) {
1075 const int ct = solver->AddLinearConstraint(
1076 0,
kint64max, {{lp_cumuls.front(), 1}, {lp_break_end[br], -1}});
1077 const int break_is_before_route = solver->AddVariable(0, 1);
1078 solver->SetEnforcementLiteral(
ct, break_is_before_route);
1079 solver->SetCoefficient(break_in_one_slack_ct, break_is_before_route, 1);
1082 if (vehicle_end_min <= break_start_max) {
1083 const int ct = solver->AddLinearConstraint(
1084 0,
kint64max, {{lp_break_start[br], 1}, {lp_cumuls.back(), -1}});
1085 const int break_is_after_route = solver->AddVariable(0, 1);
1086 solver->SetEnforcementLiteral(
ct, break_is_after_route);
1087 solver->SetCoefficient(break_in_one_slack_ct, break_is_after_route, 1);
1092 for (
int pos = 0; pos < path_size - 1; ++pos) {
1095 const int64 slack_start_min =
1096 CapAdd(current_route_min_cumuls_[pos], pre_travel[pos]);
1097 if (slack_start_min > break_start_max)
break;
1098 const int64 slack_end_max =
1099 CapSub(current_route_max_cumuls_[pos + 1], post_travel[pos]);
1100 if (break_end_min > slack_end_max)
continue;
1101 const int64 slack_duration_max =
1103 current_route_min_cumuls_[pos]),
1104 fixed_transit[pos]),
1106 if (slack_duration_max < break_duration_min)
continue;
1113 const int break_in_slack = solver->AddVariable(0, 1);
1114 solver->SetCoefficient(break_in_one_slack_ct, break_in_slack, 1);
1115 if (slack_linear_lower_bound_ct[pos] == -1) {
1116 slack_linear_lower_bound_ct[pos] =
1117 solver->AddLinearConstraint(
kint64min, 0, {{lp_slacks[pos], -1}});
1119 solver->SetCoefficient(slack_linear_lower_bound_ct[pos], break_in_slack,
1120 break_duration_min);
1121 if (solver->IsCPSATSolver()) {
1126 const int break_duration_in_slack =
1127 solver->AddVariable(0, slack_duration_max);
1128 solver->AddProductConstraint(break_duration_in_slack,
1129 {break_in_slack, lp_break_duration[br]});
1130 if (slack_exact_lower_bound_ct[pos] == -1) {
1131 slack_exact_lower_bound_ct[pos] =
1132 solver->AddLinearConstraint(
kint64min, 0, {{lp_slacks[pos], -1}});
1134 solver->SetCoefficient(slack_exact_lower_bound_ct[pos],
1135 break_duration_in_slack, 1);
1138 const int break_start_after_current_ct = solver->AddLinearConstraint(
1140 {{lp_break_start[br], 1}, {lp_cumuls[pos], -1}});
1141 solver->SetEnforcementLiteral(break_start_after_current_ct,
1144 const int break_ends_before_next_ct = solver->AddLinearConstraint(
1146 {{lp_cumuls[pos + 1], 1}, {lp_break_end[br], -1}});
1147 solver->SetEnforcementLiteral(break_ends_before_next_ct,
1153 if (!solver->IsCPSATSolver())
return true;
1159 if (!
interval->MustBePerformed())
return true;
1162 for (
int br = 1; br < num_breaks; ++br) {
1163 solver->AddLinearConstraint(
1164 0,
kint64max, {{lp_break_end[br - 1], -1}, {lp_break_start[br], 1}});
1167 for (
const auto& distance_duration :
1169 const int64 limit = distance_duration.first;
1170 const int64 min_break_duration = distance_duration.second;
1198 int previous_cover = solver->AddVariable(
CapAdd(vehicle_start_min, limit),
1199 CapAdd(vehicle_start_max, limit));
1200 solver->AddLinearConstraint(limit, limit,
1201 {{previous_cover, 1}, {lp_cumuls.front(), -1}});
1202 for (
int br = 0; br < num_breaks; ++br) {
1203 if (lp_break_start[br] == -1)
continue;
1204 const int64 break_end_min =
CapSub(breaks[br]->EndMin(), cumul_offset);
1205 const int64 break_end_max =
CapSub(breaks[br]->EndMax(), cumul_offset);
1208 const int break_is_eligible = solver->AddVariable(0, 1);
1209 const int break_is_not_eligible = solver->AddVariable(0, 1);
1211 solver->AddLinearConstraint(
1212 1, 1, {{break_is_eligible, 1}, {break_is_not_eligible, 1}});
1213 const int positive_ct = solver->AddLinearConstraint(
1215 {{lp_break_end[br], 1}, {lp_break_start[br], -1}});
1216 solver->SetEnforcementLiteral(positive_ct, break_is_eligible);
1217 const int negative_ct = solver->AddLinearConstraint(
1219 {{lp_break_end[br], 1}, {lp_break_start[br], -1}});
1220 solver->SetEnforcementLiteral(negative_ct, break_is_not_eligible);
1227 const int break_cover = solver->AddVariable(
1230 const int limit_cover_ct = solver->AddLinearConstraint(
1231 limit, limit, {{break_cover, 1}, {lp_break_end[br], -1}});
1232 solver->SetEnforcementLiteral(limit_cover_ct, break_is_eligible);
1233 const int empty_cover_ct = solver->AddLinearConstraint(
1234 CapAdd(vehicle_start_min, limit),
CapAdd(vehicle_start_min, limit),
1235 {{break_cover, 1}});
1236 solver->SetEnforcementLiteral(empty_cover_ct, break_is_not_eligible);
1240 solver->AddMaximumConstraint(cover, {previous_cover, break_cover});
1243 const int route_end_is_not_covered = solver->AddReifiedLinearConstraint(
1244 1,
kint64max, {{lp_cumuls.back(), 1}, {previous_cover, -1}});
1245 const int break_start_cover_ct = solver->AddLinearConstraint(
1246 0,
kint64max, {{previous_cover, 1}, {lp_break_start[br], -1}});
1247 solver->SetEnforcementLiteral(break_start_cover_ct,
1248 route_end_is_not_covered);
1250 previous_cover = cover;
1252 solver->AddLinearConstraint(0,
kint64max,
1253 {{previous_cover, 1}, {lp_cumuls.back(), -1}});
1259 void DimensionCumulOptimizerCore::SetGlobalConstraints(
1260 bool optimize_costs, RoutingLinearSolverWrapper* solver) {
1264 if (optimize_costs && global_span_coeff > 0) {
1265 solver->SetObjectiveCoefficient(max_end_cumul_, global_span_coeff);
1266 solver->SetObjectiveCoefficient(min_start_cumul_, -global_span_coeff);
1270 for (
const RoutingDimension::NodePrecedence& precedence :
1272 const int first_cumul_var = index_to_cumul_variable_[precedence.first_node];
1273 const int second_cumul_var =
1274 index_to_cumul_variable_[precedence.second_node];
1275 if (first_cumul_var < 0 || second_cumul_var < 0) {
1280 DCHECK_NE(first_cumul_var, second_cumul_var)
1281 <<
"Dimension " << dimension_->
name()
1282 <<
" has a self-precedence on node " << precedence.first_node <<
".";
1285 const int ct = solver->CreateNewConstraint(precedence.offset,
kint64max);
1286 solver->SetCoefficient(
ct, second_cumul_var, 1);
1287 solver->SetCoefficient(
ct, first_cumul_var, -1);
1291 void DimensionCumulOptimizerCore::SetValuesFromLP(
1292 const std::vector<int>& lp_variables,
int64 offset,
1293 RoutingLinearSolverWrapper* solver, std::vector<int64>* lp_values) {
1294 if (lp_values ==
nullptr)
return;
1295 lp_values->assign(lp_variables.size(),
kint64min);
1296 for (
int i = 0; i < lp_variables.size(); i++) {
1297 const int cumul_var = lp_variables[i];
1298 if (cumul_var < 0)
continue;
1299 const double lp_value_double = solver->GetValue(cumul_var);
1300 const int64 lp_value_int64 =
1304 (*lp_values)[i] =
CapAdd(lp_value_int64, offset);
1310 : optimizer_core_(dimension,
1312 !dimension->GetNodePrecedences().empty()) {
1314 absl::make_unique<RoutingGlopWrapper>(GetGlopParametersForGlobalLP());
1318 const std::function<
int64(
int64)>& next_accessor,
1319 int64* optimal_cost_without_transits) {
1321 int64 transit_cost = 0;
1322 if (optimizer_core_.
Optimize(next_accessor, solver_.get(),
nullptr,
nullptr,
1323 &
cost, &transit_cost)) {
1324 if (optimal_cost_without_transits !=
nullptr) {
1325 *optimal_cost_without_transits =
CapSub(
cost, transit_cost);
1333 const std::function<
int64(
int64)>& next_accessor,
1334 std::vector<int64>* optimal_cumuls, std::vector<int64>* optimal_breaks) {
1335 return optimizer_core_.
Optimize(next_accessor, solver_.get(), optimal_cumuls,
1336 optimal_breaks,
nullptr,
nullptr);
1340 const std::function<
int64(
int64)>& next_accessor) {
1341 return optimizer_core_.
Optimize(next_accessor, solver_.get(),
nullptr,
1342 nullptr,
nullptr,
nullptr);
1346 const std::function<
int64(
int64)>& next_accessor,
1347 std::vector<int64>* packed_cumuls, std::vector<int64>* packed_breaks) {
1349 packed_cumuls, packed_breaks);
#define DCHECK_NE(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
bool PropagateCumulBounds(const std::function< int64(int64)> &next_accessor, int64 cumul_offset)
const RoutingDimension & dimension() const
CumulBoundsPropagator(const RoutingDimension *dimension)
bool OptimizeAndPack(const std::function< int64(int64)> &next_accessor, RoutingLinearSolverWrapper *solver, std::vector< int64 > *cumul_values, std::vector< int64 > *break_values)
DimensionCumulOptimizerCore(const RoutingDimension *dimension, bool use_precedence_propagator)
const RoutingDimension * dimension() const
bool Optimize(const std::function< int64(int64)> &next_accessor, RoutingLinearSolverWrapper *solver, std::vector< int64 > *cumul_values, std::vector< int64 > *break_values, int64 *cost, int64 *transit_cost, bool clear_lp=true)
DimensionSchedulingStatus OptimizeAndPackSingleRoute(int vehicle, const std::function< int64(int64)> &next_accessor, RoutingLinearSolverWrapper *solver, std::vector< int64 > *cumul_values, std::vector< int64 > *break_values)
DimensionSchedulingStatus OptimizeSingleRoute(int vehicle, const std::function< int64(int64)> &next_accessor, RoutingLinearSolverWrapper *solver, std::vector< int64 > *cumul_values, std::vector< int64 > *break_values, int64 *cost, int64 *transit_cost, bool clear_lp=true)
bool ComputeCumuls(const std::function< int64(int64)> &next_accessor, std::vector< int64 > *optimal_cumuls, std::vector< int64 > *optimal_breaks)
bool IsFeasible(const std::function< int64(int64)> &next_accessor)
GlobalDimensionCumulOptimizer(const RoutingDimension *dimension)
bool ComputeCumulCostWithoutFixedTransits(const std::function< int64(int64)> &next_accessor, int64 *optimal_cost_without_transits)
bool ComputePackedCumuls(const std::function< int64(int64)> &next_accessor, std::vector< int64 > *packed_cumuls, std::vector< int64 > *packed_breaks)
virtual int64 Max() const =0
virtual int64 Min() const =0
DimensionSchedulingStatus ComputePackedRouteCumuls(int vehicle, const std::function< int64(int64)> &next_accessor, std::vector< int64 > *packed_cumuls, std::vector< int64 > *packed_breaks)
LocalDimensionCumulOptimizer(const RoutingDimension *dimension, RoutingSearchParameters::SchedulingSolver solver_type)
const RoutingDimension * dimension() const
DimensionSchedulingStatus ComputeRouteCumuls(int vehicle, const std::function< int64(int64)> &next_accessor, std::vector< int64 > *optimal_cumuls, std::vector< int64 > *optimal_breaks)
DimensionSchedulingStatus ComputeRouteCumulCost(int vehicle, const std::function< int64(int64)> &next_accessor, int64 *optimal_cost)
DimensionSchedulingStatus ComputeRouteCumulCostWithoutFixedTransits(int vehicle, const std::function< int64(int64)> &next_accessor, int64 *optimal_cost_without_transits)
static int64 FastInt64Round(double x)
Dimensions represent quantities accumulated at nodes along the routes.
SimpleBoundCosts::BoundCost GetSoftSpanUpperBoundForVehicle(int vehicle) const
const std::vector< IntVar * > & cumuls() const
Like CumulVar(), TransitVar(), SlackVar() but return the whole variable vectors instead (indexed by i...
int64 global_span_cost_coefficient() const
const std::vector< std::pair< int64, int64 > > & GetBreakDistanceDurationOfVehicle(int vehicle) const
Returns the pairs (distance, duration) specified by break distance constraints.
int64 GetSpanCostCoefficientForVehicle(int vehicle) const
RoutingModel * model() const
Returns the model on which the dimension was created.
int64 GetGlobalOptimizerOffset() const
int64 GetCumulVarSoftLowerBoundCoefficient(int64 index) const
Returns the cost coefficient of the soft lower bound of a cumul variable for a given variable index.
bool HasCumulVarSoftLowerBound(int64 index) const
Returns true if a soft lower bound has been set for a given variable index.
int64 GetCumulVarSoftLowerBound(int64 index) const
Returns the soft lower bound of a cumul variable for a given variable index.
bool HasBreakConstraints() const
Returns true if any break interval or break distance was defined.
int64 GetLocalOptimizerOffsetForVehicle(int vehicle) const
int GetPreTravelEvaluatorOfVehicle(int vehicle) const
!defined(SWIGPYTHON)
const std::vector< IntervalVar * > & GetBreakIntervalsOfVehicle(int vehicle) const
Returns the break intervals set by SetBreakIntervalsOfVehicle().
int64 GetPickupToDeliveryLimitForPair(int pair_index, int pickup, int delivery) const
int64 GetCumulVarSoftUpperBound(int64 index) const
Returns the soft upper bound of a cumul variable for a given variable index.
const RoutingModel::TransitCallback2 & transit_evaluator(int vehicle) const
Returns the callback evaluating the transit value between two node indices for a given vehicle.
IntVar * SlackVar(int64 index) const
SortedDisjointIntervalList GetAllowedIntervalsInRange(int64 index, int64 min_value, int64 max_value) const
Returns allowed intervals for a given node in a given interval.
const std::string & name() const
Returns the name of the dimension.
const std::vector< NodePrecedence > & GetNodePrecedences() const
bool HasCumulVarSoftUpperBound(int64 index) const
Returns true if a soft upper bound has been set for a given variable index.
bool HasSoftSpanUpperBounds() const
int64 GetCumulVarSoftUpperBoundCoefficient(int64 index) const
Returns the cost coefficient of the soft upper bound of a cumul variable for a given variable index.
int GetPostTravelEvaluatorOfVehicle(int vehicle) const
const std::vector< SortedDisjointIntervalList > & forbidden_intervals() const
Returns forbidden intervals for each node.
int64 GetSpanUpperBoundForVehicle(int vehicle) const
virtual void SetCoefficient(int ct, int index, double coefficient)=0
virtual int NumVariables() const =0
virtual int CreateNewConstraint(int64 lower_bound, int64 upper_bound)=0
virtual double GetObjectiveCoefficient(int index) const =0
virtual int64 GetObjectiveValue() const =0
virtual int64 GetVariableLowerBound(int index) const =0
virtual bool SetVariableBounds(int index, int64 lower_bound, int64 upper_bound)=0
virtual void ClearObjective()=0
virtual double GetValue(int index) const =0
virtual DimensionSchedulingStatus Solve(absl::Duration duration_limit)=0
virtual void SetObjectiveCoefficient(int index, double coefficient)=0
virtual bool SolutionIsInteger() const =0
const IndexPairs & GetPickupAndDeliveryPairs() const
Returns pickup and delivery pairs currently in the model.
int vehicles() const
Returns the number of vehicle routes in the model.
static const int64 kint64max
static const int64 kint64min
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapSub(int64 x, int64 y)
int64 CapAdd(int64 x, int64 y)
DimensionSchedulingStatus
int64 CapProd(int64 x, int64 y)
void FillPathEvaluation(const std::vector< int64 > &path, const RoutingModel::TransitCallback2 &evaluator, std::vector< int64 > *values)
std::vector< double > lower_bounds