OR-Tools多行程VRP：不同车辆二次访问目的地的软约束惩罚实现

针对你用复制节点+虚拟depot实现的多行程VRP，要添加“同一车辆二次访问必须是首次去过的目的地，违反则加惩罚”的软约束，核心思路是跟踪车辆的原始目的地访问历史，识别违反规则的访问行为，再将惩罚项纳入目标函数。以下是具体实现步骤（以Python版OR-Tools为例）：

1. 先做好节点映射 #

首先维护复制节点到原始节点的映射关系，方便后续关联复制节点和对应的真实目的地：

# 假设：
# - 0是真实depot，virtual_depot_id是虚拟depot的节点ID
# - original_num是原始目的地的数量
# - copy_nodes_of_original是字典，key为原始节点ID，value是对应的复制节点列表
total_nodes = 0  # 你的总节点数（含depot、虚拟depot、所有复制节点）
copy_to_original = [0] * total_nodes
# 映射复制节点到原始节点
for original_node in range(1, original_num + 1):
    for copy_node in copy_nodes_of_original[original_node]:
        copy_to_original[copy_node] = original_node
# 虚拟depot映射到自己
copy_to_original[virtual_depot_id] = virtual_depot_id

2. 定义辅助变量跟踪访问历史 #

为每个车辆和每个原始目的地创建布尔变量，标记该车辆是否访问过这个原始目的地：

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

# 假设你已经初始化了model、routing等对象
has_visited = {}
for v in range(num_vehicles):
    has_visited[v] = {}
    for i in range(1, original_num + 1):
        has_visited[v][i] = model.NewBoolVar(f"has_visited_v{v}_orig{i}")

3. 关联访问行为与辅助变量 #

确保只要车辆访问了某个原始目的地的任意复制节点，就标记该原始目的地为已访问：

# routing.ActiveVar(v, c)表示车辆v是否访问节点c
for v in range(num_vehicles):
    for c in range(total_nodes):
        if c == 0 or c == virtual_depot_id:
            continue  # 跳过depot和虚拟depot
        original_i = copy_to_original[c]
        # 如果车辆v访问节点c，那么has_visited[v][original_i]必须为True
        model.AddImplication(routing.ActiveVar(v, c), has_visited[v][original_i])

4. 识别违反约束的行为 #

创建布尔变量标记违反规则的情况：当车辆在已经访问过至少一个其他原始目的地后，首次访问某个新的原始目的地，就算违反：

PENALTY = 5000  # 惩罚系数，根据你的路径成本量级调整
violation = {}
for v in range(num_vehicles):
    violation[v] = {}
    for i in range(1, original_num + 1):
        violation[v][i] = model.NewBoolVar(f"violation_v{v}_orig{i}")
        # 计算车辆v访问过的其他原始目的地数量
        other_visited_sum = sum(has_visited[v][j] for j in range(1, original_num + 1) if j != i)
        # 违反条件：车辆访问了i，且已经访问过至少一个其他目的地
        model.Add(has_visited[v][i] + other_visited_sum >= 2).OnlyEnforceIf(violation[v][i])
        model.Add(has_visited[v][i] + other_visited_sum <= 1).OnlyEnforceIf(violation[v][i].Not())

5. 将惩罚纳入目标函数 #

把所有违反情况的惩罚加到总目标中，让求解器优先选择违反少的解：

# 假设你已经定义了原路径成本的计算逻辑，比如total_cost
total_penalty = sum(violation[v][i] * PENALTY for v in range(num_vehicles) for i in range(1, original_num + 1))
# 最小化总路径成本+惩罚
routing.SetCost(model.Minimize(total_cost + total_penalty))

针对多行程的优化（可选） #

如果你的多行程是通过虚拟depot分割行程的（比如路径是depot -> ... -> 虚拟depot -> ... -> depot），可以精准约束仅在第二次及之后的行程中首次访问新目的地才惩罚：

1. 为每个节点创建变量标记是否在虚拟depot之后访问：

after_virtual = {}
for v in range(num_vehicles):
    after_virtual[v] = {}
    for c in range(total_nodes):
        after_virtual[v][c] = model.NewBoolVar(f"after_virtual_v{v}_node{c}")
    # 从虚拟depot出发的节点，标记为在之后的行程
    for c in range(total_nodes):
        if c == virtual_depot_id:
            continue
        model.AddImplication(routing.NextVar(v, virtual_depot_id) == c, after_virtual[v][c])
    # 传递性：如果节点a在虚拟depot之后，车辆从a到b，则b也在之后
    for a in range(total_nodes):
        for b in range(total_nodes):
            if a == b:
                continue
            model.AddImplication(routing.NextVar(v, a) == b, after_virtual[v][b]).OnlyEnforceIf(after_virtual[v][a])

2. 修改违反约束的判断，仅考虑虚拟depot之后的首次访问：

# 重新定义violation变量
for v in range(num_vehicles):
    for i in range(1, original_num + 1):
        # 找到该原始目的地的所有复制节点
        copy_nodes = copy_nodes_of_original[i]
        # 车辆在虚拟depot之后访问了该原始目的地的任意节点
        visited_after_virtual = model.NewBoolVar(f"visited_after_virtual_v{v}_orig{i}")
        model.AddMaxEquality(visited_after_virtual, [after_virtual[v][c] for c in copy_nodes])
        # 违反条件：在虚拟depot之后首次访问i，且之前已经访问过其他目的地
        other_visited_sum = sum(has_visited[v][j] for j in range(1, original_num + 1) if j != i)
        model.Add(visited_after_virtual + other_visited_sum >= 2).OnlyEnforceIf(violation[v][i])
        model.Add(visited_after_virtual + other_visited_sum <= 1).OnlyEnforceIf(violation[v][i].Not())

关键注意事项 #

• 惩罚系数PENALTY要合理：既要大到让违反约束的解成本明显升高，又不能大到完全排除必要的违反场景（如果业务允许少量例外）。
• 如果原始节点数量极大，要注意变量数量，可考虑用整数变量替代布尔变量，或简化约束逻辑减少计算量。

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