Google Or-Tools带时间窗的VRP求解返回Null问题求助

核心问题 #

你需要在VRP中实现两个关键时间窗约束：第1个地点（节点1）上午9:00前到达（≤540分钟）、第4个地点（节点4）上午11:00前到达（≤660分钟），但设置严格时间窗时求解失败，宽松时间窗虽成功但路径顺序不符合业务要求。

关键问题排查 #

1. 时间窗设置错误：原代码中节点1的时间窗设为535-615（8:55-10:15），未严格匹配“9:00前到达”的要求；同时默认给所有节点设置了535的起始时间，限制了车辆出发时间，可能导致路径规划无解。
2. 时间维度容量不足：原代码中_capacity = 1000，若总路径时间超过1000分钟会被强制截断，导致无解。
3. 起始累积变量未固定：_fix_start_cumul_to_zero = false允许车辆延迟出发，可能错过时间窗；同时目标函数设置不合理，未优先保证关键节点的时间约束。
4. 初始解策略局限：PathCheapestArc策略可能生成无法满足时间窗的初始路径，且30秒的搜索时间可能不足找到可行解。

修复步骤与代码示例 #

1. 修正时间窗配置 #

严格按照业务需求设置关键节点的时间窗，其他节点保留宽松约束：

IDictionary<int, TravelLocationlTimeWindowModel> locations = new Dictionary<int, TravelLocationlTimeWindowModel>();

for (int i = 0; i < 7; i++)
{
    string _from_lat = (i * 50).ToString();
    string _from_lng = (i * 100).ToString();
    TravelLocationlTimeWindowModel locationTravelTimeModel = new TravelLocationlTimeWindowModel();
    var location = new GeoLocationEntity { lat = _from_lat, lng = _from_lng };

    // 默认时间窗：0到当日结束（1440分钟）
    locationTravelTimeModel.time_window_start = 0;
    locationTravelTimeModel.time_window_end = 1440;

    if (i == 1)
    {
        // 第1个地点：必须9:00前到达
        locationTravelTimeModel.time_window_end = 540;
    }
    else if (i == 4)
    {
        // 第4个地点：必须11:00前到达
        locationTravelTimeModel.time_window_end = 660;
    }
    locationTravelTimeModel.geo_location = location;
    locations.Add(i, locationTravelTimeModel);
}

2. 调整时间维度参数 #

设置足够大的容量，固定车辆起始时间为0，确保路径时间不被不合理限制：

long _slack_max = 5; // 允许5分钟等待时间
long _capacity = 1440; // 设为当日总分钟数，避免路径超时
bool _fix_start_cumul_to_zero = true; // 强制车辆从时间0出发
string _dimension_name = "Time";

_routing.AddDimension(transitCallbackIndex, _slack_max, _capacity, _fix_start_cumul_to_zero, _dimension_name);

3. 优化求解参数与目标函数 #

更换初始解策略，延长搜索时间，优先最小化总路径结束时间：

// 目标：最小化车辆回到 depot 的时间
_routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(_routing.End(0)));

RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters();

// 采用Savings策略生成更合理的初始路径
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.Savings;
searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch;
searchParameters.TimeLimit = new Duration { Seconds = 60 }; // 延长搜索时间至60秒
searchParameters.LogSearch = true;

Assignment _solution = _routing.SolveWithParameters(searchParameters);

4. 强制路径顺序（可选） #

如果需要确保第1个地点优先访问，添加顺序约束：

RoutingDimension timeDimension = _routing.GetMutableDimension("Time");

// 约束：第1个地点的到达时间早于其他所有地点（除 depot）
for (int i = 2; i < locations.Count(); i++)
{
    long index1 = _manager.NodeToIndex(1);
    long indexI = _manager.NodeToIndex(i);
    _routing.AddConstraint(timeDimension.CumulVar(index1) <= timeDimension.CumulVar(indexI));
}

额外说明 #

• 若仍无解，需检查时间矩阵是否符合实际路况：比如从depot到节点1的时间为127分钟，到达时间127≤540，本身是满足约束的；若存在其他节点的时间窗冲突，需逐一排查。
• 开启LogSearch = true后，可查看求解日志中的约束冲突信息，定位具体无解原因。

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