or-tools：某些位置不同 slack_max

Question

在我的项目中，我使用 or-tools 来解决 VRPTW 问题。我需要为不同的节点设置不同的等待时间。例如。我有 6 个地点。

车厂。最大时间 window (0, 1440)
客户1的上车点。时间window (0, 10)
客户1的送货点。时间window (0, 50)
客户2的上车点。时间window (500, 510)
客户2的送货点。时间window (500, 600)
车辆服务点。最大时间 window (0, 1440)

如果我将 slack_max 设置为 addDimension

routing.addDimension(transitCallbackIndex, // transit callback
                1440, // allow waiting time
                60 * 24 * 2,
                false, // start cumul to zero
                "Time");

我的车辆在每个位置的等待时间范围 (0, 1440)。在那种情况下，时间超出 pickup/delivery 节点的范围时间 windows。我如何只为车辆服务点设置松弛时间，因为该节点的时间 window 是最大值？

我试过像这样设置松弛

  if  (index == 5) {
    timeDimension.slackVar(index).setRange(0, 1440);
  }

但这并不像我预期的那样有效。

完整代码示例：

package test;

import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.Assignment;
import com.google.ortools.constraintsolver.FirstSolutionStrategy;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.IntervalVar;
import com.google.ortools.constraintsolver.RoutingDimension;
import com.google.ortools.constraintsolver.RoutingIndexManager;
import com.google.ortools.constraintsolver.RoutingModel;
import com.google.ortools.constraintsolver.RoutingSearchParameters;
import com.google.ortools.constraintsolver.Solver;
import com.google.ortools.constraintsolver.main;
import java.util.Arrays;
import java.util.logging.Logger;

/** Minimal VRP with Resource Constraints.*/
public class Test {
//    static {
//        System.loadLibrary("jniortools");
//    }
    private static final Logger logger = Logger.getLogger(Test.class.getName());

    static class DataModel {
        public final long[][] timeMatrix = {
                {0, 0, 0, 0, 0, 0},
                {0, 0, 10, 0, 10, 0},
                {0, 10, 0, 10, 0, 0},
                {0, 0, 10, 0, 10, 0},
                {0, 10, 0, 10, 0, 0},
                {0, 0, 0, 0, 0, 0}
        };
        public final long[][] timeWindows = {
                {0, 1440},
                {0, 10}, // 1 from
                {0, 50}, // 1 to
                {500, 510}, // 2 from
                {500, 600}, // 2 to
                {0, 1440}, // rest location
        };
        public final int[][] pickupDeliveries = {
                {1, 2},
                {3, 4},
        };
        public final int vehicleNumber = 1;
        public final int depot = 0;
    }


    public static void main(String[] args) throws Exception {
        Loader.loadNativeLibraries();
        // Instantiate the data problem.
        final DataModel data = new DataModel();

        // Create Routing Index Manager
        RoutingIndexManager manager =
                new RoutingIndexManager(data.timeMatrix.length, data.vehicleNumber, data.depot);

        // Create Routing Model.
        RoutingModel routing = new RoutingModel(manager);
        Solver solver = routing.solver();

        // Create and register a transit callback.
        final int transitCallbackIndex =
                routing.registerTransitCallback((long fromIndex, long toIndex) -> {
                    // Convert from routing variable Index to user NodeIndex.
                    int fromNode = manager.indexToNode(fromIndex);
                    int toNode = manager.indexToNode(toIndex);
                    return data.timeMatrix[fromNode][toNode];
                });

        // Define cost of each arc.
        routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

        // Add Time constraint.
        routing.addDimension(transitCallbackIndex, // transit callback
                1440, // allow waiting time
                60 * 24 * 2,
                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.length; ++i) {
            long index = manager.nodeToIndex(i);
            if (index >= 0) {
                timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
            }

            if  (index == 5) {
                timeDimension.slackVar(index).setRange(0, 1440);
            }

        }
        // 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)));
        }

