数据¶
我们提供的多仓库车辆路径问题 (MDVRP) 实例来自 Cordeau_2011 instances。数据文件的格式如下：
- 第一行：数据类型（MDVRP 对应数字 2）、每个仓库的卡车数量、客户数量、仓库数量
- 对每个仓库：该仓库可用卡车的最大路径时长和容量
- 对每个客户：客户 ID、坐标 x 和 y、服务时间、需求
- 对每个仓库：仓库 ID、坐标 x 和 y。
建模思路¶
多仓库车辆路径问题 (MDVRP) 的 OptAgent 模型使用 list 决策变量。对每个仓库及其可用的每辆卡车，我们定义一个 list 变量表示它访问的客户序列。在所有 list 上施加 partition 约束，确保每个客户恰好由一辆卡车服务。
每辆卡车运送的总数量通过 lambda 函数 调用 sum 算子对所有访问过的客户进行求和计算。请注意，求和中的项数和 list 的大小在搜索过程中会动态变化。我们将这一数量约束为不超过卡车容量。
然后我们计算每辆卡车行驶的距离。利用另一个 lambda 函数，我们对路径上每个相邻客户之间的距离求和。类似地，我们计算每条路径的总时长，并将其约束为不超过卡车的最大路径时长限制。
目标是最小化所有卡车的总行驶距离。
Python 实现¶
from pathlib import Path
from optagent import OptModel, solve
import sys
import math
def main(instance_file, output_file=None, time_limit=20):
(
nb_trucks_per_depot, nb_customers, nb_depots, route_duration_capacity,
truck_capacity, demands_data, service_time_data,
distance_matrix_data, distance_warehouse_data,
) = read_input_mdvrp(instance_file)
model = OptModel()
customer_sequences = [
[
model.list(nb_customers)
for k in range(nb_trucks_per_depot)
]
for d in range(nb_depots)
]
all_sequences = [
customer_sequences[d][k]
for d in range(nb_depots)
for k in range(nb_trucks_per_depot)
]
model.constraint(model.partition(all_sequences))
demands = model.array(demands_data)
service_time = model.array(service_time_data)
dist_customers = model.array(distance_matrix_data)
route_distances = []
for depot in range(nb_depots):
dist_depot = model.array(distance_warehouse_data[depot])
for truck in range(nb_trucks_per_depot):
sequence = customer_sequences[depot][truck]
count = model.count(sequence)
demand_lambda = model.lambda_function(
lambda customer: demands[customer // 1]
)
route_quantity = model.sum(sequence, demand_lambda)
model.constraint(
route_quantity <= truck_capacity[depot],
)
distance_lambda = model.lambda_function(
lambda position: dist_customers[
sequence[(position - 1) // 1], sequence[position // 1]
]
)
route_distance = model.sum(model.range(1, count), distance_lambda) + model.iif(
count > 0,
dist_depot[sequence[0]] + dist_depot[sequence[(count - 1) // 1]],
0,
)
service_lambda = model.lambda_function(
lambda customer: service_time[customer // 1]
)
route_service_time = model.sum(sequence, service_lambda)
if route_duration_capacity[depot] > 0:
model.constraint(
route_distance + route_service_time <= route_duration_capacity[depot],
)
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"route_{d}_{k}": customer_sequences[d][k].value
for d in range(nb_depots)
for k in range(nb_trucks_per_depot)
},
}
lines = [
f"Customers = {nb_customers}; Depots = {nb_depots}; "
f"Total distance = {values['total_distance']}; Status = {solution.feasible}"
]
for depot in range(nb_depots):
for truck in range(nb_trucks_per_depot):
route = values[f"route_{depot}_{truck}"]
if route:
customers = " ".join(str(customer + 1) for customer in route)
lines.append(f"Depot {depot + 1}, truck {truck + 1}: {customers}")
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
# Input files following "Cordeau"'s format
def read_input_mdvrp(filename):
with open(filename) as f:
instance = f.readlines()
nb_line = 0
datas = instance[nb_line].split()
# Numbers of trucks per depot, customers and depots
nb_trucks_per_depot = int(datas[1])
nb_customers = int(datas[2])
nb_depots = int(datas[3])
route_duration_capacity = [None]*nb_depots # Time capacity for every type of truck from every depot
truck_capacity = [None]*nb_depots # Capacity for every type of truck from every depot
for d in range(nb_depots):
nb_line += 1
capacities = instance[nb_line].split()
route_duration_capacity[d] = int(capacities[0])
truck_capacity[d] = int(capacities[1])
# Coordinates X and Y, service time and demand for customers
nodes_xy = [[None, None]] * nb_customers
service_time = [None] * nb_customers
demands = [None] * nb_customers
for n in range(nb_customers):
nb_line += 1
customer = instance[nb_line].split()
nodes_xy[n] = [float(customer[1]), float(customer[2])]
service_time[n] = int(customer[3])
demands[n] = int(customer[4])
# Coordinates X and Y of every depot
depot_xy = [None] * nb_depots
for d in range(nb_depots):
nb_line += 1
depot = instance[nb_line].split()
depot_xy[d] = [float(depot[1]), float(depot[2])]
# Compute the distance matrices
distance_matrix_customers = compute_distance_matrix_customers(nodes_xy)
distance_warehouse = compute_distance_warehouse(depot_xy, nodes_xy)
return nb_trucks_per_depot, nb_customers, nb_depots, route_duration_capacity, \
truck_capacity, demands, service_time, distance_matrix_customers, distance_warehouse
# Compute the distance matrix for customers
def compute_distance_matrix_customers(nodes_xy):
nb_customers = len(nodes_xy)
distance_matrix = [[0 for _ in range(nb_customers)] for _ in range(nb_customers)]
for i in range(nb_customers):
for j in range(i+1, nb_customers):
distij = compute_dist(nodes_xy[i], nodes_xy[j])
distance_matrix[i][j] = distij
distance_matrix[j][i] = distij
return distance_matrix
# Compute the distance matrix for warehouses/depots
def compute_distance_warehouse(depot_xy, nodes_xy):
nb_customers = len(nodes_xy)
nb_depots = len(depot_xy)
distance_warehouse = [[0 for _ in range(nb_customers)] for _ in range(nb_depots)]
for i in range(nb_customers):
for d in range(nb_depots):
distance_warehouse[d][i] = compute_dist(depot_xy[d], nodes_xy[i])
return distance_warehouse
# Compute the distance between two points
def compute_dist(p, q):
return math.sqrt(math.pow(p[0] - q[0], 2) + math.pow(p[1] - q[1], 2))
本地运行¶
以下代码格演示如何调用 OptAgent 的多仓库车辆路径模型。
INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)
solution_p01 = main(INSTANCE_DIR / "p01", time_limit=1)