建模思路¶
带吃水限制的旅行商问题 (TSPDL) 的 OptAgent 模型是 TSP 模型的扩展。路径规划部分使用 list 决策变量表示港口访问顺序，并最小化闭环路径的总行驶距离。
船舶的吃水是指水面线与船底之间的距离。吃水深度随着船舶的载重增加而增加，每个港口都有吃水限制，超过该限制的船舶无法进入该港。因此，在海运中，能否访问某个地点取决于所装载货物的多少。在其他场景中，只要某个地点的可访问性取决于车辆重量，也会出现类似的限制。与取货送货问题 (PDP) 类似，这需要通过递归数组计算车辆在路径上的重量：访问一个港口后的重量等于此前重量减去该港口的需求量。然后使用 and 运算符确保所有吃水限制都得到满足。
另一种做法是，你可以最小化累计的超重：
overweight <- sum(0...nbCities, i => max(0, weight[i] - weightLimit[cities[i]]));
当寻找满足所有吃水限制的解需要数秒以上时，这种方法会是一个不错的方案。
Python 实现¶
from pathlib import Path
from optagent import OptModel, solve
def read_tokens(filename):
return Path(filename).read_text(encoding="utf-8").split()
def read_instance(filename):
file_it = iter(read_tokens(filename))
# The input files follow the TSPLib "explicit" format
for token in file_it:
if token == "N:":
nb_cities = int(next(file_it))
if token == "Distance:[":
# Distance from i to j
distance_data = [[int(next(file_it)) for _ in range(nb_cities)] for _ in range(nb_cities)]
if token == "Demand:":
next(file_it)
# Vector representing the demand in terms of weight for each city
demand_data = [int(next(file_it)) for _ in range(nb_cities)]
if token == "Draft:":
next(file_it)
break
# Vector used to store the weight (draft) limit for each city
draft_limit_data = [int(next(file_it)) for _ in range(nb_cities)]
return nb_cities, distance_data, demand_data, draft_limit_data
def main(input_file, output_file=None, time_limit=5):
nb_cities, distance_data, demand_data, draft_limit_data = read_instance(input_file)
total_weight = sum(demand_data)
model = OptModel()
# A list variable: cities[i] is the index of the ith city in the tour
cities = model.list(nb_cities)
# All cities must be visited
model.constraint(model.count(cities) == nb_cities)
# Model arrays support indexing with city decision expressions.
distance_matrix = model.array(distance_data)
demand = model.array(demand_data)
draft_limit = model.array(draft_limit_data)
# Compute the weight of the vehicle along the tour
weight_lambda = model.lambda_function(
lambda position, previous: model.iif(
position == 0,
total_weight,
previous - demand[cities[(position - 1) // 1]],
)
)
vehicle_weight = model.array(model.range(0, nb_cities), weight_lambda, 0)
# At each step, the vehicle's weight must not exceed the weight limit allowed for the city.
draft_constraint_lambda = model.lambda_function(
lambda position: vehicle_weight[position // 1] <= draft_limit[cities[position // 1]]
)
model.constraint(
model.and_(model.range(0, nb_cities), draft_constraint_lambda),
)
# Minimize the total distance
distance_to_next_city = model.lambda_function(
lambda position: distance_matrix[cities[(position - 1) // 1], cities[position // 1]]
)
objective = (
model.sum(model.range(1, nb_cities), distance_to_next_city) + distance_matrix[cities[nb_cities - 1], cities[0]]
)
model.minimize(objective)
solution = solve(model, time_limit_s=float(time_limit))
if not solution.feasible:
print(f"No feasible tour found; Status = {solution.status}")
return solution
tour = list(cities.value)
result_text = f"Total distance = {objective.value}; Status = {solution.status}\nTour: {' '.join(map(str, tour))}"
print(result_text)
if output_file is not None:
Path(output_file).write_text(
f"{objective.value}\n{' '.join(map(str, tour))}\n",
encoding="utf-8",
)
return solution
INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)
solution_burma14 = main(INSTANCE_DIR / "burma14_10_1.dat", time_limit=1)