设施选址问题 (FLP)¶

类别： 选址

使用 OptAgent 的 Python 接口描述变量、约束与目标。

问题与原始示例来源：Hexaly Code Templates。

问题描述¶

设施选址问题 (FLP) 的定义如下。给定一组地点以及每对地点之间的运输成本,从中选取 p 个地点作为设施,以最小化运输成本。一个地点的运输成本等于其到最近设施的距离。因此,目标是为设施提供最优布局以最小化运输成本。该问题也称为 P-Median 问题。

学到的要点¶

添加布尔决策变量来建模一个地点是否被选为设施
使用 iif 和 min 算子计算每个地点到最近设施的运输成本
使用 OptAgent 的 ModelBuilder 建模、solve 求解并读取解中的表达式值

数据¶

我们提供的数据文件来自 OR-LIB。其格式如下:

地点数量
原始实例中的边数
要选择的设施数量
距离矩阵,使用 Floyd 算法从原始文件计算得出。

建模思路¶

设施选址问题 (FLP) 的 OptAgent 模型使用布尔决策变量来表示每个地点是否被选为设施。我们将这些布尔值的和约束为不超过 p,以确保设施数量最多为 p。

然后我们需要计算运输成本。注意,在模型中无需为每个地点定义其最近设施,只需计算该地点与其最近设施之间的距离即可。利用三元算子,我们可以计算地点 i 与设施 j 之间的运输成本:若 j 为设施则等于 i 与 j 的距离,否则为有限的大惩罚值 2 * max_distance。利用对所有可能设施的 min 算子,我们可以计算地点 i 与其最近设施之间的距离,对所有 i 均如此。

最后,需要最小化的目标即为这些运输成本之和。

Python 实现¶

from pathlib import Path

from optagent import OptModel, solve




def read_instance(instance_file):
    file_it = iter(int(value) for value in Path(instance_file).read_text().split())
    n = next(file_it)
    next(file_it)  # Skip the number of edges.
    p = next(file_it)
    distances = [[next(file_it) for _ in range(n)] for _ in range(n)]
    max_distance = max(max(row) for row in distances)
    return n, p, max_distance, distances


def main(instance_file, output_file=None, time_limit=20):
    n, p, max_distance, distances = read_instance(instance_file)

    model = OptModel()
    # One variable for each location: 1 if facility, 0 otherwise
    is_open = [model.bool() for _ in range(n)]
    opened_locations = model.sum(is_open)
    # Keep the original Hexaly formulation: select no more than p facilities.
    # The finite 2 * max_distance penalty makes fewer (or no) open facilities feasible.
    # Nonnegative distances make extra facilities non-worsening, but a time-limited
    # heuristic solve may return such a feasible solution before finding a better one.
    model.constraint(opened_locations <= p)

    # Costs between location i and j is w[i][j] if j is a facility or 2 * wmax if not
    location_costs = []
    for location in range(n):
        # 这里相当于直接根据布尔变量取值来进行不同罚分的设定
        candidate_costs = [
            model.iif(is_open[facility], distances[location][facility], 2 * max_distance)
            for facility in range(n)
        ]
        # Cost between location i and the closest facility
        location_costs.append(model.min(candidate_costs))

    total_cost = model.sum(location_costs)
    model.minimize(total_cost)

    solution = solve(model, time_limit_s=float(time_limit))
    values = {'total_cost': total_cost.value, **{f'is_open_{i}': variable.value for i, variable in enumerate(is_open)}}
    facilities = [i for i in range(n) if values[f"is_open_{i}"]]
    result_text = (
        f"Total cost = {values['total_cost']}; Facilities = {facilities}; "
        f"Status = {solution.feasible}"
    )
    print(result_text)
    if output_file is not None:
        Path(output_file).write_text(
            f"{values['total_cost']}\n{' '.join(map(str, facilities))}\n",
            encoding="utf-8",
        )
    return solution

本地运行¶

INSTANCE_DIR = Path.cwd() / "instances"

# 在当前建模下，什么都不做也是可行解
solution = main(INSTANCE_DIR / "pmed1.in", time_limit=5)