OR-Tools  8.1
routing_flow.cc
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
17 
18 namespace operations_research {
19 
20 namespace {
21 // Compute set of disjunctions involved in a pickup and delivery pair.
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);
29  }
30  }
31 }
32 } // namespace
33 
35  // TODO(user): Support overlapping disjunctions and disjunctions with
36  // a cardinality > 1.
37  absl::flat_hash_set<int> disjunction_nodes;
38  for (DisjunctionIndex i(0); i < GetNumberOfDisjunctions(); ++i) {
39  if (GetDisjunctionMaxCardinality(i) > 1) return false;
40  for (int64 node : GetDisjunctionIndices(i)) {
41  if (!disjunction_nodes.insert(node).second) return false;
42  }
43  }
44  for (const auto& pd_pairs : GetPickupAndDeliveryPairs()) {
45  absl::flat_hash_set<DisjunctionIndex> disjunctions;
46  AddDisjunctionsFromNodes(*this, pd_pairs.first, &disjunctions);
47  AddDisjunctionsFromNodes(*this, pd_pairs.second, &disjunctions);
48  // Pairs involving more than 2 disjunctions are not supported.
49  if (disjunctions.size() > 2) return false;
50  }
51  // Detect if a "unary" dimension prevents from having more than a single
52  // non-start/end node (or a single pickup and delivery pair) on a route.
53  // Binary dimensions are not considered because they would result in a
54  // quadratic check.
55  for (const RoutingDimension* const dimension : dimensions_) {
56  // TODO(user): Support vehicle-dependent dimension callbacks.
57  if (dimension->class_evaluators_.size() != 1) {
58  continue;
59  }
60  const TransitCallback1& transit =
61  UnaryTransitCallbackOrNull(dimension->class_evaluators_[0]);
62  if (transit == nullptr) {
63  continue;
64  }
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);
68  }
69  std::vector<int64> transits(nexts_.size(), kint64max);
70  for (int i = 0; i < nexts_.size(); ++i) {
71  if (!IsStart(i) && !IsEnd(i)) {
72  transits[i] = std::min(transits[i], transit(i));
73  }
74  }
75  int64 min_transit = kint64max;
76  // Find the minimal accumulated value resulting from a pickup and delivery
77  // pair.
78  for (const auto& pd_pairs : GetPickupAndDeliveryPairs()) {
79  const auto transit_cmp = [&transits](int i, int j) {
80  return transits[i] < transits[j];
81  };
82  min_transit = std::min(
83  min_transit,
84  // Min transit from pickup.
85  transits[*std::min_element(pd_pairs.first.begin(),
86  pd_pairs.first.end(), transit_cmp)] +
87  // Min transit from delivery.
88  transits[*std::min_element(pd_pairs.second.begin(),
89  pd_pairs.second.end(), transit_cmp)]);
90  }
91  // Find the minimal accumulated value resulting from a non-pickup/delivery
92  // node.
93  for (int i = 0; i < transits.size(); ++i) {
94  if (GetPickupIndexPairs(i).empty() && GetDeliveryIndexPairs(i).empty()) {
95  min_transit = std::min(min_transit, transits[i]);
96  }
97  }
98  // If there cannot be more than one node or pickup and delivery, a matching
99  // problem has been detected.
100  if (CapProd(min_transit, 2) > max_vehicle_capacity) return true;
101  }
102  return false;
103 }
104 
105 // Solve matching model using a min-cost flow. Here is the underlyihg flow:
106 //
107 // ---------- Source -------------
108 // | (1,0) | (N,0)
109 // V V
110 // (vehicles) unperformed
111 // | (1,cost) |
112 // V |
113 // (nodes/pickup/deliveries) | (1,penalty)
114 // | (1,0) |
115 // V |
116 // disjunction <---------
117 // | (1, 0)
118 // V
119 // Sink
120 //
121 // On arcs, (,) represents (capacity, cost).
122 // N: number of disjunctions
123 //
124 
125 namespace {
126 struct FlowArc {
131 };
132 } // namespace
133 
134 bool RoutingModel::SolveMatchingModel(
135  Assignment* assignment, const RoutingSearchParameters& parameters) {
136  VLOG(2) << "Solving with flow";
137  assignment->Clear();
138 
139  // Collect dimensions with costs.
140  // TODO(user): If the costs are soft cumul upper (resp. lower) bounds only,
141  // do not use the LP model.
142  const std::vector<RoutingDimension*> dimensions =
144  std::vector<LocalDimensionCumulOptimizer> optimizers;
145  optimizers.reserve(dimensions.size());
146  for (RoutingDimension* dimension : dimensions) {
147  optimizers.emplace_back(dimension,
148  parameters.continuous_scheduling_solver());
149  }
150 
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);
155  // Create pickup and delivery pair flow nodes.
156  // TODO(user): Check pair alternatives correspond exactly to at most two
157  // disjunctions.
158  absl::flat_hash_map<int, std::pair<int64, int64>> flow_to_pd;
159  for (const auto& pd_pairs : GetPickupAndDeliveryPairs()) {
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);
170  num_flow_nodes++;
171  }
172  }
173  DCHECK_LE(disjunctions.size(), 2);
174  int64 penalty = 0;
175  if (disjunctions.size() < 2) {
176  penalty = kNoPenalty;
177  } else {
178  for (DisjunctionIndex index : disjunctions) {
179  const int64 d_penalty = GetDisjunctionPenalty(index);
180  if (d_penalty == kNoPenalty) {
181  penalty = kNoPenalty;
182  break;
183  }
184  penalty = CapAdd(penalty, d_penalty);
185  }
186  }
187  disjunction_penalties.push_back(penalty);
188  }
189  // Create non-pickup and delivery flow nodes.
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 =
194  GetDisjunctionIndices(node);
195  DCHECK_LE(disjunctions.size(), 1);
196  disjunction_to_flow_nodes.push_back({});
197  disjunction_penalties.push_back(
198  disjunctions.empty() ? kNoPenalty
199  : GetDisjunctionPenalty(disjunctions.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);
204  num_flow_nodes++;
205  } else {
206  for (int n : GetDisjunctionIndices(disjunctions.back())) {
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);
210  num_flow_nodes++;
211  }
212  }
213  }
214 
215  std::vector<FlowArc> arcs;
216 
217  // Build a flow node for each disjunction and corresponding arcs.
218  // Each node exits to the sink through a node, for which the outgoing
219  // capacity is one (only one of the nodes in the disjunction is performed).
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;
225  } else {
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});
229  }
230  num_flow_nodes++;
231  }
232  }
233 
234  // Build arcs from each vehicle to each non-vehicle flow node; the cost of
235  // each arc corresponds to:
236  // start(vehicle) -> pickup -> delivery -> end(vehicle)
237  // or
238  // start(vehicle) -> node -> end(vehicle)
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) {
242  const int64 start = Start(vehicle);
243  const int64 end = End(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;
247  int64 node = -1;
248  int64 cost = 0;
249  bool add_arc = false;
250  if (gtl::FindCopy(flow_to_pd, flow_node, &pd_pair)) {
251  const int64 pickup = pd_pair.first;
252  const int64 delivery = pd_pair.second;
253  if (IsVehicleAllowedForIndex(vehicle, pickup) &&
254  IsVehicleAllowedForIndex(vehicle, delivery)) {
255  add_arc = true;
256  cost =
257  CapAdd(GetArcCostForVehicle(start, pickup, vehicle),
258  CapAdd(GetArcCostForVehicle(pickup, delivery, vehicle),
259  GetArcCostForVehicle(delivery, end, vehicle)));
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;
264  // TODO(user): if the result is RELAXED_OPTIMAL_ONLY, do a
265  // second pass with an MP solver.
266  if (optimizer.ComputeRouteCumulCostWithoutFixedTransits(
267  vehicle,
268  [&nexts](int64 node) { return nexts.find(node)->second; },
269  &cumul_cost_value) !=
271  cost = CapAdd(cost, cumul_cost_value);
272  } else {
273  add_arc = false;
274  break;
275  }
276  }
277  }
278  } else if (gtl::FindCopy(flow_to_non_pd, flow_node, &node)) {
279  if (IsVehicleAllowedForIndex(vehicle, node)) {
280  add_arc = true;
281  cost = CapAdd(GetArcCostForVehicle(start, node, vehicle),
282  GetArcCostForVehicle(node, end, vehicle));
283  const absl::flat_hash_map<int64, int64> nexts = {{start, node},
284  {node, end}};
285  for (LocalDimensionCumulOptimizer& optimizer : optimizers) {
286  int64 cumul_cost_value = 0;
287  // TODO(user): if the result is RELAXED_OPTIMAL_ONLY, do a
288  // second pass with an MP solver.
289  if (optimizer.ComputeRouteCumulCostWithoutFixedTransits(
290  vehicle,
291  [&nexts](int64 node) { return nexts.find(node)->second; },
292  &cumul_cost_value) !=
294  cost = CapAdd(cost, cumul_cost_value);
295  } else {
296  add_arc = false;
297  break;
298  }
299  }
300  }
301  } else {
302  DCHECK(false);
303  }
304  if (add_arc) {
305  arcs.push_back({num_flow_nodes, flow_node, 1, cost});
306  }
307  }
308  }
309  flow_to_vehicle[num_flow_nodes] = vehicle;
310  vehicle_to_flow.push_back(num_flow_nodes);
311  num_flow_nodes++;
312  }
313  // Create flow source and sink nodes.
314  const int source = num_flow_nodes + 1;
315  const int sink = source + 1;
316  // Source connected to vehicle nodes.
317  for (int vehicle = 0; vehicle < vehicles(); ++vehicle) {
318  arcs.push_back({source, vehicle_to_flow[vehicle], 1, 0});
319  }
320  // Handle unperformed nodes.
321  // Create a node to catch unperformed nodes and connect it to source.
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];
329  if (penalty != kNoPenalty) {
330  arcs.push_back({unperformed, flow_node, 1, penalty});
331  }
332  // Connect non-vehicle flow nodes to sinks.
333  arcs.push_back({flow_node, sink, 1, 0});
334  }
335 
336  // Rescale costs for min-cost flow; assuming max cost resulting from the
337  // push-relabel flow algorithm is max_arc_cost * (num_nodes+1) * (num_nodes+1)
338  // (cost-scaling multiplies arc costs by num_nodes+1 and the flow itself can
339  // accumulate num_nodes+1 such arcs (with capacity being 1 for costed arcs)).
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; });
344  // SimpleMinCostFlow adds a source and a sink node, so actual number of
345  // nodes to consider is num_flow_nodes + 3.
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);
351  }
352 
353  SimpleMinCostFlow flow;
354  // Add arcs to flow.
355  for (const FlowArc& arc : arcs) {
356  flow.AddArcWithCapacityAndUnitCost(arc.tail, arc.head, arc.capacity,
357  arc.cost / scale_factor);
358  }
359 
360  // Set flow supply (number of non-vehicle nodes or pairs).
361  flow.SetNodeSupply(source, flow_supply);
362  flow.SetNodeSupply(sink, -flow_supply);
363 
364  // TODO(user): Take time limit into account.
365  if (flow.Solve() != SimpleMinCostFlow::OPTIMAL) {
366  return false;
367  }
368 
369  // Map the flow result to assignment, only setting next variables.
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;
376  int node = -1;
377  int index = -1;
378  if (gtl::FindCopy(flow_to_pd, flow.Head(i), &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);
383  } else if (gtl::FindCopy(flow_to_disjunction, flow.Head(i), &index)) {
384  for (int64 flow_node : disjunction_to_flow_nodes[index]) {
385  if (gtl::FindCopy(flow_to_pd, flow_node, &pd_pair)) {
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);
390  }
391  }
392  }
393  int vehicle = -1;
394  if (flow.Tail(i) == unperformed) {
395  // Head is unperformed.
396  for (int node : nodes) {
397  assignment->Add(NextVar(node))->SetValue(node);
398  used_nodes.insert(node);
399  }
400  } else if (gtl::FindCopy(flow_to_vehicle, flow.Tail(i), &vehicle)) {
401  // Head is performed on a 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);
407  current = node;
408  }
409  assignment->Add(NextVar(current))->SetValue(End(vehicle));
410  }
411  }
412  }
413  // Adding unused nodes.
414  for (int node = 0; node < Size(); ++node) {
415  if (!IsStart(node) && used_nodes.count(node) == 0) {
416  assignment->Add(NextVar(node))->SetValue(node);
417  }
418  }
419  // Adding unused vehicles.
420  for (int vehicle = 0; vehicle < vehicles(); ++vehicle) {
421  if (!used_vehicles[vehicle]) {
422  assignment->Add(NextVar(Start(vehicle)))->SetValue(End(vehicle));
423  }
424  }
425  return true;
426 }
427 
428 } // namespace operations_research
operations_research::RoutingModel::GetDimensionsWithSoftOrSpanCosts
std::vector< RoutingDimension * > GetDimensionsWithSoftOrSpanCosts() const
Returns dimensions with soft or vehicle span costs.
Definition: routing.cc:4978
operations_research::RoutingModel::TransitCallback1
RoutingTransitCallback1 TransitCallback1
Definition: routing.h:241
tail
int64 tail
Definition: routing_flow.cc:127
operations_research::RoutingModel::vehicles
int vehicles() const
Returns the number of vehicle routes in the model.
Definition: routing.h:1333
min
int64 min
Definition: alldiff_cst.cc:138
VLOG
#define VLOG(verboselevel)
Definition: base/logging.h:978
max
int64 max
Definition: alldiff_cst.cc:139
operations_research::CapProd
int64 CapProd(int64 x, int64 y)
Definition: saturated_arithmetic.h:231
routing.h
operations_research::RoutingModel::GetNumberOfDisjunctions
int GetNumberOfDisjunctions() const
Returns the number of node disjunctions in the model.
Definition: routing.h:655
operations_research::RoutingModel::RoutingDimension
friend class RoutingDimension
Definition: routing.h:1924
operations_research::RoutingModel::IsStart
bool IsStart(int64 index) const
Returns true if 'index' represents the first node of a route.
Definition: routing.cc:3882
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::RoutingModel::IsVehicleAllowedForIndex
bool IsVehicleAllowedForIndex(int vehicle, int64 index)
Returns true if a vehicle is allowed to visit a given node.
Definition: routing.h:682
int64
int64_t int64
Definition: integral_types.h:34
index
int index
Definition: pack.cc:508
operations_research::MinCostFlowBase::OPTIMAL
@ OPTIMAL
Definition: min_cost_flow.h:196
operations_research::RoutingModel::Size
int64 Size() const
Returns the number of next variables in the model.
Definition: routing.h:1335
cost
int64 cost
Definition: routing_flow.cc:130
a
int64 a
Definition: constraint_solver/table.cc:42
routing_lp_scheduling.h
min_cost_flow.h
operations_research::RoutingModel::DisjunctionIndex
RoutingDisjunctionIndex DisjunctionIndex
Definition: routing.h:239
operations_research::DimensionSchedulingStatus::INFEASIBLE
@ INFEASIBLE
operations_research::CapAdd
int64 CapAdd(int64 x, int64 y)
Definition: saturated_arithmetic.h:124
operations_research::RoutingModel::UnaryTransitCallbackOrNull
const TransitCallback1 & UnaryTransitCallbackOrNull(int callback_index) const
Definition: routing.h:411
operations_research::RoutingModel::GetDisjunctionPenalty
int64 GetDisjunctionPenalty(DisjunctionIndex index) const
Returns the penalty of the node disjunction of index 'index'.
Definition: routing.h:646
operations_research::RoutingModel::GetPickupIndexPairs
const std::vector< std::pair< int, int > > & GetPickupIndexPairs(int64 node_index) const
Returns pairs for which the node is a pickup; the first element of each pair is the index in the pick...
Definition: routing.cc:1693
operations_research::RoutingModel::IsEnd
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
Definition: routing.h:1174
operations_research::RoutingModel::NextVar
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
Definition: routing.h:1195
DCHECK
#define DCHECK(condition)
Definition: base/logging.h:884
operations_research::RoutingModel::GetDisjunctionIndices
const std::vector< DisjunctionIndex > & GetDisjunctionIndices(int64 index) const
Returns the indices of the disjunctions to which an index belongs.
Definition: routing.h:619
operations_research::RoutingModel::IsMatchingModel
bool IsMatchingModel() const
Returns true if a vehicle/node matching problem is detected.
Definition: routing_flow.cc:34
operations_research::RoutingModel::GetDeliveryIndexPairs
const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs(int64 node_index) const
Same as above for deliveries.
Definition: routing.cc:1699
operations_research::RoutingModel::GetDisjunctionMaxCardinality
int64 GetDisjunctionMaxCardinality(DisjunctionIndex index) const
Returns the maximum number of possible active nodes of the node disjunction of index 'index'.
Definition: routing.h:651
model
GRBmodel * model
Definition: gurobi_interface.cc:269
operations_research::RoutingModel::End
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
Definition: routing.h:1170
operations_research::RoutingModel::Start
int64 Start(int vehicle) const
Model inspection.
Definition: routing.h:1168
b
int64 b
Definition: constraint_solver/table.cc:43
operations_research::RoutingModel::GetPickupAndDeliveryPairs
const IndexPairs & GetPickupAndDeliveryPairs() const
Returns pickup and delivery pairs currently in the model.
Definition: routing.h:734
operations_research::RoutingDimension
Dimensions represent quantities accumulated at nodes along the routes.
Definition: routing.h:2356
capacity
int64 capacity
Definition: routing_flow.cc:129
head
int64 head
Definition: routing_flow.cc:128
DCHECK_LE
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
gtl::FindCopy
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
Definition: map_util.h:155
parameters
SatParameters parameters
Definition: cp_model_fz_solver.cc:108
operations_research::RoutingModel::kNoPenalty
static const int64 kNoPenalty
Constant used to express a hard constraint instead of a soft penalty.
Definition: routing.h:383
operations_research::RoutingModel::GetArcCostForVehicle
int64 GetArcCostForVehicle(int64 from_index, int64 to_index, int64 vehicle) const
Returns the cost of the transit arc between two nodes for a given vehicle.
Definition: routing.cc:3904
operations_research::RoutingModel::nodes
int nodes() const
Sizes and indices Returns the number of nodes in the model.
Definition: routing.h:1331
kint64max
static const int64 kint64max
Definition: integral_types.h:62