Vehicle does not take break in a route that ends later than the break time window

Hi,

I am testing with the break feature again and have encountered the following issue.

The small vrp is defined at the end of the post. Basically I have one vehicle with time window 0~10 and two services with no time window and each with service time 5. The vehicle has a break with time window 5~5 and service time 1. Thus, obviously the vehicle is not able to do both services and take the break because that will break the time window constraint of the vehicle. What I expect is that the vehicle does one service and stops with no break. However, to my surprise, the solution is that the vehicle does two services and stops with no break.

Is this a bug, or do I have any misunderstanding with break?

Best regards,
He

    VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
            .build();
    VehicleImpl v1 = VehicleImpl.Builder.newInstance("v1")
            .setType(type)
            .setReturnToDepot(true)
            .setStartLocation(Location.newInstance(0, 0))
            .setEarliestStart(0)
            .setLatestArrival(10)
            .setBreak(
                    Break.Builder.newInstance("break")
                            .setServiceTime(1)
                            .addTimeWindow(5, 5)
                            .build()
            )
            .build();

    Service s1 = Service.Builder.newInstance("s1").setLocation(Location.newInstance(0, 0))
            .setServiceTime(5)
            .build();
    Service s2 = Service.Builder.newInstance("s2").setLocation(Location.newInstance(0, 0))
            .setServiceTime(5)
            .build();

    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
            .addJob(s1).addJob(s2)
            .addVehicle(v1)
            .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
            .build();

    VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(vrp).buildAlgorithm();
    VehicleRoutingProblemSolution s = Solutions.bestOf(algorithm.searchSolutions());
    SolutionPrinter.print(vrp, s, SolutionPrinter.Print.VERBOSE);
1 Like

This is unexpected behaviour and seems to be a bug. Would you mind to post it as bug in the issue tracker? Thanks a lot, @jie31best.

it seems to me that it is due to the logic in BreakScheduling:

it does not handle properly the case when 1) the vehicle has a break; 2) the route end time is after the break time window; and 3) the break cannot be inserted into the route.

I am trying to fix this.

I have added the following else{} in informJobInserted() of BreakScheduling, which removes job2insert from inRoute in the case that the break cannot be added to the route even though the route ends later than the break time window.

            if(!(iData instanceof InsertionData.NoInsertionFound)){
                ...
            }
            else {
                removed = inRoute.getTourActivities().removeJob(job2insert);
                if(removed){
                    logger.trace("ruin: {}", job2insert.getId());
                    stateManager.removed(job2insert,inRoute);
                    stateManager.reCalculateStates(inRoute);
                }
            }

However, apparently this is not good enough, because this will remove the job from the vrp for good. I will need to find a way to add the job to the collection of unassigned jobs, but I am not sure how.

@stefan is this the way to go? If so, how can I add the job to the collection of unassigned jobs? Thanks!

Best regards,
He

Hello
I have had the same problem, checking I could find that when applying the break.

InsertionData iData = breakInsertionCalculator.getInsertionData (route, aBreak, route.getVehicle (), route.getDepartureTime (), route.getDriver (), Double.MAX_VALUE);

In BreakScheduling.java

Checking that i found a state:
ConstraintsStatus status = hardActivityLevelConstraint.fulfilled (insertContext, prevAct, breakAct2Insert, nextAct, prevActStartTime);

In BreakInsertionCalculator.java

When you do not insert the break it is because it returns NOT_FULLFILLET_BREAK, I try modify (Its possible not good but work in my case) Evaluating the hours of departure and entry to the services, not only with the end of route to apply break but eliminate the constraint in BreakInsertionCalculator.java

