问题描述¶
在选址路径问题 (LRP) 中，它是带容量车辆路径问题 (CVRP) 的扩展，一组具有统一容量的配送车辆必须为具有单一商品已知需求的客户提供服务。与仅有一个配送中心位置的 CVRP 不同，LRP 有多个可用的配送中心，每个配送中心都有自己的开放成本和容量。车辆从同一个配送中心出发并返回。每个客户必须恰好被一辆车辆服务，并且每辆车和每个配送中心服务的总需求不能超过其容量。目标是最小化总成本，即路径长度之和加上配送中心和路径的开放成本之和。
学习要点¶
- 添加 列表决策变量 来建模卡车的客户序列
- 添加 集合决策变量 来建模配送中心关联的卡车
- 通过 '
find' 算子获取每辆卡车的配送中心的索引 - 定义 符号 Lambda 函数 来计算行驶距离
数据¶
我们提供的选址路径问题 (LRP) 实例来自 S. Barreto instances。数据文件的格式如下：
- 客户数
- 配送中心数
- 配送中心和客户的 x、y 坐标
- 配送车辆的容量
- 每个配送中心的容量
- 每个客户的需求
- 每个配送中心的开放成本
- 路径的开放成本
- 一个布尔值，指示是否应对成本取整。
建模思路¶
选址路径问题 (LRP) 的OptAgent模型使用 列表决策变量。对于每辆卡车，我们定义一个 list variable 表示其访问的客户的序列。在所有列表上使用 partition 约束，我们确保每个客户恰好被一辆卡车服务。此外，我们还使用 集合决策变量。对于每个配送中心，我们定义一个 set variable 表示在该配送中心出发和结束路径的卡车。在 set 上使用另一个 partition 约束，我们确保每辆卡车与一个配送中心关联。
每辆卡车的总配送量通过 符号 Lambda 函数 对所有访问的客户应用 sum 算子计算得到。注意，此求和中项的数量在搜索过程中会随着列表的大小变化而变化。然后我们可以将该数量约束为小于卡车的容量。
使用 find 算子，我们可以检索与每辆卡车关联的配送中心的索引。这使我们能够计算从每辆卡车的配送中心到其第一个客户，以及从其最后一个客户返回其配送中心的距离。为了计算每条路径的总长度，我们还需要知道客户到客户之间的距离：我们使用另一个 符号 Lambda 函数 来对沿途的距离求和。
如果一条路径至少服务一个客户，则认为该路径是开放的；如果至少有一个非空序列使用该配送中心，则认为该配送中心是开放的。这些条件通过 count 算子计算。
最后，我们可以通过对所有路径的总长度以及每条开放路径和每个开放配送中心的开放成本求和来计算目标函数。
Python 实现¶
import math
from pathlib import Path
from optagent import OptModel, solve
def read_elem(filename):
with open(filename) as f:
return [str(elem) for elem in f.read().split()]
def main(instance_file, output_file=None, time_limit=20):
#
# Read instance data
#
nb_customers, nb_depots, vehicle_capacity, opening_route_cost, demands_data, \
capacity_depots, opening_depots_cost, dist_matrix_data, dist_depots_data = \
read_input_lrp(instance_file)
min_nb_trucks = int(math.ceil(sum(demands_data) / vehicle_capacity))
nb_trucks = int(math.ceil(1.5 * min_nb_trucks))
model = OptModel()
# Each route is a list of customers; partition assigns every customer once.
customers_sequences = [
model.list(nb_customers)
for r in range(nb_trucks)
]
model.constraint(model.partition(customers_sequences))
# Each depot is a set of routes that start and end at that depot.
depots = [model.set(nb_trucks) for d in range(nb_depots)]
depots_array = model.array(depots)
model.constraint(model.partition(depots))
demands = model.array(demands_data)
dist_matrix = model.array(dist_matrix_data)
dist_depots = model.array(dist_depots_data)
sequence_used = []
associated_depot = []
quantity_served = []
route_distances = []
route_costs = []
for r, sequence in enumerate(customers_sequences):
count = model.count(sequence)
used = count > 0
depot = model.find(depots_array, r)
demand_lambda = model.lambda_function(lambda customer: demands[customer // 1])
quantity = model.sum(sequence, demand_lambda)
model.constraint(quantity <= vehicle_capacity)
distance_lambda = model.lambda_function(
lambda position: dist_matrix[sequence[position // 1], sequence[position // 1 + 1]]
)
distance = model.sum(model.range(0, count - 1), distance_lambda) + model.iif(
used,
dist_depots[sequence[0], depot] + dist_depots[sequence[count - 1], depot],
0,
)
sequence_used.append(used)
associated_depot.append(depot)
quantity_served.append(quantity)
route_distances.append(distance)
route_costs.append(used * opening_route_cost + distance)
quantity_served_array = model.array(quantity_served)
depot_costs = []
for d, depot in enumerate(depots):
depot_open = model.count(depot) > 0
depot_costs.append(depot_open * opening_depots_cost[d])
depot_lambda = model.lambda_function(lambda route: quantity_served_array[route // 1])
depot_quantity = model.sum(depot, depot_lambda)
model.constraint(depot_quantity <= capacity_depots[d])
total_cost = model.sum(route_costs) + model.sum(depot_costs)
model.minimize(total_cost)
solution = solve(model, time_limit_s=float(time_limit))
values = {
"total_cost": total_cost.value,
**{f"route_{r}": sequence.value for r, sequence in enumerate(customers_sequences)},
**{f"depot_{r}": depot.value for r, depot in enumerate(associated_depot)},
}
lines = [
f"Customers = {nb_customers}; Depots = {nb_depots}; Trucks = {nb_trucks}; "
f"Total cost = {values['total_cost']}; Status = {solution.feasible}"
]
for r in range(nb_trucks):
route = values[f"route_{r}"]
if route:
lines.append(f"Route {r} (depot {values[f'depot_{r}']}): {' '.join(map(str, route))}")
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
def read_input_lrp_dat(filename):
file_it = iter(read_elem(filename))
nb_customers = int(next(file_it))
nb_depots = int(next(file_it))
x_depot = [None] * nb_depots
y_depot = [None] * nb_depots
for i in range(nb_depots):
x_depot[i] = int(next(file_it))
y_depot[i] = int(next(file_it))
x_customer = [None] * nb_customers
y_customer = [None] * nb_customers
for i in range(nb_customers):
x_customer[i] = int(next(file_it))
y_customer[i] = int(next(file_it))
vehicle_capacity = int(next(file_it))
capacity_depots = [None] * nb_depots
for i in range(nb_depots):
capacity_depots[i] = int(next(file_it))
demands = [None] * nb_customers
for i in range(nb_customers):
demands[i] = int(next(file_it))
temp_opening_cost_depot = [None] * nb_depots
for i in range(nb_depots):
temp_opening_cost_depot[i] = float(next(file_it))
temp_opening_route_cost = int(next(file_it))
are_cost_double = int(next(file_it))
opening_depots_cost = [None] * nb_depots
if are_cost_double == 1:
opening_depots_cost = temp_opening_cost_depot
opening_route_cost = temp_opening_route_cost
else:
opening_route_cost = round(temp_opening_route_cost)
for i in range(nb_depots):
opening_depots_cost[i] = round(temp_opening_cost_depot[i])
distance_customers = compute_distance_matrix(x_customer, y_customer, are_cost_double)
distance_customers_depots = compute_distance_depot(x_customer, y_customer,
x_depot, y_depot, are_cost_double)
return nb_customers, nb_depots, vehicle_capacity, opening_route_cost, demands, \
capacity_depots, opening_depots_cost, distance_customers, distance_customers_depots
# Compute the distance matrix
def compute_distance_matrix(customers_x, customers_y, are_cost_double):
nb_customers = len(customers_x)
dist_customers = [[None for _ in range(nb_customers)] for _ in range(nb_customers)]
for i in range(nb_customers):
dist_customers[i][i] = 0
for j in range(nb_customers):
dist = compute_dist(customers_x[i], customers_x[j],
customers_y[i], customers_y[j], are_cost_double)
dist_customers[i][j] = dist
dist_customers[j][i] = dist
return dist_customers
# Compute the distance depot matrix
def compute_distance_depot(customers_x, customers_y, depot_x, depot_y, are_cost_double):
nb_customers = len(customers_x)
nb_depots = len(depot_x)
distance_customers_depots = [[None for _ in range(nb_depots)] for _ in range(nb_customers)]
for i in range(nb_customers):
for d in range(nb_depots):
dist = compute_dist(customers_x[i], depot_x[d],
customers_y[i], depot_y[d], are_cost_double)
distance_customers_depots[i][d] = dist
return distance_customers_depots
def compute_dist(xi, xj, yi, yj, are_cost_double):
dist = math.sqrt(math.pow(xi - xj, 2) + math.pow(yi - yj, 2))
if are_cost_double == 0:
dist = math.ceil(100 * dist)
return dist
def read_input_lrp(filename):
if Path(filename).suffix.lower() == ".dat":
return read_input_lrp_dat(filename)
raise ValueError(f"Unknown file format: {Path(filename).suffix}")
本地运行¶
以下代码格演示如何调用 OptAgent 的 LRP 模型。
INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)
solution_gaspelle = main(INSTANCE_DIR / "coordGaspelle.dat", time_limit=1)
solution_christ50 = main(INSTANCE_DIR / "coordChrist50.dat", time_limit=1)