22 template <
typename Disjunctions>
23 void AddDisjunctionsFromNodes(
const RoutingModel&
model,
24 const std::vector<int64>& nodes,
25 Disjunctions* disjunctions) {
26 for (
int64 node : nodes) {
27 for (
const auto disjunction :
model.GetDisjunctionIndices(node)) {
28 disjunctions->insert(disjunction);
37 absl::flat_hash_set<int> disjunction_nodes;
41 if (!disjunction_nodes.insert(node).second)
return false;
45 absl::flat_hash_set<DisjunctionIndex> disjunctions;
46 AddDisjunctionsFromNodes(*
this, pd_pairs.first, &disjunctions);
47 AddDisjunctionsFromNodes(*
this, pd_pairs.second, &disjunctions);
49 if (disjunctions.size() > 2)
return false;
57 if (dimension->class_evaluators_.size() != 1) {
62 if (transit ==
nullptr) {
65 int64 max_vehicle_capacity = 0;
66 for (
int64 vehicle_capacity : dimension->vehicle_capacities()) {
67 max_vehicle_capacity =
std::max(max_vehicle_capacity, vehicle_capacity);
69 std::vector<int64> transits(nexts_.size(),
kint64max);
70 for (
int i = 0; i < nexts_.size(); ++i) {
72 transits[i] =
std::min(transits[i], transit(i));
79 const auto transit_cmp = [&transits](
int i,
int j) {
80 return transits[i] < transits[j];
85 transits[*std::min_element(pd_pairs.first.begin(),
86 pd_pairs.first.end(), transit_cmp)] +
88 transits[*std::min_element(pd_pairs.second.begin(),
89 pd_pairs.second.end(), transit_cmp)]);
93 for (
int i = 0; i < transits.size(); ++i) {
95 min_transit =
std::min(min_transit, transits[i]);
100 if (
CapProd(min_transit, 2) > max_vehicle_capacity)
return true;
134 bool RoutingModel::SolveMatchingModel(
135 Assignment* assignment,
const RoutingSearchParameters&
parameters) {
136 VLOG(2) <<
"Solving with flow";
142 const std::vector<RoutingDimension*> dimensions =
144 std::vector<LocalDimensionCumulOptimizer> optimizers;
145 optimizers.reserve(dimensions.size());
147 optimizers.emplace_back(dimension,
151 int num_flow_nodes = 0;
152 std::vector<std::vector<int64>> disjunction_to_flow_nodes;
153 std::vector<int64> disjunction_penalties;
154 std::vector<bool> in_disjunction(
Size(),
false);
158 absl::flat_hash_map<int, std::pair<int64, int64>> flow_to_pd;
160 disjunction_to_flow_nodes.push_back({});
161 absl::flat_hash_set<DisjunctionIndex> disjunctions;
162 AddDisjunctionsFromNodes(*
this, pd_pairs.first, &disjunctions);
163 AddDisjunctionsFromNodes(*
this, pd_pairs.second, &disjunctions);
164 for (
int64 pickup : pd_pairs.first) {
165 in_disjunction[pickup] =
true;
166 for (
int64 delivery : pd_pairs.second) {
167 in_disjunction[delivery] =
true;
168 flow_to_pd[num_flow_nodes] = {pickup, delivery};
169 disjunction_to_flow_nodes.back().push_back(num_flow_nodes);
175 if (disjunctions.size() < 2) {
184 penalty =
CapAdd(penalty, d_penalty);
187 disjunction_penalties.push_back(penalty);
190 absl::flat_hash_map<int, int64> flow_to_non_pd;
191 for (
int node = 0; node <
Size(); ++node) {
192 if (
IsStart(node) || in_disjunction[node])
continue;
193 const std::vector<DisjunctionIndex>& disjunctions =
196 disjunction_to_flow_nodes.push_back({});
197 disjunction_penalties.push_back(
200 if (disjunctions.empty()) {
201 in_disjunction[node] =
true;
202 flow_to_non_pd[num_flow_nodes] = node;
203 disjunction_to_flow_nodes.back().push_back(num_flow_nodes);
207 in_disjunction[n] =
true;
208 flow_to_non_pd[num_flow_nodes] = n;
209 disjunction_to_flow_nodes.back().push_back(num_flow_nodes);
215 std::vector<FlowArc> arcs;
220 absl::flat_hash_map<int, int> flow_to_disjunction;
221 for (
int i = 0; i < disjunction_to_flow_nodes.size(); ++i) {
222 const std::vector<int64>& flow_nodes = disjunction_to_flow_nodes[i];
223 if (flow_nodes.size() == 1) {
224 flow_to_disjunction[flow_nodes.back()] = i;
226 flow_to_disjunction[num_flow_nodes] = i;
227 for (
int64 flow_node : flow_nodes) {
228 arcs.push_back({flow_node, num_flow_nodes, 1, 0});
239 std::vector<int> vehicle_to_flow;
240 absl::flat_hash_map<int, int> flow_to_vehicle;
241 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
244 for (
const std::vector<int64>& flow_nodes : disjunction_to_flow_nodes) {
245 for (
int64 flow_node : flow_nodes) {
246 std::pair<int64, int64> pd_pair;
249 bool add_arc =
false;
251 const int64 pickup = pd_pair.first;
252 const int64 delivery = pd_pair.second;
260 const absl::flat_hash_map<int64, int64> nexts = {
261 {start, pickup}, {pickup, delivery}, {delivery, end}};
262 for (LocalDimensionCumulOptimizer& optimizer : optimizers) {
263 int64 cumul_cost_value = 0;
266 if (optimizer.ComputeRouteCumulCostWithoutFixedTransits(
268 [&nexts](
int64 node) { return nexts.find(node)->second; },
269 &cumul_cost_value) !=
278 }
else if (
gtl::FindCopy(flow_to_non_pd, flow_node, &node)) {
283 const absl::flat_hash_map<int64, int64> nexts = {{start, node},
285 for (LocalDimensionCumulOptimizer& optimizer : optimizers) {
286 int64 cumul_cost_value = 0;
289 if (optimizer.ComputeRouteCumulCostWithoutFixedTransits(
291 [&nexts](
int64 node) { return nexts.find(node)->second; },
292 &cumul_cost_value) !=
305 arcs.push_back({num_flow_nodes, flow_node, 1,
cost});
309 flow_to_vehicle[num_flow_nodes] = vehicle;
310 vehicle_to_flow.push_back(num_flow_nodes);
314 const int source = num_flow_nodes + 1;
315 const int sink = source + 1;
317 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
318 arcs.push_back({source, vehicle_to_flow[vehicle], 1, 0});
322 const int unperformed = num_flow_nodes;
323 const int64 flow_supply = disjunction_to_flow_nodes.size();
324 arcs.push_back({source, unperformed, flow_supply, 0});
325 for (
const auto& flow_disjunction_element : flow_to_disjunction) {
326 const int flow_node = flow_disjunction_element.first;
327 const int64 penalty =
328 disjunction_penalties[flow_disjunction_element.second];
330 arcs.push_back({unperformed, flow_node, 1, penalty});
333 arcs.push_back({flow_node, sink, 1, 0});
340 int64 scale_factor = 1;
341 const FlowArc& arc_with_max_cost = *std::max_element(
342 arcs.begin(), arcs.end(),
343 [](
const FlowArc&
a,
const FlowArc&
b) { return a.cost < b.cost; });
346 const int actual_flow_num_nodes = num_flow_nodes + 3;
347 if (log(
static_cast<double>(arc_with_max_cost.cost) + 1) +
348 2 * log(actual_flow_num_nodes) >
350 scale_factor =
CapProd(actual_flow_num_nodes, actual_flow_num_nodes);
353 SimpleMinCostFlow flow;
355 for (
const FlowArc& arc : arcs) {
356 flow.AddArcWithCapacityAndUnitCost(arc.tail, arc.head, arc.capacity,
357 arc.cost / scale_factor);
361 flow.SetNodeSupply(source, flow_supply);
362 flow.SetNodeSupply(sink, -flow_supply);
370 std::vector<bool> used_vehicles(
vehicles(),
false);
371 absl::flat_hash_set<int> used_nodes;
372 for (
int i = 0; i < flow.NumArcs(); ++i) {
373 if (flow.Flow(i) > 0 && flow.Tail(i) != source && flow.Head(i) != sink) {
374 std::vector<int>
nodes;
375 std::pair<int64, int64> pd_pair;
379 nodes.push_back(pd_pair.first);
380 nodes.push_back(pd_pair.second);
381 }
else if (
gtl::FindCopy(flow_to_non_pd, flow.Head(i), &node)) {
382 nodes.push_back(node);
384 for (
int64 flow_node : disjunction_to_flow_nodes[
index]) {
386 nodes.push_back(pd_pair.first);
387 nodes.push_back(pd_pair.second);
388 }
else if (
gtl::FindCopy(flow_to_non_pd, flow_node, &node)) {
389 nodes.push_back(node);
394 if (flow.Tail(i) == unperformed) {
396 for (
int node :
nodes) {
397 assignment->Add(
NextVar(node))->SetValue(node);
398 used_nodes.insert(node);
400 }
else if (
gtl::FindCopy(flow_to_vehicle, flow.Tail(i), &vehicle)) {
402 used_vehicles[vehicle] =
true;
403 int current =
Start(vehicle);
404 for (
int node :
nodes) {
405 assignment->Add(
NextVar(current))->SetValue(node);
406 used_nodes.insert(node);
409 assignment->Add(
NextVar(current))->SetValue(
End(vehicle));
414 for (
int node = 0; node <
Size(); ++node) {
415 if (!
IsStart(node) && used_nodes.count(node) == 0) {
416 assignment->Add(
NextVar(node))->SetValue(node);
420 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
421 if (!used_vehicles[vehicle]) {