53 if (num_chain_tasks > 0) {
56 for (
int task = 0; task < num_chain_tasks; ++task) {
66 for (
int task = num_chain_tasks - 1; task >= 0; --task) {
70 if (time < tasks->
start_min[task])
return false;
75 const int num_tasks = tasks->
start_min.size();
76 for (
int task = 0; task < num_tasks; ++task) {
107 const int num_tasks = tasks->
start_min.size();
109 for (
int task = 0; task < num_tasks; ++task) {
115 for (
int task = 0; task < num_tasks; ++task) {
126 std::reverse(it, it + num_chain_tasks);
127 std::reverse(it + num_chain_tasks, it + num_tasks);
137 const int num_tasks = tasks->
start_min.size();
139 tasks_by_start_min_.resize(num_tasks);
140 std::iota(tasks_by_start_min_.begin(), tasks_by_start_min_.end(), 0);
142 tasks_by_start_min_.begin(), tasks_by_start_min_.end(),
143 [&](
int i,
int j) { return tasks->start_min[i] < tasks->start_min[j]; });
144 event_of_task_.resize(num_tasks);
145 for (
int event = 0;
event < num_tasks; ++event) {
146 event_of_task_[tasks_by_start_min_[event]] = event;
149 tasks_by_end_max_.resize(num_tasks);
150 std::iota(tasks_by_end_max_.begin(), tasks_by_end_max_.end(), 0);
152 tasks_by_end_max_.begin(), tasks_by_end_max_.end(),
153 [&](
int i,
int j) { return tasks->end_max[i] < tasks->end_max[j]; });
157 theta_lambda_tree_.
Reset(num_tasks);
158 for (
const int task : tasks_by_end_max_) {
170 for (
int i = num_tasks - 1; i >= 0; --i) {
171 const int task = tasks_by_end_max_[i];
177 int64 available_energy;
179 tasks->
end_max[task], &critical_event, &optional_event,
181 const int optional_task = tasks_by_start_min_[optional_event];
191 theta_lambda_tree_.
RemoveEvent(event_of_task_[task]);
198 const int num_tasks = tasks->
start_min.size();
200 tasks_by_start_min_.resize(num_tasks);
201 std::iota(tasks_by_start_min_.begin(), tasks_by_start_min_.end(), 0);
203 tasks_by_start_min_.begin(), tasks_by_start_min_.end(),
204 [&](
int i,
int j) { return tasks->start_min[i] < tasks->start_min[j]; });
205 event_of_task_.resize(num_tasks);
206 for (
int event = 0;
event < num_tasks; ++event) {
207 event_of_task_[tasks_by_start_min_[event]] = event;
209 theta_lambda_tree_.
Reset(num_tasks);
213 nonchain_tasks_by_start_max_.resize(num_tasks - num_chain_tasks);
214 std::iota(nonchain_tasks_by_start_max_.begin(),
215 nonchain_tasks_by_start_max_.end(), num_chain_tasks);
216 std::sort(nonchain_tasks_by_start_max_.begin(),
217 nonchain_tasks_by_start_max_.end(), [&tasks](
int i,
int j) {
218 return tasks->end_max[i] - tasks->duration_min[i] <
219 tasks->end_max[j] - tasks->duration_min[j];
224 int index_nonchain = 0;
225 for (
int i = 0; i < num_chain_tasks; ++i) {
228 while (index_nonchain < nonchain_tasks_by_start_max_.size()) {
229 const int task = nonchain_tasks_by_start_max_[index_nonchain];
234 event_of_task_[task], tasks->
start_min[task],
252 const int num_tasks = tasks->
start_min.size();
253 for (
int task = 0; task < num_tasks; ++task) {
289 const int route_start = 0;
291 const int num_tasks = tasks->
start_min.size();
310 for (
int task = tasks->
num_chain_tasks + 1; task < num_tasks; ++task) {
314 for (
int task = num_tasks - 2; task >= tasks->
num_chain_tasks; --task) {
320 while (index_break_by_emax < num_tasks &&
321 tasks->
end_max[index_break_by_emax] <= tasks->
end_max[route_start]) {
322 ++index_break_by_emax;
325 if (index_break_by_emax == num_tasks) {
341 int64 xor_active_tasks = route_start;
342 int num_active_tasks = 1;
344 const int64 route_start_time =
348 while (index_break_by_emax < num_tasks) {
352 if (index_break_by_smin < num_tasks) {
356 if (previous_time < route_start_time && route_start_time < current_time) {
357 current_time = route_start_time;
359 if (previous_time < route_end_time && route_end_time < current_time) {
360 current_time = route_end_time;
364 if (num_active_tasks == 1) {
367 if (xor_active_tasks != route_end) {
368 tasks->
end_min[xor_active_tasks] =
370 CapSub(current_time, max_distance));
371 if (xor_active_tasks != route_start) {
375 minimum_break_duration,
376 CapSub(
CapSub(current_time, max_distance), previous_time)));
381 while (index_break_by_smin < num_tasks &&
382 current_time == tasks->
start_min[index_break_by_smin]) {
384 minimum_break_duration) {
385 xor_active_tasks ^= index_break_by_smin;
388 ++index_break_by_smin;
390 while (index_break_by_emax < num_tasks &&
394 minimum_break_duration) {
395 xor_active_tasks ^= index_break_by_emax;
398 ++index_break_by_emax;
400 if (current_time == route_start_time) {
401 xor_active_tasks ^= route_start;
404 if (current_time == route_end_time) {
405 xor_active_tasks ^= route_end;
410 if (num_active_tasks <= 0)
return false;
411 if (num_active_tasks == 1) {
412 if (xor_active_tasks != route_start) {
417 if (xor_active_tasks != route_end) {
419 tasks->
duration_min[xor_active_tasks], minimum_break_duration);
423 previous_time = current_time;
431 if (num_chain_tasks < 1)
return true;
436 int64 sum_chain_durations = 0;
437 const auto duration_start = tasks->
duration_min.begin();
438 const auto duration_end = tasks->
duration_min.begin() + num_chain_tasks;
439 for (
auto it = duration_start; it != duration_end; ++it) {
440 sum_chain_durations =
CapAdd(sum_chain_durations, *it);
442 int64 sum_forced_nonchain_durations = 0;
443 for (
int i = num_chain_tasks; i < tasks->
start_min.size(); ++i) {
449 sum_forced_nonchain_durations =
454 CapAdd(sum_chain_durations, sum_forced_nonchain_durations));
458 const int64 end_minus_start =
472 if (num_chain_tasks < 1)
return true;
473 if (num_chain_tasks == tasks->
start_min.size())
return true;
474 const int task_index = num_chain_tasks;
476 const int64 min_possible_chain_end = tasks->
end_min[num_chain_tasks - 1];
479 int64 total_duration = 0;
481 total_duration_before_.resize(num_chain_tasks);
482 for (
int i = 0; i < num_chain_tasks; ++i) {
483 total_duration_before_[i] = total_duration;
493 const int64 chain_span_min =
494 min_possible_chain_end -
496 if (chain_span_min > tasks->
span_max) {
511 bool schedule_is_feasible =
false;
512 for (
int i = 0; i < num_chain_tasks; ++i) {
517 const int64 block_start_min =
520 const int64 block_start_max =
523 if (block_start_min > block_start_max)
continue;
537 const int64 head_inflection =
538 max_possible_chain_start + total_duration_before_[i];
541 const int64 tail_inflection = min_possible_chain_end -
542 (total_duration - total_duration_before_[i]) -
556 const int64 optimal_interval_min_start =
557 std::min(head_inflection, tail_inflection);
558 const int64 optimal_interval_max_start =
559 std::max(head_inflection, tail_inflection);
562 int64 block_start =
std::max(optimal_interval_min_start, block_start_min);
566 if (optimal_interval_max_start < block_start_min) {
568 block_start = block_start_min;
569 }
else if (block_start_max < optimal_interval_min_start) {
571 block_start = block_start_max;
574 const int64 head_duration =
575 std::max(block_start, head_inflection) - max_possible_chain_start;
576 const int64 tail_duration =
577 min_possible_chain_end -
std::min(block_start, tail_inflection);
578 const int64 optimal_span_at_i = head_duration + tail_duration;
579 span_min =
std::min(span_min, optimal_span_at_i);
580 schedule_is_feasible =
true;
582 if (!schedule_is_feasible || span_min > tasks->
span_max) {
594 const int num_nodes = path.size();
597 for (
int i = 0; i < num_nodes; ++i) {
604 const int64 before_visit =
606 const int64 after_visit =
607 (i == num_nodes - 1) ? 0 : travel_bounds.
pre_travels[i];
617 if (i == num_nodes - 1)
break;
630 CapAdd(pre_travel, post_travel))));
635 CapAdd(pre_travel, post_travel))));
651 const int num_travels = travel_bounds->
min_travels.size();
690 model_(dimension->
model()),
691 dimension_(dimension) {
692 vehicle_demons_.resize(model_->
vehicles());
696 for (
int vehicle = 0; vehicle < model_->
vehicles(); vehicle++) {
702 solver(),
this, &GlobalVehicleBreaksConstraint::PropagateVehicle,
703 "PropagateVehicle", vehicle);
706 interval->WhenAnything(vehicle_demons_[vehicle]);
709 const int num_cumuls = dimension_->
cumuls().size();
710 const int num_nexts = model_->
Nexts().size();
711 for (
int node = 0; node < num_cumuls; node++) {
713 solver(),
this, &GlobalVehicleBreaksConstraint::PropagateNode,
714 "PropagateNode", node);
715 if (node < num_nexts) {
725 for (
int vehicle = 0; vehicle < model_->
vehicles(); vehicle++) {
728 PropagateVehicle(vehicle);
736void GlobalVehicleBreaksConstraint::PropagateNode(
int node) {
739 if (vehicle < 0 || vehicle_demons_[vehicle] ==
nullptr)
return;
743void GlobalVehicleBreaksConstraint::FillPartialPathOfVehicle(
int vehicle) {
745 int current = model_->
Start(vehicle);
746 while (!model_->
IsEnd(current)) {
747 path_.push_back(current);
750 : model_->
End(vehicle);
752 path_.push_back(current);
755void GlobalVehicleBreaksConstraint::FillPathTravels(
756 const std::vector<int64>& path) {
757 const int num_travels = path.size() - 1;
760 for (
int i = 0; i < num_travels; ++i) {
768void GlobalVehicleBreaksConstraint::PropagateVehicle(
int vehicle) {
770 FillPartialPathOfVehicle(vehicle);
771 const int num_nodes = path_.size();
772 FillPathTravels(path_);
776 travel_bounds_.
pre_travels.assign(num_nodes - 1, 0);
812 task_translators_.clear();
813 for (
int i = 0; i < num_nodes; ++i) {
814 const int64 before_visit =
816 const int64 after_visit =
817 (i == num_nodes - 1) ? 0 : travel_bounds_.
pre_travels[i];
818 task_translators_.emplace_back(dimension_->
CumulVar(path_[i]), before_visit,
820 if (i == num_nodes - 1)
break;
821 task_translators_.emplace_back();
825 if (!
interval->MustBePerformed())
continue;
826 task_translators_.emplace_back(
interval);
830 const int num_tasks = tasks_.
start_min.size();
831 for (
int task = 0; task < num_tasks; ++task) {
832 task_translators_[task].SetStartMin(tasks_.
start_min[task]);
833 task_translators_[task].SetStartMax(tasks_.
start_max[task]);
834 task_translators_[task].SetDurationMin(tasks_.
duration_min[task]);
835 task_translators_[task].SetEndMin(tasks_.
end_min[task]);
836 task_translators_[task].SetEndMax(tasks_.
end_max[task]);
844 const int64 last_bound_arc =
845 num_nodes - 2 - (model_->
NextVar(path_[num_nodes - 2])->
Bound() ? 0 : 1);
846 for (
int i = 0; i <= last_bound_arc; ++i) {
847 const int64 arc_start_max =
850 const int64 arc_end_min =
852 i < num_nodes - 2 ? travel_bounds_.
pre_travels[i + 1] : 0);
853 int64 total_break_inside_arc = 0;
856 if (!
interval->MustBePerformed())
continue;
862 if (arc_start_max < interval_end_min &&
863 interval_start_max < arc_end_min) {
864 total_break_inside_arc += interval_duration_min;
873 bool has_optional =
false;
881 if (!has_optional)
return;
883 const std::vector<IntervalVar*>& break_intervals =
885 for (
int pos = 0; pos < num_nodes - 1; ++pos) {
887 const int64 visit_start_offset =
889 const int64 visit_start_max =
891 const int64 visit_end_offset =
892 (pos < num_nodes - 1) ? travel_bounds_.
pre_travels[pos] : 0;
893 const int64 visit_end_min =
896 for (IntervalVar*
interval : break_intervals) {
897 if (!
interval->MayBePerformed())
continue;
898 const bool interval_is_performed =
interval->MustBePerformed();
904 if (pos < num_nodes - 1 && interval_duration_min > current_slack_max) {
907 const int64 arc_start_offset =
909 const int64 arc_start_max = visit_start_max;
910 const int64 arc_end_offset =
911 (pos < num_nodes - 2) ? travel_bounds_.
pre_travels[pos + 1] : 0;
912 const int64 arc_end_min =
915 if (arc_start_max < interval_end_min) {
917 if (interval_is_performed) {
918 dimension_->
CumulVar(path_[pos + 1])
923 if (interval_start_max < arc_end_min) {
925 if (interval_is_performed) {
935 if (visit_start_max < interval_end_min) {
936 interval->SetStartMin(visit_end_min);
937 if (interval_is_performed) {
943 if (interval_start_max < visit_end_min) {
944 interval->SetEndMax(visit_start_max);
945 if (interval_is_performed) {
955class VehicleBreaksFilter :
public BasePathFilter {
957 VehicleBreaksFilter(
const RoutingModel& routing_model,
958 const RoutingDimension& dimension);
959 std::string DebugString()
const override {
return "VehicleBreaksFilter"; }
960 bool AcceptPath(
int64 path_start,
int64 chain_start,
961 int64 chain_end)
override;
965 void FillPathOfVehicle(
int64 vehicle);
966 std::vector<int64> path_;
968 const RoutingModel& model_;
969 const RoutingDimension& dimension_;
971 DisjunctivePropagator disjunctive_propagator_;
972 DisjunctivePropagator::Tasks tasks_;
974 std::vector<int64> old_start_min_;
975 std::vector<int64> old_start_max_;
976 std::vector<int64> old_end_min_;
977 std::vector<int64> old_end_max_;
979 std::vector<int> start_to_vehicle_;
980 TravelBounds travel_bounds_;
983VehicleBreaksFilter::VehicleBreaksFilter(
const RoutingModel& routing_model,
984 const RoutingDimension& dimension)
985 : BasePathFilter(routing_model.Nexts(),
986 routing_model.Size() + routing_model.vehicles()),
987 model_(routing_model),
988 dimension_(dimension) {
990 start_to_vehicle_.resize(Size(), -1);
991 for (
int i = 0; i < routing_model.vehicles(); ++i) {
992 start_to_vehicle_[routing_model.Start(i)] = i;
996void VehicleBreaksFilter::FillPathOfVehicle(
int64 vehicle) {
998 int current = model_.
Start(vehicle);
999 while (!model_.
IsEnd(current)) {
1000 path_.push_back(current);
1001 current = GetNext(current);
1003 path_.push_back(current);
1006bool VehicleBreaksFilter::AcceptPath(
int64 path_start,
int64 chain_start,
1008 const int vehicle = start_to_vehicle_[path_start];
1014 FillPathOfVehicle(vehicle);
1019 tasks_.num_chain_tasks = tasks_.start_min.size();
1023 tasks_.forbidden_intervals.clear();
1024 if (std::any_of(path_.begin(), path_.end(), [
this](
int64 node) {
1025 return dimension_.forbidden_intervals()[node].NumIntervals() > 0;
1027 tasks_.forbidden_intervals.assign(tasks_.start_min.size(),
nullptr);
1028 for (
int i = 0; i < path_.size(); ++i) {
1029 tasks_.forbidden_intervals[2 * i] =
1034 tasks_.distance_duration =
1039 bool is_feasible =
true;
1040 int maximum_num_iterations = 8;
1041 while (--maximum_num_iterations >= 0) {
1042 old_start_min_ = tasks_.start_min;
1043 old_start_max_ = tasks_.start_max;
1044 old_end_min_ = tasks_.end_min;
1045 old_end_max_ = tasks_.end_max;
1046 is_feasible = disjunctive_propagator_.
Propagate(&tasks_);
1047 if (!is_feasible)
break;
1049 if ((old_start_min_ == tasks_.start_min) &&
1050 (old_start_max_ == tasks_.start_max) &&
1051 (old_end_min_ == tasks_.end_min) && (old_end_max_ == tasks_.end_max)) {
1063 new VehicleBreaksFilter(routing_model, dimension));
#define DCHECK_LE(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
A constraint is the main modeling object.
A Demon is the base element of a propagation queue.
bool EdgeFinding(Tasks *tasks)
Does edge-finding deductions on all tasks.
bool Precedences(Tasks *tasks)
Propagates the deductions from the chain of precedences, if there is one.
bool DistanceDuration(Tasks *tasks)
Propagates distance_duration constraints, if any.
bool MirrorTasks(Tasks *tasks)
Transforms the problem with a time symmetry centered in 0.
bool ForbiddenIntervals(Tasks *tasks)
Tasks might have holes in their domain, this enforces such holes.
bool Propagate(Tasks *tasks)
Computes new bounds for all tasks, returns false if infeasible.
bool DetectablePrecedencesWithChain(Tasks *tasks)
Does detectable precedences deductions on tasks in the chain precedence, taking the time windows of n...
bool ChainSpanMinDynamic(Tasks *tasks)
Computes a lower bound of the span of the chain, taking into account only the first nonchain task.
bool ChainSpanMin(Tasks *tasks)
Propagates a lower bound of the chain span, end[num_chain_tasks] - start[0], to span_min.
void Post() override
This method is called when the constraint is processed by the solver.
void InitialPropagate() override
This method performs the initial propagation of the constraint.
GlobalVehicleBreaksConstraint(const RoutingDimension *dimension)
virtual void SetMax(int64 m)=0
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual void SetMin(int64 m)=0
virtual int64 Max() const =0
virtual int64 Min() const =0
virtual void WhenRange(Demon *d)=0
Attach a demon that will watch the min or the max of the expression.
virtual void WhenBound(Demon *d)=0
This method attaches a demon that will be awakened when the variable is bound.
Interval variables are often used in scheduling.
virtual int64 StartMax() const =0
virtual int64 DurationMax() const =0
virtual int64 EndMax() const =0
virtual bool MustBePerformed() const =0
These methods query, set, and watch the performed status of the interval var.
virtual int64 StartMin() const =0
These methods query, set, and watch the start position of the interval var.
virtual int64 EndMin() const =0
These methods query, set, and watch the end position of the interval var.
virtual int64 DurationMin() const =0
These methods query, set, and watch the duration of the interval var.
void EnqueueDelayedDemon(Demon *const d)
This method pushes the demon onto the propagation queue.
Dimensions represent quantities accumulated at nodes along the routes.
IntVar * CumulVar(int64 index) const
Get the cumul, transit and slack variables for the given node (given as int64 var index).
const std::vector< std::pair< int64, int64 > > & GetBreakDistanceDurationOfVehicle(int vehicle) const
Returns the pairs (distance, duration) specified by break distance constraints.
const std::vector< IntVar * > & cumuls() const
Like CumulVar(), TransitVar(), SlackVar() but return the whole variable vectors instead (indexed by i...
const RoutingModel::TransitCallback2 & transit_evaluator(int vehicle) const
Returns the callback evaluating the transit value between two node indices for a given vehicle.
bool HasBreakConstraints() const
Returns true if any break interval or break distance was defined.
IntVar * SlackVar(int64 index) const
int GetPreTravelEvaluatorOfVehicle(int vehicle) const
!defined(SWIGPYTHON)
RoutingModel * model() const
Returns the model on which the dimension was created.
const std::vector< IntervalVar * > & GetBreakIntervalsOfVehicle(int vehicle) const
Returns the break intervals set by SetBreakIntervalsOfVehicle().
IntVar * FixedTransitVar(int64 index) const
const std::vector< SortedDisjointIntervalList > & forbidden_intervals() const
Returns forbidden intervals for each node.
int GetPostTravelEvaluatorOfVehicle(int vehicle) const
Solver * solver() const
Returns the underlying constraint solver.
const TransitCallback2 & TransitCallback(int callback_index) const
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
const std::vector< IntVar * > & Nexts() const
Returns all next variables of the model, such that Nexts(i) is the next variable of the node correspo...
int vehicles() const
Returns the number of vehicle routes in the model.
IntVar * VehicleVar(int64 index) const
Returns the vehicle variable of the node corresponding to index.
int64 Start(int vehicle) const
Model inspection.
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
T * RevAlloc(T *object)
Registers the given object as being reversible.
void GetEventsWithOptionalEnvelopeGreaterThan(IntegerType target_envelope, int *critical_event, int *optional_event, IntegerType *available_energy) const
IntegerType GetOptionalEnvelope() const
void RemoveEvent(int event)
void Reset(int num_events)
void AddOrUpdateOptionalEvent(int event, IntegerType initial_envelope_opt, IntegerType energy_max)
void AddOrUpdateEvent(int event, IntegerType initial_envelope, IntegerType energy_min, IntegerType energy_max)
IntegerType GetEnvelope() const
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 CapAdd(int64 x, int64 y)
void AppendTasksFromPath(const std::vector< int64 > &path, const TravelBounds &travel_bounds, const RoutingDimension &dimension, DisjunctivePropagator::Tasks *tasks)
IntVarLocalSearchFilter * MakeVehicleBreaksFilter(const RoutingModel &routing_model, const RoutingDimension &dimension)
int64 CapSub(int64 x, int64 y)
void FillTravelBoundsOfVehicle(int vehicle, const std::vector< int64 > &path, const RoutingDimension &dimension, TravelBounds *travel_bounds)
void AppendTasksFromIntervals(const std::vector< IntervalVar * > &intervals, DisjunctivePropagator::Tasks *tasks)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
Demon * MakeDelayedConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
void FillPathEvaluation(const std::vector< int64 > &path, const RoutingModel::TransitCallback2 &evaluator, std::vector< int64 > *values)
A structure to hold tasks described by their features.
std::vector< int64 > end_max
std::vector< int64 > start_min
std::vector< int64 > duration_min
std::vector< int64 > start_max
std::vector< const SortedDisjointIntervalList * > forbidden_intervals
std::vector< bool > is_preemptible
std::vector< int64 > duration_max
std::vector< std::pair< int64, int64 > > distance_duration
std::vector< int64 > end_min
std::vector< int64 > max_travels
std::vector< int64 > min_travels
std::vector< int64 > post_travels
std::vector< int64 > pre_travels