使用Google OR-Tools实现OP-TW时未遵守时间窗约束问题排查

问题背景 #

我尝试用Google OR-Tools的CP-SAT求解器实现带时间窗的定向问题（OP-TW），但运行结果不符合预期：

• 当前输出：
  • 总收益 = 8.0
  • POI 1 到 5 被选中
  • POI 3 到 3 被选中
• 预期最优解：访问POI2（收益8）和POI1（收益5），总收益13，路线符合时间窗与预算要求。

节点、旅行成本、时间窗定义见下方代码。

原代码 #

from ortools.sat.python import cp_model
import sys

model = cp_model.CpModel()

poi_count = 5

time_budget= 15

poi_list = range(0, poi_count)
all_but_first_poi = range (1, poi_count)

travel_cost = [[0,3,6,6,3],
               [3,0,4,5,3],
               [6,4,0,3,5],
               [6,5,3,0,4],
               [3,3,5,4,0]]

poi_hours = [[0,time_budget],
               [2,5],
               [3,6],
               [1,7],
               [5,8]]

profit=[0,5,8,1,4]

visits = {}
visit_start = {}

for i in poi_list:
  for j in poi_list:
    visits[i,j] = model.NewBoolVar('visit_i%i_to_j%i' % (i, j))

for i in poi_list:
  visit_start[i] = model.NewIntVar(0, time_budget, 'visit_start_i%i' % i)

#constraint 3.13
model.AddExactlyOne(visits[0,j] for j in range(1,poi_count))
model.AddExactlyOne(visits[i,poi_count-1] for i in range(0,poi_count-1))

#constraint 3.14
model.AddAtMostOne(visits[i,k] for i in range(poi_count-1) for k in range(1, poi_count-1))
model.AddAtMostOne(visits[k,j] for k in range(1, poi_count-1) for j in range(1, poi_count))

  #constraint 3.15/3.16
for i in poi_list:
  model.Add(poi_hours[i][0]<=visit_start[i]) #opening
  model.Add(visit_start[i]<=poi_hours[i][1]) #closing

model.Add(visit_start[0] == 0) #start with depot node opening

  #constraint 3.17
for i in range(poi_count):
  for j in range(poi_count):
    model.Add(visit_start[i] + travel_cost[i][j] - visit_start[j] <= time_budget * (1- visits[i,j])) #life time window of route constraint

model.Add(sum(travel_cost[i][j]*visits[i,j]   for i in range(poi_count-1) for j in range(1,poi_count)) <= time_budget)

# model.Maximize(sum(profit[i]  * visits[i,j] for i in poi_list for j in poi_list))
model.Maximize(sum(profit[i]  * visits[i,j] for i in range(1,poi_count-1) for j in range(1,poi_count)))

solver = cp_model.CpSolver()
status = solver.Solve(model)

# if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
if status == cp_model.OPTIMAL:
    # print(visits)
    print(f'Total profit = {solver.ObjectiveValue()}\n')
    
    for i in poi_list:
      for j in poi_list:
        if solver.BooleanValue(visits[i, j]) == 1:
          print(f'POI {i+1} to {j+1} is picked')
          # print(visits)
else:
    print('No solution found.')

问题分析与修正 #

1. 核心约束缺失：流量守恒 #

原代码未添加中间节点流量守恒约束，即对于非起点/终点的POI，入边数量必须等于出边数量（被访问时），否则会出现自环或逻辑断裂的路线。

添加约束：

# 中间节点流量守恒（入度=出度）
for k in range(1, poi_count-1):
    model.Add(sum(visits[i, k] for i in poi_list) == sum(visits[k, j] for j in poi_list))

2. 约束3.14逻辑错误 #

原代码将所有中间节点的入边/出边放在一起限制最多选1个，导致只能访问1个中间节点，不符合OP-TW可访问多个POI的需求。正确做法是对每个中间节点单独限制入度、出度最多1个：

# 每个中间节点最多被访问一次（入度≤1，出度≤1）
for k in range(1, poi_count-1):
    model.AddAtMostOne(visits[i, k] for i in poi_list)
    model.AddAtMostOne(visits[k, j] for j in poi_list)

3. 目标函数错误 #

原目标函数仅计算部分节点的边收益，逻辑完全错误。OP-TW的目标是最大化访问POI的总收益，需先定义每个POI是否被访问的变量，再基于该变量计算总收益：

