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

31

33

34struct DataModel {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

53 };

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

55 {0, 5},

56 {7, 12},

57 {10, 15},

58 {16, 18},

59 {10, 13},

60 {0, 5},

61 {5, 10},

62 {0, 4},

63 {5, 10},

64 {0, 3},

65 {10, 16},

66 {10, 15},

67 {0, 5},

68 {5, 10},

69 {7, 8},

70 {10, 15},

71 {11, 15},

72 };

73 const int num_vehicles = 4;

74 const RoutingIndexManager::NodeIndex depot{0};

75};

76

77

78

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

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

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

87 int64_t total_time{0};

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

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

90 continue;

91 }

92 int64_t index = routing.Start(vehicle_id);

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

94 std::ostringstream route;

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

96 auto time_var = time_dimension.CumulVar(index);

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

99 << ") -> ";

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

101 }

102 auto time_var = time_dimension.CumulVar(index);

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

105 << ")";

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

107 total_time += solution.Min(time_var);

108 }

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

110 LOG(INFO) << "";

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

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

113}

114

115

116void VrpTimeWindows() {

117

118

119 DataModel data;

120

121

122

123

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

125 data.depot);

126

127

128

129

130 RoutingModel routing(manager);

131

132

133

134

135 const int transit_callback_index = routing.RegisterTransitCallback(

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

137 const int64_t to_index) -> int64_t {

138

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

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

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

142 });

143

144

145

146

147 routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

148

149

150

151

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

153 routing.AddDimension(transit_callback_index,

154 int64_t{30},

155 int64_t{30},

156 false,

157 time);

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

159

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

161 const int64_t index =

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

164 data.time_windows[i].second);

165 }

166

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

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

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

170 data.time_windows[0].second);

171 }

172

173

174

175

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

177 routing.AddVariableMinimizedByFinalizer(

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

179 routing.AddVariableMinimizedByFinalizer(

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

181 }

182

183

184

185

187 searchParameters.set_first_solution_strategy(

189

190

191

192

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

194

195

196

197

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

199

200}

201}

202

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

204 operations_research::VrpTimeWindows();

205 return EXIT_SUCCESS;

206}

207

208