Jsprit giving wrong solutions in case of multiday routing while routing orders with time window

PROBLEM STATEMENT:

I have a use case where I am trying to run routing on 3 orders(each order has its own service time and its own time window).
I want to run routing on these 3 orders where the driver takes a break after every 14 hours(840 mins) and the break duration is of 10 hrs (600 mins)

Following are the details of the 3 orders:

The column delsertime indicates delivery service time.
The columns starttime and endtimes indicate the time window of the order i.e. the order shall be delivered only in this time window

Since this case is for multiday routing I intend to add a custom multibreak and swap constraint to the builder.
I have implemented this in the following way:-
JOB BUILDER:-

jobs =  jspritRoutingService.getJspritJobs(routingProblem, isContainsWeightLimit, weightSkillMap, maxReturnTime);

The Time Window is added in the following way:-

int startTime = routingUtils.convertStringTimeToMinutes(order.getStartTime());
int endTime = routingUtils.convertStringTimeToMinutes(order.getEndTime());
if (startTime > endTime) {
   throw new RuntimeException(" ========== Invalid Slot Id " + order.getOrderId() + " Start " + order.getStartTime() + " End " + order.getEndTime());
}
jobBuilder.addTimeWindow(startTime, endTime);

com.graphhopper.jsprit.core.problem.job.Delivery jspritJobService = (com.graphhopper.jsprit.core.problem.job.Delivery) jobBuilder.build();
jobs.add(jspritJobService);

JSPRIT BUILDER :

 Jsprit.Builder vraBuilder = Jsprit.Builder.newInstance(vrp)
                .setProperty(Jsprit.Parameter.THREADS, jspritThreadCount.toString())
                .setProperty(Jsprit.Parameter.FIXED_COST_PARAM, "2.0");
        VariationCoefficientTermination prematureTermination;
        if(routingProblem.isDynamicRoutingProblem()){
            vraBuilder.setProperty(Jsprit.Parameter.CONSTRUCTION, "best_insertion");
        }
        // if problem is complex, try getting results faster
        if (!isLoopOptimizationProblem(routingProblem)) {
            prematureTermination = new VariationCoefficientTermination(40, 0.001);
        } else {
            vraBuilder.setProperty(Jsprit.Parameter.ITERATIONS, "10000");
            prematureTermination = new VariationCoefficientTermination(100, 0.001);
        }
        if (minimumLoadUtilizationConstraint.isMinCapacityUtilConstraintActive(routingProblem)) {
            // if minimum load utilization constraint is required, set objective function in the problem builder
            Map<String, RoutingFleet> fleetIdMap = routingProblem.getFleets().stream().collect(Collectors.toMap(RoutingFleet::getFleetId, Function.identity()));
            Map<String, RoutingOrder> jobIdMap = routingProblem.getJobs().stream().collect(Collectors.toMap(ro -> ro.getOrderId().toString(), Function.identity()));
            vraBuilder.setObjectiveFunction(getSolutionCalculator(vrp, jobIdMap, routingProblem, fleetIdMap));
        } else if(singleBreakActive.get()){
            log.trace("Applying single break constraint RequestId {}", requestId);
            Map<String, RoutingFleet> fleetIdMap = routingProblem.getFleets().stream().collect(Collectors.toMap(RoutingFleet::getFleetId, Function.identity()));
            vraBuilder.setObjectiveFunction(getSolutionCalculatorForSingleBreakActive(vrp, fleetIdMap, requestId));
        }

        boolean isMultipleBreakConstraintActive = multipleBreakConstraint.isMultipleBreakConstraintActive(routingProblem);
        boolean isDriverSwapEnabled = driverSwapConstraint.isDriverSwapEnabled(routingProblem);
        if (isMultipleBreakConstraintActive || isDriverSwapEnabled) {      //// MULTI BREAK AND SWAP CASE
            StateManager stateManager = new StateManager(vrp);
            StateId timeStateId = stateManager.createStateId("time");
            stateManager.addStateUpdater(new TimeUpdater(stateManager, costMatrix, timeStateId));
            ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);
            vraBuilder.addCoreStateAndConstraintStuff(true);
            constraintManager.addConstraint(new BreakNSwapTimeConstraintsService(costMatrix, stateManager, timeStateId, routingProblem.getBreakTimeDuration(), routingProblem.getMaxWorkingTimeBeforeBreak(), routingProblem.getDriverSwapTime(), routingProblem.getMaxWorkingTimePerDay()), ConstraintManager.Priority.CRITICAL);
            vraBuilder.setStateAndConstraintManager(stateManager, constraintManager);
        }

        VehicleRoutingAlgorithm vra = vraBuilder.buildAlgorithm();

        vra.setPrematureAlgorithmTermination(prematureTermination);
        vra.addListener(prematureTermination);
        TimeTermination timeTermination = new TimeTermination(480000); // 8 minutes
        vra.addTerminationCriterion(timeTermination);
        vra.addListener(timeTermination);
        UnassignedJobReasonTracker reasonTracker = new UnassignedJobReasonTracker();
        vra.addListener(reasonTracker);
        Collection<VehicleRoutingProblemSolution> solutions = vra.searchSolutions();

