Google OR-Tools: vrp_with_time_limit.cc
Simple VRP example.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16#include <algorithm>
17#include <cstdint>
18#include <cstdlib>
19#include <sstream>
20
21#include "google/protobuf/duration.pb.h"
28
29
35
36void PrintSolution(const RoutingIndexManager& manager,
37 const RoutingModel& routing, const Assignment& solution) {
38 int64_t max_route_distance = 0;
39 for (int vehicle_id = 0; vehicle_id < manager.num_vehicles(); ++vehicle_id) {
40 if (!routing.IsVehicleUsed(solution, vehicle_id)) {
41 continue;
42 }
43 int64_t index = routing.Start(vehicle_id);
44 LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
45 int64_t route_distance = 0;
46 std::stringstream route;
47 while (!routing.IsEnd(index)) {
48 route << manager.IndexToNode(index).value() << " -> ";
49 const int64_t previous_index = index;
50 index = solution.Value(routing.NextVar(index));
51 route_distance += const_cast<RoutingModel&>(routing).GetArcCostForVehicle(
52 previous_index, index, int64_t{vehicle_id});
53 }
54 LOG(INFO) << route.str() << manager.IndexToNode(index).value();
55 LOG(INFO) << "Distance of the route: " << route_distance << "m";
56 max_route_distance = std::max(route_distance, max_route_distance);
57 }
58 LOG(INFO) << "Maximum of the route distances: " << max_route_distance << "m";
59 LOG(INFO) << "";
60 LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
61}
62
63
64void VrpGlobalSpan() {
65
66
67 const int num_locations = 20;
68 const int num_vehicles = 5;
70
71
72
73
74 RoutingIndexManager manager(num_locations, num_vehicles, depot);
75
76
77
78
79 RoutingModel routing(manager);
80
81
82
83
84 const int transit_callback_index = routing.RegisterTransitCallback(
85 [](int64_t from_index, int64_t to_index) -> int64_t {
86 (void)from_index;
87 (void)to_index;
88 return 1;
89 });
90
91
92
93
94 routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);
95
96
97
98
99 routing.AddDimension(transit_callback_index,
100 0,
101 3000,
102 true, "Distance");
103 const RoutingDimension& distance_dimension =
104 routing.GetDimensionOrDie("Distance");
105 const_cast<RoutingDimension&>(distance_dimension)
106 .SetGlobalSpanCostCoefficient(100);
107
108
109
110
112 search_parameters.set_first_solution_strategy(
114 search_parameters.set_local_search_metaheuristic(
116 search_parameters.set_log_search(true);
117 search_parameters.mutable_time_limit()->set_seconds(5);
118
119
120
121
122 const Assignment* solution = routing.SolveWithParameters(search_parameters);
123
124
125
126
127 PrintSolution(manager, routing, *solution);
128
129}
130}
131
132int main(int , char* []) {
133 operations_research::VrpGlobalSpan();
134 return EXIT_SUCCESS;
135}
136
static constexpr Value PATH_CHEAPEST_ARC
RoutingNodeIndex NodeIndex
int main(int argc, char **argv)
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
RoutingSearchParameters DefaultRoutingSearchParameters()
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...