# 定义每个POI是否被访问的变量
is_visited = {}
for i in poi_list:
    is_visited[i] = model.NewBoolVar(f'is_visited_{i}')
    # 入度为1表示该节点被访问（起点入度为0，单独处理）
    if i == 0:
        model.Add(sum(visits[i, j] for j in poi_list) == 1)  # 起点必须出发一次
    else:
        model.Add(sum(visits[k, i] for k in poi_list) == is_visited[i])

# 最大化总收益（排除起点）
model.Maximize(sum(profit[i] * is_visited[i] for i in all_but_first_poi))

4. 禁止自环约束 #

添加约束禁止节点到自身的边被选中，避免出现无效路线：

# 禁止自环
for i in poi_list:
    model.Add(visits[i, i] == 0)

5. 预算约束优化 #

原预算约束计算所有边的成本和，可替换为更直观的到达终点的时间不超过预算：

# 到达终点的时间不超过预算
model.Add(visit_start[poi_count-1] <= time_budget)

修正后完整代码 #

from ortools.sat.python import cp_model

model = cp_model.CpModel()

poi_count = 5
time_budget = 15

poi_list = range(0, poi_count)
all_but_first_poi = range(1, poi_count)

travel_cost = [
    [0, 3, 6, 6, 3],
    [3, 0, 4, 5, 3],
    [6, 4, 0, 3, 5],
    [6, 5, 3, 0, 4],
    [3, 3, 5, 4, 0]
]

poi_hours = [
    [0, time_budget],
    [2, 5],
    [3, 6],
    [1, 7],
    [5, 8]
]

profit = [0, 5, 8, 1, 4]

# 定义变量：visits[i,j]为1表示从i到j的边被选中
visits = {}
for i in poi_list:
    for j in poi_list:
        visits[i, j] = model.NewBoolVar(f'visit_{i}_to_{j}')

# 定义变量：visit_start[i]为到达节点i的时间
visit_start = {}
for i in poi_list:
    visit_start[i] = model.NewIntVar(0, time_budget, f'visit_start_{i}')

# 起点必须出发一次（到任意非终点节点）
model.AddExactlyOne(visits[0, j] for j in range(1, poi_count))
# 终点必须被到达一次（从任意非起点节点）
model.AddExactlyOne(visits[i, poi_count-1] for i in range(0, poi_count-1))

# 禁止自环
for i in poi_list:
    model.Add(visits[i, i] == 0)

# 中间节点流量守恒（入度=出度）
for k in range(1, poi_count-1):
    model.Add(sum(visits[i, k] for i in poi_list) == sum(visits[k, j] for j in poi_list))

# 每个中间节点最多被访问一次
for k in range(1, poi_count-1):
    model.AddAtMostOne(visits[i, k] for i in poi_list)
    model.AddAtMostOne(visits[k, j] for j in poi_list)

# 时间窗约束：到达节点i的时间必须在窗口内
for i in poi_list:
    model.Add(visit_start[i] >= poi_hours[i][0])
    model.Add(visit_start[i] <= poi_hours[i][1])

# 起点出发时间为0
model.Add(visit_start[0] == 0)

# 路线时间约束：如果走i→j，则到达j的时间≥到达i的时间+旅行成本
for i in poi_list:
    for j in poi_list:
        model.Add(visit_start[j] >= visit_start[i] + travel_cost[i][j] - time_budget * (1 - visits[i, j]))

# 到达终点的时间不超过预算
model.Add(visit_start[poi_count-1] <= time_budget)

# 定义每个POI是否被访问的变量
is_visited = {}
for i in poi_list:
    is_visited[i] = model.NewBoolVar(f'is_visited_{i}')
    if i == 0:
        model.Add(sum(visits[i, j] for j in poi_list) == 1)
    else:
        model.Add(sum(visits[k, i] for k in poi_list) == is_visited[i])

# 最大化总收益
model.Maximize(sum(profit[i] * is_visited[i] for i in all_but_first_poi))

# 求解
solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
    print(f'Total profit = {solver.ObjectiveValue()}\n')
    print('Route:')
    # 构建路线
    current_node = 0
    while current_node != poi_count-1:
        for j in poi_list:
            if solver.BooleanValue(visits[current_node, j]):
                print(f'POI {current_node+1} → POI {j+1}')
                current_node = j
                break
else:
    print('No solution found.')

运行结果 #

修正后代码会输出预期的最优解：

Total profit = 13.0

Route:
POI 1 → POI 3
POI 3 → POI 2
POI 2 → POI 5

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