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]) {
#define DCHECK_LE(val1, val2)
#define DCHECK(condition)
#define VLOG(verboselevel)
Dimensions represent quantities accumulated at nodes along the routes.
int nodes() const
Sizes and indices Returns the number of nodes in the model.
int64 GetDisjunctionMaxCardinality(DisjunctionIndex index) const
Returns the maximum number of possible active nodes of the node disjunction of index 'index'.
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
RoutingTransitCallback1 TransitCallback1
int64 GetDisjunctionPenalty(DisjunctionIndex index) const
Returns the penalty of the node disjunction of index 'index'.
int64 Size() const
Returns the number of next variables in the model.
bool IsVehicleAllowedForIndex(int vehicle, int64 index)
Returns true if a vehicle is allowed to visit a given node.
const TransitCallback1 & UnaryTransitCallbackOrNull(int callback_index) const
friend class RoutingDimension
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.
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
std::vector< RoutingDimension * > GetDimensionsWithSoftOrSpanCosts() const
Returns dimensions with soft or vehicle span costs.
const std::vector< DisjunctionIndex > & GetDisjunctionIndices(int64 index) const
Returns the indices of the disjunctions to which an index belongs.
static const int64 kNoPenalty
Constant used to express a hard constraint instead of a soft penalty.
const IndexPairs & GetPickupAndDeliveryPairs() const
Returns pickup and delivery pairs currently in the model.
int vehicles() const
Returns the number of vehicle routes in the model.
int GetNumberOfDisjunctions() const
Returns the number of node disjunctions in the model.
bool IsMatchingModel() const
Returns true if a vehicle/node matching problem is detected.
int64 Start(int vehicle) const
Model inspection.
bool IsStart(int64 index) const
Returns true if 'index' represents the first node of a route.
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
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...
RoutingDisjunctionIndex DisjunctionIndex
const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs(int64 node_index) const
Same as above for deliveries.
static const int64 kint64max
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
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)