关于Google OR-Tools CVRP求解器的两大疑问：目标与depot设置

1. 当前代码的优化目标确认 #

当前代码已经实现了所有路径总距离的优化，具体说明：

• OR-Tools的RoutingModel默认优化目标是所有弧段（节点间路径）的成本总和，也就是所有车辆路径的总距离之和。
• SetGlobalSpanCostCoefficient()是专门用于切换优化目标为「最长单车辆路径距离」（最小化所有车辆路径中的最大长度）的方法，你的代码未调用该方法，因此默认目标就是总距离。
• 后续扩展多车辆时，只要保持SetArcCostEvaluatorOfAllVehicles使用距离回调，求解器依然会自动优化所有车辆路径的总距离之和，无需额外调整。

2. data["depot"] = 0的含义 #

这个参数的作用是指定求解器使用「节点索引为0的节点」作为所有车辆的起点和终点，与该节点的坐标是否为(0,0)完全无关：

• 你的distance_matrix是基于生成的客户位置（包含非零坐标的depot）计算的，其中索引0对应的就是你定义的depot节点的距离数据（比如distance_matrix[0][i]是depot到第i个节点的距离）。
• 求解器会让所有车辆从这个索引对应的节点出发，完成配送后必须返回该节点，不需要修改坐标把depot设为(0,0)，只要保证distance_matrix的索引和节点顺序对应即可。

附当前代码 #

def create_data_model():
    data = {}
    data["distance_matrix"] = createDistanceMatrix(customers).tolist()
    data["demands"] = customers['Demand'].astype(int).tolist()
    data["vehicle_capacities"] = [1000]
    data["num_vehicles"] = 1
    data["depot"] = 0
    return data

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    total_distance = 0
    total_load = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"Route for vehicle {vehicle_id}:\n"
        route_distance = 0
        route_load = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_load += data["demands"][node_index]
            plan_output += f" {node_index} Load({route_load}) -> "
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n"
        plan_output += f"Distance of the route: {route_distance}m\n"
        plan_output += f"Load of the route: {route_load}\n"
        print(plan_output)
        total_distance += route_distance
        total_load += route_load
    print(f"Total distance of all routes: {total_distance}m")
    print(f"Total load of all routes: {total_load}")

def main():
    """Solve the CVRP problem."""
    # 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)

    # Create and register a transit callback.
    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)

    # Add Capacity constraint.
    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data["demands"][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data["vehicle_capacities"],  # vehicle maximum capacities
        True,  # start cumul to zero
        "Capacity",
    )

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    search_parameters.time_limit.FromSeconds(5)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)

内容的提问来源于stack exchange，提问作者Levi Rohring