本節提供範例，說明如何解決下方地圖所示地點的旅遊專員問題 (TSP)。
下列各節將介紹使用 OR-Tools 來解決 TSP 的 Python、C++、Java 和 C# 程式
建立資料
以下程式碼會建立問題的資料。
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;
};
「距離矩陣」是一個陣列，其 i、j 項目是指從位置 i 到位置 j 的距離，陣列索引以下列順序對應位置：
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
這類資料也包括：
- 問題中的車輛數，也就是 1，因為這是 TSP。(針對車輛轉送問題 (VRP)，車輛數量可以大於 1)。
- 路徑：路線的起點和終點。這裡的庫碼為 0，相當於紐約。
建立距離矩陣的其他方法
在此範例中，距離矩陣已明確定義距離。您也可以使用函式來計算不同地點之間的距離，例如使用 Euclidean 公式表示平面上兩點之間的距離。不過，還是能預先計算位置之間的所有距離，並將這些距離儲存在矩陣中，而不是在執行階段計算。如需透過此方式建立距離矩陣的範例，請參閱範例：鑽電路板一文。
另一種方法是使用 Google Maps Distance Matrix API，以動態的方式建立距離 (或交通時間) 矩陣以轉送路線問題。
建立轉送模型
程式主要部分中的下列程式碼會建立索引管理員 (manager) 和轉送模型 (routing)。manager.IndexToNode 方法會將解題工具的內部索引 (您可以放心忽略) 轉換為位置的數字。位置數字對應距離矩陣的索引。
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);
RoutingIndexManager 的輸入：
- 距離矩陣的列數，也就是地點數量 (包括車庫)。
- 問題的車輛數量。
- 與儲存區相對應的節點。
建立距離回呼
如要使用轉送解題工具，您必須建立距離 (或大眾運輸) 回呼：這個函式可接受任何位置組合，並傳回這些地點之間的距離。最簡單的方法是使用距離矩陣。
下列函式會建立回呼，並將該函式註冊為 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);
在這個範例中，弧形評估工具是 transit_callback_index，這是距離距離回呼的內部解析器。也就是說，兩個位置之間的移動費用只是這兩個地點之間的距離。不過一般來說，成本通常也會受到其他因素影響。
此外，您也可以使用 routing.SetArcCostEvaluatorOfVehicle() 方法定義多個弧形成本評估工具，以取決於在不同地點之間行經的車輛。舉例來說，如果車輛的時速不同，您可以將地點之間的交通費用定義為距離 (即行車速度) 除以車速。
設定搜尋參數
以下程式碼會設定預設搜尋參數和尋找第一個解決方案的經驗法則：
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;
程式碼會將第一個解決方案策略設為 PATH_CHEAPEST_ARC，透過重複新增最小權重的邊緣，與解題工具的先前路徑 (除了在廢棄物庫除外) 重複加入，以建立解題工具的初始路徑。如需其他選項的資訊，請參閱第一個解決方案策略。
新增解決方案印表機
顯示解題工具傳回的解決方案的函式如下所示。這個函式會從解決方案擷取路徑並列印至主控台。
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);
}
這個函式會顯示最佳路線及其距離，由 ObjectiveValue() 提供。
解決並列印解決方案
最後，您可以呼叫解題工具並列印解決方案：
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);
這麼做會傳回解決方案，並顯示最佳路線。
執行程式
當您執行這些程式時，它們會顯示下列輸出結果。
Objective: 7293 miles Route for vehicle 0: 0 -> 7 -> 2 -> 3 -> 4 -> 12 -> 6 -> 8 -> 1 -> 11 -> 10 -> 5 -> 9 -> 0
在本範例中，只有一個路徑是 TSP，因此只有一個路徑。但是，在一般的車道路線問題中，解決方案包含多個路徑。
將路徑儲存至清單或陣列
除了直接列印解決方案之外，您也可以將路徑 (或 VRP 的路徑) 儲存到清單或陣列中。這種做法能讓您妥善設定路線，以便日後使用時執行。例如，您可以使用不同參數執行多次程式，並將傳回的解決方案中的路徑儲存到檔案中進行比較。
以下函式會將解決方案的路徑儲存到任何 VRP (可能是多輛車) 中，並以清單 (Python) 或陣列 (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;
}
您可以使用這些函式，在「轉送」區段中的任何 VRP 範例中取得路徑。
以下程式碼會顯示路徑。
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];
}
}
在目前的範例中，此程式碼會傳回下列路徑：
Route 0 [0, 7, 2, 3, 4, 12, 6, 8, 1, 11, 10, 5, 9, 0]
作為練習，請修改上述程式碼的格式，讓輸出的格式與程式的解決方案印表機相同。
完成計畫
完整的 TSP 計畫如下。
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);
}
}
範例：鑽電路板
下一個範例涉及透過自動化鑽頭在電路板上鑽孔。問題是，找出鑽頭在最短的路板上移動，以便鑽出所有必要的孔。此範例擷取自 TSPLIB，這是 TSP 問題的程式庫。
以下是顯示空洞地點的散佈圖：
以下各節說明使用解題工具的預設搜尋參數，能為電路板問題找出良好解決方案的程式。之後，我們將示範如何變更搜尋策略，找出更適合的解決方案。
建立資料
問題資料由飛機中的 280 點構成，如上圖所示。程式會在與飛機點的對應點陣列中建立陣列，如下所示。
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;
};
計算距離矩陣
以下函式會計算資料中兩個點之間的 Euclidean 距離，並儲存在陣列中。由於轉送解析器是處理整數，因此函式會將計算距離四捨五入為整數。本示例中的捨入結果不會影響解決方案，但在其他情況下也可能受到影響。請參閱縮放距離矩陣，瞭解如何避免可能四捨五入的問題。
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;
}
新增距離回呼
建立距離回呼的程式碼幾乎與前例相同。但在這種情況下，程式會在呼叫回呼之前呼叫計算距離矩陣的函式。
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);
解決方案印表機
下列函式會將解決方案列印至主控台。為了提高輸出內容的精簡程度，函式只會顯示路徑中的位置索引。
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);
}
主函式
主函式基本上與上一個範例中的函式相同，但還包含呼叫建立距離矩陣的函式。
執行程式
完整計畫請參閱下一節。當您執行該程式時，會顯示下列路徑：
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
以下是對應路徑的圖表：
OR-Tools 程式庫可快速找到上述導覽：一般電腦不到一秒即可完成。上述遊覽的總長度為 2790。
完成計畫
以下是電路板範例的完整程式。
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);
}
}
變更搜尋策略
轉送解題工具不一定會將最佳解決方案傳回至 TSP，因為轉送問題在計算上是難免。例如，上一個範例傳回的解決方案並非最佳路徑。
如要尋找更好的解決方案，您可以使用更進階的搜尋策略，稱為「引導式本機搜尋」，讓解題工具逃脫當地最低值。這個解決方案比所有附近的路徑短，但並非全域最低限度。將地點從本地最低限度移開後，解題工具會繼續搜尋。
以下範例說明如何設定電路板範例的引導式本機搜尋。
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
在程式開頭加入下列「匯入」陳述式：import com.google.protobuf.Duration;請依照以下方式設定搜尋參數：
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#
在程式開頭加入下列幾行：using Google.Protobuf.WellKnownTypes; // Duration然後依以下方式設定搜尋參數：
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;
如需其他本地搜尋策略，請參閱區域搜尋選項。
以上範例也會啟用搜尋功能的紀錄功能。雖然不需要記錄，但對於偵錯而言非常實用。
進行上述變更後，執行程式時，您會收到以下解決方案，相較於上一節介紹的解決方案更短。
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
如需更多搜尋選項，請參閱轉送選項一文。
最佳演算法現在可以定期處理數萬個節點的 TSP 執行個體。(撰寫期間的記錄為 TSPLIB 中的 pla85900 執行個體，TSPLIB 是具有 85,900 個節點的 VLSI 應用程式)。針對使用數百萬個節點的執行個體，這個解決方案已保證在最佳導覽的 1% 以內。)
縮放距離矩陣
由於轉送解析器是處理整數，因此，如果距離矩陣包含非整數項目，您就必須將距離四捨五入為整數。如果有些差異比較小，則四捨五入會影響解決方案。
如要避免四捨五入的問題，您可以 scale 距離矩陣：將矩陣的所有項目乘以 100。這會讓任何路徑的長度乘以 100 倍，但不會改變解決方案。這種做法的好處是，當您將矩陣項目四捨五入時，與距離相差的小數值 (最多為 0.5) 是很小的，因此對解決方案沒有太大的影響。
縮放距離矩陣時，您也必須變更解決方案印表機，將縮放後的路徑長度除以縮放比例係數，這樣才能顯示該路徑未縮放的距離。