问题描述¶
汽车排序问题 涉及安排一组汽车的生产顺序。这些汽车并非完全相同,在基本车型的基础上有不同的配置选项可供选择。装配线上有不同的工作站来安装各种选项(空调、天窗等)。这些工作站有最大产能限制,它们最多能处理装配线上一定比例的车辆。因此,必须将汽车排成一个序列,以使每个工作站的产能都不会被超过。例如,如果某个工作站最多能处理装配线上三分之二的车辆,那么在序列中任意连续 3 辆车的窗口内,至多只能有 2 辆车需要该选项。
学到的要点¶
- 使用 列表决策变量 来表示汽车的序列
- 区分 结构性约束与第一优先级目标
- 使用 非线性算子 来计算违规次数
建模思路¶
汽车排序问题的 OptAgent 模型使用一个 列表决策变量 来表示汽车的序列。列表的第 i 个元素对应于第 i 辆要生产的汽车的索引。使用 partition 算子,可以确保待生产的每辆汽车都出现在装配线上。
根据这个序列,我们可以对每个选项和装配线上的每个位置,计算出从该位置开始的窗口中具有该选项的车辆数量。然后我们可以推导出每个选项和每个窗口的违规数量。
尽管这个问题是一个纯可行性问题,我们仍然选择添加一个目标,即使所有选项和所有窗口的产能违规次数之和最小化。事实上,无产能违规更像是“业务”约束,而不是结构性约束。如果出现少量违规,装配线会减速但仍可继续运行。相反,在装配线上的某个位置同时放置两辆车在物理上是不可能的:这是一个结构性约束。有关高优先级目标和硬约束之间区别的更多信息,请参阅文档中的 此章节。
Python 实现¶
from pathlib import Path
from optagent import OptModel, solve
def read_integers(filename):
return [
int(value)
for value in Path(filename).read_text(encoding="utf-8").split()
]
def read_instance(instance_file):
file_it = iter(read_integers(instance_file))
nb_positions = next(file_it)
nb_options = next(file_it)
nb_classes = next(file_it)
max_cars_per_window = [next(file_it) for _ in range(nb_options)]
window_size = [next(file_it) for _ in range(nb_options)]
nb_cars = []
options = []
initial_sequence = []
for class_index in range(nb_classes):
next(file_it)
nb_cars.append(next(file_it))
options.append([next(file_it) == 1 for _ in range(nb_options)])
initial_sequence.extend([class_index] * nb_cars[class_index])
return (
nb_positions,
nb_options,
max_cars_per_window,
window_size,
options,
initial_sequence,
)
def main(instance_file, output_file=None, time_limit=60):
(
nb_positions,
nb_options,
max_cars_per_window,
window_size,
options_data,
initial_sequence,
) = read_instance(instance_file)
model = OptModel()
# sequence[i] = j if class initially planned on position j is produced on position i
sequence = model.list(nb_positions)
# sequence is a permutation of the initial production plan, all indexes must appear exactly once
model.constraint(model.partition(sequence))
# Create arrays to be able to access them with "at" operators
initial_array = model.array(initial_sequence)
option_array = model.array(options_data)
# Number of cars with option o in each window
nb_cars_windows = [None] * nb_options
for option in range(nb_options):
nb_cars_windows[option] = [None] * nb_positions
for start in range(nb_positions - window_size[option] + 1):
nb_cars_windows[option][start] = model.sum(
option_array[initial_array[sequence[start + offset]]][option]
for offset in range(window_size[option])
)
# Number of violations of option o capacity in each window
nb_violations_windows = [None] * nb_options
for option in range(nb_options):
nb_violations_windows[option] = [None] * nb_positions
for start in range(nb_positions - window_size[option] + 1):
nb_violations_windows[option][start] = model.max(
nb_cars_windows[option][start] - max_cars_per_window[option],
0,
)
total_violations = model.sum(
nb_violations_windows[option][start]
for option in range(nb_options)
for start in range(nb_positions - window_size[option] + 1)
)
model.minimize(total_violations)
solution = solve(model, time_limit_s=float(time_limit))
values = {'violations': total_violations.value, 'sequence': sequence.value}
print(f"Violations = {values['violations']}; Status = {solution.feasible}")
sequence_text = " ".join(
str(initial_sequence[index]) for index in values["sequence"]
)
print(sequence_text)
if output_file is not None:
Path(output_file).write_text(
f"{int(values['violations'])}\n{sequence_text}\n", encoding="utf-8"
)
return solution
本地运行¶
INSTANCE_DIR = Path.cwd() / "instances"
solution = main(INSTANCE_DIR / "4_72.in", time_limit=5)