基于Google OR-Tools的带值守约束VRP模型时间边界失效问题求助

模型需求 #

构建修改版车辆路径规划（VRP）模型，要求始终有一辆车辆在指定位置待命，以响应其他节点的突发紧急情况。

模型设计（基于C++版Google OR-Tools Routing Library） #

核心规则 #

• (A) 设置一组与车辆数相等的特殊节点代表值守位置，每辆车可前往至少一个特殊节点；
• (B) 任何时刻必须有且仅有一个特殊节点被车辆占用。

约束实现方案 #

为满足规则(B)，添加了4条约束：

1. 指定一辆车的路径起点为特殊节点（而非 depot）；
2. 将特殊节点到 depot 的运输成本设为0，确保该节点成为路径的最后访问点；
3. 所有特殊节点的Slack变量之和等于所有路径结束时间的最大值（覆盖全时间范围）；
4. CumulVar(special_node[i]) + SlackVar(special_node[i]) == CumulVar(special_node[i+1])，确保值守时段无重叠。

车辆可正常启动路径，随时前往特殊节点停留，再返回完成路径。特殊节点集合为{1,17,18,19}，涉及时间窗(TW)、Slack(S)、运输时间(T=距离(i,next(i))+Slack)。

当前进展 #

当时间维度的等待和操作时间上限设为较大值（kTimeMax>~40）时，模型运行正常，约束均能生效。

待解决问题 #

当设置较小的时间维度上限（如kTimeMax=22）时，约束3和约束4似乎被忽略，模型无法满足“始终有一辆车值守”的要求，寻求解决建议。

代码示例 #

#include <cstdint>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_index_manager.h"
#include "ortools/constraint_solver/routing_parameters.h"

namespace operations_research {
    void VrpTimeWindows() {
        // Instantiate the data problem.
        DataModel data;

        const int kSpecialNode{ 1 };

        // Real + duplicated nodes
        const int kNumNodes = data.time_matrix.size() + (data.num_vehicles - 1);

        // Route starts-ends locations
        const std::vector<std::pair<RoutingIndexManager::NodeIndex, RoutingIndexManager::NodeIndex>>
            starts_ends{
                {RoutingIndexManager::NodeIndex{kSpecialNode},   RoutingIndexManager::NodeIndex{0}},
                {RoutingIndexManager::NodeIndex{0},   RoutingIndexManager::NodeIndex{0}},
                {RoutingIndexManager::NodeIndex{0},   RoutingIndexManager::NodeIndex{0}},
                {RoutingIndexManager::NodeIndex{0},   RoutingIndexManager::NodeIndex{0}}
        };

        // Create Routing Index Manager
        RoutingIndexManager manager(kNumNodes, data.num_vehicles, starts_ends);

        // Create Routing Model.
        RoutingModel routing(manager);

        // Get pointer to CP Solver.
        Solver* const solver = routing.solver();

        // Create and register a transit callback.
        const int transit_callback_index = routing.RegisterTransitCallback(
            [&data, &manager, kNumNodes](int64_t from_index, int64_t to_index) -> int64_t {
                // Convert from routing variable Index to time matrix NodeIndex.
                auto from_node = manager.IndexToNode(from_index).value();
                auto to_node = manager.IndexToNode(to_index).value();
                // callback(kNumNodes-1, depot) = 0.
                auto last_special_node = RoutingIndexManager::NodeIndex{ kNumNodes - 1 }.value();
                if (from_node == last_special_node && to_node == data.depot.value())
                {
                    return 0;
                }
                // Any node out of time_matrix equals kSpecialNode.
                if (from_node >= data.time_matrix.size())
                {
                    from_node = kSpecialNode;
                }
                if (to_node >= data.time_matrix.size())
                {
                    to_node = kSpecialNode;
                }
                 return data.time_matrix[from_node][to_node];
            });

        // Define cost of each arc.
        routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

        // Add Time constraint.
        std::string time{ "Time" };
        const int64_t kTimeMax{ 22 };
        routing.AddDimension(transit_callback_index,  // transit callback index
            kTimeMax,   // allow waiting time
            kTimeMax,   // maximum time per vehicle
            false,      // Don't force start cumul to zero
            time);
        const RoutingDimension& time_dimension = routing.GetDimensionOrDie(time);

        // Instantiate route start and end times to produce feasible times.
        for (int i = 0; i < data.num_vehicles; ++i) {
            routing.AddVariableMinimizedByFinalizer(
                time_dimension.CumulVar(routing.Start(i)));
            routing.AddVariableMinimizedByFinalizer(
                time_dimension.CumulVar(routing.End(i)));
        }

        std::vector<int> special_nodes = { kSpecialNode };
        for (size_t i = data.time_matrix.size(); i < kNumNodes; i++)
        {
            special_nodes.push_back(i);
        }

        // Non-overlep between slacks of special nodes.
        // cumul(special[i]) + slack(special[i]) = cumul(special[i+1]) 
        for (size_t i = 0; i < special_nodes.size() - 1; i++)
        {
            int64_t index = 
                manager.NodeToIndex(RoutingIndexManager::NodeIndex(special_nodes[i]));
            int64_t next_index =
                manager.NodeToIndex(RoutingIndexManager::NodeIndex(special_nodes[i + 1]));
            solver->AddConstraint(solver->MakeEquality(
                solver->MakeSum({
                    time_dimension.CumulVar(index), time_dimension.SlackVar(index) }),
                time_dimension.CumulVar(next_index)
            ));
        }

        std::vector<IntVar*> end_cumuls;
        for (int i = 0; i < data.num_vehicles; ++i)
        {
            end_cumuls.push_back(time_dimension.CumulVar(routing.End(i)));
        }

        std::vector<IntVar*> special_node_slacks;
        for (size_t i = 0; i < special_nodes.size(); i++)
        {
            special_node_slacks.push_back(
                time_dimension.SlackVar(manager.NodeToIndex(
                    RoutingIndexManager::NodeIndex{ special_nodes[i] })));
        }

        // sum(special_node_slacks) == max(end_cumuls)
        solver->AddConstraint(solver->MakeEquality(
            solver->MakeSum(special_node_slacks),
            solver->MakeMax(end_cumuls)
        ));

        // Allow access to slack and transit variables after problem resolution.
        for (const auto& slack : time_dimension.slacks())
        {
            routing.AddToAssignment(slack);
        }
        for (const auto& transit : time_dimension.transits())
        {
            routing.AddToAssignment(transit);
        }

        // Setting first solution heuristic.
        RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
        searchParameters.set_first_solution_strategy(
            FirstSolutionStrategy::PATH_CHEAPEST_ARC);

        // Solve the problem.
        const Assignment* solution = routing.SolveWithParameters(searchParameters);

        // Print solution on console.
        PrintSolution(data, manager, routing, *solution);
    }
}  // namespace operations_research

