25#include "absl/container/btree_set.h"
26#include "absl/random/distributions.h"
27#include "absl/random/random.h"
28#include "absl/strings/str_format.h"
29#include "absl/strings/string_view.h"
30#include "absl/types/span.h"
44 return absl::Uniform<int64_t>(absl::BitGen(), 0,
45 std::numeric_limits<int64_t>::max());
50 : randomizer_(
GetSeed(use_deterministic_seed)), speed_(speed) {
60 const int64_t x = absl::Uniform(randomizer_, 0, x_max + 1);
61 const int64_t y = absl::Uniform(randomizer_, 0, y_max + 1);
62 for (
int i = 0; i < duplicates; ++i) {
69 return locations_[from].DistanceTo(locations_[
to]);
82 if (node1 < locations_.size() && node2 < locations_.size()) {
83 return locations_[node1].IsAtSameLocation(locations_[node2]);
88 int64_t node2)
const {
95LocationContainer::Location::Location() : x_(0), y_(0) {}
97LocationContainer::Location::Location(int64_t x, int64_t y) : x_(x), y_(y) {}
99int64_t LocationContainer::Location::DistanceTo(
100 const Location& location)
const {
101 return Abs(x_ - location.x_) + Abs(y_ - location.y_);
104bool LocationContainer::Location::IsAtSameLocation(
105 const Location& location)
const {
106 return x_ == location.x_ && y_ == location.y_;
109int64_t LocationContainer::Location::Abs(int64_t value) {
110 return std::max(value, -value);
114 bool use_deterministic_seed)
117 use_deterministic_seed_(use_deterministic_seed) {
122 const int64_t kDemandMax = 5;
123 const int64_t kDemandMin = 1;
124 demand_ = std::make_unique<int64_t[]>(size_);
125 std::mt19937 randomizer(
GetSeed(use_deterministic_seed_));
126 for (
int order = 0; order < size_; ++order) {
127 if (order == depot_) {
130 demand_[order] = kDemandMin + absl::Uniform(randomizer, 0,
131 kDemandMax - kDemandMin + 1);
137 return demand_[from.value()];
143 : time_per_demand_unit_(time_per_demand_unit),
144 demand_(
std::move(demand)),
145 transition_time_(
std::move(transition_time)) {}
148 return time_per_demand_unit_ * demand_(from,
to) + transition_time_(from,
to);
154 : stop_time_(stop_time),
155 location_container_(location_container),
156 transition_time_(
std::move(transition_time)) {}
160 return location_container_.SameLocation(from,
to)
162 : stop_time_ + transition_time_(from,
to);
168 bool use_same_vehicle_costs, int64_t max_nodes_per_group,
169 int64_t same_vehicle_cost,
170 absl::Span<const std::string> dimension_names) {
171 std::vector<const operations_research::RoutingDimension*> dimensions;
172 for (
const std::string& dimension_name : dimension_names) {
173 dimensions.push_back(&
routing.GetDimensionOrDie(dimension_name));
177 std::string plan_output = absl::StrFormat(
"Cost %d\n", plan.
ObjectiveValue());
181 for (int64_t order = 0; order <
routing.Size(); ++order) {
184 if (dropped.empty()) {
185 absl::StrAppendFormat(&dropped,
" %d",
188 absl::StrAppendFormat(&dropped,
", %d",
193 if (!dropped.empty()) {
194 plan_output +=
"Dropped orders:" + dropped +
"\n";
197 if (use_same_vehicle_costs) {
199 int64_t group_same_vehicle_cost = 0;
200 absl::btree_set<int> visited;
201 for (int64_t order = 0; order <
routing.Size(); ++order) {
205 if (group_size == max_nodes_per_group) {
206 if (visited.size() > 1) {
207 group_same_vehicle_cost += (visited.size() - 1) * same_vehicle_cost;
213 if (visited.size() > 1) {
214 group_same_vehicle_cost += (visited.size() - 1) * same_vehicle_cost;
216 LOG(INFO) <<
"Same vehicle costs: " << group_same_vehicle_cost;
220 const auto str_append_variable =
221 [&plan, &plan_output](
const IntVar* var, absl::string_view name) {
222 if (var ==
nullptr || !plan.
Contains(var))
return;
223 const int64_t var_min = plan.
Min(var);
224 const int64_t var_max = plan.
Max(var);
225 if (var_min == var_max) {
226 absl::StrAppendFormat(&plan_output,
"%s(%d) ", name, var_min);
228 absl::StrAppendFormat(&plan_output,
"%s(%d, %d) ", name, var_min,
232 for (
int route_number = 0; route_number <
routing.vehicles();
234 int64_t order =
routing.Start(route_number);
235 absl::StrAppendFormat(&plan_output,
"Route %d: ", route_number);
237 plan_output +=
"Empty\n";
240 absl::StrAppendFormat(&plan_output,
"%d ",
242 for (
const operations_research::RoutingDimension* dimension : dimensions) {
243 str_append_variable(dimension->CumulVar(order), dimension->name());
245 routing.IsEnd(order) ? nullptr : dimension->SlackVar(order);
246 str_append_variable(slack_var, dimension->
name() +
"Slack");
248 if (
routing.IsEnd(order))
break;
249 plan_output +=
"-> ";
255 LOG(INFO) << plan_output;
int64_t Value(const IntVar *var) const
int64_t Max(const IntVar *var) const
int64_t Min(const IntVar *var) const
bool Contains(const IntVar *var) const
int64_t ObjectiveValue() const
int64_t ManhattanDistance(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
void AddRandomLocation(int64_t x_max, int64_t y_max)
int64_t ManhattanTime(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
bool SameLocation(RoutingIndexManager::NodeIndex node1, RoutingIndexManager::NodeIndex node2) const
void AddLocation(int64_t x, int64_t y)
LocationContainer(int64_t speed, bool use_deterministic_seed)
int64_t NegManhattanDistance(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
int64_t SameLocationFromIndex(int64_t node1, int64_t node2) const
virtual std::string name() const
Object naming.
int64_t Demand(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
RandomDemand(int size, RoutingIndexManager::NodeIndex depot, bool use_deterministic_seed)
RoutingNodeIndex NodeIndex
NodeIndex IndexToNode(int64_t index) const
ServiceTimePlusTransition(int64_t time_per_demand_unit, operations_research::RoutingNodeEvaluator2 demand, operations_research::RoutingNodeEvaluator2 transition_time)
int64_t Compute(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
StopServiceTimePlusTransition(int64_t stop_time, const LocationContainer &location_container, operations_research::RoutingNodeEvaluator2 transition_time)
int64_t Compute(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
Common utilities for parsing routing instances.
In SWIG mode, we don't want anything besides these top-level includes.
void DisplayPlan(const RoutingIndexManager &manager, const RoutingModel &routing, const operations_research::Assignment &plan, bool use_same_vehicle_costs, int64_t max_nodes_per_group, int64_t same_vehicle_cost, absl::Span< const std::string > dimension_names)
BlossomGraph::NodeIndex NodeIndex
int32_t GetSeed(bool deterministic)
Random seed generator.
std::function< int64_t(RoutingNodeIndex, RoutingNodeIndex)> RoutingNodeEvaluator2
trees with all degrees equal to