for (Location location : locations) {
breakAct2Insert.setLocation(location);
breakAct2Insert.setTheoreticalEarliestOperationStartTime(breakToInsert.getTimeWindow().getStart());
breakAct2Insert.setTheoreticalLatestOperationStartTime(breakToInsert.getTimeWindow().getEnd());
//DF MODIFY
double partida = prevAct.getArrTime();
if (prevAct.getArrTime() < prevAct.getTheoreticalEarliestOperationStartTime())
partida = prevAct.getTheoreticalEarliestOperationStartTime();
if (partida > (breakToInsert.getTimeWindow().getEnd())) {
breakThis = false;
continue;
}
double arribo = nextAct.getArrTime();
if (nextAct.getArrTime() < nextAct.getTheoreticalEarliestOperationStartTime())
arribo = nextAct.getTheoreticalEarliestOperationStartTime();
if (prevAct.getEndTime() <= breakToInsert.getTimeWindow().getEnd() && arribo >= breakToInsert.getTimeWindow().getStart()) {

// ConstraintsStatus status = hardActivityLevelConstraint.fulfilled(insertionContext, prevAct, breakAct2Insert, nextAct, prevActStartTime);
// if (status.equals(ConstraintsStatus.FULFILLED)) {
// from job2insert induced costs at activity level
double additionalICostsAtActLevel = softActivityConstraint.getCosts(insertionContext, prevAct, breakAct2Insert, nextAct, prevActStartTime);
double additionalTransportationCosts = additionalTransportCostsCalculator.getCosts(insertionContext, prevAct, nextAct, breakAct2Insert, prevActStartTime);
if (additionalICostsAtRouteLevel + additionalICostsAtActLevel + additionalTransportationCosts < bestCost) {
bestCost = additionalICostsAtRouteLevel + additionalICostsAtActLevel + additionalTransportationCosts;
insertionIndex = actIndex;
bestLocation = location;
}
breakThis = false;
// } else if (status.equals(ConstraintsStatus.NOT_FULFILLED)) {
// breakThis = false;
// }
} else {
breakThis = false;
}
}

And now Insert Break always in the route that ends later than the break window

Hi @dante_fuster,

Thanks a lot for your idea, but I have tried your modification to BreakInsertionCalculator and it doesn’t seem to solve my issue.

Best regards,
He

what I am trying these days is that, in ServiceInsertionCalculator (and also ShipmentInsertionCalculator), after the check of the hard activity constraint status, I add a new check such that, if it fails, status will be set to ConstraintsStatus.NOT_FULFILLED.

the new check is to check if the insertion of the new activity will make the insertion of the break into the route impossible. it consists of the following steps:

  1. check if new vehicle has break;
  2. if yes, check if the break has already been inserted;
  3. if not, check if new route end time after the insertion of the new activity is later than break time window;
  4. if yes, check if the break can be inserted into the route with the new activity in it.

in step 3), I need a new state updater for vehicle dependent route end time to obtain the route end time with the new vehicle before the insertion of the new activity, and another state updater for vehicle dependent future waiting times to obtain the future waiting time of the next activity with the new vehicle. with those two, and after calculating the delay in the next activity end time, I will be able to get the new route end time after the insertion of the new activity and compare with the break time window end time.

in step 4), I am currently stuck here. I try to use the BreakInsertionCalculator in the following way:

i) firstly I construct a route which represents the current route after the insertion of the new activity;
ii) then I call breakInsertionCalculator.getInsertionData() to get the insertion data, and
iii) if it is InsertionData.NoInsertionFound, I set status to ConstraintsStatus.NOT_FULFILLED, and so the insertion of the new activity at the current position will be rejected.

however, it seems I need to update some states for the constructed route between steps i) and ii), such as LATEST_OPERATION_START_TIME of the activities (and maybe others, I am not sure), but I am not sure how…

@stefan, what do you think of the above approach? does it look promising?

Thanks.

Best regards,
He

Hello
you comment the state an the IF?

hmm, it seems the problem of updating states in step 4) can be resolved by calling stateManager.reCalculateStates() for the constructed route before step ii) and then calling the same method again for the current route after step ii).

and now this issue seems to be fixed. I will make a PR later. @stefan