or-tools: dirrerent slack_max для некоторых мест

В своем проекте я использую or-tools для решения проблемы VRPTW. Мне нужно установить разное время ожидания для разных узлов. Например. У меня 6 локаций.

  1. Депо автомобиля. С максимальным временным окном (0, 1440)
  2. Пункт самовывоза для клиента 1. Временное окно (0, 10)
  3. Пункт доставки для клиента 1. Временное окно (0, 50)
  4. Пункт самовывоза для клиента 2. Временное окно (500, 510)
  5. Пункт доставки для клиента 2. Временное окно (500, 600)
  6. Пункт обслуживания автомобилей. С максимальным временным окном (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) в каждом месте. В этом случае время выходит за пределы временных окон узла выдачи / выдачи. Как я могу установить резерв времени только для точки обслуживания транспортного средства, потому что временное окно для этого узла является максимальным?

Я пробовал установить слабину вот так

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



person Dmitry Ermichev    schedule 21.12.2020    source источник
comment
Вы использовали диспетчер индексов для преобразования 5-го узла в соответствующий индекс резервной переменной?   -  person Laurent Perron    schedule 21.12.2020


Ответы (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 уже содержит [0, 1440] для узла 5.
  • чтобы установить нулевой резерв для узлов 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

Итак, последний вопрос, что вы имеете в виду, но это не работает, как я ожидал. Каков наблюдаемый результат и чего вы ожидали?

person Mizux    schedule 22.12.2020