Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
routing_utils.h
Go to the documentation of this file.
1// Copyright 2010-2025 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
14#ifndef OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_UTILS_H_
15#define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_UTILS_H_
16
17#include <cstdint>
18#include <functional>
19#include <utility>
20#include <vector>
21
22#include "absl/types/span.h"
23
24namespace operations_research {
25
26// Tracks whether bins constrained by several nonnegative dimensions can contain
27// items added incrementally. Also tracks soft violation costs.
29 public:
30 explicit BinCapacities(int num_bins)
31 : num_bins_(num_bins),
32 load_per_bin_(num_bins),
33 load_limits_per_bin_(num_bins),
34 total_cost_(0) {}
35
36 // Represents the limits of a bin with respect to a dimension:
37 // - max_load is a max total load, can cause TryAddItemToBin() to return false
38 // if load would exceed max_load.
39 // - soft_max_load is a max load that can be exceeded, causing the TotalCost()
40 // to increase. Initial value *may* be negative, to help with modelling.
41 // - cost_above_soft_max_load is the cost incurred per unit by which load
42 // exceeds soft_max_load.
43 struct LoadLimit {
44 int64_t max_load;
47 };
48
49 void AddDimension(
50 std::function<int64_t(int, int)> load_demand_of_item_for_bin,
51 std::vector<LoadLimit> load_limit_per_bin);
52 int NumDimensions() const { return load_demands_per_dimension_.size(); }
53
54 // Checks whether adding item(s) is feasible w.r.t. dimensions.
55 bool CheckAdditionFeasibility(int item, int bin) const;
56 bool CheckAdditionsFeasibility(absl::Span<const int> items, int bin) const;
57 // Adds item to bin, returns whether the bin is feasible.
58 // The item is still added even when infeasible.
59 bool AddItemToBin(int item, int bin);
60 // Removes item from bin, return whether the bin is feasible.
61 bool RemoveItemFromBin(int item, int bin);
62 // Returns the total cost incurred by violating soft costs.
63 int64_t TotalCost() const { return total_cost_; }
64 // Removes all items from given bin, resets the total cost.
65 void ClearItemsOfBin(int bin);
66 // Removes all items from all bins.
67 void ClearItems();
68
69 private:
70 const int num_bins_;
71 // load_per_bin_[bin][dimension]
72 std::vector<std::vector<int64_t>> load_per_bin_;
73 // load_limits_per_bin_[bin][dimension].
74 std::vector<std::vector<LoadLimit>> load_limits_per_bin_;
75 // load_demands_per_dimension_[dimension](item, bin).
76 std::vector<std::function<int64_t(int, int)>> load_demands_per_dimension_;
77 int64_t total_cost_;
78};
79
80// Returns false if the route starting with 'start' is empty. Otherwise sets
81// most_expensive_arc_starts_and_ranks and first_expensive_arc_indices according
82// to the most expensive chains on the route, and returns true.
84 int num_arcs, int64_t start,
85 const std::function<int64_t(int64_t)>& next_accessor,
86 const std::function<bool(int64_t)>& is_end,
87 const std::function<int64_t(int64_t, int64_t, int64_t)>&
88 arc_cost_for_route_start,
89 std::vector<std::pair<int64_t, int>>* most_expensive_arc_starts_and_ranks,
90 std::pair<int, int>* first_expensive_arc_indices);
91
92} // namespace operations_research
93
94#endif // OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_UTILS_H_
void ClearItems()
Removes all items from all bins.
bool RemoveItemFromBin(int item, int bin)
Removes item from bin, return whether the bin is feasible.
void AddDimension(std::function< int64_t(int, int)> load_demand_of_item_for_bin, std::vector< LoadLimit > load_limit_per_bin)
void ClearItemsOfBin(int bin)
Removes all items from given bin, resets the total cost.
bool CheckAdditionFeasibility(int item, int bin) const
Checks whether adding item(s) is feasible w.r.t. dimensions.
int64_t TotalCost() const
Returns the total cost incurred by violating soft costs.
bool AddItemToBin(int item, int bin)
bool CheckAdditionsFeasibility(absl::Span< const int > items, int bin) const
In SWIG mode, we don't want anything besides these top-level includes.
bool FindMostExpensiveArcsOnRoute(int num_arcs, int64_t start, const std::function< int64_t(int64_t)> &next_accessor, const std::function< bool(int64_t)> &is_end, const std::function< int64_t(int64_t, int64_t, int64_t)> &arc_cost_for_route_start, std::vector< std::pair< int64_t, int > > *most_expensive_arc_starts_and_ranks, std::pair< int, int > *first_expensive_arc_indices)