1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16#include <cstdint>

17#include <cstdlib>

18#include <sstream>

19#include <string>

20#include <utility>

21#include <vector>

22

29

30

32

33struct DataModel {

34 const std::vector<std::vector<int64_t>> time_matrix{

35 {0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7},

36 {6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14},

37 {9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9},

38 {8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16},

39 {7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14},

40 {3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8},

41 {6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5},

42 {2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10},

43 {3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6},

44 {2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5},

45 {6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4},

46 {6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10},

47 {4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8},

48 {4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6},

49 {5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2},

50 {9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9},

51 {7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0},

52 };

53 const std::vector<std::pair<int64_t, int64_t>> time_windows{

54 {0, 5},

55 {7, 12},

56 {10, 15},

57 {5, 14},

58 {5, 13},

59 {0, 5},

60 {5, 10},

61 {0, 10},

62 {5, 10},

63 {0, 5},

64 {10, 16},

65 {10, 15},

66 {0, 5},

67 {5, 10},

68 {7, 12},

69 {10, 15},

70 {5, 15},

71 };

72 const int num_vehicles = 4;

73

74 const int vehicle_load_time = 5;

75 const int vehicle_unload_time = 5;

76 const int depot_capacity = 2;

77

78 const RoutingIndexManager::NodeIndex depot{0};

79};

80

81

82

88void PrintSolution(const DataModel& data, const RoutingIndexManager& manager,

89 const RoutingModel& routing, const Assignment& solution) {

90 const RoutingDimension& time_dimension = routing.GetDimensionOrDie("Time");

91 int64_t total_time{0};

92 for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {

93 if (!routing.IsVehicleUsed(solution, vehicle_id)) {

94 continue;

95 }

96 int64_t index = routing.Start(vehicle_id);

97 LOG(INFO) << "Route for vehicle " << vehicle_id << ":";

98 std::ostringstream route;

99 while (!routing.IsEnd(index)) {

100 auto time_var = time_dimension.CumulVar(index);

101 route << manager.IndexToNode(index).value() << " Time("

103 << ") -> ";

104 index = solution.Value(routing.NextVar(index));

105 }

106 auto time_var = time_dimension.CumulVar(index);

107 LOG(INFO) << route.str() << manager.IndexToNode(index).value() << " Time("

109 << ")";

110 LOG(INFO) << "Time of the route: " << solution.Min(time_var) << "min";

111 total_time += solution.Min(time_var);

112 }

113 LOG(INFO) << "Total time of all routes: " << total_time << "min";

114 LOG(INFO) << "";

115 LOG(INFO) << "Advanced usage:";

116 LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";

117}

118

119

120void VrpTimeWindows() {

121

122

123 DataModel data;

124

125

126

127

128 RoutingIndexManager manager(data.time_matrix.size(), data.num_vehicles,

129 data.depot);

130

131

132

133

134 RoutingModel routing(manager);

135

136

137

138

139 const int transit_callback_index = routing.RegisterTransitCallback(

140 [&data, &manager](const int64_t from_index,

141 const int64_t to_index) -> int64_t {

142

143 const int from_node = manager.IndexToNode(from_index).value();

144 const int to_node = manager.IndexToNode(to_index).value();

145 return data.time_matrix[from_node][to_node];

146 });

147

148

149

150

151 routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

152

153

154

155

156 const std::string time = "Time";

157 routing.AddDimension(transit_callback_index,

158 int64_t{30},

159 int64_t{30},

160 false,

161 time);

162 const RoutingDimension& time_dimension = routing.GetDimensionOrDie(time);

163

164 for (int i = 1; i < data.time_windows.size(); ++i) {

165 const int64_t index =

167 time_dimension.CumulVar(index)->SetRange(data.time_windows[i].first,

168 data.time_windows[i].second);

169 }

170

171 for (int i = 0; i < data.num_vehicles; ++i) {

172 const int64_t index = routing.Start(i);

173 time_dimension.CumulVar(index)->SetRange(data.time_windows[0].first,

174 data.time_windows[0].second);

175 }

176

177

178

179

180 Solver* solver = routing.solver();

181 std::vector<IntervalVar*> intervals;

182 for (int i = 0; i < data.num_vehicles; ++i) {

183

184 intervals.push_back(solver->MakeFixedDurationIntervalVar(

185 time_dimension.CumulVar(routing.Start(i)), data.vehicle_load_time,

186 "depot_interval"));

187

188 intervals.push_back(solver->MakeFixedDurationIntervalVar(

189 time_dimension.CumulVar(routing.End(i)), data.vehicle_unload_time,

190 "depot_interval"));

191 }

192

193

194

195 std::vector<int64_t> depot_usage(intervals.size(), 1);

196 solver->AddConstraint(solver->MakeCumulative(intervals, depot_usage,

197 data.depot_capacity, "depot"));

198

199

200

201

202 for (int i = 0; i < data.num_vehicles; ++i) {

203 routing.AddVariableMinimizedByFinalizer(

204 time_dimension.CumulVar(routing.Start(i)));

205 routing.AddVariableMinimizedByFinalizer(

206 time_dimension.CumulVar(routing.End(i)));

207 }

208

209

210

211

213 searchParameters.set_first_solution_strategy(

215

216

217

218

219 const Assignment* solution = routing.SolveWithParameters(searchParameters);

220

221

222

223

224 PrintSolution(data, manager, routing, *solution);

225

226}

227}

228

229int main(int , char* []) {

230 operations_research::VrpTimeWindows();

231 return EXIT_SUCCESS;

232}

233