问题描述¶
我们定义团体座位预订背包问题 (GSR-KP) 如下。我们考虑一列座位数固定的火车，它需要停靠若干车站。在一组预订请求中，我们必须选择接受其中的一个子集。每个请求指定了一个团体人数和一个出行区间（从起始站到终点站）。对于每个团体，所分配的座位必须是相邻的。在整个路线上的任何位置，已占用的座位数都不能超过火车的座位容量。
目标是最大化整个行程的火车的总体利用率，以整个行程预订的座位总数来衡量。
学习要点¶
- 添加
optional_interval来为每个被选中的请求建模所分配的连续座位 - 使用
presence来检测某个请求是否被选中
数据¶
我们提供的实例来自 Clausen et al.。数据文件的格式如下：
第一行：预订请求的数量
第二行：
行程总车站数
火车的座位容量
接下来的每一行，对应每个请求：
行程经过的车站数
座位数
起始车站
（两个其他未使用的度量）
建模思路¶
团体座位预订背包问题 (GSR-KP) 的 OptAgent 模型使用 optional_interval variables 来表示分配给每个请求的连续座位。我们使用 presence 算子来检测某个请求是否被选中。
对于每个被选中的请求，对应 interval 的长度等于所需的座位数。
我们确保任意两个在行程上有重叠的被选中请求所分配的座位互不重叠。
目标是最大化火车的总体利用率。模型会计算最优利用率的一个简单上界，并将其作为 OptAgent 的 objective_threshold，在达到该上界时停止搜索。
Python 实现¶
from pathlib import Path
from optagent import OptModel, solve
def read_integers(filename):
return [int(value) for value in Path(filename).read_text().split()]
def read_instance(instance_file):
file_it = iter(read_integers(instance_file))
nb_requests = int(next(file_it))
nb_stations = int(next(file_it))
nb_seats = int(next(file_it))
nb_stations_request = [0] * nb_requests
nb_seats_request = [0] * nb_requests
first_station_request = [0] * nb_requests
for request in range(nb_requests):
nb_stations_request[request] = int(next(file_it))
nb_seats_request[request] = int(next(file_it))
first_station_request[request] = int(next(file_it))
next(file_it) # Skip unused value.
next(file_it) # Skip unused value.
# Requests that share at least one station segment.
sharing_station = [[] for _ in range(nb_requests)]
for first in range(nb_requests):
for second in range(first + 1, nb_requests):
if (
first_station_request[first] < first_station_request[second] + nb_stations_request[second]
and first_station_request[first] + nb_stations_request[first] > first_station_request[second]
):
sharing_station[first].append(second)
return (
nb_requests,
nb_stations,
nb_seats,
nb_stations_request,
nb_seats_request,
sharing_station,
)
def main(instance_file, output_file=None, time_limit=5):
(
nb_requests,
nb_stations,
nb_seats,
nb_stations_request,
nb_seats_request,
sharing_station,
) = read_instance(instance_file)
model = OptModel()
# 一个 optional_interval 同时表达了两个决策：要不要接受订单，以及接受以后安排到哪些座位
request_selected = [model.optional_interval(0, nb_seats) for _ in range(nb_requests)]
# A selected request occupies exactly its requested number of consecutive seats.
for request in range(nb_requests):
# 如果被接受，存在团体人数约束
model.constraint(
model.iif(
request_selected[request].presence(),
request_selected[request].length() == nb_seats_request[request],
True,
)
)
# Requests overlapping on the journey cannot occupy the same seats.
for first in range(nb_requests):
for second in sharing_station[first]:
both_selected = model.and_(
request_selected[first].presence(),
request_selected[second].presence(),
)
seats_disjoint = model.or_(
request_selected[second] < request_selected[first],
request_selected[first] < request_selected[second],
)
# 如果同时选中，要求两个座位 interval 不相交
model.constraint(model.iif(both_selected, seats_disjoint, True))
# 最大化“座位 × 行程长度”, 即最大化所有被接受订单产生的座位里程/座位区间利用量
utilization = model.sum(
[
request_selected[request].presence() * nb_seats_request[request] * nb_stations_request[request]
for request in range(nb_requests)
]
)
model.maximize(utilization)
# Optional intervals start absent in the current OptAgent search. A short run
# may therefore keep the feasible empty allocation with utilization zero.
solution = solve(
model,
time_limit_s=float(time_limit),
objective_threshold={0: nb_seats * nb_stations},
)
if not solution.feasible:
print(f"No feasible allocation found; Status = {solution.feasible}")
return solution
expressions = {"utilization": utilization}
for request in range(nb_requests):
expressions[f"request_{request}_selected"] = request_selected[request].presence()
expressions[f"request_{request}_start"] = request_selected[request].start()
expressions[f"request_{request}_end"] = request_selected[request].end()
values = {name: expression.value for name, expression in expressions.items()}
selected_rows = []
for request in range(nb_requests):
if values[f"request_{request}_selected"]:
selected_rows.append(
(
request,
values[f"request_{request}_start"],
values[f"request_{request}_end"] - 1,
)
)
print(f"Utilization = {values['utilization']}; Status = {solution.feasible}")
for request, first_seat, last_seat in selected_rows:
print(f"{request}: [{first_seat}...{last_seat}]")
if output_file is not None:
allocation_text = "\n".join(
f"{request}: [{first_seat}...{last_seat}]" for request, first_seat, last_seat in selected_rows
)
Path(output_file).write_text(f"{int(values['utilization'])}\n{allocation_text}\n", encoding="utf-8")
return solution
本地运行¶
INSTANCE_DIR = Path.cwd() / "instances"
# 注意：这个不分配也是可行解
solution = main(INSTANCE_DIR / "G20N10_30_0.txt", time_limit=10)