如何定义无需返回起点的TSP？及路由模型不指定depot、允许起止点不同的方法

首先明确一下，你说的「无需返回起点、允许起点终点不同」的TSP，其实就是开环旅行商问题（Open TSP）——和传统闭环TSP的核心区别就是不需要回到起始节点，只需要遍历所有节点一次即可，起点和终点可以是任意两个不同的节点。

针对Google OR-Tools的pywrapcp.RoutingModel，虽然构造函数要求必须传入depot参数，但我们可以通过修改约束来实现Open TSP的需求，具体步骤如下：

核心思路 #

RoutingModel默认会强制路径回到指定的depot节点，所以我们的关键操作是解除「必须返回depot」的约束，同时允许路径的起点和终点为任意节点。

具体实现代码 #

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def setup_open_tsp(tsp_size, distance_matrix):
    # 初始化模型：这里depot传一个占位符（比如0），后续会解除它的强制约束
    model_params = pywrapcp.DefaultRoutingModelParameters()
    routing = pywrapcp.RoutingModel(tsp_size, 1, 0, model_params)

    # 注册距离成本回调函数（替换成你的实际距离计算逻辑）
    def transit_callback(from_index, to_index):
        from_node = routing.IndexToNode(from_index)
        to_node = routing.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]

    transit_callback_idx = routing.RegisterTransitCallback(transit_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_idx)

    # 关键：解除起点和终点的固定约束，允许任意节点作为起点/终点
    routing.SetAllowedStartEndLocations([], [])

    # 配置搜索策略（可选，用PATH_CHEAPEST_ARC快速生成初始解）
    search_params = pywrapcp.DefaultRoutingSearchParameters()
    search_params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC

    return routing, search_params

# 示例调用
if __name__ == "__main__":
    tsp_size = 5
    # 示例距离矩阵（替换成你的实际数据）
    distance_matrix = [
        [0, 10, 15, 20, 25],
        [10, 0, 35, 25, 30],
        [15, 35, 0, 30, 40],
        [20, 25, 30, 0, 45],
        [25, 30, 40, 45, 0]
    ]

    routing, search_params = setup_open_tsp(tsp_size, distance_matrix)
    assignment = routing.SolveWithParameters(search_params)

    if assignment:
        print("Open TSP路径：")
        index = routing.Start(0)
        route = []
        while not routing.IsEnd(index):
            node = routing.IndexToNode(index)
            route.append(node)
            index = assignment.Value(routing.NextVar(index))
        route.append(routing.IndexToNode(index))
        print(" -> ".join(map(str, route)))
        print(f"总路径成本：{assignment.ObjectiveValue()}")

关键细节解释 #

1. 占位符depot：RoutingModel的构造函数必须传入depot参数，所以我们随便传一个节点（比如0）作为占位符，后续通过约束修改让它失去强制作用。
2. 解除起止节点约束：routing.SetAllowedStartEndLocations([], [])这个方法会告诉模型，车辆的起点和终点都可以是任意节点，不再限制为传入的depot。
3. 确保遍历所有节点：默认情况下，RoutingModel会要求所有节点都被访问一次（除非你主动添加Disjunction允许跳过节点），所以不需要额外配置就能满足TSP遍历所有节点的要求。

额外说明 #

如果你想更灵活地控制（比如指定某些节点不能作为起点/终点），可以给SetAllowedStartEndLocations传入具体的节点列表，比如SetAllowedStartEndLocations([1,2], [3,4])，表示只能从1或2出发，到3或4结束。

内容的提问来源于stack exchange，提问作者Leevi L