数据¶
本示例中使用的多趟容量受限车辆路径问题 (MTCVRP) 实例来自 S. Barreto 选址路径问题 (LRP) 实例。其格式如下：
- 客户数量
- 仓库数量
- 仓库和客户的 x 与 y 坐标
- 配送车辆的容量
- 每个仓库的容量（此处忽略）
- 每个客户的需求
- 每个仓库的开放成本（此处忽略）
- 每条路径的开放成本（此处忽略）
- 一个布尔值，指示是否对成本进行四舍五入（此处忽略）
此外，容量已除以 2，卡车数量及其最大行驶距离已在本示例中手动设置。
建模思路¶
多趟容量受限车辆路径问题 (MTCVRP) 的 OptAgent 模型使用 list 决策变量，表示每辆卡车访问的客户和仓库序列。为了确保每个客户恰好被访问一次，我们在所有 list 上施加 partition 约束。
然而，我们不希望对每个仓库也施加恰好访问一次的约束。为避免这种情况，我们为每个仓库定义最大访问次数，并对仓库进行复制：下标在 nbCustomers+d*nbDepotCopies 到 nbCustomers+(d+1)*nbDepotCopies-1 之间表示仓库 d 的副本。此外，我们定义一个虚拟 list，包含所有不需要的仓库访问。通过使用 ‘contains’ 和 ‘not’ 算子，我们确保该虚拟 list 不包含任何客户位置。
每辆卡车沿路径的载荷会变化：访问客户时增加，访问仓库时归零。我们使用 递归数组 计算卡车随时间的载荷：访问客户后的载荷等于访问上一位置后的载荷加上当前客户的需求；访问仓库后的载荷为零。通过使用可变参数 ‘and’ 算子，我们确保路径上任何时刻都满足容量约束。
为了计算每辆卡车行驶的距离，我们使用另一个 lambda 函数 对路径上每个相邻位置之间的距离求和。然后我们可以将该距离约束为不超过最大距离。
目标函数为总行驶距离。
Python 实现¶
from pathlib import Path
from optagent import OptModel, solve
import math
def read_elem(filename):
with open(filename) as f:
return [str(elem) for elem in f.read().split()]
def read_input_multi_trip_vrp(filename):
if Path(filename).suffix.lower() == ".dat":
return read_input_multi_trip_vrp_dat(filename)
raise ValueError(f"Unknown file format: {Path(filename).suffix}")
def read_input_multi_trip_vrp_dat(filename):
file_it = iter(read_elem(filename))
nb_customers = int(next(file_it))
nb_depots = int(next(file_it))
depots_x = [None] * nb_depots
depots_y = [None] * nb_depots
for i in range(nb_depots):
depots_x[i] = int(next(file_it))
depots_y[i] = int(next(file_it))
customers_x = [None] * nb_customers
customers_y = [None] * nb_customers
for i in range(nb_customers):
customers_x[i] = int(next(file_it))
customers_y[i] = int(next(file_it))
truck_capacity = int(next(file_it))//2
# Skip depots capacity infos (not related to the problem)
for i in range(nb_depots):
next(file_it)
demands_data = [None] * nb_customers
for i in range(nb_customers):
demands_data[i] = int(next(file_it))
nb_depot_copies = 20
nb_total_locations = nb_customers + nb_depots*nb_depot_copies
max_dist = 400
nb_trucks = 3
dist_matrix_data = compute_distance_matrix(depots_x, depots_y, customers_x, customers_y, nb_depot_copies)
return nb_customers, nb_trucks, truck_capacity, dist_matrix_data, nb_depots, \
nb_depot_copies, nb_total_locations, demands_data, max_dist
# Compute the distance matrix
def compute_distance_matrix(depots_x, depots_y, customers_x, customers_y, nb_depot_copies):
nb_customers = len(customers_x)
nb_depots = len(depots_x)
nb_total_locations = nb_customers + nb_depots*nb_depot_copies
dist_matrix = [[0 for _ in range(nb_total_locations)] for _ in range(nb_total_locations)]
for i in range(nb_customers):
dist_matrix[i][i] = 0
for j in range(i,nb_customers):
dist = compute_dist(customers_x[i], customers_x[j], customers_y[i], customers_y[j])
dist_matrix[i][j] = dist
dist_matrix[j][i] = dist
for d in range(nb_depots):
dist = compute_dist(customers_x[i], depots_x[d], customers_y[i], depots_y[d])
for c in range(nb_depot_copies):
j = nb_customers+d*nb_depot_copies + c
dist_matrix[i][j] = dist
dist_matrix[j][i] = dist
for i in range(nb_customers, nb_total_locations):
for j in range(nb_customers, nb_total_locations):
# Going from one depot to an other is never worth it
dist_matrix[i][j] = 100000
return dist_matrix
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))
def main(instance_file, output_file=None, time_limit=20):
(
nb_customers, nb_trucks, truck_capacity, dist_matrix_data, nb_depots,
nb_depot_copies, nb_total_locations, demands_data, max_dist,
) = read_input_multi_trip_vrp(instance_file)
model = OptModel()
visit_orders = [
model.list(nb_total_locations)
for k in range(nb_trucks + 1)
]
for customer in range(nb_customers):
model.constraint(model.not_(visit_orders[nb_trucks].contains(customer)))
model.constraint(model.partition(visit_orders))
demands = model.array(demands_data)
dist_matrix = model.array(dist_matrix_data)
trucks_used = [model.count(visit_orders[k]) > 0 for k in range(nb_trucks)]
route_distances = []
for k in range(nb_trucks):
sequence = visit_orders[k]
count = model.count(sequence)
route_quantity_lambda = model.lambda_function(
lambda position, previous: model.iif(
sequence[position // 1] < nb_customers,
previous + demands[sequence[position // 1]],
0,
)
)
route_quantity = model.array(model.range(0, count), route_quantity_lambda, 0)
quantity_lambda = model.lambda_function(
lambda position: route_quantity[position // 1] <= truck_capacity
)
model.constraint(model.and_(model.range(0, count), quantity_lambda))
distance_lambda = model.lambda_function(
lambda position: dist_matrix[sequence[(position - 1) // 1], sequence[position // 1]]
)
route_distance = model.sum(model.range(1, count), distance_lambda) + model.iif(
count > 0,
dist_matrix[nb_customers, sequence[0]]
+ dist_matrix[sequence[(count - 1) // 1], nb_customers],
0,
)
model.constraint(route_distance <= max_dist)
route_distances.append(route_distance)
total_distance = model.sum(route_distances)
model.minimize(total_distance)
solution = solve(model, time_limit_s=float(time_limit))
values = {
"total_distance": total_distance.value,
**{f"truck_{k}": visit_orders[k].value for k in range(nb_trucks)},
}
lines = [
f"Customers = {nb_customers}; Trucks = {nb_trucks}; Capacity = {truck_capacity}; "
f"Total distance = {values['total_distance']}; Status = {solution.feasible}"
]
for k in range(nb_trucks):
route = values[f"truck_{k}"]
if route:
display = []
for location in route:
if location < nb_customers:
display.append(str(location))
else:
depot = (location - nb_customers) // nb_depot_copies + 1
display.append(f"D{depot}")
lines.append(f"Truck {k}: {' '.join(display)}")
result_text = "\n".join(lines)
print(result_text)
if output_file is not None:
Path(output_file).write_text(result_text + "\n", encoding="utf-8")
return solution
本地运行¶
以下代码格演示如何调用 OptAgent 的多趟车辆路径模型。
INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)
solution_christ100 = main(INSTANCE_DIR / "coordChrist100.dat", time_limit=1)