如何保证ortools计算生成的路线不会穿过指定的禁行区域

OR-Tools 的 Routing 路由库原生不支持直接传入几何避让区域，它的核心定位是解决基于图模型的 TSP/VRP 类组合优化问题，仅感知节点 ID、边的成本和边的可用性，不理解节点对应的几何坐标和空间避让规则。

你可以通过以下方案在路线计算阶段就实现避让限制，不需要事后校验修正：

• 预计算所有节点对的直连线段是否穿过白色规避区域，需自行实现线段和掩码的碰撞检测函数，输入两个点的坐标和二值掩码，输出线段是否合法（未穿过避让区）
• 对所有判定为不合法的边，有两种处理方式：
  1. 成本惩罚法：在距离矩阵中将该边的成本设置为远高于所有合法路径总长度的极大值，OR-Tools 求解时会自动规避这类高成本边
  2. 直接禁用边：调用 OR-Tools 的 API 直接移除对应边的可选性，实现更严格的限制，不需要依赖成本权重
• 如果 SLIC 分割点密度较低，就算是两个合法节点的直连边也会穿过避让区，可以预先对这类边计算沿避让区边缘的绕行路径长度，用实际绕行长度替换欧氏距离填入距离矩阵即可

以下是现有代码的修改示例，采用直接禁用边+成本惩罚的双重方案：

// 需自行实现该碰撞检测函数，返回true表示线段穿过避让区
bool IsSegmentCrossForbidden(int from_x, int from_y, int to_x, int to_y, const Image& mask) {
    // 可实现线段采样检测/掩码边界碰撞检测逻辑
}

void GConstraintSolver::compute_path(const std::vector<std::vector<int>>& locations, Path &path, const Image& mask) {
    const int num_vehicles = 1;
    const operations_research::RoutingIndexManager::NodeIndex depot{0};
    int node_num = (int)locations.size();
    operations_research::RoutingIndexManager manager(node_num, num_vehicles, depot);
    operations_research::RoutingModel routing(manager);

    const auto distance_matrix = ComputeEuclideanDistanceMatrix(locations);
    const int64_t FORBIDDEN_COST = std::numeric_limits<int64_t>::max() / 2;

    const int transit_callback_index = routing.RegisterTransitCallback(
            [&distance_matrix, &manager, &locations, &mask, FORBIDDEN_COST](int64_t from_index, int64_t to_index) -> int64_t {
                auto from_node = (size_t)manager.IndexToNode(from_index).value();
                auto to_node = (size_t)manager.IndexToNode(to_index).value();
                // 先判断线段是否合法
                if (IsSegmentCrossForbidden(locations[from_node][0], locations[from_node][1],
                                            locations[to_node][0], locations[to_node][1], mask)) {
                    return FORBIDDEN_COST;
                }
                return distance_matrix[from_node][to_node];
            });

    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);
    
    // 可选：直接禁用所有不合法的边，避免求解器误选
    for (int from = 0; from < node_num; from++) {
        int64_t from_index = manager.NodeToIndex(operations_research::RoutingIndexManager::NodeIndex(from)).value();
        for (int to = 0; to < node_num; to++) {
            if (from == to) continue;
            if (IsSegmentCrossForbidden(locations[from][0], locations[from][1],
                                        locations[to][0], locations[to][1], mask)) {
                routing.NextVar(from_index).RemoveValue(to);
            }
        }
    }

    operations_research::RoutingSearchParameters searchParameters = operations_research::DefaultRoutingSearchParameters();
    searchParameters.set_first_solution_strategy(
            operations_research::FirstSolutionStrategy::PATH_CHEAPEST_ARC);
    const operations_research::Assignment *solution = routing.SolveWithParameters(searchParameters);
    build_path(manager, routing, *solution, locations, path, mask);
}

注意事项 #

• 实现线段碰撞检测时可以根据精度要求调整采样步长，若避让区为规则多边形，也可以采用更高效的多边形碰撞检测逻辑
• 若设置直接禁用边，需保证整个节点图是连通的，否则求解器会返回无解，这种情况可以降低SLIC分割步长增加节点密度，保证合法路径连通性
• FORBIDDEN_COST 不要设置为int64的最大值，避免求解器内部计算成本总和时出现溢出问题

内容的提问来源于stack exchange，提问作者Doug. B.