用OptaPlanner求解带时间窗的车辆路径问题

Question

要求

我有一个车队。每辆车都有一个容量和它的存款，这个存款有一个时间窗口。从VRP的OptaPlanner的例子来看，我只对我作为浮点处理的容量做了一个变化。据我所知，OptaPlanner示例中的所有车辆都被移动到一个仓库。在我的情况下，每辆车都有自己的车辆段，每辆车都有自己固定的车辆段，有可能几辆车都有同一个车辆段。

R2-我有访问（送货服务）。每次访问都有一个需求和一个时间窗口。从VRP的OptaPlanner的例子来看，我只做了一个修改，要求我把它作为一个类型“float”来处理。

在OptaPlanner域中，我将vehicle中的变量“capacity”和visit中的变量“demand”修改为“float”类型。

Constraint vehicleCapacity(ConstraintFactory constraintFactory) {
    return constraintFactory.from(PlanningVisit.class)
            .groupBy(PlanningVisit::getVehicle, sumBigDecimal(PlanningVisit::getDemand))
            .filter((vehicle, demand) -> demand.compareTo(vehicle.getCapacity()) > 0)
            .penalizeLong(
                    "vehicle capacity",
                    HardSoftLongScore.ONE_HARD,
                    (vehicle, demand) -> demand.subtract(vehicle.getCapacity()).longValue());
}

2-在OptaPlanner的例子中，我理解TW是一个乘以一千的长，但我不知道这个长是否表示一个小时或日期，或者它只是一个小时转换成分钟乘以一千。我所做的是将TW转换为分钟并乘以千，例如，如果它是8am，就绪时间是一个等于'480000'的日志。在服务持续时间的情况下，我不乘以1000，我总是把它视为10分钟。我的转换正确吗？，这是OptaPlanner期望的长吗？

3-我明白，使用OptaPlanner的例子来处理时间窗口，我可以解决这个需求(R2)，而不用做任何改动，但是由于我找不到的原因，这并没有给我一个可行的解决方案。例如，它返回给我：花费的时间(5000)，最佳得分(-3313987hard/-4156887soft)。

我一定是做错了什么，但我找不到哪里，不仅不符合存款的TW，而且每次访问的到达时间都超过了定义的TW。我不明白为什么我会得到这么大的到达时间，甚至超过定义的限制1天（所有到达时间超过1440000=1400min=24=12am)，也就是说，他们在这个时间之后到达。

这是我得到的结果：分数（-3313987硬/-4156887软）

路线1指车辆1所跟随的路线

Depot 1 with TW (8:00 a 13:00)
    ready_time: 480000
    due_time: 780000


Visit 2 (8:30 a 12:30)
    ready_time: 510000
    due_time: 750000
    service_duraration 10 = 10

    arrival_time: 1823943
    departure_time: 1833943

Visit 4 (9:30 a 12:30)
    ready_time: 570000
    due_time: 750000
    service_duraration 10

    arrival_time: 1739284
    departure_time: 1739294

Visit 3 (14:40 a 15:30)
    ready_time: 880000
    due_time: 930000
    service_duraration 10

    arrival_time: 1150398
    departure_time: 1150408

Depot 2 with TW (12:00 a 17:00)
    ready_time: 720000
    due_time: 1020000

Visit 1 (14:00 a 16:30)
    ready_time: 840000
    due_time: 990000
    service_duraration 10 = 10

    arrival_time: 2523243
    departure_time: 2523253

public class ArrivalTimeUpdatingVariableListener implements VariableListener<PlanningVisit> {
    ...

    protected void updateArrivalTime(ScoreDirector scoreDirector, TimeWindowedVisit sourceCustomer) {

       Standstill previousStandstill = sourceCustomer.getPreviousStandstill();
       Long departureTime = previousStandstill == null ? null
               : (previousStandstill instanceof TimeWindowedVisit)
               ? ((TimeWindowedVisit) previousStandstill).getDepartureTime()
               : ((TimeWindowedDepot) ((PlanningVehicle) 
                                 previousStandstill).getDepot()).getReadyTime();
       TimeWindowedVisit shadowCustomer = sourceCustomer;
       Long arrivalTime = calculateArrivalTime(shadowCustomer, departureTime);
       while (shadowCustomer != null && !Objects.equals(shadowCustomer.getArrivalTime(), 
           arrivalTime)) {
               scoreDirector.beforeVariableChanged(shadowCustomer, "arrivalTime");
               shadowCustomer.setArrivalTime(arrivalTime);
               scoreDirector.afterVariableChanged(shadowCustomer, "arrivalTime");
               departureTime = shadowCustomer.getDepartureTime();
               shadowCustomer = shadowCustomer.getNextVisit();
               arrivalTime = calculateArrivalTime(shadowCustomer, departureTime);
             }        
        }

