В своем проекте я использую or-tools для решения проблемы VRPTW. Мне нужно установить разное время ожидания для разных узлов. Например. У меня 6 локаций.
- Депо автомобиля. С максимальным временным окном (0, 1440)
- Пункт самовывоза для клиента 1. Временное окно (0, 10)
- Пункт доставки для клиента 1. Временное окно (0, 50)
- Пункт самовывоза для клиента 2. Временное окно (500, 510)
- Пункт доставки для клиента 2. Временное окно (500, 600)
- Пункт обслуживания автомобилей. С максимальным временным окном (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");
}
}