26 return model.GetVehicleClassesCount() == 1;
30int 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);
62using ArcVarMap = std::map<Arc, int>;
66void 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]);
108std::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]);
142std::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]);
181void 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]);
222ArcVarMap 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;
265 if (depot_node_var ==
nullptr)
continue;
266 ct->add_vars(*depot_node_var);
269 if (node_depot_var ==
nullptr)
continue;
270 ct->add_vars(*node_depot_var);
276 LinearConstraintProto*
ct = cp_model->add_constraints()->mutable_linear();
281 for (
int node = 0; node < num_nodes; ++node) {
282 if (
model.IsStart(node) ||
model.IsEnd(node))
continue;
284 if (
var ==
nullptr)
continue;
292 LinearConstraintProto*
ct = cp_model->add_constraints()->mutable_linear();
295 std::unique_ptr<IntVarIterator> iter(
296 model.NextVar(
tail)->MakeDomainIterator(
false));
297 bool depot_added =
false;
298 for (
int head : InitAndGetValues(iter.get())) {
302 if (depot_added)
continue;
307 if (
var ==
nullptr)
continue;
315 LinearConstraintProto*
ct = cp_model->add_constraints()->mutable_linear();
323 if (
var ==
nullptr)
continue;
329 AddPickupDeliveryConstraints(
model, arc_vars, cp_model);
331 AddDimensions(
model, arc_vars, cp_model);
336 RoutesConstraintProto* routes_ct =
337 cp_model->add_constraints()->mutable_routes();
338 for (
const auto arc_var : arc_vars) {
339 const int tail = arc_var.first.tail;
340 const int head = arc_var.first.head;
341 routes_ct->add_tails(
tail == 0 ? depot :
tail == depot ? 0 :
tail);
342 routes_ct->add_heads(
head == 0 ? depot :
head == depot ? 0 :
head);
343 routes_ct->add_literals(arc_var.second);
350 const RoutingDimension* master_dimension =
nullptr;
351 for (
const RoutingDimension* dimension :
model.GetDimensions()) {
353 if (dimension->GetUnaryTransitEvaluator(0) !=
nullptr) {
354 master_dimension = dimension;
358 if (master_dimension !=
nullptr) {
360 master_dimension->GetUnaryTransitEvaluator(0);
361 for (
int node = 0; node < num_nodes; ++node) {
364 if (!
model.IsEnd(node) && (!
model.IsStart(node) || node == depot)) {
365 routes_ct->add_demands(transit(node));
368 DCHECK_EQ(routes_ct->demands_size(), num_nodes + 1 -
model.vehicles());
369 routes_ct->set_capacity(master_dimension->vehicle_capacities()[0]);
377ArcVarMap PopulateSingleRouteModelFromRoutingModel(
const RoutingModel&
model,
378 CpModelProto* cp_model) {
380 const int num_nodes =
model.Nexts().size();
381 CircuitConstraintProto* circuit =
382 cp_model->add_constraints()->mutable_circuit();
384 std::unique_ptr<IntVarIterator> iter(
385 model.NextVar(
tail)->MakeDomainIterator(
false));
386 for (
int head : InitAndGetValues(iter.get())) {
396 const int index = AddVariable(cp_model, 0, 1);
397 circuit->add_literals(
index);
398 circuit->add_tails(
tail);
399 circuit->add_heads(
head);
400 cp_model->mutable_objective()->add_vars(
index);
401 cp_model->mutable_objective()->add_coeffs(
cost);
405 AddPickupDeliveryConstraints(
model, arc_vars, cp_model);
406 AddDimensions(
model, arc_vars, cp_model);
413ArcVarMap PopulateModelFromRoutingModel(
const RoutingModel&
model,
414 CpModelProto* cp_model) {
415 if (
model.vehicles() == 1) {
416 return PopulateSingleRouteModelFromRoutingModel(
model, cp_model);
418 return PopulateMultiRouteModelFromRoutingModel(
model, cp_model);
422bool ConvertToSolution(
const CpSolverResponse&
response,
423 const RoutingModel&
model,
const ArcVarMap& arc_vars,
424 Assignment* solution) {
425 if (
response.status() != CpSolverStatus::OPTIMAL &&
426 response.status() != CpSolverStatus::FEASIBLE)
428 const int depot = GetDepotFromModel(
model);
430 for (
const auto& arc_var : arc_vars) {
431 if (
response.solution(arc_var.second) != 0) {
432 const int tail = arc_var.first.tail;
433 const int head = arc_var.first.head;
434 if (
head == depot)
continue;
438 solution->Add(
model.NextVar(
model.Start(vehicle)))->SetValue(
head);
444 for (
int v = 0; v <
model.vehicles(); ++v) {
445 int current =
model.Start(v);
446 while (solution->Contains(
model.NextVar(current))) {
447 current = solution->Value(
model.NextVar(current));
449 solution->Add(
model.NextVar(current))->SetValue(
model.End(v));
454void AddSolutionAsHintToModel(
const Assignment* solution,
455 const RoutingModel&
model,
456 const ArcVarMap& arc_vars,
457 CpModelProto* cp_model) {
458 if (solution ==
nullptr)
return;
459 PartialVariableAssignment*
const hint = cp_model->mutable_solution_hint();
461 const int depot = GetDepotFromModel(
model);
462 const int num_nodes =
model.Nexts().size();
467 if (tail_index == depot && head_index == depot)
continue;
468 const int*
const var_index =
474 if (var_index ==
nullptr)
continue;
475 hint->add_vars(*var_index);
482CpSolverResponse SolveRoutingModel(
483 const CpModelProto& cp_model, absl::Duration remaining_time,
484 const std::function<
void(
const CpSolverResponse&
response)>& observer) {
488 parameters.set_max_time_in_seconds(absl::ToDoubleSeconds(remaining_time));
492 if (observer !=
nullptr) {
506 const RoutingSearchParameters& search_parameters,
509 if (!sat::RoutingModelCanBeSolvedBySat(
model))
return false;
510 sat::CpModelProto cp_model;
511 cp_model.mutable_objective()->set_scaling_factor(
512 search_parameters.log_cost_scaling_factor());
513 cp_model.mutable_objective()->set_offset(search_parameters.log_cost_offset());
514 const sat::ArcVarMap arc_vars =
515 sat::PopulateModelFromRoutingModel(
model, &cp_model);
516 sat::AddSolutionAsHintToModel(initial_solution,
model, arc_vars, &cp_model);
517 return sat::ConvertToSolution(
518 sat::SolveRoutingModel(cp_model,
model.RemainingTime(),
nullptr),
model,
#define DCHECK_EQ(val1, val2)
An Assignment is a variable -> domains mapping, used to report solutions to the user.
RoutingTransitCallback1 TransitCallback1
RoutingTransitCallback2 TransitCallback2
This file implements a wrapper around the CP-SAT model proto.
SharedResponseManager * response
static const int64 kint64max
bool operator!=(const STLCountingAllocator< T, A > &a, const STLCountingAllocator< T, A > &b)
bool ContainsKey(const Collection &collection, const Key &key)
void InsertOrDie(Collection *const collection, const typename Collection::value_type &value)
const Collection::value_type::second_type * FindOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
std::function< void(Model *)> NewFeasibleSolutionObserver(const std::function< void(const CpSolverResponse &response)> &observer)
Creates a solution observer with the model with model.Add(NewFeasibleSolutionObserver([](response){....
std::ostream & operator<<(std::ostream &os, const BoolVar &var)
std::function< SatParameters(Model *)> NewSatParameters(const std::string ¶ms)
Creates parameters for the solver, which you can add to the model with.
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
CpSolverResponse SolveCpModel(const CpModelProto &model_proto, Model *model)
Solves the given CpModelProto.
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool SolveModelWithSat(const RoutingModel &model, const RoutingSearchParameters &search_parameters, const Assignment *initial_solution, Assignment *solution)
Attempts to solve the model using the cp-sat solver.
int64 CapAdd(int64 x, int64 y)
int64 CapSub(int64 x, int64 y)
std::pair< int64, int64 > Arc
LinearRange operator==(const LinearExpr &lhs, const LinearExpr &rhs)