    private Long calculateArrivalTime(TimeWindowedVisit customer, Long previousDepartureTime) {
       if (customer == null || customer.getPreviousStandstill() == null) {
              return null;
       }
       if (customer.getPreviousStandstill() instanceof PlanningVehicle) {
           // PreviousStandstill is the Vehicle, so we leave from the Depot at the best suitable time
           return Math.max(customer.getReadyTime(),
                     previousDepartureTime + customer.distanceFromPreviousStandstill());
       }
       return previousDepartureTime + customer.distanceFromPreviousStandstill();
     }
}

   public TimeWindowedVehicleRoutingSolution find(UUID jobId) {
        //load VRP from DB
        RoutingProblem byJobId = routingProblemRepository.findVRP(jobId);
        Set<Vehicle> vehicles = byJobId.getVehicles();
        Set<Visit> visits = byJobId.getVisits();

        //building solution
        List<PlanningDepot> planningDepots = new ArrayList<>();
        List<PlanningVehicle> planningVehicles = new ArrayList<>();
        List<PlanningVisit> planningVisits = new ArrayList<>();


        vehicles.forEach(vehicle -> {
            //submit to planner location of the deposit, add to matrix for calculating distance
            PlanningLocation planningLocation = 
                        optimizer.submitToPlanner(vehicle.getDepot().getLocation());

            //Depot, Vehicle and Visit are my persistence JPA entities, they are not the OptaPlanner 
             domain entities.
            //The OptaPlanner domain entities are: PlanningVehicle, PlanningDepot and PlanningVisit
            //I build the entities of the optaplanner domain from my persistence entities

            Depot depot = vehicle.getDepot();
            TimeWindowedDepot timeWindowedDepot = new TimeWindowedDepot();
            TimeWindowedDepot timeWindowedDepot = new TimeWindowedDepot(depot.getId(), 
                     planningLocation, depot.getStart(), depot.getEnd());

        PlanningVehicle planningVehicle = new PlanningVehicle();
        planningVehicle.setId(vehicle.getId());
        planningVehicle.setCapacity(vehicle.getCapacity());
        // each vehicle has its deposit
        planningVehicle.setDepot(timeWindowedDepot);

        planningVehicles.add(planningVehicle);
       });

       visits.forEach(visit -> {
           //submit to planner location of the visit, add to matrix for calculating distance
            PlanningLocation planningLocation = optimizer.submitToPlanner(visit.getLocation());

            TimeWindowedVisit timeWindowedVisit = new TimeWindowedVisit();
            TimeWindowedVisit timeWindowedVisit = new TimeWindowedVisit(visit.getId(),     
                  planningLocation, visit.getLoad(),visit.getStart(), visit.getEnd(), 
                  visit.getServiceDuration());

            planningVisits.add(timeWindowedVisit);
      });

    //create TWVRP
    TimeWindowedVehicleRoutingSolution solution = new TimeWindowedVehicleRoutingSolution();
    solution.setId(jobId);
    solution.setDepotList(planningDepots);
    solution.setVisitList(planningVisits);
    solution.setVehicleList(planningVehicles);

    return solution;
}

public void solve(UUID jobId) {
    if (!planRepository.isResolved(jobId)) {
        logger.info("Starting solver");

        TimeWindowedVehicleRoutingSolution solution = null;
        TimeWindowedVehicleRoutingSolution timeWindowedVehicleRoutingSolution = find(jobId);
        
        try {
            SolverJob<TimeWindowedVehicleRoutingSolution, UUID> solverJob = 
                           solverManager.solve(jobId, timeWindowedVehicleRoutingSolution);

            solution = solverJob.getFinalBestSolution();
            save(jobId, solution);

        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
    } else
        logger.info("This job already has a solution");
}

对不起，书法的事，英语不是我的语言。

Answer 1

非常感谢杰弗里，我应用了你的建议，找到了我问题的根源。感谢您的帮助！

我将对所发生的事情进行评论，以防对某人有用：碰巧我在计算距离时使用了OptaWeb的示例，该示例使用GrahHopper来实现这一目的，默认情况下它返回最小距离，这是计算与时间一样远的原因。通过引入时间窗口，我打破了比分：

Math.max(customer.getReadyTime(),
previousDepartureTime + customer.distanceFromPreviousStandstill())

我的分数被打破了，因为我没有对所有变量使用相同的转换，即TW：就绪时间和出发时间以分钟为单位并乘以千，而距离以毫秒为单位。

null

当距离回到我身边时：

• 距离:641263

因此我的分数被打破了。

我所做的是将我所有的时间变量转换为毫秒：

null