Phần này trình bày ví dụ về cách giải quyết Vấn đề về nhân viên bán hàng du lịch (TSP) đối với những vị trí được hiển thị trên bản đồ bên dưới.
Các phần sau trình bày các chương trình bằng Python, C++, Java và C# giúp giải quyết TSP bằng OR-Tools
Tạo dữ liệu
Đoạn mã dưới đây sẽ tạo dữ liệu cho vấn đề này.
Python
def create_data_model():
"""Stores the data for the problem."""
data = {}
data["distance_matrix"] = [
[0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],
[2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],
[713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],
[1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],
[1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],
[1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],
[2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],
[213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],
[2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],
[875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],
[1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],
[2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],
[1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0],
]
data["num_vehicles"] = 1
data["depot"] = 0
return data
C++
struct DataModel {
const std::vector<std::vector<int64_t>> distance_matrix{
{0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972},
{2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579},
{713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260},
{1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987},
{1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371},
{1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999},
{2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701},
{213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099},
{2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600},
{875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162},
{1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200},
{2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504},
{1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0},
};
const int num_vehicles = 1;
const RoutingIndexManager::NodeIndex depot{0};
};
Java
static class DataModel {
public final long[][] distanceMatrix = {
{0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972},
{2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579},
{713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260},
{1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987},
{1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371},
{1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999},
{2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701},
{213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099},
{2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600},
{875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162},
{1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200},
{2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504},
{1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0},
};
public final int vehicleNumber = 1;
public final int depot = 0;
}
C#
class DataModel
{
public long[,] DistanceMatrix = {
{ 0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972 },
{ 2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579 },
{ 713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260 },
{ 1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987 },
{ 1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371 },
{ 1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999 },
{ 2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701 },
{ 213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099 },
{ 2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600 },
{ 875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162 },
{ 1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200 },
{ 2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504 },
{ 1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0 },
};
public int VehicleNumber = 1;
public int Depot = 0;
};
Ma trận khoảng cách là một mảng có i, mục nhập j là khoảng cách từ vị trí i đến vị trí j tính bằng dặm, trong đó chỉ mục mảng tương ứng với các vị trí theo thứ tự sau:
0. New York - 1. Los Angeles - 2. Chicago - 3. Minneapolis - 4. Denver - 5. Dallas
- 6. Seattle - 7. Boston - 8. San Francisco - 9. St. Louis - 10. Houston - 11. Phoenix - 12. Salt Lake City
Các dữ liệu này cũng bao gồm:
- Số lượng xe gặp sự cố, là 1 xe vì đây là TSP. (Đối với vấn đề về định tuyến xe (VRP), số lượng xe có thể lớn hơn 1.)
- Kho hàng: vị trí bắt đầu và kết thúc của tuyến đường. Trong trường hợp này, kho hàng là 0, tương ứng với New York.
Các cách khác để tạo ma trận khoảng cách
Trong ví dụ này, ma trận khoảng cách được xác định rõ ràng trong chương trình. Bạn cũng có thể sử dụng hàm để tính khoảng cách giữa các vị trí: ví dụ: công thức Euclidean cho khoảng cách giữa các điểm trong mặt phẳng. Tuy nhiên, việc tính toán trước tất cả khoảng cách giữa các vị trí và lưu trữ trong một ma trận sẽ hiệu quả hơn, thay vì tính toán chúng trong thời gian chạy. Hãy xem Ví dụ: khoan bảng mạch để tìm hiểu ví dụ về cách tạo ma trận khoảng cách theo cách này.
Một cách khác là sử dụng API ma trận khoảng cách Google Maps để tạo động ma trận khoảng cách (hoặc thời gian đi lại) cho một vấn đề về định tuyến.
Tạo mô hình định tuyến
Mã sau trong phần chính của chương trình sẽ tạo trình quản lý chỉ mục (manager) và mô hình định tuyến (routing). Phương thức manager.IndexToNode chuyển đổi các chỉ mục nội bộ của trình giải quyết (bạn có thể bỏ qua một cách an toàn) các số cho vị trí. Số vị trí tương ứng với các chỉ mục của ma trận khoảng cách.
Python
data = create_data_model()
manager = pywrapcp.RoutingIndexManager(
len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
)
routing = pywrapcp.RoutingModel(manager)
C++
DataModel data;
RoutingIndexManager manager(data.distance_matrix.size(), data.num_vehicles,
data.depot);
RoutingModel routing(manager);
Java
final DataModel data = new DataModel();
RoutingIndexManager manager =
new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);
RoutingModel routing = new RoutingModel(manager);
C#
DataModel data = new DataModel();
RoutingIndexManager manager =
new RoutingIndexManager(data.DistanceMatrix.GetLength(0), data.VehicleNumber, data.Depot);
RoutingModel routing = new RoutingModel(manager);
Dữ liệu đầu vào cho RoutingIndexManager là:
- Số hàng của ma trận khoảng cách, là số lượng vị trí (bao gồm cả kho hàng).
- Số lượng xe gặp sự cố.
- Nút tương ứng với kho lưu trữ.
Tạo lệnh gọi lại khoảng cách
Để sử dụng trình giải mã định tuyến, bạn cần tạo một lệnh gọi lại khoảng cách (hoặc phương tiện): một hàm nhận bất kỳ cặp vị trí nào và trả về khoảng cách giữa chúng. Cách dễ nhất để làm việc này là sử dụng ma trận khoảng cách.
Hàm sau đây tạo lệnh gọi lại và đăng ký lệnh gọi lại với trình giải mã dưới dạng
transit_callback_index.
Python
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["distance_matrix"][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
C++
const int transit_callback_index = routing.RegisterTransitCallback(
[&data, &manager](const int64_t from_index,
const int64_t to_index) -> int64_t {
// Convert from routing variable Index to distance matrix NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
const int to_node = manager.IndexToNode(to_index).value();
return data.distance_matrix[from_node][to_node];
});
Java
final int transitCallbackIndex =
routing.registerTransitCallback((long fromIndex, long toIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return data.distanceMatrix[fromNode][toNode];
});
C#
int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
{
// Convert from routing variable Index to
// distance matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return data.DistanceMatrix[fromNode, toNode];
});
The callback accepts two indices, from_index and to_index, and returns the
corresponding entry of the distance matrix.
Set the cost of travel
The arc cost evaluator tells the solver how to calculate the cost of travel between any two locations — in other words, the cost of the edge (or arc) joining them in the graph for the problem. The following code sets the arc cost evaluator.
Python
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
C++
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);
Java
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
C#
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
Trong ví dụ này, trình đánh giá chi phí arc là transit_callback_index, là tham chiếu nội bộ của trình giải toán đến lệnh gọi lại khoảng cách. Điều này có nghĩa là chi phí đi lại giữa hai địa điểm bất kỳ chỉ là khoảng cách giữa hai địa điểm đó.
Tuy nhiên, nhìn chung chi phí cũng có thể liên quan đến các yếu tố khác.
Bạn cũng có thể xác định nhiều người đánh giá chi phí vòng cung phụ thuộc vào xe nào đang di chuyển giữa các vị trí, bằng cách sử dụng phương thức routing.SetArcCostEvaluatorOfVehicle().
Ví dụ: nếu các xe có tốc độ khác nhau, bạn có thể xác định chi phí di chuyển giữa các vị trí bằng khoảng cách chia cho tốc độ của xe, hay nói cách khác là thời gian di chuyển.
Đặt các tham số tìm kiếm
Mã sau đây đặt tham số tìm kiếm mặc định và phương thức phỏng đoán để tìm giải pháp đầu tiên:
Python
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
C++
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
searchParameters.set_first_solution_strategy(
FirstSolutionStrategy::PATH_CHEAPEST_ARC);
Java
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();
C#
RoutingSearchParameters searchParameters =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
Mã này đặt chiến lược giải pháp đầu tiên thành PATH_CHEAPEST_ARC, tạo tuyến đường ban đầu cho trình giải toán bằng cách thêm các cạnh có trọng số nhỏ nhất không dẫn đến nút đã truy cập trước đó (ngoài kho lưu trữ). Để biết các
tuỳ chọn khác, hãy xem
Chiến lược giải pháp đầu tiên.
Thêm máy in giải pháp
Dưới đây là hàm hiển thị lời giải của trình giải. Hàm này trích xuất tuyến đường từ giải pháp và in ra bảng điều khiển.
Python
def print_solution(manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()} miles")
index = routing.Start(0)
plan_output = "Route for vehicle 0:\n"
route_distance = 0
while not routing.IsEnd(index):
plan_output += f" {manager.IndexToNode(index)} ->"
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
plan_output += f" {manager.IndexToNode(index)}\n"
print(plan_output)
plan_output += f"Route distance: {route_distance}miles\n"
C++
//! @brief Print the solution.
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const RoutingIndexManager& manager,
const RoutingModel& routing, const Assignment& solution) {
// Inspect solution.
LOG(INFO) << "Objective: " << solution.ObjectiveValue() << " miles";
int64_t index = routing.Start(0);
LOG(INFO) << "Route:";
int64_t distance{0};
std::stringstream route;
while (!routing.IsEnd(index)) {
route << manager.IndexToNode(index).value() << " -> ";
const int64_t previous_index = index;
index = solution.Value(routing.NextVar(index));
distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{0});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Route distance: " << distance << "miles";
LOG(INFO) << "";
LOG(INFO) << "Advanced usage:";
LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}
Java
/// @brief Print the solution.
static void printSolution(
RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
// Solution cost.
logger.info("Objective: " + solution.objectiveValue() + "miles");
// Inspect solution.
logger.info("Route:");
long routeDistance = 0;
String route = "";
long index = routing.start(0);
while (!routing.isEnd(index)) {
route += manager.indexToNode(index) + " -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, 0);
}
route += manager.indexToNode(routing.end(0));
logger.info(route);
logger.info("Route distance: " + routeDistance + "miles");
}
C#
/// <summary>
/// Print the solution.
/// </summary>
static void PrintSolution(in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution)
{
Console.WriteLine("Objective: {0} miles", solution.ObjectiveValue());
// Inspect solution.
Console.WriteLine("Route:");
long routeDistance = 0;
var index = routing.Start(0);
while (routing.IsEnd(index) == false)
{
Console.Write("{0} -> ", manager.IndexToNode((int)index));
var previousIndex = index;
index = solution.Value(routing.NextVar(index));
routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode((int)index));
Console.WriteLine("Route distance: {0}miles", routeDistance);
}
Hàm này hiển thị tuyến đường tối ưu và khoảng cách từ tuyến đường đó, do ObjectiveValue() cung cấp.
Giải và in giải pháp
Cuối cùng, bạn có thể gọi trình giải và in giải pháp:
Python
solution = routing.SolveWithParameters(search_parameters)
if solution:
print_solution(manager, routing, solution)
C++
const Assignment* solution = routing.SolveWithParameters(searchParameters); PrintSolution(manager, routing, *solution);
Java
Assignment solution = routing.solveWithParameters(searchParameters); printSolution(routing, manager, solution);
C#
Assignment solution = routing.SolveWithParameters(searchParameters); PrintSolution(routing, manager, solution);
Thao tác này sẽ trả về giải pháp và hiển thị tuyến đường tối ưu.
Chạy chương trình
Khi bạn chạy các chương trình, chúng sẽ hiển thị kết quả sau.
Objective: 7293 miles Route for vehicle 0: 0 -> 7 -> 2 -> 3 -> 4 -> 12 -> 6 -> 8 -> 1 -> 11 -> 10 -> 5 -> 9 -> 0
Trong ví dụ này, chỉ có một tuyến đường vì đó là tuyến đường TSP. Tuy nhiên, trong các vấn đề chung về việc định tuyến xe, giải pháp này sẽ chứa nhiều tuyến.
Lưu các tuyến đường vào một danh sách hoặc mảng
Thay vì in trực tiếp giải pháp, bạn có thể lưu tuyến (hoặc các tuyến cho VRP) vào một danh sách hoặc mảng. Điều này có lợi thế là làm cho các tuyến đường có sẵn trong trường hợp bạn muốn làm điều gì đó với chúng sau này. Ví dụ: bạn có thể chạy chương trình này nhiều lần với nhiều tham số và lưu các tuyến trong giải pháp được trả về vào một tệp để so sánh.
Các hàm sau đây lưu các tuyến trong giải pháp vào mọi VRP (có thể với nhiều xe) dưới dạng một danh sách (Python) hoặc một mảng (C++).
Python
def get_routes(solution, routing, manager):
"""Get vehicle routes from a solution and store them in an array."""
# Get vehicle routes and store them in a two dimensional array whose
# i,j entry is the jth location visited by vehicle i along its route.
routes = []
for route_nbr in range(routing.vehicles()):
index = routing.Start(route_nbr)
route = [manager.IndexToNode(index)]
while not routing.IsEnd(index):
index = solution.Value(routing.NextVar(index))
route.append(manager.IndexToNode(index))
routes.append(route)
return routes
C++
std::vector<std::vector<int>> GetRoutes(const Assignment& solution,
const RoutingModel& routing,
const RoutingIndexManager& manager) {
// Get vehicle routes and store them in a two dimensional array, whose
// i, j entry is the node for the jth visit of vehicle i.
std::vector<std::vector<int>> routes(manager.num_vehicles());
// Get routes.
for (int vehicle_id = 0; vehicle_id < manager.num_vehicles(); ++vehicle_id) {
int64_t index = routing.Start(vehicle_id);
routes[vehicle_id].push_back(manager.IndexToNode(index).value());
while (!routing.IsEnd(index)) {
index = solution.Value(routing.NextVar(index));
routes[vehicle_id].push_back(manager.IndexToNode(index).value());
}
}
return routes;
}
Bạn có thể sử dụng các hàm này để lấy tuyến đường trong mọi ví dụ về VRP trong mục Định tuyến.
Mã sau đây cho thấy các tuyến đường.
Python
routes = get_routes(solution, routing, manager)
# Display the routes.
for i, route in enumerate(routes):
print('Route', i, route)
C++
const std::vector⟨std::vector⟨int⟩⟩
routes = GetRoutes(*solution,
routing,
manager);
// Display the routes.
for (int vehicle_id = 0; vehicle_id < routes.size(); ++vehicle_id) {
LOG(INFO) << "Route " << vehicle_id;
for (int j = 1; j < routes[vehicle_id].size(); ++j) {
LOG(INFO) << routes[vehicle_id][j];
}
}
Trong ví dụ hiện tại, mã này trả về tuyến đường sau:
Route 0 [0, 7, 2, 3, 4, 12, 6, 8, 1, 11, 10, 5, 9, 0]
Như một bài tập thể dục, hãy sửa đổi mã ở trên để định dạng đầu ra giống như máy in giải pháp cho chương trình.
Hoàn thành chương trình
Chương trình TSP hoàn chỉnh được trình bày bên dưới.
Python
"""Simple Travelling Salesperson Problem (TSP) between cities."""
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""Stores the data for the problem."""
data = {}
data["distance_matrix"] = [
[0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],
[2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],
[713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],
[1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],
[1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],
[1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],
[2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],
[213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],
[2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],
[875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],
[1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],
[2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],
[1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0],
]
data["num_vehicles"] = 1
data["depot"] = 0
return data
def print_solution(manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()} miles")
index = routing.Start(0)
plan_output = "Route for vehicle 0:\n"
route_distance = 0
while not routing.IsEnd(index):
plan_output += f" {manager.IndexToNode(index)} ->"
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
plan_output += f" {manager.IndexToNode(index)}\n"
print(plan_output)
plan_output += f"Route distance: {route_distance}miles\n"
def main():
"""Entry point of the program."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["distance_matrix"][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(manager, routing, solution)
if __name__ == "__main__":
main()
C++
#include <cmath>
#include <cstdint>
#include <sstream>
#include <vector>
#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_index_manager.h"
#include "ortools/constraint_solver/routing_parameters.h"
namespace operations_research {
struct DataModel {
const std::vector<std::vector<int64_t>> distance_matrix{
{0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972},
{2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579},
{713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260},
{1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987},
{1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371},
{1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999},
{2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701},
{213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099},
{2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600},
{875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162},
{1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200},
{2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504},
{1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0},
};
const int num_vehicles = 1;
const RoutingIndexManager::NodeIndex depot{0};
};
//! @brief Print the solution.
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const RoutingIndexManager& manager,
const RoutingModel& routing, const Assignment& solution) {
// Inspect solution.
LOG(INFO) << "Objective: " << solution.ObjectiveValue() << " miles";
int64_t index = routing.Start(0);
LOG(INFO) << "Route:";
int64_t distance{0};
std::stringstream route;
while (!routing.IsEnd(index)) {
route << manager.IndexToNode(index).value() << " -> ";
const int64_t previous_index = index;
index = solution.Value(routing.NextVar(index));
distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{0});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Route distance: " << distance << "miles";
LOG(INFO) << "";
LOG(INFO) << "Advanced usage:";
LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}
void Tsp() {
// Instantiate the data problem.
DataModel data;
// Create Routing Index Manager
RoutingIndexManager manager(data.distance_matrix.size(), data.num_vehicles,
data.depot);
// Create Routing Model.
RoutingModel routing(manager);
const int transit_callback_index = routing.RegisterTransitCallback(
[&data, &manager](const int64_t from_index,
const int64_t to_index) -> int64_t {
// Convert from routing variable Index to distance matrix NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
const int to_node = manager.IndexToNode(to_index).value();
return data.distance_matrix[from_node][to_node];
});
// Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);
// Setting first solution heuristic.
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
searchParameters.set_first_solution_strategy(
FirstSolutionStrategy::PATH_CHEAPEST_ARC);
// Solve the problem.
const Assignment* solution = routing.SolveWithParameters(searchParameters);
// Print solution on console.
PrintSolution(manager, routing, *solution);
}
} // namespace operations_research
int main(int /*argc*/, char* /*argv*/[]) {
operations_research::Tsp();
return EXIT_SUCCESS;
}
Java
package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.Assignment;
import com.google.ortools.constraintsolver.FirstSolutionStrategy;
import com.google.ortools.constraintsolver.RoutingIndexManager;
import com.google.ortools.constraintsolver.RoutingModel;
import com.google.ortools.constraintsolver.RoutingSearchParameters;
import com.google.ortools.constraintsolver.main;
import java.util.logging.Logger;
/** Minimal TSP using distance matrix. */
public class TspCities {
private static final Logger logger = Logger.getLogger(TspCities.class.getName());
static class DataModel {
public final long[][] distanceMatrix = {
{0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972},
{2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579},
{713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260},
{1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987},
{1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371},
{1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999},
{2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701},
{213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099},
{2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600},
{875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162},
{1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200},
{2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504},
{1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0},
};
public final int vehicleNumber = 1;
public final int depot = 0;
}
/// @brief Print the solution.
static void printSolution(
RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
// Solution cost.
logger.info("Objective: " + solution.objectiveValue() + "miles");
// Inspect solution.
logger.info("Route:");
long routeDistance = 0;
String route = "";
long index = routing.start(0);
while (!routing.isEnd(index)) {
route += manager.indexToNode(index) + " -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, 0);
}
route += manager.indexToNode(routing.end(0));
logger.info(route);
logger.info("Route distance: " + routeDistance + "miles");
}
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// Instantiate the data problem.
final DataModel data = new DataModel();
// Create Routing Index Manager
RoutingIndexManager manager =
new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);
// Create Routing Model.
RoutingModel routing = new RoutingModel(manager);
// Create and register a transit callback.
final int transitCallbackIndex =
routing.registerTransitCallback((long fromIndex, long toIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return data.distanceMatrix[fromNode][toNode];
});
// Define cost of each arc.
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();
// Solve the problem.
Assignment solution = routing.solveWithParameters(searchParameters);
// Print solution on console.
printSolution(routing, manager, solution);
}
}
C#
using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;
/// <summary>
/// Minimal TSP using distance matrix.
/// </summary>
public class TspCities
{
class DataModel
{
public long[,] DistanceMatrix = {
{ 0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972 },
{ 2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579 },
{ 713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260 },
{ 1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987 },
{ 1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371 },
{ 1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999 },
{ 2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701 },
{ 213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099 },
{ 2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600 },
{ 875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162 },
{ 1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200 },
{ 2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504 },
{ 1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0 },
};
public int VehicleNumber = 1;
public int Depot = 0;
};
/// <summary>
/// Print the solution.
/// </summary>
static void PrintSolution(in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution)
{
Console.WriteLine("Objective: {0} miles", solution.ObjectiveValue());
// Inspect solution.
Console.WriteLine("Route:");
long routeDistance = 0;
var index = routing.Start(0);
while (routing.IsEnd(index) == false)
{
Console.Write("{0} -> ", manager.IndexToNode((int)index));
var previousIndex = index;
index = solution.Value(routing.NextVar(index));
routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode((int)index));
Console.WriteLine("Route distance: {0}miles", routeDistance);
}
public static void Main(String[] args)
{
// Instantiate the data problem.
DataModel data = new DataModel();
// Create Routing Index Manager
RoutingIndexManager manager =
new RoutingIndexManager(data.DistanceMatrix.GetLength(0), data.VehicleNumber, data.Depot);
// Create Routing Model.
RoutingModel routing = new RoutingModel(manager);
int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
{
// Convert from routing variable Index to
// distance matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return data.DistanceMatrix[fromNode, toNode];
});
// Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
// Solve the problem.
Assignment solution = routing.SolveWithParameters(searchParameters);
// Print solution on console.
PrintSolution(routing, manager, solution);
}
}
Ví dụ: khoan bảng mạch
Ví dụ tiếp theo liên quan đến việc khoan lỗ trên bảng mạch bằng máy khoan tự động. Vấn đề là tìm tuyến đường ngắn nhất để máy khoan đưa lên bảng để khoan tất cả các lỗ cần thiết. Ví dụ này được lấy từ TSPLIB, một thư viện về các vấn đề TSP.
Dưới đây là biểu đồ tán xạ của các vị trí cho lỗ:
Các phần sau đây trình bày các chương trình tìm giải pháp tốt cho sự cố bảng mạch, sử dụng thông số tìm kiếm mặc định của trình giải toán. Sau đó, chúng tôi sẽ hướng dẫn bạn cách tìm ra giải pháp tốt hơn bằng cách thay đổi chiến lược tìm kiếm.
Tạo dữ liệu
Dữ liệu của vấn đề bao gồm 280 điểm trong mặt phẳng, hiển thị trong biểu đồ tán xạ ở trên. Lập trình này sẽ tạo dữ liệu trong một loạt các cặp được sắp xếp theo thứ tự tương ứng với các điểm trong mặt phẳng, như minh hoạ dưới đây.
Python
def create_data_model():
"""Stores the data for the problem."""
data = {}
# Locations in block units
data["locations"] = [
# fmt: off
(288, 149), (288, 129), (270, 133), (256, 141), (256, 157), (246, 157),
(236, 169), (228, 169), (228, 161), (220, 169), (212, 169), (204, 169),
(196, 169), (188, 169), (196, 161), (188, 145), (172, 145), (164, 145),
(156, 145), (148, 145), (140, 145), (148, 169), (164, 169), (172, 169),
(156, 169), (140, 169), (132, 169), (124, 169), (116, 161), (104, 153),
(104, 161), (104, 169), (90, 165), (80, 157), (64, 157), (64, 165),
(56, 169), (56, 161), (56, 153), (56, 145), (56, 137), (56, 129),
(56, 121), (40, 121), (40, 129), (40, 137), (40, 145), (40, 153),
(40, 161), (40, 169), (32, 169), (32, 161), (32, 153), (32, 145),
(32, 137), (32, 129), (32, 121), (32, 113), (40, 113), (56, 113),
(56, 105), (48, 99), (40, 99), (32, 97), (32, 89), (24, 89),
(16, 97), (16, 109), (8, 109), (8, 97), (8, 89), (8, 81),
(8, 73), (8, 65), (8, 57), (16, 57), (8, 49), (8, 41),
(24, 45), (32, 41), (32, 49), (32, 57), (32, 65), (32, 73),
(32, 81), (40, 83), (40, 73), (40, 63), (40, 51), (44, 43),
(44, 35), (44, 27), (32, 25), (24, 25), (16, 25), (16, 17),
(24, 17), (32, 17), (44, 11), (56, 9), (56, 17), (56, 25),
(56, 33), (56, 41), (64, 41), (72, 41), (72, 49), (56, 49),
(48, 51), (56, 57), (56, 65), (48, 63), (48, 73), (56, 73),
(56, 81), (48, 83), (56, 89), (56, 97), (104, 97), (104, 105),
(104, 113), (104, 121), (104, 129), (104, 137), (104, 145), (116, 145),
(124, 145), (132, 145), (132, 137), (140, 137), (148, 137), (156, 137),
(164, 137), (172, 125), (172, 117), (172, 109), (172, 101), (172, 93),
(172, 85), (180, 85), (180, 77), (180, 69), (180, 61), (180, 53),
(172, 53), (172, 61), (172, 69), (172, 77), (164, 81), (148, 85),
(124, 85), (124, 93), (124, 109), (124, 125), (124, 117), (124, 101),
(104, 89), (104, 81), (104, 73), (104, 65), (104, 49), (104, 41),
(104, 33), (104, 25), (104, 17), (92, 9), (80, 9), (72, 9),
(64, 21), (72, 25), (80, 25), (80, 25), (80, 41), (88, 49),
(104, 57), (124, 69), (124, 77), (132, 81), (140, 65), (132, 61),
(124, 61), (124, 53), (124, 45), (124, 37), (124, 29), (132, 21),
(124, 21), (120, 9), (128, 9), (136, 9), (148, 9), (162, 9),
(156, 25), (172, 21), (180, 21), (180, 29), (172, 29), (172, 37),
(172, 45), (180, 45), (180, 37), (188, 41), (196, 49), (204, 57),
(212, 65), (220, 73), (228, 69), (228, 77), (236, 77), (236, 69),
(236, 61), (228, 61), (228, 53), (236, 53), (236, 45), (228, 45),
(228, 37), (236, 37), (236, 29), (228, 29), (228, 21), (236, 21),
(252, 21), (260, 29), (260, 37), (260, 45), (260, 53), (260, 61),
(260, 69), (260, 77), (276, 77), (276, 69), (276, 61), (276, 53),
(284, 53), (284, 61), (284, 69), (284, 77), (284, 85), (284, 93),
(284, 101), (288, 109), (280, 109), (276, 101), (276, 93), (276, 85),
(268, 97), (260, 109), (252, 101), (260, 93), (260, 85), (236, 85),
(228, 85), (228, 93), (236, 93), (236, 101), (228, 101), (228, 109),
(228, 117), (228, 125), (220, 125), (212, 117), (204, 109), (196, 101),
(188, 93), (180, 93), (180, 101), (180, 109), (180, 117), (180, 125),
(196, 145), (204, 145), (212, 145), (220, 145), (228, 145), (236, 145),
(246, 141), (252, 125), (260, 129), (280, 133)
# fmt: on
]
data["num_vehicles"] = 1
data["depot"] = 0
return data
C++
struct DataModel {
const std::vector<std::vector<int>> locations{
{288, 149}, {288, 129}, {270, 133}, {256, 141}, {256, 157}, {246, 157},
{236, 169}, {228, 169}, {228, 161}, {220, 169}, {212, 169}, {204, 169},
{196, 169}, {188, 169}, {196, 161}, {188, 145}, {172, 145}, {164, 145},
{156, 145}, {148, 145}, {140, 145}, {148, 169}, {164, 169}, {172, 169},
{156, 169}, {140, 169}, {132, 169}, {124, 169}, {116, 161}, {104, 153},
{104, 161}, {104, 169}, {90, 165}, {80, 157}, {64, 157}, {64, 165},
{56, 169}, {56, 161}, {56, 153}, {56, 145}, {56, 137}, {56, 129},
{56, 121}, {40, 121}, {40, 129}, {40, 137}, {40, 145}, {40, 153},
{40, 161}, {40, 169}, {32, 169}, {32, 161}, {32, 153}, {32, 145},
{32, 137}, {32, 129}, {32, 121}, {32, 113}, {40, 113}, {56, 113},
{56, 105}, {48, 99}, {40, 99}, {32, 97}, {32, 89}, {24, 89},
{16, 97}, {16, 109}, {8, 109}, {8, 97}, {8, 89}, {8, 81},
{8, 73}, {8, 65}, {8, 57}, {16, 57}, {8, 49}, {8, 41},
{24, 45}, {32, 41}, {32, 49}, {32, 57}, {32, 65}, {32, 73},
{32, 81}, {40, 83}, {40, 73}, {40, 63}, {40, 51}, {44, 43},
{44, 35}, {44, 27}, {32, 25}, {24, 25}, {16, 25}, {16, 17},
{24, 17}, {32, 17}, {44, 11}, {56, 9}, {56, 17}, {56, 25},
{56, 33}, {56, 41}, {64, 41}, {72, 41}, {72, 49}, {56, 49},
{48, 51}, {56, 57}, {56, 65}, {48, 63}, {48, 73}, {56, 73},
{56, 81}, {48, 83}, {56, 89}, {56, 97}, {104, 97}, {104, 105},
{104, 113}, {104, 121}, {104, 129}, {104, 137}, {104, 145}, {116, 145},
{124, 145}, {132, 145}, {132, 137}, {140, 137}, {148, 137}, {156, 137},
{164, 137}, {172, 125}, {172, 117}, {172, 109}, {172, 101}, {172, 93},
{172, 85}, {180, 85}, {180, 77}, {180, 69}, {180, 61}, {180, 53},
{172, 53}, {172, 61}, {172, 69}, {172, 77}, {164, 81}, {148, 85},
{124, 85}, {124, 93}, {124, 109}, {124, 125}, {124, 117}, {124, 101},
{104, 89}, {104, 81}, {104, 73}, {104, 65}, {104, 49}, {104, 41},
{104, 33}, {104, 25}, {104, 17}, {92, 9}, {80, 9}, {72, 9},
{64, 21}, {72, 25}, {80, 25}, {80, 25}, {80, 41}, {88, 49},
{104, 57}, {124, 69}, {124, 77}, {132, 81}, {140, 65}, {132, 61},
{124, 61}, {124, 53}, {124, 45}, {124, 37}, {124, 29}, {132, 21},
{124, 21}, {120, 9}, {128, 9}, {136, 9}, {148, 9}, {162, 9},
{156, 25}, {172, 21}, {180, 21}, {180, 29}, {172, 29}, {172, 37},
{172, 45}, {180, 45}, {180, 37}, {188, 41}, {196, 49}, {204, 57},
{212, 65}, {220, 73}, {228, 69}, {228, 77}, {236, 77}, {236, 69},
{236, 61}, {228, 61}, {228, 53}, {236, 53}, {236, 45}, {228, 45},
{228, 37}, {236, 37}, {236, 29}, {228, 29}, {228, 21}, {236, 21},
{252, 21}, {260, 29}, {260, 37}, {260, 45}, {260, 53}, {260, 61},
{260, 69}, {260, 77}, {276, 77}, {276, 69}, {276, 61}, {276, 53},
{284, 53}, {284, 61}, {284, 69}, {284, 77}, {284, 85}, {284, 93},
{284, 101}, {288, 109}, {280, 109}, {276, 101}, {276, 93}, {276, 85},
{268, 97}, {260, 109}, {252, 101}, {260, 93}, {260, 85}, {236, 85},
{228, 85}, {228, 93}, {236, 93}, {236, 101}, {228, 101}, {228, 109},
{228, 117}, {228, 125}, {220, 125}, {212, 117}, {204, 109}, {196, 101},
{188, 93}, {180, 93}, {180, 101}, {180, 109}, {180, 117}, {180, 125},
{196, 145}, {204, 145}, {212, 145}, {220, 145}, {228, 145}, {236, 145},
{246, 141}, {252, 125}, {260, 129}, {280, 133},
};
const int num_vehicles = 1;
const RoutingIndexManager::NodeIndex depot{0};
};
Java
static class DataModel {
public final int[][] locations = {{288, 149}, {288, 129}, {270, 133}, {256, 141}, {256, 157},
{246, 157}, {236, 169}, {228, 169}, {228, 161}, {220, 169}, {212, 169}, {204, 169},
{196, 169}, {188, 169}, {196, 161}, {188, 145}, {172, 145}, {164, 145}, {156, 145},
{148, 145}, {140, 145}, {148, 169}, {164, 169}, {172, 169}, {156, 169}, {140, 169},
{132, 169}, {124, 169}, {116, 161}, {104, 153}, {104, 161}, {104, 169}, {90, 165},
{80, 157}, {64, 157}, {64, 165}, {56, 169}, {56, 161}, {56, 153}, {56, 145}, {56, 137},
{56, 129}, {56, 121}, {40, 121}, {40, 129}, {40, 137}, {40, 145}, {40, 153}, {40, 161},
{40, 169}, {32, 169}, {32, 161}, {32, 153}, {32, 145}, {32, 137}, {32, 129}, {32, 121},
{32, 113}, {40, 113}, {56, 113}, {56, 105}, {48, 99}, {40, 99}, {32, 97}, {32, 89},
{24, 89}, {16, 97}, {16, 109}, {8, 109}, {8, 97}, {8, 89}, {8, 81}, {8, 73}, {8, 65},
{8, 57}, {16, 57}, {8, 49}, {8, 41}, {24, 45}, {32, 41}, {32, 49}, {32, 57}, {32, 65},
{32, 73}, {32, 81}, {40, 83}, {40, 73}, {40, 63}, {40, 51}, {44, 43}, {44, 35}, {44, 27},
{32, 25}, {24, 25}, {16, 25}, {16, 17}, {24, 17}, {32, 17}, {44, 11}, {56, 9}, {56, 17},
{56, 25}, {56, 33}, {56, 41}, {64, 41}, {72, 41}, {72, 49}, {56, 49}, {48, 51}, {56, 57},
{56, 65}, {48, 63}, {48, 73}, {56, 73}, {56, 81}, {48, 83}, {56, 89}, {56, 97}, {104, 97},
{104, 105}, {104, 113}, {104, 121}, {104, 129}, {104, 137}, {104, 145}, {116, 145},
{124, 145}, {132, 145}, {132, 137}, {140, 137}, {148, 137}, {156, 137}, {164, 137},
{172, 125}, {172, 117}, {172, 109}, {172, 101}, {172, 93}, {172, 85}, {180, 85}, {180, 77},
{180, 69}, {180, 61}, {180, 53}, {172, 53}, {172, 61}, {172, 69}, {172, 77}, {164, 81},
{148, 85}, {124, 85}, {124, 93}, {124, 109}, {124, 125}, {124, 117}, {124, 101}, {104, 89},
{104, 81}, {104, 73}, {104, 65}, {104, 49}, {104, 41}, {104, 33}, {104, 25}, {104, 17},
{92, 9}, {80, 9}, {72, 9}, {64, 21}, {72, 25}, {80, 25}, {80, 25}, {80, 41}, {88, 49},
{104, 57}, {124, 69}, {124, 77}, {132, 81}, {140, 65}, {132, 61}, {124, 61}, {124, 53},
{124, 45}, {124, 37}, {124, 29}, {132, 21}, {124, 21}, {120, 9}, {128, 9}, {136, 9},
{148, 9}, {162, 9}, {156, 25}, {172, 21}, {180, 21}, {180, 29}, {172, 29}, {172, 37},
{172, 45}, {180, 45}, {180, 37}, {188, 41}, {196, 49}, {204, 57}, {212, 65}, {220, 73},
{228, 69}, {228, 77}, {236, 77}, {236, 69}, {236, 61}, {228, 61}, {228, 53}, {236, 53},
{236, 45}, {228, 45}, {228, 37}, {236, 37}, {236, 29}, {228, 29}, {228, 21}, {236, 21},
{252, 21}, {260, 29}, {260, 37}, {260, 45}, {260, 53}, {260, 61}, {260, 69}, {260, 77},
{276, 77}, {276, 69}, {276, 61}, {276, 53}, {284, 53}, {284, 61}, {284, 69}, {284, 77},
{284, 85}, {284, 93}, {284, 101}, {288, 109}, {280, 109}, {276, 101}, {276, 93}, {276, 85},
{268, 97}, {260, 109}, {252, 101}, {260, 93}, {260, 85}, {236, 85}, {228, 85}, {228, 93},
{236, 93}, {236, 101}, {228, 101}, {228, 109}, {228, 117}, {228, 125}, {220, 125},
{212, 117}, {204, 109}, {196, 101}, {188, 93}, {180, 93}, {180, 101}, {180, 109},
{180, 117}, {180, 125}, {196, 145}, {204, 145}, {212, 145}, {220, 145}, {228, 145},
{236, 145}, {246, 141}, {252, 125}, {260, 129}, {280, 133}};
public final int vehicleNumber = 1;
public final int depot = 0;
}
C#
class DataModel
{
public int[,] Locations = {
{ 288, 149 }, { 288, 129 }, { 270, 133 }, { 256, 141 }, { 256, 157 }, { 246, 157 }, { 236, 169 },
{ 228, 169 }, { 228, 161 }, { 220, 169 }, { 212, 169 }, { 204, 169 }, { 196, 169 }, { 188, 169 },
{ 196, 161 }, { 188, 145 }, { 172, 145 }, { 164, 145 }, { 156, 145 }, { 148, 145 }, { 140, 145 },
{ 148, 169 }, { 164, 169 }, { 172, 169 }, { 156, 169 }, { 140, 169 }, { 132, 169 }, { 124, 169 },
{ 116, 161 }, { 104, 153 }, { 104, 161 }, { 104, 169 }, { 90, 165 }, { 80, 157 }, { 64, 157 },
{ 64, 165 }, { 56, 169 }, { 56, 161 }, { 56, 153 }, { 56, 145 }, { 56, 137 }, { 56, 129 },
{ 56, 121 }, { 40, 121 }, { 40, 129 }, { 40, 137 }, { 40, 145 }, { 40, 153 }, { 40, 161 },
{ 40, 169 }, { 32, 169 }, { 32, 161 }, { 32, 153 }, { 32, 145 }, { 32, 137 }, { 32, 129 },
{ 32, 121 }, { 32, 113 }, { 40, 113 }, { 56, 113 }, { 56, 105 }, { 48, 99 }, { 40, 99 },
{ 32, 97 }, { 32, 89 }, { 24, 89 }, { 16, 97 }, { 16, 109 }, { 8, 109 }, { 8, 97 },
{ 8, 89 }, { 8, 81 }, { 8, 73 }, { 8, 65 }, { 8, 57 }, { 16, 57 }, { 8, 49 },
{ 8, 41 }, { 24, 45 }, { 32, 41 }, { 32, 49 }, { 32, 57 }, { 32, 65 }, { 32, 73 },
{ 32, 81 }, { 40, 83 }, { 40, 73 }, { 40, 63 }, { 40, 51 }, { 44, 43 }, { 44, 35 },
{ 44, 27 }, { 32, 25 }, { 24, 25 }, { 16, 25 }, { 16, 17 }, { 24, 17 }, { 32, 17 },
{ 44, 11 }, { 56, 9 }, { 56, 17 }, { 56, 25 }, { 56, 33 }, { 56, 41 }, { 64, 41 },
{ 72, 41 }, { 72, 49 }, { 56, 49 }, { 48, 51 }, { 56, 57 }, { 56, 65 }, { 48, 63 },
{ 48, 73 }, { 56, 73 }, { 56, 81 }, { 48, 83 }, { 56, 89 }, { 56, 97 }, { 104, 97 },
{ 104, 105 }, { 104, 113 }, { 104, 121 }, { 104, 129 }, { 104, 137 }, { 104, 145 }, { 116, 145 },
{ 124, 145 }, { 132, 145 }, { 132, 137 }, { 140, 137 }, { 148, 137 }, { 156, 137 }, { 164, 137 },
{ 172, 125 }, { 172, 117 }, { 172, 109 }, { 172, 101 }, { 172, 93 }, { 172, 85 }, { 180, 85 },
{ 180, 77 }, { 180, 69 }, { 180, 61 }, { 180, 53 }, { 172, 53 }, { 172, 61 }, { 172, 69 },
{ 172, 77 }, { 164, 81 }, { 148, 85 }, { 124, 85 }, { 124, 93 }, { 124, 109 }, { 124, 125 },
{ 124, 117 }, { 124, 101 }, { 104, 89 }, { 104, 81 }, { 104, 73 }, { 104, 65 }, { 104, 49 },
{ 104, 41 }, { 104, 33 }, { 104, 25 }, { 104, 17 }, { 92, 9 }, { 80, 9 }, { 72, 9 },
{ 64, 21 }, { 72, 25 }, { 80, 25 }, { 80, 25 }, { 80, 41 }, { 88, 49 }, { 104, 57 },
{ 124, 69 }, { 124, 77 }, { 132, 81 }, { 140, 65 }, { 132, 61 }, { 124, 61 }, { 124, 53 },
{ 124, 45 }, { 124, 37 }, { 124, 29 }, { 132, 21 }, { 124, 21 }, { 120, 9 }, { 128, 9 },
{ 136, 9 }, { 148, 9 }, { 162, 9 }, { 156, 25 }, { 172, 21 }, { 180, 21 }, { 180, 29 },
{ 172, 29 }, { 172, 37 }, { 172, 45 }, { 180, 45 }, { 180, 37 }, { 188, 41 }, { 196, 49 },
{ 204, 57 }, { 212, 65 }, { 220, 73 }, { 228, 69 }, { 228, 77 }, { 236, 77 }, { 236, 69 },
{ 236, 61 }, { 228, 61 }, { 228, 53 }, { 236, 53 }, { 236, 45 }, { 228, 45 }, { 228, 37 },
{ 236, 37 }, { 236, 29 }, { 228, 29 }, { 228, 21 }, { 236, 21 }, { 252, 21 }, { 260, 29 },
{ 260, 37 }, { 260, 45 }, { 260, 53 }, { 260, 61 }, { 260, 69 }, { 260, 77 }, { 276, 77 },
{ 276, 69 }, { 276, 61 }, { 276, 53 }, { 284, 53 }, { 284, 61 }, { 284, 69 }, { 284, 77 },
{ 284, 85 }, { 284, 93 }, { 284, 101 }, { 288, 109 }, { 280, 109 }, { 276, 101 }, { 276, 93 },
{ 276, 85 }, { 268, 97 }, { 260, 109 }, { 252, 101 }, { 260, 93 }, { 260, 85 }, { 236, 85 },
{ 228, 85 }, { 228, 93 }, { 236, 93 }, { 236, 101 }, { 228, 101 }, { 228, 109 }, { 228, 117 },
{ 228, 125 }, { 220, 125 }, { 212, 117 }, { 204, 109 }, { 196, 101 }, { 188, 93 }, { 180, 93 },
{ 180, 101 }, { 180, 109 }, { 180, 117 }, { 180, 125 }, { 196, 145 }, { 204, 145 }, { 212, 145 },
{ 220, 145 }, { 228, 145 }, { 236, 145 }, { 246, 141 }, { 252, 125 }, { 260, 129 }, { 280, 133 },
};
public int VehicleNumber = 1;
public int Depot = 0;
};
Tính toán ma trận khoảng cách
Hàm dưới đây tính toán khoảng cách Euclidean giữa hai điểm bất kỳ trong dữ liệu và lưu trữ điểm đó trong một mảng. Vì trình giải mã định tuyến hoạt động trên số nguyên nên hàm sẽ làm tròn khoảng cách được tính toán thành số nguyên. Việc làm tròn không ảnh hưởng đến giải pháp trong ví dụ này, nhưng có thể trong các trường hợp khác. Hãy xem phần Điều chỉnh tỷ lệ ma trận khoảng cách để biết cách tránh làm tròn các vấn đề.
Python
def compute_euclidean_distance_matrix(locations):
"""Creates callback to return distance between points."""
distances = {}
for from_counter, from_node in enumerate(locations):
distances[from_counter] = {}
for to_counter, to_node in enumerate(locations):
if from_counter == to_counter:
distances[from_counter][to_counter] = 0
else:
# Euclidean distance
distances[from_counter][to_counter] = int(
math.hypot((from_node[0] - to_node[0]), (from_node[1] - to_node[1]))
)
return distances
C++
// @brief Generate distance matrix.
std::vector<std::vector<int64_t>> ComputeEuclideanDistanceMatrix(
const std::vector<std::vector<int>>& locations) {
std::vector<std::vector<int64_t>> distances =
std::vector<std::vector<int64_t>>(
locations.size(), std::vector<int64_t>(locations.size(), int64_t{0}));
for (int from_node = 0; from_node < locations.size(); from_node++) {
for (int to_node = 0; to_node < locations.size(); to_node++) {
if (from_node != to_node)
distances[from_node][to_node] = static_cast<int64_t>(
std::hypot((locations[to_node][0] - locations[from_node][0]),
(locations[to_node][1] - locations[from_node][1])));
}
}
return distances;
}
Java
/// @brief Compute Euclidean distance matrix from locations array.
/// @details It uses an array of locations and computes
/// the Euclidean distance between any two locations.
private static long[][] computeEuclideanDistanceMatrix(int[][] locations) {
// Calculate distance matrix using Euclidean distance.
long[][] distanceMatrix = new long[locations.length][locations.length];
for (int fromNode = 0; fromNode < locations.length; ++fromNode) {
for (int toNode = 0; toNode < locations.length; ++toNode) {
if (fromNode == toNode) {
distanceMatrix[fromNode][toNode] = 0;
} else {
distanceMatrix[fromNode][toNode] =
(long) Math.hypot(locations[toNode][0] - locations[fromNode][0],
locations[toNode][1] - locations[fromNode][1]);
}
}
}
return distanceMatrix;
}
C#
/// <summary>
/// Euclidean distance implemented as a callback. It uses an array of
/// positions and computes the Euclidean distance between the two
/// positions of two different indices.
/// </summary>
static long[,] ComputeEuclideanDistanceMatrix(in int[,] locations)
{
// Calculate the distance matrix using Euclidean distance.
int locationNumber = locations.GetLength(0);
long[,] distanceMatrix = new long[locationNumber, locationNumber];
for (int fromNode = 0; fromNode < locationNumber; fromNode++)
{
for (int toNode = 0; toNode < locationNumber; toNode++)
{
if (fromNode == toNode)
distanceMatrix[fromNode, toNode] = 0;
else
distanceMatrix[fromNode, toNode] =
(long)Math.Sqrt(Math.Pow(locations[toNode, 0] - locations[fromNode, 0], 2) +
Math.Pow(locations[toNode, 1] - locations[fromNode, 1], 2));
}
}
return distanceMatrix;
}
Thêm lệnh gọi lại khoảng cách
Mã tạo lệnh gọi lại khoảng cách gần giống như trong ví dụ trước. Tuy nhiên, trong trường hợp này, chương trình sẽ gọi hàm tính toán ma trận khoảng cách trước khi thêm lệnh gọi lại.
Python
distance_matrix = compute_euclidean_distance_matrix(data["locations"])
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return distance_matrix[from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
C++
const auto distance_matrix = ComputeEuclideanDistanceMatrix(data.locations);
const int transit_callback_index = routing.RegisterTransitCallback(
[&distance_matrix, &manager](const int64_t from_index,
const int64_t to_index) -> int64_t {
// Convert from routing variable Index to distance matrix NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
const int to_node = manager.IndexToNode(to_index).value();
return distance_matrix[from_node][to_node];
});
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);
Java
final long[][] distanceMatrix = computeEuclideanDistanceMatrix(data.locations);
final int transitCallbackIndex =
routing.registerTransitCallback((long fromIndex, long toIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return distanceMatrix[fromNode][toNode];
});
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
C#
long[,] distanceMatrix = ComputeEuclideanDistanceMatrix(data.Locations);
int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
{
// Convert from routing variable Index to
// distance matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return distanceMatrix[fromNode, toNode];
});
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
Máy in giải pháp
Hàm sau đây in giải pháp vào bảng điều khiển. Để đầu ra nhỏ gọn hơn, hàm sẽ chỉ hiển thị các chỉ mục của vị trí trong tuyến đường.
Python
def print_solution(manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
index = routing.Start(0)
plan_output = "Route:\n"
route_distance = 0
while not routing.IsEnd(index):
plan_output += f" {manager.IndexToNode(index)} ->"
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
plan_output += f" {manager.IndexToNode(index)}\n"
print(plan_output)
plan_output += f"Objective: {route_distance}m\n"
C++
//! @brief Print the solution
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const RoutingIndexManager& manager,
const RoutingModel& routing, const Assignment& solution) {
LOG(INFO) << "Objective: " << solution.ObjectiveValue();
// Inspect solution.
int64_t index = routing.Start(0);
LOG(INFO) << "Route:";
int64_t distance{0};
std::stringstream route;
while (!routing.IsEnd(index)) {
route << manager.IndexToNode(index).value() << " -> ";
const int64_t previous_index = index;
index = solution.Value(routing.NextVar(index));
distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{0});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Route distance: " << distance << "miles";
LOG(INFO) << "";
LOG(INFO) << "Advanced usage:";
LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}
Java
/// @brief Print the solution.
static void printSolution(
RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
// Solution cost.
logger.info("Objective: " + solution.objectiveValue());
// Inspect solution.
logger.info("Route:");
long routeDistance = 0;
String route = "";
long index = routing.start(0);
while (!routing.isEnd(index)) {
route += manager.indexToNode(index) + " -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routing.getArcCostForVehicle(previousIndex, index, 0);
}
route += manager.indexToNode(routing.end(0));
logger.info(route);
logger.info("Route distance: " + routeDistance);
}
C#
/// <summary>
/// Print the solution.
/// </summary>
static void PrintSolution(in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution)
{
Console.WriteLine("Objective: {0}", solution.ObjectiveValue());
// Inspect solution.
Console.WriteLine("Route:");
long routeDistance = 0;
var index = routing.Start(0);
while (routing.IsEnd(index) == false)
{
Console.Write("{0} -> ", manager.IndexToNode((int)index));
var previousIndex = index;
index = solution.Value(routing.NextVar(index));
routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode((int)index));
Console.WriteLine("Route distance: {0}m", routeDistance);
}
Hàm chính
Hàm chính về cơ bản giống như hàm trong ví dụ trước, nhưng cũng bao gồm lệnh gọi hàm tạo ma trận khoảng cách.
Chạy chương trình
Bạn có thể xem các chương trình hoàn chỉnh trong phần tiếp theo. Khi chạy chương trình, bạn sẽ thấy tuyến đường sau:
Total distance: 2790 Route of vehicle 0: 0 -> 1 -> 279 -> 2 -> 278 -> 277 -> 247 -> 248 -> 249 -> 246 -> 244 -> 243 -> 242 -> 241 -> 240 -> 239 -> 238 -> 237 -> 236 -> 235 -> 234 -> 233 -> 232 -> 231 -> 230 -> 245 -> 250 -> 229 -> 228 -> 227 -> 226 -> 225 -> 224 -> 223 -> 222 -> 221 -> 220 -> 219 -> 218 -> 217 -> 216 -> 215 -> 214 -> 213 -> 212 -> 211 -> 210 -> 209 -> 208 -> 251 -> 254 -> 255 -> 257 -> 256 -> 253 -> 252 -> 207 -> 206 -> 205 -> 204 -> 203 -> 202 -> 142 -> 141 -> 146 -> 147 -> 140 -> 139 -> 265 -> 136 -> 137 -> 138 -> 148 -> 149 -> 177 -> 176 -> 175 -> 178 -> 179 -> 180 -> 181 -> 182 -> 183 -> 184 -> 186 -> 185 -> 192 -> 196 -> 197 -> 198 -> 144 -> 145 -> 143 -> 199 -> 201 -> 200 -> 195 -> 194 -> 193 -> 191 -> 190 -> 189 -> 188 -> 187 -> 163 -> 164 -> 165 -> 166 -> 167 -> 168 -> 169 -> 171 -> 170 -> 172 -> 105 -> 106 -> 104 -> 103 -> 107 -> 109 -> 110 -> 113 -> 114 -> 116 -> 117 -> 61 -> 62 -> 63 -> 65 -> 64 -> 84 -> 85 -> 115 -> 112 -> 86 -> 83 -> 82 -> 87 -> 111 -> 108 -> 89 -> 90 -> 91 -> 102 -> 101 -> 100 -> 99 -> 98 -> 97 -> 96 -> 95 -> 94 -> 93 -> 92 -> 79 -> 88 -> 81 -> 80 -> 78 -> 77 -> 76 -> 74 -> 75 -> 73 -> 72 -> 71 -> 70 -> 69 -> 66 -> 68 -> 67 -> 57 -> 56 -> 55 -> 54 -> 53 -> 52 -> 51 -> 50 -> 49 -> 48 -> 47 -> 46 -> 45 -> 44 -> 43 -> 58 -> 60 -> 59 -> 42 -> 41 -> 40 -> 39 -> 38 -> 37 -> 36 -> 35 -> 34 -> 33 -> 32 -> 31 -> 30 -> 29 -> 124 -> 123 -> 122 -> 121 -> 120 -> 119 -> 118 -> 156 -> 157 -> 158 -> 173 -> 162 -> 161 -> 160 -> 174 -> 159 -> 150 -> 151 -> 155 -> 152 -> 154 -> 153 -> 128 -> 129 -> 130 -> 131 -> 18 -> 19 -> 20 -> 127 -> 126 -> 125 -> 28 -> 27 -> 26 -> 25 -> 21 -> 24 -> 22 -> 23 -> 13 -> 12 -> 14 -> 11 -> 10 -> 9 -> 7 -> 8 -> 6 -> 5 -> 275 -> 274 -> 273 -> 272 -> 271 -> 270 -> 15 -> 16 -> 17 -> 132 -> 133 -> 269 -> 268 -> 134 -> 135 -> 267 -> 266 -> 264 -> 263 -> 262 -> 261 -> 260 -> 258 -> 259 -> 276 -> 3 -> 4 -> 0
Dưới đây là biểu đồ của tuyến đường tương ứng:
Thư viện OR-Tools sẽ tìm thấy hướng dẫn ở trên rất nhanh: trong chưa đầy một giây trên một máy tính thông thường. Tổng thời lượng của chuyến tham quan ở trên là 2790.
Hoàn thành chương trình
Dưới đây là những chương trình hoàn chỉnh cho ví dụ về bảng mạch.
Python
"""Simple Travelling Salesperson Problem (TSP) on a circuit board."""
import math
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""Stores the data for the problem."""
data = {}
# Locations in block units
data["locations"] = [
# fmt: off
(288, 149), (288, 129), (270, 133), (256, 141), (256, 157), (246, 157),
(236, 169), (228, 169), (228, 161), (220, 169), (212, 169), (204, 169),
(196, 169), (188, 169), (196, 161), (188, 145), (172, 145), (164, 145),
(156, 145), (148, 145), (140, 145), (148, 169), (164, 169), (172, 169),
(156, 169), (140, 169), (132, 169), (124, 169), (116, 161), (104, 153),
(104, 161), (104, 169), (90, 165), (80, 157), (64, 157), (64, 165),
(56, 169), (56, 161), (56, 153), (56, 145), (56, 137), (56, 129),
(56, 121), (40, 121), (40, 129), (40, 137), (40, 145), (40, 153),
(40, 161), (40, 169), (32, 169), (32, 161), (32, 153), (32, 145),
(32, 137), (32, 129), (32, 121), (32, 113), (40, 113), (56, 113),
(56, 105), (48, 99), (40, 99), (32, 97), (32, 89), (24, 89),
(16, 97), (16, 109), (8, 109), (8, 97), (8, 89), (8, 81),
(8, 73), (8, 65), (8, 57), (16, 57), (8, 49), (8, 41),
(24, 45), (32, 41), (32, 49), (32, 57), (32, 65), (32, 73),
(32, 81), (40, 83), (40, 73), (40, 63), (40, 51), (44, 43),
(44, 35), (44, 27), (32, 25), (24, 25), (16, 25), (16, 17),
(24, 17), (32, 17), (44, 11), (56, 9), (56, 17), (56, 25),
(56, 33), (56, 41), (64, 41), (72, 41), (72, 49), (56, 49),
(48, 51), (56, 57), (56, 65), (48, 63), (48, 73), (56, 73),
(56, 81), (48, 83), (56, 89), (56, 97), (104, 97), (104, 105),
(104, 113), (104, 121), (104, 129), (104, 137), (104, 145), (116, 145),
(124, 145), (132, 145), (132, 137), (140, 137), (148, 137), (156, 137),
(164, 137), (172, 125), (172, 117), (172, 109), (172, 101), (172, 93),
(172, 85), (180, 85), (180, 77), (180, 69), (180, 61), (180, 53),
(172, 53), (172, 61), (172, 69), (172, 77), (164, 81), (148, 85),
(124, 85), (124, 93), (124, 109), (124, 125), (124, 117), (124, 101),
(104, 89), (104, 81), (104, 73), (104, 65), (104, 49), (104, 41),
(104, 33), (104, 25), (104, 17), (92, 9), (80, 9), (72, 9),
(64, 21), (72, 25), (80, 25), (80, 25), (80, 41), (88, 49),
(104, 57), (124, 69), (124, 77), (132, 81), (140, 65), (132, 61),
(124, 61), (124, 53), (124, 45), (124, 37), (124, 29), (132, 21),
(124, 21), (120, 9), (128, 9), (136, 9), (148, 9), (162, 9),
(156, 25), (172, 21), (180, 21), (180, 29), (172, 29), (172, 37),
(172, 45), (180, 45), (180, 37), (188, 41), (196, 49), (204, 57),
(212, 65), (220, 73), (228, 69), (228, 77), (236, 77), (236, 69),
(236, 61), (228, 61), (228, 53), (236, 53), (236, 45), (228, 45),
(228, 37), (236, 37), (236, 29), (228, 29), (228, 21), (236, 21),
(252, 21), (260, 29), (260, 37), (260, 45), (260, 53), (260, 61),
(260, 69), (260, 77), (276, 77), (276, 69), (276, 61), (276, 53),
(284, 53), (284, 61), (284, 69), (284, 77), (284, 85), (284, 93),
(284, 101), (288, 109), (280, 109), (276, 101), (276, 93), (276, 85),
(268, 97), (260, 109), (252, 101), (260, 93), (260, 85), (236, 85),
(228, 85), (228, 93), (236, 93), (236, 101), (228, 101), (228, 109),
(228, 117), (228, 125), (220, 125), (212, 117), (204, 109), (196, 101),
(188, 93), (180, 93), (180, 101), (180, 109), (180, 117), (180, 125),
(196, 145), (204, 145), (212, 145), (220, 145), (228, 145), (236, 145),
(246, 141), (252, 125), (260, 129), (280, 133)
# fmt: on
]
data["num_vehicles"] = 1
data["depot"] = 0
return data
def compute_euclidean_distance_matrix(locations):
"""Creates callback to return distance between points."""
distances = {}
for from_counter, from_node in enumerate(locations):
distances[from_counter] = {}
for to_counter, to_node in enumerate(locations):
if from_counter == to_counter:
distances[from_counter][to_counter] = 0
else:
# Euclidean distance
distances[from_counter][to_counter] = int(
math.hypot((from_node[0] - to_node[0]), (from_node[1] - to_node[1]))
)
return distances
def print_solution(manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
index = routing.Start(0)
plan_output = "Route:\n"
route_distance = 0
while not routing.IsEnd(index):
plan_output += f" {manager.IndexToNode(index)} ->"
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
plan_output += f" {manager.IndexToNode(index)}\n"
print(plan_output)
plan_output += f"Objective: {route_distance}m\n"
def main():
"""Entry point of the program."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data["locations"]), data["num_vehicles"], data["depot"]
)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
distance_matrix = compute_euclidean_distance_matrix(data["locations"])
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return distance_matrix[from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(manager, routing, solution)
if __name__ == "__main__":
main()
C++
#include <cmath>
#include <cstdint>
#include <sstream>
#include <vector>
#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_index_manager.h"
#include "ortools/constraint_solver/routing_parameters.h"
namespace operations_research {
struct DataModel {
const std::vector<std::vector<int>> locations{
{288, 149}, {288, 129}, {270, 133}, {256, 141}, {256, 157}, {246, 157},
{236, 169}, {228, 169}, {228, 161}, {220, 169}, {212, 169}, {204, 169},
{196, 169}, {188, 169}, {196, 161}, {188, 145}, {172, 145}, {164, 145},
{156, 145}, {148, 145}, {140, 145}, {148, 169}, {164, 169}, {172, 169},
{156, 169}, {140, 169}, {132, 169}, {124, 169}, {116, 161}, {104, 153},
{104, 161}, {104, 169}, {90, 165}, {80, 157}, {64, 157}, {64, 165},
{56, 169}, {56, 161}, {56, 153}, {56, 145}, {56, 137}, {56, 129},
{56, 121}, {40, 121}, {40, 129}, {40, 137}, {40, 145}, {40, 153},
{40, 161}, {40, 169}, {32, 169}, {32, 161}, {32, 153}, {32, 145},
{32, 137}, {32, 129}, {32, 121}, {32, 113}, {40, 113}, {56, 113},
{56, 105}, {48, 99}, {40, 99}, {32, 97}, {32, 89}, {24, 89},
{16, 97}, {16, 109}, {8, 109}, {8, 97}, {8, 89}, {8, 81},
{8, 73}, {8, 65}, {8, 57}, {16, 57}, {8, 49}, {8, 41},
{24, 45}, {32, 41}, {32, 49}, {32, 57}, {32, 65}, {32, 73},
{32, 81}, {40, 83}, {40, 73}, {40, 63}, {40, 51}, {44, 43},
{44, 35}, {44, 27}, {32, 25}, {24, 25}, {16, 25}, {16, 17},
{24, 17}, {32, 17}, {44, 11}, {56, 9}, {56, 17}, {56, 25},
{56, 33}, {56, 41}, {64, 41}, {72, 41}, {72, 49}, {56, 49},
{48, 51}, {56, 57}, {56, 65}, {48, 63}, {48, 73}, {56, 73},
{56, 81}, {48, 83}, {56, 89}, {56, 97}, {104, 97}, {104, 105},
{104, 113}, {104, 121}, {104, 129}, {104, 137}, {104, 145}, {116, 145},
{124, 145}, {132, 145}, {132, 137}, {140, 137}, {148, 137}, {156, 137},
{164, 137}, {172, 125}, {172, 117}, {172, 109}, {172, 101}, {172, 93},
{172, 85}, {180, 85}, {180, 77}, {180, 69}, {180, 61}, {180, 53},
{172, 53}, {172, 61}, {172, 69}, {172, 77}, {164, 81}, {148, 85},
{124, 85}, {124, 93}, {124, 109}, {124, 125}, {124, 117}, {124, 101},
{104, 89}, {104, 81}, {104, 73}, {104, 65}, {104, 49}, {104, 41},
{104, 33}, {104, 25}, {104, 17}, {92, 9}, {80, 9}, {72, 9},
{64, 21}, {72, 25}, {80, 25}, {80, 25}, {80, 41}, {88, 49},
{104, 57}, {124, 69}, {124, 77}, {132, 81}, {140, 65}, {132, 61},
{124, 61}, {124, 53}, {124, 45}, {124, 37}, {124, 29}, {132, 21},
{124, 21}, {120, 9}, {128, 9}, {136, 9}, {148, 9}, {162, 9},
{156, 25}, {172, 21}, {180, 21}, {180, 29}, {172, 29}, {172, 37},
{172, 45}, {180, 45}, {180, 37}, {188, 41}, {196, 49}, {204, 57},
{212, 65}, {220, 73}, {228, 69}, {228, 77}, {236, 77}, {236, 69},
{236, 61}, {228, 61}, {228, 53}, {236, 53}, {236, 45}, {228, 45},
{228, 37}, {236, 37}, {236, 29}, {228, 29}, {228, 21}, {236, 21},
{252, 21}, {260, 29}, {260, 37}, {260, 45}, {260, 53}, {260, 61},
{260, 69}, {260, 77}, {276, 77}, {276, 69}, {276, 61}, {276, 53},
{284, 53}, {284, 61}, {284, 69}, {284, 77}, {284, 85}, {284, 93},
{284, 101}, {288, 109}, {280, 109}, {276, 101}, {276, 93}, {276, 85},
{268, 97}, {260, 109}, {252, 101}, {260, 93}, {260, 85}, {236, 85},
{228, 85}, {228, 93}, {236, 93}, {236, 101}, {228, 101}, {228, 109},
{228, 117}, {228, 125}, {220, 125}, {212, 117}, {204, 109}, {196, 101},
{188, 93}, {180, 93}, {180, 101}, {180, 109}, {180, 117}, {180, 125},
{196, 145}, {204, 145}, {212, 145}, {220, 145}, {228, 145}, {236, 145},
{246, 141}, {252, 125}, {260, 129}, {280, 133},
};
const int num_vehicles = 1;
const RoutingIndexManager::NodeIndex depot{0};
};
// @brief Generate distance matrix.
std::vector<std::vector<int64_t>> ComputeEuclideanDistanceMatrix(
const std::vector<std::vector<int>>& locations) {
std::vector<std::vector<int64_t>> distances =
std::vector<std::vector<int64_t>>(
locations.size(), std::vector<int64_t>(locations.size(), int64_t{0}));
for (int from_node = 0; from_node < locations.size(); from_node++) {
for (int to_node = 0; to_node < locations.size(); to_node++) {
if (from_node != to_node)
distances[from_node][to_node] = static_cast<int64_t>(
std::hypot((locations[to_node][0] - locations[from_node][0]),
(locations[to_node][1] - locations[from_node][1])));
}
}
return distances;
}
//! @brief Print the solution
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const RoutingIndexManager& manager,
const RoutingModel& routing, const Assignment& solution) {
LOG(INFO) << "Objective: " << solution.ObjectiveValue();
// Inspect solution.
int64_t index = routing.Start(0);
LOG(INFO) << "Route:";
int64_t distance{0};
std::stringstream route;
while (!routing.IsEnd(index)) {
route << manager.IndexToNode(index).value() << " -> ";
const int64_t previous_index = index;
index = solution.Value(routing.NextVar(index));
distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{0});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Route distance: " << distance << "miles";
LOG(INFO) << "";
LOG(INFO) << "Advanced usage:";
LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}
void Tsp() {
// Instantiate the data problem.
DataModel data;
// Create Routing Index Manager
RoutingIndexManager manager(data.locations.size(), data.num_vehicles,
data.depot);
// Create Routing Model.
RoutingModel routing(manager);
const auto distance_matrix = ComputeEuclideanDistanceMatrix(data.locations);
const int transit_callback_index = routing.RegisterTransitCallback(
[&distance_matrix, &manager](const int64_t from_index,
const int64_t to_index) -> int64_t {
// Convert from routing variable Index to distance matrix NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
const int to_node = manager.IndexToNode(to_index).value();
return distance_matrix[from_node][to_node];
});
// Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);
// Setting first solution heuristic.
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
searchParameters.set_first_solution_strategy(
FirstSolutionStrategy::PATH_CHEAPEST_ARC);
// Solve the problem.
const Assignment* solution = routing.SolveWithParameters(searchParameters);
// Print solution on console.
PrintSolution(manager, routing, *solution);
}
} // namespace operations_research
int main(int /*argc*/, char* /*argv*/[]) {
operations_research::Tsp();
return EXIT_SUCCESS;
}
Java
package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.Assignment;
import com.google.ortools.constraintsolver.FirstSolutionStrategy;
import com.google.ortools.constraintsolver.RoutingIndexManager;
import com.google.ortools.constraintsolver.RoutingModel;
import com.google.ortools.constraintsolver.RoutingSearchParameters;
import com.google.ortools.constraintsolver.main;
import java.util.logging.Logger;
/** Minimal TSP. */
public class TspCircuitBoard {
private static final Logger logger = Logger.getLogger(TspCircuitBoard.class.getName());
static class DataModel {
public final int[][] locations = {{288, 149}, {288, 129}, {270, 133}, {256, 141}, {256, 157},
{246, 157}, {236, 169}, {228, 169}, {228, 161}, {220, 169}, {212, 169}, {204, 169},
{196, 169}, {188, 169}, {196, 161}, {188, 145}, {172, 145}, {164, 145}, {156, 145},
{148, 145}, {140, 145}, {148, 169}, {164, 169}, {172, 169}, {156, 169}, {140, 169},
{132, 169}, {124, 169}, {116, 161}, {104, 153}, {104, 161}, {104, 169}, {90, 165},
{80, 157}, {64, 157}, {64, 165}, {56, 169}, {56, 161}, {56, 153}, {56, 145}, {56, 137},
{56, 129}, {56, 121}, {40, 121}, {40, 129}, {40, 137}, {40, 145}, {40, 153}, {40, 161},
{40, 169}, {32, 169}, {32, 161}, {32, 153}, {32, 145}, {32, 137}, {32, 129}, {32, 121},
{32, 113}, {40, 113}, {56, 113}, {56, 105}, {48, 99}, {40, 99}, {32, 97}, {32, 89},
{24, 89}, {16, 97}, {16, 109}, {8, 109}, {8, 97}, {8, 89}, {8, 81}, {8, 73}, {8, 65},
{8, 57}, {16, 57}, {8, 49}, {8, 41}, {24, 45}, {32, 41}, {32, 49}, {32, 57}, {32, 65},
{32, 73}, {32, 81}, {40, 83}, {40, 73}, {40, 63}, {40, 51}, {44, 43}, {44, 35}, {44, 27},
{32, 25}, {24, 25}, {16, 25}, {16, 17}, {24, 17}, {32, 17}, {44, 11}, {56, 9}, {56, 17},
{56, 25}, {56, 33}, {56, 41}, {64, 41}, {72, 41}, {72, 49}, {56, 49}, {48, 51}, {56, 57},
{56, 65}, {48, 63}, {48, 73}, {56, 73}, {56, 81}, {48, 83}, {56, 89}, {56, 97}, {104, 97},
{104, 105}, {104, 113}, {104, 121}, {104, 129}, {104, 137}, {104, 145}, {116, 145},
{124, 145}, {132, 145}, {132, 137}, {140, 137}, {148, 137}, {156, 137}, {164, 137},
{172, 125}, {172, 117}, {172, 109}, {172, 101}, {172, 93}, {172, 85}, {180, 85}, {180, 77},
{180, 69}, {180, 61}, {180, 53}, {172, 53}, {172, 61}, {172, 69}, {172, 77}, {164, 81},
{148, 85}, {124, 85}, {124, 93}, {124, 109}, {124, 125}, {124, 117}, {124, 101}, {104, 89},
{104, 81}, {104, 73}, {104, 65}, {104, 49}, {104, 41}, {104, 33}, {104, 25}, {104, 17},
{92, 9}, {80, 9}, {72, 9}, {64, 21}, {72, 25}, {80, 25}, {80, 25}, {80, 41}, {88, 49},
{104, 57}, {124, 69}, {124, 77}, {132, 81}, {140, 65}, {132, 61}, {124, 61}, {124, 53},
{124, 45}, {124, 37}, {124, 29}, {132, 21}, {124, 21}, {120, 9}, {128, 9}, {136, 9},
{148, 9}, {162, 9}, {156, 25}, {172, 21}, {180, 21}, {180, 29}, {172, 29}, {172, 37},
{172, 45}, {180, 45}, {180, 37}, {188, 41}, {196, 49}, {204, 57}, {212, 65}, {220, 73},
{228, 69}, {228, 77}, {236, 77}, {236, 69}, {236, 61}, {228, 61}, {228, 53}, {236, 53},
{236, 45}, {228, 45}, {228, 37}, {236, 37}, {236, 29}, {228, 29}, {228, 21}, {236, 21},
{252, 21}, {260, 29}, {260, 37}, {260, 45}, {260, 53}, {260, 61}, {260, 69}, {260, 77},
{276, 77}, {276, 69}, {276, 61}, {276, 53}, {284, 53}, {284, 61}, {284, 69}, {284, 77},
{284, 85}, {284, 93}, {284, 101}, {288, 109}, {280, 109}, {276, 101}, {276, 93}, {276, 85},
{268, 97}, {260, 109}, {252, 101}, {260, 93}, {260, 85}, {236, 85}, {228, 85}, {228, 93},
{236, 93}, {236, 101}, {228, 101}, {228, 109}, {228, 117}, {228, 125}, {220, 125},
{212, 117}, {204, 109}, {196, 101}, {188, 93}, {180, 93}, {180, 101}, {180, 109},
{180, 117}, {180, 125}, {196, 145}, {204, 145}, {212, 145}, {220, 145}, {228, 145},
{236, 145}, {246, 141}, {252, 125}, {260, 129}, {280, 133}};
public final int vehicleNumber = 1;
public final int depot = 0;
}
/// @brief Compute Euclidean distance matrix from locations array.
/// @details It uses an array of locations and computes
/// the Euclidean distance between any two locations.
private static long[][] computeEuclideanDistanceMatrix(int[][] locations) {
// Calculate distance matrix using Euclidean distance.
long[][] distanceMatrix = new long[locations.length][locations.length];
for (int fromNode = 0; fromNode < locations.length; ++fromNode) {
for (int toNode = 0; toNode < locations.length; ++toNode) {
if (fromNode == toNode) {
distanceMatrix[fromNode][toNode] = 0;
} else {
distanceMatrix[fromNode][toNode] =
(long) Math.hypot(locations[toNode][0] - locations[fromNode][0],
locations[toNode][1] - locations[fromNode][1]);
}
}
}
return distanceMatrix;
}
/// @brief Print the solution.
static void printSolution(
RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
// Solution cost.
logger.info("Objective: " + solution.objectiveValue());
// Inspect solution.
logger.info("Route:");
long routeDistance = 0;
String route = "";
long index = routing.start(0);
while (!routing.isEnd(index)) {
route += manager.indexToNode(index) + " -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routing.getArcCostForVehicle(previousIndex, index, 0);
}
route += manager.indexToNode(routing.end(0));
logger.info(route);
logger.info("Route distance: " + routeDistance);
}
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// Instantiate the data problem.
final DataModel data = new DataModel();
// Create Routing Index Manager
RoutingIndexManager manager =
new RoutingIndexManager(data.locations.length, data.vehicleNumber, data.depot);
// Create Routing Model.
RoutingModel routing = new RoutingModel(manager);
// Create and register a transit callback.
final long[][] distanceMatrix = computeEuclideanDistanceMatrix(data.locations);
final int transitCallbackIndex =
routing.registerTransitCallback((long fromIndex, long toIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return distanceMatrix[fromNode][toNode];
});
// Define cost of each arc.
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();
// Solve the problem.
Assignment solution = routing.solveWithParameters(searchParameters);
// Print solution on console.
printSolution(routing, manager, solution);
}
}
C#
using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;
/// <summary>
/// Minimal TSP.
/// A description of the problem can be found here:
/// http://en.wikipedia.org/wiki/Travelling_salesperson_problem.
/// </summary>
public class TspCircuitBoard
{
class DataModel
{
public int[,] Locations = {
{ 288, 149 }, { 288, 129 }, { 270, 133 }, { 256, 141 }, { 256, 157 }, { 246, 157 }, { 236, 169 },
{ 228, 169 }, { 228, 161 }, { 220, 169 }, { 212, 169 }, { 204, 169 }, { 196, 169 }, { 188, 169 },
{ 196, 161 }, { 188, 145 }, { 172, 145 }, { 164, 145 }, { 156, 145 }, { 148, 145 }, { 140, 145 },
{ 148, 169 }, { 164, 169 }, { 172, 169 }, { 156, 169 }, { 140, 169 }, { 132, 169 }, { 124, 169 },
{ 116, 161 }, { 104, 153 }, { 104, 161 }, { 104, 169 }, { 90, 165 }, { 80, 157 }, { 64, 157 },
{ 64, 165 }, { 56, 169 }, { 56, 161 }, { 56, 153 }, { 56, 145 }, { 56, 137 }, { 56, 129 },
{ 56, 121 }, { 40, 121 }, { 40, 129 }, { 40, 137 }, { 40, 145 }, { 40, 153 }, { 40, 161 },
{ 40, 169 }, { 32, 169 }, { 32, 161 }, { 32, 153 }, { 32, 145 }, { 32, 137 }, { 32, 129 },
{ 32, 121 }, { 32, 113 }, { 40, 113 }, { 56, 113 }, { 56, 105 }, { 48, 99 }, { 40, 99 },
{ 32, 97 }, { 32, 89 }, { 24, 89 }, { 16, 97 }, { 16, 109 }, { 8, 109 }, { 8, 97 },
{ 8, 89 }, { 8, 81 }, { 8, 73 }, { 8, 65 }, { 8, 57 }, { 16, 57 }, { 8, 49 },
{ 8, 41 }, { 24, 45 }, { 32, 41 }, { 32, 49 }, { 32, 57 }, { 32, 65 }, { 32, 73 },
{ 32, 81 }, { 40, 83 }, { 40, 73 }, { 40, 63 }, { 40, 51 }, { 44, 43 }, { 44, 35 },
{ 44, 27 }, { 32, 25 }, { 24, 25 }, { 16, 25 }, { 16, 17 }, { 24, 17 }, { 32, 17 },
{ 44, 11 }, { 56, 9 }, { 56, 17 }, { 56, 25 }, { 56, 33 }, { 56, 41 }, { 64, 41 },
{ 72, 41 }, { 72, 49 }, { 56, 49 }, { 48, 51 }, { 56, 57 }, { 56, 65 }, { 48, 63 },
{ 48, 73 }, { 56, 73 }, { 56, 81 }, { 48, 83 }, { 56, 89 }, { 56, 97 }, { 104, 97 },
{ 104, 105 }, { 104, 113 }, { 104, 121 }, { 104, 129 }, { 104, 137 }, { 104, 145 }, { 116, 145 },
{ 124, 145 }, { 132, 145 }, { 132, 137 }, { 140, 137 }, { 148, 137 }, { 156, 137 }, { 164, 137 },
{ 172, 125 }, { 172, 117 }, { 172, 109 }, { 172, 101 }, { 172, 93 }, { 172, 85 }, { 180, 85 },
{ 180, 77 }, { 180, 69 }, { 180, 61 }, { 180, 53 }, { 172, 53 }, { 172, 61 }, { 172, 69 },
{ 172, 77 }, { 164, 81 }, { 148, 85 }, { 124, 85 }, { 124, 93 }, { 124, 109 }, { 124, 125 },
{ 124, 117 }, { 124, 101 }, { 104, 89 }, { 104, 81 }, { 104, 73 }, { 104, 65 }, { 104, 49 },
{ 104, 41 }, { 104, 33 }, { 104, 25 }, { 104, 17 }, { 92, 9 }, { 80, 9 }, { 72, 9 },
{ 64, 21 }, { 72, 25 }, { 80, 25 }, { 80, 25 }, { 80, 41 }, { 88, 49 }, { 104, 57 },
{ 124, 69 }, { 124, 77 }, { 132, 81 }, { 140, 65 }, { 132, 61 }, { 124, 61 }, { 124, 53 },
{ 124, 45 }, { 124, 37 }, { 124, 29 }, { 132, 21 }, { 124, 21 }, { 120, 9 }, { 128, 9 },
{ 136, 9 }, { 148, 9 }, { 162, 9 }, { 156, 25 }, { 172, 21 }, { 180, 21 }, { 180, 29 },
{ 172, 29 }, { 172, 37 }, { 172, 45 }, { 180, 45 }, { 180, 37 }, { 188, 41 }, { 196, 49 },
{ 204, 57 }, { 212, 65 }, { 220, 73 }, { 228, 69 }, { 228, 77 }, { 236, 77 }, { 236, 69 },
{ 236, 61 }, { 228, 61 }, { 228, 53 }, { 236, 53 }, { 236, 45 }, { 228, 45 }, { 228, 37 },
{ 236, 37 }, { 236, 29 }, { 228, 29 }, { 228, 21 }, { 236, 21 }, { 252, 21 }, { 260, 29 },
{ 260, 37 }, { 260, 45 }, { 260, 53 }, { 260, 61 }, { 260, 69 }, { 260, 77 }, { 276, 77 },
{ 276, 69 }, { 276, 61 }, { 276, 53 }, { 284, 53 }, { 284, 61 }, { 284, 69 }, { 284, 77 },
{ 284, 85 }, { 284, 93 }, { 284, 101 }, { 288, 109 }, { 280, 109 }, { 276, 101 }, { 276, 93 },
{ 276, 85 }, { 268, 97 }, { 260, 109 }, { 252, 101 }, { 260, 93 }, { 260, 85 }, { 236, 85 },
{ 228, 85 }, { 228, 93 }, { 236, 93 }, { 236, 101 }, { 228, 101 }, { 228, 109 }, { 228, 117 },
{ 228, 125 }, { 220, 125 }, { 212, 117 }, { 204, 109 }, { 196, 101 }, { 188, 93 }, { 180, 93 },
{ 180, 101 }, { 180, 109 }, { 180, 117 }, { 180, 125 }, { 196, 145 }, { 204, 145 }, { 212, 145 },
{ 220, 145 }, { 228, 145 }, { 236, 145 }, { 246, 141 }, { 252, 125 }, { 260, 129 }, { 280, 133 },
};
public int VehicleNumber = 1;
public int Depot = 0;
};
/// <summary>
/// Euclidean distance implemented as a callback. It uses an array of
/// positions and computes the Euclidean distance between the two
/// positions of two different indices.
/// </summary>
static long[,] ComputeEuclideanDistanceMatrix(in int[,] locations)
{
// Calculate the distance matrix using Euclidean distance.
int locationNumber = locations.GetLength(0);
long[,] distanceMatrix = new long[locationNumber, locationNumber];
for (int fromNode = 0; fromNode < locationNumber; fromNode++)
{
for (int toNode = 0; toNode < locationNumber; toNode++)
{
if (fromNode == toNode)
distanceMatrix[fromNode, toNode] = 0;
else
distanceMatrix[fromNode, toNode] =
(long)Math.Sqrt(Math.Pow(locations[toNode, 0] - locations[fromNode, 0], 2) +
Math.Pow(locations[toNode, 1] - locations[fromNode, 1], 2));
}
}
return distanceMatrix;
}
/// <summary>
/// Print the solution.
/// </summary>
static void PrintSolution(in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution)
{
Console.WriteLine("Objective: {0}", solution.ObjectiveValue());
// Inspect solution.
Console.WriteLine("Route:");
long routeDistance = 0;
var index = routing.Start(0);
while (routing.IsEnd(index) == false)
{
Console.Write("{0} -> ", manager.IndexToNode((int)index));
var previousIndex = index;
index = solution.Value(routing.NextVar(index));
routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode((int)index));
Console.WriteLine("Route distance: {0}m", routeDistance);
}
public static void Main(String[] args)
{
// Instantiate the data problem.
DataModel data = new DataModel();
// Create Routing Index Manager
RoutingIndexManager manager =
new RoutingIndexManager(data.Locations.GetLength(0), data.VehicleNumber, data.Depot);
// Create Routing Model.
RoutingModel routing = new RoutingModel(manager);
// Define cost of each arc.
long[,] distanceMatrix = ComputeEuclideanDistanceMatrix(data.Locations);
int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
{
// Convert from routing variable Index to
// distance matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return distanceMatrix[fromNode, toNode];
});
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
// Solve the problem.
Assignment solution = routing.SolveWithParameters(searchParameters);
// Print solution on console.
PrintSolution(routing, manager, solution);
}
}
Thay đổi chiến lược tìm kiếm
Trình giải mã định tuyến không phải lúc nào cũng trả về giải pháp tối ưu cho TSP, vì các sự cố định tuyến không thể tính toán được. Ví dụ: giải pháp được trả về trong ví dụ trước không phải là tuyến tối ưu.
Để tìm giải pháp tốt hơn, bạn có thể sử dụng chiến lược tìm kiếm nâng cao hơn, có tên là tìm kiếm địa phương có hướng dẫn, giúp trình giải toán thoát khỏi tối thiểu cục bộ – giải pháp ngắn hơn tất cả các tuyến lân cận, nhưng không phải là tối thiểu toàn cầu. Sau khi thoát khỏi mức tối thiểu cục bộ, trình giải toán sẽ tiếp tục tìm kiếm.
Các ví dụ bên dưới cho thấy cách đặt tìm kiếm cục bộ có hướng dẫn cho ví dụ về bảng mạch.
Python
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 30
search_parameters.log_search = True
C++
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
searchParameters.set_local_search_metaheuristic(
LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH);
searchParameters.mutable_time_limit()->set_seconds(30);
search_parameters.set_log_search(true);
Java
Thêm câu lệnh `import` sau vào đầu chương trình:import com.google.protobuf.Duration;Sau đó, đặt tham số tìm kiếm như sau:
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH)
.setTimeLimit(Duration.newBuilder().setSeconds(30).build())
.setLogSearch(true)
.build();
C#
Thêm dòng sau vào đầu chương trình:using Google.Protobuf.WellKnownTypes; // DurationSau đó, đặt tham số tìm kiếm như sau:
RoutingSearchParameters searchParameters =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch;
searchParameters.TimeLimit = new Duration { Seconds = 30 };
searchParameters.LogSearch = true;
Đối với các chiến lược tìm kiếm tại địa phương khác, hãy xem bài viết Các tuỳ chọn tìm kiếm tại địa phương.
Các ví dụ ở trên cũng cho phép ghi nhật ký tìm kiếm. Mặc dù không nhất thiết phải ghi nhật ký, nhưng tính năng này có thể hữu ích cho việc gỡ lỗi.
Khi chạy chương trình sau khi thực hiện các thay đổi ở trên, bạn sẽ nhận được giải pháp sau, giải pháp này ngắn hơn so với giải pháp được hiển thị trong phần trước.
Objective: 2672 Route: 0 -> 3 -> 276 -> 4 -> 5 -> 6 -> 8 -> 7 -> 9 -> 10 -> 11 -> 14 -> 12 -> 13 -> 23 -> 22 -> 24 -> 21 -> 25 -> 26 -> 27 -> 28 -> 125 -> 126 -> 127 -> 20 -> 19 -> 130 -> 129 -> 128 -> 153 -> 154 -> 152 -> 155 -> 151 -> 150 -> 177 -> 176 -> 175 -> 180 -> 161 -> 160 -> 174 -> 159 -> 158 -> 157 -> 156 -> 118 -> 119 -> 120 -> 121 -> 122 -> 123 -> 124 -> 29 -> 30 -> 31 -> 32 -> 33 -> 34 -> 35 -> 36 -> 37 -> 38 -> 39 -> 40 -> 41 -> 42 -> 59 -> 60 -> 58 -> 43 -> 44 -> 45 -> 46 -> 47 -> 48 -> 49 -> 50 -> 51 -> 52 -> 53 -> 54 -> 55 -> 56 -> 57 -> 67 -> 68 -> 66 -> 69 -> 70 -> 71 -> 72 -> 73 -> 75 -> 74 -> 76 -> 77 -> 78 -> 80 -> 81 -> 88 -> 79 -> 92 -> 93 -> 94 -> 95 -> 96 -> 97 -> 98 -> 99 -> 100 -> 101 -> 102 -> 91 -> 90 -> 89 -> 108 -> 111 -> 87 -> 82 -> 83 -> 86 -> 112 -> 115 -> 85 -> 84 -> 64 -> 65 -> 63 -> 62 -> 61 -> 117 -> 116 -> 114 -> 113 -> 110 -> 109 -> 107 -> 103 -> 104 -> 105 -> 106 -> 173 -> 172 -> 171 -> 170 -> 169 -> 168 -> 167 -> 166 -> 165 -> 164 -> 163 -> 162 -> 187 -> 188 -> 189 -> 190 -> 191 -> 192 -> 185 -> 186 -> 184 -> 183 -> 182 -> 181 -> 179 -> 178 -> 149 -> 148 -> 138 -> 137 -> 136 -> 266 -> 267 -> 135 -> 134 -> 268 -> 269 -> 133 -> 132 -> 131 -> 18 -> 17 -> 16 -> 15 -> 270 -> 271 -> 272 -> 273 -> 274 -> 275 -> 259 -> 258 -> 260 -> 261 -> 262 -> 263 -> 264 -> 265 -> 139 -> 140 -> 147 -> 146 -> 141 -> 142 -> 145 -> 144 -> 198 -> 197 -> 196 -> 193 -> 194 -> 195 -> 200 -> 201 -> 199 -> 143 -> 202 -> 203 -> 204 -> 205 -> 206 -> 207 -> 252 -> 253 -> 256 -> 257 -> 255 -> 254 -> 251 -> 208 -> 209 -> 210 -> 211 -> 212 -> 213 -> 214 -> 215 -> 216 -> 217 -> 218 -> 219 -> 220 -> 221 -> 222 -> 223 -> 224 -> 225 -> 226 -> 227 -> 232 -> 233 -> 234 -> 235 -> 236 -> 237 -> 230 -> 231 -> 228 -> 229 -> 250 -> 245 -> 238 -> 239 -> 240 -> 241 -> 242 -> 243 -> 244 -> 246 -> 249 -> 248 -> 247 -> 277 -> 278 -> 2 -> 279 -> 1 -> 0
Để biết thêm các tuỳ chọn tìm kiếm, hãy xem Tuỳ chọn định tuyến.
Các thuật toán tốt nhất hiện nay thường có thể giải quyết các thực thể TSP bằng hàng chục nghìn nút. (Bản ghi tại thời điểm ghi là phiên bản pla85900 trong TSPLIB, một ứng dụng VLSI có 85.900 nút. Đối với một số trường hợp với hàng triệu nút, các giải pháp được đảm bảo nằm trong khoảng 1% tham quan tối ưu.)
Điều chỉnh tỷ lệ ma trận khoảng cách
Vì trình giải mã định tuyến hoạt động trên các số nguyên, nên nếu ma trận khoảng cách có các mục không phải số nguyên, thì bạn phải làm tròn khoảng cách đến số nguyên. Nếu một số khoảng cách nhỏ, việc làm tròn có thể ảnh hưởng đến giải pháp.
Để tránh vấn đề khi làm tròn, bạn có thể scale ma trận khoảng cách: nhân tất cả các mục của ma trận với một số lớn – chẳng hạn như 100. Hàm này nhân chiều dài của mọi tuyến đường với hệ số 100 nhưng không thay đổi giải pháp. Ưu điểm là bây giờ khi bạn làm tròn các mục nhập ma trận, lượng làm tròn (tối đa là 0,5) rất nhỏ so với khoảng cách, vì vậy sẽ không ảnh hưởng đáng kể đến giải pháp.
Nếu bạn điều chỉnh ma trận khoảng cách, bạn cũng cần thay đổi máy in giải pháp để chia độ dài tuyến đường theo tỷ lệ cho hệ số tỷ lệ để máy in hiển thị khoảng cách theo tỷ lệ của các tuyến.