问题描述¶
在 Prize-Collecting Vehicle Routing Problem (PCVRP) 中，一组具有相同容量的配送车辆必须为对某种共同商品有已知需求的客户提供服务。车辆从一个共同的配送中心出发并最终返回该配送中心，每辆车服务的总需求量不得超过其容量。每位客户最多只能被一辆车访问。无需访问所有客户，但需要满足一个最低的需求量。此外，每位被访问的客户会带来一定的奖励。有三个优化目标：最小化车队规模、最大化所收集的奖励、最小化总行驶距离。
学习要点¶
- 添加 列表决策变量 来建模每辆卡车的客户访问顺序
- 定义 符号 Lambda 函数 来计算行驶距离和所收集的奖励
- 添加 多个目标
数据¶
我们提供的 Prize-Collecting Vehicle Routing Problem (PCVRP) 实例来自 Long et al. Set A instances。他们为 Augerat et al. Set A instances 添加了奖励值以及必须满足的最低需求量。数据文件的格式如下：
- 第一行：车辆数量、车辆容量、必须满足的最低需求量
- 第二行：配送中心的 ID 和坐标
- 接下来几行，对于每位客户：该客户的 ID、坐标、需求和奖励
建模思路¶
Prize-Collecting Vehicle Routing Problem (PCVRP) 的 OptAgent 模型使用 列表决策变量。对于每辆卡车，我们定义一个 list 变量，表示该卡车访问的客户顺序。通过在所有 list 上使用 disjoint 约束，我们确保每位客户最多被一辆卡车服务。
如果一辆卡车至少访问一位客户，则该卡车在车队中被使用。借助 ‘count’ 算子（返回 list 中的元素个数），我们可以检查每辆卡车是否被使用，然后计算车队中使用的卡车总数。
每辆卡车交付的总需求量通过 符号 Lambda 函数 计算，对所有访问的客户应用 ‘sum’ 算子。注意此求和中项的数量以及 list 的大小在搜索过程中是变化的。然后我们可以约束该数量不超过卡车容量。类似地，我们计算每辆卡车在其路线上收集的总奖励。
从一位客户到下一位客户的行驶距离同样通过在二维距离矩阵上使用 ‘at’ 算子来访问。我们使用另一个 符号 Lambda 函数 对每辆卡车在其路线上的距离进行求和，从而计算其总行驶距离。
三个目标按字典序进行优化。我们首先最小化使用的卡车数量，然后最大化所收集的总奖励，最后最小化所有卡车的总行驶距离。
Python 实现¶
# Copyright (c) Hexaly. Permission is hereby granted to use, copy,
# and modify this code for applications developed with Hexaly.
import math
from pathlib import Path
from optagent import OptModel, solve
def read_elem(filename):
return Path(filename).read_text(encoding="utf-8").split()
def main(instance_file, output_file=None, time_limit=20):
#
# Read instance data
#
nb_customers, nb_trucks, truck_capacity, dist_matrix_data, dist_depot_data, \
demands_data, demands_to_satisfy, prizes_data = read_input_pcvrp(instance_file)
model = OptModel()
# Sequence of customers visited by each truck
customers_sequences = [
model.list(nb_customers)
for k in range(nb_trucks)
]
# A customer might be visited by only one truck
model.constraint(model.disjoint(customers_sequences))
# Create model arrays for expression-based indexing.
demands = model.array(demands_data)
prizes = model.array(prizes_data)
dist_matrix = model.array(dist_matrix_data)
dist_depot = model.array(dist_depot_data)
# A truck is used if it visits at least one customer
trucks_used = [model.count(sequence) > 0 for sequence in customers_sequences]
dist_routes = []
route_prizes = []
route_quantities = []
for k, sequence in enumerate(customers_sequences):
count = model.count(sequence)
# The quantity needed in each route must not exceed the truck capacity
demand_lambda = model.lambda_function(lambda customer: demands[customer // 1])
route_quantity = model.sum(sequence, demand_lambda)
route_quantities.append(route_quantity)
model.constraint(route_quantity <= truck_capacity)
# Distance traveled by each truck
dist_lambda = model.lambda_function(
lambda position: dist_matrix[
sequence[(position - 1) // 1], sequence[position // 1]
]
)
route_distance = model.sum(model.range(1, count), dist_lambda) + model.iif(
count > 0,
dist_depot[sequence[0]] + dist_depot[sequence[(count - 1) // 1]],
0,
)
dist_routes.append(route_distance)
# Route prize of truck k
prize_lambda = model.lambda_function(lambda customer: prizes[customer // 1])
route_prizes.append(model.sum(sequence, prize_lambda))
# Total nb demands satisfied
total_quantity = model.sum(route_quantities)
# Minimal number of demands to satisfy
model.constraint(total_quantity >= demands_to_satisfy)
# Total nb trucks used
nb_trucks_used = model.sum(trucks_used)
# Total distance traveled
total_distance = model.sum(dist_routes)
# Total prize
total_prize = model.sum(route_prizes)
# Lexicographic objectives, in the same order as the original Hexaly model.
model.minimize(nb_trucks_used)
model.maximize(total_prize)
model.minimize(total_distance)
solution = solve(model, time_limit_s=float(time_limit))
values = {
"total_prize": total_prize.value,
"nb_trucks_used": nb_trucks_used.value,
"total_distance": total_distance.value,
"total_quantity": total_quantity.value,
**{f"route_{k}": sequence.value for k, sequence in enumerate(customers_sequences)},
}
print(
f"Prize = {values['total_prize']}; Trucks used = {values['nb_trucks_used']}; "
f"Distance = {values['total_distance']}; Demand = {values['total_quantity']}; "
f"Status = {solution.feasible}"
)
# Write the solution in the original output format.
if output_file is not None:
lines = [
f"{values['total_prize']} {values['nb_trucks_used']} {values['total_distance']}"
]
nb_unvisited_customers = nb_customers
for k in range(nb_trucks):
route = values[f"route_{k}"]
if not route:
continue
lines.append(" ".join(str(customer + 1) for customer in route))
nb_unvisited_customers -= len(route)
lines.append(f"{nb_unvisited_customers} {values['total_quantity']}")
Path(output_file).write_text("\n".join(lines) + "\n", encoding="utf-8")
return solution
# The input files follow the "longjianyu" format
def read_input_pcvrp(filename):
file_it = iter(read_elem(filename))
nb_trucks = int(next(file_it))
truck_capacity = int(next(file_it))
demands_to_satisfy = int(next(file_it))
n = 0
customers_x = []
customers_y = []
depot_x = 0
depot_y = 0
demands = []
prizes = []
it = next(file_it, None)
while (it != None):
node_id = int(it)
if node_id != n:
raise ValueError(f"Unexpected node index {node_id}; expected {n}")
if n == 0:
depot_x = int(next(file_it))
depot_y = int(next(file_it))
else:
customers_x.append(int(next(file_it)))
customers_y.append(int(next(file_it)))
demands.append(int(next(file_it)))
prizes.append(int(next(file_it)))
it = next(file_it, None)
n += 1
distance_matrix = compute_distance_matrix(customers_x, customers_y)
distance_depots = compute_distance_depots(depot_x, depot_y, customers_x, customers_y)
nb_customers = n - 1
return nb_customers, nb_trucks, truck_capacity, distance_matrix, distance_depots, \
demands, demands_to_satisfy, prizes
# Compute the distance matrix
def compute_distance_matrix(customers_x, customers_y):
nb_customers = len(customers_x)
distance_matrix = [[None for _ in range(nb_customers)] for _ in range(nb_customers)]
for i in range(nb_customers):
distance_matrix[i][i] = 0
for j in range(nb_customers):
dist = compute_dist(customers_x[i], customers_x[j], customers_y[i], customers_y[j])
distance_matrix[i][j] = dist
distance_matrix[j][i] = dist
return distance_matrix
# Compute the distances to depot
def compute_distance_depots(depot_x, depot_y, customers_x, customers_y):
nb_customers = len(customers_x)
distance_depots = [None] * nb_customers
for i in range(nb_customers):
dist = compute_dist(depot_x, customers_x[i], depot_y, customers_y[i])
distance_depots[i] = dist
return distance_depots
def compute_dist(xi, xj, yi, yj):
exact_dist = math.sqrt(math.pow(xi - xj, 2) + math.pow(yi - yj, 2))
return int(math.floor(exact_dist + 0.5))
实例调用¶
下面使用仓库提供的 PCVRP 实例运行模型。
INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)
solution_pcvrp = main(INSTANCE_DIR / "A-n32-k5_1.txt", time_limit=1)
solution_pcvrp.feasible