问题描述¶
在卡车装载问题中，给定的一组物品需要装载到卡车中。因此，每件物品必须恰好被分配到一辆卡车。
每辆卡车有两层：底层和上层。每一层具有相同的物品位置数量，每辆卡车也具有相同的载重能力。因此，分配给某辆卡车的物品总重量不得超过该载重能力。
除重量外，物品还可能存在堆放限制：
- 类型 1 物品必须放置在底层，并且其上方不能再放置其他物品，称为 “Alone（独占）” 物品。
- 类型 2 物品必须放置在底层，但其上方可以再放置其他物品，称为 “Floor（底层）” 物品。
- 类型 3 物品没有任何堆放限制，称为 “No-restriction（无限制）” 物品。
- 类型 4 物品上方不能再放置其他物品，但可以放在底层或上层，称为 “Delicate（易碎）” 物品。
此外，卡车的上层只有在底层被装满时才能使用。目标是最小化所使用的卡车数量。
学习要点¶
- 使用 set 决策变量建模各卡车中所装物品
- 使用 lambda 函数计算卡车总重量并强制执行堆放限制
- 在后处理函数中使用 OptAgent 找到的解生成具体摆放
建模思路¶
卡车装载问题的 OptAgent 模型使用 set 决策变量表示分配给每辆卡车的物品集合。约束这些 set 变量构成 partition（划分），以确保每件物品恰好属于一辆卡车。
我们使用对集合的 sum（求和） 运算符以及一个返回指定物品索引对应重量的 lambda 函数来计算每辆卡车的总重量。需要注意的是，该求和的项数在搜索过程中会随着集合大小变化而变化。然后约束总重量不超过卡车的载重能力。
“Alone” 和 “Floor” 物品必须位于其所在卡车的底层。因此，模型保证在任何卡车中它们都不超过每层的可用位置数。接着我们对 “Alone” 和 “Delicate” 物品添加类似的约束，因为它们上方不能再放置其他物品。
“Alone” 物品必须放置在底层，并且由于其上方不能再放置物品，因此会同时占用对应的上方位置。也就是说，它们占用两个位置单位而非一个。然后模型保证每辆卡车中被占用的位置数不超过总位置数。
我们使用 count（计数）运算符计算使用的卡车总数，该运算符返回集合中元素的数量。
该模型仅给出每辆卡车所装载的物品集合。物品在卡车内的具体摆放则由一个后处理函数另行计算。该函数先装载 “Alone” 和 “Floor” 物品以确保它们位于底层，然后装载 “No-restriction” 物品，最后装载必然位于最上层的 “Delicate” 物品。
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(filename):
file_it = iter(read_integers(filename))
nb_items = next(file_it)
truck_weight_capacity = next(file_it)
level_spots_count = next(file_it)
item_weights = []
item_categories = []
item_volumes = []
for _ in range(nb_items):
weight = next(file_it)
category = next(file_it)
item_weights.append(weight)
item_categories.append(category)
# An Alone item blocks a floor position and the position above it.
item_volumes.append(2 if category == 1 else 1)
return (
nb_items,
truck_weight_capacity,
level_spots_count,
item_weights,
item_categories,
item_volumes,
)
# Insert an item into the next free slot in the truck.
def place_first_available_pos(positions, item, level_spots_count):
if len(positions[0]) < level_spots_count:
positions[0].append(item)
else:
positions[1].append(item)
# The model assigns items to trucks; this builds a feasible two-level placement.
def inside_truck(truck_set, item_categories, level_spots_count):
# Split the items assigned to the truck by category
set_a = [] # Type 1: floor level and nothing above. Called "Alone" items
set_f = [] # Type 2: floor level. Called "Floor" items
set_n = [] # Type 3: no restriction. Called "No-restriction" items
set_d = [] # Type 4: nothing above. Called "Delicate" items
for i in truck_set:
category = item_categories[i]
if category == 1:
set_a.append(i)
elif category == 2:
set_f.append(i)
elif category == 3:
set_n.append(i)
else:
set_d.append(i)
# Initialize the two-level position list: positions[0] represents the floor level, and positions[1] the upper level
positions = [[], []]
#
# Assign positions to items, from the most constraining category to the least constraining one: A -> F -> N -> D
#
# Place all "Alone" items on the floor, and leave the corresponding upper positions empty (represented by -1)
for i in set_a:
positions[0].append(i)
positions[1].append(-1)
# Place all "Floor" items on the floor
for i in set_f:
positions[0].append(i)
# Place all "No-restriction" items at the first available position
for i in set_n:
place_first_available_pos(positions, i, level_spots_count)
# Place all "Delicate" items at the first available position
for i in set_d:
place_first_available_pos(positions, i, level_spots_count)
return positions
def pad_left(x, width):
return (" " if x == -1 else str(x)).rjust(width)
def main(input_file, output_file=None, time_limit=10):
(
nb_items,
truck_weight_capacity,
level_spots_count,
item_weights,
item_categories,
item_volumes,
) = read_instance(input_file)
# Bounds on the number of used trucks
nb_min_trucks = (sum(item_weights) + truck_weight_capacity - 1) // truck_weight_capacity
nb_max_trucks = nb_items
model = OptModel()
# trucks[k] is the set of items assigned to truck k.
trucks = [model.set(nb_items) for truck in range(nb_max_trucks)]
# Each item must be assigned to exactly one truck.
model.constraint(model.partition(trucks))
weights = model.array(item_weights)
categories = model.array(item_categories)
volumes = model.array(item_volumes)
weight_lambda = model.lambda_function(lambda item: weights[item // 1])
volume_lambda = model.lambda_function(lambda item: volumes[item // 1])
floor_lambda = model.lambda_function(lambda item: model.or_(categories[item // 1] == 1, categories[item // 1] == 2))
delicate_lambda = model.lambda_function(
lambda item: model.or_(categories[item // 1] == 1, categories[item // 1] == 4)
)
truck_weights = []
trucks_used = []
for truck, truck_items in enumerate(trucks):
truck_weight = model.sum(truck_items, weight_lambda)
truck_weights.append(truck_weight)
model.constraint(
truck_weight <= truck_weight_capacity,
)
model.constraint(
model.sum(truck_items, volume_lambda) <= 2 * level_spots_count,
)
model.constraint(
model.sum(truck_items, floor_lambda) <= level_spots_count,
)
model.constraint(
model.sum(truck_items, delicate_lambda) <= level_spots_count,
)
trucks_used.append(model.count(truck_items) > 0)
total_used_trucks = model.sum(trucks_used)
model.minimize(total_used_trucks)
solution = solve(
model,
time_limit_s=float(time_limit),
objective_threshold={0: nb_min_trucks},
)
if not solution.feasible:
print(f"No feasible loading found; Status = {solution.status}")
return solution
print_width = len(str(nb_items - 1)) + 2
lines = [f"Number of used trucks: {total_used_trucks.value}", ""]
for truck in range(nb_max_trucks):
if not trucks_used[truck].value:
continue
positions = inside_truck(trucks[truck].value, item_categories, level_spots_count)
separator = "-" * (level_spots_count * print_width)
lines.extend(
[
f"Truck weight: {truck_weights[truck].value}",
separator,
"".join(pad_left(item, print_width) for item in positions[1]),
"".join(pad_left(item, print_width) for item in positions[0]),
separator,
"",
]
)
result_text = "\n".join(lines) + "\n"
print(f"Status = {solution.status}")
print(result_text, end="")
if output_file is not None:
Path(output_file).write_text(result_text, encoding="utf-8")
return solution
INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)
solution_t60_00 = main(INSTANCE_DIR / "t60_00.txt", time_limit=1)