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 // Vehicle Routing Problem with Breaks.:
15 // A description of the Vehicle Routing Problem can be found here:
16 // http://en.wikipedia.org/wiki/Vehicle_routing_problem.
17 // This variant also includes vehicle breaks which must happen during the day
18 // with two alternate breaks schemes: either a long break in the middle of the
19 // day or two smaller ones which can be taken during a longer period of the day.
20
21 // [START program]
22 // [START import]
23 #include <cstdint>
24 #include <vector>
25
26 #include "ortools/constraint_solver/constraint_solver.h"
27 #include "ortools/constraint_solver/routing.h"
28 #include "ortools/constraint_solver/routing_enums.pb.h"
29 #include "ortools/constraint_solver/routing_index_manager.h"
30 #include "ortools/constraint_solver/routing_parameters.h"
31 // [END import]
32
33 namespace operations_research {
34 // [START data_model]
35 struct DataModel {
36 const std::vector<std::vector<int64_t>> time_matrix{
37 {0, 27, 38, 34, 29, 13, 25, 9, 15, 9, 26, 25, 19, 17, 23, 38, 33},
38 {27, 0, 34, 15, 9, 25, 36, 17, 34, 37, 54, 29, 24, 33, 50, 43, 60},
39 {38, 34, 0, 49, 43, 25, 13, 40, 23, 37, 20, 63, 58, 56, 39, 77, 37},
40 {34, 15, 49, 0, 5, 32, 43, 25, 42, 44, 61, 25, 31, 41, 58, 28, 67},
41 {29, 9, 43, 5, 0, 26, 38, 19, 36, 38, 55, 20, 25, 35, 52, 33, 62},
42 {13, 25, 25, 32, 26, 0, 11, 15, 9, 12, 29, 38, 33, 31, 25, 52, 35},
43 {25, 36, 13, 43, 38, 11, 0, 26, 9, 23, 17, 50, 44, 42, 25, 63, 24},
44 {9, 17, 40, 25, 19, 15, 26, 0, 17, 19, 36, 23, 17, 16, 33, 37, 42},
45 {15, 34, 23, 42, 36, 9, 9, 17, 0, 13, 19, 40, 34, 33, 16, 54, 25},
46 {9, 37, 37, 44, 38, 12, 23, 19, 13, 0, 17, 26, 21, 19, 13, 40, 23},
47 {26, 54, 20, 61, 55, 29, 17, 36, 19, 17, 0, 43, 38, 36, 19, 57, 17},
48 {25, 29, 63, 25, 20, 38, 50, 23, 40, 26, 43, 0, 5, 15, 32, 13, 42},
49 {19, 24, 58, 31, 25, 33, 44, 17, 34, 21, 38, 5, 0, 9, 26, 19, 36},
50 {17, 33, 56, 41, 35, 31, 42, 16, 33, 19, 36, 15, 9, 0, 17, 21, 26},
51 {23, 50, 39, 58, 52, 25, 25, 33, 16, 13, 19, 32, 26, 17, 0, 38, 9},
52 {38, 43, 77, 28, 33, 52, 63, 37, 54, 40, 57, 13, 19, 21, 38, 0, 39},
53 {33, 60, 37, 67, 62, 35, 24, 42, 25, 23, 17, 42, 36, 26, 9, 39, 0},
54 };
55 const std::vector<int64_t> service_time{
56 0, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
57 };
58 const int num_vehicles = 4;
59 const RoutingIndexManager::NodeIndex depot{0};
60 };
61 // [END data_model]
62
63 //! @brief Print the solution.
64 //! @param[in] data Data of the problem.
65 //! @param[in] manager Index manager used.
66 //! @param[in] routing Routing solver used.
67 //! @param[in] solution Solution found by the solver.
68 // [START solution_printer]
PrintSolution(const RoutingIndexManager & manager,const RoutingModel & routing,const Assignment & solution)69 void PrintSolution(const RoutingIndexManager& manager,
70 const RoutingModel& routing, const Assignment& solution) {
71 LOG(INFO) << "Objective: " << solution.ObjectiveValue();
72
73 LOG(INFO) << "Breaks:";
74 const Assignment::IntervalContainer& intervals =
75 solution.IntervalVarContainer();
76 for (const IntervalVarElement& break_interval : intervals.elements()) {
77 if (break_interval.PerformedValue()) {
78 LOG(INFO) << break_interval.Var()->name() << " "
79 << break_interval.DebugString();
80 } else {
81 LOG(INFO) << break_interval.Var()->name() << ": Unperformed";
82 }
83 }
84
85 const RoutingDimension& time_dimension = routing.GetDimensionOrDie("Time");
86 int64_t total_time{0};
87 for (int vehicle_id = 0; vehicle_id < manager.num_vehicles(); ++vehicle_id) {
88 LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
89 int64_t index = routing.Start(vehicle_id);
90 std::stringstream route;
91 while (routing.IsEnd(index) == false) {
92 const IntVar* time_var = time_dimension.CumulVar(index);
93 route << manager.IndexToNode(index).value() << " Time("
94 << solution.Value(time_var) << ") -> ";
95 index = solution.Value(routing.NextVar(index));
96 }
97 const IntVar* time_var = time_dimension.CumulVar(index);
98 route << manager.IndexToNode(index).value() << " Time("
99 << solution.Value(time_var) << ")";
100 LOG(INFO) << route.str();
101 LOG(INFO) << "Time of the route: " << solution.Value(time_var) << "min";
102 total_time += solution.Value(time_var);
103 }
104 LOG(INFO) << "Total time of all routes: " << total_time << "min";
105 LOG(INFO) << "";
106 LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
107 }
108 // [END solution_printer]
109
VrpBreaks()110 void VrpBreaks() {
111 // Instantiate the data problem.
112 // [START data]
113 DataModel data;
114 // [END data]
115
116 // Create Routing Index Manager
117 // [START index_manager]
118 RoutingIndexManager manager(data.time_matrix.size(), data.num_vehicles,
119 data.depot);
120 // [END index_manager]
121
122 // Create Routing Model.
123 // [START routing_model]
124 RoutingModel routing(manager);
125 // [END routing_model]
126
127 // Create and register a transit callback.
128 // [START transit_callback]
129 const int transit_callback_index = routing.RegisterTransitCallback(
130 [&data, &manager](int64_t from_index, int64_t to_index) -> int64_t {
131 // Convert from routing variable Index to distance matrix NodeIndex.
132 int from_node = manager.IndexToNode(from_index).value();
133 int to_node = manager.IndexToNode(to_index).value();
134 return data.time_matrix[from_node][to_node] +
135 data.service_time[from_node];
136 });
137 // [END transit_callback]
138
139 // Define cost of each arc.
140 // [START arc_cost]
141 routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);
142 // [END arc_cost]
143
144 // Add Time constraint.
145 // [START time_constraint]
146 routing.AddDimension(transit_callback_index,
147 10, // needed optional waiting time to place break
148 180, // maximum time per vehicle
149 true, // Force start cumul to zero.
150 "Time");
151 RoutingDimension* time_dimension = routing.GetMutableDimension("Time");
152 time_dimension->SetGlobalSpanCostCoefficient(10);
153 // [END time_constraint]
154
155 // Add Breaks
156 std::vector<int64_t> service_times(routing.Size());
157 for (int index = 0; index < routing.Size(); index++) {
158 const RoutingIndexManager::NodeIndex node = manager.IndexToNode(index);
159 service_times[index] = data.service_time[node.value()];
160 }
161
162 Solver* const solver = routing.solver();
163 for (int vehicle = 0; vehicle < manager.num_vehicles(); ++vehicle) {
164 std::vector<IntervalVar*> break_intervals;
165 IntervalVar* const break_interval = solver->MakeFixedDurationIntervalVar(
166 50, // start min
167 60, // start max
168 10, // duration: 10min
169 false, // optional: no
170 absl::StrCat("Break for vehicle ", vehicle));
171 break_intervals.push_back(break_interval);
172
173 time_dimension->SetBreakIntervalsOfVehicle(break_intervals, vehicle,
174 service_times);
175 }
176
177 // Setting first solution heuristic.
178 // [START parameters]
179 RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
180 searchParameters.set_first_solution_strategy(
181 FirstSolutionStrategy::PATH_CHEAPEST_ARC);
182 // [END parameters]
183
184 // Solve the problem.
185 // [START solve]
186 const Assignment* solution = routing.SolveWithParameters(searchParameters);
187 // [END solve]
188
189 // Print solution on console.
190 // [START print_solution]
191 if (solution != nullptr) {
192 PrintSolution(manager, routing, *solution);
193 } else {
194 LOG(INFO) << "No solution found.";
195 }
196 // [END print_solution]
197 }
198 } // namespace operations_research
199
main(int,char ** argv)200 int main(int /*argc*/, char** argv) {
201 operations_research::VrpBreaks();
202 return EXIT_SUCCESS;
203 }
204 // [END program]
205