具有相关维度约束的车辆路径问题（Google ORTools）

Question

我是 OR-Tools 的新手，我正在尝试解决具有来自 Google's guide.

的容量限制的修改后的 VRP

在我的问题中，车辆运输多种类型的物品。有些类型可以一起运输，有些则不能。

我试过的

在下面的代码中，类型是 A 和 B（它们不应一起传输）。

首先我定义了需求的两个回调并将维度添加到路由模型

int demandACallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) => {
    var fromNode = manager.IndexToNode(fromIndex);
    return demandsA[fromNode];
});
int demandBCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) => {
    var fromNode = manager.IndexToNode(fromIndex);
    return demandsB[fromNode];
});

routing.AddDimensionWithVehicleCapacity(demandACallbackIndex, 0,
                                        capacitiesA,
                                        true,
                                        "CapacityA");
routing.AddDimensionWithVehicleCapacity(demandBCallbackIndex, 0,
                                        capacitiesB,
                                        true,
                                        "CapacityB");

然后我检索了尺寸并为每个节点 routing.solver() 添加了约束

var capacityADimension = routing.GetDimensionOrDie("CapacityA");
var capacityBDimension = routing.GetDimensionOrDie("CapacityB");

for (int i = 0; i < noDeliveries; i++) {
    var index = manager.NodeToIndex(i);
    routing.solver().Add(capacityADimension.CumulVar(index) * capacityBDimension.CumulVar(index) == 0);
}

当我运行求解器（有两辆车）时，这些约束似乎被忽略了（一辆车保持停放状态，而另一辆车完成所有工作，即使它不应该运输两种类型的物品）。

使用 OR-Tools 甚至可以做到这一点吗？如果是，我做错了什么？

完整代码

public SimpleVehicleRoutingSolutionDto SolveVehicleRoutingWithItemConstraints(long[,] distances, long[] capacitiesA, long[] capacitiesB, long[] demandsA, long[] demandsB, int depot)
{
    int noVehicles = capacitiesA.Length;
    int noDeliveries = deliveriesA.Length;

    RoutingIndexManager manager =
        new RoutingIndexManager(noDeliveries, noVehicles, depot);

    RoutingModel routing = new RoutingModel(manager);

    int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) => {
        var fromNode = manager.IndexToNode(fromIndex);
        var toNode = manager.IndexToNode(toIndex);
        return distances[fromNode, toNode];
    });

    routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

    int demandACallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) => {
        // Convert from routing variable Index to demand NodeIndex.
        var fromNode = manager.IndexToNode(fromIndex);
        return demandsA[fromNode];
    });
    int demandBCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) => {
        // Convert from routing variable Index to demand NodeIndex.
        var fromNode = manager.IndexToNode(fromIndex);
        return demandsB[fromNode];
    });
    routing.AddDimensionWithVehicleCapacity(demandACallbackIndex, 0,
                                            capacitiesA,
                                            true,
                                            "CapacityA");
    routing.AddDimensionWithVehicleCapacity(demandBCallbackIndex, 0,
                                            capacitiesB,
                                            true,
                                            "CapacityB");

    var capacityADimension = routing.GetDimensionOrDie("CapacityA");
    var capacityBDimension = routing.GetDimensionOrDie("CapacityB");

    for (int i = 0; i < noDeliveries; i++) {
        var index = manager.NodeToIndex(i);
        routing.solver().Add(capacityADimension.CumulVar(index) * capacityBDimension.CumulVar(index) == 0);
    }


    RoutingSearchParameters searchParameters =
        operations_research_constraint_solver.DefaultRoutingSearchParameters();
    searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
    searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch;
    searchParameters.TimeLimit = new Duration { Seconds = 1 };


    Assignment solution = routing.SolveWithParameters(searchParameters);
    var ret = new SimpleVehicleRoutingSolutionDto();

    long totalDistance = 0;
    for (int i = 0; i < noVehicles; ++i)
    {
        var vecihle = new VehiclePathDto { Index = i };
        long routeDistance = 0;
        var index = routing.Start(i);
        while (routing.IsEnd(index) == false)
        {
            long nodeIndex = manager.IndexToNode(index);
            vecihle.Waypoints.Add(new WaypointDto { Index = nodeIndex });
            var previousIndex = index;
            index = solution.Value(routing.NextVar(index));
            routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
        }
        vecihle.Distance = routeDistance;
        ret.Vehicles.Add(vecihle);
        totalDistance += routeDistance;
    }
    ret.TotalDistance = totalDistance;

    return ret;
}

输入：

long[,] dist = {
    { 0, 5, 6 },
    { 5, 0, 3 },
    { 6, 3, 0 }
};

long[] capA = { 5, 5 };
long[] capB = { 5, 5 };

long[] demA = { 0, 1, 0 };
long[] demB = { 0, 0, 1 };


var routingSolution = vehicleRouting.SolveVehicleRoutingWithItemConstraints(dist, capA, capB, demA, demB, 0);

Answer 1

我解决了这个问题。

问题是节点数是3（noDeliveries），但是索引数是6，所以我只对其中的一半设置了约束。

固定代码：

for (int i = 0; i < manager.GetNumberOfIndices(); i++) {
    routing.solver().Add(capacityADimension.CumulVar(i) * capacityBDimension.CumulVar(i) == 0);
}

编辑：

如果只为路由结束节点设置约束会更好，因为 CumulVar 值严格增加。

for (int j = 0; j < noVehicles; j++) {
    var index = routing.End(j);
    routing.solver().Add(capacityADimension.CumulVar(index) * capacityBDimension.CumulVar(index) == 0);
}

具有相关维度约束的车辆路径问题（Google ORTools）

Vehicle routing problem with dependent dimension constraints (Google ORTools)

or-tools

我试过的

完整代码