谷歌或工具路由-解决方案为空

Question

我正在尝试实现Google OR Tools的VRPTW。但我面临着一个问题。当我传递动态时间矩阵时，解决方案对象为空，但当我传递示例中给出的时间矩阵时它就起作用了。

这是我的代码

public class DataModel
{
public long[,] DistanceMatrix { get; set; }
public long[,] TimeMatrix = {
//commented matrix is dynamic generated
// {0,5,20,10,0,5},  
//{5,0,25,10,5,5},
//{20,25,0,30,20,20},
//{10,10,30,0,10,15},
//{0,5,20,10,0,5},
//{5,5,20,15,5,0},
{0, 6, 9, 8, 7, 3},
{6, 0, 8, 3, 2, 6},
{9, 8, 0, 11, 10, 6},
{8, 3, 11, 0, 1, 7},
{7, 2, 10, 1, 0, 6},
{3, 6, 6, 7, 6, 0},
};
public long[,] TimeWindows = {
{0, 5},    // depot
{7, 12},   // 1
{10, 15},  // 2
{16, 18},  // 3
{10, 13},  // 4
{0, 5},    // 5
};
public int VehicleNumber = 3;
public int Depot = 0;
};

这是的主要功能代码

DataModel data = new DataModel();
// data.TimeMatrix = TimeMatrix;
// Create Routing Index Manager
RoutingIndexManager manager = new RoutingIndexManager(
data.TimeMatrix.GetLength(0),
data.VehicleNumber,
data.Depot);
// Create a Routing Model.
RoutingModel routing = new RoutingModel(manager);
// Create and register a transit callback.
int transitCallbackIndex = routing.RegisterTransitCallback(
(long fromIndex, long toIndex) =>
{
// Convert from routing variable Index to distance matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return data.TimeMatrix[fromNode, toNode];
}
);
// Define the cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Add Distance constraint.
routing.AddDimension(
transitCallbackIndex, // transit callback
30, // allow waiting time
30, // vehicle maximum capacities
false,  // start cumul to zero
"Time");
RoutingDimension timeDimension = routing.GetMutableDimension("Time");
// Add time window constraints for each location except depot.
for (int i = 1; i < data.TimeWindows.GetLength(0); ++i)
{
long index = manager.NodeToIndex(i);
timeDimension.CumulVar(index).SetRange(
data.TimeWindows[i, 0],
data.TimeWindows[i, 1]);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.VehicleNumber; ++i)
{
long index = routing.Start(i);
timeDimension.CumulVar(index).SetRange(
data.TimeWindows[0, 0],
data.TimeWindows[0, 1]);
}
// Instantiate route start and end times to produce feasible times.
for (int i = 0; i < data.VehicleNumber; ++i)
{
routing.AddVariableMinimizedByFinalizer(
timeDimension.CumulVar(routing.Start(i)));
routing.AddVariableMinimizedByFinalizer(
timeDimension.CumulVar(routing.End(i)));
}
// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy =
FirstSolutionStrategy.Types.Value.PathCheapestArc;
// Solve the problem.
Assignment solution = routing.SolveWithParameters(searchParameters);  //it is null when dynamic time matrix is used, but it is not null when time matrix mentioned in example is used.

问题似乎出在AddDimension方法中。我对此感到震惊，但找不到任何解决办法。请提出任何解决方案。

Answer 1

Solution为null表示解算器无法找到任何可行的解决方案。很可能你的时间窗口太紧了。

要么尝试放松你的时间窗口

或者确保节点是可选的(使用addDisjunction(。