int main(int /*argc*/, char* /*argv*/[]) {
    operations_research::VrpTimeWindows();
    return EXIT_SUCCESS;
}

解决建议 #

1. 强制特殊节点被访问 #

当kTimeMax较小时，求解器可能跳过特殊节点以满足时间限制，导致约束失效。为每个特殊节点添加强制访问约束：

for (int node : special_nodes) {
  routing.AddDisjunction({manager.NodeToIndex(RoutingIndexManager::NodeIndex(node))}, 100000);
}

设置极高的惩罚值，确保节点必须被纳入车辆路径。

2. 调整时间维度参数 #

当前等待时间上限与kTimeMax相同，可能限制Slack变量的取值空间。可适当调大等待时间上限，或为Slack变量单独设置范围：

// 调整AddDimension参数，增大等待时间上限
routing.AddDimension(transit_callback_index,
    kTimeMax * 2,   // 允许更长的等待时间
    kTimeMax,
    false,
    time);

// 为Slack变量设置非负约束
for (auto* slack : special_node_slacks) {
  solver->AddConstraint(solver->MakeGreaterOrEqual(slack, 0));
}

3. 优化约束逻辑 #

原约束依赖Slack变量的间接控制，可改为直接设置值守时段的时间窗衔接：

• 为每个特殊节点设置专属时间窗，确保相邻节点的时间窗无缝衔接（如节点1的结束时间等于节点17的开始时间）；
• 使用序列约束强制车辆按顺序访问特殊节点，保证值守连续性：

  std::vector<int64_t> special_indices;
  for (int node : special_nodes) {
    special_indices.push_back(manager.NodeToIndex(RoutingIndexManager::NodeIndex(node)));
  }
  routing.AddSequenceConstraint(special_indices, true);
  

4. 调整搜索策略 #

PATH_CHEAPEST_ARC启发式易陷入局部最优，切换到更全局的搜索策略并增加时间限制：

searchParameters.set_first_solution_strategy(FirstSolutionStrategy::AUTOMATIC);
searchParameters.mutable_local_search_operators()->set_use_path_relinking(true);
searchParameters.set_time_limit(absl::Seconds(10));

5. 验证变量取值 #

求解后打印特殊节点的CumulVar和SlackVar值，确认约束是否真的被违反，还是输出解析错误：

if (solution != nullptr) {
  for (int node : special_nodes) {
    int64_t index = manager.NodeToIndex(RoutingIndexManager::NodeIndex(node));
    LOG(INFO) << "Node " << node << ": Cumul=" << solution->Value(time_dimension.CumulVar(index))
              << ", Slack=" << solution->Value(time_dimension.SlackVar(index));
  }
}

内容的提问来源于stack exchange，提问作者fernando.de.almeida