Блог

Следуя примерам python здесь

Я пытаюсь создать ту же функцию в java, которая заключается в том, чтобы загружать материалы и доставлять их клиентам, и если следующий спрос превышает оставшуюся емкость, перейдите в хранилище и перезагрузите. Все это происходит без каких-либо ограничений по времени, однако в моем случае есть только 1 транспортное средство. Проблема в том, что во многих случаях решение является нулевым.

Например: спрос: [0, -30, -30, -30, 17, 17, 18, 18, 18, 18] при вместимости транспортного средства 30 приводит к нулю. Тем не менее, один и тот же спрос с разной вместимостью транспортного средства прекрасно работает, например -18 , 36 , 48 , 96 .

Первое требование равно 0, потому что это начальное местоположение.

Вот код, который я использую:

 final OrDataModel data = buildDataModel();

RoutingIndexManager manager = new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);

RoutingModel routing = new RoutingModel(manager);

final int transitCallbackIndex =
routing.registerTransitCallback((long fromIndex, long toIndex) -> {
  int fromNode = manager.indexToNode(fromIndex);
  int toNode = manager.indexToNode(toIndex);
  return data.distanceMatrix[fromNode][toNode];
});

routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
routing.addDimension(transitCallbackIndex, 0, 1000000, true, "Distance");
RoutingDimension distanceDimension = routing.getDimensionOrDie("Distance");
distanceDimension.setGlobalSpanCostCoefficient(100);

final int demandCallbackIndex = routing.registerUnaryTransitCallback(
  (long fromIndex) -> {
  // Convert from routing variable Index to user NodeIndex.
  int fromNode = manager.indexToNode(fromIndex);
  return data.demands[fromNode];
});

routing.addDimension(demandCallbackIndex, data.vehicleCapacity, data.vehicleCapacity, true, "Capacity");
RoutingDimension capacityDimension = routing.getDimensionOrDie("Capacity");

//No penalty in case multi-trip visit is skipped when not required
for(int i = 1; i <= data.multiTrips - 1; i  ) {
  int fromNode = manager.indexToNode(i);
  routing.addDisjunction(new long[] { fromNode }, 0);
}

// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
  main.defaultRoutingSearchParameters()
  .toBuilder()
  .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
  .setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH)
  .setTimeLimit(Duration.newBuilder().setSeconds(1).build())
  .build();

// Solve the problem.
Assignment solution = routing.solveWithParameters(searchParameters);

if(solution != null) {
   printSolution(data, routing, manager, solution);
} else {
  System.out.print("no results");
}
 

 private static OrDataModel buildDataModel() {
    
    List<Long> volumes = new ArrayList<>();
    List<double[]> locations = new ArrayList<>();
    readCsvFile(volumes, locations);
    
    double totalVolume = LCollectionUtils.sumDoubleProperty(volumes, volume -> volume);
    
    int maxCapacity = 30;
    
    int multiTrips = calculateMultiTrips(totalVolume, maxCapacity);
    
    List<double[]> multiTripLocations = new ArrayList<>();
    for(int i = 0; i < multiTrips; i  ) {
        multiTripLocations.add(new double[] { 24.3653, 54.7136 });
    }
    
    List<double[]> allLocations = new ArrayList<double[]>(multiTripLocations);
    allLocations.addAll(locations);
    double[][] matrix = new double[allLocations.size()][];
    matrix = allLocations.toArray(matrix);
    
    long[][] distanceMatrix = buildDistanceMatrix(matrix, multiTrips);
    long[][] timeMatrix = buildTimeMatrix(matrix, multiTrips);
    long[] demands = fillDemands(multiTrips, matrix.length, volumes, maxCapacity);
    
    long[][] timeWindows = fillTimeWindow(allLocations.size(), multiTrips);
    
    return OrDataModel.from(matrix, distanceMatrix, timeMatrix, demands, allLocations.size(), multiTrips, maxCapacity, timeWindows, totalVolume);
}

private static long[] fillDemands(int minimumMultiTrips, int numberOfLocations, List<Long> allVolumes, long vehicleCapacity) {
    
    long[] demands = new long[numberOfLocations];
    
    //first demand is at depot so 0
    demands[0] = 0;
    
    int index;
    for(index = 1; index < minimumMultiTrips; index  ) {
        demands[index] = (long)-vehicleCapacity;
    }
    
    for(int j = 0; j < allVolumes.size(); j  ) {
        demands[index] = allVolumes.get(j);
        index  ;
    }
    
    return demands;
}


private static int calculateMultiTrips(double totalVolume, int capacity) {
    double remainder = totalVolume % capacity;
    double quotient = totalVolume / capacity;
    double multiTrip = remainder == 0 ? quotient : quotient   1;
    return (int)multiTrip;
}

private static long[][] buildDistanceMatrix(double[][] locations, int minimumMultiTrips) {

    long[][] distanceData = new long[locations.length][locations.length];

    for (int i = 0; i < locations.length; i  ) {
        
        LatLng fromLatLng = new LatLng().lat(locations[i][0]).lng(locations[i][1]);

        for (int j = 0; j < locations.length; j  ) {

            if (i == j) {
                distanceData[i][j] = 0;
            }
            
            else if(i < minimumMultiTrips amp;amp; j < minimumMultiTrips) {
                distanceData[i][j] = 100000;
            }
            
            else {
                LatLng toLatLng = new LatLng().lat(locations[j][0]).lng(locations[j][1]);
                LatLngQueryDataFetcher distanceFetcher = new HaversineDistanceFetcher(30, 1.25);
                sh.locus.pjp.server.model.distance.TimeDistancePair response = distanceFetcher.fetch(fromLatLng, toLatLng);
                distanceData[i][j] = response.getDistance();
            }
        }
    }

    return distanceData;
}
 

Код очень прост. Чтение по запросу, латинскому и длинному из файла csv. Жестко закодировано местоположение домашней базы для этого образца. Построил матрицу расстояний и времени, но только с использованием матрицы расстояний. Что, возможно, я упускаю?

примечание. AddDisjunction принимает индекс, а не узел, поэтому в основном ваш код :

     //No penalty in case multi-trip visit is skipped when not required
    for(int i = 1; i <= data.multiTrips - 1; i  ) {
        int fromNode = manager.indexToNode(i);
        routing.addDisjunction(new long[] { fromNode }, 0);
    }
 

это неправильно, вам нужно обратное

     //No penalty in case multi-trip visit is skipped when not required
    for(int i = 1; i <= data.multiTrips - 1; i  ) {
        int fromIndex = manager.nodeToIndex(i);
        routing.addDisjunction(new long[] { fromIndex }, 0);
    }