如何在OR-Tools校车车辆路径规划问题中最小化乘客乘车时长？

核心思路 #

你的场景分为早班（住宅→学校）和晚班（学校→住宅），两者的乘车时长计算逻辑不同，但都可以通过OR-Tools的CumulVar（累计时间变量）结合节点访问状态变量ActiveVar来构建目标函数，最终最小化所有乘客的乘车时长总和。

关键概念说明 #

• CumulVar[vehicle][node]：表示车辆vehicle在节点node的累计时间（需注意：若你的时间维度包含服务时间，该变量通常代表离开节点的时间；若未包含服务时间，则代表到达节点的时间）。
• ActiveVar[vehicle][node]：二进制变量，值为1时表示车辆vehicle访问了节点node，用于过滤未被服务的节点，避免无效时长计算。

早班场景（住宅→学校）实现 #

乘车时长公式 #

每个乘客的乘车时长 = 到达学校的时间 - 住宅接人时间

• 若CumulVar是离开节点时间：
  • 到达学校时间 = CumulVar[veh][school] - service_time[school]
  • 住宅接人时间 = CumulVar[veh][home] - service_time[home]

代码实现片段 #

假设你已完成基础的RoutingModel和Manager初始化，以下是核心目标函数构建和约束设置：

# 1. 定义关键节点索引
school_node = 5  # 学校节点编号
home_nodes = [1,2,3,4]  # 所有住宅节点编号
service_time = [0,2,2,2,2,5]  # 各节点服务时间（depot:0，住宅:2，学校:5）

# 2. 添加时间维度（包含服务时间）
time_dimension = routing.AddTimeDimension(
    transit_callback_index,  # 已注册的行驶时间回调
    0,  # 无松弛时间
    300,  # 单辆车最大总时长（分钟）
    False,
    "Time"
)
# 为节点添加服务时间约束
for node in range(manager.GetNumberOfNodes()):
    if node == data['depot']:
        continue
    time_dimension.CumulVar(node).SetMin(time_dimension.CumulVar(node).Min() + service_time[node])

# 3. 设置所有车辆终点为学校
for vehicle_id in range(data['num_vehicles']):
    routing.SetEnd(vehicle_id, manager.NodeToIndex(school_node))

# 4. 构建最小化乘车时长的目标函数
objective = routing.LinearExpr.Zero()
school_idx = manager.NodeToIndex(school_node)

for vehicle_id in range(data['num_vehicles']):
    # 计算车辆到达学校的时间
    arrive_school = routing.LinearExpr.Sub(
        time_dimension.CumulVar(vehicle_id, school_idx),
        service_time[school_node]
    )
    for home_node in home_nodes:
        home_idx = manager.NodeToIndex(home_node)
        # 计算车辆到达住宅的时间（接人时间）
        arrive_home = routing.LinearExpr.Sub(
            time_dimension.CumulVar(vehicle_id, home_idx),
            service_time[home_node]
        )
        # 仅当车辆访问该住宅时，计入乘车时长
        active = routing.ActiveVar(vehicle_id, home_idx)
        duration = routing.LinearExpr.Sub(arrive_school, arrive_home)
        term = routing.LinearExpr.Mul(active, duration)
        objective = routing.LinearExpr.Add(objective, term)

# 设置目标函数为最小化总和
routing.AddMinimizedObjective(objective)

晚班场景（学校→住宅）实现 #

乘车时长公式 #

每个乘客的乘车时长 = 到达住宅的时间 - 离开学校的时间

• 若CumulVar是离开节点时间：
  • 离开学校时间 = CumulVar[veh][school]（学校为起点，到达时间为0，加上服务时间即为离开时间）
  • 到达住宅时间 = CumulVar[veh][home] - service_time[home]

代码实现片段 #

仅需修改起点设置和目标函数：

# 1. 设置所有车辆起点为学校
manager = pywrapcp.RoutingIndexManager(
    len(data['travel_time']),
    data['num_vehicles'],
    school_node  # 起点改为学校
)

# 2. 设置所有车辆终点为depot
for vehicle_id in range(data['num_vehicles']):
    routing.SetEnd(vehicle_id, manager.NodeToIndex(data['depot']))

# 3. 构建晚班目标函数
objective = routing.LinearExpr.Zero()
school_idx = manager.NodeToIndex(school_node)

for vehicle_id in range(data['num_vehicles']):
    # 车辆离开学校的时间（CumulVar直接为离开时间）
    leave_school = time_dimension.CumulVar(vehicle_id, school_idx)
    for home_node in home_nodes:
        home_idx = manager.NodeToIndex(home_node)
        # 计算车辆到达住宅的时间
        arrive_home = routing.LinearExpr.Sub(
            time_dimension.CumulVar(vehicle_id, home_idx),
            service_time[home_node]
        )
        active = routing.ActiveVar(vehicle_id, home_idx)
        duration = routing.LinearExpr.Sub(arrive_home, leave_school)
        term = routing.LinearExpr.Mul(active, duration)
        objective = routing.LinearExpr.Add(objective, term)

routing.AddMinimizedObjective(objective)

注意事项 #

1. 时间维度的CumulVar定义：务必确认你的时间维度是否包含服务时间，若未包含，需直接使用CumulVar作为到达时间，无需减去服务时间。
2. 节点访问约束：确保所有住宅节点被覆盖（通过容量约束或强制访问约束），避免出现未服务的节点。
3. 求解器参数调优：可调整搜索策略（如GUIDED_LOCAL_SEARCH）和时间限制，以平衡求解速度和结果质量。

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