Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
cvrptw_lib.cc
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
15
16#include <algorithm>
17#include <cstdint>
18#include <limits>
19#include <memory>
20#include <random>
21#include <string>
22#include <utility>
23#include <vector>
24
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"
35
36namespace operations_research {
37
39
40int32_t GetSeed(bool deterministic) {
41 if (deterministic) {
42 return 7777777;
43 } else {
44 return absl::Uniform<int64_t>(absl::BitGen(), 0,
45 std::numeric_limits<int64_t>::max());
46 }
47}
48
49LocationContainer::LocationContainer(int64_t speed, bool use_deterministic_seed)
50 : randomizer_(GetSeed(use_deterministic_seed)), speed_(speed) {
51 CHECK_LT(0, speed_);
52}
53
54void LocationContainer::AddRandomLocation(int64_t x_max, int64_t y_max) {
55 AddRandomLocation(x_max, y_max, 1);
56}
57
58void LocationContainer::AddRandomLocation(int64_t x_max, int64_t y_max,
59 int duplicates) {
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) {
63 AddLocation(x, y);
64 }
65}
66
68 NodeIndex to) const {
69 return locations_[from].DistanceTo(locations_[to]);
70}
71
73 NodeIndex to) const {
74 return -ManhattanDistance(from, to);
75}
76
78 return ManhattanDistance(from, to) / speed_;
79}
80
82 if (node1 < locations_.size() && node2 < locations_.size()) {
83 return locations_[node1].IsAtSameLocation(locations_[node2]);
84 }
85 return false;
86}
88 int64_t node2) const {
89 // The direct conversion from constraint model indices to routing model
90 // nodes is correct because the depot is node 0.
91 // TODO(user): Fetch proper indices from routing model.
92 return SameLocation(NodeIndex(node1), NodeIndex(node2));
93}
94
95LocationContainer::Location::Location() : x_(0), y_(0) {}
96
97LocationContainer::Location::Location(int64_t x, int64_t y) : x_(x), y_(y) {}
98
99int64_t LocationContainer::Location::DistanceTo(
100 const Location& location) const {
101 return Abs(x_ - location.x_) + Abs(y_ - location.y_);
102}
103
104bool LocationContainer::Location::IsAtSameLocation(
105 const Location& location) const {
106 return x_ == location.x_ && y_ == location.y_;
107}
108
109int64_t LocationContainer::Location::Abs(int64_t value) {
110 return std::max(value, -value);
111}
112
114 bool use_deterministic_seed)
115 : size_(size),
116 depot_(depot),
117 use_deterministic_seed_(use_deterministic_seed) {
118 CHECK_LT(0, size_);
119}
120
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_) {
128 demand_[order] = 0;
129 } else {
130 demand_[order] = kDemandMin + absl::Uniform(randomizer, 0,
131 kDemandMax - kDemandMin + 1);
132 }
133 }
134}
135
136int64_t RandomDemand::Demand(NodeIndex from, NodeIndex /*to*/) const {
137 return demand_[from.value()];
138}
139
141 int64_t time_per_demand_unit, RoutingNodeEvaluator2 demand,
142 RoutingNodeEvaluator2 transition_time)
143 : time_per_demand_unit_(time_per_demand_unit),
144 demand_(std::move(demand)),
145 transition_time_(std::move(transition_time)) {}
146
148 return time_per_demand_unit_ * demand_(from, to) + transition_time_(from, to);
149}
150
152 int64_t stop_time, const LocationContainer& location_container,
153 RoutingNodeEvaluator2 transition_time)
154 : stop_time_(stop_time),
155 location_container_(location_container),
156 transition_time_(std::move(transition_time)) {}
157
159 NodeIndex to) const {
160 return location_container_.SameLocation(from, to)
161 ? 0
162 : stop_time_ + transition_time_(from, to);
163}
164
166 const RoutingModel& routing,
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));
174 }
175
176 // Display plan cost.
177 std::string plan_output = absl::StrFormat("Cost %d\n", plan.ObjectiveValue());
178
179 // Display dropped orders.
180 std::string dropped;
181 for (int64_t order = 0; order < routing.Size(); ++order) {
182 if (routing.IsStart(order) || routing.IsEnd(order)) continue;
183 if (plan.Value(routing.NextVar(order)) == order) {
184 if (dropped.empty()) {
185 absl::StrAppendFormat(&dropped, " %d",
186 manager.IndexToNode(order).value());
187 } else {
188 absl::StrAppendFormat(&dropped, ", %d",
189 manager.IndexToNode(order).value());
190 }
191 }
192 }
193 if (!dropped.empty()) {
194 plan_output += "Dropped orders:" + dropped + "\n";
195 }
196
197 if (use_same_vehicle_costs) {
198 int group_size = 0;
199 int64_t group_same_vehicle_cost = 0;
200 absl::btree_set<int> visited;
201 for (int64_t order = 0; order < routing.Size(); ++order) {
202 if (routing.IsStart(order) || routing.IsEnd(order)) continue;
203 ++group_size;
204 visited.insert(plan.Value(routing.VehicleVar(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;
208 }
209 group_size = 0;
210 visited.clear();
211 }
212 }
213 if (visited.size() > 1) {
214 group_same_vehicle_cost += (visited.size() - 1) * same_vehicle_cost;
215 }
216 LOG(INFO) << "Same vehicle costs: " << group_same_vehicle_cost;
217 }
218
219 // Display actual output for each vehicle.
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);
227 } else {
228 absl::StrAppendFormat(&plan_output, "%s(%d, %d) ", name, var_min,
229 var_max);
230 }
231 };
232 for (int route_number = 0; route_number < routing.vehicles();
233 ++route_number) {
234 int64_t order = routing.Start(route_number);
235 absl::StrAppendFormat(&plan_output, "Route %d: ", route_number);
236 if (routing.IsEnd(plan.Value(routing.NextVar(order)))) {
237 plan_output += "Empty\n";
238 } else {
239 while (true) {
240 absl::StrAppendFormat(&plan_output, "%d ",
241 manager.IndexToNode(order).value());
242 for (const operations_research::RoutingDimension* dimension : dimensions) {
243 str_append_variable(dimension->CumulVar(order), dimension->name());
244 operations_research::IntVar* const slack_var =
245 routing.IsEnd(order) ? nullptr : dimension->SlackVar(order);
246 str_append_variable(slack_var, dimension->name() + "Slack");
247 }
248 if (routing.IsEnd(order)) break;
249 plan_output += "-> ";
250 order = plan.Value(routing.NextVar(order));
251 }
252 plan_output += "\n";
253 }
254 }
255 LOG(INFO) << plan_output;
256}
257} // namespace operations_research
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 ManhattanDistance(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
Definition cvrptw_lib.cc:67
void AddRandomLocation(int64_t x_max, int64_t y_max)
Definition cvrptw_lib.cc:54
int64_t ManhattanTime(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
Definition cvrptw_lib.cc:77
bool SameLocation(RoutingIndexManager::NodeIndex node1, RoutingIndexManager::NodeIndex node2) const
Definition cvrptw_lib.cc:81
void AddLocation(int64_t x, int64_t y)
Definition cvrptw_lib.h:43
LocationContainer(int64_t speed, bool use_deterministic_seed)
Definition cvrptw_lib.cc:49
int64_t NegManhattanDistance(RoutingIndexManager::NodeIndex from, RoutingIndexManager::NodeIndex to) const
Definition cvrptw_lib.cc:72
int64_t SameLocationFromIndex(int64_t node1, int64_t node2) const
Definition cvrptw_lib.cc:87
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)
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.
Definition cvrptw_lib.cc:40
std::function< int64_t(RoutingNodeIndex, RoutingNodeIndex)> RoutingNodeEvaluator2
Definition cvrptw_lib.h:33
STL namespace.
trees with all degrees equal to