下载 Notebook 下载完整案例

带颜色约束的车辆排序问题¶

类别： 排程

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

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

问题描述¶

带涂装车间批次约束的车辆排序问题 涉及一组汽车的生产调度。这些汽车并不完全相同,基本车型有不同的可选配置。装配线上设有不同的工位以安装各种选装件(空调、变速箱、颜色等)。

该问题最初由汽车制造商雷诺提交给法国运筹学与决策支持协会(ROADEF) 2005 年挑战赛。

学习要点¶

数据¶

数据文件的格式如下:

第 1 行:车辆数量、选项数量、类别数量、最大涂装批次大小、目标顺序、起始位置。
对于每个选项:在该块中具有该选项的最大车辆数、该块的大小、该选项是否为高优先级。
对于每个类别:颜色、该类别的车辆数量、对于每个选项,此类别是否需要该选项(1 或 0)。
对于起始位置之前的每个位置:最初计划生产的类别

更多细节,请参阅挑战赛网站。

建模思路¶

带涂装车间批次约束的车辆排序问题的 OptAgent 模型使用列表决策变量表示车辆序列。列表中的第 i 个元素对应于第 i 个生产的车辆的索引。由于每辆车必须恰好生产一次,因此我们对该列表变量施加排列约束。

由该序列,我们可以针对每个选项与生产线上的每个位置,计算在该位置开始的窗口中具有该选项的车辆数。据此可以推导出每个选项与每个窗口的违反数。类似地,我们使用 neq 与 or 算子对涂装车间批次大小施加约束。

尽管该问题是一个纯可行性问题,我们仍选择添加目标,以最小化所有选项与所有窗口的容量违反数之和。事实上,没有容量违反更像是一种"业务"约束,而非结构性约束。如果存在少量违反,装配线仍可继续生产,只需暂时调整生产节奏即可。

我们定义三个目标:

最小化高优先级选项的窗口容量违反数
最小化低优先级选项的窗口容量违反数
最小化颜色变更次数

这三个目标按字典序进行优化:声明顺序即定义了其重要性顺序。

Python 实现¶

from pathlib import Path

from optagent import OptModel, solve



COLOR_HIGH_LOW, HIGH_LOW_COLOR, HIGH_COLOR_LOW, COLOR_HIGH, HIGH_COLOR = range(5)


def read_instance(filename):
    values = [int(value) for value in Path(filename).read_text().split()]
    iterator = iter(values)
    positions, options, classes = next(iterator), next(iterator), next(iterator)
    batch_limit, objective_order, start = next(iterator), next(iterator), next(iterator)
    capacities, windows, priority = [], [], []
    has_low_priority_options = False
    for _ in range(options):
        capacities.append(next(iterator))
        windows.append(next(iterator))
        is_priority = next(iterator) == 1
        priority.append(is_priority)
        has_low_priority_options |= not is_priority
    if not has_low_priority_options:
        if objective_order == COLOR_HIGH_LOW:
            objective_order = COLOR_HIGH
        elif objective_order == HIGH_COLOR_LOW:
            objective_order = HIGH_COLOR
        elif objective_order == HIGH_LOW_COLOR:
            objective_order = HIGH_COLOR
    colors, option_data = [], []
    for _ in range(classes):
        colors.append(next(iterator))
        next(iterator)
        option_data.append([next(iterator) for _ in range(options)])
    initial = [next(iterator) for _ in range(positions)]
    return positions, batch_limit, objective_order, start, capacities, windows, priority, colors, option_data, initial


def main(instance_file, time_limit=20):
    n, batch, objective_order, start, capacities, windows, priority, colors_data, option_data, initial = read_instance(
        instance_file
    )
    model = OptModel()
    # sequence[i] = j if class initially planned on position j is produced on position i
    sequence = model.list(n)
    # sequence is a permutation of the initial production plan, all indexes must appear exactly once
    model.constraint(model.partition(sequence))
    
    # Past classes (before startPosition) can not move later
    [model.constraint(sequence[p] == p) for p in range(start)]

    # Create arrays to be able to access them with "at" operators
    classes, colors, options = model.array(initial), model.array(colors_data), model.array(option_data)
    high, low = [], []
    for option, (limit, width, is_high) in enumerate(zip(capacities, windows, priority)):
        for begin in range(start - width + 1, n):
            members = [position for position in range(begin, begin + width) if 0 <= position < n]
            count = model.sum(options[classes[sequence[position]]][option] for position in members)
            (high if is_high else low).append(model.max(count - limit, 0))
    color_changes = [
        colors[classes[sequence[p]]] != colors[classes[sequence[p + 1]]] for p in range(max(0, start - 1), n - 1)
    ]
    # Keep Hexaly's exclusive upper bound for strict source parity. Since range excludes
    # its stop, the original example may omit the final mathematically valid window.
    for begin in range(start, n - batch - 1):
        model.constraint(
            model.or_(
                colors[classes[sequence[begin + offset]]]
                != colors[classes[sequence[begin + offset + 1]]]
                for offset in range(batch)
            )
        )
    color_objective, high_objective, low_objective = model.sum(*color_changes), model.sum(*high), model.sum(*low)
    objective_map = {
        COLOR_HIGH_LOW: (color_objective, high_objective, low_objective),
        HIGH_LOW_COLOR: (high_objective, low_objective, color_objective),
        HIGH_COLOR_LOW: (high_objective, color_objective, low_objective),
        COLOR_HIGH: (color_objective, high_objective),
        HIGH_COLOR: (high_objective, color_objective),
    }
    for objective in objective_map[objective_order]:
        model.minimize(objective)
    solution = solve(model, time_limit_s=float(time_limit))
    values = {'color': color_objective.value, 'high': high_objective.value, 'low': low_objective.value, 'sequence': sequence.value}
    print(
        f"Color = {values['color']}; High = {values['high']}; Low = {values['low']}; Status = {solution.feasible}"
    )
    return solution

本地运行¶

INSTANCE_DIR = Path.cwd() / "instances"

solution = main(INSTANCE_DIR / "022_3_4_EP_RAF_ENP.in", time_limit=1)

Starting OptAgent PORTFOLIO
Parameters: time_limit=1s threads=auto seed=0
Solve summary:
  status: NO_FEASIBLE_SOLUTION_FOUND
  improvements: initial=0 search=0
  evaluated: 0
  wall_time: 1s
  termination: wall_time_exhausted