1 // Copyright 2010-2021 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 //
15 // Capacitated Vehicle Routing Problem with Time Windows and Breaks.
16 // A description of the Capacitated Vehicle Routing Problem with Time Windows
17 // can be found here:
18 // http://en.wikipedia.org/wiki/Vehicle_routing_problem.
19 // The variant which is tackled by this model includes a capacity dimension,
20 // time windows and optional orders, with a penalty cost if orders are not
21 // performed. For the sake of simplicty, orders are randomly located and
22 // distances are computed using the Manhattan distance. Distances are assumed
23 // to be in meters and times in seconds.
24 // This variant also includes vehicle breaks which must happen during the day
25 // with two alternate breaks schemes: either a long break in the middle of the
26 // day or two smaller ones which can be taken during a longer period of the day.
27 
28 #include <cstdint>
29 #include <vector>
30 
31 #include "absl/flags/parse.h"
32 #include "absl/flags/usage.h"
33 #include "absl/random/random.h"
34 #include "absl/strings/str_cat.h"
35 #include "examples/cpp/cvrptw_lib.h"
36 #include "google/protobuf/text_format.h"
37 #include "ortools/base/commandlineflags.h"
38 #include "ortools/base/integral_types.h"
39 #include "ortools/base/logging.h"
40 #include "ortools/constraint_solver/routing.h"
41 #include "ortools/constraint_solver/routing_enums.pb.h"
42 #include "ortools/constraint_solver/routing_index_manager.h"
43 #include "ortools/constraint_solver/routing_parameters.h"
44 #include "ortools/constraint_solver/routing_parameters.pb.h"
45 
46 using operations_research::Assignment;
47 using operations_research::DefaultRoutingSearchParameters;
48 using operations_research::FirstSolutionStrategy;
49 using operations_research::GetSeed;
50 using operations_research::IntervalVar;
51 using operations_research::LocationContainer;
52 using operations_research::RandomDemand;
53 using operations_research::RoutingDimension;
54 using operations_research::RoutingIndexManager;
55 using operations_research::RoutingModel;
56 using operations_research::RoutingNodeIndex;
57 using operations_research::RoutingSearchParameters;
58 using operations_research::ServiceTimePlusTransition;
59 using operations_research::Solver;
60 
61 ABSL_FLAG(int, vrp_orders, 100, "Nodes in the problem.");
62 ABSL_FLAG(int, vrp_vehicles, 20,
63           "Size of Traveling Salesman Problem instance.");
64 ABSL_FLAG(bool, vrp_use_deterministic_random_seed, false,
65           "Use deterministic random seeds.");
66 ABSL_FLAG(std::string, routing_search_parameters, "",
67           "Text proto RoutingSearchParameters (possibly partial) that will "
68           "override the DefaultRoutingSearchParameters()");
69 
70 const char* kTime = "Time";
71 const char* kCapacity = "Capacity";
72 
main(int argc,char ** argv)73 int main(int argc, char** argv) {
74   google::InitGoogleLogging(argv[0]);
75   absl::ParseCommandLine(argc, argv);
76   CHECK_LT(0, absl::GetFlag(FLAGS_vrp_orders))
77       << "Specify an instance size greater than 0.";
78   CHECK_LT(0, absl::GetFlag(FLAGS_vrp_vehicles))
79       << "Specify a non-null vehicle fleet size.";
80   // VRP of size absl::GetFlag(FLAGS_vrp_size).
81   // Nodes are indexed from 0 to absl::GetFlag(FLAGS_vrp_orders), the starts and
82   // ends of the routes are at node 0.
83   const RoutingIndexManager::NodeIndex kDepot(0);
84   RoutingIndexManager manager(absl::GetFlag(FLAGS_vrp_orders) + 1,
85                               absl::GetFlag(FLAGS_vrp_vehicles), kDepot);
86   RoutingModel routing(manager);
87   RoutingSearchParameters parameters = DefaultRoutingSearchParameters();
88   CHECK(google::protobuf::TextFormat::MergeFromString(
89       absl::GetFlag(FLAGS_routing_search_parameters), &parameters));
90   parameters.set_first_solution_strategy(
91       FirstSolutionStrategy::PARALLEL_CHEAPEST_INSERTION);
92 
93   // Setting up locations.
94   const int64_t kXMax = 100000;
95   const int64_t kYMax = 100000;
96   const int64_t kSpeed = 10;
97   LocationContainer locations(
98       kSpeed, absl::GetFlag(FLAGS_vrp_use_deterministic_random_seed));
99   for (int location = 0; location <= absl::GetFlag(FLAGS_vrp_orders);
100        ++location) {
101     locations.AddRandomLocation(kXMax, kYMax);
102   }
103 
104   // Setting the cost function.
105   const int vehicle_cost = routing.RegisterTransitCallback(
106       [&locations, &manager](int64_t i, int64_t j) {
107         return locations.ManhattanDistance(manager.IndexToNode(i),
108                                            manager.IndexToNode(j));
109       });
110   routing.SetArcCostEvaluatorOfAllVehicles(vehicle_cost);
111 
112   // Adding capacity dimension constraints.
113   const int64_t kVehicleCapacity = 40;
114   const int64_t kNullCapacitySlack = 0;
115   RandomDemand demand(manager.num_nodes(), kDepot,
116                       absl::GetFlag(FLAGS_vrp_use_deterministic_random_seed));
117   demand.Initialize();
118   routing.AddDimension(routing.RegisterTransitCallback(
119                            [&demand, &manager](int64_t i, int64_t j) {
120                              return demand.Demand(manager.IndexToNode(i),
121                                                   manager.IndexToNode(j));
122                            }),
123                        kNullCapacitySlack, kVehicleCapacity,
124                        /*fix_start_cumul_to_zero=*/true, kCapacity);
125 
126   // Adding time dimension constraints.
127   const int64_t kTimePerDemandUnit = 300;
128   const int64_t kHorizon = 24 * 3600;
129   ServiceTimePlusTransition time(
130       kTimePerDemandUnit,
131       [&demand](RoutingNodeIndex i, RoutingNodeIndex j) {
132         return demand.Demand(i, j);
133       },
134       [&locations](RoutingNodeIndex i, RoutingNodeIndex j) {
135         return locations.ManhattanTime(i, j);
136       });
137   routing.AddDimension(
138       routing.RegisterTransitCallback([&time, &manager](int64_t i, int64_t j) {
139         return time.Compute(manager.IndexToNode(i), manager.IndexToNode(j));
140       }),
141       kHorizon, kHorizon, /*fix_start_cumul_to_zero=*/false, kTime);
142   RoutingDimension* const time_dimension = routing.GetMutableDimension(kTime);
143 
144   // Adding time windows.
145   std::mt19937 randomizer(
146       GetSeed(absl::GetFlag(FLAGS_vrp_use_deterministic_random_seed)));
147   const int64_t kTWDuration = 5 * 3600;
148   for (int order = 1; order < manager.num_nodes(); ++order) {
149     const int64_t start =
150         absl::Uniform<int32_t>(randomizer, 0, kHorizon - kTWDuration);
151     time_dimension->CumulVar(order)->SetRange(start, start + kTWDuration);
152     routing.AddToAssignment(time_dimension->SlackVar(order));
153   }
154 
155   // Minimize time variables.
156   for (int i = 0; i < routing.Size(); ++i) {
157     routing.AddVariableMinimizedByFinalizer(time_dimension->CumulVar(i));
158   }
159   for (int j = 0; j < absl::GetFlag(FLAGS_vrp_vehicles); ++j) {
160     routing.AddVariableMinimizedByFinalizer(
161         time_dimension->CumulVar(routing.Start(j)));
162     routing.AddVariableMinimizedByFinalizer(
163         time_dimension->CumulVar(routing.End(j)));
164   }
165 
166   // Adding vehicle breaks:
167   // - 40min breaks between 11:00am and 1:00pm
168   // or
169   // - 2 x 30min breaks between 10:00am and 3:00pm, at least 1h apart
170   // First, fill service time vector.
171   std::vector<int64_t> service_times(routing.Size());
172   for (int node = 0; node < routing.Size(); node++) {
173     if (node >= routing.nodes()) {
174       service_times[node] = 0;
175     } else {
176       const RoutingIndexManager::NodeIndex index(node);
177       service_times[node] = kTimePerDemandUnit * demand.Demand(index, index);
178     }
179   }
180   const std::vector<std::vector<int>> break_data = {
181       {/*start_min*/ 11, /*start_max*/ 13, /*duration*/ 2400},
182       {/*start_min*/ 10, /*start_max*/ 15, /*duration*/ 1800},
183       {/*start_min*/ 10, /*start_max*/ 15, /*duration*/ 1800}};
184   Solver* const solver = routing.solver();
185   for (int vehicle = 0; vehicle < absl::GetFlag(FLAGS_vrp_vehicles);
186        ++vehicle) {
187     std::vector<IntervalVar*> breaks;
188     for (int i = 0; i < break_data.size(); ++i) {
189       IntervalVar* const break_interval = solver->MakeFixedDurationIntervalVar(
190           break_data[i][0] * 3600, break_data[i][1] * 3600, break_data[i][2],
191           true, absl::StrCat("Break ", i, " on vehicle ", vehicle));
192       breaks.push_back(break_interval);
193     }
194     // break1 performed iff break2 performed
195     solver->AddConstraint(solver->MakeEquality(breaks[1]->PerformedExpr(),
196                                                breaks[2]->PerformedExpr()));
197     // break2 start 1h after break1.
198     solver->AddConstraint(solver->MakeIntervalVarRelationWithDelay(
199         breaks[2], Solver::STARTS_AFTER_END, breaks[1], 3600));
200     // break0 performed iff break2 unperformed
201     solver->AddConstraint(solver->MakeNonEquality(breaks[0]->PerformedExpr(),
202                                                   breaks[2]->PerformedExpr()));
203 
204     time_dimension->SetBreakIntervalsOfVehicle(std::move(breaks), vehicle,
205                                                service_times);
206   }
207 
208   // Adding penalty costs to allow skipping orders.
209   const int64_t kPenalty = 10000000;
210   const RoutingIndexManager::NodeIndex kFirstNodeAfterDepot(1);
211   for (RoutingIndexManager::NodeIndex order = kFirstNodeAfterDepot;
212        order < routing.nodes(); ++order) {
213     std::vector<int64_t> orders(1, manager.NodeToIndex(order));
214     routing.AddDisjunction(orders, kPenalty);
215   }
216 
217   // Solve, returns a solution if any (owned by RoutingModel).
218   const Assignment* solution = routing.SolveWithParameters(parameters);
219   if (solution != nullptr) {
220     LOG(INFO) << "Breaks: ";
221     for (const auto& break_interval :
222          solution->IntervalVarContainer().elements()) {
223       if (break_interval.PerformedValue() == 1) {
224         LOG(INFO) << break_interval.Var()->name() << " "
225                   << break_interval.DebugString();
226       } else {
227         LOG(INFO) << break_interval.Var()->name() << " unperformed";
228       }
229     }
230     DisplayPlan(manager, routing, *solution, false, 0, 0,
231                 routing.GetDimensionOrDie(kCapacity),
232                 routing.GetDimensionOrDie(kTime));
233   } else {
234     LOG(INFO) << "No solution found.";
235   }
236   return EXIT_SUCCESS;
237 }
238