Google OR-Tools：基于路径位置的节点动态成本设置问题

针对你的需求（节点作为中间节点/最终目的地时成本不同），可以通过固定基础成本+结束节点额外成本的方式建模，以下是具体的Python实现方案：

核心思路 #

你的总成本可以拆解为：

• 所有被访问节点的part成本之和（固定值，若所有非仓库节点都必须访问）
• 最终目的地节点的final成本与part成本的差值（即final_i - part_i，这部分是变量，需要最小化）

因为所有非仓库节点都要访问，基础成本是固定的，只需让模型选择final_i - part_i最小的节点作为最终目的地，同时生成合理的访问路径。

完整代码实现 #

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

# 定义成本数据
costs = [
    {"part": 0, "final": 0},
    {"part": 2, "final": 3},
    {"part": 4, "final": 2},
    {"part": 1, "final": 3},
]

def create_data_model():
    data = {}
    data["costs"] = costs
    data["num_nodes"] = len(costs)
    data["depot"] = 0  # 仓库节点
    data["num_vehicles"] = 1  # 单车辆路径规划
    # 边的基础成本设为0，我们通过节点成本调整总费用
    data["distance_matrix"] = [[0]*data["num_nodes"] for _ in range(data["num_nodes"])]
    return data

def main():
    data = create_data_model()
    # 初始化路由管理器和模型
    manager = pywrapcp.RoutingIndexManager(
        data["num_nodes"], data["num_vehicles"], data["depot"]
    )
    routing = pywrapcp.RoutingModel(manager)

    # 1. 定义边的基础成本回调（这里设为0）
    def transit_callback(from_index, to_index):
        return 0

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

    # 2. 设置所有非仓库节点必须被访问（惩罚值设为极大，确保必须访问）
    for node in range(1, data["num_nodes"]):
        routing.AddDisjunction([manager.NodeToIndex(node)], 100000)

    # 3. 计算基础成本（所有非仓库节点的part成本之和）
    base_cost = sum(node["part"] for node in data["costs"][1:])

    # 4. 设置每个节点作为最终目的地的额外成本（final - part）
    for i in range(1, data["num_nodes"]):
        end_cost = data["costs"][i]["final"] - data["costs"][i]["part"]
        routing.SetFixedCostOfEnd(manager.NodeToIndex(i), end_cost)

    # 5. 配置求解参数
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    # 使用PATH_CHEAPEST_ARC策略快速生成初始解
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )

    # 6. 求解并输出结果
    solution = routing.SolveWithParameters(search_parameters)
    if solution:
        total_cost = base_cost + solution.ObjectiveValue()
        print(f"总成本: {total_cost}")
        # 提取路径
        route = []
        index = routing.Start(0)
        while not routing.IsEnd(index):
            route.append(manager.IndexToNode(index))
            index = solution.Value(routing.NextVar(index))
        route.append(manager.IndexToNode(index))
        print(f"最优路径: {' -> '.join(map(str, route))}")

if __name__ == "__main__":
    main()

代码说明 #

1. 数据模型：定义仓库节点、车辆数、边的基础成本矩阵（设为0，因为成本由节点位置决定）。
2. 边成本回调：注册一个返回0的回调，我们不依赖边的成本，只关注节点的位置成本。
3. 强制节点访问：通过AddDisjunction设置极大惩罚，确保所有非仓库节点都被访问。
4. 基础成本计算：预先计算所有非仓库节点的part成本之和，这部分是固定开销。
5. 结束节点成本设置：使用SetFixedCostOfEnd为每个节点设置作为最终目的地的额外成本（final - part），模型会自动选择额外成本最小的节点作为终点。
6. 求解与输出：使用默认搜索策略求解，最终总成本为基础成本加上模型求解得到的额外成本，同时输出最优路径。

运行这段代码后，会输出：

总成本: 5
最优路径: 0 -> 1 -> 3 -> 2

完全符合你的预期。

内容的提问来源于stack exchange，提问作者Nguyen Hoang Vu