数据¶
我们提供的带回程取货车辆路径问题 (VRPB) 实例来自 LKH-3 和 JSprit，采用 TSPLib 格式：
- 节点数量在关键字 DIMENSION 之后给出（只有一个仓库，因此客户数量为节点数减 1）。
- 可用卡车数量在关键字 VEHICLES 之后给出。
- 卡车载重能力在关键字 CAPACITY 之后给出。
- 边权类型在关键字 EDGE_WEIGHT_TYPE 之后给出。本例中边权类型始终为 EXACT_2D。
- 在关键字 NODE_COORD_SECTION 之后，依次列出每个节点的 id 以及对应的 x、y 坐标。
- 在关键字 DEMAND_SECTION 之后，依次列出每个节点的 id 以及对应的需求量。
- 在关键字 BACKHAUL_SECTION 之后，列出取货节点的 id。
- 配送中心在关键字 DEPOT_SECTION 之后列出。本例中只有一个配送中心。
建模思路¶
带回程取货车辆路径问题 (VRPB) 的 OptAgent 模型如下。对每辆卡车定义一个 list 变量表示其客户访问序列，并在所有 list 上施加 partition（划分）约束，保证每位客户恰好由一辆卡车服务。
为表达每条路径上普通客户和回程客户之间的先后顺序约束，我们使用 and（与） 运算符和一个 lambda 函数。该约束的含义是：不能在一个取货客户之后再次访问送货客户。需要注意的是，约束项数会随着路径长度变化。
接下来需要为每辆卡车编写载重约束。借助另一个 lambda 函数，我们对所有访问的客户使用 sum（求和） 运算符，分别计算向普通客户送达的货物总量以及从回程客户取回的货物总量，并将这两个量约束为不超过卡车载重能力。
类似地，我们计算每辆卡车的行驶距离。再借助一个 lambda 函数，沿路径累加从一个客户到下一个客户的距离，并加上仓库与路径首尾客户之间的两条边。模型先最小化使用的车辆数，再最小化总行驶距离。
Python 实现¶
import math
from pathlib import Path
from optagent import OptModel, solve
def read_tokens(filename):
return Path(filename).read_text(encoding="utf-8").split()
def main(instance_file, output_file=None, time_limit=20):
(
nb_customers,
nb_trucks,
truck_capacity,
distance_matrix_data,
distance_depot_data,
delivery_demands_data,
pickup_demands_data,
backhaul_data,
) = read_input_vrpb(instance_file)
model = OptModel()
customers_sequences = [model.list(nb_customers) for truck in range(nb_trucks)]
model.constraint(model.partition(customers_sequences))
delivery_demands = model.array(delivery_demands_data)
pickup_demands = model.array(pickup_demands_data)
distance_matrix = model.array(distance_matrix_data)
distance_depot = model.array(distance_depot_data)
is_backhaul = model.array([backhaul_data[customer] for customer in range(nb_customers)])
trucks_used = [model.count(sequence) > 0 for sequence in customers_sequences]
route_distances = []
for truck, sequence in enumerate(customers_sequences):
count = model.count(sequence)
# Once a route starts pickups, it cannot return to deliveries.
precedence_lambda = model.lambda_function(
lambda position: model.or_(
is_backhaul[sequence[(position - 1) // 1]] == 0,
is_backhaul[sequence[position // 1]] == 1,
)
)
model.constraint(
model.and_(model.range(1, count), precedence_lambda),
)
delivery_lambda = model.lambda_function(lambda customer: delivery_demands[customer // 1])
route_delivery_quantity = model.sum(sequence, delivery_lambda)
model.constraint(
route_delivery_quantity <= truck_capacity,
)
pickup_lambda = model.lambda_function(lambda customer: pickup_demands[customer // 1])
route_pickup_quantity = model.sum(sequence, pickup_lambda)
model.constraint(
route_pickup_quantity <= truck_capacity,
)
distance_lambda = model.lambda_function(
lambda position: distance_matrix[sequence[(position - 1) // 1], sequence[position // 1]]
)
route_distances.append(
model.sum(model.range(1, count), distance_lambda)
+ model.iif(
count > 0,
distance_depot[sequence[0]] + distance_depot[sequence[(count - 1) // 1]],
0,
)
)
nb_trucks_used = model.sum(trucks_used)
total_distance = model.sum(route_distances)
model.minimize(nb_trucks_used)
model.minimize(total_distance)
solution = solve(model, time_limit_s=float(time_limit))
if not solution.feasible:
print(f"No feasible routes found; Status = {solution.status}")
return solution
routes = [list(sequence.value) for sequence in customers_sequences]
display_lines = [
f"Trucks used = {nb_trucks_used.value}; Total distance = {total_distance.value}; Status = {solution.status}"
]
display_lines.extend(
f"Truck {truck + 1}: {' '.join(str(customer + 2) for customer in route)}"
for truck, route in enumerate(routes)
if route
)
print("\n".join(display_lines))
if output_file is not None:
output_lines = [f"{nb_trucks_used.value} {total_distance.value}"]
output_lines.extend(" ".join(str(customer + 2) for customer in route) + " " for route in routes if route)
Path(output_file).write_text("\n".join(output_lines) + "\n", encoding="utf-8")
return solution
# The input files follow the "CVRPLib" format
def read_input_vrpb(filename):
file_it = iter(read_tokens(filename))
nb_nodes = 0
while True:
token = next(file_it)
if token == "DIMENSION":
next(file_it) # Removes the ":"
nb_nodes = int(next(file_it))
nb_customers = nb_nodes - 1
elif token == "VEHICLES":
next(file_it) # Removes the ":"
nb_trucks = int(next(file_it))
elif token == "CAPACITY":
next(file_it) # Removes the ":"
truck_capacity = int(next(file_it))
elif token == "EDGE_WEIGHT_TYPE":
next(file_it) # Removes the ":"
token = next(file_it)
if token != "EXACT_2D":
raise ValueError(f"Edge weight type {token} is not supported; expected EXACT_2D")
elif token == "NODE_COORD_SECTION":
break
customers_x = [None] * nb_customers
customers_y = [None] * nb_customers
depot_x = 0
depot_y = 0
for n in range(nb_nodes):
node_id = int(next(file_it))
if node_id != n + 1:
raise ValueError(f"Unexpected node index {node_id}; expected {n + 1}")
if node_id == 1:
depot_x = int(next(file_it))
depot_y = int(next(file_it))
else:
# -2 because original customer indices are in 2..nbNodes
customers_x[node_id - 2] = int(next(file_it))
customers_y[node_id - 2] = int(next(file_it))
distance_matrix = compute_distance_matrix(customers_x, customers_y)
distance_depots = compute_distance_depots(depot_x, depot_y, customers_x, customers_y)
token = next(file_it)
if token != "DEMAND_SECTION":
raise ValueError(f"Expected DEMAND_SECTION, got {token}")
demands = [None] * nb_customers
for n in range(nb_nodes):
node_id = int(next(file_it))
if node_id != n + 1:
raise ValueError(f"Unexpected node index {node_id}; expected {n + 1}")
if node_id == 1:
if int(next(file_it)) != 0:
raise ValueError("Demand for depot should be 0")
else:
# -2 because original customer indices are in 2..nbNodes
demands[node_id - 2] = int(next(file_it))
token = next(file_it)
if token != "BACKHAUL_SECTION":
raise ValueError(f"Expected BACKHAUL_SECTION, got {token}")
is_backhaul = {i: False for i in range(nb_customers)}
while True:
node_id = int(next(file_it))
if node_id == -1:
break
# -2 because original customer indices are in 2..nbNodes
is_backhaul[node_id - 2] = True
delivery_demands = [0 if is_backhaul[i] else demands[i] for i in range(nb_customers)]
pickup_demands = [demands[i] if is_backhaul[i] else 0 for i in range(nb_customers)]
token = next(file_it)
if token != "DEPOT_SECTION":
raise ValueError(f"Expected DEPOT_SECTION, got {token}")
depot_id = int(next(file_it))
if depot_id != 1:
raise ValueError(f"Depot id is supposed to be 1, got {depot_id}")
end_of_depot_section = int(next(file_it))
if end_of_depot_section != -1:
raise ValueError("Expected exactly one depot")
return (
nb_customers,
nb_trucks,
truck_capacity,
distance_matrix,
distance_depots,
delivery_demands,
pickup_demands,
is_backhaul,
)
# Compute the distance matrix
def compute_distance_matrix(customers_x, customers_y):
nb_customers = len(customers_x)
distance_matrix = [[None for i in range(nb_customers)] for j 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))
INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)
solution_a1 = main(INSTANCE_DIR / "A1.vrpb", time_limit=1)