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