or-tools 为 tsp 设置自定义成本

Question

我正在做一个需要解决流程中的 TSP 的项目。为此，我找到了 or-tools。据我了解，tsp 的 or-tools 使用距离作为成本，这意味着任何两个位置之间的旅行成本就是它们之间的距离。我需要手动设置成本，因为我希望成本受其他一些因素的影响，而不仅仅是距离。这是在 or-tools 中设置 TSP 成本的代码。

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)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

关于这段代码我有 2 个问题：
1- distance_callback 是一个函数。为什么在 routing.RegisterTransitCallback(distance_callback) 中没有参数调用函数？
2- 我如何更改此代码以设置我的自定义成本？

我有一个自定义成本矩阵，我尝试用我自己的成本矩阵 return data['cost_matrix'][from_node][to_node] 替换 return data['distance_matrix'][from_node][to_node]，但它并没有正常工作。

Answer 1

您可以注册每辆车的距离回调。

参见：the SetArcCostEvaluatorOfVehicle method

Answer 2

此回调将由 C++ 库调用，python 包是一个 native 包，它使用 SWIG 包装了 C++ 库。
从技术上讲，求解器只需要您注册函数（或 lambda），该函数采用两个参数（int64 from_index、int64 to_index）并返回一个整数 (int64).
一个好的起点

cost_callback_indices = []
for vehicle_idx in range(data['vehicle_number']):
    def vehicle_cost_callback(from_index, to_index, i=vehicle_idx):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][i][from_node][to_node]
    cost_callback_index = routing.RegisterTransitCallback(vehicle_cost_callback)
    cost_callback_indices.append(cost_callback_index)
    routing.SetArcCostEvaluatorOfVehicle(cost_callback_index, vehicle_idx)

参见：https://github.com/google/or-tools/issues/1795#issue-540774218

or-tools 为 tsp 设置自定义成本

or-tools setting custom cost for tsp

traveling-salesman

python-3.x

or-tools