jsprit代价计算

 

总方案计算

private SolutionCostCalculator getObjectiveFunction(final VehicleRoutingProblem vrp, final double maxCosts) {
    if (objectiveFunction != null) return objectiveFunction;

    SolutionCostCalculator solutionCostCalculator = new SolutionCostCalculator() {
        @Override
        public double getCosts(VehicleRoutingProblemSolution solution) {
            double costs = 0.;

            for (VehicleRoute route : solution.getRoutes()) {
                costs += route.getVehicle().getType().getVehicleCostParams().fix;
                boolean hasBreak = false;
                TourActivity prevAct = route.getStart();
                for (TourActivity act : route.getActivities()) {
                    if (act instanceof BreakActivity) hasBreak = true;
                    costs += vrp.getTransportCosts().getTransportCost(prevAct.getLocation(), act.getLocation(), prevAct.getEndTime(), route.getDriver(), route.getVehicle());
                    costs += vrp.getActivityCosts().getActivityCost(act, act.getArrTime(), route.getDriver(), route.getVehicle());
                    prevAct = act;
                }
                costs += vrp.getTransportCosts().getTransportCost(prevAct.getLocation(), route.getEnd().getLocation(), prevAct.getEndTime(), route.getDriver(), route.getVehicle());
                if (route.getVehicle().getBreak() != null) {
                    if (!hasBreak) {
                        //break defined and required but not assigned penalty
                        if (route.getEnd().getArrTime() > route.getVehicle().getBreak().getTimeWindow().getEnd()) {
                            costs += 4 * (maxCosts * 2 + route.getVehicle().getBreak().getServiceDuration() * route.getVehicle().getType().getVehicleCostParams().perServiceTimeUnit);
                        }
                    }
                }
            }
            for(Job j : solution.getUnassignedJobs()){
                costs += maxCosts * 2 * (11 - j.getPriority());
            }
            return costs;
        }
    };
    return solutionCostCalculator;
}

 

 单个插入点，插入位置评估计算 -> (localActivityInsertionCostsCaculator.java)：

  public InsertionData getInsertionData(final VehicleRoute currentRoute, final Job jobToInsert, final Vehicle newVehicle, double newVehicleDepartureTime, final Driver newDriver, final double bestKnownCosts) {
      JobInsertionContext insertionContext = new JobInsertionContext(currentRoute, jobToInsert, newVehicle, newDriver, newVehicleDepartureTime);
      Service service = (Service) jobToInsert;
      int insertionIndex = InsertionData.NO_INDEX;

      TourActivity deliveryAct2Insert = activityFactory.createActivities(service).get(0);
      insertionContext.getAssociatedActivities().add(deliveryAct2Insert);

      /*
      check hard constraints at route level
       */
      InsertionData noInsertion = checkRouteContraints(insertionContext, constraintManager);
      if (noInsertion != null) return noInsertion;

      Collection<HardConstraint> failedActivityConstraints = new ArrayList<>();

      /*
      check soft constraints at route level
       */
      double additionalICostsAtRouteLevel = softRouteConstraint.getCosts(insertionContext);

      double bestCost = bestKnownCosts;
      additionalICostsAtRouteLevel += additionalAccessEgressCalculator.getCosts(insertionContext);
TimeWindow bestTimeWindow = null;

      /*
      generate new start and end for new vehicle
       */
      Start start = new Start(newVehicle.getStartLocation(), newVehicle.getEarliestDeparture(), Double.MAX_VALUE);
      start.setEndTime(newVehicleDepartureTime);
      End end = new End(newVehicle.getEndLocation(), 0.0, newVehicle.getLatestArrival());

      TourActivity prevAct = start;
      double prevActStartTime = newVehicleDepartureTime;
      int actIndex = 0;
      Iterator<TourActivity> activityIterator = currentRoute.getActivities().iterator();
      boolean tourEnd = false;
      while(!tourEnd){
          TourActivity nextAct;
          if(activityIterator.hasNext()) nextAct = activityIterator.next();
          else{
              nextAct = end;
              tourEnd = true;
          }
          boolean not_fulfilled_break = true;
	for(TimeWindow timeWindow : service.getTimeWindows()) {
              deliveryAct2Insert.setTheoreticalEarliestOperationStartTime(timeWindow.getStart());
              deliveryAct2Insert.setTheoreticalLatestOperationStartTime(timeWindow.getEnd());
              ActivityContext activityContext = new ActivityContext();
              activityContext.setInsertionIndex(actIndex);
              insertionContext.setActivityContext(activityContext);
              ConstraintsStatus status = fulfilled(insertionContext, prevAct, deliveryAct2Insert, nextAct, prevActStartTime, failedActivityConstraints, constraintManager);
              if (status.equals(ConstraintsStatus.FULFILLED)) {
                  double additionalICostsAtActLevel = softActivityConstraint.getCosts(insertionContext, prevAct, deliveryAct2Insert, nextAct, prevActStartTime);
                  double additionalTransportationCosts = activityInsertionCostsCalculator.getCosts(insertionContext, prevAct, nextAct, deliveryAct2Insert, prevActStartTime);
                  if (additionalICostsAtRouteLevel + additionalICostsAtActLevel + additionalTransportationCosts < bestCost) {
                      bestCost = additionalICostsAtRouteLevel + additionalICostsAtActLevel + additionalTransportationCosts;
                      insertionIndex = actIndex;
                      bestTimeWindow = timeWindow;
                  }
                  not_fulfilled_break = false;
              } else if (status.equals(ConstraintsStatus.NOT_FULFILLED)) {
                  not_fulfilled_break = false;
              }
	}
          if(not_fulfilled_break) break;
          double nextActArrTime = prevActStartTime + transportCosts.getTransportTime(prevAct.getLocation(), nextAct.getLocation(), prevActStartTime, newDriver, newVehicle);
          prevActStartTime = Math.max(nextActArrTime, nextAct.getTheoreticalEarliestOperationStartTime()) + activityCosts.getActivityDuration(nextAct,nextActArrTime,newDriver,newVehicle);
          prevAct = nextAct;
          actIndex++;
      }
      if(insertionIndex == InsertionData.NO_INDEX) {
          InsertionData emptyInsertionData = new InsertionData.NoInsertionFound();
          for (HardConstraint c : failedActivityConstraints) {
              emptyInsertionData.addFailedConstrainName(c.getClass().getSimpleName());
          }
          return emptyInsertionData;
      }
      InsertionData insertionData = new InsertionData(bestCost, InsertionData.NO_INDEX, insertionIndex, newVehicle, newDriver);
      deliveryAct2Insert.setTheoreticalEarliestOperationStartTime(bestTimeWindow.getStart());
      deliveryAct2Insert.setTheoreticalLatestOperationStartTime(bestTimeWindow.getEnd());
      insertionData.getEvents().add(new InsertActivity(currentRoute, newVehicle, deliveryAct2Insert, insertionIndex));
      insertionData.getEvents().add(new SwitchVehicle(currentRoute,newVehicle,newVehicleDepartureTime));
      insertionData.setVehicleDepartureTime(newVehicleDepartureTime);
      return insertionData;
  }

 

一个节点选择好一个最优插入点后，需要评估对整体方案的影响

计算插入一个节点后的代价，用来比较各个unsignedJobs的打分：
static double score(Job unassignedJob, InsertionData best, InsertionData secondBest, ScoringFunction scoringFunction){
    if (best == null) {
        throw new IllegalStateException("cannot insert job " + unassignedJob.getId());
    }
    double score;
    if (secondBest == null) { //either there is only one vehicle or there are more vehicles, but they cannot load unassignedJob
        //if only one vehicle, I want the job to be inserted with min iCosts
        //if there are more vehicles, I want this job to be prioritized since there are no alternatives
        score = (11 - unassignedJob.getPriority()) * (Integer.MAX_VALUE - best.getInsertionCost()) + scoringFunction.score(best, unassignedJob);
    } else {
        score = (11 - unassignedJob.getPriority()) * (secondBest.getInsertionCost() - best.getInsertionCost()) + scoringFunction.score(best, unassignedJob);
    }
    return score;
}