        // Define Transportation Requests.
        for (int[] request : data.pickupDeliveries) {
            long pickupIndex = manager.nodeToIndex(request[0]);
            long deliveryIndex = manager.nodeToIndex(request[1]);
            routing.addPickupAndDelivery(pickupIndex, deliveryIndex);
            solver.addConstraint(
                    solver.makeEquality(routing.vehicleVar(pickupIndex), routing.vehicleVar(deliveryIndex)));
            solver.addConstraint(solver.makeLessOrEqual(
                    timeDimension.cumulVar(pickupIndex), timeDimension.cumulVar(deliveryIndex)));
        }

        // Setting first solution heuristic.
        RoutingSearchParameters searchParameters =
                main.defaultRoutingSearchParameters()
                        .toBuilder()
                        .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
                        .build();

        // Solve the problem.
        Assignment solution = routing.solveWithParameters(searchParameters);
        if (solution == null) {
            System.err.println("No solution found");
            return;
        }

        // Print solution on console.
        printSolution(data, routing, manager, solution);
    }


    /// @brief Print the solution.
    static void printSolution(
            DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
        RoutingDimension timeDimension = routing.getMutableDimension("Time");
        long totalTime = 0;
        for (int i = 0; i < data.vehicleNumber; ++i) {
            long index = routing.start(i);
            logger.info("Route for Vehicle " + i + ":");
            String route = "";
            while (!routing.isEnd(index)) {
                IntVar timeVar = timeDimension.cumulVar(index);
                route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
                        + solution.max(timeVar) + ") -> ";
                index = solution.value(routing.nextVar(index));
            }
            IntVar timeVar = timeDimension.cumulVar(index);
            route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
                    + solution.max(timeVar) + ")";
            logger.info(route);
            logger.info("Time of the route: " + solution.min(timeVar) + "min");
            totalTime += solution.min(timeVar);
        }
        logger.info("Total time of all routes: " + totalTime + "min");
    }
}

Answer 1

在您的代码中：

        // Add time window constraints for each location except depot.
        for (int i = 1; i < data.timeWindows.length; ++i) {
            long index = manager.nodeToIndex(i);
            if (index >= 0) {
                timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
            }

            if  (index == 5) {
                timeDimension.slackVar(index).setRange(0, 1440);
            }

        }

我认为：

这里你的if条件应该使用i,
因为你的循环从 1 开始，你已经跳过了仓库（节点 0），
您的 timeWindows 结构已经包含节点 5 的 [0, 1440]。
要将 P&D 节点的松弛度强制为零，您应该使用 SetValue()

所以你可以这样重写它：

       // Add time window constraints for each location except depot.
        for (int i = 1; i < data.timeWindows.length; ++i) {
            long index = manager.nodeToIndex(i);
            timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
            if  (i == 5) {
                timeDimension.slackVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
            } else { // disable waiting time for Pickup&Drop location
                timeDimension.slackVar(index).setValue(0);
            }
        }

可能的输出：

$ mvn exec:java
[INFO] --- exec-maven-plugin:3.0.0:java (default-cli) @ test ---
Dec 22, 2020 12:40:45 PM Test printSolution
INFO: Route for Vehicle 0:
Dec 22, 2020 12:40:45 PM Test printSolution
INFO: 0 Time(0,0) -> 1 Time(0,10) -> 2 Time(10,20) -> 5 Time(10,20) -> 3 Time(500,500) -> 4 Time(510,510) -> 0 Time(510,510)
Dec 22, 2020 12:40:45 PM Test printSolution
INFO: Time of the route: 510min
Dec 22, 2020 12:40:45 PM Test printSolution
INFO: Total time of all routes: 510min

那么最后一个问题，你所说的“但它没有像我预期的那样工作”是什么意思？观察到的输出是什么？您期望什么？

or-tools：某些位置不同 slack_max

or-tools: dirrerent slack_max for some locations

or-tools

vehicle-routing