OR-Tools路由问题：含晚时间窗节点时路径混乱的优化需求

问题背景 #

现有11个节点：10个时间窗为[0, horizon]的节点，1个时间窗从下午2点（需转换为对应数值单位，如假设12点对应600、下午2点对应800）开始至horizon的节点。不含该晚时间窗节点时，路径可在12点完成；加入后，Solver生成大量循环路径拖延时间以满足该节点时间窗，而非使用已启用的Slack等待至下午2点后访问该节点。

时间窗通过Time维度CumulVar的SetMin()/SetMax()建模，节点SlackVar的Max值设为horizon，Time维度slack_max设为horizon，force_start_cumul_to_zero为false。期望Solver生成将晚时间窗节点置于路径末尾并使用Slack等待的优化路径。

核心问题分析 #

• 目标函数导向偏差：当前仅用SetSpanCostCoefficientForAllVehicles(1)最小化路径时间跨度，但循环路径的时间跨度和「先完成所有节点+Slack等待」的跨度可能相同，Solver会随机选择可行解，而循环路径在初始解生成阶段更容易被构造。
• 初始解策略不合理：BEST_INSERTION策略优先插入节点，易忽略时间窗的时序合理性，生成包含循环的初始路径，后续局部搜索难以跳出局部最优。
• Slack无使用激励：未对Slack设置成本优势，Solver没有动力选择「等待」而非「循环」，两者在当前目标下成本一致。
• 时间窗建模存在错误：示例代码中对非depot节点的时间窗End设置为SetMin(kHorizon)（应为SetMax(kHorizon)），需确保晚时间窗节点的Start约束正确。

解决建议 #

1. 调整目标函数，惩罚循环行为 #

增加总行驶时间的权重，让循环路径的成本远高于「完成节点+等待」的成本：

// 新增：将行驶时间计入弧成本，最小化总行驶时长
routing_model.SetArcCostEvaluatorOfVehicle(time_transit_callback_2_indices[0], 0);
// 保留原有的时间跨度惩罚
routing_model.GetMutableDimension("Time")->SetSpanCostCoefficientForAllVehicles(1);

2. 更换初始解策略 #

改用更倾向于生成无循环路径的初始策略，为后续局部搜索提供合理起点：

parameters.set_first_solution_strategy(
    operations_research::FirstSolutionStrategy::PATH_CHEAPEST_ARC
);

3. 强制晚时间窗节点为路径末尾（业务允许时） #

通过约束确保晚节点之后只能前往终点，直接避免循环：

// 假设晚时间窗节点索引为11（根据实际节点数调整）
int64_t late_node_index = 11;
solver->AddConstraint(
    solver->MakeEquality(routing_model.NextVar(late_node_index), routing_model.End(0))
);

4. 修正时间窗建模 #

确保晚时间窗节点的CumulVar约束正确：

// 下午2点对应的数值（根据实际时间单位调整）
int64_t late_node_start_time = 800;
time_dimension.CumulVar(late_node_index)->SetMin(late_node_start_time);
time_dimension.CumulVar(late_node_index)->SetMax(kHorizon);

5. 优化局部搜索参数 #

启用路径邻域搜索并延长求解时间，帮助Solver跳出循环路径的局部最优：

parameters.mutable_local_search_operators()->set_use_path_lns(
    operations_research::OptionalBoolean::BOOL_TRUE
);
parameters.mutable_time_limit()->set_seconds(60); // 延长求解时间

6. 移除冲突的Finalizer设置 #

当前对起点CumulVar设置AddVariableMaximizedByFinalizer与「起点时间固定为0」的约束冲突，建议移除：

// 删除该行代码
// routing_model.AddVariableMaximizedByFinalizer(time_dimension.CumulVar(routing_model.Start(vehicle_idx)));

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