26 return model.GetVehicleClassesCount() == 1;
30 int AddVariable(CpModelProto* cp_model,
int64 lb,
int64 ub) {
31 const int index = cp_model->variables_size();
32 IntegerVariableProto*
const var = cp_model->add_variables();
47 return a.tail ==
b.tail &&
a.head ==
b.head;
50 friend bool operator<(
const Arc&
a,
const Arc&
b) {
51 return a.tail ==
b.tail ?
a.head <
b.head :
a.tail <
b.tail;
53 friend std::ostream&
operator<<(std::ostream& strm,
const Arc& arc) {
54 return strm <<
"{" << arc.tail <<
", " << arc.head <<
"}";
57 friend H AbslHashValue(H h,
const Arc&
a) {
58 return H::combine(std::move(h),
a.tail,
a.head);
62 using ArcVarMap = std::map<Arc, int>;
66 void AddDimensions(
const RoutingModel&
model,
const ArcVarMap& arc_vars,
67 CpModelProto* cp_model) {
68 for (
const RoutingDimension* dimension :
model.GetDimensions()) {
71 dimension->transit_evaluator(0);
72 std::vector<int> cumuls(dimension->cumuls().size(), -1);
73 const int64 min_start = dimension->cumuls()[
model.Start(0)]->Min();
75 dimension->vehicle_capacities()[0]);
76 for (
int i = 0; i < cumuls.size(); ++i) {
77 if (
model.IsStart(i) ||
model.IsEnd(i))
continue;
79 const int64 cumul_min =
81 std::max(dimension->cumuls()[i]->Min(),
83 const int64 cumul_max =
85 std::min(dimension->cumuls()[i]->Max(),
87 cumuls[i] = AddVariable(cp_model, cumul_min, cumul_max);
89 for (
const auto arc_var : arc_vars) {
90 const int tail = arc_var.first.tail;
91 const int head = arc_var.first.head;
95 ConstraintProto*
ct = cp_model->add_constraints();
96 ct->add_enforcement_literal(arc_var.second);
97 LinearConstraintProto* arg =
ct->mutable_linear();
98 arg->add_domain(transit(
tail,
head));
100 arg->add_vars(cumuls[
tail]);
102 arg->add_vars(cumuls[
head]);
108 std::vector<int> CreateRanks(
const RoutingModel&
model,
109 const ArcVarMap& arc_vars,
110 CpModelProto* cp_model) {
111 const int depot = GetDepotFromModel(
model);
112 const int size =
model.Size() +
model.vehicles();
113 const int rank_size =
model.Size() -
model.vehicles();
114 std::vector<int> ranks(size, -1);
115 for (
int i = 0; i < size; ++i) {
116 if (
model.IsStart(i) ||
model.IsEnd(i))
continue;
117 ranks[i] = AddVariable(cp_model, 0, rank_size);
119 ranks[depot] = AddVariable(cp_model, 0, 0);
120 for (
const auto arc_var : arc_vars) {
121 const int tail = arc_var.first.tail;
122 const int head = arc_var.first.head;
125 ConstraintProto*
ct = cp_model->add_constraints();
126 ct->add_enforcement_literal(arc_var.second);
127 LinearConstraintProto* arg =
ct->mutable_linear();
130 arg->add_vars(ranks[
tail]);
132 arg->add_vars(ranks[
head]);
142 std::vector<int> CreateVehicleVars(
const RoutingModel&
model,
143 const ArcVarMap& arc_vars,
144 CpModelProto* cp_model) {
145 const int depot = GetDepotFromModel(
model);
146 const int size =
model.Size() +
model.vehicles();
147 std::vector<int> vehicles(size, -1);
148 for (
int i = 0; i < size; ++i) {
149 if (
model.IsStart(i) ||
model.IsEnd(i))
continue;
150 vehicles[i] = AddVariable(cp_model, 0, size - 1);
152 for (
const auto arc_var : arc_vars) {
153 const int tail = arc_var.first.tail;
154 const int head = arc_var.first.head;
158 ConstraintProto*
ct = cp_model->add_constraints();
159 ct->add_enforcement_literal(arc_var.second);
160 LinearConstraintProto* arg =
ct->mutable_linear();
161 arg->add_domain(
head);
162 arg->add_domain(
head);
163 arg->add_vars(vehicles[
head]);
168 ConstraintProto*
ct = cp_model->add_constraints();
169 ct->add_enforcement_literal(arc_var.second);
170 LinearConstraintProto* arg =
ct->mutable_linear();
173 arg->add_vars(vehicles[
tail]);
175 arg->add_vars(vehicles[
head]);
181 void AddPickupDeliveryConstraints(
const RoutingModel&
model,
182 const ArcVarMap& arc_vars,
183 CpModelProto* cp_model) {
184 if (
model.GetPickupAndDeliveryPairs().empty())
return;
185 const std::vector<int> ranks = CreateRanks(
model, arc_vars, cp_model);
186 const std::vector<int> vehicles =
187 CreateVehicleVars(
model, arc_vars, cp_model);
188 for (
const auto& pairs :
model.GetPickupAndDeliveryPairs()) {
189 const int64 pickup = pairs.first[0];
190 const int64 delivery = pairs.second[0];
193 ConstraintProto*
ct = cp_model->add_constraints();
194 LinearConstraintProto* arg =
ct->mutable_linear();
197 arg->add_vars(ranks[delivery]);
199 arg->add_vars(ranks[pickup]);
204 ConstraintProto*
ct = cp_model->add_constraints();
205 LinearConstraintProto* arg =
ct->mutable_linear();
208 arg->add_vars(vehicles[delivery]);
210 arg->add_vars(vehicles[pickup]);
222 ArcVarMap PopulateMultiRouteModelFromRoutingModel(
const RoutingModel&
model,
223 CpModelProto* cp_model) {
225 const int num_nodes =
model.Nexts().size();
226 const int depot = GetDepotFromModel(
model);
231 std::unique_ptr<IntVarIterator> iter(
232 model.NextVar(
tail)->MakeDomainIterator(
false));
233 for (
int head : InitAndGetValues(iter.get())) {
240 if (head_index == tail_index)
continue;
244 const Arc arc = {tail_index, head_index};
246 const int index = AddVariable(cp_model, 0, 1);
248 cp_model->mutable_objective()->add_vars(
index);
249 cp_model->mutable_objective()->add_coeffs(
cost);
259 LinearConstraintProto*
ct = cp_model->add_constraints()->mutable_linear();
262 for (
int node = 0; node < num_nodes; ++node) {
263 if (
model.IsStart(node) ||
model.IsEnd(node))
continue;
272 LinearConstraintProto*
ct = cp_model->add_constraints()->mutable_linear();
277 for (
int node = 0; node < num_nodes; ++node) {
278 if (
model.IsStart(node) ||
model.IsEnd(node))
continue;
286 LinearConstraintProto*
ct = cp_model->add_constraints()->mutable_linear();
289 std::unique_ptr<IntVarIterator> iter(
290 model.NextVar(
tail)->MakeDomainIterator(
false));
291 bool depot_added =
false;
292 for (
int head : InitAndGetValues(iter.get())) {
296 if (depot_added)
continue;
307 LinearConstraintProto*
ct = cp_model->add_constraints()->mutable_linear();
319 AddPickupDeliveryConstraints(
model, arc_vars, cp_model);
321 AddDimensions(
model, arc_vars, cp_model);
326 RoutesConstraintProto* routes_ct =
327 cp_model->add_constraints()->mutable_routes();
328 for (
const auto arc_var : arc_vars) {
329 const int tail = arc_var.first.tail;
330 const int head = arc_var.first.head;
331 routes_ct->add_tails(
tail == 0 ? depot :
tail == depot ? 0 :
tail);
332 routes_ct->add_heads(
head == 0 ? depot :
head == depot ? 0 :
head);
333 routes_ct->add_literals(arc_var.second);
340 const RoutingDimension* master_dimension =
nullptr;
341 for (
const RoutingDimension* dimension :
model.GetDimensions()) {
343 if (dimension->GetUnaryTransitEvaluator(0) !=
nullptr) {
344 master_dimension = dimension;
348 if (master_dimension !=
nullptr) {
350 master_dimension->GetUnaryTransitEvaluator(0);
351 for (
int node = 0; node < num_nodes; ++node) {
354 if (!
model.IsEnd(node) && (!
model.IsStart(node) || node == depot)) {
355 routes_ct->add_demands(transit(node));
358 DCHECK_EQ(routes_ct->demands_size(), num_nodes + 1 -
model.vehicles());
359 routes_ct->set_capacity(master_dimension->vehicle_capacities()[0]);
367 ArcVarMap PopulateSingleRouteModelFromRoutingModel(
const RoutingModel&
model,
368 CpModelProto* cp_model) {
370 const int num_nodes =
model.Nexts().size();
371 CircuitConstraintProto* circuit =
372 cp_model->add_constraints()->mutable_circuit();
374 std::unique_ptr<IntVarIterator> iter(
375 model.NextVar(
tail)->MakeDomainIterator(
false));
376 for (
int head : InitAndGetValues(iter.get())) {
386 const int index = AddVariable(cp_model, 0, 1);
387 circuit->add_literals(
index);
388 circuit->add_tails(
tail);
389 circuit->add_heads(
head);
390 cp_model->mutable_objective()->add_vars(
index);
391 cp_model->mutable_objective()->add_coeffs(
cost);
395 AddPickupDeliveryConstraints(
model, arc_vars, cp_model);
396 AddDimensions(
model, arc_vars, cp_model);
403 ArcVarMap PopulateModelFromRoutingModel(
const RoutingModel&
model,
404 CpModelProto* cp_model) {
405 if (
model.vehicles() == 1) {
406 return PopulateSingleRouteModelFromRoutingModel(
model, cp_model);
408 return PopulateMultiRouteModelFromRoutingModel(
model, cp_model);
412 bool ConvertToSolution(
const CpSolverResponse&
response,
413 const RoutingModel&
model,
const ArcVarMap& arc_vars,
414 Assignment* solution) {
418 const int depot = GetDepotFromModel(
model);
420 for (
const auto& arc_var : arc_vars) {
421 if (
response.solution(arc_var.second) != 0) {
422 const int tail = arc_var.first.tail;
423 const int head = arc_var.first.head;
424 if (
head == depot)
continue;
428 solution->Add(
model.NextVar(
model.Start(vehicle)))->SetValue(
head);
434 for (
int v = 0; v <
model.vehicles(); ++v) {
435 int current =
model.Start(v);
436 while (solution->Contains(
model.NextVar(current))) {
437 current = solution->Value(
model.NextVar(current));
439 solution->Add(
model.NextVar(current))->SetValue(
model.End(v));
444 void AddSolutionAsHintToModel(
const Assignment* solution,
445 const RoutingModel&
model,
446 const ArcVarMap& arc_vars,
447 CpModelProto* cp_model) {
448 if (solution ==
nullptr)
return;
449 PartialVariableAssignment*
const hint = cp_model->mutable_solution_hint();
451 const int depot = GetDepotFromModel(
model);
452 const int num_nodes =
model.Nexts().size();
457 if (tail_index == depot && head_index == depot)
continue;
458 const int*
const var_index =
464 if (var_index ==
nullptr)
continue;
465 hint->add_vars(*var_index);
472 CpSolverResponse SolveRoutingModel(
473 const CpModelProto& cp_model, absl::Duration remaining_time,
474 const std::function<
void(
const CpSolverResponse&
response)>& observer) {
478 parameters.set_max_time_in_seconds(absl::ToDoubleSeconds(remaining_time));
482 if (observer !=
nullptr) {
496 const RoutingSearchParameters& search_parameters,
499 if (!sat::RoutingModelCanBeSolvedBySat(
model))
return false;
500 sat::CpModelProto cp_model;
501 cp_model.mutable_objective()->set_scaling_factor(
502 search_parameters.log_cost_scaling_factor());
503 cp_model.mutable_objective()->set_offset(search_parameters.log_cost_offset());
504 const sat::ArcVarMap arc_vars =
505 sat::PopulateModelFromRoutingModel(
model, &cp_model);
506 sat::AddSolutionAsHintToModel(initial_solution,
model, arc_vars, &cp_model);
507 return sat::ConvertToSolution(
508 sat::SolveRoutingModel(cp_model,
model.RemainingTime(),
nullptr),
model,