OR-Tools VRP开发：节点3紧邻节点7的前置约束实现求助

问题原因 #

AddNodePrecedence(manager, 3, 7) 仅能保证节点3在节点7之前被访问，但无法强制两者紧邻——中间仍可能插入其他节点。要实现严格紧邻，需要直接约束节点的前后继关系。

核心思路 #

通过OR-Tools的NextVar变量强制节点3的下一个节点必须是7，同时确保节点7的前一个节点是3（前者已经隐含后者，但显式约束更稳妥）。由于两辆车速度不同，时间维度的约束需要基于车辆速度单独计算，但紧邻约束不依赖时间，只需要路径上的直接衔接。

完整代码示例 #

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

def create_data_model():
    """构建VRP数据模型，包含不同速度的车辆"""
    data = {}
    # 节点坐标（depot=0, 1-10对应问题中的1-10）
    data['locations'] = [
        (0, 0),    # depot 0
        (1, 2),    # 1
        (3, 5),    # 2
        (2, 1),    # 3
        (5, 3),    # 4
        (4, 0),    # 5
        (6, 2),    # 6
        (2, 4),    # 7
        (7, 6),    # 8
        (8, 1),    # 9
        (9, 3)     # 10
    ]
    # 车辆数量及对应速度（单位：距离/时间单位）
    data['num_vehicles'] = 2
    data['vehicle_speeds'] = [1.0, 1.5]  # 车辆0速度1，车辆1速度1.5
    data['depot'] = 0
    return data

def compute_time_matrix(data):
    """计算时间矩阵，根据车辆速度不同，时间=距离/速度"""
    import math
    locations = data['locations']
    num_locations = len(locations)
    # 先计算距离矩阵
    distance_matrix = []
    for from_loc in locations:
        row = []
        for to_loc in locations:
            dx = from_loc[0] - to_loc[0]
            dy = from_loc[1] - to_loc[1]
            row.append(math.hypot(dx, dy))
        distance_matrix.append(row)
    
    # 为每辆车生成时间矩阵
    time_matrices = []
    for speed in data['vehicle_speeds']:
        time_matrix = [[dist / speed for dist in row] for row in distance_matrix]
        time_matrices.append(time_matrix)
    return time_matrices

def print_solution(data, manager, routing, solution):
    """打印求解结果"""
    total_time = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = f"Vehicle {vehicle_id+1}路径:\n"
        route_time = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            next_index = solution.Value(routing.NextVar(index))
            next_node_index = manager.IndexToNode(next_index)
            # 获取当前车辆的时间矩阵
            time_matrix = compute_time_matrix(data)[vehicle_id]
            route_time += time_matrix[node_index][next_node_index]
            plan_output += f" {node_index} ->"
            index = next_index
        plan_output += f" {manager.IndexToNode(index)}\n"
        plan_output += f" 路径总时间: {route_time:.2f}\n"
        print(plan_output)
        total_time += route_time
    print(f"所有车辆总时间: {total_time:.2f}")

def main():
    data = create_data_model()
    time_matrices = compute_time_matrix(data)
    
    # 创建路由管理器
    manager = pywrapcp.RoutingIndexManager(
        len(data['locations']), data['num_vehicles'], data['depot']
    )
    
    # 创建路由模型
    routing = pywrapcp.RoutingModel(manager)
    
    # 定义时间回调函数：根据车辆ID返回对应时间矩阵的弧成本
    def time_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        vehicle_id = routing.VehicleVar(from_index).Value()
        return int(time_matrices[vehicle_id][from_node][to_node] * 1000)  # 放大为整数避免精度问题
    
    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    
    # 设置车辆的时间成本
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    
    # 添加时间窗口约束（这里设置为无约束，仅作为时间累积变量的载体）
    time = 'Time'
    routing.AddDimension(
        transit_callback_index,
        0,  # 等待时间上限
        1000,  # 总时间上限
        False,  # 不强制从零开始（depot出发时间可灵活调整）
        time
    )
    time_dimension = routing.GetDimensionOrDie(time)
    
    # -------------------------- 核心：添加严格紧邻约束 --------------------------
    # 获取节点3和7的索引
    node_3_index = manager.NodeToIndex(3)
    node_7_index = manager.NodeToIndex(7)
    
    # 强制节点3的下一个节点必须是7
    routing.solver().Add(routing.NextVar(node_3_index) == node_7_index)
    
    # 可选：强制节点7的前一个节点是3（上面的约束已隐含此条件，显式添加更保险）
    # routing.solver().Add(routing.PreviousVar(node_7_index) == node_3_index)
    
    # -------------------------- 求解配置 --------------------------
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    search_parameters.time_limit.seconds = 5
    
    # 求解
    solution = routing.SolveWithParameters(search_parameters)
    
    # 输出结果
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("未找到可行解")

if __name__ == '__main__':
    main()

代码说明 #

• 数据模型：定义了节点坐标、车辆数量及各自速度，为时间矩阵计算提供基础。
• 时间矩阵：根据车辆速度分别计算时间，解决不同速度车辆的时间成本差异问题。
• 紧邻约束：通过routing.NextVar(node_3_index) == node_7_index强制节点3的下一个节点是7，确保两者严格紧邻。
• 求解配置：使用引导局部搜索策略，在有限时间内找到较优解。

运行代码后，你会看到节点3始终紧邻在节点7之前被访问，且分配给同一辆车，符合问题要求。

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