问题描述¶
在带转运设施的车辆路径问题 (VRPTF) 中,它是带容量约束的车辆路径问题 (CVRP) 的扩展。一队具有相同容量的配送车辆必须为对单一商品有已知需求的客户提供服务。车辆从一个公共配送中心出发并最终返回该配送中心。每个客户只能由一辆车辆为其服务,可以是直接服务,也可以通过转运设施间接服务。每辆车服务的总需求不能超过其容量。将客户分配到某个设施会产生费用。虽然可以采用不同的费用模型,我们选择将客户到设施的距离作为费用。目标是使服务所有客户的总费用最小化,即总行驶距离与客户到设施分配费用之和。
学到的建模技巧¶
- 使用 list 决策变量建模卡车的客户访问顺序
- 使用 disjoint 和 contains 约束每个客户恰好选择一种服务方式
- 使用 lambda 函数对路线距离、需求量和设施分配费用求和
数据¶
我们提供的带转运设施的车辆路径问题 (VRPTF) 实例来自 C. Prodhon 实例集,用于选址路径问题 (LRP)。数据文件的格式如下:
- 客户数量
- 配送中心数量
- 配送中心与客户的 x 和 y 坐标
- 配送车辆的容量
- 每个配送中心的容量
- 每个客户的需求量
- 每个配送中心的开启成本
- 一条路径的开启成本
我们将提供的配送中心用作转运设施。由于在求解带转运设施的车辆路径问题 (VRPTF) 时这些信息不相关,我们忽略以下数值:
- 每个配送中心的容量
- 每个配送中心的开启成本
- 一条路径的开启成本
我们计算公共配送中心的坐标为包含所有客户和设施的最小边界矩形的中心。
建模思路¶
用于带转运设施的车辆路径问题的 OptAgent 模型为每辆卡车 r 定义一个 list 变量 (routes[r]) 来表示其路径。它对应于按顺序访问的节点序列。我们考虑 nbCustomers + nbCustomers * nbFacilities 个节点:
- 每个客户 c 对应一个节点。如果 routes[r] 访问节点 c,则表示客户 c 由卡车 r 直接服务。
- 每个设施 f 对应一个节点,并为每个客户 c 各复制一份。如果 routes[r] 访问节点 nbCustomers + c * nbFacilities + f,则表示客户 c 由卡车 r 通过转运设施 f 服务。
我们通过 disjoint 运算符约束所有列表两两互不相交,从而确保没有任何节点被多次访问。序列数 nbTrucks 是服务所有客户且不超载所需的最小卡车数量,乘以 1.5 的系数以保证可行性。
每个客户 c 必须恰好被服务一次,可以是直接服务或通过设施服务。contains(routes, c) 在任意卡车直接服务客户 c 时为 true,否则为 false。同理,设施复制节点的 contains 表达式表示某辆卡车通过相应设施服务客户。直接服务与所有设施服务方式的 contains 之和必须等于 1。
配送给客户 c 的货物量必须满足相应的需求 demands[c]。我们将每辆卡车服务的货物量计算为其路线中所有节点的需求之和,并约束其不超过卡车容量。
路线距离由客户及设施复制节点之间的 distanceMatrix 和往返公共配送中心的 depotDistances 计算。assignmentCosts 对直接服务节点取 0,对设施复制节点取客户到相应设施的距离。
最后,目标是最小化总行驶距离与总分配费用之和。
Python 实现¶
import math
from pathlib import Path
from optagent import OptModel, solve
def read_elements(filename):
return Path(filename).read_text(encoding="utf-8").split()
def main(instance_file, output_file=None, time_limit=20):
data = read_input(instance_file)
nb_customers = data["nb_customers"]
nb_facilities = data["nb_facilities"]
capacity = data["truck_capacity"]
customer_demands = data["customer_demands"]
# A point is either a customer or a facility
# Facilities are duplicated for each customer
nb_points = nb_customers + nb_customers * nb_facilities
demands_data = customer_demands + [demand for demand in customer_demands for _ in range(nb_facilities)]
min_nb_trucks = int(math.ceil(sum(customer_demands) / capacity))
nb_trucks = int(math.ceil(1.5 * min_nb_trucks))
model = OptModel()
route_sequences = [model.list(nb_points) for truck in range(nb_trucks)]
routes = model.array(route_sequences)
model.constraint(model.disjoint(route_sequences))
demands = model.array(demands_data)
distance_matrix = model.array(data["distance_matrix"])
depot_distances = model.array(data["depot_distances"])
assignment_costs = model.array(data["assignment_costs"])
for customer in range(nb_customers):
first_facility = nb_customers + customer * nb_facilities
facility_used = [
model.contains(routes, facility) for facility in range(first_facility, first_facility + nb_facilities)
]
delivery_count = model.contains(routes, customer) + model.sum(facility_used)
model.constraint(delivery_count == 1)
route_distances = []
route_assignment_costs = []
for truck, route in enumerate(route_sequences):
count = model.count(route)
demand_lambda = model.lambda_function(lambda point: demands[point // 1])
quantity_served = model.sum(route, demand_lambda)
model.constraint(quantity_served <= capacity)
distance_lambda = model.lambda_function(
lambda position: distance_matrix[route[(position - 1) // 1], route[position // 1]]
)
route_distances.append(
model.sum(model.range(1, count), distance_lambda)
+ model.iif(
count > 0,
depot_distances[route[0]] + depot_distances[route[(count - 1) // 1]],
0,
)
)
assignment_lambda = model.lambda_function(lambda point: assignment_costs[point // 1])
route_assignment_costs.append(model.sum(route, assignment_lambda))
total_distance_cost = model.sum(route_distances)
total_assignment_cost = model.sum(route_assignment_costs)
total_cost = total_distance_cost + total_assignment_cost
model.minimize(total_cost)
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_values = [list(route.value) for route in route_sequences]
header = (
f"File name: {instance_file}; totalCost = {total_cost.value}; "
f"totalDistance = {total_distance_cost.value}; "
f"totalAssignementCost = {total_assignment_cost.value}"
)
route_lines = []
for truck, route in enumerate(routes_values):
if not route:
continue
points = []
for point in route:
if point < nb_customers:
points.append(f"Customer {point}")
else:
facility = (point - nb_customers) % nb_facilities
customer = (point - nb_customers) // nb_facilities
points.append(f"Facility {facility} assigned to Customer {customer}")
route_lines.append(f"Route {truck} [{', '.join(points)}]")
result_text = "\n".join([header, *route_lines]) + "\n"
print(f"Total cost = {total_cost.value}; Status = {solution.status}")
print(result_text, end="")
if output_file is not None:
Path(output_file).write_text(result_text, encoding="utf-8")
return solution
def read_input_dat(filename):
file_it = iter(read_elements(filename))
nb_customers = int(next(file_it))
nb_facilities = int(next(file_it))
facilities_x = [None] * nb_facilities
facilities_y = [None] * nb_facilities
for i in range(nb_facilities):
facilities_x[i] = int(next(file_it))
facilities_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))
# Facility capacities : skip
for f in range(nb_facilities):
next(file_it)
customer_demands = [None] * nb_customers
for i in range(nb_customers):
customer_demands[i] = int(next(file_it))
depot_x, depot_y = compute_depot_coordinates(customers_x, customers_y, facilities_x, facilities_y)
depot_distances, distance_matrix = compute_distances(
customers_x, customers_y, facilities_x, facilities_y, depot_x, depot_y
)
assignment_costs = compute_assignment_costs(nb_customers, nb_facilities, distance_matrix)
return {
"nb_customers": nb_customers,
"nb_facilities": nb_facilities,
"truck_capacity": truck_capacity,
"customer_demands": customer_demands,
"depot_distances": depot_distances,
"distance_matrix": distance_matrix,
"assignment_costs": assignment_costs,
}
def compute_depot_coordinates(customers_x, customers_y, facilities_x, facilities_y):
# Compute the coordinates of the bounding box containing all of the points
x_min = min(min(customers_x), min(facilities_x))
x_max = max(max(customers_x), max(facilities_x))
y_min = min(min(customers_y), min(facilities_y))
y_max = max(max(customers_y), max(facilities_y))
# We assume that the depot is at the center of the bounding box
return x_min + (x_max - x_min) // 2, y_min + (y_max - y_min) // 2
def compute_distances(customers_x, customers_y, facilities_x, facilities_y, depot_x, depot_y):
nb_customers = len(customers_x)
nb_facilities = len(facilities_x)
nb_points = nb_customers + nb_customers * nb_facilities
# Distance to depot
depot_distances = [None] * nb_points
# Customer to depot
for c in range(nb_customers):
depot_distances[c] = compute_dist(customers_x[c], depot_x, customers_y[c], depot_y)
# Facility to depot
for c in range(nb_customers):
for f in range(nb_facilities):
depot_distances[nb_customers + c * nb_facilities + f] = compute_dist(
facilities_x[f], depot_x, facilities_y[f], depot_y
)
# Distance between points
distance_matrix = [[None for _ in range(nb_points)] for _ in range(nb_points)]
# Distances between customers
for c_1 in range(nb_customers):
for c_2 in range(nb_customers):
distance_matrix[c_1][c_2] = compute_dist(
customers_x[c_1], customers_x[c_2], customers_y[c_1], customers_y[c_2]
)
# Distances between customers and facilities
for c_1 in range(nb_customers):
for f in range(nb_facilities):
distance = compute_dist(facilities_x[f], customers_x[c_1], facilities_y[f], customers_y[c_1])
for c_2 in range(nb_customers):
# Index representing serving c_2 through facility f
facility_index = nb_customers + c_2 * nb_facilities + f
distance_matrix[facility_index][c_1] = distance
distance_matrix[c_1][facility_index] = distance
# Distances between facilities
for f_1 in range(nb_facilities):
for f_2 in range(nb_facilities):
dist = compute_dist(facilities_x[f_1], facilities_x[f_2], facilities_y[f_1], facilities_y[f_2])
for c_1 in range(nb_customers):
for c_2 in range(nb_customers):
distance_matrix[nb_customers + c_1 * nb_facilities + f_1][
nb_customers + c_2 * nb_facilities + f_2
] = dist
return depot_distances, distance_matrix
def compute_assignment_costs(nb_customers, nb_facilities, distance_matrix):
# Compute assignment cost for each point
nb_points = nb_customers + nb_customers * nb_facilities
assignment_costs = [0] * nb_points
for c in range(nb_customers):
for f in range(nb_facilities):
# Cost of serving customer c through facility f
assignment_costs[nb_customers + c * nb_facilities + f] = distance_matrix[c][
nb_customers + c * nb_facilities + f
]
return assignment_costs
def compute_dist(xi, xj, yi, yj):
exact_dist = math.sqrt(math.pow(xi - xj, 2) + math.pow(yi - yj, 2))
return round(exact_dist)
def read_input(filename):
if Path(filename).suffix.lower() == ".dat":
return read_input_dat(filename)
raise ValueError(f"Unknown file format: {Path(filename).suffix}")
INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)
solution_coord20 = main(INSTANCE_DIR / "coord20-5-1.dat", time_limit=1)