OR-Tools  8.2
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
18namespace operations_research {
19
20namespace {
21// Compute set of disjunctions involved in a pickup and delivery pair.
22template <typename Disjunctions>
23void 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
125namespace {
126struct FlowArc {
131};
132} // namespace
133
134bool 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 =
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
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK(condition)
Definition: base/logging.h:884
#define VLOG(verboselevel)
Definition: base/logging.h:978
Dimensions represent quantities accumulated at nodes along the routes.
Definition: routing.h:2368
int nodes() const
Sizes and indices Returns the number of nodes in the model.
Definition: routing.h:1343
int64 GetDisjunctionMaxCardinality(DisjunctionIndex index) const
Returns the maximum number of possible active nodes of the node disjunction of index 'index'.
Definition: routing.h:663
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
Definition: routing.h:1182
RoutingTransitCallback1 TransitCallback1
Definition: routing.h:242
const IndexPairs & GetPickupAndDeliveryPairs() const
Returns pickup and delivery pairs currently in the model.
Definition: routing.h:746
int64 GetDisjunctionPenalty(DisjunctionIndex index) const
Returns the penalty of the node disjunction of index 'index'.
Definition: routing.h:658
int64 Size() const
Returns the number of next variables in the model.
Definition: routing.h:1347
bool IsVehicleAllowedForIndex(int vehicle, int64 index)
Returns true if a vehicle is allowed to visit a given node.
Definition: routing.h:694
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
Definition: routing.h:1207
const std::vector< DisjunctionIndex > & GetDisjunctionIndices(int64 index) const
Returns the indices of the disjunctions to which an index belongs.
Definition: routing.h:631
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:3918
std::vector< RoutingDimension * > GetDimensionsWithSoftOrSpanCosts() const
Returns dimensions with soft or vehicle span costs.
Definition: routing.cc:4996
const TransitCallback1 & UnaryTransitCallbackOrNull(int callback_index) const
Definition: routing.h:417
static const int64 kNoPenalty
Constant used to express a hard constraint instead of a soft penalty.
Definition: routing.h:384
int vehicles() const
Returns the number of vehicle routes in the model.
Definition: routing.h:1345
int GetNumberOfDisjunctions() const
Returns the number of node disjunctions in the model.
Definition: routing.h:667
bool IsMatchingModel() const
Returns true if a vehicle/node matching problem is detected.
Definition: routing_flow.cc:34
int64 Start(int vehicle) const
Model inspection.
Definition: routing.h:1180
bool IsStart(int64 index) const
Returns true if 'index' represents the first node of a route.
Definition: routing.cc:3896
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
Definition: routing.h:1186
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:1707
RoutingDisjunctionIndex DisjunctionIndex
Definition: routing.h:240
const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs(int64 node_index) const
Same as above for deliveries.
Definition: routing.cc:1713
SatParameters parameters
GRBmodel * model
static const int64 kint64max
int64_t int64
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
Definition: map_util.h:155
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapAdd(int64 x, int64 y)
int64 CapProd(int64 x, int64 y)
int index
Definition: pack.cc:508
int64 tail
int64 cost
int64 head
int64 capacity