PROBLEM :-

As given in the input orders every order has its own start time and end time(i.e. the order shall be delivered only in that specific time window). Upon checking the vrp, the jobs object take correct time windows and correct service time but in the solution, one of the jobs is taking an unusually long service time.
When I am adding a custom input of break and swap constraint the end time of one of the jobs is computed wrongly

For eg:

  1. One of the jobs (say job1) has a time window from 300 to 960 minutes and we select the route for three days. We pass an array of time windows for three days i.e. 300-960, 1740-2400, 3180-3840.
  2. The service time for the job1 is 28 mins
    Following is the solution obtained:

±-------------------------------------------------------------------------------------------------------------------------------+
| detailed solution |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| route | vehicle | activity | job | arrTime | endTime | costs |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 1 | 29 1 | start | - | undef | 1 | 0 |
| 1 | 29 1 | delivery | 1 | 447 | 478 | 553722 |
| 1 | 29 1 | delivery | 3 | 483 | 513 | 559269 |
| 1 | 29 1 | delivery | 2 | 529 | 1768 | 571546 |
| 1 | 29 1 | end | - | 2214 | undef | 1131311 |
±-------------------------------------------------------------------------------------------------------------------------------+

As observed in the solution, the second job for which the time window was from 05:00 to 16:00 and the service time was 28 mins, the job is starting at 529 mins and is ending on the next day 1768. While it should have been 529 + 28 = 557.

Also this issue arises only when I am trying to add the following custom constraint:-

constraintManager.addConstraint(new BreakNSwapTimeConstraintsService(costMatrix, stateManager, timeStateId, routingProblem.getBreakTimeDuration(), routingProblem.getMaxWorkingTimeBeforeBreak(), routingProblem.getDriverSwapTime(), routingProblem.getMaxWorkingTimePerDay()), ConstraintManager.Priority.CRITICAL);

This particular constraint in the builder is causing the issue. On removing this constraint the solution comes out to be correct sometimes but not always. There have been cases where the solution was wrong even when this constrant was removed.

I also tried to add vehicle time window constraint as a hard constraint but that also gave the same result

The BreakNSwapTimeConstraintsService.java :

public class BreakNSwapTimeConstraintsService implements HardActivityConstraint {
   public BreakNSwapTimeConstraintsService(VehicleRoutingTransportCostsMatrix costsMatrix, 
   StateManager stateManager, StateId timeStateId, double breakTime, double breakAfterMinutes , 
  double swapTime, double swapTimeEveryMinutes) {
       this.costsMatrix = costsMatrix;
       this.stateManager=stateManager;
       this.timeStateId= timeStateId;
       this.breakTime= breakTime;
       this.breakAfterMinutes= breakAfterMinutes;
       this.swapTime=swapTime;
       this.swapTimeEveryMinutes=swapTimeEveryMinutes;
   }

