Google OR-Tools v9.15
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
tsp_circuit_board.cc

Simple TSP example.

1// Copyright 2010-2025 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// [START program]
15// [START import]
16#include <cmath>
17#include <cstdint>
18#include <cstdlib>
19#include <sstream>
20#include <vector>
21
22#include "ortools/base/logging.h"
23#include "ortools/constraint_solver/constraint_solver.h"
24#include "ortools/constraint_solver/routing.h"
25#include "ortools/constraint_solver/routing_enums.pb.h"
26#include "ortools/constraint_solver/routing_index_manager.h"
27#include "ortools/constraint_solver/routing_parameters.h"
28// [END import]
29
30namespace operations_research {
31// [START data_model]
32struct DataModel {
33 const std::vector<std::vector<int>> locations{
34 {288, 149}, {288, 129}, {270, 133}, {256, 141}, {256, 157}, {246, 157},
35 {236, 169}, {228, 169}, {228, 161}, {220, 169}, {212, 169}, {204, 169},
36 {196, 169}, {188, 169}, {196, 161}, {188, 145}, {172, 145}, {164, 145},
37 {156, 145}, {148, 145}, {140, 145}, {148, 169}, {164, 169}, {172, 169},
38 {156, 169}, {140, 169}, {132, 169}, {124, 169}, {116, 161}, {104, 153},
39 {104, 161}, {104, 169}, {90, 165}, {80, 157}, {64, 157}, {64, 165},
40 {56, 169}, {56, 161}, {56, 153}, {56, 145}, {56, 137}, {56, 129},
41 {56, 121}, {40, 121}, {40, 129}, {40, 137}, {40, 145}, {40, 153},
42 {40, 161}, {40, 169}, {32, 169}, {32, 161}, {32, 153}, {32, 145},
43 {32, 137}, {32, 129}, {32, 121}, {32, 113}, {40, 113}, {56, 113},
44 {56, 105}, {48, 99}, {40, 99}, {32, 97}, {32, 89}, {24, 89},
45 {16, 97}, {16, 109}, {8, 109}, {8, 97}, {8, 89}, {8, 81},
46 {8, 73}, {8, 65}, {8, 57}, {16, 57}, {8, 49}, {8, 41},
47 {24, 45}, {32, 41}, {32, 49}, {32, 57}, {32, 65}, {32, 73},
48 {32, 81}, {40, 83}, {40, 73}, {40, 63}, {40, 51}, {44, 43},
49 {44, 35}, {44, 27}, {32, 25}, {24, 25}, {16, 25}, {16, 17},
50 {24, 17}, {32, 17}, {44, 11}, {56, 9}, {56, 17}, {56, 25},
51 {56, 33}, {56, 41}, {64, 41}, {72, 41}, {72, 49}, {56, 49},
52 {48, 51}, {56, 57}, {56, 65}, {48, 63}, {48, 73}, {56, 73},
53 {56, 81}, {48, 83}, {56, 89}, {56, 97}, {104, 97}, {104, 105},
54 {104, 113}, {104, 121}, {104, 129}, {104, 137}, {104, 145}, {116, 145},
55 {124, 145}, {132, 145}, {132, 137}, {140, 137}, {148, 137}, {156, 137},
56 {164, 137}, {172, 125}, {172, 117}, {172, 109}, {172, 101}, {172, 93},
57 {172, 85}, {180, 85}, {180, 77}, {180, 69}, {180, 61}, {180, 53},
58 {172, 53}, {172, 61}, {172, 69}, {172, 77}, {164, 81}, {148, 85},
59 {124, 85}, {124, 93}, {124, 109}, {124, 125}, {124, 117}, {124, 101},
60 {104, 89}, {104, 81}, {104, 73}, {104, 65}, {104, 49}, {104, 41},
61 {104, 33}, {104, 25}, {104, 17}, {92, 9}, {80, 9}, {72, 9},
62 {64, 21}, {72, 25}, {80, 25}, {80, 25}, {80, 41}, {88, 49},
63 {104, 57}, {124, 69}, {124, 77}, {132, 81}, {140, 65}, {132, 61},
64 {124, 61}, {124, 53}, {124, 45}, {124, 37}, {124, 29}, {132, 21},
65 {124, 21}, {120, 9}, {128, 9}, {136, 9}, {148, 9}, {162, 9},
66 {156, 25}, {172, 21}, {180, 21}, {180, 29}, {172, 29}, {172, 37},
67 {172, 45}, {180, 45}, {180, 37}, {188, 41}, {196, 49}, {204, 57},
68 {212, 65}, {220, 73}, {228, 69}, {228, 77}, {236, 77}, {236, 69},
69 {236, 61}, {228, 61}, {228, 53}, {236, 53}, {236, 45}, {228, 45},
70 {228, 37}, {236, 37}, {236, 29}, {228, 29}, {228, 21}, {236, 21},
71 {252, 21}, {260, 29}, {260, 37}, {260, 45}, {260, 53}, {260, 61},
72 {260, 69}, {260, 77}, {276, 77}, {276, 69}, {276, 61}, {276, 53},
73 {284, 53}, {284, 61}, {284, 69}, {284, 77}, {284, 85}, {284, 93},
74 {284, 101}, {288, 109}, {280, 109}, {276, 101}, {276, 93}, {276, 85},
75 {268, 97}, {260, 109}, {252, 101}, {260, 93}, {260, 85}, {236, 85},
76 {228, 85}, {228, 93}, {236, 93}, {236, 101}, {228, 101}, {228, 109},
77 {228, 117}, {228, 125}, {220, 125}, {212, 117}, {204, 109}, {196, 101},
78 {188, 93}, {180, 93}, {180, 101}, {180, 109}, {180, 117}, {180, 125},
79 {196, 145}, {204, 145}, {212, 145}, {220, 145}, {228, 145}, {236, 145},
80 {246, 141}, {252, 125}, {260, 129}, {280, 133},
81 };
82 const int num_vehicles = 1;
83 const RoutingIndexManager::NodeIndex depot{0};
84};
85// [END data_model]
86
87// [START distance_matrix]
88// @brief Generate distance matrix.
89std::vector<std::vector<int64_t>> ComputeEuclideanDistanceMatrix(
90 const std::vector<std::vector<int>>& locations) {
91 std::vector<std::vector<int64_t>> distances =
92 std::vector<std::vector<int64_t>>(
93 locations.size(), std::vector<int64_t>(locations.size(), int64_t{0}));
94 for (int from_node = 0; from_node < locations.size(); from_node++) {
95 for (int to_node = 0; to_node < locations.size(); to_node++) {
96 if (from_node != to_node)
97 distances[from_node][to_node] = static_cast<int64_t>(
98 std::hypot((locations[to_node][0] - locations[from_node][0]),
99 (locations[to_node][1] - locations[from_node][1])));
100 }
101 }
102 return distances;
103}
104// [END distance_matrix]
105
106// [START solution_printer]
111void PrintSolution(const RoutingIndexManager& manager,
112 const RoutingModel& routing, const Assignment& solution) {
113 LOG(INFO) << "Objective: " << solution.ObjectiveValue();
114 // Inspect solution.
115 int64_t index = routing.Start(0);
116 LOG(INFO) << "Route:";
117 int64_t distance{0};
118 std::stringstream route;
119 while (!routing.IsEnd(index)) {
120 route << manager.IndexToNode(index).value() << " -> ";
121 const int64_t previous_index = index;
122 index = solution.Value(routing.NextVar(index));
123 distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{0});
124 }
125 LOG(INFO) << route.str() << manager.IndexToNode(index).value();
126 LOG(INFO) << "Route distance: " << distance << "mm";
127 LOG(INFO) << "";
128 LOG(INFO) << "Advanced usage:";
129 LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
130}
131// [END solution_printer]
132
133void Tsp() {
134 // Instantiate the data problem.
135 // [START data]
136 DataModel data;
137 // [END data]
138
139 // Create Routing Index Manager
140 // [START index_manager]
141 RoutingIndexManager manager(data.locations.size(), data.num_vehicles,
142 data.depot);
143 // [END index_manager]
144
145 // Create Routing Model.
146 // [START routing_model]
147 RoutingModel routing(manager);
148 // [END routing_model]
149
150 // [START transit_callback]
151 const auto distance_matrix = ComputeEuclideanDistanceMatrix(data.locations);
152 const int transit_callback_index = routing.RegisterTransitCallback(
153 [&distance_matrix, &manager](const int64_t from_index,
154 const int64_t to_index) -> int64_t {
155 // Convert from routing variable Index to distance matrix NodeIndex.
156 const int from_node = manager.IndexToNode(from_index).value();
157 const int to_node = manager.IndexToNode(to_index).value();
158 return distance_matrix[from_node][to_node];
159 });
160 // [END transit_callback]
161
162 // Define cost of each arc.
163 // [START arc_cost]
164 routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);
165 // [END arc_cost]
166
167 // Setting first solution heuristic.
168 // [START parameters]
169 RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
170 searchParameters.set_first_solution_strategy(
171 FirstSolutionStrategy::PATH_CHEAPEST_ARC);
172 // [END parameters]
173
174 // Solve the problem.
175 // [START solve]
176 const Assignment* solution = routing.SolveWithParameters(searchParameters);
177 // [END solve]
178
179 // Print solution on console.
180 // [START print_solution]
181 PrintSolution(manager, routing, *solution);
182 // [END print_solution]
183}
184} // namespace operations_research
185
186int main(int /*argc*/, char* /*argv*/[]) {
187 operations_research::Tsp();
188 return EXIT_SUCCESS;
189}
190// [END program]
operations_research::FirstSolutionStrategy::PATH_CHEAPEST_ARC
static constexpr Value PATH_CHEAPEST_ARC
Definition routing_enums.pb.h:670
constraint_solver.h
main
int main(int argc, char **argv)
Definition fz.cc:218
operations_research
OR-Tools root namespace.
Definition binary_indexed_tree.h:21
operations_research::solution
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
operations_research::DefaultRoutingSearchParameters
RoutingSearchParameters DefaultRoutingSearchParameters()
Definition routing_parameters.cc:263
routing.h
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
routing_enums.pb.h
routing_index_manager.h
routing_parameters.h