基于OR-Tools的最优生产序列：线性成本计算及可扩展方案咨询

原代码中arr[o[n]][o[n+1]]无法运行的核心原因是：OR-Tools CP-SAT的整数决策变量（o[n]）在求解前是未知的，不能直接作为numpy数组的索引——数组索引需要确定的整数值，而变量是待求解的符号。下面提供两种可行方案，均支持扩展到多步成本计算：

方案一：CP-SAT手动建模（灵活支持自定义成本规则） #

步骤1：统一变量与数组的索引规则 #

将序列变量o[n]的范围改为0-based（与numpy数组索引一致），避免索引错位问题。

步骤2：用AddElement构建转移成本 #

利用OR-Tools的AddElement函数，根据变量索引从常数数组中取值，再累加总成本：

import numpy as np
from ortools.sat.python import cp_model

N = 5
# 生成0-based的转移成本矩阵
cost_matrix = np.random.randint(1, 11, size=(N, N))
flat_cost = cost_matrix.flatten()  # 二维转一维，方便通过单索引取值

model = cp_model.CpModel()
solver = cp_model.CpSolver()

# 定义序列变量：o[n]表示第n个位置的产品编号（0~N-1）
o = {n: model.NewIntVar(0, N-1, f'order_{n}') for n in range(N)}

# 约束：所有产品仅出现一次
model.AddAllDifferent(o.values())

# 构建总成本表达式
step_costs = []
for n in range(N-1):
    # 计算转移对应的一维索引：from_product * N + to_product
    transfer_index = model.NewIntVar(0, N*N-1, f'transfer_index_{n}')
    model.Add(transfer_index == o[n] * N + o[n+1])
    
    # 获取该转移对应的成本值
    single_step_cost = model.NewIntVar(1, 10, f'step_cost_{n}')
    model.AddElement(transfer_index, flat_cost.tolist(), single_step_cost)
    step_costs.append(single_step_cost)

# 最小化总转移成本
total_cost = sum(step_costs)
model.Minimize(total_cost)

# 求解并输出结果
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
    sequence = [solver.Value(o[n]) for n in range(N)]
    print(f"最优生产序列：{sequence}")
    print(f"最小总成本：{solver.Value(total_cost)}")

扩展到多步成本计算 #

• 如果需要计算第n个元素到第n+z个元素的累计转移成本（比如z=2时，n→n+1→n+2的成本和），只需将对应区间内的single_step_cost累加即可。
• 如果是直接的跨z步跳转成本（比如有单独的z步转移成本矩阵cost_matrix_z），则复用AddElement逻辑，将索引改为o[n] * N + o[n+z]，从cost_matrix_z.flatten()中取值。

方案二：用OR-Tools Routing库解决（TSP专用，高效简洁） #

OR-Tools的Routing库专门针对路径规划问题（包括TSP）做了底层优化，无需手动建模约束，代码更简洁：

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import numpy as np

N = 5
# 生成0-based转移成本矩阵，对角线设为极大值避免自循环
cost_matrix = np.random.randint(1, 11, size=(N, N))
np.fill_diagonal(cost_matrix, 1000)

def create_data_model():
    data = {}
    data['cost_matrix'] = cost_matrix.tolist()
    data['num_vehicles'] = 1  # 对应单条生产序列
    data['depot'] = 0  # 起点可任意选择，后续处理为开环序列
    return data

data = create_data_model()

# 初始化路由求解器
manager = pywrapcp.RoutingIndexManager(N, data['num_vehicles'], data['depot'])
routing = pywrapcp.RoutingModel(manager)

# 定义成本回调函数：返回从节点i到j的转移成本
def cost_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['cost_matrix'][from_node][to_node]

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

# 设置求解策略（优先选成本最低的路径）
search_params = pywrapcp.DefaultRoutingSearchParameters()
search_params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC

# 求解
solution = routing.SolveWithParameters(search_params)

if solution:
    # 提取开环序列（去掉TSP默认的闭环起点重复）
    index = routing.Start(0)
    sequence = []
    while not routing.IsEnd(index):
        sequence.append(manager.IndexToNode(index))
        index = solution.Value(routing.NextVar(index))
    print(f"最优生产序列：{sequence}")
    print(f"最小总成本：{solution.ObjectiveValue()}")

多步成本扩展说明 #

如果需要将多步成本纳入优化目标，可以预处理得到k步转移成本矩阵（比如通过动态规划计算任意两点间k步的最小累计成本），然后修改回调函数返回对应成本值；若仅需在求解后计算多步成本，直接用得到的序列遍历成本矩阵累加即可。

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