   private final VehicleRoutingTransportCostsMatrix costsMatrix;
   private final StateManager stateManager;
   private final StateId timeStateId;
   private final double breakTime;
   private final double breakAfterMinutes;
   private final double swapTime;
   private final double swapTimeEveryMinutes;



Can you please advise on which step is going wrong which is resulting in this issue.

Please post whole code of BreakNSwapTimeConstraintsService class and would be nice if you post results with waiting time column.

Hi Tomas, I have added the complete code of the class

I see only class open curly bracket, but not closing one. And there is only constructor and class properties, but not body. That is not whole code.

public class BreakNSwapTimeConstraintsService implements HardActivityConstraint {
    public BreakNSwapTimeConstraintsService(VehicleRoutingTransportCostsMatrix costsMatrix, StateManager stateManager, StateId timeStateId, double breakTime, double breakAfterMinutes , double swapTime, double swapTimeEveryMinutes) {
        this.costsMatrix = costsMatrix;
        this.stateManager=stateManager;
        this.timeStateId= timeStateId;
        this.breakTime= breakTime;
        this.breakAfterMinutes= breakAfterMinutes;
        this.swapTime=swapTime;
        this.swapTimeEveryMinutes=swapTimeEveryMinutes;
    }

    private final VehicleRoutingTransportCostsMatrix costsMatrix;
    private final StateManager stateManager;
    private final StateId timeStateId;
    private final double breakTime;
    private final double breakAfterMinutes;
    private final double swapTime;
    private final double swapTimeEveryMinutes;


    @Override
    public HardActivityConstraint.ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
        if(newAct.getTheoreticalLatestOperationStartTime() ==0.0 || newAct.getTheoreticalEarliestOperationStartTime() == 0.0){
            return HardActivityConstraint.ConstraintsStatus.FULFILLED;
        }
        double prevToNewTime=getTime(prevAct.getLocation(),newAct.getLocation());
        double newToNextTime=getTime(newAct.getLocation(),nextAct.getLocation());

        Double routeTimeToPrev = stateManager.getRouteState(iFacts.getRoute(), timeStateId, Double.class);

        if (routeTimeToPrev == null) routeTimeToPrev = 0.0;
        double routeTimePrevToNew = prevToNewTime;
        double routeTimeToNew = newAct.getEndTime();
        double routeTimeNewToNext = newToNextTime;

        double vehicleStartTime=iFacts.getRoute().getStart().getEndTime();

        int numberOfBreaksRequiredToNew = (int) ((routeTimeToPrev + routeTimePrevToNew) / breakAfterMinutes);
        int numberOfBreaksRequiredToNext = (int) ((routeTimeToNew + routeTimeNewToNext) / breakAfterMinutes);

        double workingTimeWithBreaksToNew = routeTimeToPrev + routeTimePrevToNew + (numberOfBreaksRequiredToNew * breakTime);
        int numberOfSwapRequiredToNew = (int) (workingTimeWithBreaksToNew / swapTimeEveryMinutes);

        double workingTimeWithBreaksToNext = routeTimeToNew + routeTimeNewToNext + (numberOfBreaksRequiredToNext * breakTime);
        int numberOfSwapRequiredToNext = (int) (workingTimeWithBreaksToNext / swapTimeEveryMinutes);


        double arrivalTimeWithBreaksNSwapsNewAct = vehicleStartTime + routeTimeToPrev + routeTimePrevToNew + (numberOfBreaksRequiredToNew * breakTime) + (numberOfSwapRequiredToNew * swapTime);
        double arrivalTimeWithBreaksNSwapsNextAct = vehicleStartTime + routeTimeToNew + routeTimeNewToNext + (numberOfBreaksRequiredToNext * breakTime) + (numberOfSwapRequiredToNext * swapTime);

        boolean newActArrivalWindowBreached = arrivalTimeWithBreaksNSwapsNewAct > newAct.getTheoreticalLatestOperationStartTime();
        boolean nextActArrivalWindowBreached = arrivalTimeWithBreaksNSwapsNextAct > nextAct.getTheoreticalLatestOperationStartTime();

        if(newActArrivalWindowBreached || nextActArrivalWindowBreached)
            return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED;

        return HardActivityConstraint.ConstraintsStatus.FULFILLED;


    }

    private double getTime(Location from, Location to) {
        return costsMatrix.getTransportTime(from,to,0,null,null);
    }

}

Try dump out waiting time on route. It looks like the vehicle waits in prev location for next window to open.

Powered by Discourse