1.2.2

下载 Notebook 下载完整案例

旅行商问题 (TSP)¶

类别： 路径优化

使用 OptAgent 的 Python 接口描述变量、约束与目标。

问题与原始示例来源：Hexaly Code Templates。

问题描述¶

旅行商问题 (TSP) 定义如下：给定 n 个城市以及每对城市之间的距离，寻找一条总长度最短的环游路径，使其恰好访问每个城市一次。从城市 i 到城市 j 的距离与从城市 j 到城市 i 的距离可能不同。

学习要点¶

• 使用 list 决策变量建模城市的排列
• 使用 lambda 函数计算相邻城市之间的行驶距离
• 求解后读取 list 决策变量的城市访问顺序

数据¶

所提供的旅行商问题 (TSP) 实例来自 TSPLib 非对称 TSP 数据库，采用 TSPLib 显式格式。城市数量在关键字 “DIMENSION:” 之后定义，完整的距离矩阵在关键字 “EDGE_WEIGHT_SECTION” 之后给出。

建模思路¶

该 OptAgent 模型基于一个 list 决策变量表示城市访问顺序。list 变量的第 i 个元素对应路径中第 i 个访问城市的索引。首先约束该 list 包含所有城市，以确保每个城市恰好访问一次。随后通过二维模型数组按决策表达式索引距离矩阵，使用 lambda 函数对相邻城市之间的距离求和，再加上从最后一个城市返回第一个城市的闭环距离。

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 == "DIMENSION:":
            nb_cities = int(next(file_it))
        if token == "EDGE_WEIGHT_SECTION":
            break

    # Distance from i to j
    distance_data = [[int(next(file_it)) for _ in range(nb_cities)] for _ in range(nb_cities)]
    return nb_cities, distance_data


def main(input_file, output_file=None, time_limit=5):
    nb_cities, distance_data = read_instance(input_file)
    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)

    # A model array supports indexing with city decision expressions.
    distance_matrix = model.array(distance_data)

    # 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_br17 = main(INSTANCE_DIR / "br17.atsp", time_limit=1)